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 = 2k+b, pro 0 ≤ b ≤ 2k. 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 2k−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 = 22+1 zkrácené binární kódování přiřadí prvním třem symbolům (22-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 23 = 8 a tedy u = 2k-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 2k ≤ n ≤ 2k+1 symbolů, tak v kódování existuje takových u = 2k+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 24-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 < 2k−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 = 2k 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
