Cvičení 5

Témata:

1. Průměrná délka kódu, redundance
2. Kraft-MacMillanova nerovnost
3. Shannonova věta, optimalita kódu
4. Test jednoznačné dekódovatelnosti
5. RLE
6. MTF

Uvažovaná kódování

Vše jsme si ukazovali na následujících kódech:

• C₀ : {A, B, C, D} → {0, 1}, kde C₀(A) = 0, C₀(B) = 0, C₀(C) = 10, C₀(D) = 01;
• C₁ : {A, B, C, D} → {0, 1}, kde C₁(A) = 0, C₁(B) = 01, C₁(C) = 110, C₁(D) = 111;
• C₂ : {A, B, C, D} → {0, 1}, kde C₂(A) = 0, C₂(B) = 10, C₂(C) = 110, C₂(D) = 111;
• C₃ : {A, B, C, D} → {0, 1}, kde C₃(A) = 0, C₃(B) = 01, C₃(C) = 011, C₃(D) = 0111.

Průměrná délka a redundance kódu

Spočítali jsme průměrné délky a redundance kódu C₀ až C₂.

Kraft-Macmillanovy nerovnosti

Ukázali jsme si použítí Kraftovy nerovnosti - tj odpovědi na otázky typu:

• existuje jednoznačně dekódovatelný/prefixový kód z abecedy se 4 symboly do abecedy se 2 symboly, který má kódy symbolů s délkami 1, 2, 3 a 3? Souvisí s kódem C₂, jak?
• existuje jednoznačně dekódovatelný/prefixový kód z abecedy se 4 symboly do abecedy se 2 symboly, který má kódy symbolů s délkami 1, 1, 2 a 2? Souvisí s kódem C₀, jak?

Shanonova věta, optimalita kódu

Pospojovali jsme si dosavadní poznatky dohormady a ukázali si na nich praktický význam Shannonovy věty. Zmínili jsme si i blokové kódy a další drobnosti okolo.

Jednoznačná dekódovatelnost

U kódů výše jsme algoritmicky zkontrolovali jejich jednoznačnou dekódovatelnost.

RLE a MTF

Nakonec jsme si vyzkoušeli algoritmy Run Length Encoding (RLE) a Move To Front (MTF) na krátkém příkladě:

• AAABBBRAKKKKKKAAAAADAAAAABBBBBBRRRRRRRA
• (pro RLE symbol příznaku -, k = 1 nebo k = 4).

Naprogramujte si:

1. RLE (kódování i dekoódování)
2. MTF (kódování i dekoódování)
3. Test jednoznačné dekódovatelnosti