Codificación Shannon

¿Qué es el método de Shannon?

Se refiere a la probabilidad de aparición de cada símbolo en un mensaje, básicamente se utiliza para la compresión de datos.

Un poco de historia

Este método de codificación fue desarrollado por Claude Shannon en los laboratorios Bell y por Robert Fano en MIT (Massachussets Institute of Technology) en la década del 40 casi simultáneamente. La técnica fue propuesta por Claude Elwood Shannon, en “Una TeoríaMatemática de la Comunicación”, su artículo de 1948 introduciendo el campo de la teoría de la información. El método fue atribuido a Robert Fano, quien posteriormente lo publicó como uninforme técnico.

Propiedades Tablas de códigos

vDiferentes códigos, tienen diferentes tipos de bits

vLos códigos para símbolos con bajas probabilidades tienen más bits

vLos códigos para símbolos con altas probabilidades tienen menos bits

vCódigos de longitud diferente pueden ser unívocamente decodificados

¿Qué es la entropía?

vLa entropía se refiere a la cantidad de bits necesarios para representar un símbolo

En un símbolo = - log2 (probabilidad)

      En un mensaje = suma de la entropía de sus símbolos 

Utilización del método

1.- Para una secuencia de símbolos, se calcula la correspondiente lista de frecuencias de aparición de los símbolos.

DDABEBADACABAAECDCBAEACA

BCBAADDEAACAEAB

wA = 15 ; B = 7; C = 6; D = 6; E = 5

 Total de veces que se repite cada símbolo en la series  

2.- Se ordena la lista de símbolos según su frecuencia en orden decreciente.

              Frecuencia: Veces que aparece cada letra o símbolo en la serie  a transmitir

3.- Se divide la lista en dos partes, de forma que la suma total de frecuencias de la mitad superior sea lo más cercana posible a la suma total de la parte inferior.

4.- A la mitad superior de la lista se le asigna el dígito binario 0, y a la mitad inferior se le asigna el dígito binario 1. Esto significa que los códigos de los símbolos en la primera mitad empezarán todos con 0 y los códigos en la segunda mitad empezarán todos con 1.

5.- Cada una de las mitades, se subdivide en grupos y se agregan bits (digitos binarios) a los códigos hasta que cada grupo conste de un único símbolo.

6.- Se pueden representar los símbolos a modo de árbol binario

7.- Se calcula la entropía como:

    X = Largo de la serie  / frecuencia

               Entropía = Log ₂ (X)

8.- Una vez calculada la entropía se calcula la entropía en el mensaje (cantidad de bits necesarios para representar el símbolo en el mensaje)

                               Entropia * frecuencia del símbolo

9.- Finalmente el cálculo de los bits de código a transmitir está dado por la representación binaria (0,1) del símbolo y  los bits de mensajes es la multiplicación de los bits de códigos * la frecuencia del símbolo

        10.- Conclusión

    vSi codificáramos esta secuencia de símbolos utilizando 8 bits, utilizaríamos en total 312 bits (8 * 39 = 312).

    vSi utilizáramos Shannon sólo usaríamos 89 bits.

Ejemplo de código de Shannon

Codificar con codificación de Shannon la siguiente frase: "anita lava la tina"

 Código en Matlab:

clc;

clear all;

close all;

aa=fopen('anitalavandera.txt');

bb=fread(aa);

cc=unique(bb); %Encuentra caracteres usados

taas=length(bb);

for n=1:length(cc)

    d(n,1)=length(find(bb==cc(n))); %Cuenta la aparición de cada caracter

    

end

ss=transpose(d)./taas;

ss=sort(ss,'descend');

siling=ceil(log2(1/ss(1)));

sf=0;

fano=0;

n=1;Hs=0;

for iii=1:length(ss)

   Hs=Hs+ ss(iii)*log2(1/ss(iii));

end

shano=ss(1);

for o=1:length(ss)-1

   fano=fano+ss(o);

   sf=[sf 0]+[zeros(1,o) fano]; 

   siling=[siling 0]+[zeros(1,o) ceil(log2(1/ss(o+1)))];

end

for r=1:length(sf)

    esf=sf(r);

    

    for p=1:siling(r)

    

        esf=mod(esf,1)*2;

        h(p)=esf-mod(esf,1);

        

    end

    hh(r)=h(1)*10^(siling(r)-1);

    for t=2:siling(r)

        hh(r)=hh(r)+h(t)*10^(siling(r)-t);    

    end

end

c={'0','1'};

for i=1:length(hh)

    u=1;

   for t=siling(i):-1:1

       f=floor(hh(i)/10^(t-1));

       hh(i)=mod(hh(i),10^(t-1));       

       if f==1

           if u==1

                d=c{2};

           else

                d=[d c{2}];

           end

       else

           if u==1

                d=c{1};

           else

                d=[d c{1}];

           end

       end

       codex{i,:}={d};

       u=u+1;

   end

end

tao=siling(1)*ss(1);

for u=1:length(ss)-1

   tao=tao+siling(u+1)*ss(u+1);

end

T=tao/n;

B=[flipud(rot90(ss)),flipud(rot90(siling)),flipud(rot90(sf))];

disp(['       S','        Li','        Pk'])

disp(B)

disp('Code')

disp(codex)

disp(['Hs = ',num2str(Hs)])

disp(['T = ',num2str(T),'bits/symbol'])

disp([num2str(Hs),' <= ',num2str(T),' <= ',num2str(Hs+1)])

Resultados:

       S        Li        Pk

    0.3333    2.0000         0

    0.1667    3.0000    0.3333

    0.1111    4.0000    0.5000

    0.1111    4.0000    0.6111

    0.1111    4.0000    0.7222

    0.1111    4.0000    0.8333

    0.0556    5.0000    0.9444

Hs = 2.5997

T = 3.2222bits/symbol

2.5997 <= 3.2222 <= 3.5997


Referencias:
Archivo de la facultad de ingeniería de la Universidad de las Américas.

Link para descargar el archivo de MatLab:

http://www.mediafire.com/download/g2ams42gd425qm5/shannonanita.rar

Código Huffman

Codificación Huffman:

Es un método general de codificación y compresión diseñado para minimizar el número medio de bits necesarios para transmitir un símbolo cuando se debe transmitir varias copias independientes y estadísticamente equivalentes de dicho símbolo. Este método determina cómo los distintos valores del símbolo deben representarse como cadenas binarias.

Supongamos que tenemos que enviar el símbolo X que puede tomar valores {x₁,...x_n} con probabilidad {p₁,...,p_n}. La idea es reservar palabras cortas para los valores más frecuentes de X. Este método no requiere usar ningún tipo de separador entre los valores.

Ejemplo:

x1 (0.5)

x2 (0.3)

x3 (0.15)

x4 (0.05)

• Si se usan 00, 01, 10 y 11 necesitaremos siempre 2 bits para el valor de X.
• Si se usan las palabras 0,10,110,111 necesitaremos como término medio 1.7 bits (menos de 2).

El código del ejemplo es de longitud variable, pero no se requiere usar ningún tipo de separador entre los valores.

• x₃ x₁ x₄ x₃ x₃ x₂ = 110011111011010 Sólo puede decodificarse correctamente.

La razón es que siempre puede reconocer el final de una palabra porque ninguna otra palabra es el principio de otra dada. Un código con esta propiedad se denomina código prefijo. El código Huffman es el código prefijo que requiere el mínimo número medio de bits por símbolo.

Para derivar el código Huffman se hacen las siguientes operaciones:

1. Escoger los dos símbolos x_i, x_j con probabilidad más pequeña.
2. Se las reemplaza por y_i0 e y_i1.
3. Se borra x_i y x_j de la lista y se añadey_i con probabilidad p_i+p_j.
4. Volver al paso 1 hasta terminar con todos los símbolos.

Árbol de Huffman

El código queda definido por el camino desde C a cada nodo. La conversión para describir el código de Huffman es:

Práctica

Calcular el árbol de Huffman de la siguiente frase: "Anita lava la tina" en Matlab.

Código para Matlab:

clc;

clear all;

close all;

my_str = 'Anita lava la tina';  %Cadena de caracteres

auto_prob = 1;

if (auto_prob == 1)

    % Calcula automaticamente la probabilidad, si no le da valor a 0

    % para hacerlo manual

    % Con ASCII la version por cada caracter

    % Cada valor de  ASCII  representa la probabilidad de encontrar el caracter

    prob_dist = double(my_str);

else

          prob_dist = [10 19 30 40 50]; %Se define la probabilidad manual de distribución

end

num_bits = ceil(log2(length(prob_dist))) %Se calcula el número de bits

disp('Character Probability:');

for i = 1:length(prob_dist)

display(strcat(my_str(i),' -->  ',num2str(prob_dist(i))));

end

total = sum(prob_dist)

for i = 1:length(my_str)

clase_str{i} = my_str(i);

end

%mostramos la suma de la probabilidad

%guardamos la inicial de los simbolos y sus probabilidades para usarlos despues

init_str = clase_str;

init_prob = prob_dist;

sorted_prob = prob_dist;

rear = 1;

while (length(sorted_prob) > 1)

% Clase Probabilidad 

[sorted_prob,indeces] = sort(sorted_prob,'ascend');

% Clase de la cadena basada en la incidencia

clase_str = clase_str(indeces);

% Crea nuevo simbolo

new_node = strcat(clase_str(2),clase_str(1));

new_prob = sum(sorted_prob(1:2));

% Se recorre el simbolo usado del viejo

clase_str =  clase_str(3:length(clase_str));

sorted_prob = sorted_prob(3:length(sorted_prob));

% Agregamos un nuevo simbolo detras del viejo

clase_str = [clase_str, new_node];

sorted_prob = [sorted_prob, new_prob];

% Agregamos un nuevo simbolo

newq_str(rear) = new_node;

newq_prob(rear) = new_prob;

rear = rear + 1;

end

tree = [newq_str,init_str];

tree_prob = [newq_prob, init_prob];

% Usamos la clase de elementos de arbol completo

[sorted_tree_prob,indeces] = sort(tree_prob,'descend');

sorted_tree = tree(indeces);

parent(1) = 0;

num_children = 2;

for i = 2:length(sorted_tree)

% Extraemos el simbolo

me = sorted_tree{i};

% Buscamos un parecido de simbolo

count = 1;

parent_maybe = sorted_tree{i-count};

diff = strfind(parent_maybe,me);

while (isempty(diff))

count = count + 1;

parent_maybe = sorted_tree{i-count};

diff = strfind(parent_maybe,me);

end

parent(i) = i - count;

end

treeplot(parent);

title(strcat('Arbol de Codigo de Huffman - "',my_str,'"'));

display(sorted_tree)

display(sorted_tree_prob)

[xs,ys,h,s] = treelayout(parent);

text(xs,ys,sorted_tree);

for i = 2:length(sorted_tree)

% Uso las coordenadas para acomodarlo

my_x = xs(i);

my_y = ys(i);

% Uso el parentesco de las coordenadas

parent_x = xs(parent(i));

parent_y = ys(parent(i));

% Calculo el ancho de las coordenadas (midpoint)

mid_x = (my_x + parent_x)/2;

mid_y = (my_y + parent_y)/2;

%Calculo el ancho  (Positiva = 1, Negativa = 0)

slope  = (parent_y - my_y)/(parent_x - my_x);

if (slope > 0)

weight(i) = 1;

else

weight(i) = 0;

end

text(mid_x,mid_y,num2str(weight(i)));

end

for i = 1:length(sorted_tree)

% Codigo de inicializar

code{i} = '';

% Crear un ciclo para encontra el parentesco

index = i;

p = parent(index);

while(p ~= 0)

w = num2str(weight(index));

code{i} = strcat(w,code{i});

index = parent(index);

p = parent(index);

end

end

codeBook = [sorted_tree', code']

Resultados

Ventana de comandos de Matlab:

num_bits =

     5

Character Probability:

A -->65

n -->110

i -->105

t -->116

a -->97

 -->32

l -->108

a -->97

v -->118

a -->97

 -->32

l -->108

a -->97

 -->32

t -->116

i -->105

n -->110

a -->97

total =

        1642

sorted_tree = 

  Columns 1 through 9

    'vttnnlliiaaaaa   A'    'vttnnlli'    'iaaaaa   A'    'vttn'    'nlli'    'iaaa'    'aa   A'    'vt'    'tn'

  Columns 10 through 24

    'nl'    'li'    'ia'    'aa'    'aa'    '   A'    'v'    't'    't'    'n'    'n'    'l'    'l'    'i'    'i'

  Columns 25 through 35

    'a'    'a'    'a'    'a'    'a'    '   '    'A'    '  '    ' '    ' '    ' '

sorted_tree_prob =

  Columns 1 through 9

        1642         891         751         460         431         396         355         234         226

  Columns 10 through 18

         218         213         202         194         194         161         118         116         116

  Columns 19 through 27

         110         110         108         108         105         105          97          97          97

  Columns 28 through 35

          97          97          96          65          64          32          32          32

codeBook = 

    'vttnnlliiaaaaa   A'    ''         

    'vttnnlli'              '1'        

    'iaaaaa   A'            '0'        

    'vttn'                  '11'       

    'nlli'                  '10'       

    'iaaa'                  '01'       

    'aa   A'                '00'       

    'vt'                    '111'      

    'tn'                    '110'      

    'nl'                    '101'      

    'li'                    '100'      

    'ia'                    '011'      

    'aa'                    '001'      

    'aa'                    '0011'     

    '   A'                  '000'      

    'v'                     '1111'     

    't'                     '1101'     

    't'                     '11011'    

    'n'                     '1011'     

    'n'                     '10111'    

    'l'                     '1001'     

    'l'                     '10011'    

    'i'                     '0111'     

    'i'                     '01111'    

    'a'                     '00111'    

    'a'                     '001111'   

    'a'                     '0011111'  

    'a'                     '00111111' 

    'a'                     '001111111'

    '   '                   '0001'     

    'A'                     '0000'     

    '  '                    '00011'    

    ' '                     '000111'   

    ' '                     '0001111'  

    ' '                     '00011111' 

Archivo para Matlab:

http://www.mediafire.com/download/jj6m5mtr5b5dz4t/juanitobuenohuffman.rar

Fuente:

http://neo.lcc.uma.es/evirtual/cdd/tutorial/presentacion/huffman.html