miniatura|Comparació de les longituds dels codis de Fibonacci, delta Elias i gamma. Codificació Elias o codificació gamma Elias és un codi universal que codifica nombres enters positius desenvolupat per Peter Elias. S'utilitza més habitualment quan es codifiquen nombres enters el límit superior dels quals no es pot determinar prèviament.
Codificació Per codificar un nombre x ≥ 1:
Deixa sigui la potència més alta de 2 que conté, de manera que 2N ≤ x < 2N +1 . Escriure zero bits, aleshores Afegeix la forma binària de , un nombre binari de -bit.
Una manera equivalent d'expressar el mateix procés:
Codificar en unari; és a dir, com a zeros seguits d'un u. Afegeix la resta dígits binaris de a aquesta representació de .
Per representar un nombre , Elias gamma (γ) utilitza bits.
El codi comença (s'afegeix la distribució de probabilitat implícita del codi per a més claredat): NumberBinaryγ encodingImplied probability1 = 20 + 0111/22 = 21 + 01 00 1 01/83 = 21 + 11 10 1 11/84 = 22 + 01 0000 1 001/325 = 22 + 11 0100 1 011/326 = 22 + 21 1000 1 101/327 = 22 + 31 1100 1 111/328 = 23 + 01 000000 1 0001/1289 = 23 + 11 001000 1 0011/12810 = 23 + 21 010000 1 0101/12811 = 23 + 31 011000 1 0111/12812 = 23 + 41 100000 1 1001/12813 = 23 + 51 101000 1 1011/12814 = 23 + 61 110000 1 1101/12815 = 23 + 71 111000 1 1111/12816 = 24 + 01 00000000 1 00001/51217 = 24 + 11/512
Descodificació Per descodificar un enter codificat amb gamma d'Elias:
Llegeix i compta els 0 del flux fins que arribis al primer 1. Anomena aquest recompte de zeros N. Considerant que el que s'ha assolit és el primer dígit de l'enter, amb un valor de 2N, llegiu els N dígits restants de l'enter.
Usos La codificació gamma s'utilitza en aplicacions on el valor codificat més gran no es coneix amb antelació o per comprimir dades en què els valors petits són molt més freqüents que els valors grans.
La codificació gamma pot ser més eficient pel que fa a la mida en aquestes situacions. Per exemple, tingueu en compte que, a la taula anterior, si es tria una mida fixa de 8 bits per emmagatzemar un nombre petit com el nombre 5, el binari resultant seria 00000101, mentre que la versió de bits variables amb codificació γ seria 00 1 01, necessitant 3 bits menys. Al contrari, valors més grans, com 254 emmagatzemats en una mida fixa de 8 bits, serien 11111110 mentre que la versió de bits variables amb codificació γ seria 0000000 1 1111110, necessitant 7 bits addicionals.
La codificació gamma és un element bàsic del codi delta Elias.
Generalitzacions La codificació gamma no codifica zeros ni nombres enters negatius. Una manera de gestionar el zero és sumar 1 abans de codificar i després restar 1 després de descodificar. Una altra manera és prefixar cada codi diferent de zero amb un 1 i després codificar el zero com un únic 0.
Una manera de codificar tots els nombres enters és configurar una bijecció, assignant els nombres enters (0, −1, 1, −2, 2, −3, 3, ...) a (1, 2, 3, 4, 5, 6, 7, ...) abans de codificar. En programari, això es fa més fàcilment assignant entrades no negatives a sortides senars i entrades negatives a sortides parells, de manera que el bit menys significatiu es converteix en un bit de signe invertit:
La codificació exponencial-Golomb generalitza el codi gamma a nombres enters amb una distribució de llei de potències "més plana", igual que la codificació Golomb generalitza el codi unari. Implica dividir el nombre per un divisor positiu, normalment una potència de 2, escriure el codi gamma per a un nombre més gran que el quocient i escriure el residu en un codi binari ordinari.
Referències
Categoria:Codificació Categoria:Compressió de dades