Elias delta koodi

Elias delta -koodi on Peter Eliasin kehittämä yleinen koodi positiivisten kokonaislukujen koodaamiseen.

Koodaus

Numeron N koodausalgoritmi:

Count - merkitsevien bittien määrä luvun binääriesityksessä . $L$ $N$
Count - merkitsevien bittien määrä luvun binääriesityksessä . $M$ $L$
Kirjoita muistiin nollia ja yksi yksikkö. $M-1$
Liitä - luvun binääriesityksen vähiten merkitsevät bitit ilman merkittävintä ( ). $L_{2}$ $M-1$ $L$ $2^{{M-1}}$
Liitä - luvun binääriesityksen vähiten merkitsevät bitit ilman merkittävintä ( ). $N_2$ $L-1$ $N$ $2^{{L-1}}$

Muuten tämä algoritmi voidaan kuvata seuraavasti:

Count - merkitsevien bittien määrä luvun binääriesityksessä . $L$ $N$
Koodaa Elias - gammakoodilla (γ(L)). $L$
Lisää luvun binääriesitys ilman alkulukua. $N$

Eli sekä delta- että Elias-gammakoodissa luku on koodattu eksponenttiksi (luvun kapasiteetti - merkitsevien bittien määrä) ja mantissaksi (todella merkitseväksi bitiksi), mutta gammakoodissa eksponentti kirjoitetaan unaarimuoto , ja deltakoodissa siihen sovelletaan gammakoodausta uudelleen. $L$ $N_2$

Esimerkki numeron 10 koodauksesta:

Luvun binääriesityksessä on 4 merkitsevää bittiä ( ). $N=10=1010_{2}$ $L = 4$
Luvun binääriesityksessä on 3 merkitsevää bittiä ( ). $L=4=100_{2}$ $M = 3$
Kirjoitamme nollan ja yhden yksikön → . $M-1 = 2$ 001
Lisätään luvun bitit ilman suurinta yksikköä → . $L$ 00
Lisätään luvun bitit ilman suurinta yksikköä → . $N$ 010
Tulos - 00100010.

Ensimmäisen 17 numeron koodauksen tulokset (vertailun vuoksi näytetään myös gammakoodi):

N		L		M	delta koodi		Pituus, bitti	Arvioitu todennäköisyys	gamma koodi		Pituus, bitti
N		L		M	γ(L)	$N_2$	Pituus, bitti	Arvioitu todennäköisyys	$L$	$N_2$	Pituus, bitti
yksi	$1_{2}$	yksi	$1_{2}$	yksi	yksi		yksi	1/2	yksi		yksi
2	$10_{2}$	2	$10_{2}$	2	01 0	0	neljä	1/16	01	0	3
3	$11_{2}$	2	$10_{2}$	2	01 0	yksi	neljä	1/16	01	yksi	3
neljä	$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	kymmenen	5	1/32	001	kymmenen	5
7	$111_{2}$	3	$11_{2}$	2	01 1	yksitoista	5	1/32	001	yksitoista	5
kahdeksan	$1000_{2}$	neljä	$100_{2}$	3	001 00	000	kahdeksan	1/256	0001	000	7
9	$1001_{2}$	neljä	$100_{2}$	3	001 00	001	kahdeksan	1/256	0001	001	7
kymmenen	$1010_{2}$	neljä	$100_{2}$	3	001 00	010	kahdeksan	1/256	0001	010	7
yksitoista	$1011_{2}$	neljä	$100_{2}$	3	001 00	011	kahdeksan	1/256	0001	011	7
12	$1100_{2}$	neljä	$100_{2}$	3	001 00	100	kahdeksan	1/256	0001	100	7
13	$1101_{2}$	neljä	$100_{2}$	3	001 00	101	kahdeksan	1/256	0001	101	7
neljätoista	$1110_{2}$	neljä	$100_{2}$	3	001 00	110	kahdeksan	1/256	0001	110	7
viisitoista	$1111_{2}$	neljä	$100_{2}$	3	001 00	111	kahdeksan	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

Alkuperäisten arvojen lisäkäsittelyllä delta-koodia voidaan käyttää myös nolla- ja negatiivisten kokonaislukujen koodaamiseen (katso: Elias Gamma Code#Generalization ).

Dekoodaus

Algoritmi numeron dekoodaamiseksi Elias-deltakoodista:

Count - nollien määrä tulovirrassa ensimmäiseen nollia asti. $M$
Yhtä seuraa luvun vähiten merkitsevä bitti , lue ne ja lisää arvo tulokseen . Jos syöttövirran bitit kirjoitetaan korkeasta matalaan, niin ensimmäinen nollasarjan jälkeinen voidaan lukea osana luvun binääriesitystä , jolloin ei ole tarpeen lisätä erillisessä vaiheessa . $M$ $L$ $2^{M}$ $L$ $L$ $2^{M}$
Seuraavaksi tulevat luvun vähiten merkitsevät bitit , lue ne ja lisää arvo tulokseen . $L-1$ $N$ $2^{{L-1}}$

Esimerkki bittisekvenssin 001010001 dekoodaamisesta :

Lue virrasta 001 ja määritä, että alussa on 2 etunollaa ( ). $M = 2$
Lue seuraavat bitit virrasta → 01 ; se antaa . $M = 2$ $L=2^{M}+01_{2}=4+1=5$
Lue seuraavat bitit virrasta → 0001 ; se antaa . $L-1 = 4$ $N=2^{{L-1}}+0001_{2}=16+1=17$

Tehokkuus

Numeroilla 2, 3, 8…15 deltakoodi on pidempi kuin gammakoodi, numeroilla 1, 4…7, 16…31 deltakoodin pituus on sama kuin gammakoodin pituus, kaikilla muilla. numerot delta - koodi on lyhyempi kuin gamma - koodi . Näin ollen deltakoodi on sitä vähemmän kannattava kuin gammakoodi, mitä epätasaisempi koodattujen lukujen todennäköisyysjakauma ja sitä todennäköisemmin niiden arvot lähestyvät nollaa.

Katso myös

Elias Omega Code

Kirjallisuus

D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin. Osa 1. Häviöttömät pakkausmenetelmät. Luku 1. Muistittomien tietolähteiden koodaus. Mantissien ja eksponentien erottelu // Tietojen pakkausmenetelmät. Arkistointien järjestely, kuvan ja videon pakkaus. - M .: Dialog-MEPhI, 2002. - S. 23-24. — 384 s. — ISBN 5-86404-170-x .
Universaalit koodisanajoukot ja kokonaislukujen esitykset // IEEE Transactions on Information Theory : päiväkirja. - 1975. - maaliskuu ( osa 21 , nro 2 ) . - s. 194-203 . - doi : 10.1109/tit.1975.1055349 .