Unární kódování

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledá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.

Příklady unárního kódování
n (nezáporné) n (kladné) Unární kód Inverze
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ř. Golombovo kódování.

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Unary coding na anglické Wikipedii.