3.3.2 Kódování pomocí tabulky

 

Průvodce studiem
Zde si ukážeme, jak nalézt kód minimální délky pomocí tabulky. Tento postup je vhodný pro "ruční" výpočet.

 

Doba potřebná ke studiu

Přibližný čas, který strávíte studiem této kapitoly, je 20 - 30 minut.

 

Příklad

Zadání:
Zakódujme 4 znaky Huffmanovým kódem, známe-li pravděpodobnosti jejich výskytu, a spočítejme průměrnou délku kódového slova.

Znak Pravděpodobnost
E
 0,4
F
 0,2
G 0,2
H 0,2

Řešení:

Krok 1 - budeme postupně vytvářet tabulku.

  • V prvním sloupci jsou zdrojové znaky uspořádané podle pravděpodobnostního výskytu.
  • Sečteme poslední dvě pravděpodobnosti (provedeme redukci) a výsledek zařadíme podle velikosti mezi ostatní pravděpodobnosti - třetí sloupec - redukce je odlišena modrou barvou.
  • Znovu sečteme poslední dvě pravděpodobnosti a výsledek opět zařadíme podle velikosti - pátý sloupec.
  • Spodním dvěma znakům v každém sloupci přiřadíme kódové znaky 1 a 0.

 

E (0,4)
E (0,4)
G, H, F (0,6) 1
F (0,2)
G, H (0,4) 1
 E (0,4) 0
G (0,2) 1
 F (0,2) 0
H (0,2)
 0

 

Krok 2 - přiřazení kódových slov jednotlivým zdrojovým znakům.

  • Uděláme si novou tabulku, v prvním sloupci jsou všechny zdrojové znaky.
  • Dále budeme vycházet z předchozí tabulky a budeme postupovat od zadu. Znaky G, H, F mají přiřazenou 1 - ve druhém sloupci nově vytvářené tabulky budou mít hodnou 1 a znak E má přiřazenou 0 - ve druhém sloupci nově vytvářené tabulky bude mít hodnou 0. Tím je vyplněný druhý sloupec nové tabulky.
  • V předchozí tabulce se posuneme dopředu. Znaky G, H mají 1 - ve třetím sloupci nově vytvářené tabulky budou mít hodnou 1 a znak F má 0 ve třetím sloupci nově vytvářené tabulky bude mít hodnou 0. Tím je vyplněný třetí sloupec nové tabulky.
  • Posuneme se opět dopředu. Znak G má 1 - ve čtvrtém sloupci nově vytvářené tabulky bude mít hodnou 1 a znak H má 0 ve čtvrtém sloupci nově vytvářené tabulky bude mít hodnou 0.
  • V posledním sloupci nové tabulky jsou kódová slova pro jednotlivé zdrojové znaky.

 

E
 0

0
F
 1
 0
10
G
 1
 1 1
 111
H
 1
 1
 0
 110

Všiměte si také, že nám vyšel prefixový kód. Toto je vlastnost Huffmanova kódování. Toto kódování je tedy jednoznačně dekódovatelné.

Průměrná délka kódového slova je:

d* = 1x0,4 + 2x0,2 + 3x0,2 + 3x0,2 = 2

Předchozí | Další