|
1101000010011011100010100110 …Belgilar bloklariga bo'linishi mumkin110, 10, 0, 10, 0, 110, 111, 0, 0, 0, 10, 10, 0, 110, …Dekodlash daraxtini qurish uchun quyidagi qoidaga muvofiq:
Shakl 10. Keyingi savol oqim (tezkor) dekodlash kodlari. Belgilarni ko'rsatish orqali avvalgisidan olingan kodni ko'rib chiqings1 \u003d 0; s2 \u003d 01; s3 \u003d 011; s4 \u003d 111. Deylik, biz ketma-ketlikni oldik 011111...111 ... Xabar matnini dekodlashning yagona usuli bu bitlarni guruhning oxiridan 3 ga guruhlash va oldin nolga teng guruhlarni tanlash, so'ngra dekodlashingiz mumkin. Bunday kodni noyob tarzda dekodlash mumkin, ammo darhol emas! Kod hal qilish uchun uzatish tugaguncha kutish kerak! Amalda ushbu yondashuv dekodlash tezligini inkor etadi (MakMillan teoremasi), shuning uchun darhol dekodlash usullarini izlash kerakXuddi shu belgini kodlashning ikkita usulini ko'rib chiqing, Sis1 \u003d 0; s2 \u003d 10; s3 \u003d 110; s4 \u003d 1110, s5 \u003d 1111,
Ushbu usul uchun dekodlash daraxti 10.III-rasmda keltirilgan
Shakl 10.III
Ikkinchi yo'l
s1 \u003d 00; s2 \u003d 01; s3 \u003d 100; s4 \u003d 110, s5 \u003d 111, Ushbu ketishning dekodlash daraxti 10.IV-rasmda ko'rsatilgan. Kod sifatini o'lchashning eng aniq usuli - bu xabarlar to'plamining o'rtacha uzunligi. Buning uchun har bir belgining kod uzunligini mos keladigan pi ehtimoli bilan ko'paytirilishini hisoblashingiz kerak. Bu butun kodning uzunligini beradi. Q belgilar alifbosi uchun o'rtacha L uzunlik kodining formulasi quyidagicha Bu erda pi - si belgisining paydo bo'lish ehtimoli, li - kodlangan belgining mos keladigan uzunligi. Samarali kod uchun L qiymati iloji boricha kichikroq bo'lishi kerak. Agar P1 \u003d 1/2, p2 \u003d 1/4, p3 \u003d 1/8, p4 \u003d 1/16 va p5 \u003d 1/16 bo'lsa, unda # 1 kod uchun biz kod uzunligining qiymatini olamizVa kod №2 uchunOlingan qiymatlar birinchi kodning afzalligini ko'rsatadi.
Agar alfavitdagi barcha so'zlarning paydo bo'lish ehtimoli bir xil bo'lsa, unda ikkinchi kod afzalroq bo'ladi. Masalan, pi \u003d 1/5 bilan kodning uzunligi # 1Va kodning uzunligi # 2Ushbu natija 2 ta kodning afzalligini ko'rsatadi. Shunday qilib, "yaxshi" kodni loyihalashda ramzlar ehtimolini hisobga olish kerakshakl 10.IVShakl 10.VLi belgi kodining chegara qiymatini belgilaydigan Kraft tengsizligini ko'rib chiqing. 2-asosda tengsizlik quyidagicha ifodalanadi Ushbu tengsizlik shuni ko'rsatadiki, alifboda juda ko'p qisqa belgilar bo'lishi mumkin emas, aks holda bu miqdor juda katta bo'ladi. Kraftning har qanday tezkor noyob dekodlash kodi uchun tengsizligini isbotlash uchun biz dekodlash daraxtini quramiz va matematik induksiya usulini qo'llaymiz. Agar daraxt 10.V rasmda ko'rsatilgandek bitta yoki ikkita bargga ega bo'lsa, unda shubhasiz tengsizlik haqiqatdir. Bundan tashqari, agar daraxtning ikkitadan ko'p barglari bo'lsa, unda biz uzun daraxt m ni ikkita kichik daraxtga ajratamiz. Induksiya printsipiga ko'ra, biz tengsizlikning balandligi m -1 yoki undan past bo'lgan har bir novda uchun to'g'ri deb hisoblaymiz. Induksiya printsipiga ko'ra, tengsizlikni har bir filialga qo'llash. K "va K" "novdalari kodlarining uzunligini belgilaylik. Daraxtning ikkita novdasi birlashtirilganda, ularning har biri uzunligi 1 ga ko'payadi, shuning uchun kodning uzunligi K '/ 2 va K' '/ 2 yig'indilaridan iboratTeorema isbotlanganMakmillan teoremasining isbotini ko'rib chiqing. Biz Kraftning tengsizligini soddalashtirilgan dekodlash kodlariga qo'llaymiz. Buning isboti har qanday K\u003e 1 son uchun raqamning n-chi kuchi n ning chiziqli funktsiyasidan kattaroq ekanligiga asoslanadi, bu erda n juda katta son. Biz Kraft tengsizligini n-darajaga ko'taramiz va ifodani yig'indisi sifatida ifodalaymiz
Bu erda Nk - k uzunlikdagi belgilar soni, yig'indisi n-sonli belgining minimal uzunligidan boshlanadi va maksimal nl uzunligi bilan tugaydi, bu erda l - kodlangan belgining maksimal uzunligi. Noyob dekodlash uchun talab shuni anglatadiki. Miqdor shaklda taqdim etilgan
Agar K\u003e 1 bo'lsa, unda tengsizlikning yolg'onga aylanishi uchun n ni etarlicha katta qilib qo'yish kerak. Shuning uchun, k<= 1; теорема Макмиллана доказанаKeling, Kraft tengsizligini qo'llashning bir nechta misollarini ko'rib chiqaylik. Uzunligi 1, 3, 3, 3 bo'lgan noyob dekodlangan kod bo'lishi mumkinmi? Ha, beri
1, 2, 2, 3 uzunliklar haqida nima deyish mumkin? Formulaga muvofiq hisoblang
Tengsizlik buzildi! Ushbu kodda juda ko'p qisqa belgilar mavjudNuqta kodlari (vergul kodlari) - bu 1 ta belgidan tashkil topgan kodlar, ularning barchasi 0 bo'lgan oxirgi belgidan tashqari 0 bilan tugaydi. Maxsus holatlardan biri bu kod
Do'stlaringiz bilan baham: |
