Optimal kodlash xususiyatlari:
1. Eng maqbul kodlash sxemasi bo'lsin.
Isbot (qarama-qarshi)
Ushbu mulk buzilsin, ya'ni. p t\u003e Pj & | (3, |\u003e | p y |).
a / kodlarni o'zgartirish orqali olingan (3, ... va p y, ya'ni a /: a - "RU; va) - "R (..)
Keyin
Biz bu bilan ziddiyatga duch keldik va, - optimal kodlash sxemasi.
2. a, eng maqbul kodlash sxemasi bo'lsin
Keyin, maksimal uzunlikdagi elementar kodlar orasida ikkitasi bor, faqat oxirgi bitda farq qiladi.Keyin alifbo tartibida kodlash sxemasiehtimollik taqsimoti uchun eng maqbuldir
O'z-o'zini to'g'rilash kodlariL:
Tarkibga qarshi kod shovqin manbai bo'lgan C aloqa kanali bo'lsin.Kodlash F chaqirdi jahlga qarshi, yoki xatolarni tuzatish kodlash, yoki o'z-o'zini to'g'rilash, agar quyidagi shart bajarilsa: qayerda S dan A *, KgB A \u003d IN = {0,1}.
Xatolar turlari:
1. Bitni almashtirish xatosi: 0 -\u003e 1; 1 ^ 0.
2. Ishdan bo'shatish xatosi: 0 -\u003e L; 1 -\u003e L.
3. Tushirishni kiritish xatosi: L - "0; L ^ 1.
Aloqa kanali har bir turdagi xatolar sonining yuqori bahosi bilan tavsiflanadi, bu uzunlikdagi xabarni uzatish paytida mumkin. Xarakterli bo'lgan aloqa kanalini ko'rib chiqing. Uzunlik xabarida bit almashtirishning mumkin bo'lgan bitta xatosi p
Xatoni tuzatish uchun xabar bilan birga uzatish kerak qo'shimcha ma'lumot.
Xato aniqlash kodi:
Boshqa raqamlarning yig'indisiga teng bo'lgan bitni qo'shib, aniq raqam bilan raqamlarda kamida bitta xato bo'lganligini tekshirishingiz mumkin.
Huffman kodi: Huffman kodi eng maqbul kodlashdir. Qurilish qoidalariHuffman kodining qurilishi alifboni siqishga asoslangan.Keling, ikkita mumkin bo'lgan harflarni ajratmaslikka rozilik beraylik a t _ x va va hokazoAlifbo harflarini qayta tartiblash A xortib borayotgan ehtimolliklarda. Olingan alifbo yana bir marta siqiladi. Alfavitni olaylik A 2: A 2 \u003d t-2 va hokazo, alifboga siqish AT _ 2 : | D t _ 2 | \u003d 2. Ushbu alifboning ikkita harfiga 0 va 1 kodlarini tayinlaymiz.Alifboning barcha harflarining kodlari aniqlansin A) _ x, alifbosi harflari kodlarini aniqlang Aj_ 2.Alifbo harflari Alifbo ichiga kiradigan Aj_ 2 A y._ x bir xil kodga ega.
Shunday qilib, A m _ 2, ..., A.
Shunday qilib, boshlab AT _ 2 , asl alifboning A kodi qurilgan bo'lib, ushbu kod prefiks bo'ladi va shuning uchun uni ajratish mumkin. Kodlar to'plami (0,1) ikki harfli alfavit uchun maqbuldir _ 2 da. Har bir qadamda eng yaxshi kodlash sxemasi eng maqbul kodlash sxemasidan yana tuziladi va natijada olingan kod maqbuldir.Huffman kodi buyurtma qilingan ehtimolliklar uchun ishlatiladi.Misol: Ehtimol taqsimot bilan alifbo uchun optimal kodlash sxemasini tuzing /? \u003d (0.2; 0.2; 0.19; 0.12; 0.11; 0.09; 0.09) (ehtimolliklar oshmaydi). Qaror
1. Ehtimollarni jadvalning birinchi ustuniga kamayish tartibida yozing.
2. So'nggi ikkita ehtimollikni qo'shing: 0.09 + 0.09 \u003d 0.18.
3. Qolgan ehtimolliklarni pasayish tartibida tartiblang va natijani uchinchi ustunga yozing.
4. Yana ikkita oxirgi sonlarni qo'shing va tartiblang, beshinchi ustunga yozing va hokazo, bittagina qo'shilgan 0,6 va 0,4 dan ikkitagina raqam qolmaguncha.
5. Yuqori raqamga "0" kodi, pastki qismida - "1" beriladi.
6. Endi biz o'ngdan chapga siljiymiz: mavjud raqamlarga biz bir xil kodni (0.4 - "1") tayinlaymiz va 0.6 raqamiga qo'shadiganlarga "00" (yuqori) va "kodlarni tayinlaymiz. 01 "(pastki qismida).
7. Xuddi shunday, biz birinchi ustunga etib boramiz va vektorning barcha elementlari uchun kodlarni yaratamiz r (11-jadvalga qarang).
Do'stlaringiz bilan baham: |