|
Misol: 6 ta harfdan iborat alifboda ehtimoli 0 ga teng : 4; 0: 2; 0: 2; 0: 1; 0: 05; 0: 05. Qurilish uchun uchlik
|
| bet | 4/7 | | Sana | 05.12.2023 | | Hajmi | 61,92 Kb. | | #111549 |
Bog'liq yip7fgoVs88CUK-UkxQi0zZmR1AQGJvr (1) Misol: 6 ta harfdan iborat alifboda ehtimoli 0 ga teng : 4; 0: 2; 0: 2; 0: 1; 0: 05; 0: 05. Qurilish uchun uchlik Huffman kodi, biz alifbomizga nol ehtimollik bilan boshqa xayoliy harf qo'shishimiz va jadvalda ko'rsatilgandek davom etishimiz kerak:
|
Harf raqami
|
Ehtimollar va kodlar
|
|
|
|
|
|
|
|
|
|
|
Manba alifbosi A
|
Siqilgan alifbo A 1
|
Siqilgan alifbo A 2
|
|
|
|
|
|
|
|
0: 4 - 0
|
0: 4 - 0
|
0: 4 - 0
|
|
|
|
|
|
|
|
|
|
0: 2 - 2
|
0: 2 - 2
|
0: 4 - 1
|
|
|
|
|
|
|
|
|
|
0: 2 - 10
|
0: 2 - 10
|
0: 2 - 2
|
|
|
|
|
|
|
|
|
|
0: 1 - 11
|
0: 2 - 11
|
|
|
|
|
|
|
|
|
|
|
|
0: 05 - 120
|
|
|
|
|
|
|
|
|
|
|
|
|
0: 05 - 121
|
|
|
|
|
|
|
|
|
|
|
|
|
0 - ---
|
|
|
|
|
|
|
|
|
|
| |
Teorema: har qanday n raqamlar k 1 ; k 2 ; : : : ; k n, tengsizlikni qondirish
|
|
|
+
|
|
|
+ : : : +
|
|
|
|
|
|
|
k
|
|
k
|
|
|
|
|
|
|
|
|
|
|
|
6 1 (∗ ):
|
|
|
|
m
|
|
m
|
|
|
|
|
|
|
Har qanday k n raqamlar ba'zilarining xabar uzunligi m-tushunarli
|
|
|
|
|
|
|
|
|
|
|
|
mkn
|
|
|
|
|
|
|
|
|
|
|
|
|
mos keladigan kod n alifbo harflari n elementar signallarni qabul qilish ketma-ketligi m mumkin bo'lgan qiymatlar.
Bu bayonot ( ∗ ) birinchi marta 1949 yilda amerikalik olim L. Kraft tomonidan isbotlangan va keyinchalik B. Makmillan tomonidan umumlashtirilgan, shuning uchun tengsizlik ( ∗ ) ko'pincha Kraft-McMillan tengsizligi deb ataladi. Tengsizlikdan foydalanish ( ∗ ) quyidagi natijani olishingiz mumkin:
Teorema: uchun asosiy kodlash teoremasi m-ic kodlari.Har qanday kodlash usuli yordamida m-mchny kodining o'rtacha soni k Xabarning bir harfi uchun elementar signallar hech qachon nisbatlar jurnalidan kam bo'lishi mumkin emas Hm, qayerda H- xabarning bir harfining entropiyasi. Biroq, agar bloklar etarlicha uzun bo'lsa, uni har doim bu qiymatga o'zboshimchalik bilan yaqinlashtirish mumkin N harflar.
Natija: Agar aloqa liniyasi orqali vaqt birligida uzatish mumkin bo'lsa L elementar signallarni qabul qilish m turli ma'nolar, keyin tezlik xabar almashish yoqilgan
tezlik, o'zboshimchalik bilan yaqin v(lekin kichikroq v) mumkin. Qiymat C=L jurnal m faqat xususiyatlariga bog'liq aloqa liniyalari, maxraj bo'lganda H uzatiladigan xabarni tavsiflaydi. Qiymat C bildiradi eng katta raqam vaqt birligida aloqa liniyasi orqali uzatilishi mumkin bo'lgan axborot birliklari. U aloqa liniyasining tarmoqli kengligi deb ataladi.
Uchun samarali foydalanish kanal (yuk koeffitsienti l→1 ortishi), uni kirishdagi axborot manbai bilan muvofiqlashtirish kerak. Shannon tomonidan taklif qilingan kanal uchun kodlash teoremalariga asoslanib, bunday moslashuv shovqinsiz va shovqinsiz kanallar uchun ham mumkin.
Interferentsiyasiz kanal uchun kodlash teoremasi. Agar xabar manbai [bit/sek] sig'imga ega bo'lsa va aloqa kanali [bit/sek] sig'imga ega bo'lsa, u holda xabar aloqa kanali orqali o'rtacha tezlikda ma'lumot uzatiladigan tarzda kodlanishi mumkin. qiymatiga o'zboshimchalik bilan yaqin, lekin undan oshmasligi kerak.
Shennon, shuningdek, bunday kodlash uchun optimal kodlash deb nomlangan usulni taklif qildi. Keyinchalik, bunday kodlash g'oyasi Fano va Huffman asarlarida ishlab chiqilgan. Hozirgi vaqtda bunday kodlar amaliyotda keng qo'llaniladi (samarali va optimal kodlash).
Shovqinli kanal uchun Shennonning bevosita kodlash teoremasi.
Har qanday xabar manbasi ishlashi uchun [bps] dan kam o'tkazish qobiliyati[bps], o'zboshimchalik bilan kichik xato ehtimoli e bilan xabar manbai tomonidan yaratilgan barcha ma'lumotlarni uzatishni ta'minlash imkonini beruvchi kodlash usuli mavjud.
Shovqinli kanal uchun teskari kodlash teoremasi.
Agar xabar manbasining ishlashi kanal sig'imidan katta bo'lsa, ma'lumotni o'zboshimchalik bilan kichik xato ehtimoli bilan uzatish imkonini beruvchi kodlash usuli mavjud emas.
Shovqinli kanal uchun kodlash teoremasining isboti matematik jihatdan ancha katta, shuning uchun biz uning jismoniy tomonlarini umumiy muhokama qilish bilan cheklanamiz. amaliy qo'llash:
1. Teorema axborotni ishonchli uzatish bilan tizimning mumkin bo'lgan samaradorligining nazariy chegarasini belgilaydi. Teoremadan kelib chiqadiki, kanaldagi interferensiya uzatish aniqligiga cheklovlar qo'ymaydi. Cheklovlar faqat uzatish tezligiga qo'yiladi, bunda o'zboshimchalik bilan yuqori uzatish ishonchliligiga erishish mumkin.
Bunday holda, diskret kanalning ishonchliligi odatda bitta belgini noto'g'ri qabul qilish ehtimoli qiymati bilan baholanadi. Xatolik ehtimoli qanchalik past bo'lsa, kanalning ishonchliligi shunchalik yuqori bo'ladi. Ishonchlilik, o'z navbatida, shovqin immunitetini tavsiflaydi axborot tizimi.
Axborot uzatish tezligi tizimning samaradorligini tavsiflaydi.
2. Teorema ko'rsatilgan ideal uzatishni ta'minlaydigan kodlarni qurish usullari haqidagi savolga tegmaydi. Bunday kodlashning asosiy imkoniyatini asoslab, u aniq kodlarni ishlab chiqish uchun olimlarning sa'y-harakatlarini safarbar qildi.
3. O'tkazuvchanlik kengligigacha bo'lgan har qanday cheklangan ma'lumot uzatish tezligida, o'zboshimchalik bilan kichik xatolik ehtimoli faqat kodlangan belgilar ketma-ketligining davomiyligini cheksiz ko'payishi bilan erishiladi. Shunday qilib, shovqin mavjudligida xatosiz uzatish faqat nazariy jihatdan mumkin. Haddan tashqari uzun belgilar ketma-ketligini kodlashda xatolik ehtimoli juda past va etarlicha yuqori samaradorlik bilan ma'lumot uzatishni ta'minlash mumkin.
Kanal sig'imi C dan kam bo'lgan H xabar manbasining har qanday ishlashi uchun bunday kodlash usuli mavjud bo'lib, u xabar manbai tomonidan yaratilgan barcha ma'lumotlarni o'zboshimchalik bilan kichik xato ehtimoli bilan uzatishni ta'minlashga imkon beradi.
Garchi Shennon tomonidan taklif qilingan ushbu teoremaning isboti keyinchalik chuqurroq va qat'iyroq matematik taqdimotga duchor bo'lgan bo'lsa-da, uning g'oyasi o'zgarishsiz qoldi. Faqat kerakli kodlash usulining mavjudligi isbotlangan, buning uchun hamma uchun o'rtacha xato ehtimoli topiladi mumkin bo'lgan usullar kodlash va uni e ning o'zboshimchalik bilan kichik qiymatidan kichikroq qilish mumkinligini ko'rsating. Shu bilan birga, xato ehtimoli o'rtacha qiymatdan past bo'lgan kamida bitta kodlash usuli mavjud.
|
| |
