CÓDIGO HUFFMAN

DAVID A. HUFFMAN

• NACIÓ EN OHIO.

• TÍTULO EN INGENIERÍA ELÉCTRICA EN LA UNIVERSIDAD ESTATAL DE OHIO.

• REALIZO SU SERVICIO MILITAR, LLEGANDO A SER OFICIAL DE LA MARINA.

ESTUDIOS

• CONTINUÓ SUS ESTUDIOS CONSIGUIENDO LOS TÍTULOS DE INGENIERÍA ELECTRÓNICA Y DE POSTGRADO EN OHIO (1949) Y EN EL INSTITUTO TECNOLÓGICO DE MASSACHUSETTS (MIT), RESPECTIVAMENTE.

• SE UNIÓ AL CUERPO DOCENTE EN 1953 EN EL MIT. EN 1967, FUE A LA UNIVERSIDAD DE CALIFORNIA (SANTA CRUZ), TAMBIÉN COMO DOCENTE, Y FUNDÓ EL DEPARTAMENTO DE CIENCIA INFORMÁTICA.

CONTRIBUCIONES

• TEORÍA DE LA INFORMACIÓN Y CODIFICACIÓN.

• DISEÑOS DE SEÑAL PARA APLICACIONES DE RADAR Y COMUNICACIONES.

• PROCEDIMIENTOS DE DISEÑO PARA CIRCUITOS LÓGICOS ASÍNCRONOS.

• MURIÓ EN 1999 DESPUÉS DE UNA LUCHA DE 10 MESES CONTRA EL CÁNCER.

ORIGEN DEL CODIGO HUFFMAN

• EN 1951, EN LA ASIGNATURA “TEORÍA DE LA INFORMACIÓN”

• REALIZACIÓN DE UN EXAMEN FINAL O LA PRESENTACIÓN DE UN TRABAJO.

• EL PROFESOR ROBERT. M. FANO ASIGNÓ LAS CONDICIONES DEL TRABAJO BAJO LA PREMISA DE ENCONTRAR EL CÓDIGO BINARIO MÁS EFICIENTE.

• MIENTRAS ESTUDIABA VINO A SU MENTE LA IDEA DE USAR ÁRBOLES BINARIOS DE FRECUENCIA ORDENADA Y RÁPIDAMENTE PROBÓ QUE ÉSTE ERA EL MÉTODO MÁS EFICIENTE.

LA CODIFICACIÓN DE HUFFMAN ES UN ALGORITMO PARA LA CREACIÓN DE CÓDIGOS DE HUFFMAN.

ESTE ALGORITMO TOMA UN ALFABETO DE N SÍMBOLOS, JUNTO CON SUS FRECUENCIAS DE

APARICIÓN ASOCIADAS, Y PRODUCE UN CÓDIGO DE HUFFMAN PARA ESE ALFABETO Y ESAS FRECUENCIAS.

CONSTRUCCIÓN DEL ALGORITMO DE HUFFMAN

• EL ALGORITMO CONSISTE EN LA CREACIÓN DE UN ÁRBOL BINARIO QUE TIENE CADA UNO DE LOS SÍMBOLOS POR HOJA, Y

CONSTRUIDO DE TAL FORMA QUE SIGUIÉNDOLO DESDE LA RAÍZ A CADA UNA DE SUS HOJAS SE OBTIENE EL CÓDIGO HUFFMAN ASOCIADO.

PASOS PARA CREAR EL ÁRBOL BINARIO

1. SE CREAN VARIOS ÁRBOLES, UNO POR CADA UNO DE LOS SÍMBOLOS DEL ALFABETO, CONSISTIENDO CADA UNO DE LOS ÁRBOLES EN UN NODO SIN HIJOS, Y ETIQUETADO CADA UNO CON SU SÍMBOLO ASOCIADO Y SU FRECUENCIA DE APARICIÓN.

2. SE TOMAN LOS DOS ÁRBOLES DE MENOR FRECUENCIA, Y SE UNEN CREANDO UN NUEVO ÁRBOL. LA ETIQUETA DE LA RAÍZ SERÁ LA SUMA DE LAS FRECUENCIAS DE LAS RAÍCES DE LOS DOS ÁRBOLES QUE SE UNEN, Y CADA UNO DE ESTOS ÁRBOLES SERÁ UN HIJO DEL NUEVO ÁRBOL. TAMBIÉN SE ETIQUETAN LAS DOS RAMAS DEL NUEVO ÁRBOL: CON UN 0 LA DE LA IZQUIERDA, Y CON UN 1 LA DE LA DERECHA.

3. SE REPITE EL PASO 2 HASTA QUE SÓLO QUEDE UN ÁRBOL.

OBTENER EL CÓDIGO DE UN SÍMBOLO

1. COMENZAR CON UN CÓDIGO VACÍO.

2. INICIAR EL RECORRIDO DEL ÁRBOL EN LA HOJA ASOCIADA AL SÍMBOLO.

3. COMENZAR UN RECORRIDO DEL ÁRBOL HACIA ARRIBA.

4. CADA VEZ QUE SE SUBA UN NIVEL, AÑADIR AL CÓDIGO LA ETIQUETA DE LA RAMA QUE SE HA RECORRIDO.

5. TRAS LLEGAR A LA RAÍZ, INVERTIR EL CÓDIGO.

6. EL RESULTADO ES EL CÓDIGO HUFFMAN DESEADO.

OBTENER UN SÍMBOLO A PARTIR DEL CÓDIGO

1. COMENZAR EL RECORRIDO DEL ÁRBOL EN LA RAÍZ DE ÉSTE.

2. EXTRAER EL PRIMER SÍMBOLO DEL CÓDIGO A DESCODIFICAR.

3. DESCENDER POR LA RAMA ETIQUETADA CON ESE SÍMBOLO.

4. VOLVER AL PASO 2 HASTA QUE SE LLEGUE A UNA HOJA, QUE SERÁ EL SÍMBOLO ASOCIADO AL CÓDIGO.

Símbolo Frecuencia

Código Huffman

A 0.15 010

B 0.30 00

C 0.20 10

D 0.05 1110

E 0.15 011

F 0.05 11111

G 0.10 110

EJEMPLO DE APLICACIÓN

• UNA SONDA ESPACIAL HA SIDO LANZADA AL ESPACIO PARA CONTAR CIERTO TIPO DE PERTURBACIONES ESTELARES. HA DE CONTAR CUÁNTAS SE PRODUCEN EN CADA MINUTO, Y TIENE CADA DÍA UNA VENTANA DE TIEMPO BASTANTE REDUCIDA PARA ENVIAR LOS DATOS A TIERRA; POR TANTO, INTERESA REDUCIR AL MÁXIMO EL TIEMPO DE TRANSMISIÓN, Y PARA ELLO SE RECURRE A CODIFICAR LAS MUESTRAS MEDIANTE UN CÓDIGO DE HUFFMAN.

• PUEDE OBSERVARSE QUE, EN LA CODIFICACIÓN BINARIA, TODOS LOS POSIBLES VALORES RECIBEN CÓDIGOS DEL MISMO NÚMERO DE BITS, MIENTRAS QUE EN LA CODIFICACIÓN HUFFMAN, CADA VALOR TIENE UN NÚMERO DIFERENTE DE BITS: LOS CÓDIGOS MÁS FRECUENTES POSEEN DOS BITS, MIENTRAS QUE LOS MENOS FRECUENTES POSEEN CUATRO BITS.

• 5,4,2,3,2,2,1,0,1,3,2,4,3,4,3,2,3,4,2,4

• -> UTILIZANDO LA CODIFICACIÓN BINARIA, SERÍA UNA SERIE DE 60 BITS; 3 BITS POR SÍMBOLO.

• 101100010011010010001000001011010100011100011010011100010100

• 101.100.010.011.010.010.001.000.001.011.010.100.011.100.011.010.011.100.010.100

• -> UTILIZANDO, EN CAMBIO, LA CODIFICACIÓN HUFFMAN, SE TENDRÍA QUE ENVIAR UNA SECUENCIA DE 53 BITS; 2,65 BITS POR SÍMBOLO.

• 01110110001100001001010110001101101101100110110000110

• 0111.0110.0011.0000.1001.0101.1000.1101.1011.0110.0110.1100.0011.0