Codificació aritmètica

La codificació aritmètica és una forma de codificació entrópica utilisat en compressió sense pèrdues. Normalment, una cadena de caràcters està representada utilisant un número fix de bits per caràcter, com en el còdic ASCII. Quan una cadena és convertida a codificació aritmètica, els caràcters freqüentment usats seran almagasenats en menys bits i els de us menys habitual seran almagasenats en més bits, resultant en menys bits utilisats en total. La codificació aritmètica diferix d'atres formes de codificació entrópica, com la codificació de Huffman, en que més que separar l'entrada a símbols components i reemplaçar cada u en un còdic, la codificació aritmètica codifica el mensage sancer a un sol número, una fracció n on [0.0 ≤ ''n'' < 1.0).

Un eixemple de codificació aritmètica suponent una distribució de provabilitat fixa de tres símbols "A", "B" i "C". La provabilitat de "A" és 50%, la provabilitat de "B" és 33% i la provabilitat de "C" és 17%. Ademés assumim que la profunditat de recursión és coneguda en cada pas.
En el pas un codifiquem "B", el qual està dins de l'interval [0.5, 0.83): l'número binario "0.10x" és el còdic més curt que representa un interval que està enterament dins de [0.5, 0.83). "x" significa una seqüència de bits arbitrària. Hi ha dos casos extrems: la x més chicoteta representa un número infinit de zeros, la qual cosa representa el costat esquerre de l'interval representat. Després el costat esquerre de l'interval és dec(0.10) = 0.5. La x més gran representa un número infinit d'uns la qual cosa dona un número que convergix cap a dec(0.11) = 0.75. Per lo tant, "0.10x" representa l'interval [0.5, 0.75) el qual està dins de [0.5, 0.83).
Ara podem deixar la part "0." lloc que tots els intervals comencen en  "0." i podem ignorar la part "x" perque no importa que seqüència de bits representa, nos mantenim dins de [0.5, 0.75).

Detalls d'implementació i eixemples

Provabilitats iguals

En el cas més simple, la provabilitat d'aparició de cada símbol és igual. Per eixemple, considere un conjunt de tres símbols A, B i C, cada u en la mateixa provabilitat d'ocórrer. Un simple còdic de bloc requeriria 2 bits per símbol, lo que és un desperdici: una de les variacions de bits mai és usada. És dir, A=00, B=01 i C=10, pero 11 no és usat.

Una solució més eficient és representar una seqüència d'estos tres símbols com un número racional en base 3 a on cada dígit representa un símbol. Per eixemple, la seqüència "ABBCAB" podria convertir-se en 0.011201₃ (en la codificació aritmètica els números estan entre 0 i 1). El pas següent és codificar este número ternario usant un número binario de punt fix en la suficient precisió per a recuperar-ho, tal com 0.0010110010₂ —açò és només 10 bits; 2 bits són salvats en comparació a la codificació per bloc—. Açò és factible per a seqüències llargues perque hi ha algoritmes eficients per a convertir la base de números precisos arbitrariamente.

Per a decodificar el valor, coneixent que la cadena original tenia llongitut 6, un pugues simplement convertir de regrés a base 3, redonejar a 6 dígits i recuperar la cadena.

Definint un model

En general, els codificadores aritmètics poden produir una eixida prop de l'òptim per a qualsevol conjunt de símbols i provabilitats donat (el valor òptim és -log₂P bits per cada símbol de provabilitat P, veja teorema de codificació de fonts). Els algoritmes de compressió que usen la codificació aritmètica inicien determinant un model de les senyes - bàsicament una predicció de que patrons seran trobats en els símbols del mensage. Lo més encertada que siga la predicció, lo més prop a l'òptim que seá l'eixida.

Eixemple: un simple model estàtic per a descriure l'eixida d'un instrument de monitoreo particular sobre el temps podria ser:

• 60 % de provabilitat del símbol NEUTRAL
• 20 % de provabilitat del símbol POSITIVE

• 10 % de provabilitat del símbol NEGATIVE
• 10 % de provabilitat del símbol END-OF-DATA (Fi de les senyes). (La presència d'este símbol significa que la transmissió serà 'terminada internament', com és prou comuna en compressió de senyes; quan este símbol apareix en el fluix de senyes, el decodificador sabrà que el fluix sancer ha segut decodificado.)

Els models també poden manejar alfabets diferents al simple conjunt de quatre símbols triat per a este eixemple. Models més sofisticats també són possibles: la modelació de alt-orde canvia la seua estimació de la provabilitat actual d'un símbol basat en els símbols que li precedixen (el context), aixina que en un model per a text en anglés, per eixemple, el percentage de provabilitat de "o" seria molt més alt quan li seguix a una "Q" o a una "q". Els models poden ser inclús adaptatius, de manera que contínuament canvien la seua predicció de les senyes basades en lo que el fluix de senyes conté actualment. El decodificador deu tindre el mateix model que el codificador.

Codificació i decodificación: perspectiva general

En general, cada pas del procés de codificació, llevat per l'últim, és el mateix; el codificador té bàsicament només tres peces de senyes a considerar:

• El següent símbol que necessita ser codificat.
• l'interval actual (a l'inici del procés de codificació, l'interval és [0,1], pero això canviarà).
• Les provabilitats que el model assigna a cada u dels varis símbols que són possibles en esta etapa (com es va mencionar abans, els models d'alt-orde o adaptatius impliquen que estes provabilitats no són necessàriament les mateixes en cada pas).

El codificador dividix l'interval actual en sub-intervals, cada u representant una fracció de l'actual interval proporcional a la provabilitat d'eixe símbol en el context actual. Qualsevol que siga l'interval que corresponga al símbol actual que seguix a ser codificat es torna l'interval usat en el següent pas.

Eixemple: per al model de quatre símbols de dalt:

• l'interval per a NEUTRAL seria [0, 0.6)
• l'interval per a POSITIVE seria [0.6, 0.8)
• l'interval per a NEGATIVE seria [0.8, 0.9)
• l'interval per a END-OF-DATA seria [0.9, 1).

Quan tots els símbols hagen segut codificats, l'interval resultant inequívocament identifica la seqüència de símbols que ho varen produir. Qualsevol que tinga el mateix interval final i el model que és usat pot reconstruir la seqüència de símbols que deu haver segut ingressada al codificador per a resultar en eixe interval final.

No és necessari transmetre l'interval final, no obstant, és només necessari transmetre una fracció que cau dins de l'interval. En particular, només és necessari transmetre suficients dígits (en qualsevol base) de la fracció de manera que totes les fraccions que comencen en eixos dígits caiguen dins de l'interval final; açò garantisarà que el còdic resultant és un còdic prefixe.

Codificació i decodificación: eixemple

Un diagrama mostrant la decodificación de 0.538 (el punt circular) en el model d'eixemple. La regió és dividida en subregiones proporcionals a les freqüències dels símbols, després la subregión que conté el punt és successivament subdividida de la mateixa forma.

Considere el procés per a decodificar un mensage codificat en el model de quatre símbols donat. El mensage és codificat en la fracció 0.538 (usant decimal per a claritat, en lloc de binario; també assumint que hi ha només tants dígits com es necessiten per a decodificar el mensage).

El procés inicia en el mateix interval pel decodificador: [0,1), i usant el mateix model, dividint-ho en els mateixos quatre sub-intervals que el codificador deu tindre. La fracció 0.538 cau dins del sub-interval per a NEUTRAL, [0, 0.6); açò indica que el primer símbol que el codificador deu haver llegit ha segut NEUTRAL, llavors est és el primer símbol del mensage.

Després dividixca l'interval [0, 0.6) en sub-intervals:

• l'interval per a NEUTRAL seria [0, 0.36), 60 % de [0, 0.6).
• l'interval per a POSITIVE seria [0.36, 0.48), 20 % de [0, 0.6).
• l'interval per a NEGATIVE seria [0.48, 0.54), 10 % de [0, 0.6).
• l'interval per a END-OF-DATA seria [0.54, 0.6), 10 % de [0, 0.6).

ya que 0.538 està dins de l'interval [0.48, 0.54), el segon símbol del mensage deu haver segut NEGATIVE.

Una atra volta dividixca el nostre interval en sub-intervals:

• l'interval per a NEUTRAL seria [0.48, 0.516).
• l'interval per a POSITIVE seria [0.516, 0.528).
• l'interval per a NEGATIVE seria [0.528, 0.534).
• l'interval per a END-OF-DATA seria [0.534, 0.540).

Ara 0.538 cau dins de l'interval del símbol END-OF-DATA; per lo tant, este deu ser el següent símbol. ya que és també el símbol de terminació, vol dir que la decodificación està completa. Si el fluix de senyes no està terminat internament, es necessita una atra forma d'indicar quan el fluix es deté. D'una atra forma, el procés de decodificación podria continuar per sempre, erròneament llegint més símbols de la fracció dels que varen ser codificats en ella.