Teoría de la información

y codificación
INTRODUCCIÓN A LA TEORÍA DE LA INFORMACIÓN
Comunicación
Mensaje digital: secuencia de elementos de un alfabeto.
◦ Alfabeto: conjunto numerable y finito de símbolos
◦ Longitud del mensaje: número de elementos que forman el mensaje
◦ Alfabeto binario, ASCII, Unicode
◦ Bit: Unidad de medida de cantidad de información, equivalente a la elección entre dos posibilidades
igualmente probables.
Comunicación
Canal punto a punto: medio físico apto para la transmisión de mensajes desde un punto (origen)
a otro punto (destino)
◦ Canal digital o discreto: solo se pueden enviar mensajes digitales de un determinado alfabeto.
◦ Régimen de transmisión del canal: referido a la velocidad de transmisión o el inverso del tiempo
necesario para enviar un símbolo del alfabeto.
◦ Tiempo de propagación del mensaje: tiempo necesario para que un símbolo atraviese el canal.
◦ Idealmente el mensaje que sale del canal debería ser siempre idéntico al que ha entrado.

Otros tipos de canales: broadcast.

Objetivo: conseguir un canal de comunicación
perfecto sobre un canal real
Canal sin ruido (utopía)
Mensaje Mensaje

Canal ruidoso 𝑆 𝑆መ
◦ Medios guiados y no guiados Codificador Decodificador

◦ Fuentes de ruido:
◦ Línea de teléfono t r
Canal ruidoso
◦ Comunicación tierra sonda espacial
◦ Reproducción de una célula
◦ Línea de fibra óptica submarina
◦ Disco duro mecánico
Objetivo: conseguir un canal de comunicación
perfecto sobre un canal real
Problema: si se transmite una cadena de bits sobre el canal, existe la posibilidad de que el
mensaje recibido no sea idéntico al transmitido.
Es preferible tener un canal de comunicación en que esta probabilidad de error sea cero o tan
próxima a cero que sea despreciable.
Canal simétrico binario: modelo donde la probabilidad de transmitir un bit de forma correcta
sea (1-f) y la probabilidad de transmisión de forma incorrecta sea f
◦ 𝑃 𝑦 = 0 𝑥 = 0 = 1 − 𝑓; 𝑃 𝑦 = 0 𝑥 = 1 = 𝑓;

◦ 𝑃 𝑦 = 1 𝑥 = 0 = 𝑓; 𝑃 𝑦 =1 𝑥 =1 =1−𝑓
Objetivo: conseguir un canal de comunicación
perfecto sobre un canal real
Si f=0.1 uno de cada 10 bits va a estar alterado. Un disco duro no debería alterar ningún bit a lo
largo de toda su vida útil. Si esperamos leer y escribir un gigabyte al día durante 10 años hará
falta que f < 10-15.
◦ Solución física: mejorar las características físicas del canal de comunicación para reducir la probabilidad
de error.
◦ Solución del sistema: añadir sistemas que permitan detectar y corregir los errores introducidos por el
canal.
Comunicación sobre canal ruidoso
Dividir el codificador
◦ Codificador de la fuente: consiga representar los mensajes de la fuente con el menor número posible de
símbolos de un cierto alfabeto de codificación.
◦ Codificador del canal: permita la consecución de una transmisión fiable sobre un canal ruidoso con un
coste mínimo.

Transformación de la señal digital, modulación de la señal para convertirla en un valor

transmitible por el medio.
Códigos de detección de errores, añaden cierta redundancia en la señal a transmitir.
Mensaje Mensaje

𝑆 𝑆መ

Codificador Decodificador

t r
Canal ruidoso
Códigos de repetición
Códigos de repetición Secuencia origen 𝑆 Secuencia transmitida 𝑡
0 000
1 111

Algoritmo de votación mayoritaria: consiste en dar como válido el valor que tengan la mayoría
de valores de salida para el canal simétrico binario.

Secuencia recibida r Secuencia

decodificada 𝑆መ
000 0
001 0
010 0
100 0
101 1
110 1
011 1
111 1
Códigos de rèpetición
La probabilidad de un error está determinada por la probabilidad de que dos bits en un bloque
de 3 cambien de valor, que por tanto depende de 𝑓 2 . En el caso de un canal simétrico binario
con f=0.1, el código 𝑅3 tiene una probabilidad de error después de decodificarlo de 𝑝𝑏 ≅ 0.03
por bit.
El precio que hay que pagar por esta reducción de errores es que la tasa de transmisión ha
quedado dividida por 3.
En general para poder reducir la frecuencia de los errores, será a costa de reducir la tasa de
transmisión efectiva.
Códigos de Hamming(7,4)
Códigos de bloque, es una regla para convertir una secuencia de bits fuente s de longitud K en
una secuencia transmitida t de longitud N. Para añadir redundancia se hace N mayor que K.
Los N-K bits extra son una función lineal de los K bits originales, que son los bits de
chequeo de paridad.
El código de Hamming (7,4), transmite 7 bits a partir de un bloque de 4 bits. Usa paridad par.

t5 1

s1 s2 1 0
s3 0

t7 s4 t6 1 0 0
Códigos de Hamming(7,4)
s4s3s2s1 t7t6t5t4t3t2t1
0000 0000000
0001 1010001
0010 0110010
0011 1100011
0100 1110100
0101 0100101
0110 1000110
0111 0010111
1000 1101000
1001 0111001
1010 1011010
1011 0001011
1100 0011100
1101 1001101
1110 0101110
1111 1111111
Códigos de Hamming(7,4)
Dado que el código de Hamming es un código lineal, se puede escribir en forma de
operaciones matriciales.
𝑡 = 𝐺𝑇𝑠
Donde G es la matriz generadora del código y la operación de codificación será la
suma binaria o XOR:
1011
0111
1110
𝐺𝑇 = 0 0 0 1
0010
0100
1000
Códigos de Hamming(7,4)
1011
0111
1110
𝐺 𝑇 = 0 0 0 1 y 𝑠 = [0001]
0010
0100
1000
1011
0111
1
1110
𝑇 0
𝑡 =𝐺 𝑠 = 0001 = 1010001
0
0010
0
0100
1000
Códigos de Hamming(7,4)
Decodificación por síndrome. Como ejemplo vamos a asumir que la transmisión fue t=1010001 y
que el ruido cambia de estado el segundo bit, de forma que el vector recibido es 𝒓 =
1010001 ۩ 0000010 = 1010011.
Escribiremos el vector recibido en tres círculos y miraremos en los tres círculos a ver si la paridad
sigue siendo par.

S0
r5 1

r1 r2 1 1*
r3 0
S2
S1
r7 r4 r6 1 0 0
Códigos de Hamming(7,4)
Los círculos cuya paridad no es par se muestran con línea punteada.
La tarea de decodificación es encontrar el menor número de bits cambiados que pueden
generar esa violación de las reglas de paridad.
Al patrón de violación de las reglas de paridad se le denomina síndrome, y se puede escribir
como un vector binario.
En el ejemplo, el síndrome es 𝒛 = (𝑆2 , 𝑆1 , 𝑆0 ) → z = (0, 1, 1) porque el tercer círculo tiene la
paridad correcta y los dos primeros no.
Códigos de Hamming(7,4)
La pregunta que hay que hacerse es si es posible cambiar detectar el bit que está generando
este patrón de síndrome.
Síndrome z 000 100 010 110 001 101 011 111
Bit modificado Ninguno r7 r6 r4 r5 r1 r2 r3
En este caso cambiando r2 desaparece el síndrome, por lo tanto es el bit que se considera como
modificado durante la transmisión.
Hay 7 tipos diferentes de síndromes uno por cada bit que se puede cambiar durante la
transmisión.
Si cambia más de un bit, no será posible detectar el error.
Códigos de Hamming(7,4)
Propiedades del código de Hamming
◦ Cada uno de los posibles vectores recibidos de 7 bits tiene o una codificación posible o está a un bit de
esa codificación.
◦ Dado que hay tres restricciones de paridad cada una de las cuales puede o no ser violada, aparecen
2x2x2=8 distintos síndromes.
◦ 7 síndromes distintos de cero, uno para cada uno de los patrones de error y el síndrome de todo cero
que corresponde al caso en que no hay error.
◦ El decodificador usará su mapa de síndromes distintos de cero para saber que bit cambiar en caso de
que haya un solo bit erróneo.
Códigos de Hamming(7,4)
Propiedades del código de Hamming
◦ Habrá un error de decodificación en el caso en que los 4 bits decodificados 𝑠Ƹ1 𝑠Ƹ2 𝑠Ƹ3 𝑠Ƹ4 no coincidan con
los bits originales 𝑠1 𝑠2 𝑠3 𝑠4 .
◦ La probabilidad de error de bloque 𝑃𝐵 es la probabilidad de que uno o más bits de los bits decodificados
en un bloque falle y no corresponda con su bit original.
𝑃𝐵 = 𝑃(𝑠Ƹ ≠ 𝑠)
◦ La probabilidad de error de bit 𝑝𝐵 es la probabilidad media de que el bit decodificado no coincida con
su bit original
𝐾
1
𝑝𝐵 = ෍ 𝑃(𝑠Ƹ𝑘 ≠ 𝑠𝑘 )
𝐾
𝑘=1
Códigos de Hamming(7,4)
Para cualquier canal, existe un sistema de codificación que permite la comunicación con un error
de probabilidad 𝑝𝐵 arbitrariamente pequeño a tasas de comunicación distintas de cero.
Capacidad máxima del canal es la tasa máxima a la cual la comunicación es posible en estas
circunstancias.
La fórmula para la capacidad de un canal binario simétrico con un nivel de ruido f es:
1 1
𝐶 𝑓 = 1 − 𝐻2 𝑓 = 1 − 𝑓𝑙𝑜𝑔2 𝑓 + (1 − 𝑓)𝑙𝑜𝑔2 1−𝑓

Para un canal con nivel de ruido f=0.1 su capacidad C≈0.53.

En el caso de los códigos de Hamming se consigue un R=4/7 para una 𝑝𝐵 =0.09.