Eliášův delta kód

Eliasův delta kód je univerzální kód pro kódování kladných celých čísel, který vyvinul Peter Elias.

Kódování

Algoritmus pro kódování čísla N:

Počet – počet platných bitů v binární reprezentaci čísla . $L$ $N$
Počet – počet platných bitů v binární reprezentaci čísla . $M$ $L$
Zapište si nuly a jednu jednotku. $M-1$
Append - nejméně významné bity binární reprezentace čísla bez nejvýznamnějšího ( ). $L_{2}$ $M-1$ $L$ $2^{{M-1}}$
Append - nejméně významné bity binární reprezentace čísla bez nejvýznamnějšího ( ). $N_2$ $L-1$ $N$ $2^{{L-1}}$

Jinak lze tento algoritmus popsat následovně:

Počet – počet platných bitů v binární reprezentaci čísla . $L$ $N$
Kódujte pomocí Eliasova gama kódu (γ(L)). $L$
Přidejte binární reprezentaci čísla bez úvodního. $N$

To znamená, že v delta i Elias gama kódu je číslo zakódováno jako exponent (kapacita čísla - počet platných bitů) a mantisa (ve skutečnosti významné bity), ale v gama kódu je exponent zapsán v unární forma a v delta kódu je na něj opět aplikováno gama kódování. $L$ $N_2$

Příklad kódování čísla 10:

Binární reprezentace čísla má 4 platné bity ( ). $N=10=1010_{2}$ $L=4$
Binární reprezentace čísla má 3 platné bity ( ). $L=4=100_{2}$ $M=3$
Píšeme nulu a jednu jednotku → . $M-1=2$ 001
Sečteme bity čísla bez nejvyšší jednotky → . $L$ 00
Sečteme bity čísla bez nejvyšší jednotky → . $N$ 010
Výsledek - 00100010.

Výsledky kódování prvních 17 čísel (pro srovnání je zobrazen také gama kód):

N		L		M	delta kód		Délka, kousek	Odhadovaná pravděpodobnost	gama kód		Délka, kousek
N		L		M	γ(L)	$N_2$	Délka, kousek	Odhadovaná pravděpodobnost	$L$	$N_2$	Délka, kousek
jeden	$1_{2}$	jeden	$1_{2}$	jeden	jeden		jeden	1/2	jeden		jeden
2	$10_{2}$	2	$10_{2}$	2	01 0	0	čtyři	1/16	01	0	3
3	$11_{2}$	2	$10_{2}$	2	01 0	jeden	čtyři	1/16	01	jeden	3
čtyři	$100_{2}$	3	$11_{2}$	2	01 1	00	5	1/32	001	00	5
5	$101_{2}$	3	$11_{2}$	2	01 1	01	5	1/32	001	01	5
6	$110_{2}$	3	$11_{2}$	2	01 1	deset	5	1/32	001	deset	5
7	$111_{2}$	3	$11_{2}$	2	01 1	jedenáct	5	1/32	001	jedenáct	5
osm	$1000_{2}$	čtyři	$100_{2}$	3	001 00	000	osm	1/256	0001	000	7
9	$1001_{2}$	čtyři	$100_{2}$	3	001 00	001	osm	1/256	0001	001	7
deset	$1010_{2}$	čtyři	$100_{2}$	3	001 00	010	osm	1/256	0001	010	7
jedenáct	$1011_{2}$	čtyři	$100_{2}$	3	001 00	011	osm	1/256	0001	011	7
12	$1100_{2}$	čtyři	$100_{2}$	3	001 00	100	osm	1/256	0001	100	7
13	$1101_{2}$	čtyři	$100_{2}$	3	001 00	101	osm	1/256	0001	101	7
čtrnáct	$1110_{2}$	čtyři	$100_{2}$	3	001 00	110	osm	1/256	0001	110	7
patnáct	$1111_{2}$	čtyři	$100_{2}$	3	001 00	111	osm	1/256	0001	111	7
16	$10 000_{2}$	5	$101_{2}$	3	001 01	0000	9	1/512	00001	0000	9
17	$10001_{2}$	5	$101_{2}$	3	001 01	0001	9	1/512	00001	0001	9

S dodatečným zpracováním původních hodnot lze delta kód použít také ke kódování nulových a záporných celých čísel (viz: Elias Gamma Code#Generalization ).

Dekódování

Algoritmus pro dekódování čísla z Eliasova delta kódu:

Počet - počet nul ve vstupním proudu do první. $M$
Po jedničce následují nejméně významné bity čísla , přečti je a přičti hodnotu k výsledku . Pokud jsou bity ve vstupním toku zapsány od vysoké k nízké, pak první po úvodní řadě nul lze číst jako součást binární reprezentace čísla , v takovém případě není nutné přidávat v samostatném kroku . $M$ $L$ $2^{M}$ $L$ $L$ $2^{M}$
Dále následují nejméně významné bity čísla , přečtěte je a přidejte hodnotu k výsledku . $L-1$ $N$ $2^{{L-1}}$

Příklad dekódování bitové sekvence 001010001 :

Přečtěte si z proudu 001 a určete, že na začátku jsou 2 úvodní nuly ( ). $M=2$
Přečtěte si další bity z proudu → 01 ; to dává . $M=2$ $L=2^{M}+01_{2}=4+1=5$
Přečíst další bity z proudu → 0001 ; to dává . $L-1=4$ $N=2^{{L-1}}+0001_{2}=16+1=17$

Účinnost

Pro čísla 2, 3, 8…15 je delta kód delší než gama kód, pro čísla 1, 4…7, 16…31 je délka delta kódu stejná jako délka gama kódu, pro všechny ostatní čísla, delta kód je kratší než gama kód. V souladu s tím je delta kód tím méně ziskový než gama kód, čím nerovnoměrnější je rozložení pravděpodobnosti kódovaných čísel a tím pravděpodobnější jsou jejich hodnoty, když se blíží nule.

Viz také

Elias Omega Code

Literatura

D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin. Sekce 1. Bezeztrátové kompresní metody. Kapitola 1. Kódování bezpamětových datových zdrojů. Separace mantis a exponentů // Metody komprese dat. Uspořádání archivátorů, komprese obrazu a videa. - M .: Dialog-MEPhI, 2002. - S. 23-24. — 384 s. — ISBN 5-86404-170-x .
Univerzální sady kódových slov a reprezentace celých čísel // IEEE Transactions on Information Theory : deník. - 1975. - březen ( roč. 21 , č. 2 ). - S. 194-203 . - doi : 10.1109/tit.1975.1055349 .