Unární kódování

Unární kódování je kódování, které zakóduje přirozené číslo n pomocí n po sobě následujících jedniček a jednou nulou (pokud je přirozené číslo chápáno jako nezáporné celé číslo) nebo jako n − 1 po sobě následujících jedniček následovaných jednou nulou (když přirozené číslo je chápáno jako kladné celé číslo). Například 5 je reprezentována 111110 nebo 11110. Některé varianty tohoto kódování prohazují 0 a 1. Nuly a jedničky můžeme považovat za zaměnitelné bez ztráty obecnosti. Unární kódování tvoří prefixový kód.

0	1	0	1
1	2	10	01
2	3	110	001
3	4	1110	0001
4	5	11110	00001
5	6	111110	000001
6	7	1111110	0000001
7	8	11111110	00000001
8	9	111111110	000000001
9	10	1111111110	0000000001

Unární kódování je optimálním kódováním pro následující diskrétní pravděpodobnostní rozdělení

:\operatorname{P}(n) = 2^{-n}\,

pro n=1,2,3,....

Kódujeme-li po symbolech, pak je unární kódování optimální pro každé geometrické rozdělení

:\operatorname{P}(n) = (k-1)k^{-n}\,

pro každé k ≥ φ = 1.61803398879…, zlatý řez, nebo více obecně, pro každé diskrétní rozdělení pro které platí

:\operatorname{P}(n) \ge \operatorname{P}(n+1) + \operatorname{P}(n+2)\,

pro n=1,2,3,....

Přestože je kódování optimální pro výše zmíněné pravděpodobnosti, Golombovo kódování dosahuje lepšího kompresního poměru pro geometrická rozdělení, protože nepovažuje vstupní symboly za nezávislé. Ze stejného důvodu funguje aritmetické kódování lépe pro obecná rozdělení pravděpodobnosti.

Modifikované unární kódování je použito v UTF-8. Unární kódování je také použito v kódováních, která používají schémata pro dělení kódových slov jako např. +more Golombovo kódování.

Reference

Kategorie:Teorie kódování