Clase 2

Códigos unívocamente
decodificables
Supongamos que tenemos el siguiente alfabeto
S ={0,1}
Y una fuente de memora nula con M= 3 símbolos
T ={a ,b , c}
decodificables
Una posible combinación que podemos obtener
sería la siguiente:
S ={0,10,11}
Este código es U.D porque cualquier codificación
que se realice no presenta ambigüedades.
decodificables
Este código no es unívocamente decodificable porque la

secuencia 10011 puede ser decodificada como BAAB o
CABB o CAD
Códigos instantáneos (prefijo)
Los códigos prefijo son aquellos que dentro de cualquier
codificación, ninguno empieza con el valor de otro código
S =[3 , 11,22] Código prefijo
S =[1 ,12,33 ] Código no prefijo
Podemos saber instantáneamente su decodificación!!!

S =[1 , 2,33,34,50,61]
1611333425012 Analicemos esta secuencia

Ejercicio
C (a) =0 C (a) =101

C (b) =10 C (b) =00
C (c )=110 C (c )=0001
C (d )=111 C (d)=1
011001111010 1101000001001
Cual es prefijo?, por qué?

0 1
0
a 1
b 1
0
c
d
Longitud media de código
La longitud media de código se mide de la
siguiente manera:
Y nos relaciona el “promedio ” de digitos binarios

utilizados para codificar una secuencia de
símbolos
Longitud media de código
Si tenemos la probabilidad de cada símbolo y la
longitud de cada codificación podemos obtener la
longitud media de la siguiente manera:
Inecuación de Kraft
Definamos la eficiencia de una codificación como :
La idea es lograr decodificar sin perder información, esto requiere que

se tenga la longitud de código adecuada, luego la condición para que
un código sea unívocamente decodificables es:
Ejercicio
Evaluar la eficiencia de cada código,

que código es unívocamente
decodificable?
SOLUCION
Símbolos con alta probabilidad deben codificarse con
palabras mas cortas mientras que los símbolos con baja
probabilidad de ocurrencia deben codificarse con palabras
mas largas
La Longitud media de código no debería superar el valor

de la entropía, la idea es que esa longitud media de código
se acerque lo mas posible al valor de la entropía de la
fuente.
Teorema de Shannon
Sirve para escoger la longitud de cada símbolo codíficado,

esta desigualdad nos lleva a la siguiente expresión respecto a
la entropía.
Teorema de Shannon
Si la fuente agrupa los símbolos en n bloques, la entropía
sería nH(x) y por lo tanto la desigualdad se convierte en
Dividiendo por n tenemos:
Si n es muy grande , la longitud media de código tenderá

al valor de la entropía.
Teorema de Shannon
Completar el cuadro utilizando el teorema de shannon , hallar la entropía y

longitud media de código para cada codificación
Codificación de Shannon-Fano
La longitud de la codificación crece a medida que la
probabilidad del símbolo decrece.
Asegura que sea unívocamente decodificable.
Se aplica la técnica de divide y vencerás!!
Se divide la suma de probabilidades en valores similares.

Se agrega un cero en cada casilla y de ahí para abajo se
agregan unos
Se repite la tarea hasta que se termine de codificar

Calcular entropía y eficiencia

Hallar la codificación de Shannon-
Fano para esta secuencia de
símbolos
Hallar H(x) y eficiencia.
Calcular entropía , longitud media de

codigo y eficiencia
Codigos compactos binarios
● Conformar las fuentes reducidas hasta que solo queden
dos símbolos
● Asignar 0 y 1 a cada uno
● Los numeros que conformaron la suma anterior deben ir

acompañados por su respectivo valor de acuerdo al
generado por la última fuente reducida y codificados por
otro 0 y otro 1.
● Repetir el paso anterior hasta llegar a la primera fuente

reducida.
Ejercicio

codigo y eficiencia
Tarea
Esta es la
codificación de
shannon Fano,
hallarla por medio
de codigos
compactos binarios

codigo y eficiencia
Codigos compactos r-arios
Los códigos compactos binarios combinan 2 valores de
probabilidad, es decir la fuente se va reduciendo de a un símbolo.
Los códigos r-arios combinan r valores y por lo tanto la fuente se

va reduciendo de a (r-1) símbolos.
La idea es que la fuente reducida sea de r valores
Esto no siempre va a pasar, por lo tanto hay que agregar desde el

inicio valores falsos que compensen esta falta. La probabilidad de
estos valores falsos debe ser cero.
De acuerdo a esto la fuente original debe estar compuesta por
r+a(r-1) símbolos con a= valor entero

Codigos compactos r-arios
Se trabajan de manera similar a los binarios, la gran diferencia está en la suma
que se debe realizar para conformar las fuentes reducidas
Eficiencia y redundancia
Eficiencia
Redundancia= 1- eficiencia
Canal de información
Entropía a prori y a posteriori
Supongamos que sabemos la probabilidad de haber
enviado un 0 dado que se recibió un 0, pero que pasa
cuando no sabemos exactamente que símbolo enviamos
y sólo sabemos el simbolo que recibimos?, cual es la
probabilidad de NO HABERSE equivocado?, o cuando
solo sabemos que símbolo enviamos pero no estamos
seguros de que simbolo vamos a recibir, cuál es la
probabilidad de que no nos VAMOS a equivocar?
Calcular p(b=0), p(b=1) y probabilidades a posteriori y entropías a

posteriori
Canal sin ruido
Un canal sin ruido es aquel que tiene SOLO UN elemento
diferente de cero en cada columna de su matriz de
probabilidades.
[
1/2 1/ 2 0
P= 0
0
0 0 0
0 3 /5 3 / 10 1 /10 0
0 0 0 0 1 ]
Canal sin ruido
Canal Determinante
Un canal sin ruido es aquel que tiene SOLO UN elemento
diferente de cero en cada fila de su matriz de
probabilidades.
[ ]
1 0 0
1 0 0
P= 0 1 0
0 1 0
0 1 0
0 0 1
Canal Determinante
Información mutua
Información mutua
Información mutua
I ( A ; B)=H ( A )−H ( A I B)
I ( A ; B)=H (B)−H ( B I A )
I ( A ; B)=I (B ; A)
Canales en serie
H ( A I C)≥H ( A I B)
I ( A ; B)≥I ( A ;C )
Canales en serie
P(BIA)=
P(CIB)=
Hallar P(CIA)
Canales en serie
Canales en serie
Obtener I(X;Y) ,I(X;Z)

Canales reducidos
Canales reducidos
Canales reducidos
Canales reducidos
Capacidad de Canal
La información mutua puede ser escrita de la siguiente
manera:
Supongamos que tenemos un canal binario simétrico cuya

cantidad de información es la siguiente:
H(p) es la función herradura, w y p son las probabilidades respectivas

para cada entrada.
Capacidad de Canal
Capacidad de Canal
La capacidad de Canal es la máxima cantidad de información transferida a medida
que se van variando las distribuciones de entrada (probabilidades)
Si se tiene una fuente cin una tasa de s simbolos/segundo, entonces la capacidad

de canal esta dada por:
Capacidad de Canal
Por otro lado podemos definir la capacida de canal como:
S
C=BLog2 (1+ )
N
B= Ancho de Banda
S/N= La relación señal a ruido
Limite de Nyquist
f b≤2 B
Detecciones de errores
Los errores surgen de la modificación involuntaria de
información en el proceso de transmisión y recepción.
Esto puede deberse a diferentes tipos de ruido en el sistema o

fallos externos en los equipos.
Códigos detectores de error
Los codigos detectores de errores una vez detectan

problemas en el mensaje solicita la retransmisión del mismo.
Distancia de Hamming
La distancia de Hamming esta dada por el número de bits diferentes entre dos
mensajes.
Distancia de Hamming=4
Propiedades para la detección de errores
Para detectar d errores de un bit entre dos palabras es necesario un código con una
distancia de hamming de al menos d+1
Con una distancia de hamming d se pueden detectar d-1 errores
Ejemplo: C={001,010,100} distancia de Hamming=? Tip: hallar la distancia entre

mensajes
Un error en 001-----→101,011,000 , son mensajes que no pertenecen a C
Dos errores en 001----→111,010,001 hay dos mensajes que pertenecen a C

Corrección de errores
Propiedades para la corrección de errores
Para corregir d errores de un bit entre dos palabras es necesario un código con una
distancia de Hamming de al menos 2d+1
De otra forma: Con una distancia de Hamming de d se pueden corregir (d-1)/2 errores
Ejercicio
C = {0000000000, 0000011111, 1111100000, distancia de hamming=?

1111111111}, ,Cuántos errores se pueden detectar?,Cúantos errores se pueden
corregir?,
Comprobación de paridad
A los bloques se les añade un bit llamado de paridad

y que, normalmente, precede a la información
• Bit de paridad par:

- Nº total de “1” par: Bit de paridad = 0
- Nº total de “1” impar: Bit de paridad = 1
• Bit de paridad impar:

- Nº total de “1” par: Bit de paridad = 1
- Nº total de “1” impar: Bit de paridad = 0
Completar la tabla con criterio par

(1) e impar (2)
Codigos de redunancia ciclica
Se interpretan las cadenas de 1’s y 0’s como coeficientes
enteros módulo 2 de polinomios
• Los k bits de cada mensaje se tratan como si fueran los
coeficientes de un polinomio M(x), de orden k-1, en el
que las
operaciones se hacen en módulo 2
• Si el mensaje fuese: 10010110
el polinomio considerado sería:
M(x) = 1 • x^7 + 0 • x^ 6 + 0 • x^ 5 + 1 • x^ 4 + 0 • x^ 3 + 1
• x^ 2 + 1 • x^ 1 + 0 • x 0 =
= x ^7 + x^ 4 + x ^2 + x
• Se utiliza un polinomio generador G(x) de grado r. Este
polinomio
está predeterminado, y es el mismo en el emisor y el
receptor
Receptor:
- Recibe el mensaje T’(x) del emisor
- Divide T’(x) entre G(x)
- Si el resto es cero, el mensaje ha llegado
correctamente
(T’(x) = T(x))
- Si el resto no es cero, el mensaje ha llegado con
error y hay
que pedir una retransmisión (T’(x) ≠ T(x))
Referencias
Abramson, N. (1963). Information theory and coding.
Carlson, A. B. (1986). Communication Systems: An Introducton to Signals and
Noise in Electrical Communication. McGraw Hill.
https://www.allsyllabus.com/aj/note/Computer_Science/Information%20Theo
ry%20and%20Coding/s12/Joint%20and%20Conditional%20Entropies.php#.WsJv0H
UbM8o
http://arantxa.ii.uam.es/~ig/teoria/temas/IG_tema-4-2008-2009.pdf
Calcular entropía y eficiencia

Clase 2

Cargado por

Copyright:

Formatos disponibles

Clase 2

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Clase 2

Cargado por

Copyright:

Formatos disponibles

Códigos unívocamente

Este código no es unívocamente decodificable porque la

S =[3 , 11,22] Código prefijo

S =[1 ,12,33 ] Código no prefijo

Podemos saber instantáneamente su decodificación!!!

1611333425012 Analicemos esta secuencia

C (a) =0 C (a) =101

Cual es prefijo?, por qué?

Y nos relaciona el “promedio ” de digitos binarios

La idea es lograr decodificar sin perder información, esto requiere que

Evaluar la eficiencia de cada código,

La Longitud media de código no debería superar el valor

Sirve para escoger la longitud de cada símbolo codíficado,

Dividiendo por n tenemos:

Si n es muy grande , la longitud media de código tenderá

Completar el cuadro utilizando el teorema de shannon , hallar la entropía y

Se aplica la técnica de divide y vencerás!!

Se divide la suma de probabilidades en valores similares.

Se repite la tarea hasta que se termine de codificar

Calcular entropía y eficiencia

Hallar H(x) y eficiencia.

Calcular entropía , longitud media de

● Asignar 0 y 1 a cada uno

● Los numeros que conformaron la suma anterior deben ir

● Repetir el paso anterior hasta llegar a la primera fuente

Calcular entropía , longitud media de

Calcular entropía , longitud media de

Los códigos r-arios combinan r valores y por lo tanto la fuente se

La idea es que la fuente reducida sea de r valores

Esto no siempre va a pasar, por lo tanto hay que agregar desde el

De acuerdo a esto la fuente original debe estar compuesta por

r+a(r-1) símbolos con a= valor entero

Calcular p(b=0), p(b=1) y probabilidades a posteriori y entropías a

Obtener I(X;Y) ,I(X;Z)

Supongamos que tenemos un canal binario simétrico cuya

H(p) es la función herradura, w y p son las probabilidades respectivas

Si se tiene una fuente cin una tasa de s simbolos/segundo, entonces la capacidad

S/N= La relación señal a ruido

Esto puede deberse a diferentes tipos de ruido en el sistema o

Los codigos detectores de errores una vez detectan

Con una distancia de hamming d se pueden detectar d-1 errores

Ejemplo: C={001,010,100} distancia de Hamming=? Tip: hallar la distancia entre

Un error en 001-----→101,011,000 , son mensajes que no pertenecen a C

Dos errores en 001----→111,010,001 hay dos mensajes que pertenecen a C

C = {0000000000, 0000011111, 1111100000, distancia de hamming=?

A los bloques se les añade un bit llamado de paridad

• Bit de paridad par:

• Bit de paridad impar:

Completar la tabla con criterio par

Calcular entropía y eficiencia

También podría gustarte