Teoría de la Información y Códigos Correctores

Prof. Víctor Ramos

🌎 http://victor.ramos.online.fr UAM-Iztapalapa
🖂 [email protected] Ciudad de México
Estructura de un sistema de comunicaciones digitales
(again)

Codificador
Codificador 𝐮 Codificador 𝐯
Codificador Codificador Modulador
de fuente de Modulador
de
defuente
fuente decanal
canal

Canal
Canal Σ 𝜂

Codificador
Decodificador û Decodificador 𝐫
Decodificador Decodificador Demodulador
de fuente de Demodulador
dedefuente
fuente decanal
canal

2
Códigos correctores de errores

Los códigos correctores de errores permiten corregir los errores, si no son

demasiados

Este código QR puede leerse gracias a un código Reed-Solomon

3
Canales de comunicación con ruido

 Módem EF → aire → Módem EF

 Módem → Línea telefónica → Módem
 Tarjeta WiFi → Ondas de radio → Tarjeta WiFi
 Sonda espacial → Ondas de radio → Tierra
 RAM → Unidad de disco → RAM
 RAM → Memoria flash → RAM
 Impresora → Código QR → Cámara del
teléfono

4
Un modelo para el ruido en el canal

Canal binario simétrico (BSC) con 𝑓 = 0.1
●
𝑓 : probabilidad de inversión de bit
0 0
1 1

Otro canal importante: Canal de borrado (erasure channel).

Modela pérdidas de paquetes en redes inalámbricas.

5
Códigos de repetición

Repetir cada bit de un mensaje un predeterminado número de veces, e.g., 3 (R3)

𝐮 𝐯

Ejemplo: transmitir 𝐮 = 0010110 sobre el BSC con 𝑓 = 0.1

El mensaje recibido es: 𝐫 = 𝐯 + 𝐧
𝐧 es el ruido agregado, 𝐯 la palabra transmitida

𝐮
𝐯
𝐧
𝐫

6
Códigos de repetición (cont.)

¿Cómo se decodifica el código de repetición R3?

Se utiliza el algoritmo de mayoría de votos

𝐮
𝐯
𝐧
𝐫
û 0 0 1 0 0 1 0
Errores corregidos *
Errores no detectados *

7
Códigos de repetición
Se reduce la probabilidad de error
Sin embargo, ¡la tasa de transferencia de información disminuye un factor de 3!

8 Fuente: Information theory, inference and learning algorithms, David MacKay, Cambridge Press
Resumen: código de repetición
 Cada bit de información se codifica a 3 bits transmitidos. La tasa del código es
𝑅 = 𝑘/𝑛 = ⅓ 𝑘: bits de información 𝑛: tamaño de la palabra
 Este código puede corregir la inversión de un bit (o dos bits de redundancia
(erasure bits, no mostrados)
Palabra de código recibida Decodificada como
000 0 (sin errores)
001 0
010 0
100 0
111 1 (sin errores)
110 1
101 1
011 1

9
Códigos rectangulares

Códigos rectangulares: la info se acomoda en un rectángulo de

(𝑚 – 1) × (𝑛 - 1)
Paridad par: las sumas en
renglón y columna son las
mismas
1 1 1
Redundancia=1+ + +
m−1 n−1 (m−1)(n−1)

Para un tamaño dado mn, la redundancia será menor

cuando el rectángulo se aproxime a un cuadrado.

Para códigos cuadrados de tamaño 𝑛, se tienen

(𝑛 – 1)2 bits de información y 2𝑛 – 1 bits de paridad en
los lados

10
Códigos rectangulares: ejemplo

Error corregible
Sin errores de un bit

Error de paridad

Error de paridad

11
Visualización de los códigos correctores de errores
(ECCs)

Un ECC escoge un subconjunto del espacio para las palabras de código válidas
Num. de mensajes válidos < num. total de mensajes posibles
Se sacrifica velocidad de transmisión por robustez (tradeoff)
El tamaño de cada círculo es la cantidad de redundancia
Mientras más grande el círculo (más redundancia), menor el número de mensajes válidos

Palabras de código

Volumen dentro del

que
puede tolerarse el
ruido

12
Objetivo de los códigos correctores de errores

Encontrar esquemas matemáticos que permitan

codificación y decodificación eficientes en tiempo y
espacio y, al mismo tiempo, ofrecer altas tasas de
comunicación y bajas tasas de errores de bit, a pesar
de la presencia de ruido

13
Tipos de códigos correctores de errores
 Algebraicos
 Códigos de Hamming
 Reed-Solomon [CD, DVD, unidades de disco duro, códigos QR]
 Códigos BCH
 Códigos de grafos dispersos
 Turbo [CDMA 2000 1x]
 Repetir acumular
 LDPC (Low Density Parity Check)
- WiMax, 802.11n, 10GBase 10, 802.3an
 Fountain, Tornado, LT, Raptor
- Difusión móvil celular 3GPP, DVB-H para multicast IP

14
Tipos de códigos (otras clasificaciones)

Códigos de bloque Códigos convolucionales

●
Mensaje: 𝐮 = (𝑢0, 𝑢1, …, 𝑢𝑘−1) ●
También aceptan bloques de
●
2𝑘 diferentes mensajes posibles información de 𝑘 bits, 𝐮
●
Palabra de código: 𝐯 = (𝑣0, 𝑣1, …, 𝑣𝑛−1)
●
Producen una secuencia de código, 𝐯,
de tamaño 𝑛
●
Hay 2𝑘 posibles palabras de código
diferentes ●
𝐮 y 𝐯 denotan secuencias de bloques
●
A esto se le llama código de bloque ●
Cada bloque codificado depende
(𝑛, 𝑘) también de los bloques previos
●
Tasa del código: 𝑅 = 𝑘/𝑛 ●
Son códigos con memoria de orden 𝑚
●
Códigos sin memoria; i.e., se pueden ●
Se implementan con lógica secuencial
implementar con lógica combinacional

15
Código binario de bloque

Un código binario de tamaño 𝑀 y tamaño de palabra 𝑛, es un conjunto de 𝑀 palabras

binarias llamadas palabras de código

𝑀 = 2𝑘 para un entero 𝑘
Al código se le conoce como código binario (𝑛, 𝑘)

Ejemplo: C = {10101, 10010, 01110, 11111}

Es un código muy pobre y muy pequeño, pero satisface la definición
¿𝑀? ¿𝑛?
𝑀 = 4 (palabras de código) 𝑛 = 5 (bits por palabra de código)

16
Código binario de bloque (cont.)

Podemos usar C = {10101, 10010, 01110, 11111} para representar números de dos bits:
00⟷10101
01⟷10010
10⟷01110
11⟷11111
Si se recibe 1 de las 4 palabras de código, suponemos que los dos bits de datos
correspondientes son los dos bits originales
Si ocurre un error, recibimos una palabra de cinco bits desconocida
Ejemplo: recibimos (01100), entonces suponemos que (01110) fue la palabra de código
transmitida y que (10) son los dos bits de datos.

17
Código binario de bloque (cont.)
● El del ejemplo no es un buen código porque no es capaz de corregir muchos patrones de errores

●Deseamos diseñar un código de manera que cada palabra de código sea tan diferente como sea
posible de cualquier otra palabra

Deseamos esto en particular cuando el tamaño del bloque es grande

●

Encontrar buenos códigos podría parecer simple, sin embargo es muy difícil
●

Muchos códigos aún no se han descubierto

●

18
Códigos lineales de bloque
●
Para 2𝑘 mensajes posibles, hay 2𝑘 palabras
●
Las 2𝑘 palabras deben ser distintas
●
Correspondencia 1-1 entre 𝐮 y 𝐯
Definición:

Un código de bloque de tamaño 𝑛 y 2𝑘 palabras posibles es un código lineal

(𝑛,𝑘) ⇔ sus 2𝑘 palabras posibles forman un subespacio dimensional del
espacio vectorial de las 𝑛 tuplas sobre el campo GF(2)

●
Un código de bloque es lineal ⇔ la suma de dos palabras también es una
palabra de código

19
Ejemplo de código de bloque con 𝑘 = 4 y 𝑛 = 7

2𝑛=128 palabras
posibles

20
Ejemplo de código de bloque con 𝑘 = 4 y 𝑛 = 7

2𝑘=16 palabras
válidas

Sin embargo, las

128−16=112
palabras inválidas
son muy útiles

21
Ejemplo de código de bloque con 𝑘 = 4 y 𝑛 = 7

Código
Mensajes Código Mensajes Código sistemático

(0 0 0 0) (0 0 0 0 0 0 0) (0 0 0 1) (1 0 1 0 0 0 1)
(1 0 0 0) (1 1 0 1 0 0 0) (1 0 0 1) (0 1 1 1 0 0 1)
(0 1 0 0) (0 1 1 0 1 0 0) (0 1 0 1) (1 1 0 0 1 0 1)
(1 1 0 0) (1 0 1 1 1 0 0) (1 1 0 1) (0 0 0 1 1 0 1)
(0 0 1 0) (1 1 1 0 0 1 0) (0 0 1 1) (0 1 0 0 0 1 1)
(1 0 1 0) (0 0 1 1 0 1 0) (1 0 1 1) (1 0 0 1 0 1 1)
(0 1 1 0) (1 0 0 0 1 1 0) (0 1 1 1) (0 0 1 0 1 1 1)
(1 1 1 0) (0 1 0 1 1 1 0) (1 1 1 1) (1 1 1 1 1 1 1)

22
Códigos de Hamming: ejemplo 𝐻(7, 4)
Se desea una comunicación con muy baja probabilidad de error y velocidad considerable
Añadir redundancia a bloques de datos en lugar de un bit a la vez
𝐮1𝐮2𝐮3𝐮4 → 𝐯1𝐯2𝐯3𝐯4𝐯5𝐯6𝐯7
𝐯1 – 𝐯4 se escogen tales que:
𝐮1𝐮2𝐮3𝐮4 → 𝐮1𝐮2𝐮3𝐮4𝐯5𝐯6𝐯7
Ejemplo: 1000 → 1000101 𝐯5 1
Los bits de paridad se calculan así:
𝐮1 𝐮2 1 0
𝐮3 0
𝐯5 = 𝐮1 + 𝐮2 + 𝐮3 mod 2 → 1 + 0 + 0 = 1
𝐯6 = 𝐮2 + 𝐮3 + 𝐮4 mod 2 → 0 + 0 + 0 = 0 𝐯7 𝐮4 𝐯6 1 0 0
𝐯7 = 𝐮1 + 𝐮3 + 𝐮4 mod 2 → 1 + 0 + 0 = 1

23
Códigos de Hamming: ejemplo 𝐻(7, 4) (cont.)

Las 16 palabras de este código de Hamming son:

𝐮 𝐯 𝐮 𝐯 𝐮 𝐯 𝐮 𝐯

Cualquier par de palabras del código difiere en al menos 3 bits

Verificar que la suma de dos palabras del Escoger cuatro mensajes de la fuente, 𝐮, y
código es otra palabra de código construir las palabras de código correspondientes

24
¿Preguntas?

25
Teoría de la Información y Códigos Correctores
Prof. Víctor Ramos

🌎 http://victor.ramos.online.fr UAM-Iztapalapa
🖂 [email protected] Ciudad de México
Lista de polinomios primitivos
m m
3 1 + X + X3 14 1 + X + X6 + X10 + X14
4 1 + X + X4 15 1 + X + X15
5 1 + X2 + X5 16 1 + X + X3 + X12 + X16
6 1 + X + X6 17 1 + X3 + X17
7 1 + X3 + X7 18 1 + X7 + X18
8 1 + X2 + X3 + X4 + X8 19 1 + X + X2 + X5 + X19
9 1 + X4 + X9 20 1 + X3 + X20
10 1 + X3 + X10 21 1 + X2 + X21
11 1 + X2 + X11 22 1 + X + X22
12 1 + X + X4 + X6 + X12 23 1 + X5 + X23
13 1 + X + X3 + X4 + X13 24 1 + X + X2 + X7 + X24

27
Construcción del campo de Galois GF(2m)

0•0=0 Entonces:
0•1=1•0=0 0 • αj = αj • 0 = 0
1•1=1 1 • αj = αj • 1 = αj
0•α=α•0=0 αi • αj = αj • αi = αi + j
1•α=α•1=α Tenemos el siguiente conjunto de
elementos sobre el que está definida
α2 = α • α la multiplicación:
α2 = α • α • α F = {0, 1, α, α2, …, αj, …}
… Donde 1 = α0
α2 = α • α ••• α (j veces)

28
Representaciones de los elementos de GF(24)
generados por p(X) = 1 + X + X4
En Polinomios 4-tupla
potencias
0 0 (0 0 0 0)
1 1 (1 0 0 0)
α α (0 1 0 0)
α2 α2 (0 0 1 0)
α3 α3 (0 0 0 1)
α4 1+α (1 1 0 0)
α5 α + α2 (0 1 1 0)
α6 α2 + α3 (0 0 1 1)
α7 1+α + α3 (1 1 0 1)
α8 1 + α2 (1 0 1 0)
α9 α + α3 (0 1 0 1)
α10 1 + α + α2 (1 1 1 0)
α11 α + α2 + (0 1 1 1)
α 3

29 α12 1 + α + α2 + (1 1 1 1)
α3