Cvičení 6

Témata:

1. Test jednoznačné dekódovatelnosti
2. Kraftova nerovnost
3. Průměrná délka a redundance kódu
4. Rozšíření zdrojové abecedy, optimální kód
5. RLE

Test jednoznačné dekódovatelnosti

Ukázali jsme si na kódech

• 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.

Prošli jsme i konstrukci slova, které není jednoznačně dekódovatelné (pokud takové existuje).

Kraftova nerovnost

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

• existuje jednoznačně dekódovatelný 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?
• existuje jednoznačně dekódovatelný kód z abecedy se 4 symboly do abecedy se 2 symboly, který má kódy symbolů s délkami 1, 2, 2 a 2?

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

Následoval příklad na průměrnou délku a redundnaci kódu

• vstupní abeceda {A, B, C, D}, kód C₂ při pravděpodobnostech P(A) = 2/5, P(B) = P(C) = P(D) = 1/5 (získany například ze vstupu AABCDDBACA).

Rozšíření zdrojové abecedy

Dále jsme si na tomtéž příkladě řeklii, co nám může přinést rozšíření zdrojové abecedy - optimáln(ějš)í kód.

RLE

Nakonec jsme si vyzkoušeli run length encoding (RLE) na krátkém příkladě

• aaabbbrakkkkkkaaaaadaaaaabbbbbbrrrrrrra, symbol příznaku -, k = 1 nebo k = 4.

Naprogramujte si:

1. Průměrná délka kódu
2. Redundance kódu
3. RLE (kódování i dekódování)