Huffman Ejemplos

download Huffman Ejemplos

of 16

  • date post

    01-Oct-2015
  • Category

    Documents

  • view

    216
  • download

    1

Embed Size (px)

description

jbbhjhb

Transcript of Huffman Ejemplos

  • Codificacin de Fuente y de CanalCodificacin de Fuente y de Canal

    PRCTICA 7PRCTICA 7 ( 2 sesiones)

    Laboratorio de Seales y Comunicaciones 3er curso, Ingeniera Tcnica de Telecomunicacin

    Javier Ramos Lpez, Fernando Daz de Mara, Fernando Prez Cruz y David Luengo Garca

  • 1. Objetivos

    Los objetivos principales de esta prctica son los siguientes:

    Estudiar la cantidad de informacin media generada por una fuente discreta o por una fuente continua cuantificada mediante el concepto de entropa.

    Construir cdigos de fuente capaces de proporcionar una tasa de salida cercana a la entropa de la fuente: cdigos de Huffman.

    Construir cdigos de canal capaces de proporcionar una cierta proteccin frente a errores: cdigos de Hamming.

    2. Contenido Terico

    A continuacin se va a realizar una breve descripcin de los elementos que van a ser necesarios para la realizacin de esta primera prctica: la codificacin de fuente (cdigos de Huffman), y la codificacin de canal (cdigos de Hamming). Esta descripcin no va a sustituir la informacin recibida en las asignaturas de Teora de la Comunicacin y Comunicaciones Digitales, y se deber acudir a las referencias bibliogrficas de estas asignaturas para comprender todos los aspectos tericos que se van a tratar en estas prcticas.

    2.1. Codificacin de Fuente

    La salida que se tiene del codificador est en muchos casos correlada, y algunos bits o cadenas de bits son mucho ms probables que otros. Esto provoca que se transmitan ms bits de los que son estrictamente necesarios para enviar la informacin deseada entre el transmisor y el receptor. La cantidad de informacin por smbolo generada por una fuente viene medida por su entropa. Suponiendo que una fuente discreta es capaz de generar un total de M valores distintos, cada uno de ellos con probabilidad pi, su entropa se define como:

    !=

    "=M

    i

    ii ppH1

    2log .

    La entropa proporciona el lmite inferior del nmero de bits por muestra necesarios para transmitir la informacin de la fuente sin prdidas, y es la tasa de salida hacia la que debe tender un buen codificador de fuente. Cuando la tasa de transmisin es mucho mayor que la entropa de la fuente, entonces es posible que algunas de las propiedades

  • de las modulaciones (por ejemplo su anchura espectral) no sean idnticas a los valores tericos, lo que puede dar lugar a interferencias con otros sistemas de comunicaciones. La codificacin de fuente se encarga de eliminar dicha correlacin de tal forma que los bits que aparecen a su salida estn incorrelados, y todas las cadenas de cualquier longitud son igualmente probables, obtenindose un espectro similar al terico y una cadena de bits a transmitir lo ms corta posible.

    Una de las formas ms habituales de realizar la codificacin de fuente es la codificacin de Huffman, en la que a cada smbolo o cadena de bits de idntica longitud se le asigna otra cadena de bits de longitud variable. Cuanto mayor sea la probabilidad de aparicin de un smbolo (o cadena de bits) menor ser la longitud de la cadena asignada, de tal forma que la longitud media de las cadenas resultantes sea menor que la de las cadenas de bits originales. La ventaja de este tipo de codificadores es que se pueden ilustrar de manera sencilla mediante un ejemplo.

    Ejemplo:

    Supongamos que se dispone de una fuente continua que discretizamos empleando un cuantificador uniforme con 8 niveles. A continuacin codificamos sus salidas, asignn-dole a cada muestra de entrada un smbolo compuesto por tres bits. Las probabilidades de cada uno de estos smbolos son: P(000) =0.2, P(001) =0.01, P(010) =0.4, P(011) =0.04, P(100) =0.1, P(101) =0.02, P(110) =0.07 y P(111) =0.16. En consecuencia, la entropa de esta fuente es

    38.2log1

    2 =!= "=

    M

    i

    ii ppH ,

    que es significativamente inferior a los 3 bits por muestra que estamos empleando si tomamos directamente la salida del codificador. La codificacin de Huffman le va asignar a cada cadena de 3 bits una cadena de longitud variable que minimice el nmero de bits medio por smbolo. Por supuesto, dichas cadenas de bits deben ser unvocamente decodificables. Para asignar estas cadenas se ordenan los smbolos de acuerdo con sus probabilidades: desde el ms probable hasta el menos probable. A continuacin, se juntan los dos smbolos menos probables, dando lugar a un nuevo smbolo cuya probabilidad es la suma de ambos, y se vuelven a ordenar. Esta operacin (parte hacia delante del algoritmo) se repite hasta que se hayan sumado todas las probabilidades, generndose un rbol de smbolos. En la Figura 1 se muestran las probabilidades ordenadas en cada iteracin del algoritmo para este ejemplo.

  • Figura 1: Suma de probabilidades para construir el cdigo de Huffman del ejemplo.

    Una vez que el rbol est completamente construido (es decir, en el momento en que todos los smbolos se han juntado en uno solo con probabilidad 1), se recorre el rbol de derecha a izquierda (parte hacia atrs del algoritmo), asociando con cada bifurcacin (esto es, donde se han sumado 2 probabilidades) un 0 y un 1 en cada una de sus ramas (se puede hacer de manera arbitraria). En la Figura 2 se muestra dicha asignacin, donde siempre se ha situado el 0 en la rama superior.

    Figura 2: Asignacin de bits a cada bifurcacin del rbol del ejemplo.

    Por ltimo, se leen los bits de derecha a izquierda hasta llegar al smbolo original, y dicha cadena de bits es la que se le asigna a cada smbolo de entrada. En la Figura 3 se muestra la cadena de longitud variable asignada a cada cadena de tres bits, pudindose

  • apreciar que los smbolos ms probables tienen asociadas cadenas ms cortas, y los menos probables cadenas asignadas ms largas. Este ejemplo es constructivo en el sentido de que cualquier cdigo de Huffman se puede obtener de la misma manera. Adems, se puede demostrar que para una asignacin no fraccionaria de bits por smbolo dicho cdigo es ptimo. Es decir, se trata del que ms se acerca al lmite terico dado por la entropa de la fuente.

    Figura 3: Asignacin de cdigos realizada por el codificador de Huffman.

    La calidad de un cdigo de fuente se puede medir por diversos parmetros, de los que en esta prctica nicamente consideraremos dos: la tasa de compresin y la eficiencia. La longitud media de un cdigo se define como la longitud en promedio de una palabra del mismo:

    !=

    =M

    i

    iinpL1

    ,

    donde ni es el nmero de bits usados para codificar el smbolo i-simo. Ahora, la tasa de compresin de un cdigo de Huffman se define como la relacin de compresin lograda frente a un cdigo de longitud fija utilizado para codificar dicha fuente:

    ! "L

    M2log=# .

    Una segunda medida de rendimiento es la eficiencia del cdigo, que mide lo cercana que se encuentra su longitud media del lmite terico dado por la entropa:

    ( )L

    XH=! .

  • Para un cdigo de Huffman se cumple que 1!" , y 1))(1/()( !!+ "XHXH . Como

    ejemplo, el cdigo del apartado anterior es un buen cdigo, ya que su longitud media es 2.44 (recurdese que su entropa era 2.38), lo que implica una tasa de compresin de 1.23 y una eficiencia del 97.54 % (el lmite anterior nos indica que para esta fuente la eficiencia de un cdigo de Huffman debe ser superior al 70.41 %).

    Por ltimo, aunque los cdigos de Huffman sean ptimos para asignaciones no fraccio-narias de bits, su rendimiento (longitud media del cdigo) puede encontrarse muy lejos de la entropa de la fuente. Esto sucede por ejemplo cuando se dispone de una fuente con probabilidades muy dispares pero muy pocos smbolos para realizar asignaciones de cdigos de longitud variable (por ejemplo, una fuente binaria cuyos smbolos tengan probabilidades 0.9 y 0.1). En estos casos, el rendimiento se puede mejorar realizando una extensin del cdigo. La manera ms sencilla de hacerlo consiste en suponer que los smbolos consecutivos son independientes, tomar bloques de k smbolos en lugar de tomarlos de uno en uno, y disear un cdigo de Huffman para los Mk smbolos resultantes. Se puede demostrar que mejora el rendimiento del cdigo (esto es, que disminuye su longitud media) conforme aumenta el valor de k, tendiendo su longitud media hacia el valor de la entropa (lmite terico) cuando k tiende a infinito. Obviamente, el inconveniente de realizar una extensin del cdigo estriba en que aumenta su complejidad conforme se van utilizando valores mayores de k.

    2.2. Codificacin de canal

    El codificador de canal introduce redundancia controlada de tal forma que si se produce algn error en el canal de comunicaciones se pueda detectar y/o corregir. Hay distintos sistemas de proteccin contra errores: cdigos bloque, cdigos convolucionales, cdigos de rejilla (trellis), etc. En esta prctica nos vamos a centrar en los ms sencillos: los cdigos bloque lineales. Estos cdigos toman los bits de la entrada de k en k, y los transforman en n bits de salida (es decir, aaden r=n-k bits de redundancia). Para llevar a cabo esta transformacin se multiplica un vector fila de k bits por una matriz de kn

    elementos binarios, y se realiza la operacin de mdulo 2 sobre el vector salida de n elementos. Los bits de redundancia son los que van a permitir detectar y corregir los errores que se produzcan en el canal de comunicaciones. En la Figura 4 se muestra de forma esquemtica y algebraica el funcionamiento del codificador.

    Figura 4: Modelo esquemtico y algebraico del codificador de canal.

  • Es posible detectar la existencia de un error en el canal de comunicaciones con estos cdigos gracias a que a la salida del codificador se tiene un espacio vectorial de dimensin n (con 2n posibles vectores por lo tanto), dentro del cual nicamente existen 2k vectores vlidos. En consecuencia, 2n 2k vectores no se pueden dar a no ser que se haya producido