miniatura|Comparació de les longituds dels codis de Fibonacci, delta Elias i gamma. La codificació ω Elias o codificació omega Elias és un codi universal que codifica els nombres enters positius desenvolupat per Peter Elias. Igual que la codificació gamma Elias i la codificació delta Elias, funciona prefixant l'enter positiu amb una representació del seu ordre de magnitud en un codi universal. A diferència d'aquests altres dos codis, però, Elias omega codifica recursivament aquest prefix; per tant, de vegades es coneixen com a codis Elias recursius.
La codificació Omega 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.
Per codificar un enter positiu N:
Poseu un "0" al final del codi. Si N = 1, atura; la codificació s'ha completat. Anteposa la representació binària de N al principi del codi. Això haurà de ser com a mínim dos bits, el primer bit dels quals serà un 1. Sigui N igual al nombre de bits que s'hi acaben d'afegir abans, menys un. Torneu al pas 2 per anteposar la codificació de la nova N.
Per descodificar un enter positiu codificat amb omega d'Elias:
Comenceu amb una variable N, establerta al valor 1. Si el següent bit és un "0", aleshores s'atura. El nombre descodificat és N. Si el següent bit és un "1", aleshores llegeix-lo més N bits més i utilitza aquest nombre binari com a nou valor de N. Torna al pas 2.
Exemples Els codis omega es poden considerar com un nombre de "grups". Un grup és o bé un únic bit 0, que finalitza el codi, o bé dos o més bits que comencen amb 1, seguits d'un altre grup.
Els primers codis es mostren a continuació. S'hi inclou l'anomenada distribució implícita, que descriu la distribució de valors per als quals aquesta codificació produeix un codi de mida mínima; vegeu Relació dels codis universals amb la compressió pràctica per a més detalls. ValorCodiProbabilitat implícita101/2210 01/8311 01/8410 100 01/64510 101 01/64610 110 01/64710 111 01/64811 1000 01/128911 1001 01/1281011 1010 01/1281111 1011 01/1281211 1100 01/1281311 1101 01/1281411 1110 01/1281511 1111 01/1281610 100 10000 01/20481710 100 10001 01/2048...10010 110 1100100 01/8192100011 1001 1111101000 01/131.07210.00011 1101 10011100010000 01/2.097.152100.00010 100 10000 11000011010100000 01/268.435.4561.000.0001/2.147.483.648 La codificació per a 1 googol, 10100, és 11 1000 101001100 (15 bits de capçalera de longitud) seguida de la representació binària de 333 bits d'1 googol, que és 10010 01001001 10101101 00100101 10010100 11000011 01111100 11101011 00001011 00100111 10000100 11000100 11001110 00001011 11110011 10001010 11001110 01000000 10001110 00100001 00011010 01111100 10101010 10110010 01000011 00001000 10101000 00101110 10001111 00010000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 i un 0 final, per a un total de 349 bits.
Un googol a la centèsima potència (1010000) és un nombre binari de 33.220 bits. La seva codificació omega té una longitud de 33.243 bits: 11 1111 1000000111000100 (22 bits), seguit de 33.220 bits del valor i un 0 final. Sota la codificació delta Elias, el mateix nombre té una longitud de 33.250 bits: 000000000000000 1000000111000100 (31 bits) seguit de 33.219 bits del valor. La codificació omega i la delta són, respectivament, un 0,07% i un 0,09% més llargues que la representació binària ordinària de 33.220 bits del nombre.
Longitud del codi Per a la codificació d'un enter positiu , el nombre de bits necessaris, , és recursivament: És a dir, la longitud del codi omega d'Elias per al nombre enter és on el nombre de termes de la suma està limitat superiorment pel logaritme iterat binari. Per ser precisos, sigui Nosaltres tenim per a alguns , i la longitud del codi és Des de , tenim .
Com que el logaritme iterat creix més lentament que tots els per a qualsevol fix , la taxa de creixement asimptòtic és , on la suma acaba quan cau per sota d'un.
Referències
Categoria:Codificació Categoria:Compressió de dades