Codificació entròpica
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]
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]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.
Codis de longitud variable (Variable Length Coding - VLC)
[modifica]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.
Evidentment, el nombre de bits mig està per damunt de l'entropia:
Bibliografia
[modifica]- Thomas M. Cover, Joy A. Thomas, Elements of Information Theory, Wiley-Interscience, 2006 (ISBN 978-0-471-24195-9) (anglès)
- David MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003 (ISBN 0-521-64298-1) (anglès)
- Mark Nelson, La Compression des données / texte, images, sons, Dunod, 1993. ISBN 978-2100016815 (francès)