LABORATORIO DE SISTEMAS DE COMUNICACIONES
PRÁCTICA # 5
CODIFICACIÓN DE FUENTE: HUFFMAN
OBJETIVOS:
• Entender el comportamiento de los diferentes componentes implicados en la
codificación de fuente.
• Evaluar el desempeño de los diferentes mecanismos de codificación de fuente
cuantificación y códigos Huffman.
MARCO TEÓRICO:
En esta práctica se podrá entender el flujo de datos a través de la codificación de fuente.
Para llevar a cabo este proceso, se cuenta con 6 bloques, en donde cada uno de ellos cumple
una función específica y dentro de los cuales figuran los siguientes:
1. Lectura del archivo de audio
LabVIEW presenta un bloque personalizado que lee un archivo de audio sin procesar (.wav)
y salidas con la forma de onda de audio de modo que emite una matriz de formas de onda
(en el caso de una señal estéreo, obtiene 2 formas de onda: una para los altavoces izquierdo
y derecho). Para efectos del caso, en el archivo .wav se tiene solo 1 canal, en donde lo
extraemos directamente. Tome en cuenta que, a diferencia de Matlab, la numeración de
los elementos en una matriz comienza desde 0 en LabVIEW. Cada forma de onda tiene una
matriz de muestras de tiempo (denotada como "Y") y el tiempo de muestreo (denotado por
"dt") las cuales se desea transmitir de manera eficiente.
2. Cuantificar los coeficientes obtenidos a través de la codificación de fuente
Los coeficientes son números reales. La comunicación digital usa codificación binaria, por
lo que no se puede transmitir los números reales con la mayor precisión posible. Hay una
compensación entre la cantidad de datos que se necesita transmitir versus la precisión que
se requiere o también conocida como Resolución. Se entiende entonces como resolución a
la cantidad de bits que se emplea para expresar cada muestra de codificación de fuente.
Por lo tanto, si se trabaja con una resolución de 4 bits /muestra, entonces se necesita
transmitir solo 4 bits de datos por muestra de codificación de fuente. Sin embargo, no sería
capaz de representar la relación 24 = 16 , es decir 16 valores diferentes de códigos de
fuente y todos los demás valores, tendrían que redondearse a uno de estos 16. Este proceso
realiza el requerimiento de cuantificación según la "Resolución" que elija.
3. Codificación de Huffman.
Después de la cuantificación, nos queda una matriz de muestras, donde cada muestra es un
número binario de longitud definida por el proceso de resolución. En este proceso, algunas
de las muestras se repetirán con mayor frecuencia que otras de manera que para analizar
la redundancia y comprimir aún más los datos, se requiere usar la codificación Huffman.
4. Decodificación de Huffman.
En esta etapa, se decodifica el código de Huffman en el lado del receptor (note que el
receptor también necesita conocer los parámetros del código Huffman en orden para
decodificarlo).
5. Decuantificación
La matriz de números binarios obtenidos después de la etapa anterior se convierte
nuevamente en una serie de datos reales dentro del proceso.
6. Formación de la onda reconstruida
Finalmente, formamos una forma de onda con las muestras de tiempo obtenidas para
reproducirlas.
ACTIVIDADES A DESARROLLAR:
Para esta práctica de laboratorio, Ud. debe implementar las partes del codificador de
fuente. Los bloques del decodificador le serán provistos.
FORMANDO EL CÓDIGO HUFFMAN
Llegando a la etapa final de codificación de fuente, necesitamos realizar la codificación de
Huffman en la matriz de números binarios obtenida anteriormente. Tenga en cuenta que
cada uno de estos números binarios será de longitud L (donde L = es la resolución que elija
en el panel frontal de simulator).
El sub-VI, form_frequency_distribution.vi toma la matriz bidimensional de bits y cuenta el
número de ocurrencias de cada uno de los números binarios, formando así una tabla de
distribución de frecuencias.
La siguiente etapa de la codificación de Huffman requiere que formemos el árbol de
Huffman para lo cual, nosotros debemos almacenar este árbol como un clúster que consta
de 6 arreglos que son:
Figura 1.- Salida de [Link]
• Número de nodos: a cada nodo en el árbol se le asigna un número (comenzando
en 0).
• Frecuencia: frecuencia de aparición del número binario correspondiente a
nodo (para nodos que no son hojas, es la suma de las frecuencias de sus dos hijos).
• Padre: Número del nodo padre (por defecto es -1 si el nodo no tiene padre o el
padre aún es desconocido).
• 0/1 hijo: usemos una notación donde llamamos a los hijos de un nodo como el 0-
ésimo hijo y el 1er hijo. Esta es una matriz de 0s / 1s que representa si el nodo
es el 0-ésimo hijo de su padre o el 1er hijo. (Por defecto es -1 si el nodo no tiene
padre o el padre aún se desconoce).
• 0 hijo: el número del 0º hijo del nodo (por defecto es -1 si el nodo tiene
sin hijos).
• 1 hijo: el número del primer hijo del nodo (predeterminado en -1 si el nodo tiene
sin hijos).
• Valor decimal: el valor decimal del número binario correspondiente a la
nodo.
El sub-VI form_frequency_distribution.vi genera una versión inicializada de este árbol
donde solo se contabilizan los nodos de hoja. Debe agregar entradas al grupo de árboles
para cada uno de los nodos principales.
Escriba la lógica para construir el árbol completo a partir de esta versión inicializada en
form_tree.vi.
Para ayudarlo a visualizar los formatos de datos exactos y el proceso de creación de árboles,
analice el siguiente ejemplo.
Figura 2.- Salida de form_tree.vi.
En primer lugar, digamos que la matriz de números binarios es como se muestra en el
campo "datos de entrada" en la figura 2. La figura muestra el resultado obtenido después
de ejecutar form_frequency_distribution.vi en estos datos de entrada. Tenga en cuenta que
las secuencias binarias "1100" y "1000" aparecen 4 y 3 veces respectivamente y las
secuencias binarias "0010" y "0001" aparecen una vez. La tabla de frecuencias se muestra
en la figura 3, en el grupo de árbol incluido, debajo de la etiqueta de "frecuencia". Las
representaciones decimales de "1100" y "1000" son "12" y "8" respectivamente y para
"0010" y "0001" son "1" y "2" respectivamente. El árbol de Huffman para dicha matriz se
muestra en la figura 4 a continuación.
Tenga en cuenta que el árbol inicializado solo representa los 4 nodos hoja. El árbol final
(salida de form_tree.vi) debería verse como se muestra en 3.
FORMACIÓN DEL LIBRO DE CÓDIGOS
Ahora tenemos el árbol Huffman listo, pero necesitamos generar el libro de códigos. El 'libro
de códigos' es un mapeo de los números binarios (de resolución 'L') a las secuencias
Huffman. Es como un diccionario donde se puede buscar cualquier binario de L bits y
encuentra que es la secuencia correspondiente de Huffman. Para crear este diccionario,
necesitamos encontrar las codificaciones Huffman de todos los binarios de L bits.
Figura 3.- Árbol
Es la representación de los números que tienen una frecuencia distinta de cero. Recuerde
que para obtener la codificación Huffman, se necesita atravesar el árbol hacia arriba (desde
un nodo hoja a la cúspide) y obtener la secuencia de bits de código Huffman apropiada de
esta ruta. Por ej. consulte las figuras 4 y 6, el valor decimal '12' es un 0 hijo de la raíz nodo
y, por lo tanto, la representación Huffman de '12' (es decir, "1100") es "0". Del mismo modo,
el valor decimal '1' (es decir, "0001") es el hijo 0 del nodo 4, que es el hijo 0 del nodo 5, que
a su vez es el 1-hijo del nodo raíz y, por lo tanto, la representación huffman de '1' (es decir,
"0001") es "100". Asegúrese de entender bien este algoritmo.
Eventualmente, se desea generar 2 matrices, una matriz de valores decimales (de los nodos
hoja) y otra serie de cadenas (los códigos Huffman correspondientes de los nodos hoja).
FINALIZACIÓN DEL CODIFICADOR DE HUFFMAN
Una vez que se forma el libro de códigos, la codificación de un flujo de bits entrante es solo
una búsqueda del 'diccionario' y este proceso ha sido ejecutado por Ud. Si los dos bloques
descritos anteriormente (form_tree y form_codebook) funcionan correctamente, entonces
esto debería funcionar también. Sin embargo, se puede realizar una comprobación final
ingresando las entradas como se muestra:
Figura 4.- Salida de form_tree
Figura 5.- Salida de form_codebook
PRUEBAS A REALIZAR:
1. Señal de audio RX y constelación recibida con una resolución de 8 bits, modulación 16
QAM y SNR=15dB.
2. Señal de audio RX y constelación recibida con una resolución de 8 bits, modulación 16
QAM y SNR=5dB.
3. Señal de audio RX y constelación recibida con una resolución de 8 bits, modulación 8
QAM y SNR=15dB.
4. Señal de audio RX y constelación recibida con una resolución de 8 bits, modulación 8
QAM y SNR=5dB.
5. Realizar una tabla donde se muestre el porcentaje de compresión al variar el nivel de
cuantificación, mantenga un SNR=20dB y una modulación 16 QAM.
Nivel de cuantificación: 4, 8 y 12.
PREGUNTAS A CONTESTAR:
1. Considere una fuente discreta sin memoria con alfabeto {𝑠0 , 𝑠1 , 𝑠2 } con probabilidades
𝑝0 = 1/4, 𝑝1 = 1/4 y 𝑝2 = 1/2. Calcule la entropía de la fuente.
2. Considere los cuatros códigos listados en la tabla.
Símbolo Código I Código II Código III Código IV
𝑠0 0 0 0 00
𝑠1 10 01 01 01
𝑠2 110 001 011 10
𝑠3 1110 0010 110 110
𝑠4 1111 0011 111 111
a) Identifique los códigos prefijos.
b) De los códigos identificados en el literal a), construya los árboles de decisión.
3. Dada la siguiente tabla de distribución de frecuencias halle los códigos para los valores
decimales, usando codificación de Huffman:
4. De los códigos hallados en la pregunta 3, halle la longitud del código y la eficiencia.
5. Considere la siguiente secuencia binaria: 11101001100010110100, use Lempel-Ziv para
codificarla.
BIBLIOGRAFÍA:
[1] L. W. Couch, Sistemas de Comunicación Digitales y Analógicos, Ciudad de Mexico: Pearson
Eduación, 2008.
