miniatura|Comparació de les longituds dels codis de Fibonacci, delta Elias i gamma. El codi Elias δ o codi Elias delta és un codi universal que codifica els nombres enters positius desenvolupat per Peter Elias.

Codificació Per codificar un número X ≥ 1:

Sigui N = ⌊log² X ⌋; sigui la potència més alta de 2 en X, de manera que 2N ≤ X < 2N +1 . Sigui L = ⌊log 2 N +1⌋ sigui la potència més alta de 2 en N +1, de manera que 2L ≤ N +1 < 2L +1 . Escriu L zeros, seguit de la representació binària de L +1 bits de N +1, seguida de tots els bits de X excepte el bit principal (és a dir, els últims N bits).

Una manera equivalent d'expressar el mateix procés:

Separa X en la potència més alta de 2 que conté (2N) i els N dígits binaris restants. Codifica N +1 amb codificació gamma Elias. Afegeix els N dígits binaris restants a aquesta representació de N + 1.

Per representar un nombre , Elias delta (δ) utilitza bits. Això és útil per a enters molt grans, on els bits de la representació codificada global acaben sent menys [dels que es podrien obtenir utilitzant la codificació gamma Elias ] a causa de la part de l'expressió anterior.

El codi comença utilitzant en lloc de : NombreNN+1Codificació δProbabilitat implícita1 = 200111/22 = 21 + 0120 1 0 01/163 = 21 + 1120 1 0 11/164 = 22 + 0230 1 1 001/325 = 22 + 1230 1 1 011/326 = 22 + 2230 1 1 101/327 = 22 + 3230 1 1 111/328 = 23 + 03400 1 00 0001/2569 = 23 + 13400 1 00 0011/25610 = 23 + 23400 1 00 0101/25611 = 23 + 33400 1 00 0111/25612 = 23 + 43400 1 00 1001/25613 = 23 + 53400 1 00 1011/25614 = 23 + 63400 1 00 1101/25615 = 23 + 73400 1 00 1111/25616 = 24 + 04500 1 01 00001/51217 = 24 + 1451/512 Per descodificar un enter codificat amb delta Elias:

Llegeix i compta zeros del flux fins que arribis al primer. Anomena aquest recompte de zeros L. Considerant que el que s'ha assolit és el primer dígit d'un enter, amb un valor de 2L, llegiu els L dígits restants de l'enter. Anomeneu aquest enter N + 1 i resteu-ne una per obtenir N. Poseu un u al primer lloc de la nostra sortida final, que representa el valor 2N. Llegeix i afegeix els següents N dígits.

Exemple:

001010011

1. 2 zeros inicials a 001

2. llegir 2 bits més, és a dir, 00101

3. descodificar N+1 = 00101 = 5

4. obtenir N = 5 − 1 = 4 bits restants per al codi complet, és a dir, '0011'

5. nombre codificat = 2 4 + 3 = 19

Aquest codi es pot generalitzar a zero o nombres enters negatius de les mateixes maneres descrites a la codificació gamma Elias.

Generalitzacions La codificació delta Elias no codifica zero ni enters negatius. Una manera de codificar tots els enters no negatius és sumar 1 abans de codificar i després restar 1 després de descodificar. Una manera de codificar tots els enters és configurar una bijecció, assignant tots els enters (0, 1, −1, 2, −2, 3, −3, ...) a enters estrictament positius (1, 2, 3, 4, 5, 6, 7, ...) abans de codificar. Aquesta bijecció es pot realitzar utilitzant la codificació "ZigZag" de Protocol Buffers (no s'ha de confondre amb el codi Zigzag ni amb la codificació d'entropia JPEG Zig-zag).

Referències

Categoria:Codificació Categoria:Compressió de dades