1. No category

Transmisi´on de Datos
Hoja de Problemas 2:
C´odigos Bloque
1.
Problema 1:
Consideremos el c´
odigo de paridad simple definido por la ecuaci´on c1 + c2 + .... + cn = 0.
Este c´
odigo es capaz de detectar un error simple. Supongamos que a˜
nadimos un segundo bit
de paridad que me incrementa la longitud del c´odigo de n a n + 1 y que tambi´en chequea el
primer bit de paridad.¿Que errores adicionales puede detectar?.
2.
Problema 2:
Consideremos la transmisi´
on de 10000 bits de informaci´on en un canal con probabilidad de
error p de 10 ∗ −3. Calcular
a)
La probabilidad de que haya error en una palabra
b)
La probabilidad de transmisi´on correcta
c)
La probabilidad de que no ocurra un error indetectable
d)
La probabilidad de que ocurra un error indetectable.
Cuando se emplean los siguientes c´odigos:
a)
Sin codificaci´
on.
b)
C´
odigo de paridad simple.
c)
C´
odigo de simple repetici´
on.
Explicar en que situaci´
on (tipo de sistema, requisitos de servicio) emplear´ıas cada c´odigo
justificando la respuesta.
3.
Problema 3:
Dado un c´
odigo bloque C definido por su matriz de paridad.
H=
1
1
1
2
1 ···
3 ···
1
15
Calcular
a)
Encontrar las ecuaciones de codificaci´on de c1 y c2 en funci´on del resto de ci usando
aritm´etica m´
odulo 16.
b)
Corregir la palabra r = (12, 4, 0, 0, 3, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4). Encontar todas las palabras
c´
odigos que puedan generar el error de la palabra considerando que afecta u
´nicamente
a un d´ıgito.
c)
Encontrar las ecuaciones de codificaci´on de c1 y c2 en funci´on del resto de ci usando
aritm´etica m´
odulo 17.
121
4.
Problema 4:
Consideremos una transmisi´
on digital donde se utiliza un c´odigo de Hamming (7,4). El canal
tiene una probabilidad de error en el bit p.
5.
a)
Calcular y representar la probabilidad de decodificaci´on err´onea en funci´on de p.
b)
Encontrar el valor de p a partir del cual la codificaci´on obtiene peor rendimiento que
no codificar. Obtener conclusiones
Problema 5:
El ISBN es un c´
odigo de longitud 10 donde el primer d´ıgito indica el lenguaje del libro
(0 para el ingl´es) los siguientes la editorial (471 Wiley) y despu´es el n´
umero asignado por
la editorial al libro. Los campos son de longitud variable. El u
´ltimo d´ıgito se utiliza como
chequeo.Se utiliza un alfabeto 11 cumpliendo la siguiente ecuaci´on:
10
X
i · x = 0 mod11
i=1
El valor decimal 10, se representa con la letra X.
6.
a)
Calcular el valor del d´ıgito de chequeo para el ISBN cuyos primeros digitos son 0-13200809.
b)
Demostrar que el c´
odigo ISBN puede detectar la transposici´on de dos d´ıgitos cualesquiera.
c)
Es sexto d´ıgito del c´
odigo ISBN 0-13-28 ]796-X ha sido borrado. Encontrar el valor
perdido.
Problema 6:
Consideremes la matriz H de paridad de un c´odigo bloque lineal dada por
H=
α
α2
α2
α
1 1
1 0
Econtrar la matriz sistem´
atica generadora de la forma G [P |I] realizando u
´nicamente operaciones por filas.
7.
Problema 7:
Consideremos el c´
odigo bloque lineal dado por el conjunto de palabras c´odigo:
C = {00000, 01110, 10101, 11011}
a)
Escribir el array est´
andar de este c´odigo.
b)
¿Es un c´
odigo perfecto o casi perfecto?.
c)
Escribir la lista de los patrones de error corregibles para el decodificador completo y
para el decodificador acotado por distancia.
122
d)
8.
Para una probabilidad de error de bit 10−3 calcular la probabilidad de error en la
decodificaci´
on para un decodificador completo. Calcular asimismo la probabilidad de
que el decodificador acotado por distancia indique un fallo en el decodificador.
Problema 8: Un sistema de memoria utiliza palabras de 16, 32 y 64 bits, y se precisa dise˜
nar
sistemas de correcci´
on. Mediante la cota de Hamming obtener cotas inferiores del n´
umero
de d´ıgitos de redundancia necesarios para corregir, 1, 2 y 3 errores.
9.
Problema 9:
Consideremos el c´
odigo LBC (8,4) definido por las siguientes ecuaciones de paridad.
v0
v1
v2
v3
= u1 + u2 + u3
= u0 + u2 + u3
= u0 + u1 + u3
= u0 + u1 + u2
Donde los ui son los bits de informaci´on, los vi son los bits de redundacia y las palabras
c´odigo est´
an formadas de la siguiente manera: (v0 , v1 , v2 , v3 , u0 , u1 , u2 , u3 ).
10.
a)
Encontrar la matriz generadora y la comprobadora de paridad del c´odigo.
b)
Determinar, sin calcular todas las palabras c´odigo, la distancia m´ınima.
c)
Decodificar la palabra r = (1, 0, 1, 0, 0, 1, 0, 0) mediante las ecuaciones de s´ındrome sin
utilizar la matriz H.
d)
Construir un circuito ´
optimo de codificaci´on (M´ınimo n´
umero de puertas l´ogicas).
e)
Construir un circuito ´
optimo para el c´alculo del s´ındrome.
Problema 10:
Consideremos el c´
odigo LBC C = {c1 , c2 , ..., cM }, donde los ci son las palabras c´odigo.
a)
Sea cij el bit j-esimo de la palabra ci . Mostrar que para cualquier j o bien cij = 0, o
bien la mitad de los cij son cero.
b)
Usar el resultado anterior para obtener la Cota de Plotkin para la distancia m´ınima de
cualquier c´
odigo binario de paridad de longitud n:
dmin ≤
11.
n · 2k−1
2k − 1
Problema 11:
Dado un c´
odigo binario C(n, n − 1) de paridad par.
a)
Obtener las matrices generadora y comprobadora de paridad para esta clase de c´odigos
y para su c´
odigo dual C ⊥.
b)
Dada una probabilidad de error en el bit de p calcular la probabilidad de la existencia
de error indetectable en C y C ⊥. ¿Cual de las dos es mayor?.
123
(Nota: Se define la distribuci´
on de pesos en un c´odigo como la cantidad de palabras de
un determinado peso en el mismo. Para la busqueda del error indetectable ayuda en gran
manera obtener esta distribuci´
on de pesos).
12.
Problema 12:
La matriz de comprobaci´
on de paridad de un c´odigo lineal binario es:

0
 1
H=
 1
1
1
1
1
0
1
1
0
1
1
0
1
1
1
0
0
0
0
1
0
0
0
0
1
0

0
0 

0 
1
a)
Calcular la distancia m´ınima del c´odigo.
b)
Escribir la tabla de decodificaci´on por s´ındrome
c)
Determinar la matriz generadora sistem´atica del c´odigo (Recordad que solo debemos
realizar operaciones por filas para no cambiar el c´odigo). Obtener la matriz generadora
del c´
odigo dual. Obtener conclusiones
124