Codificació entròpica
De Viquipèdia
Codificació entròpica és un mètode de codificació sense pèrdues. Aquest mètode de codificació 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.
Taula de continguts |
[edita] Zig-zag
El mètode de lectura en zig-zag llegeix la matriu de símbols en forma de ziga-zaga. Va llegint en diagonal enlloc de per files o columnes com seria habitual.
[edita] RLE (Run-lenght encoding)
La compressió RLE guarda el valor del símbol i conta quants símbols iguals hi ha consecutius. Per tant el que fa es generar una seqüència de valors on primerament es diu el nombre de símbols que hi hauran i després ens diu quin tipus de símbol.
Per exemple:
En la seqüència binaria: A A A A A A B B B B B B A A B B B B A A A B B hi apliquem RLE el que sortiria seria: 6A 6B 2A 4B 3A 2B
[edita] DPCM (Differential PCM)
DPCM Codifica la diferència entre un valor i l'anterior.
En molts casos la diferència entre dos símbols consecutius és mínima, per exemple si 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.
[edita] VLC (Variable Length Coding)
També anomenat Huffman. S'assigna una longitud variable de bits a cada símbol segons la seva probabilitat d'aparèixer en la seqüència a enviar. És a dir, els símbols amb probabilitat més alta de ser enviats són codificats amb un nombre de bits menor i a l'inversa.
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
En binari: 000 001 010 100 000 000 100 101 011 010 011 000 100 010 010 010 000 010 000 100 001 010 011 011 011 (75 bits)
| Símbol | Freqüència | Codi Binari | Huffman |
|---|---|---|---|
| 0 | 24% | 000 | 00 |
| 1 | 8% | 001 | 1110 |
| 2 | 28% | 010 | 01 |
| 3 | 24% | 011 | 10 |
| 4 | 12% | 100 | 110 |
| 5 | 4% | 101 | 1111 |
Codificat: 00 1110 01 10 00 00 110 1111 10 01 10 00 110 01 01 01 00 01 00 110 1110 01 10 10 10 (59 bits)
Es pot observar a la taula anterior que els símbols amb més probabilitat de sortir es codifiquen amb menys bits i els que tenen menys probabilitat amb més bits. D'aquesta forma s'aconsegueix que la seqüència codificada redueixi clarament els bits necessaris.
En aquest cas l'entropia seria 2.36 bits per símbol
L'assignació de bits és amb una topologia d'arbre, la qual cosa vol dir que si s'utilitza una combinació per codificar un símbol totes les combinacions que comencin amb aquella combinació símbol queden descartades.
