Tareas

Cap´ ıtulo 2 C´digos Instant´neos. El o a algoritmo de Huffman
2.1. Introducci´n o

Cuando los s´ ımbolos del mensaje aparecen con frecuencias significativamente diferentes, se suele usar c´digos de longitud variable con el objetivo de o reducir la longitud de los mensajes codificados. Uno de los primeros ejemplos es el c´digo Morse, desarrollado por S. Morse a mediados del siglo XIX. En o estecaso se tiene en cuenta las frecuencias de las letras del alfabeto ingl´s. e Las letras se codifican en el alfabeto binario {·, −} como se indica:

A B C D E F

·− − · ·· − · −· −·· · · · −·

G H I J K

−−· · · ·· ·· ·−−−− −·−

L M N O P

· − ·· −− −· −−− · − −·

Q R S T U

− − ·− ·−· ··· − ··−

V W X Y Z

· · ·− ·−− −·− − · −− − − ··

En realidad, el c´digo es ternario, pueses necesario indicar d´nde termina o o 18

´ ´ CAP´ ITULO 2. CODIGOS INSTANTANEOS. EL ALGORITMO DE HUFFMAN19 cada palabra y empieza la siguiente (en los c´digos de bloque, este problema o no se presenta). Con el espacio como un s´ ımbolo adicional, se pueden separar las letras, con dos las palabras y con tres las frases. Puede representarse este c´digo en forma de ´rbol de la forma siguiente: oa

E I S U R F L P A W D N K

T M G O Q

H

V

J

B X C Y Z

La raz´n fundamental de usar c´digos de longitud variable es la de exo o plotar las diferencias entre las frecuencias de los s´ ımbolos del mensaje. En el c´digo Morse se tiene en cuenta incluso la diferencia de tiempo de transo misi´n entre · y -. Por eso se codifica E como ·, ya que la E es m´s frecuente o a que la T, quese codifica como -. A continuaci´n damos una tabla con las o frecuencias de aparici´n de las letras del alfabeto ingl´s en una p´gina de o e a “Oliver Twist”. A B C D E F 112 17 28 74 168 31 G H I J K 38 85 81 3 19 L M N O P 54 23 98 112 25 Q R S T U 1 90 86 142 33 V W X Y Z 14 42 1 27 0

Definici´n 2.1.1. Consideramos una fuente que produce mensajes formados o

´ ´ CAP´ ITULO 2. CODIGOSINSTANTANEOS. EL ALGORITMO DE HUFFMAN20 con las letras del alfabeto S = {a1 , .., an } y, para cada k = 1, .., n, sea pk la probabilidad de transmitir ak . Si C = {c1 , ..., cn } es el c´digo escogido (ck es o la palabra-c´digo que codifica la letra ak ), denotemos por Lk la longitud de ck . o Se define la longitud media del c´digo como L(C) = o pk Lk . Naturalmente, los s´mbolos del c´digo C pertenecen aun alfabeto A que, por lo general, ser´ ı o a binario. Interesar´ encontrar un c´digo que minimice esta longitud media. Otra a o cuesti´n importante es la de que el c´digo sea de decodificaci´n unica, de lo o o o ´ que nos ocupamos en el siguiente apartado.

2.2.

C´digos Instant´neos o a

En el c´digo Morse se presenta el problema siguiente: una palabra-c´digo o o puede ser la parte inicialde otra. Por ejemplo: E = · es parte inicial de A = ·−. Si se recibe ·, el receptor no sabe si E es lo correcto o deber´ esperar hasta que a lleguen m´s s´ a ımbolos, antes de decodificar. Se suele decir que el c´digo no es o instant´neo. En general, se dir´ que un c´digo es instant´neo cuando ninguna a a o a palabra-c´digo es parte inicial de otra. Si ´ste es el caso, todas las palabraso ec´digos est´n en hojas. Un buen ejemplo de c´digo instant´neo es el sistema o a o a de n´meros telef´nicos. 21715 y 2171529 no pueden ser simult´neamente u o a n´meros de tel´fono, pues al marcar el segundo sonar´ el primero. Existen u e a c´digos de decodificaci´n unica que no son instant´neos. Ejemplo: o o ´ a mensaje palabra-codigo a1 0 a2 01 a3 011 a4 0111

Este c´digo es de decodificaci´n unica,pues el 0 marca el inicio de cada o o ´ palabra-c´digo, pero no es instant´neo. o a

Teorema 2.2.1. (Kraft). Sea S = {a1 , .., an } el alfabeto de cierta fuente de informaci´n que se quiere codificar mediante un alfabeto A de q s´ o ımbolos.

´ ´ CAP´ ITULO 2. CODIGOS INSTANTANEOS. EL ALGORITMO DE HUFFMAN21 1) Si C es un c´digo instant´neo cuyas palabras-c´digo tienen longitudes o a o −Lk L1 ,...