UNIVERSIDAD DE PANAMÁ

CENTRO REGIONAL UNIVERSITARIO DE VERAGUAS

FACULTAD DE INFORMÁTICA, ELECTRÓNICA Y COMUNICACIÓN
DEPARTAMENTO DE INFORMÁTICA

FOLLETO
“TEORÍA DE LA INFORMACIÓN Y CODIFICACIÓN”
INF 324

PROFESORA
OLGA ESTER BATISTA GONZÁLEZ.

SANTIAGO 2005.
 i

ÍNDICE

ÍNDICE __________________________________________________________________ i

1. GENERALIDADES ___________________________________________________ 1

1.1. OBJETIVOS GENERALES _____________________________________________ 1

1.2. OBJETIVOS ESPECÍFICOS ____________________________________________ 1

2. DESCRIPCIÓN E IMPORTANCIA DE LA TEORÍA DE LA INFORMACIÓN Y

CODIFICACIÓN. _________________________________________________________ 2

3. NOCIONES BÁSICAS DE INFORMACIÓN. ______________________________ 4

3.1. CONCEPTO DE INFORMACIÓN. _______________________________________ 4

3.2. JERARQUÍA DE LA INFORMACIÓN. ___________________________________ 5

3.2.1. LOS DATOS ________________________________________________________________ 6
3.2.2. LAS NOTICIAS _____________________________________________________________ 7
3.2.3. LOS CONOCIMIENTOS ______________________________________________________ 8
3.2.4. SABIDURÍA: _______________________________________________________________ 9

3.3. CODIFICACIÓN DE LA INFORMACIÓN_________________________________ 9

3.4. CONCEPTOS BÁSICOS DE LA TEORÍA DE LA INFORMACIÓN ___________ 10

4. INTRODUCCIÓN A LOS CÓDIGOS. ___________________________________ 15

4.1. CONCEPTO DE CADENA _____________________________________________ 15

4.2. NOTACIÓN _________________________________________________________ 15

4.3. LONGITUD__________________________________________________________ 15

4.4. YUXTAPOSICIÓN____________________________________________________ 15

4.5. EL COMPLEMENTO x c DE UNA CADENA BINARIA x __________________ 16

5. LOS CÓDIGOS ______________________________________________________ 19

5.1. DEFINICIÓN DE CÓDIGOS ___________________________________________ 19

5.2. DEFINICIÓN DE FUNCIÓN DE CODIFICACIÓN _________________________ 19

5.3. TIPOS DE CÓDIGOS _________________________________________________ 21

 ii

6. CÓDIGOS UNÍVOCAMENTE DECODIFICABLES. _______________________ 24

6.1. DEFINICIÓN DE CÓDIGO UNÍVOCAMENTE DECODIFICABLE. __________ 24

6.2. TEOREMA DE MC MILLAN’S. ________________________________________ 25

7. CÓDIGOS INSTANTÁNEOS Y EL TEOREMA DE KRAFT. ________________ 28

7.1. DEFINICIÓN DE CÓDIGOS INSTANTÁNEOS ___________________________ 28

7.2. DEFINICIÓN DE PROPIEDAD DE PREFIJO _____________________________ 29

7.3. TEOREMA DE KRAFT. _______________________________________________ 29

7.4. SÍNTESIS DE UN CÓDIGO INSTANTÁNEO. _____________________________ 32

7.5. INECUACIÓN DE KRAFT. DISCUSIÓN. ________________________________ 33

8. CODIFICACIÓN EFICIENTE _________________________________________ 35

8.1. FUENTE DE INFORMACIÓN. Longitud Promedio de un Código. ____________ 35

8.2. DEFINICIÓN DE FUENTE DE INFORMACIÓN. __________________________ 35

8.3. CODIFICACIÓN DE HUFFMAN. _______________________________________ 37

9. LA INFORMACIÓN Y SUS FUENTES. CODIFICACIÓN SIN RUIDO. _______ 41

9.1. FUENTE DE INFORMACIÓN DE MEMORIA NULA. _____________________ 42

9.1.1. DEFINICIÓN DE INFORMACIÓN. ____________________________________________ 43

9.2. PROPIEDADES DE ENTROPÍA. ________________________________________ 46

9.3. PROPIEDADES DE ENTROPÍA DE FUENTE DE MEMORIA NULA ________ 51

10. PROBLEMA FUNDAMENTAL DE LA CODIFICACIÓN DE FUENTES DE

INFORMACIÓN ________________________________________________________ 53

10.1. LONGITUD MEDIA DE UN CÓDIGO.___________________________________ 53

 Folleto-“Teoría de la información y Codificación” 1

1. GENERALIDADES
Este folleto ha sido elaborado considerando el programa de la asignatura de Teoría de la Información y
Codificación (Inf. 324) de la Licenciatura en Ingeniería en Informática de la Universidad de Panamá.
El mismo resalta, brevemente la descripción e importancia de la Teoría de la Información y
Codificación, y presenta el desarrollo los contenidos: Nociones Básicas de Información, los códigos,
los códigos unívocamente decodificables, los códigos instantáneos y el teorema de Kraft, la
codificación eficiente, la información y sus fuentes y el problema fundamental de la codificación de
fuentes de información.

1.1. OBJETIVOS GENERALES

1. Aplicar los conceptos básicos de la Teoría de la información al estudio de los algoritmos para
la compresión de la información, la detección, y corrección de errores de transmisión o
recuperación de datos.
2. Realizar un estudio de la Teoría de la información que aborde el problema: Transmisión de la
información, desde un punto de vista probabilístico.
3. Presentar algunas técnicas de codificación y decodificación de la información, básicamente
binarias.

1.2. OBJETIVOS ESPECÍFICOS

1. Definir conceptos básicos de la teoría de la información y codificación.
2. Calcular el número de mensajes posibles de longitud "m" en un código de "n" símbolos.
3. Determinar la base que nos permite un código óptimo.
4. Deducir la fórmula de la medida de la información de Hartley.
5. Obtener el número de cadena y de códigos que cumplen determinada condición.
6. Estudiar las propiedades de códigos unívocamente decodificables e instantáneos.
7. Aplicar la inecuación de Kraft y MC Millan para la construcción de un código instantáneo y
unívoco, respectivamente.
8. Definir matemáticamente teoría de la información.
9. Encontrar el valor máximo de la entropía en una fuente de información de memoria nula con
un alfabeto de q símbolos.
10. Estudiar el problema fundamental de la codificación de fuente de información.
Folleto-“Teoría de la información y Codificación” 2

1.3. DESCRIPCIÓN E IMPORTANCIA DE LA TEORÍA DE LA INFORMACIÓN Y

CODIFICACIÓN.
Cuando se habla de computadoras como máquinas capaces de tratar automáticamente la
información (realmente lo que manipulan son representaciones simbólicas de dicha
información), se está haciendo referencia a multitud de posibles procesamientos, entre los que
se pueden indicar:
 Adquisición automática de información, lo que implica su traducción o codificación a fin de
lograr una representación de dicha información en el "interior" de la computadora.
 Procesamiento automático de la información, que es en principio el objetivo buscado para la
construcción de las computadoras.
 Almacenamiento de la información, ya que quizás la información introducida y/o procesada
no es requerida en el mismo instante en el que ya se encuentra disponible después de su
tratamiento.
 Transferencia automática de la información, permitiendo así la comunicación de dicha
información entre distintos sistemas de computación o seres humanos.
 Representación de la información transferida y/o procesada en un formato inteligible o útil
para el ser humano u otra máquina

En esta descripción funcional de una computadora, en todos los puntos aparece la palabra
información, y por lo tanto debería existir un paso previo a todo lo indicado anteriormente, en
el que se estudiase cuidadosamente todo lo relativo a ello.
Así, habría que definir lo que se entiende por información, qué propiedades tiene, si es posible
medir la cantidad de información. También sería tremendamente interesante poder construir
modelos (abstractos en un principio) de sistemas que generen información, y a partir de ellos y
mediante las herramientas matemáticas adecuadas, poder deducir propiedades que de alguna
manera puedan ser útiles en el mundo real.
Llegado este punto, introducir el concepto de código es inmediato, ya que no es más que el
establecimiento de una correspondencia entre la información por representar y el conjunto de
símbolos que la representen, idea que coincide con el concepto matemático de
correspondencia.
Folleto-“Teoría de la información y Codificación” 3

El siguiente paso es unir los conceptos de fuente de información con el de código, con lo que
se obtendrá un modelo que proporciona a su salida información ya codificada, es decir, lista
para ser transformada y/o transferida por una computadora. En este punto entra en juego un
parámetro muy importante en el mundo real: el coste y la eficiencia económica. Así, se pueden
indicar las siguientes consideraciones:
 Conviene utilizar códigos que sean eficientes en cuanto al coste de transmisión; para
transmitir un mensaje se debería utilizar su representación codificada de la manera más
breve, con lo que los gastos en equipos de transmisión sean lo más bajos posibles.
 Conviene utilizar códigos que permitan almacenar la información utilizando el menor
espacio posible, ahorrándose por lo tanto en equipos como son unidades de disco o cinta,
etc.
 También es muy importante la creación de códigos seguros, es decir, que mantengan la
información del mensaje original accesible sólo a aquellos usuarios autorizados, mientras
que para el resto de los usuarios resulte ininteligible. Este aspecto es tratado por la
criptografía.
Como se ha podido observar en los últimos puntos, el estudio de la representación de la
información (es decir, los códigos), conlleva una serie de aspectos de elevadísimo interés
económico, y cuya aplicación al mundo real es indiscutible.
Otro paso que se va a modelar en la teoría de la información es el hecho de la transmisión de la
información entre dos sistemas, el emisor y el receptor. Es bien conocido que durante el
transporte las señales que codifican o representan la información pueden sufrir, y de hecho
sufren, modificaciones aleatorias que provocan cambios en el mensaje transmitido. Estos
errores, tal y como se ha indicado, son de naturaleza aleatoria, y de nuevo las matemáticas
permiten establecer modelos para su estudio y, a través de estos modelos, se determinan y
descubren las propiedades que les son inherentes. Al modelo que describe las posibles
transformaciones en el mensaje codificado durante su transmisión (aunque dichas
transformaciones pueden darse también durante el tratamiento o el almacenamiento del
mensaje codificado) se le denomina canal de información.
Estudiando los canales de información, al igual que ocurría con las fuentes de información,
pueden extraerse una serie de conclusiones muy interesantes y de aplicación inmediatas al
mundo real, como son buscar maneras de representar la información (códigos) para ser
Folleto-“Teoría de la información y Codificación” 4

enviada a través de un sistema de transmisión que posee ruido, de tal manera que la presencia
de los errores debidos a ruido afecte lo menos posible al contenido del mensaje enviado. Es
decir, se buscan códigos que minimicen el efecto del ruido y permitan reconstruir el mensaje
original sin ningún error, a pesar de que el medio de transmisión tenga ruido.

2. NOCIONES BÁSICAS DE INFORMACIÓN.

2.1. CONCEPTO DE INFORMACIÓN.

No es conveniente dar el nombre de información a ciertos modos de adquisición de
conocimientos que no pueden describirse explícitamente, tales como, por ejemplo, el
aprendizaje por reflejos condicionados o el que alguien o algo pueda adquirir,
espontáneamente, por interacción inconsciente con su entorno. Con ello se restringe bastante el
concepto de información, pero, a pesar de todo, aún permanece demasiado poco preciso. Esto
conduce a dos situaciones que son peligrosas: La primera concierne a que todo puede parecer
información; la segunda a que, como no es precisa, se quede uno en la indecisión de si algo es,
o no, información. Para obviar ambos peligros es necesario construir un modelo válido, para
todos los casos, que sea fácil de usar. Para ello, cuando se habla de un fenómeno, no es posible
esperar aprender algo válido para él si está totalmente determinado. Dicho de otra manera, de
algo invariable nada se puede decir que alguien no respondiera: «Ya lo sabía, siempre es así.»
En consecuencia, no puede existir información más que a propósito de un elemento variable, el
cual se podrá presentar en diferentes estados. La única cosa que se puede decir de ese
fenómeno es cuál de esos estados es el que actualmente se está produciendo. De todo ello, es
posible dar una definición de información más neutra del modo siguiente: «Dado un fenómeno
variable cualquiera, hay información cuando se designa el estado actual del fenómeno.»
Todo el mundo tiene una idea intuitiva de lo que es información: un mensaje, una imagen de
televisión, el resultado de una medición física, etcétera. Todos estos elementos de información
presentan una serie de propiedades comunes:
 A fin de transmitir el contenido de un mensaje o el resultado de una medición, éste(a)
debería ser desconocido para el receptor antes de la recepción. Un mensaje cuyo contenido
se conoce antes de haberlo leído no aporta información. Esta propiedad puede también
expresarse como sigue: debe haber más de una posible secuencia de símbolos, patrones o
Folleto-“Teoría de la información y Codificación” 5

valores numéricos antes de la recepción. Durante la recepción, esta incertidumbre se elimina

y la elección queda limitada a una secuencia particular.
 Con el fin de recibir información verdadera, se puede exigir, además, que el receptor pueda
entender el significado del mensaje. Así, por ejemplo, un mensaje en un lenguaje
desconocido o cifrado, sin la clave, no constituye información.
 Adicionalmente se puede imponer la condición de que el mensaje sea relevante para el
receptor. Esto es, o tiene valor para el receptor, o éste puede usar el mensaje para tomar una
decisión o para iniciar una acción con fundamento de causa.
Con el advenimiento de la sociedad postindustrial, se está pasando de una sociedad donde el
principal activo de una organización es su mano de obra a otra donde prevalece el poder de la
información o, si se quiere, de una sociedad de manufactura a otra de mentefactura, con todo
lo que ello implica. En esta sociedad, como se ha mencionado, el recurso transformado
principal es la información, como fórmula susceptible de aportar conocimientos; su recurso
estratégico son los propios conocimientos, y su principio axial la codificación de dichos
conocimientos.
Esta codificación es especialmente importante si se piensa que ya nadie es capaz de guardar en
su memoria la cantidad de información necesaria para la toma de decisiones trascendentes, por
lo que la utilización de las computadoras y la codificación magnética de la información es algo
absolutamente cotidiano. De todo esto cabe resaltar dos aspectos de la información:
 El primero concierne al punto de vista humano de la misma: En él es importante el uso que
se va a hacer de la información y cómo se interpreta.
 El segundo se refiere al punto de vista de las máquinas: Lo importante es, en la mayoría de
los casos, cómo se codifica la información.

2.2. JERARQUÍA DE LA INFORMACIÓN.

La información aparece día a día bajo diferentes formas y adoptando nombres muy variados. En
efecto, datos, noticias y conocimientos, que conforman lo que se denomina genéricamente
información, se usan de distinta forma en diferentes contextos con, a veces, distintos y otros
equivalentes significados. Así, se usará el término información o informaciones como un término
genérico que, de acuerdo con el nivel de uso, se emplea para designar indiscriminadamente a los
datos, noticias y los conocimientos.
Folleto-“Teoría de la información y Codificación” 6

La sociedad actual está agobiada por montañas de información, esto es, datos, noticias y
conocimientos que, para ser útiles, exigen, cuando menos, una rápida clasificación. Aquellos
que son capaces de clasificar, sintetizar, almacenar y aplicarlos adecuadamente, se convierten
en expertos en un dominio. Dado que pocas personas tienen tiempo, interés, medios o recursos
para convertirse en expertos, hace que la gente se base en la experiencia de otros para
satisfacer sus necesidades de información.
Sin una adecuada clasificación de la abrumadora cantidad de datos y tiempo para organizar las
noticias, la gente actúa como si estuviera en la edad de los datos. Transformar los datos en
noticias fue el desafío de la sociedad de los ochenta, convertir las noticias en conocimientos
fue el reto de la sociedad de los noventa.
La información, genéricamente considerada, forma parte de un proceso jerárquico que va de los
datos a la sabiduría, y que aparece ilustrado en la figura 1.1

Fig.1.1 Jerarquía de la información

2.2.1. LOS DATOS

Son una representación formalizada de hechos o ideas capaces de ser comunicada y/o
manipulada por algún proceso. Según las normas INOR, un dato es una representación de
Folleto-“Teoría de la información y Codificación” 7

hechos o conceptos, hecha de una manera formalizada, apta para su comunicación,

interpretación o elaboración, bien por seres humanos o por medios automáticos. Es decir, los
datos, por tanto, denotan los hechos y conceptos sin refinar, expresados en forma de
sentencias, y constan de valores y figuras. Un receptor acumula hechos y figuras para su
proceso. Los datos comprenden los materiales en bruto, y son los ingredientes para las
noticias. Estos ingredientes se recolectan, clasifican e interpretan. Sin este proceso adicional,
los datos son de poca utilidad.
El teorema de Pitágoras, que dice: «La suma de los cuadrados de los catetos es igual al
cuadrado de la hipotenusa», es una sentencia declarativa y, por tanto, es un dato. Otros datos
de este tipo son la definición declarativa de circunferencia. Quien conozca sólo datos no puede
actuar sobre ellos sin proceso adicional.

2.2.2. LAS NOTICIAS

Las noticias son el significado que un ser inteligente, hombre o computadora, expresa o extrae
de los datos por medio de convenciones conocidas o de la representación particular usada.
Esto quiere decir que la característica más importante de las noticias es su aspecto semántico.
Los datos procesados forman noticias. En este punto, la diferencia entre datos y noticias viene
dada por la cantidad de ruido. El receptor analiza los datos separando los mensajes
significativos del ruido. Este análisis de los datos es un proceso clasificador basado en algunos
criterios establecidos. Las noticias resultan de la clasificación de los datos a través del análisis
englobando la interpretación de los datos en términos de elementos localizados y asociaciones.
El proceso de análisis reduce un gran cuerpo de material fuente en cuerpos más pequeños y
relacionados. De este modo, las noticias son una acumulación de datos refinados que pueden
ser una mercancía efímera. Por ejemplo, un individuo puede refinar todos los datos utilizables
acerca de los cerrojos y llegar a tener noticia acerca de un cerrojo particular en una aplicación
concreta. Después de que se ha completado la aplicación, ese cuerpo particular de noticias
puede no usarse de nuevo. Las noticias, por tanto, se usan durante un tiempo limitado y con un
alcance limitado.
Folleto-“Teoría de la información y Codificación” 8

2.2.3. LOS CONOCIMIENTOS

El siguiente proceso interno, denominado síntesis, debería producir beneficios más amplios y a
largo plazo. Las noticias se comparan con otras o se combinan en enlaces relevantes para
formar patrones de conocimientos. El resultado del proceso de síntesis es una asimilación
de noticias relevantes concentradas. Estas noticias deben sufrir una metamorfosis para llegar
a formar conocimientos. De este modo, la síntesis construye conjuntos de noticias producidas
durante el análisis. Los conocimientos surgen de la capacidad de crear un modelo fidedigno
que describa el objeto y ejemplifique las acciones que pueden ejecutarse sobre y con el objeto.
Arsac definió las noticias como una fórmula «escrita» susceptible de aportar conocimientos.
En consecuencia, se puede y deben distinguir los datos, o sintaxis de la fórmula, de las noticias
el significado que aportan, y de los conocimientos que eventualmente producen. Esto lleva,
naturalmente, a considerar los tres niveles de la información siguientes: El sintáctico o de
datos, el semántico o de noticias y el pragmático o de conocimientos. En este sentido, una
información se basa en datos o indicios, provoca noticias y va hacia consignaciones de hechos.
De este modo, la unión, entre información como noticias e información como conocimientos,
es razonable, pero no es posible llevarla más allá e identificar totalmente ambos términos.
Cuando la ignorancia o incertidumbre acerca de algún estado de un asunto se reduce por un
acto, tal como una observación, lectura, recepción de un mensaje, etc., el acto puede verse
como una fuente de información perteneciente al asunto sometido a consideración, entonces la
cantidad de información obtenida por el acto puede ser medida por la diferencia en la
incertidumbre existente antes y después del acto.
Una reducción de incertidumbre por un acto se consuma sólo cuando algunas opciones
consideradas posibles, antes del acto, se eliminan después de él. Esto exige una conexión
semántica entre la prospectiva obtenida a partir de los actos implicados (observaciones, mensajes
recibidos, resultados experimentales, etc.) y las entidades a las cuales se aplican. Cuando esta
conexión semántica está bien establecida, como en el contexto de una típica investigación
científica, la medida de incertidumbre y la información asociada se expresa aisladamente en
términos sintácticos.
Folleto-“Teoría de la información y Codificación” 9

2.2.4. SABIDURÍA:
A partir de la experiencia y los juicios críticos que actúan sobre los conocimientos, se alcanza la
sabiduría

2.3. CODIFICACIÓN DE LA INFORMACIÓN

Para un ser humano la codificación de la información es algo absolutamente natural. Desde
pequeño uno se acostumbra a utilizar un determinado lenguaje, la lengua de sus padres, de tal
forma que incluso puede resultar difícil imaginar que el lenguaje no es más que un sistema de
codificación de la información y que, por tanto, la información no se ha de confundir con el
lenguaje en que se transmite.
Sin embargo, para una computadora, este problema de la codificación de la información, que
ni siquiera es tal para la mayoría de las personas, se convierte en el primer factor que hay que
resolver para posibilitar la utilización de dicha computadora. La inmensa mayoría de los
sistemas informáticos construidos hasta la fecha usa el código de representación binario. Este
código, como su nombre indica, emplea solamente dos símbolos, 0 y 1, para representar
cualquier información. Por tanto, en una computadora, cualquier dato, noticia o conocimiento
deberá traducirse a una cadena de ceros y unos.
Evidentemente, este sistema de representación tiene sus ventajas y sus inconvenientes. Las
principales ventajas provienen del campo de la electrónica. En efecto, resulta muy fácil
manejar, por ejemplo, un condensador con un determinado nivel de carga, que se corresponde
con un 1 si supera un umbral y un 0 si no lo supera. Por otro lado, existen una serie de
aspectos menos favorables de este sistema de codificación. El primero de ellos es el de la
ininteligibilidad de cualquier información escrita en este código tan alejado del código más
natural para el ser humano: el lenguaje. Esto se resuelve de una forma bastante sencilla a
través de los programas de traducción que pasan de esta codificación binaria a otra entendible
por el usuario de la computadora.
Otro de los posibles aspectos negativos a tener en cuenta es el de la cantidad de información que
se puede representar con un código que consta apenas de dos símbolos. A pesar de lo que pueda
parecer, el número de símbolos del sistema de codificación no impone, por sí solo, un límite a la
cantidad de información representable. Pero, como se verá más adelante, para representar
información compleja se hace necesario utilizar cadenas extremadamente largas de ceros y unos,
Folleto-“Teoría de la información y Codificación” 10

lo cual entra en una confrontación abierta con la capacidad limitada de almacenamiento de

cualquier computadora. Como consecuencia de todo esto, surge una rama de la ciencia,
denominada Teoría de la Información, encargada de estudiar el poder expresivo y las
propiedades genéricas de cualquier sistema de codificación, incluido el código binario.

2.4. CONCEPTOS BÁSICOS DE LA TEORÍA DE LA INFORMACIÓN

La Teoría de la Información se dedica al estudio de los sistemas de comunicación que,
tradicionalmente, se representan de forma esquemática, según el esquema de la figura 1.2.
La fuente del mensaje es la persona o máquina que produce la información que se trata de
comunicar.
El codificador es el encargado de traducir el mensaje a un código susceptible de ser enviado
por el canal.
El código puede ser el código binario en el caso de la transmisión dentro de una computadora,
el código Morse en los antiguos sistemas telegráficos o una onda hertziana en el caso de las
transmisiones por radio.
El canal es el medio por el cual se transmite el mensaje.
El decodificador opera de forma inversa al codificador encargándose de traducir el mensaje
codificado a su forma original o bien a un código comprensible para el destinatario.
Esta tarea puede verse complicada por efecto del ruido, término general que engloba
cualquier circunstancia capaz de producir errores en la transmisión del mensaje a través
del canal.

Fig 1.2 Representación tradicional de un sistema de comunicación

La codificación es una operación que permite representar la información (conjunto de
posibilidades) mediante un código (conjunto de símbolos), de tal forma que exista una
correspondencia entre los elementos de ambos conjuntos. Cuando se utiliza una computadora
es necesario codificar cualquier información que se pretenda transmitir a la máquina mediante
un código compatible con sus posibilidades que, como ya se ha mencionado, es, en casi todos
los casos, el código binario. A partir de ahora se prestará una especial atención a este código.
Folleto-“Teoría de la información y Codificación” 11

Como ya se ha dicho, para que un mensaje transmita realmente información, y no simplemente

una secuencia de símbolos, es preciso que proporcione a su destinatario una novedad
imprevista. Esto es, la información que puede percibir un receptor de un mensaje está en
función del número de posibilidades que puede presentar dicho mensaje. Por tanto, la cantidad
mínima de información es la que se produce sobre un fenómeno que puede presentar dos
estados posibles. La información necesaria para romper la incertidumbre sobre cuál de estos
estados es el vigente en un momento determinado es la cantidad mínima de información que se
puede identificar y constituirá, en adelante, la unidad básica para medir la cantidad de
información.
Piénsese en un ejemplo concreto: una bombilla que puede estar encendida o apagada,
presentando, por tanto, dos estados posibles. Para comunicar a alguien, que no ve la bombilla,
el estado en que ésta se encuentra es necesario, como mínimo, un código con dos símbolos,
apagado y encendido o, de forma más sencilla, 0 y 1.
De acuerdo con estos principios, para medir la información sólo basta con contar las diferentes
posibilidades o estados del sistema; en el caso de la bombilla, hay dos posibilidades, por lo que
se podría hablar de una cantidad de información igual a 2. Si el fenómeno en consideración es
el lanzamiento de dos monedas al aire, existen cuatro posibilidades (cara-cara, cara-sello,
sello-cara y sello-sello). Si se considera un mensaje compuesto por tres símbolos (que toman
valor en las 28 letras del alfabeto) el número de posibilidades es 28 3.
En general, si se tratase de un mensaje de m caracteres de longitud y éstos pertenecen a
un alfabeto con n símbolos, el número total de mensajes diferentes sería de n m . Para el
caso particular del código binario, donde el alfabeto consta de dos símbolos, el número de
mensajes diferentes de longitud m es de 2 m .
Como se ve, a medida que aumenta el número de caracteres o símbolos de un mensaje se
incrementa de forma exponencial el número de mensajes posibles. Con el fin de evitar el
manejo de cifras excesivamente elevadas a la hora de hablar de la cantidad de información de
un mensaje, se adoptará una escala logarítmica. Así, en el caso del mensaje de m caracteres,
se hablará de una cifra equivalente a Log x n m . La base de logaritmos a emplear (la variable

x ) será 2. Esta decisión no es en absoluto arbitraria y se justifica mediante el siguiente

razonamiento: como se ha mencionado, para que exista información debe de existir más de un
Folleto-“Teoría de la información y Codificación” 12

mensaje posible; olvidando de momento cifras decimales, retómese el caso de la bombilla,

donde existen dos mensajes posibles, apagada y encendida, o los correspondientes 0 y 1. Este
caso podría representar la unidad básica de información, es decir, log x 2 = 1. Para que esta
igualdad se cumpla, la base de los logaritmos deberá ser la base 2.
Por tanto, las dos posibilidades, apagada y encendida, o lo que es lo mismo, un dígito binario
(0 ó 1) o bit, representa la unidad básica para medir la cantidad de información que, en
consecuencia, se denominará también bit.
En este punto se puede definir la cantidad de información, I , para una comunicación donde el
número de mensajes posibles es N de la siguiente forma: I = Log2 N
Esta breve disertación no pretende ser más que una pequeña introducción a uno de los
principales problemas de la teoría de la información: la medida de la información.
Tal es así, que muchos autores consideran ambos conceptos como indisociables, y sólo puede
hablarse de teoría de la información bajo la idea que la información es medible. Más adelante
se desarrollan algunos de los estudios fundamentales que se han realizado con respecto a la
cuantificación de la información
Folleto-“Teoría de la información y Codificación” 13

Trabajo individual Nº 1
Indicaciones:
 Conteste A las interrogantes de la asignación N°1.
 Discusión de las respuestas en la próxima clase.
Asignación N°1
1. Defina el término información.
2. Explique las tres propiedades comunes a todo elemento de la información.
3. Explique los dos aspectos de la información que caben resaltar en el advenimiento de la
sociedad post- industrial (sociedad del conocimiento).
4. Explique cada uno de los componentes del proceso jerárquico de la información,
genéricamente considerada.
5. Señale los tres niveles, que se pueden considerar, de la información.
6. ¿Cuál es el primer factor que debemos considerar para posibilitar la utilización de un
computador? Explique
7. Explique en qué consiste el código binario (símbolos empleados y en qué se traduce
internamente cada dato noticia o conocimiento en un computador). Señale las ventajas e
inconvenientes de este sistema de representación.
8. ¿Cuál es el objeto de estudio de la teoría de la información?
9. ¿Qué se entiende por ruido en la traducción (decodificación) del mensaje?
10. ¿Cuántos mensajes de m caracteres de longitud se pueden formar con un alfabeto de n
símbolos?
11. ¿Explique uno de los principales problemas de la teoría de la Información?
12. Explique cada uno de los componentes de un sistema de comunicación y haga su
representación esquemática tradicional.
13. Señale algunos de los posibles procesamientos que las computadoras como máquinas
capaces de tratar automáticamente la información pueden realizar.
14. Nombre que recibe el modelo matemático que describe las posibles transformaciones que
pueden darse en el mensaje codificado durante su transmisión.
15. Señale tres consideraciones que debemos tener presente en cuanto al coste y la eficiencia
económica de los códigos (Representación de la información).
Folleto-“Teoría de la información y Codificación” 14

Trabajo grupal Nº 2 (Forme grupo de estudiantes)

Elabore una monografía donde se desarrollan algunos de los estudios fundamentales que se han
realizado con respecto a la cuantificación de la información:
1. MEDIDAS CLÁSICAS DE LA INFORMACIÓN
2. LA MEDIDA DE HARTLEY
3. ENTROPÍA DE SHANNON
4. MEDIDAS DE CONFIANZA
5. CÓDIGO BINARIO
6. ¿POR QUÉ EL CÓDIGO BINARIO?
7. CÓDIGO ÓPTIMO
8. FUENTES DE INFORMACIÓN
Esta monografía será sustentada el día _____________________________________________________________..
Consultar como fuente de referencia básica: Enciclopedia de Informática y Computación. Tomo:
Deontología Informática (está en la hemeroteca). Puede consultar otras fuentes de información y haga la
cita correspondiente.
MONOGRAFÍAS (Orientaciones sobre qué es una Monografía? tomado del libro “Sustente su Tesis”. Autora:
Ileana Golcher)
Una monografía es el tratamiento por escrito de un tema específico. Para lograr este objetivo presenta en forma
ordenada el resultado de las lecturas exponiendo integralmente informaciones dispersas a fin de describir hechos y
fenómenos, es decir se remite a constatar empíricamente los elementos del objeto (diagnóstico). Su atributo esencial
no es la extensión, ya que puede contener pocas páginas o la dimensión de un libro.
Las monografías presentan así características fundamentales:
• Las extensión del trabajo varía en función de la naturaleza de la investigación.
• El propósito es sistematizar conocimientos sobre un tema específico
• Es un estudio profundo.
La metodología sugerida para elaborar una monografía indica que contiene tres grandes partes estrechamente
relacionadas:
1. INTRODUCCIÓN: en la que exponen de forma general la justificación y enfoque sobre el tema o problema a
desarrollarse y el método de análisis, que se utilizará para ordenar lógicamente las informaciones.
2. DESARROLLO: Texto principal o cuerpo central: Consiste en el análisis del tema o problema. Secuencia
ordenada de explicaciones y sus pruebas bajo un criterio de coherencia y sistematización. El investigador deberá
jerarquizar los trabajos consultados, distinguiendo los más relevantes, para luego ordenar los datos eligiendo
criterios particulares. Dependiendo de la naturaleza del tema y los intereses del investigador, pueden clasificarse
por épocas, escuelas, tendencias, analogía o coincidencias de los métodos o las perspectivas teóricas de los autores.
3. SÍNTESIS y CONCLUSIONES: De acuerdo a los datos analizados, muchas veces controversiales. Se exponen
crítica y sucintamente los resultados de la investigación.
Folleto-“Teoría de la información y Codificación” 15

3. INTRODUCCIÓN A LOS CÓDIGOS.

3.1. CONCEPTO DE CADENA

El concepto de cadena es fundamental en materia de la Teoría de la Información y Codificación.
Sea S = s1 , s2 ,..sn  un conjunto finito no vacío, al cual se hace referencia como un alfabeto.
Una cadena o palabra sobre S es simplemente una secuencia finita de elementos de S.
Ejemplo: Si S =  ,  ,1 ,2}
 ,  , 11 2, 2222 son cadenas (o palabras) de S.
Los términos cadenas o palabras son sinónimos y pueden ser usadas indistintamente

3.2. NOTACIÓN
Una cadena se denota por letras en negritas tales como: x, y, z.
Si x = x1 x 2 ...x k es una cadena sobre S entonces cada x i en x es un elemento de S.

3.3. LONGITUD
La longitud de una cadena x, denotada por len (x) , es el numero de elementos en la cadena.

3.4. YUXTAPOSICIÓN
La Yuxtaposición de dos cadenas x y y es al cadena xy.
Ejemplo: la yuxtaposición de x =101 , y =1000 es xy = 1011000.
Si una cadena tiene la forma z = xy ,se dice que x es el prefijo de z.
Ejemplo: 101 es el prefijo de 1011000, y 110 es un prefijo de 1101010.
Es claro que len (xy) = len (x) + len (y)
El Conjunto de todas las cadenas sobre S la denotaremos por S * Incluimos en S * la cadena
vacía, denotada por  , y definida como la cadena que no tiene elemento, su longitud
len (  ) = 0
Si n es un numero entero no negativo el conjunto de todas las cadenas sobre S de longitud n
es denotado por S n y el conjunto de todas las cadenas sobre S de longitud n o menos es
denotado por Sn
Entonces S n  Sn  S *
Folleto-“Teoría de la información y Codificación” 16

Ejemplo si consideramos la base binaria, una cadena sobre  2 = 0, 1 es llamada cadena
binaria. Cada uno de los elementos 0 y 1 es llamado un bit, el cual es una contracción de
dígito binario.
¿Cuántas cadenas de longitud 2 hay en el alfabeto 0,1 ?
01, 00, 10, 11 22 = 4
¿Cuántas cadenas de mensajes diferentes hay en el alfabeto 0,1  si la longitud de la cadena
es 3? 23 =8 000, 001, 010, 011, 111, 110, 101, 100.
¿Cuántas cadenas de longitud n hay en el alfabeto S = 0,1?
Existen 2n cadenas de mensajes diferentes
En general en un alfabeto S = s1, s2 ,...sb de b símbolos el número total de mensajes

(cadenas) de longitud n está dado por: b n = bbbb



n veces

Ejemplo 011101 es una cadena binaria de longitud seis.

3.5. EL COMPLEMENTO x c DE UNA CADENA BINARIA x

Está definido por la cadena obtenida al reemplazar todos los ceros por unos y todos los unos por
ceros. Ejemplo (110110)c = 001001.
Una cadena sobre  3 = 0, 1,2 se llama cadena ternaria.

Si cero está en el alfabeto denotamos por 0 la cadena que contiene sólo ceros 0=0000...0
En forma similar si el 1 está en el alfabeto, denotamos por 1 la cadena 1=1111...1
Ejemplo En  5 2 0=00000, 1=11111.
Para 0  i  n , denotamos por ei a la cadena que contiene todos los elementos ceros, excepto el

de la posición i , que es 1. En  4 2 , e1 = 1000 , e2 = 0100 , e3 = 0010 , e4 = 0001

TEOREMA [Link] S un alfabeto, con K  1 elementos, entonces el número de cadenas en S n y

S n , denotado S n y S n respectivamente, está dado por:

1) S n = K n

K n +1 − 1
2) S =
K −1
n
Folleto-“Teoría de la información y Codificación” 17

Prueba:
Parte 1 Observe que cada cadena en S n puede formarse escogiendo uno de los K
símbolos para la primera posición, uno para la segunda posición, uno para la tercera posición, y
así sucesivamente. Como hay K opciones para cada una de las n posiciones, el número de
KKK...
cadenas que pueden formase de esta manera es :  K , y por tanto S n = K n
n veces

Parte 2, Usando el resultado, que acabamos de obtener, se tiene que:

Sn = S 0 + S 1 + S 2 +  + S n Por definición de S n .

Sn = K 0 + K 1 + K 2 +  + K n Por Parte 1 S n = K n

Sn = 1 + K + K 2 +  + K n Resolviendo potencias triviales (*)

K Sn = K + K 2 + K 3 +  + K n+1 Multiplicando ambos miembros por K (**)

K Sn − Sn = (K + K 2 + K 3 +  + K n+1 ) − (1 + K + K 2 +  + K n ) Restando (*) de (**)

(K − 1) Sn = K n+1 − 1 Factorizando el miembro de la izquierda, y eliminando cantidades

opuestas en el miembro de la derecha

K n +1 − 1
Sn = Despejando S n , con lo cual queda demostrado el teorema 1
K −1
TEOREMA 2: En  r , el número de cadenas con exactamente k ceros esta dada por:
n

C k ( r − 1) n −k . En particular cuando es el alfabeto binario r = 2 , se tiene C k

n n

Ejemplo 1 En el conjunto  2 cuántas cadenas de longitud 8 hay.

8

Sn = Kn S 8 = 2 8 = 256 Cadenas

De ellas cuántas contienen exactamente tres ceros?

8! [Link]!
C3 = = = 8.7 = 56 Cadenas.
n 8
Ck
5!3! 5!.3!
Hay 56 cadenas de longitud 8 que contienen exactamente tres ceros.
Ejemplo 2. Considere el conjunto  3 . Cuántas cadenas de longitud 6 hay
6

Hay S 6 = 36 = 729 cadenas de longitud seis para un alfabeto de tres elementos.

Folleto-“Teoría de la información y Codificación” 18

De ellas cuantas contiene exactamente dos ceros.

C k ( r − 1) n −k = C2 (3 − 1) 6−2 =
n 6 6!
(2) 4 =
6.5.4!
(16) = 6.5.8 = 240 Cadenas.
4!.2! 4!.2
PRÁCTICA #1
TEMA: CADENAS
RESUELVA LOS SIGUIENTES PROBLEMAS CON LA AYUDA DEL MATERIAL DE LA
CLASE ANTERIOR.
EVALUACIÓN: PARTICIPACIÓN VOLUNTARIA EN LA RESOLUCIÓN DE CADA
PROBLEMA.
PROBLEMA 1

Cuántas cadenas de longitud 6 se pueden formar en un alfabeto de 3 elementos, 36 . De éstas

cuántas contienen exactamente dos ceros.
Resp. 729, 240 cadenas
PROBLEMA 2

Hallar el número de cadenas en 10

5 que contiene exactamente tres cero(s) y exactamente dos

uno(s).
Resp. 612360 cadenas

PROBLEMA 3

Hallar el número de cadena en 12

7 que contiene por lo menos nueve cero(s).

Resp. 49969 cadenas

PROBLEMA 4

¿Cuántas cadenas de longitud tres o menos se pueden formar en un alfabeto ternario 33 ,
Cuántas de longitud 10 o menos en este mismo alfabeto?
Resp 40, 88573 cadenas.
Folleto-“Teoría de la información y Codificación” 19

4. LOS CÓDIGOS
Un código no es más que un conjunto de cadenas sobre un cierto alfabeto. Por ejemplo, el

conjunto C = 0, 10, 110, 1110 es un código sobre el alfabeto  2 . Los códigos son usados
generalmente para codificar mensajes. Por ejemplo, podemos usar C para codificar las primeras
cuatro letras del alfabeto, así:
a→0
b → 10
c → 110
d → 1110

Luego podemos codificar palabras con estas letras. La palabra cab se codifica como 110010 .
Estas ideas nos permiten comprender las definiciones que presentamos a continuación.

4.1. DEFINICIÓN DE CÓDIGOS

Sea A = a1 , a2 , ... ar  un conjunto finito, el cual llamaremos alfabeto código. Un r – ario
*
código sobre A es un subconjunto C del conjunto A de todas las palabras (cadenas) sobre A .
Los elementos de C son llamadas palabras claves. El número “r” es llamado base del código.

El alfabeto comúnmente usado y estudiado es el conjunto  2 . Los códigos sobre  2 se

3
denominan códigos binarios. Los códigos sobre se denominan códigos ternarios.

4.2. DEFINICIÓN DE FUNCIÓN DE CODIFICACIÓN

Sea S = s1 , s2 , ... s q  un conjunto finito, al cual denominaremos alfabeto fuente Suponga que C

es un código. Una función de codificación es una función biyectiva

f : S → C ( de S sobre C )
Si C es un código y f : S → C es una función de codificación, nos referimos al par ordenado
(C, f ) como un esquema de codificación para S.
Debido a que la función de codificación es biyectiva (uno a uno y sobreyectiva), ella asocia a
cada símbolo del alfabeto fuente con una y solamente una palabra clave. Además a cada palabra
clave está asociada con un símbolo del alfabeto fuente. Esto hace posible decodificar cualquier
secuencia de palabras claves. Ejemplo: Las 26 letras del alfabeto pueden ser codificadas así:
Folleto-“Teoría de la información y Codificación” 20

Sea S el alfabeto fuente S = a, b, c, d ,..., z

Sea A el alfabeto código A = 0, 1, 2, ... , 9

Sea C el código C = 00, 01, 02, ..., 25

Sea f : S → C definida por:
a → 00 f(a) = 00
b → 01 f(b) = 01
c → 02 f(c) = 02
. .
. .
. .
z → 25 f(z) = 25
Esta función de codificación puede ser usada para codificar cualquier mensaje:
Ejemplo: Math is fun 120019070818052013
Intencionalmente usamos un número de dos dígitos para cada palabra clave. Si hubiéramos

tomado el código C = 0, 1, 2, ..., 25, hubiera surgido problemas, por ejemplo la cadena 1414
llevaría diferentes mensajes.
Bebe, oo, beo obe
Seguidamente se presenta parte de un código comúnmente usado, el ASCII: Código americano
estándar para el intercambio de información.
A 01000001 J 01001010 S 01010011
B 01000010 K 01001011 T 01010100
C 01000100 L 01001100 U 01010101
D 01000101 M 01001101 V 01010110
E 01000110 N 01001110 W 01010111
F 01000111 O 01001111 X 01010011
G 01001000 P 01010000 Y 01011000
H 01001000 Q 01010001 Z 01011001
I 01001001 R 01010010 Space 01011010
Este código es usado por las microcomputadoras para almacenar caracteres en la memoria o en
medios de almacenamiento y consiste de los números binarios desde 00000000 hasta 11111111
Folleto-“Teoría de la información y Codificación” 21

(desde 0 hasta 127 en el sistema decimal) Por ejemplo el código para la letra mayúscula A es
01000001 y en decimal es 65 (Alt+65).

4.3. TIPOS DE CÓDIGOS

Los códigos pueden ser divididos en dos tipos generales a saber:
▪ Código bloque(Código de longitud fija).
▪ Código de longitud variable.
Un código bloque es aquel cuyas palabras claves todas tienen la misma longitud n. En este caso
“n” se denomina longitud de código Si el código tiene palabras de diferentes longitudes se le
llama código de longitud variable.
Ventajas y desventajas de los códigos de longitud fija:
▪ Nunca requiere de un símbolo especial para separar los caracteres del mensaje que está
siendo codificado. Ejemplo: En el código ASCII sabemos que cada 8 bit representa un
carácter.
La principal desventaja de los códigos de longitud fija, tal como el ASCII, es que los caracteres
que son usados frecuentemente, tal como la letra c, tiene códigos tan largos como los caracteres
de uso menor frecuentemente como el carácter de espacio. Aquí juega papel importante los
códigos de longitud variable ya que pueden usar palabras claves cortas para codificar caracteres
frecuentemente usados ahorrando una gran cantidad de tiempo y espacio.
Ejemplos:
1. Suponga que usted quiere un código bloque binario que contiene 126 palabras clave.
¿Cuál es la longitud mínima posible de cada palabra para este código?

Por Teorema 1 la cantidad de palabras claves de longitud "n" exactamente es:

2 n = 126
Log 2 2 n = Log 2 126
S = K , como el código es binario k = 2
n n

n = log 2 126
n  7 ya que : 2 6  126  2 7

2. ¿Cuántas funciones de codificación son posibles en el alfabeto fuente S = a, b para el

código C = 0,1
Folleto-“Teoría de la información y Codificación” 22

Hay solamente dos funciones de codificación

Código
2!=2 0 1

Función
F: a b
G: b a

F(a)=0, F(b)=1
G(b)=1, G(a)=0
3. ¿Cuántas funciones de codificación son posibles en el alfabeto fuente S = a, b, c para el
código C = 00, 01, 11
Hay solamente 6 funciones de codificación:
Código
3!=3x2=6 00 01 11
F: a b c
G: a c b
Función

H: b a c
I: b c a
J: c a b
K: c b a

Desde F(a)=00, F(b)=01, F(c)=11

G(a)=00, G(c)=01, F(b)=11
…
Hasta K(c)=00, K(b)=01, K(a)=11

4. Encuentre una fórmula para el número de funciones de codificación desde el alfabeto

fuente de tamaño "n" hasta un código de tamaño "n" . Es decir: S = s1 , s2 , s3 , sn  y

C = c1 , c2 , c3 ,cn .

c1 c2 c3 cn

Hay n! Funciones .n ...n-1 ... n-2 = 1 n!

n! maneras diferentes de asignar los símbolo del alfabeto fuente , a las cadenas del código.
Folleto-“Teoría de la información y Codificación” 23

PRÁCTICA #2
TEMA: CÓDIGOS
RESUELVA LOS SIGUIENTES PROBLEMAS CON LA AYUDA DEL MATERIAL DE LA
CLASE CORRESPONDIENTE.
EVALUACIÓN: PARTICIPACIÓN VOLUNTARIA EN LA RESOLUCIÓN DE CADA
PROBLEMA.
PROBLEMA 1
¿Cuántos códigos bloques r-arios de longitud “n” hay sobre un alfabeto código A.
¿Cuántos códigos binarios hay de longitud 4?

PROBLEMA 2
¿Cuántos códigos r-arios con palabras claves de longitud máxima “n” hay sobre un
 
alfabeto código A = a1, a2 , ar . ¿Cuántos códigos binarios hay de longitud máxima 4?

 
Ayuda (para problema 1 y 2) Si X = a1 , a2 ,, an el número de subconjuntos de X está dado

por 2 n .

PROBLEMA 3
Suponga que usted requiere un código bloque r-ario que contiene n palabras claves.¿Cuál es la
longitud mínima posible de cada palabra clave para este código?
Si el alfabeto código es A = 0,1 y el código tiene 1020 palabras claves. ¿Cuál es la longitud
mínima posible de cada palabra clave.
Folleto-“Teoría de la información y Codificación” 24

5. CÓDIGOS UNÍVOCAMENTE DECODIFICABLES.

Una de las propiedades más importantes que un código puede poseer es la decodificación única.
Informalmente hablando, esto significa que cualquier secuencia de símbolos puede ser
interpretada a lo sumo de una forma como una secuencia de palabras claves.
Formalmente tenemos la siguiente definición.

5.1. DEFINICIÓN DE CÓDIGO UNÍVOCAMENTE DECODIFICABLE.

Un código C sobre un alfabeto A es unívocamente decodificable si para cada cadena x1 x 2  x n

sobre A existe a lo sumo una secuencia de palabras claves (palabras códigos) c1c2 cm para la

cual:
c1c2 cm = x1 x 2  x n

En otras palabras, un código es unívocamente decodificable si ninguna de dos secuencias

diferentes de palabras claves representan la misma cadena, sobre A . En forma simbólica esto es:
c1c2  cn = d 1d 2  d m para cada palabra clave c i y d j se tiene que:

m=n y c1 = d1 , c2 = d 2 ... cn = d m
Ejemplo: Considere los siguientes códigos:
C1 = c1 = 0, c2 = 01, c3 = 001 C2 = d1 = 0, d 2 = 10, d 3 = 110

C1 no es unívocamente decodificable, puesto que la cadena 001 representa dos secuencias

c3 → 001
diferentes de palabras claves 
c1c 2 → 001
C2 es unívocamente decodificable puesto que cualquier cadena corresponde a lo sumo a una

secuencia de palabras claves.

Por ejemplo 1000110, leyendo de izquierda a derecha, vemos que 1 no es por si mismo una

palabra clave, pero 10 si es. Además solamente una palabra clave empieza con 10 (d 2 ) . Después

vemos a un cero, el cual debe representar d1 , ya que ninguna otra palabra clave empieza con
cero. Continuando de esta manera, vemos que esta cadena representa sólo una secuencia de
palabras claves (d 2 d1d1d 3 ) .
Folleto-“Teoría de la información y Codificación” 25

Para probar que C2 es unívocamente decodificable es necesario enunciar una serie de

observaciones que muestren que cualquier secuencia X dada de palabras claves pueden ser
interpretada de una sola manera. Asumiendo que X es leída de izquierda a derecha tenemos las
siguientes observaciones:
▪ Si encontramos a cero este debe representar a d1 .
▪ Si encontramos a un uno seguido por un cero este debe representar a d 2 .
▪ Si encontramos a un 1 seguido de otro 1, el próximo elemento debe ser un cero y así esta
secuencia debe representar a d 3 .

En general si un código es unívocamente decodificable, entonces este no puede contener

demasiadas palabras claves cortas.
Ejemplo si la palabra 010011 de longitud 6 es una palabra clave, entonces la palabra 010 y 011
de longitud 3 no pueden ser ambas palabras claves. Podemos ser más precisos acerca de la
longitud de las palabras claves en el siguiente teorema, conocido como Teorema de Mc Millan’s
(publicado por primera vez en 1956).

5.2. TEOREMA DE MC MILLAN’S.

Supongamos que C = c1 , c2 , , cq  es un código r-ario y sea li = Long(ci ) . Si C es

unívocamente decodificable, entonces las longitudes de sus palabras claves l1 , l2 , l q deben

q
1
satisfacer r
k =1
lk
 1 donde r es el número de elementos del alfabeto código.

La desigualdad en el Teorema de Mc Millan’s se llama Desigualdad de Kraft’s. El Teorema de

Mc Millan’s confirma que, para un código unívocamente decodificable las longitudes de las
palabras claves deben ser razonablemente grandes. (los números l i deben ser grandes a fin de

1
hacer los términos pequeños).
r li
Ejemplo: Suponga que queremos un código binario consistente de 6 palabras claves, pero
restringimos las longitudes de las palabras claves a un máximo de 2 (es decir li  2 para

i = 1,2, 6 ).
Puesto que hay precisamente 6 cadenas no triviales sobre A = 0,1 de longitud a lo sumo 2,
nuestro código debe consistir de estas seis cadenas. Es decir:
Folleto-“Teoría de la información y Codificación” 26

C = 0, 1, 00, 01, 10, 11. Pero este código no es unívocamente decodificable. La cadena 01 tiene
01 → c 4
dos interpretaciones:
01 → c1c 2

En este caso la poca longitud de las palabras claves nos obliga a usar palabras claves tal como 01
que son echas de palabras claves más pequeñas como (0 y 1). Esto impide al código ser
unívocamente decodificable.
Por supuesto que podía usar el Teorema de Mc Millan’s para decir que tal código no podría ser
unívocamente decodificable. En este caso:
li  2 para i = 1,2, 6

r li  r 2
1 1
De donde li
 2
r r
q q
1 1
Aplicando la sumatoria i =1 r li
 
i= r2
6 6
1 1
i =1 r li
 
i= r2
6 6
1 1
Como r = 2 i =1 r li
 
i= 22
6
1  1 
i =1 r li
 6 2 
2 
6
1 6
i =1
 
r li  4 
6
1 3
i =1
 1
r li 2
Lo que nos indica que la desigualdad de Kraft’s no se verifica para este código, por lo tanto este
no puede ser unívocamente decodificable.
Note que el Teorema de Mc Millan’s no puede decirnos cuándo un código particular es
unívocamente decodificable, sino sólo cuando no lo es. El teorema no nos dice que cualquier
código cuya longitudes de las palabras claves satisface la desigualdad de Kraft’s debe ser
unívocamente decodificable. Más bien, dice que si un código es unívocamente decodificable,
entonces la longitud de sus palabras claves deben satisfacer la desigualdad de Kraft’s. Así pues,
Folleto-“Teoría de la información y Codificación” 27

si un código no satisface esta desigualdad, podemos concluir que no es unívocamente

decodificable.
PRÁCTICA #3
TEMA: CÓDIGOS UNÍVOCAMENTE DECODIFICABLES.
RESUELVA LOS SIGUIENTES PROBLEMAS CON LA AYUDA DEL MATERIAL DE LA
CLASE CORRESPONDIENTE.
EVALUACIÓN: PARTICIPACIÓN VOLUNTARIA EN LA RESOLUCIÓN DE CADA
PROBLEMA.
1. Es el código C = 0, 10, 1100, 1101, 1110, 1111 unívocamente decodificable. Justifique.
2. Es el código C = 0, 10, 110, 1110, 11110, 11111 unívocamente decodificable. Justifique.
3. Es el código C = 0, 01, 011, 0111, 01111, 11111 unívocamente decodificable. Justifique.
4. Es el código C = 0, 10, 1101, 1110, 1011, 110110 unívocamente decodificable. Justifique.
5. Determine si hay o no un código binario unívocamente decodificable con longitudes de
palabras claves 1, 3, 3, 3, 4, 5, 5, 5. Si es así construya tal código.
Respuestas Sí, sí, sí, no, no.
Folleto-“Teoría de la información y Codificación” 28

6. CÓDIGOS INSTANTÁNEOS Y EL TEOREMA DE KRAFT.

Es claro que la decodificación única es una propiedad muy deseable. Sin embargo aunque un
código puede tener esta propiedad, aún no puede ser posible interpretar las palabras claves tan
pronto como son recibidas.
Ejemplo:
C3 =  c1 = 0, c2 = 01
El código
Es fácil ver que es unívocamente decodificable.
Ahora supongamos que la cadena 0001 esta siendo transmitida. Justo después de recibir el

primer cero, no podemos decir si esta debería ser interpretado como la palabra clave c1 0 como

el comienzo de c2 . Una vez que recibimos el segundo cero en el mensaje, sabemos que el

primer cero debe ser c1 , pero no sabemos acerca del segundo cero. Así las palabras claves no
pueden ser interpretadas tan pronto como ella son recibidas.

Por otro lado el código C4 =  d1 = 0, d 2 = 10 las palabras claves individuales pueden ser
interpretadas tan pronto como son recibidas.
Por ejemplo: considere la cadena 00100. Tan pronto como el primer cero es recibido, sabemos

inmediatamente que este debe ser de d1 y similarmente para el segundo 0. Cuando el 1 es

recibido sabemos que un cero viene después, y que la cadena 10 debe ser d 2 . Así el mensaje
puede ser interpretado palabra clave por palabra clave.

6.1. DEFINICIÓN DE CÓDIGOS INSTANTÁNEOS

Un código se dice instantáneo, siempre que en cualquier secuencia de palabras claves, cada
palabra clave puede ser interpretada tan pronto como es recibida.
Si un código es instantáneo entonces este es también unívocamente decodificable.
Sin embargo lo inverso no es verdad. Hay código que son unívocamente decodificables, pero no
instantáneo como el código.
C3 =  0, 01

Hay una forma simple de decir cuando un código es instantáneo. Para ello necesitamos de la
siguiente definición.
Folleto-“Teoría de la información y Codificación” 29

6.2. DEFINICIÓN DE PROPIEDAD DE PREFIJO

Se dice que un código tiene la propiedad de prefijo si ninguna palabra clave es un prefijo de
cualquier otra palabra clave.
Ejemplo:
El código C2 =  d1 = 0, d 2 = 10, d 3 = 110 tiene la propiedad de prefijo.

Sin embargo el código C1 = c1 = 0, c2 = 01, c3 = 001 no tiene esta propiedad puesto que c1 es

un prefijo de c2 ( y de c3 )

La importancia de la propiedad de prefijo viene del siguiente teorema.

TEOREMA: Un código C es instantáneo sí y solo sí este tiene la propiedad de prefijo.
Demostración:
(Un código C es instantáneo entonces este tiene la propiedad de prefijo).
Por reducción al absurdo. Suponga que C es instantáneo. Si una palabra clave “c” es un prefijo
de una palabra clave “d”, entonces la primera c en la secuencia cc no puede decodificarse hasta
que recibamos al menos un símbolo adicional, para cuando hallamos recibido solo la primera
cadena c, no podemos decir si o no esta debería ser interpretada como una c o como el comienzo
de una cadena d . Así, ninguna palabra clave es un prefijo de otra palabra clave y C tiene la
propiedad de prefijo.
(Si un código tiene la propiedad de prefijo entonces C es instantáneo).
Supongamos que C tiene la propiedad de prefijo. Luego tan pronto como la primera palabra
clave es recibida, podemos decodificarla, puesto que esta no puede ser un prefijo de otra palabra
clave. El mismo razonamiento se aplica a la segunda palabra clave y a todas las palabras claves
en la secuencia. Así el código C es instantáneo.
Ejemplo: puesto que el código C2 =  d1 = 0, d 2 = 10, d 3 = 110 tiene la propiedad de prefijo, el

teorema anterior nos dice que es instantáneo.

6.3. TEOREMA DE KRAFT.

Ahora veremos el teorema que nos dice precisamente cuando existe un código instantáneo con
l1 , l2 , l3 , ...lq
longitudes de palabras claves . Este teorema fue publicado por primera vez por L.G.
Kraft en 1949.
TEOREMA (Kraft’s)
Folleto-“Teoría de la información y Codificación” 30

C = c1 , c2 ,  cq 
1. Existe un código C r-ario instantáneo con longitudes de palabras
l1 , l2 , l3 , ...lq
claves sí y solo sí estas longitudes satisfacen la desigualdad de Kraft’s
q
1
r
k =1
lk
1

2. Si C es un código r-ario instantáneo. Entonces C es r-ario maximal, es decir no está

contenido en cualquier código estrictamente más grande, sí y solo sí, se cumple la
igualdad en la desigualdad de Kraft’s
q
1
r
k =1
lk
=1

3. Si C es un código instantáneo con longitudes máximas de palabra clave “m”. Si C no es

maximal, entonces es posible añadir una palabra clave de longitud “m” a C sin destruir la
propiedad de ser instantáneo.
Nota que el Teorema de Kraft’s dice que, si las longitudes l1 , l2 , l3 , ...lq satisfacen la desigualdad

de Kraft’s , entonces allí debe existir algún código instantáneo con estas longitudes de palabras
claves . Esto no dice que cualquier código cuyas longitudes de palabras claves satisfagan la
desigualdad de Kraft’s debe ser instantáneo.
Resuelva la siguiente situación:
Pruebe que el código binario C = 0, 11, 100, 110, satisface la desigualdad de Kraf’s, pero no es
instantáneo.
Sea A = 0, 1, 2 y suponga que l1 = 1, l2 = 1, l3 = 2, l4 = 4, l5 = 4, l6 = 5 , si es posible encontrar un
código con estas longitudes de palabras claves, entonces construya tal código.
El Teorema de Kraft’s y el Teorema de Mc Millan’s juntos nos dicen algo interesante acerca de
la relación entre códigos unívocamente decodificables y y códigos instantáneos en particular si
l1 , l2 , l3 , ...ln
existe un código unívocamente decodificable con longitudes de palabras claves ,
entonces de acuerdo con el Teorema de Mc Millan’s , estas longitudes deben satisfacer la
desigualdad de Kraft’s. Entonces podemos aplicar el teorema de Kraft’s para concluir que
también debe existir un código instantáneo con esas longitudes de palabras claves. En resumen,
al respecto, tenemos el siguiente teorema:
Folleto-“Teoría de la información y Codificación” 31

TEOREMA ( Códigos unívocamente decodificables y códigos instantáneos)

Si existe un código unívocamente decodificable con longitudes de palabras claves l1 , l2 , l3 , ...lq

entonces debe existir un código instantáneo con estas mismas longitudes de palabras claves.
Nuestro interés en este teorema se verá más tarde cuando regresemos a la pregunta de encontrar
códigos deseables con longitudes de palabras lo más cortas posibles. Esto nos dice que no
perdemos nada considerando sólo los códigos instantáneos (mas bien que todos los código
unívocamente decodificables)
Ejemplo: Sea A = 0,1. Suponga que se necesita un código instantáneo C que contiene las
palabras claves 0, 10, 110. ¿Cuántas palabras claves adicionales de longitud 5 podrían ser
añadidas a este código?
Solución:
Según la situación planteada se desea obtener un código instantáneo maximal.
Sea x la cantidad de palabras claves de longitud 5 que podemos añadir:
q q
1 1 1 1 1 x

k =1 r
lk
=1 r
k =1
lk
= + 2 + 3 + 5 =1
2 2 2 2
Entonces debe cumplirse: es decir:
1 1 1 x
+ 2 + 3 + 5 =1
Luego: 2 2 2 2
7 x
+ = 1 de donde x = 4
8 32
Se pueden añadir a lo suma 4 palabras claves de longitud 5. Es fácil hallar que el código
solicitado es:
C = 0, 10, 110, 11100, 11101, 11110, 11111
PRÁCTICA:
1. Escriba los prefijos de la palabra clave c1 = 0111
2. Suponga que deseamos codificar la salida de una fuente decimal S = 0, 1, 2, 3,,9, en
un código instantáneo binario. Admitamos además, que existe una razón que aconseja
codificar los símbolos 0 y 1 de la fuente decimal en palabra binarias relativamente cortas.
Este requisito se presenta realmente en una fuente que emite muchos más 0s y 1s que 2s,
3s, etc. Si codifican los 0s y 1s de la fuente en la siguiente forma:
0 →0 1 → 10
Folleto-“Teoría de la información y Codificación” 32

¿Cuán cortas podemos hacer las ocho palabras claves restantes. Si se exigen que tenga la misma
longitud? Escriba el código solicitado.

6.4. SÍNTESIS DE UN CÓDIGO INSTANTÁNEO.

La naturaleza de los requisitos que debe cumplir un código instantáneo puede apreciarse más
claramente analizando el procedimiento de síntesis de códigos en su forma más sencilla.
Intentaremos sintetizar un código instantáneo binario a partir de una fuente de cinco símbolos.

Comenzaremos asignando un 0 al símbolo S1 :

S1 → 0
Según esto, todos los demás símbolos de la fuente deben asociarse a palabras que comiencen por
1. De no ser así, S1 será prefijo de otra palabra del código. El símbolo S 2 no debe asociarse a
la palabra formada por el símbolo aislado 1, de hacerse, no quedaría ningún símbolo con el que
pudieran comenzar las tres restantes palabras. Puede adoptarse
S 2 → 10
lo que exige que los demás códigos comiencen por 11. Si
S 3 → 110

el único prefijo de tres bits sin utilizar es 111, por lo que puede hacerse
S 4 → 1110 y
S 5 → 1111

Hay que destacar que por el hecho de asignar a S1 el valor 0, automáticamente se limita el
número de posibles palabras código. Dado este paso deberemos concretarnos a palabras que
empiezan por 1. Puede imaginarse, por lo tanto, que si seleccionamos una palabra de 2 binits
para representar a S1 , tendríamos un mayor grado de libertad en la elección de las siguientes, y
llegaríamos incluso a evitar palabras tan largas como las dos últimas del código anterior.
Probaremos esta sugerencia sintetizando un nuevo código binario instantáneo con los mismos
símbolos; comenzaremos por hacer
S1 → 00

Por lo que podremos elegir S 2 → 01

Folleto-“Teoría de la información y Codificación” 33

Quedan aun dos prefijos de longitud 2 sin utilizar, prefijos que podremos emplear en la siguiente
forma:
S 3 → 10
S 4 → 110
S 5 → 111
La pregunta de cuál de los dos códigos elaborados es mejor no puede contestarse simplemente
con los criterios vistos hasta aquí. Este ejemplo se limita a demostrar que en la construcción de
un código instantáneo, cuanto más cortas sean las primeras palabras, más largas tienen que ser
las últimas. En el primer código, por elegir un 0, todas las demás palabras deberán ser
secuencias que empiecen por 1. En el segundo código, la primera palabra es 00. En este caso
podremos elegir todas las que empiezan por 1 y las que lo hacen por 01.

6.5. INECUACIÓN DE KRAFT. DISCUSIÓN.

En el caso del alfabeto binario, la inecuación de Kraft se transforma en
b

2
i =1
−1i
 1

donde la suma se extiende a todas las palabras del código. Es interesante ver en qué forma puede
li li
utilizarse esta inecuación para determinar si las de una secuencia dada de pueden constituir
las longitudes de las palabras de un código instantáneo.
s
Tomemos una fuente de información con cuatro símbolos posibles, s1 , s2 , 3 y s 4 . En la Tabla
3-6 se exponen cinco códigos que pueden adoptarse para codificar estos símbolos en alfabeto
binario.
Tabla 3-6. Cinco códigos binarios.
Símbolos de
Código A Código B Código C Código D Código E
La fuente
s1 00 0 0 0 0

s2 01 100 10 100 10
s3
10 110 110 110 110
s4
11 111 111 11 11
Folleto-“Teoría de la información y Codificación” 34

b
Calcularemos el valor de 2
i =1
−1i
para cada uno de estos códigos.

Vemos, para el código A que

4

2 i =1
−1i
= 2 −2 + 2 −2 + 2 −2 + 2 −2 = 1

Por lo tanto, las longitudes de las palabras de A son aceptables para un código instantáneo. Hay
que resaltar, sin embargo, que la inecuación de Kraft no asegura que el código A sea un código
instantáneo. La inecuación condiciona nuevamente las longitudes de las palabras y no las
palabras mismas. En `particular, en este ejemplo, la inecuación dice que puede existir un código
binario instantáneo con cuatro palabras de longitud 2. En este caso está claro que, no sólo las
longitudes del código A son aptas, sino también que las palabras mismas constituyen un código
instantáneo.
Para el código B
4

2
i =1
−1i
= 2 −1 + 2 −3 + 2 −3 + 2 −3 = 7
8
 1

Vemos nuevamente que las longitudes de sus palabras pueden constituir un código instantáneo.
Analizándolas seguidamente, comprobamos que forman realmente un código instantáneo, ya que
ninguna palabra del código coincide con el prefijo de otra. El código C es idéntico al B ,
excepto la segunda palabra de la que se ha suprimido un binit. Calculando
4

2
i =1
−1i
= 2 −1 + 2 −2 + 2 −3 + 2 −3 = 1

vemos que las longitudes de C satisfacen la inecuación de Kraft. Se confirma, además, que
constituye un código instantáneo. El código D se deduce también del B suprimiendo bits (esta
vez de la cuarta palabra). Se comprueba que sus longitudes satisfacen la inecuación de Kraft.
Como ya hemos dicho, esto no constituye condición suficiente para que el código D sea
instantáneo, y, efectivamente, en este caso puede apreciarse que la cuarta palabra es un prefijo de
la tercera. Luego el código D no es instantáneo.
Finalmente, calculamos para el código E de la tabla 3-6 el valor de la suma
4

2
i =1
−1i
= 2 −1 + 2 −2 + 2 −3 + 2 −2 = 9
8
Folleto-“Teoría de la información y Codificación” 35

Este código no requiere más análisis. Las longitudes de sus palabras no satisfacen la inecuación
de Kraft y, en consecuencia, no puede ser un código instantáneo.

7. CODIFICACIÓN EFICIENTE

7.1. FUENTE DE INFORMACIÓN. Longitud Promedio de un Código.

A fin de lograr una decifrabilidad única, el teorema de McMillan’s nos dice que debemos
permitir palabras claves razonablemente largas. Desafortunadamente, esto tiende a reducir la
eficiencia de un código, requiriendo cadenas más largas para codificar una cantidad dada de
datos.
Por otro lado, es frecuente el caso que no todos los símbolos de origen ocurren con la misma
frecuencia dentro de un mensaje. De modo que tiene sentido asignar las palabras claves más
largas a los símbolos de origen usados con menor frecuencia, de manera que reducimos el
número promedio de símbolos códigos por símbolos de origen y mejoramos la eficiencia del
código.
Nos proponemos construir una cierta clase de esquema de codificación instantánea que sea la
más eficientemente posible entre todos los esquemas de codificación instantáneas (un esquema
de codificación es instantáneo si el código correspondiente es instantáneo). Para este fin
asumiremos que cada símbolo de origen tiene asociado una probabilidad de ocurrencia.

7.2. DEFINICIÓN DE FUENTE DE INFORMACIÓN.

Una fuente de información es un par ordenado S = ( S , P) , donde S = s1 , s2 ,..., sq   es un

si
alfabeto fuente, y “ P ” es una ley de probabilidad que asigna a cada elemento “ ” de “ S ” una
P( si )
probabilidad . La secuencia P( s1 ), ..., P( sq ) es la distribución de probabilidad para S.

A menudo estamos interesados sólo en la distribución de probabilidad de la fuente, la que


podemos escribir en la forma P = p1, p2,  pq 
Una fuente puede imaginarse como una caja negra que emite símbolos de origen, uno a la vez,
para formar un mensaje. Asumiremos que la emisión de símbolos es independiente del tiempo.
En otras palabras, el hecho de que un símbolo origen dado es emitido en un instante dado no
tiene efecto sobre que símbolo de origen será emitido en cualquier otro instante.
Folleto-“Teoría de la información y Codificación” 36

Como una medida de la eficiencia de un esquema de codificación, usaremos la longitud

promedio de un código(longitud promedio de la palabra clave), la longitud media o promedio de
un código la denotamos por “L” y está dada por:
l =
q
L =  Pili Pi s
= probabilidad de ocurrencia de cada símbolo ( i ). i longitud de las
i =1

palabras claves.

Definición: Sea S = (S, P) una fuente de información, y supongamos que (C, f ) es un esquema
S = s1 , s2 ,  sq 
de codificación para . La longitud promedio de la palabra clave de (C, f ) es:
q

 Len( f ( s )) P( s )
i =1
i i

Ejemplo:
Considere el alfabeto origen S = { a, b, c, d } con probabilidad de ocurrencia.
2 2 8 5
P( a ) = P(b) = P( c ) = P( d ) =
17 17 17 17

Considere también los siguientes esquemas de codificación.

Esquema 1 Esquema 2.
a → 11 a → 0 1010
b→0 b → 00
c → 100 c → 10
d → 1010 d → 11
Se tiene
Longitud promedio para el esquema 1 = L1
4
2 2 8 5 50
L1 =  Pili = 2  + 1  + 3  + 4( ) =
i =1 17 17 17 17 17
Longitud promedio para el esquema 2 = L2
4
2 2 8 5 40
L2 =  Pili = 5  + 2 + 2 + 2 =
i −1 17 17 17 17 17
El código del esquema 2 tiene una longitud promedio de palabra clave más pequeña. En este
sentido es más eficiente del esquema 1.
Folleto-“Teoría de la información y Codificación” 37

7.3. CODIFICACIÓN DE HUFFMAN.

En 1952, D. .A Huffman publicó un método para la construcción de esquemas de codificación
instantáneas altamente eficientes. Este método es ahora conocido como codificación de
Huffman.

Teorema. Sea S = ( S , P) una fuente de información. Entonces todos los esquemas de

codificación de Huffman para S son instantáneas. Además los esquemas de codificación de
Huffman tiene la longitud promedio de las palabras claves más pequeña entre todos los esquemas
de codificación instantáneos para S.

Si denotamos por Min Ave CodeLenr (S ) , la longitud promedio mínima de las palabras claves,
tomadas sobre todos los esquemas de codificación r – arios, unívocamente decodificable para S,

y denotamos por Ave Code Lent Huff r (S ) , la longitud promedio de las palabras claves de
cualquier esquema de codificación de Huffman r – ario, se tiene que
Ave Code Lent Huff r (S ) = Min Ave CodeLenr (S )

Ejemplo. Considere el alfabeto puente y las probabilidades mostradas.

Símbolo. Probabilidad.
a 0.35
b 0.10
c 0.19
d 0.25
1 0.06
2 0.05

El esquema de codificación de Huffman es construido, completando un árbol binario, como

sigue.

Paso 1. Coloque cada símbolo dentro de un nodo.. Etiquete cada nodo con la probabilidad
correspondiente y ordénelos en orden creciente de probabilidades.
Folleto-“Teoría de la información y Codificación” 38

Paso 2. Conecte los dos nodos más a la izquierda a un nuevo nodo. Etiquete el nuevo nodo con
la suma de las probabilidades asociadas a los nodos originales. Baje esta porción de la figura de
tal manera que el nuevo nodo esté en la hilera de arriba.

Paso 3. Repita el proceso de ordenamiento de la figura de tal manera que los nodos en el nivel
superior estén en orden creciente de probabilidades, y luego conectar los dos nodos más a la
izquierda, hasta que solo un nodo permanezca en la hilera superior.
Folleto-“Teoría de la información y Codificación” 39

Paso 4. Descarte todas las probabilidades y etiquete cada segmento de línea que se inclina hacia
arriba (desde izquierda a derecha) con un cero, y cada segmento de línea que se inclina para
abajo (de izquierda a derecha) con un uno. El resultado se denomina árbol de Huffman. Para
determinar la palabra clave asociada a cada símbolo, comience en la base y escriba la secuencia
de bits encontradas en el camino en el sentido hacia abajo.

Verifique que:
Símbolo origen Código.
a 11
b 010
c 00
d 10
1 0111
2 0110
Pruebe que este es un código instantáneo y encuentre la longitud promedio de las palabras
claves. (Resp. 2.32)
Note que un código binario (bloque) requiere palabras claves de longitud al menos 3 para
codificar 6 símbolos de origen (2 2  6  2 3 ) . Así pues la longitud promedio de la palabra clave
de un código bloque de longitud fija 3 es 3, por tanto el código de Huffman reduce la longitud
promedio de las palabras claves en un 22.7%.
Notemos que el esquema de codificación de Huffman no necesariamente es único para una
fuente S dada. Esto se debe a la ambigüedad que ocurre cuando dos nodos de la hilera superior
Folleto-“Teoría de la información y Codificación” 40

tienen la misma probabilidad. Sin embargo, todos los esquemas de codificación de Huffman para
S tienen la misma longitud promedio de palabras claves, y lo cual de acuerdo al teorema anterior,
es la más pequeña entre todos los esquemas de codificación instantánea para S.
Asignación
1. Encuentre una codificación de Huffman de la distribución de probabilidad dada, en
cada situación. Determine el ahorro sobre el más eficiente código de longitud fija:
Símbolo origen Probabilidad. Símbolo origen Probabilidad. Símbolo origen Probabilidad.
A 0.1 A 0.25 A 0.1
B 0.2 B 0.25 B 0.1
C 0.4 C 0.25 C 0.1
D 0.2 D 0.24 D 0.1
E 0.1 E 0.01  
J 0.1

2. Escriba un programa en computadora que implemente la codificación de Huffman

Folleto-“Teoría de la información y Codificación” 41

8. LA INFORMACIÓN Y SUS FUENTES. CODIFICACIÓN SIN

RUIDO.
Los resultados del tema anterior (Codificación Eficiente) muestran que los esquemas de
codificación de Huffman son los más eficientes, al tener la longitud promedio de las palabras
clave lo más pequeña, entre todos los esquemas de codificación instantáneo. Nuestro objetivo es
determinar precisamente cuán eficiente puede ser un esquema de codificación. Veremos que
para cada fuente S hay un número llamado Entropía de S que tiene la propiedad que la
longitud promedio de las palabras claves de cualquier esquema de codificación instantánea para
S debe ser más grande o igual que la entropía de S . En otras palabras la entropía provee un
límite más bajo en la longitud promedio de las palabras claves de cualquier esquema de
codificación instantánea.
La entropía de la fuente intenta medir en forma precisa la cantidad de información en la fuente.
Con el fin de ilustrar el concepto de la cantidad de información obtenida de una fuente,
imaginemos que se da una competencia. Cada uno de los competidores tienen una “caja negra”

que emite símbolos de la fuente S = s1 , s2 , y probabilidad p1 =

99 1
y p2 = . El ganador de
100 100
la competencia es el primero en nombrar ambos símbolos, que es, el primero en tener la
información completa sobre el conjunto S (asumimos que ningún competidor ha visto los
símbolos con anterioridad).
Ahora suponga que en la primera vuelta, el primer concursante obtiene el símbolo s1 de la
fuente, mientras que el segundo concursante obtiene s2 . En este punto, ¿cuál concursante está
más próximo de ganar el concurso?
Puesto que el primer concursante aún necesita recibir el símbolo de origen s2 , cuya probabilidad
1
de ocurrencia es p2 = , mientras que el segundo concursante necesita recibir s1 , cuya
100
99
probabilidad de ocurrencia es p1 = , está claro que el segundo concursante tiene más
100
probabilidad de ganar que el primero. En algún sentido entonces el segundo concursante ha
recibido más información sobre S desde el símbolo de origen s2 , con la probabilidad más
pequeña de ocurrencia, con respecto al primer concursante. Lo cual permite afirmar que una vez
Folleto-“Teoría de la información y Codificación” 42

definida la información obtenida desde un símbolo de origen esta debería tener la propiedad de
que a menor probabilidad que un símbolo de origen ocurra, más información obtenemos de la
ocurrencia de ese símbolo, y a la inversa.
Como la información obtenida de un símbolo de origen no es función del símbolo en sí mismo,
sino, más bien de su probabilidad de ocurrencia, se usará la notación I ( p) , para designar la
información obtenida desde el símbolo de origen con probabilidad de ocurrencia p , a
continuación presentamos tres afirmaciones sobre la función I ( p) definida para todo 0  p  1
• I ( p)  0
• La función I ( p) es continua en
Puesto que asumimos que los eventos si y s j (ocurridos en diferentes transmisiones) son

independientes, la información de que ambos eventos han ocurrido deberá ser la suma de I ( pi ) y

I ( p j ) . Como la probabilidad de que ambos eventos han ocurrido es el producto de sus

probabilidades pi p j se tiene que:

• I ( p1 p2 ) = I ( p1 ) + I ( p2 )

8.1. FUENTE DE INFORMACIÓN DE MEMORIA NULA.

s1 , s2 ,sq
FUENTE

(Fuente de información)
Imaginemos la fuente emitiendo una secuencia de símbolos perteneciente a un alfabeto finito y
fijo S = s1 , s2 ,, sq . Los símbolos emitidos sucesivamente se eligen de acuerdo a una ley fija

de probabilidad. Ocasionalmente nos referimos a la fuente misma como S , sin que esto deba dar
lugar a confusión. En la fuente más sencilla admitiremos que los símbolos emitidos son
estadísticamente independientes. Tal fuente de información se conoce como fuente de memoria
nula y puede escribirse completamente mediante el alfabeto fuente S y la probabilidad con que
los símbolos se presentan: p( s1 ), P( s2 )  P( sq ) .
Folleto-“Teoría de la información y Codificación” 43

8.1.1. DEFINICIÓN DE INFORMACIÓN.

Sea E un suceso que puede presentarse con probabilidad P(E ) . Cuando E tiene lugar, decimos
que hemos recibido:
1
I ( E ) = log Unidades de información.
P( E )
La elección de la base de logaritmo que interviene en la definición equivale a elegir una
determinada unidad ya que:
log b x
log a x = (*)
log b a
log b x
Demostrar que log a x =
log b a

Demostración. Sea: y = log a x  a y = x Por definición de logaritmo.

Partiendo de : log b x = log b a y Reemplazando.

log b x = y log b a Propiedad de logaritmo.

log b x = log a x log b a Reemplazando y .

log b x
log a x = Despejando log a x
log b a
En el logaritmo de base 2 la unidad de información se denomina bit:
1
I ( E ) = log 2 bit.
P( E )
En el logaritmo natural de base e la unidad de información se denomina nats:
1
I ( E ) = ln nats.
P( E )
En el logaritmo de base 10 la unidad de información se denomina Hartley:
1
I ( E ) = log10 Hartley.
P( E )
(R.V. Hartley fue el primero en sugerir una unidad logarítmica de la información en 1928).
Para el logaritmo de base r la unidad de información está dada por:
1
I ( E ) = log r unidades de orden r .
P( E )
Folleto-“Teoría de la información y Codificación” 44

Comparando el logaritmo de base10 y de base e con el de base 2 y utilizando la relación (*) se

deduce que:

1 I ( E ) = log 10 10 = 1 Hartley
Si P( E ) =  1 Hartley = 3.32 bit
10 I ( E ) = log 2 10 = 3.32 bit

1 I ( E ) = log e e = 1 nat
Si P( E ) =  1 Nat = 1.44 bit
e I ( E ) = log 2 e = 1.44 bit

Ejemplo 1:
1 1
Notemos que si P( E ) = , I ( E ) = log 2 bit. = 1 bit, es decir un bit es la cantidad de
2 P( E )
información obtenida al especificar una de dos posibles alternativas igualmente probable. Esta
situación se presenta al lanzar una moneda al aire a o al examinar la salida de un sistema de
comunicación binario.
Ejemplo 2:
¿Cuál será la cantidad de información transmitida por un sistema de comunicación,
específicamente la imagen de televisión, si está formada por una estructura de puntos negros,
blancos y grises, dispuestos en 500 filas y 600 columnas aproximadamente. Admita que cada
uno de esos (500 )(600 ) = 300000 puntos puede adoptar uno de los diez niveles de brillo

diferentes, de manera que puede haber 10 300000 imágenes distintas de TV. Si todas son
1
igualmente probables, la probabilidad de una imagen cualquiera es igual a P( E ) = 300000
y la
10
cantidad de información que contiene es:
1 1
I ( E ) = log 2 = log 2 = log 2 10 300000
P( E ) 1
10 300000
I ( E ) = 300000 log 2 10 = (300000 )( 3.321928 ) = 996578 .4 bit  1x10 6 bits
Ejemplo 3:
Comparemos la información obtenida en una imagen de televisión, calculada en el ejemplo
anterior, con la información contenida en 1000 palabras emitidas por un locutor de radio.
Supongamos que el locutor tiene un vocabulario de 10000 palabras y que ha elegido entre ellas
Folleto-“Teoría de la información y Codificación” 45

1000 completamente al azar. La probabilidad de una secuencia de 1000 palabras es

1
P( E ) = , y la cantidad de información contenida es:
10000 1000
1 1
I ( E ) = log 2 = log 2= log 2 10000 1000 = 1000 log 2 10000 = 13287 .712 bits  1.3x10 4 bits
P( E )1
10000 1000
Así pues la imagen de TV equivale a 100 veces la información contenida en 1000 palabras
emitidas por un locutor de radio.
RESUELVA:
La imagen mostrada por un monitor de PC está compuesta por píxeles en una resolución de 1024
columnas por 768 filas. Sabiendo que cada píxel puede tomar cualquiera de los 256 colores
igualmente probables, ¿Cuál es la cantidad de información obtenida en una imagen de esa PC?
Resp: 6291456 bits.

8.1.2. Cálculo de la Entropía .

Puede calcularse la información media suministrada por una fuente de memoria nula en la forma
siguiente:
La presencia de un símbolo " si " corresponde a una cantidad de información igual a:

1
I ( si ) = log 2 bits (Recuerde que bit es la contracción de unidad binaria).
P ( si )

I ( si ) puede interpretarse como la información necesaria para que la presencia de " si " sea cierta.

La probabilidad de que aparezca es precisamente P( si ) de modo que la cantidad media de

q
información por símbolo de la fuente es  P( s ) I ( s )
i =1
i i bits .

Esta magnitud, cantidad media de información por símbolo de la fuente, recibe el nombre de
Entropía H (S ) de la fuente de memoria nula.
q
H ( S ) =  P( si ) I ( si ) bits
i =1

H (S ) es la entropía de una fuente S , define el valor mínimo del número medio de símbolos
necesarios para codificar cada símbolo de la fuente o el valor medio de incertidumbre de un
observador antes de conocer la salida de la fuente.
Ejemplo: 4
Folleto-“Teoría de la información y Codificación” 46

Considere la fuente S = s1 , s 2 , s3 . con p( s1 ) = , P( s2 ) = P( s3 ) = , Entonces:

1 1
2 4
1
q
1 1 1 1 1 1 1 1 3
H ( S ) =  P( si ) I ( si ) bits = log 2 1 + log 2 1 + log 2 1 = log 2 2 + 2  log 2 4 = + 1 = bits
i =1 2 2 4 4 4 4 2 4 2 2

Si medimos I ( si ) en unidades de orden r H (S ) está dado por:

q
1
H r ( S ) =  P( si ) log r unidades de orden r
i =1 P ( si )

1
q
log 2
P ( si )
De (*) se deduce: H r ( S ) =  P( si )
H (S ) H (S )
=  H r (S ) =
i =1 log 2 r log 2 r log 2 r

8.2. PROPIEDADES DE ENTROPÍA.

Con el objeto de deducir algunas propiedades de la entropía consideraremos una propiedad
particular del logaritmo. La figura que se muestra representa la curva de variación del logaritmo
natural de x y de la recta de ecuación y = x − 1

La curva y = ln x se mantiene siempre por debajo de la recta, por tanto podemos escribir la

inecuación: ln x  x − 1 se verifica la igualdad para x = 1 .

ln x  x − 1 (**)
− ln x  1 − x Multiplicando por –1
Folleto-“Teoría de la información y Codificación” 47

ln x −1  1 − x Propiedad de los logaritmos

1
ln  1− x
x (* * *) Propiedad del exponente negativo.

Deduciremos finalmente una última inecuación a partir de (**)

Sean x1 , x2 , xq y y1 , y2 , yq dos conjuntos de probabilidades, es decir xi  0 y y j  0 i, j
q q
Y  xi =  y j = 1 .
i =1 j =1

Haciendo uso de (*) q

se tiene:  xi log 2
yi q
=  xi
ln xyii
=
1 q

y
xi ln i
i =1 xi i =1 ln 2 ln 2 i =1 xi

Aplicando (**) a cada término de la suma en el miembro de la derecha de

q
yi 1 q y
 x log
i =1
i 2 = 
xi ln 2 i =1
xi ln i
xi se tiene:
q
yi 1 q  yi 
 xi log 2   xi  − 1
xi ln 2 i =1  xi
i =1 

q
yi 1 q q

 x log i 2   
xi ln 2  i =1
y i −  xi 
i =1 i =1 
q q
Como  xi =  x j = 1
i =1 j =1

q
yi
 x log
i =1
i 2
xi
 0 (* * **)

q q q
=  xi log 2 yi − log 2 xi  =  xi log 2 yi − xi log 2 xi 
yi
 xi log 2
i =1 xi i =1 i =1

 
q q q q
yi 1 1
 xi log 2
i =1 xi
=  − xi log 2 yi + xi log 2 xi = − xi log 2 +  xi log 2
−1 −1

yi i =1 xi
i =1 i =1

q q
yi 1 q
por (* * * *)
1
 xi log 2
i =1 xi
=  xi log 2 −  xi log 2  0
xi i =1 yi
i =1
Folleto-“Teoría de la información y Codificación” 48

q q
1 1
Por consiguiente  xi log 2   xi log 2 la igualdad se cumple cuando xi = yi
i =1 xi i =1 yi
A continuación, se analiza en que modo la entropía depende de la probabilidad de los diferentes
símbolos de la fuente. En particular, sería interesante conocer cuanta información puede
suministrar una fuente de información de memoria nula.
Supongamos que una fuente de memoria nula, definida por un alfabeto S = s1 , s2 ,, sq  y sus

probabilidades p(s1 ), P(s2 )  P(sq ) . La entropía H (S ) viene dada por:

q
1
H (S ) =  P(si ) log 2
i =1 p(si )
q q
1
Consideremos la expresión log 2 q − H ( S ) = log 2 q P( si ) −  P( si ) log 2
i =1 i =1 p(si )
q q
1
log 2 q − H ( S ) =  P( si ) log 2 q −  P(si ) log 2
i =1 i =1 p(si )
q
 1 
log 2 q − H ( S ) =  P( si ) log 2 q − log 2 
i =1  P ( si ) 

q  q 
log 2 q − H ( S ) =  P( si ) log 2 1 
i =1  P ( si ) 

q
log 2 q − H ( S ) =  P( si )log 2 qP( si )
i =1

q
log 2 q − H ( S ) =  P( si )
ln qP(si ) Por (*)
i =1 ln 2

1 q 
log 2 q − H ( S ) =  
ln 2  i =1
P( si ) ln qP( si )


1 q 1 
log 2 q − H ( S ) =  P( si ) ln 1 
ln 2  i =1 qP( si ) 


1 q  1 
log 2 q − H ( S )   P( si ) 1 −  Por (* * *)
ln 2  i =1  qP( si )  

1 q 1 q  P ( si )  
log 2 q − H (S )   P ( s i ) −  
ln 2  i =1 q i =1  P( si )  
Folleto-“Teoría de la información y Codificación” 49

1 q 1  P( s ) P( s 2 ) P( sq )  
log 2 q − H ( S )    P ( si ) −  1 + ++ 
ln 2  i =1 q  P( s1 ) P( s2 ) P( sq )  

1 q 1 
log 2 q − H ( S )    P ( si ) − q  =
1
1 − 1
ln 2  i =1 q  ln 2

log 2 q − H ( S )  0 (* * * * *)
Así pues H (S ) es siempre menor o igual que log q y la igualdad (* * * * *) se cumple cuando
1
P( si ) = i = 1,2,3,q .Es decir, hemos demostrado que en una fuente de información de
q

memoria nula con un alfabeto de q símbolos, el valor máximo de la entropía es precisamente

log q , alcanzándose solamente si todos los símbolos de la fuente son equiprobables.

Ejemplo 4: Considere una fuente binaria de memoria nula en tal fuente el alfabeto S = 0,1. La

probabilidad de un cero es w y la de un 1 es 1 − w , el cual denotaremos por w = 1 − w .

Calculando la entropía H (S ) y construya el gráfico.
q
1
H ( S ) =  P( si ) log 2 bits
i =1 P ( si )
1 1
H ( S ) = P( s1 ) log 2 + P( s2 ) log 2
P( s1 ) P( s2 )

1 1
H ( S ) = w log 2 + (1 − w) log 2
w 1− w
1 1
H ( S ) = w log 2 + w log 2 bits
w w
La función H (S ) se acostumbra a representar por un símbolo especial H (w) . Por definición:
1 1
H (w) = w log 2 + w log 2 bits que llamaremos función de entropía. La diferencia entre H (S )
w w

y H (w) es que H (S ) determina la entropía de una fuente particular S , mientras que H (w) es
una función de la variable w definida en el intervalo 0,1 .

Es importante saber que el límite lim w log w = 0 Así por definición 0 log 0 = 0
w→ 0

Seguidamente se presenta la curva de variación de H (w) en función de w en el intervalo 0,1 de

la variable w .
Folleto-“Teoría de la información y Codificación” 50

H(w)

Cantidad de Información

Probabilidad

1 9 1 Ln10 9 Ln 109
H (0.1) = H ( 101 ) = log 2 10 + log 2 109 = + = 0.332192809 + 0.136802754 = 0.468997593  0.47
10 10 10 Ln2 10 Ln2
2 10 8 2 Ln 102 8 Ln 108
H (0.2) = H ( 102 ) = log 2 + log 2 108 = + = 0.464385619 + 0.257542475 = 0.721928094  0.72
10 2 10 10 Ln2 10 Ln2
1 1 1 1
H (0.5) = H ( 12 ) = log 2 2 + log 2 2 = + = 1
2 2 2 2 bit
En el gráfico de la función de entropía H(w), se puede notar que:
Si la salida de la fuente binaria es cierta (bien w=0 ó w=1) la fuente no suministra ninguna
información.
El valor medio de la información aportada por un símbolo de la fuente binaria alcanza su
1 1
máximo valor en el caso de que 0 y 1 sean igualmente probables P(0) = , P(1) = , siendo el
2 2
valor máximo igual a log 2 q = log 2 2 = 1bit q=2
La salida de una fuente binaria está constituida por dígitos binarios o binits. Así una secuencia de
binits producidos por una fuente de información de memoria nula, de 0s y 1s equiprobables,
suministra un bit de información por dígito binario.
Si 0s y 1s no son igualmente probables, la cantidad de información dada por un binit(dígito
binario) será menor o mayor de 1 bit dependiendo de los valores de las probabilidades (Por
1
I ( E ) = log 2 ).
P( E )
Folleto-“Teoría de la información y Codificación” 51

La cantidad media de información suministrada por un dígito binario de tal fuente, sin embargo,
será siempre menor e igual a 1 bit por dígito binario.
Hay que notar que la cantidad máxima de información dada por una fuente de memoria nula de q
símbolos, crece lentamente al aumentar q. De hecho, la cantidad máxima de información crece
con el logaritmo del número de símbolos de la fuente, de modo que para duplicar la cantidad
máxima de información por símbolos en una fuente de q símbolos, sería necesaria una fuente de
q 2 símbolos.

Cantidad Máxima = log 2 q

2 log 2 q = log 2 q 2

8.3. PROPIEDADES DE ENTROPÍA DE FUENTE DE MEMORIA NULA

A continuación resumimos las propiedades de Entropía de una fuente de memoria nula definida
en un alfabeto S (variable aleatoria discreta) que toma valores S = s1 , s2 , , sq , con
q
probabilidades P( si )  0 i siendo  p(s ) = 1 . Denotando por H (S ) la Entropía de la fuente
i =1
i

S , se tiene que:
q q
1
H ( S ) =  P( si ) log 2 = −  p( si ) log 2 p( si )
i =1 P( si ) i =1

PROPIEDAD 1
La Entropía es no negativa y se anula sí y sólo sí la variable aleatoria en estudio posee un
resultado de probabilidad 1 y los restantes de probabilidad cero.
q
H ( S ) = −  p( s i ) log 2 p( s i )
i =1

Para los valores de 0  P( si )  1 , sus logaritmos son siempre negativos o nulos; es decir

log 2 p( si )  0
, entonces
− log 2 p( s i )  0
y el valor medio de cantidades positivas es también positivo.
P( s k ) = 1, P( s i ) = 0  i  k
Si , los sumandos que aparecen son del tipo 0 log 0, − 1 log 1 , todos

ellos nulos, luego H ( S ) = 0 .

Folleto-“Teoría de la información y Codificación” 52

q
Recíprocamente si −  p( si ) log 2 p( si ) = 0 , todos los sumandos (por ser no negativos ) deben
i =1

ser nulos, con lo cual, sólo puede tomar la forma 0 log 0, ó − 1 log 1 y solamente uno de ellos
q
puede tener probabilidad igual a la unidad para que se cumpla que  p( s ) = 1 .
i =1
i

PROPIEDAD 2
La Entropía es idéntica en dos variables si estas se diferencian en un resultado de probabilidad
nula.
H ( P( s1 ),  P( sq )) = H ( P( s1 ), , P( sq ), 0)
En efecto , pues ambas expresiones solo se

diferencian en el término 0 log 0 . En términos intuitivos diremos que la incertidumbre se

conserva al introducir en la experiencia un resultado que no puede ocurrir.
PROPIEDAD 3
Si todos los resultados son equiprobables, la Entropía coincide con la medida de incertidumbre
de Hartley (Para una experiencia de q resultados posibles Hartley propuso en 1928 la expresión
log q como medida de incertidumbre asociada.

1
En efecto si P( s1 ) = P( s2 ) =  p( sq ) = , resulta que:
q
q
1 1 1
H ( 1q ,, 1q ) =  log = − log = log q . De este modo, la Entropía se convierte en una
i =1 q q q
extensión de la medida de incertidumbre de Hartley.

PROPIEDAD 4
Conservando la equiprobabilidad de los resultados, la Entropía aumenta con el número de éstos.
Es inmediato por ser log q  log (q + 1)

PROPIEDAD 5
La Entropía de una variable que toma q valores es máxima cuando estos son equiprobables.
H ( P( s1 ) p( s2 ), P( sq ))  H ( 1q , 1q ,, 1q ) = log q ( Ya fue demostrada en clases)
Folleto-“Teoría de la información y Codificación” 53

9. PROBLEMA FUNDAMENTAL DE LA CODIFICACIÓN DE

FUENTES DE INFORMACIÓN

9.1. LONGITUD MEDIA DE UN CÓDIGO.

Se han estudiado los procedimientos para construir códigos instantáneos que asocien los
símbolos de un alfabeto fuente con palabras formadas por símbolos de un alfabeto código
cualquiera. Para un alfabeto fuente y un alfabeto código dado, es posible sin embargo, elaborar
más de un código instantáneo o unívocamente decodificable. Esta abundancia de códigos
válidos obliga a adoptar un criterio que permita elegir uno de entre ellos. Un criterio natural de
selección, aún cuando no el único posible, podría ser el de su longitud.
Desde el punto de vista de la mera economía de expresión y la consecuente economía en el
equipo de comunicación, sin tener en cuenta otras consideraciones, es preferible un código
formado por muchas palabras cortas a uno con palabras de gran longitud. Definiremos, por
tanto, la longitud media de un código.
s1 , s2 , ..., sq
DEFINICIÓN. Sea un código que asocia los símbolos de una fuente con las palabras
X 1, X 2, . . ., X q
. Supongamos que las probabilidades de los símbolos de la fuente son
P1 , P2 , . .., Pq l1 , l2 , . .., lq
y las longitudes de las palabras . Definimos la longitud media del
código, denotada por L , por la ecuación
q
L =  pi li (1)
i =1

Será interesante encontrar códigos unívocos de longitud media mínima.

DEFINICIÓN. Consideremos un código unívoco que asocia los símbolos de una fuente S con
palabras claves formadas por símbolos de un alfabeto r-ario. Este código será compacto
(respecto a S ) si su longitud media es igual o menor que la longitud media de todos los códigos
unívocos que pueden aplicarse a la misma fuente y el mismo alfabeto.
Una vez enunciada estas dos definiciones, puede formularse el problema fundamental de la
codificación de fuentes de información como aquel de la búsqueda de códigos compactos. Hay
que destacar que ambas definiciones se refieren exclusivamente a las longitudes de las palabras
de los códigos, y no a las palabras mismas. Por esta razón, puede reducirse la búsqueda a los
códigos pertenecientes a la clase de códigos instantáneos. La inecuación de McMillan garantiza
Folleto-“Teoría de la información y Codificación” 54

que cualquier conjunto de longitudes de palabras claves válido para un código unívoco, lo es
también para un código instantáneo.
La definición de L es válida tanto para las fuentes de memoria nula como de Markov. Con
objeto de simplificar la discusión, limitaremos por el momento las consideraciones a las fuentes
de memoria nula.
Consideremos una fuente de memoria nula, cuyos símbolos, s1 , s2 ,..., sq tienen respectivamente

las probabilidades de los símbolos de la fuente son P1 , P2 , ..., Pq . Supongamos un código que

l
codifica estos símbolos en un alfabeto de r símbolos, y definimos por i la longitud de la
si
palabra correspondiente a . La entropía de esa fuente de memoria nula será, entonces
q
H (S ) =  pi log
1
i =1 pi
q
sean Q1 , Q2 , ...Qq números tales que QI  0 para cualquier valor de i y Q
i =1
i = 1 . Debido a

una desigualdad probada cuando se estudiaron las propiedades de la entropía, sabemos que:
q q
1 1
 pi log
i =1
  pi log
pi i =1 Qi , se cumple la igualdad cuando Pi = Qi . Por lo tanto
q
H (S )  −  pi log Qi (2)
i =1

Qi
Esta inecuación será válida para cualquier conjunto de números positivos, , cuya suma sea la
− li
unidad. En consecuencia se podrá elegir Qi = qr (3)
r j
−l

j =1

 
 −l 
 r i 
q
De donde H ( S )  − pi log q 
  r j
i =1 −l

 j =1 

 −l 
( )
q q
 −  Pi  log r −li − log  r j 
i =1  j =1 
 −l 
( )
q q q
 −  Pi log r − li +  pi  log  r j 
i =1 i =1  j =1 
Folleto-“Teoría de la información y Codificación” 55

q q
  Pi li log r + log  r
−l j

i =1 j =1

q q
 log r  Pi li + log  r
−l j

i =1 j =1

q
H ( S )  L log r + log  r
−l j
(4)
j =1

Si exigimos que el código sea instantáneo, la inecuación de Kraft impone que el argumento del
segundo logaritmo del segundo miembro de (4) sea igual o menor que la unidad. Por lo tanto, su
logaritmo deberá ser igual o menor que cero, y
H ( S )  L log r , o bien H (S )
L (5)
log r
H (S ) viene medida en bits en la ecuación (5). Recordemos que L es el número medio de

símbolo utilizado para codificar S . Expresando la entropía asimismo en unidades r-arias, como
H (S )
se encontró en clases anteriores que H r ( S ) = , entonces podemos escribir la relación (5)
log r
en la forma siguiente: H r (S )  L
Resumiendo puede decirse que, con un código instantáneo y una fuente de memoria nula, L
debe ser igual o mayor que H r (s) . Además L alcanzará su valor mínimo si, y solamente si,

 1
pueden elegirse las longitudes de las palabras, li , iguales a log r   , donde ésta, li , sea un
 pi 
número entero para cualquier valor de i .
Folleto-“Teoría de la información y Codificación” 56

BIBLIOGRAFÍA
[ABNO1977] ABRAMSON, NORMAN TEORÍA DE LA INFORMACIÓN Y
CODIFICACIÓN. Cuarta edición. Editorial PARANINFO, Madrid
1977.

[ROST1996] ROMAN, STEVEN. INTRODUCTION TO CODING AND

INFORMATION THEORY. Springer - Verlag. 1996..
[] Enciclopedia de Informática y Computación. Tomo: Deontología
Informática.