|
Samarali kodlashOrtiqchalikni bartaraf etishga qaratilgan protseduralar.
Samarali kodlashning asosiy vazifasi manba xabarini uzatish uchun o'rtacha ikkilik elementlarning minimal sonini ta'minlashdir. Bunday holda, ma'lum bir modulyatsiya tezligida, maksimal xabarlar soni uzatiladi va shuning uchun maksimal ma'lumot uzatish tezligi.
Alifbosi bo'lgan diskret xabarlar manbai bo'lsin ...
Berilgan manbadan kelgan xabarlarni ikkilik, yagona kod bilan kodlashda sizga kerak bo'ladi har bir xabarni kodlash uchun ikkilik elementlar.
Agar ehtimolliklar manbaning barcha xabarlarining paydo bo'lishi teng bo'lsa, u holda manbaning entropiyasi (yoki bitta xabardagi o'rtacha ma'lumot miqdori) maksimal va teng bo'ladi ...
Bunday holda, har bir manba xabari axborot sig'imiga ega bit, va kodlash (tashish) uchun kamida ikkilik kombinatsiyani talab qilishi aniq elementlar. Har bir ikkilik element, bu holda, 1 bit ma'lumotni olib yuradi.
Agar alifboning bir xil hajmida xabarlar bir xil ehtimolga ega bo'lmasa, ma'lumki, manbaning entropiyasi kamroq bo'ladi.
...
Agar, bu holda, xabarni tashish uchun foydalaning -bitli kod birikmalari, keyin kod kombinatsiyasining har bir ikkilik elementi uchun 1 bitdan kam bo'ladi.
Ortiqchalik paydo bo'ladi, uni quyidagi formula bilan aniqlash mumkin
...
Yagona kod bilan kodlashda kombinatsiyaning bitta ikkilik elementi uchun o'rtacha ma'lumot miqdori
...
Misol
Rus alifbosining 32 ta harfini kodlash uchun, agar ular teng darajada bo'lsa, 5 bitli kod birikmasi kerak. BARCHA statistik munosabatlar hisobga olinsa, haqiqiy entropiya har bir harf uchun taxminan 1,5 bitni tashkil qiladi. Bu holda ortiqcha ekanligini ko'rsatish oson
,
Agar bitta elementning o'rtacha yuki juda kichik bo'lsa, savol tug'iladi, bitta xabarni tashish uchun zarur bo'lgan elementlarning o'rtacha sonini kamaytirish mumkinmi va buni qanday qilib samarali bajarish mumkin?
Ushbu muammoni hal qilish uchun bir xil bo'lmagan kodlar qo'llaniladi.
Bunda kattaroq hajmdagi maʼlumotni oʻz ichiga olgan xabarni uzatish uchun uzunroq kodli soʻz tanlanadi, kichik hajmdagi maʼlumotga ega boʻlgan xabarni uzatish uchun esa qisqa kodli soʻzlar qoʻllaniladi.
Xabarda mavjud bo'lgan ma'lumotlarning miqdori paydo bo'lish ehtimoli bilan belgilanishini hisobga olsak
, siz ushbu bayonotni takrorlashingiz mumkin.
Voqea ehtimoli yuqori bo'lgan xabar uchun qisqaroq kombinatsiya tanlanadi va aksincha, nodir xabar uzoq kombinatsiya bilan kodlanadi.
Bu. o'rtacha, har bir xabar uchun kamroq birlik elementlari sarflanadi uniformaga qaraganda.
Agar telegraf tezligi doimiy bo'lsa, u holda bitta xabarni uzatish uchun o'rtacha kamroq vaqt sarflanadi.
Bu shuni anglatadiki, bir xil telegraf tezligida bir xil kodlashdan ko'ra ko'proq xabarlar vaqt birligida uzatiladi, ya'ni. axborot uzatishning yuqori tezligi ta'minlanadi.
Berilgan manbadan xabarlarni uzatish uchun zarur bo'lgan yagona elementlarning minimal soni o'rtacha qancha?
Bu savolga javob Shennon tomonidan berilgan.
Shennon buni ko'rsatdi
1. Ikkilik kod bilan xabarni kodlash mumkin emas, shunda kod so'zining o'rtacha uzunligi xabar manbasining entropiyasidan son jihatdan kamroq edi ... , qayerda ...
2. Kodlash usuli mavjud bo'lib, unda kod so'zining o'rtacha uzunligi manba entropiyasidan biroz farq qiladi.
Tegishli kodlash usulini tanlash qoladi.
Optimal bir xil bo'lmagan kodlardan foydalanish samaradorligini baholash mumkin:
Yagona kodlash bilan solishtirganda samarali kodlash usullaridan foydalanganda har bir xabar uchun ikkilik elementlar sonining kamayishini tavsiflovchi statistik siqish nisbati ... Shuni hisobga olib , yozishingiz mumkin ... Kcc yagona kod bilan 1 dan oraliqda joylashgan , eng yaxshi kodlash usuli bilan.
Nisbiy samaradorlik nisbati
- samarali kodlashning turli usullari samaradorligini solishtirish imkonini beradi.
Noto'g'ri kodlarda kod birikmalarini ajratish muammosi paydo bo'ladi. Ushbu muammoni hal qilish prefiks kodlaridan foydalanish orqali ta'minlanadi.
Prefiksqisqaroq so'z boshqa uzunroq kodli so'zning boshi bo'lmagan kod deb ataladi. Prefiks kodlari har doim noyob tarzda dekodlanadi.
Keling, kod so'zlari to'plami uchun kod daraxti tushunchasini kiritaylik.
Kod so'zlari to'plamining aniq grafik tasvirini xabarlar va binar daraxtning barg tugunlari o'rtasida yozishmalarni o'rnatish orqali olish mumkin. Ikkilik kod daraxtining namunasi rasmda ko'rsatilgan. bitta.
Shakl 1. Ikkilik kodlar daraxtiga misol
Daraxtning ildizidan birinchi tartibli tugunlarga boradigan ikkita novda kod so'zining birinchi belgisi sifatida "0" va "1" o'rtasidagi tanlovga mos keladi: chap novda "0" ga va o'ng shoxga mos keladi. “1”. Birinchi tartib tugunlaridan keladigan ikkita shox kod so‘zlarning ikkinchi belgisiga to‘g‘ri keladi, chapdagisi “0”, o‘ngdagisi esa “1” va hokazo. Ko‘rinib turibdiki, har bir kodli so‘zning belgilar ketma-ketligi belgilab beradi. daraxtning ildizidan ko'rib chiqilayotgan xabarga mos keladigan so'nggi tugunga o'tish uchun zarur qoidalar.
Rasmiy ravishda kodli so'zlar oraliq tugunlarga ham tayinlanishi mumkin. Misol uchun, 1-rasmdagi ikkinchi tartibli oraliq tugunga 11 kodli so'z berilishi mumkin, bu tugun tomonidan yaratilgan so'nggi tugunlarga mos keladigan kod so'zlarning dastlabki ikkita belgisiga mos keladi. Biroq, oraliq tugunlarga mos keladigan kod so'zlarini xabarlarni ifodalash uchun ishlatib bo'lmaydi, chunki bu holda kod prefiksiga bo'lgan talab buziladi.
Faqat barg tugunlari xabarlarga mos kelishi talabi kod so'zlarning hech biri uzunroq kod so'zining boshiga (prefiks) mos kelmasligi shartiga teng.
Kod so'zlari ba'zi ikkilik kodlar daraxtining turli terminal cho'qqilariga mos keladigan har qanday kod prefiks hisoblanadi, ya'ni yagona dekodlangan.
Do'stlaringiz bilan baham: |
