Eliasovo gama kódování - Elias gamma coding

Eliasův γ kód nebo Eliasův gama kód je univerzální kód kódování kladných celých čísel vyvinutých Peter Elias.^[1]^{:197, 199} Používá se nejčastěji při kódování celých čísel, jejichž horní mez nelze předem určit.

Kódování

Chcete-li kódovat a číslo X ≥ 1:

Nechat ${ displaystyle N = lfloor log _ {2} x rfloor}$ být nejvyšší silou 2, kterou obsahuje, takže 2^N ≤ X < 2^N+1.
Vypracovat N tedy nulové bity
Připojit binární druh X, an N+ 1-bitové binární číslo.

Ekvivalentní způsob vyjádření stejného procesu:

Zakódovat N v unární; to je jako N nuly následované jednou.
Připojte zbývající N binární číslice X k tomuto zastoupení N.

Představovat číslo ${ displaystyle x}$ , Elias gamma (γ) používá ${ displaystyle 2 lfloor log _ {2} (x) rfloor +1}$ bity.^[1]^:199

Kód začíná ( implikovaná pravděpodobnost distribuce kódu je přidána kvůli jasnosti):

Číslo	Binární	γ kódování	Implikovaná pravděpodobnost
1 = 2⁰ + 0	`1`	`1`	1/2

2 = 2¹ + 0	`1 0`	`0 1 0`	1/8
3 = 2¹ + 1	`1 1`	`0 1 1`	1/8

4 = 2² + 0	`1 00`	`00 1 00`	1/32
5 = 2² + 1	`1 01`	`00 1 01`	1/32
6 = 2² + 2	`1 10`	`00 1 10`	1/32
7 = 2² + 3	`1 11`	`00 1 11`	1/32

8 = 2³ + 0	`1 000`	`000 1 000`	1/128
9 = 2³ + 1	`1 001`	`000 1 001`	1/128
10 = 2³ + 2	`1 010`	`000 1 010`	1/128
11 = 2³ + 3	`1 011`	`000 1 011`	1/128
12 = 2³ + 4	`1 100`	`000 1 100`	1/128
13 = 2³ + 5	`1 101`	`000 1 101`	1/128
14 = 2³ + 6	`1 110`	`000 1 110`	1/128
15 = 2³ + 7	`1 111`	`000 1 111`	1/128

16 = 2⁴ + 0	`1 0000`	`0000 1 0000`	1/512
17 = 2⁴ + 1	`1 0001`	`0000 1 0001`	1/512

Dekódování

Dekódování Eliasova gama kódovaného čísla:

Čtení a počítání 0 s ze streamu, dokud nedosáhnete prvních 1. Volejte tento počet nul N.
Vzhledem k tomu, který byl dosažen, je první číslicí celého čísla s hodnotou 2^N, přečtěte si zbývající N číslice celého čísla.

Použití

Gama kódování se používá v aplikacích, kde největší kódovaná hodnota není známa předem nebo dosud komprimovat data, ve kterých jsou malé hodnoty mnohem častější než velké hodnoty.

Gama kódování je stavebním kamenem v Eliasův delta kód.

Zobecnění

Kódování gama nekóduje nula ani záporná celá čísla. Jedním ze způsobů zpracování nuly je přidání 1 před kódováním a poté odečtení 1 po dekódování. Dalším způsobem je předpona každého nenulového kódu číslem 1 a poté kód nula jako jediná 0.

Jedním ze způsobů, jak kódovat všechna celá čísla, je nastavit a bijekce, mapování celých čísel (0, -1, 1, -2, 2, -3, 3, ...) na (1, 2, 3, 4, 5, 6, 7, ...) před kódováním. V softwaru se to nejsnadněji provádí mapováním nezáporných vstupů na liché výstupy a záporných vstupů na sudé výstupy, takže nejméně významný bit se stane invertovaným znamení bit:
${ displaystyle { begin {cases} x mapsto 2x + 1 & mathrm {when ~} x geq 0 x mapsto -2x & mathrm {when ~} x <0 end {cases}}}$

Exponenciální-Golombovo kódování stejně zobecňuje gama kód na celá čísla pomocí „plošší“ distribuce zákonů moci Golombovo kódování Zobecňuje unární kód. Zahrnuje vydělení čísla kladným dělitelem, obvykle mocninou 2, napsání gama kódu o jeden víc než kvocient a zbytek se zapíše do běžného binárního kódu.

Viz také

Reference

^ ^A ^b Elias, Peter (Březen 1975). "Univerzální sady kódových slov a reprezentace celých čísel". Transakce IEEE na teorii informací. 21 (2): 194–203. doi:10.1109 / tit.1975.1055349.

Další čtení

Sayood, Khalid (2003). "Kódy gama Levenstein a Elias". Příručka bezztrátové komprese. Elsevier. ISBN 978-0-12-620861-0.

[Elias-1] A ^b Elias, Peter (Březen 1975). "Univerzální sady kódových slov a reprezentace celých čísel". Transakce IEEE na teorii informací. 21 (2): 194–203. doi:10.1109 / tit.1975.1055349.

[1]