La codificació Golomb és un mètode de compressió de dades sense pèrdues que utilitza una família de codis de compressió de dades inventats per Solomon W. Golomb a la dècada de 1960. Els alfabets que segueixen una distribució geomètrica tindran un codi Golomb com a prefix òptim, cosa que fa que la codificació Golomb sigui molt adequada per a situacions en què l'aparició de valors petits al flux d'entrada és significativament més probable que els valors grans.

Codificació de Rice La codificació Rice (inventada per Robert F. Rice) denota l'ús d'un subconjunt de la família de codis Golomb per produir un codi de prefix més simple (però possiblement subòptim). Rice va utilitzar aquest conjunt de codis en un esquema de codificació adaptativa; la "codificació Rice" pot referir-se tant a aquest esquema adaptatiu com a l'ús d'aquest subconjunt de codis Golomb. Mentre que un codi Golomb té un paràmetre ajustable que pot ser qualsevol valor enter positiu, els codis Rice són aquells en què el paràmetre ajustable és una potència de dos. Això fa que els codis Rice siguin convenients per al seu ús en un ordinador, ja que la multiplicació i la divisió per 2 es poden implementar de manera més eficient en aritmètica binària.

Rice es va veure motivada a proposar aquest subconjunt més simple pel fet que les distribucions geomètriques sovint varien amb el temps, no es coneixen amb precisió, o ambdues coses, de manera que seleccionar el codi aparentment òptim podria no ser gaire avantatjós.

La codificació Rice s'utilitza com a etapa de codificació d'entropia en diversos mètodes de compressió d'imatges sense pèrdues i compressió de dades d'àudio.

Visió general miniatura|Exemple de codificació Golomb per a una font x amb distribució geomètrica, amb paràmetre , utilitzant codi Golomb amb El codi de 2 bits 00 s'utilitza el 20% del temps; els codis de 3 bits 010, 011 i 100 s'utilitzen més del 38% del temps; es necessiten 4 bits o més en una minoria de casos. Per a aquesta font, l'entropia = 3.610 bits; per a aquest codi amb aquesta font, la taxa = 3.639 bits; per tant, la redundància = 0.030 bits o l'eficiència = 0.992 bits per bit.

Construcció de codis La codificació Golomb utilitza un paràmetre ajustable per dividir un valor d'entrada en dues parts: , el resultat d'una divisió per , i , el residu. El quocient s'envia en la codificació unitària, seguit del residu en la codificació binària truncada. Quan La codificació Golomb és equivalent a la codificació unària.

Els codis de Golomb-Rice es poden considerar com a codis que indiquen un nombre mitjançant la posició del compartiment () i el desplaçament dins del compartiment (). La figura d'exemple mostra la posició i el desplaçament per a la codificació de l'enter utilitzant el paràmetre de Golomb-Rice , amb probabilitats de font seguint una distribució geomètrica amb .

Formalment, les dues parts vénen donades per la següent expressió, on és el nombre enter no negatiu que s'està codificant:

i

miniatura|Aquesta imatge mostra la redundància, en bits, del codi Golomb, quan s'escull de manera òptima, per a Tant com es codificaran utilitzant nombres variables de bits: mitjançant un codi unari i mitjançant bits per al codi Rice, o una elecció entre i bits per al codi Golomb (és a dir, no és una potència de 2), amb Si , aleshores utilitzeu bits per codificar ; altrament, utilitzeu +1 bits per codificar . Clarament, si és una potència de 2 i podem codificar tots els valors de amb bits.

L'enter tractat per Golomb era la longitud d'execució d'un procés de Bernoulli, que té una distribució geomètrica que comença a 0. La millor elecció del paràmetre és una funció del procés de Bernoulli corresponent, que està parametritzat per la probabilitat d'èxit en un assaig de Bernoulli determinat. és o bé la mediana de la distribució o bé la mediana ±1. Es pot determinar mitjançant aquestes desigualtats: que es resolen per Per a l'exemple amb :

El codi de Golomb per a aquesta distribució és equivalent al codi de Huffman per a les mateixes probabilitats, si fos possible calcular el codi de Huffman per al conjunt infinit de valors font.

Algorisme simple A continuació es mostra la codificació Rice-Golomb, on el codi de residu utilitza una codificació binària truncada simple, també anomenada "codificació Rice" (altres codificacions binàries de longitud variable, com les codificacions aritmètiques o de Huffman, són possibles per als codis de residu, si la distribució estadística dels codis de residu no és plana, i sobretot quan no s'utilitzen tots els residus possibles després de la divisió). En aquest algorisme, si el paràmetre M és una potència de 2, esdevé equivalent a la codificació Rice més simple:

Fixa el paràmetre M a un valor enter. Per a N, el nombre que s'ha de codificar, trobeu quocient = q = terra ( N / M ) residu = r = N mòdul M Generar paraula clau El format del codi : <Codi del quocient><Codi de la resta>, on Codi quocient (en codificació unitària) Escriviu una cadena de longitud q d'1 bits (alternativament, de 0 bits) Escriu un bit 0 (respectivament, un bit 1) Codi residual (en codificació binària truncada) Deixa Si codi r en representació binària utilitzant b bits. Si codifica el número en representació binària utilitzant b + 1 bits.

Descodificació:

Desxifra la representació unària de q (compta el nombre d'1 al principi del codi) Omet el delimitador 0 Deixa Interpreta els següents b bits com un nombre binari r''' . Si es manté, aleshores la resta Altrament, interpreta b + 1 bits com un nombre binari r''', el residu ve donat per Càlcul

Exemple Estableix Així El límit és . Codificació de la part quocientbits de sortida00110211031110411110511111061111110N Codificació de la part restantdesplaçamentbinaribits de sortida00000000011000100122001001033001101144010010055010110161211001100713110111018141110111091511111111 Per exemple, amb una codificació Rice-Golomb utilitzant el paràmetre , el nombre decimal 42 primer es dividiria en = 4 i = 2, i es codificaria com a qcode( ), rcode( ) = qcode(4), rcode(2) = 11110,010 (no cal codificar la coma de separació al flux de sortida, perquè el 0 al final del codi és suficient per indicar quan acaba i comença ; tant el qcode com l'rcode estan autodelimitats).

Referències

Categoria:Codificació Categoria:Compressió de dades