Zkrácené binární kódování

Zkrácené binární kódování je kódování typicky používané pro rovnoměrné rozdělení pravděpodobnosti s konečnou abecedou. Parametrem rozdělení je velikost abecedy n. Jde o obecnější variantu binárního kódování, kde n nemusí být mocninou o základu 2.

Nechť n = 2^k+b, pro 0 ≤ b ≤ 2^k. Pokud n je mocnina 2, můžeme si vybrat jednu ze dvou možných hodnot pro k; obě vytvoří stejný kód, který je identický se standardním binárním kódem.

Zkrácené binární kódování přiřadí prvním 2^k−b symbolům kódová slova o délce k a pak zbývajícím 2b symbolům přiřadí posledních 2b kódových slov délky k+1. Protože všechna kódová slova délky k+1 sestávají z nepoužitého kódového slova délky k, ke kterým byla připojena „0“ nebo „1“ je výsledný kód prefixový.

Příklad s n = 5

Pro abecedu {0, 1, 2, 3, 4}, n = 5 = 2²+1 zkrácené binární kódování přiřadí prvním třem symbolům (2²-1) kódová slova 00, 01 a 10. Poté přiřadí posledním dvěma symbolům 110 a 111, jsou délky tři, každé z nich obsahuje poslední nepoužité kódové slovo délky dva 11, ke kterému se přidá znak navíc.

Například pro n rovno 5 standardní binární kódování a zkrácené přiřadí tato kódová slova.

Kódové slovo10	Zkrácené binární k.	Kódové slovo			Standardní binární k.
0	0	0	0	0	0
1	1	0	0	1	1
2	2	0	1	0	2
3	Nepoužito	0	1	1	3
4	Nepoužito	1	0	0	4
5	Nepoužito	1	0	1	Nepoužito
6	3	1	1	0	Nepoužito
7	4	1	1	1	Nepoužito

Nejbližší větší mocnina dvou větší než n = 5 je 2³ = 8 a tedy u = 2^k-n = 8−5 = 3. Budeme tedy mít 3 nepoužitá kódová slova pro standardní binární kódování.

Když chceme poslat hodnotu 0 ≤ x < n, která je jedním z 2^k ≤ n ≤ 2^k+1 symbolů, tak v kódování existuje takových u = 2^k+1−n nepoužitých kódových slov.

Proces zakódování čísla x pro zkrácené binární kódování je takovýto:

• pokud je x menší než u zakódujte ho pomocí k bitů
• pokud je x větší nebo rovno u zakódujte hodnotu x+u pomocí k+1 bitu

Příklad s n = 10

Jiný příklad, zakódovat abecedu o velikosti n=10 (čísla mezi 0 a 9) vyžaduje k=4 bitů, ale v takto velké abecedě je 2⁴-10 = 6 nepoužitých kódových slov. Tedy pro všechny vstupní znaky menší než 6 zahodíme první bit, zatímco všechny vstupy větší nebo rovny 6 posuneme o 6 ke konci kódování. (Nepoužitá zakódování nejsou v tabulce.)

Vstupní hodnota	Posun	Hodnota posunu	Standardní binární k.	Zkrácené binární k.
0	0	0	0000	000
1	0	1	0001	001
2	0	2	0010	010
3	0	3	0011	011
4	0	4	0100	100
5	0	5	0101	101
6	6	12	0110	1100
7	6	13	0111	1101
8	6	14	1000	1110
9	6	15	1001	1111

Pro dekódování načteme prvních k-1 bitů, pokud rozkódováváme hodnotu menší než u, je dekódování hotovo. Pokud ne, načteme další bit (tedy k bitů) a odečteme u od výsledku.

Příklad s n = 7

Nakonec jeden z krajních případů: s n = 7 další mocnina 2 je 8 (skončíme u použití 3 bitů nebo 2 bitů pokud zahodíme nejvyšší bit) a u = 1:

Vstupní hodnota	Posun	Hodnota posunu	Standardní binární k.	Zkrácené binární k.
0	0	0	000	00
1	1	2	010	010
2	1	3	011	011
3	1	4	100	100
4	1	5	101	101
5	1	6	110	110
6	1	7	111	111

Poslední příklad ukazuje, že první nulový bit nemusí znamenat, že výsledný kód je kratší; pokud u < 2^k−1 některé delší kódy budou začínat nulovým bitem.

Pokud je n mocnina dvou, pak kódování můžeme provést pro dvě rozdílné hodnoty k. Oba vytvoří stejný výstup; výstupem prvního bude pro u = 2^k kód dlouhý k bitů pro všechny vstupy, zatímco výstupem druhého bude pro u = 0 kód o délce k+1 bit.

Odkazy

Reference

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

Související články

• Benfordův zákon
• Golombovo kódování