Codificació entròpica

De Viquipèdia
Dreceres ràpides: navegació, cerca

En teoria de la informació, codificació entròpica és un mètode de codificació sense pèrdues que és independent de les característiques específiques del medi. Aquest mètode es basa en un coneixement previ sobre els símbols que sorgiran en una trama binaria.

L'entropia és un factor per avaluar els codificadors. Es calcula amb els nombre de bits per símbol usats.

Existeixen tres tipus de codis: Codificació per longitud de sèries(Run Length Encoding - RLE), DPCM (Differential PCM) i Codis de longitud variable (Variable Length Coding - VLC)

Codificació per longitud de sèries (Run Length Encoding - RLE)[modifica | modifica el codi]

Lectura en zig-zag

La codificació Run Length realitza una lectura en zig-zag de la matriu de símbols. Utilitza un mètode de lectura en diagonal en lloc d'un recorregut per files o columnes com seria habitual.

RLE realitza una cerca de sèries consecutives d'un sol símbol dins d'una trama. Posteriorment substitueix la sèrie per una única instància del símbol i un comptador amb el nombre de repeticions.


Exemple:

Trama original: {A A A B B C C C D D D D B B A E E}

Codificació RLE: {[A,3] [B,2] [C,3] [D,4] [B,2] [A,1] [E,2]}

DPCM (Differential PCM)[modifica | modifica el codi]

Els sistemes DPCM codifiquen la diferència entre un valor i l'anterior. En codificació d'imatge, s'utilitza per codificar els coeficients DC de la Transformada Cosinus Discreta (Discrete Cosine Transform - DCT). Aquests presenten el nivell de gris mitjà del bloc i, molt sovint, el nivell mitjà de gris d'un bloc serà semblant al nivell mitjà de gris del bloc anterior. En conseqüència la diferència entre dos blocs consecutius és mínima. Si per exemple codifiquem una imatge on hi ha una gran part de cel, aleshores enviarem nombres més petits, ja que la diferència amb l'anterior valor serà quasi 0. Si no utilitzessin la codificació DPCM els valors serien molt més grans, cosa que equival a més bits en binari.

Exemple de codificació DPCM d'una imatge

Codis de longitud variable (Variable Length Coding - VLC)[modifica | modifica el codi]

Es tracta d'un cas particular de codificació aritmètica. La idea bàsica dels codis de longitud variable és assignar paraules codi de longituds diferents en funció de la probabilitat dels missatges. Els missatges més probables es codificaran amb més bits que no pas els missatges menys probables.


Per exemple:

Es vol codificar la seqüència: 0 1 2 3 0 0 4 5 3 2 3 0 4 2 2 2 0 2 0 4 1 2 3 3 3


Símbol Probabilitat Codi
0 0.24 00
1 0.08 1110
2 0.28 01
3 0.24 10
4 0.12 110
5 0.04 1111


Podem calcular el nivell mitjà de bits que s'utilitzen per codificar aquesta trama amb aquest codi arbitrari calculant el nombre de bits utilitzat per cada símbol ponderat per la probabilitat amb la que es produeix el símbol.

N_{medio}=\sum_{n=1}^N \ N_k\cdot{}P_k=\sum_{i=1}^6\ (2\cdot0,24)+(4\cdot0,08)+(2\cdot0,28)+(2\cdot0,24)+(3\cdot0,12)+(4\cdot0,04)=3,04 bits

Evidentment, el nombre de bits mig està per damunt de l'entropia:


H=\sum_{n=1}^N \ p_k\cdot log_2 p_k=2,35 bits

Vegeu també[modifica | modifica el codi]

Codificació Run-length

Codificació de Huffman

DifferentialPCM