Tema 5 -> códigos lineales PDF

Preview

Summary

Apuntes del tema 5: códigos lineales. Curso 17/18....

Description

Tema 5 Códigos Lineales Recuerda que estas notas son, únicamente, parte del material de trabajo de los profesores de esta asignatura. Los contenidos de este tema se pueden ver en los siguientes libros: Rifà, J. y Huguet, Ll. Comunicación Digital. Ed. Masson. (Tema 5) Cameron, P. J. Introduction to Algebra. Oxford University Press. (Tema 8)

Objetivos del Tema 1. Saber definir y reconocer un código lineal sobre un alfabeto del canal dado y sus propiedades básicas. 2. Saber definir y utilizar las nociones de matriz generadora y matriz control de paridad de un código lineal. 3. Saber calcular la matriz generadora de un código y una matriz control de paridad. 4. Conocer el concepto de peso Hamming. Calcular el peso de un vector. 5. Saber definir y calcular los parámetros de un código lineal: longitud, dimensión y peso mínimo. 6. Conocer las capacidades de detección y corrección de errores de un código lineal. 7. Saber construir la tabla de síndromes de un código lineal y utilizarla en el proceso de descodificación. 8. Definir un código de Hamming binario, la matriz control de paridad y la matriz generadora de dichos códigos. 87

88

Tema 5. Códigos lineales

9. Conocer y utilizar el algoritmo de descodificación para códigos de Hamming binarios. 10. Definir un código de Hamming ampliado, la matriz control de paridad y la matriz generadora de dichos códigos. 11. Conocer y utilizar el algoritmo de descodificación para códigos de Hamming ampliados.

5.1 Introducción. En un sistema de comunicación digital se modeliza la transmisión de información entre un emisor y un receptor, conectados a través de un canal de comunicación. El canal de comunicación es capaz de admitir en cada instante de tiempo un elemento de un conjunto finito de símbolos A, denominado alfabeto del canal o del código. Normalmente, el conjunto A se representa por un conjunto de dígitos, de ahí el término comunicación digital. Una cadena de n símbolos de A se denominan palabra de longitud n, el conjunto de las palabras de longitud n formadas por símbolos de A se denota por An y el conjunto de las palabras de longitud finita formadas por símbolos de A se denota por A*. El emisor tiene que representar la información que quiere transmitir en palabras del alfabeto A y enviarlas a través del canal de forma secuencial. En la mayoría de los casos, imperfecciones del canal, denominadas ruido, provocan que algunos caracteres sean transmitidos incorrectamente a través del canal, de forma que las palabras recibidas son distintas de las enviadas. La información que recibe el receptor ya no sería útil, incluso puede suceder que el receptor considere correcta la transmisión y ejecute una acción no deseada. Para evitar esto, el emisor añade información redundante al mensaje antes de su transmisión. El objetivo es que el receptor sea capaz de detectar e incluso corregir los posibles errores y reconstruir el mensaje original. Veamos unos ejemplos. Ejemplo 5.1.1. Supongamos que un centro de control marítimo tiene que transmitir a los barcos la ruta que deben seguir para llegar a puerto utilizando un canal binario, A = {0, 1}, cuya probabilidad de transmitir incorrectamente un bit es del uno por mil (uno de cada mil bits se recibirá mal). Si el emisor “codifica” navegar una milla náutica en dirección Norte por 00, en dirección Este por 01, en dirección Oeste por 10 y en dirección Sur por 11, este código no detecta errores, todo par de bits se interpreta como un mensaje correcto.

Tema 5. Códigos lineales

89

Si la ruta que se desea enviar es NNEE, quedaría codificada como 00 00 01 01 (se han insertado espacios entre las palabras para facilitar su lectura). Supongamos que por efecto de las interferencias se recibe como 00 01 01 11, lo que sería interpretado como la ruta NEES. La probabilidad de que un barco reciba correctamente una ruta de veinte millas es del 96,077 %. En el 3,923 % se recibiría un ruta incorrecta. Si el emisor añade un bit de información extra y “codifica” navegar una milla náutica en dirección Norte por 000, en dirección Este por 011, en dirección Oeste por 101 y en dirección Sur por 110, el código es capaz de detectar errores de un bit en cada palabra transmitida y la ruta quedaría codificada como 000 000 011 011. Si se recibe la transmisión 000 010 011 111, el receptor detecta que la segunda y la cuarta palabra no son válidas, pidiendo una retransmisión del mensaje. La probabilidad de recibir la ruta correctamente desciende hasta un 94,174 %, pero en un 5,820 % de los casos se detectará que la transmisión es incorrecta, pidiendo su repetición. En consecuencia, la probabilidad de interpretar mal la ruta baja del 3,923 % al 0,006 %. En el caso de que no fuese posible pedir la retransmisión de la ruta, sería preferible la utilización de un código capaz de corregir errores simples (de un bit en cada palabra transmitida). Por ejemplo, “codificando” navegar una milla náutica en dirección Norte por 00000, dirección Este por 01101, dirección Oeste por 10110 y dirección Sur por 11011, la ruta quedaría ahora codificada como 00000 00000 01101 01101. Al recibir la transmisión 00000 01000 01101 11101, de nuevo las palabras segunda y cuarta se detectan como incorrectas, pero debido a las capacidades del código son substituidas por las palabras código “más parecidas”, 00000 y 01101 respectivamente, obteniendo la ruta correcta. La probabilidad de que la ruta sea correctamente interpretada aumenta hasta el 99,98 %, pero a costa de incrementar de cuarenta a cien el número de bits transmitidos. Ejemplo 5.1.2. Para transformar una grabación musical analógica a digital, cada segundo de audio se convierte en 44 100 muestras de 32 bits, 1 411 200 bits para cada segundo de música. Para corregir posibles errores, control y visualización, cada bloque de 192 bits (corresponden a seis muestras) se transforma en un bloque de 264 bits añadiendo 72 bits de información adicional1.

1

Sin embargo, las limitaciones físicas del láser hacen necesario que cada bloque se represente

por 581 bits en la grabación de la pista del CD.

90

Tema 5. Códigos lineales

5.2 Códigos lineales Los códigos lineales son una clase particular de códigos que utilizan los conceptos del Álgebra Lineal para facilitar su implementación y mejorar su rendimiento. El alfabeto del canal se representa por el conjunto de los enteros módulo un primo p, Z p = {0, 1, 2,…, p – 1}, con las operaciones de suma y producto módulo p (apéndice 1.7.1). La mayoría de los códigos más interesantes son binarios y ternarios, para ellos se utiliza como alfabeto los conjuntos Z 2 y Z 3, respectivamente. Definición 5.2.1. Un (n, k) código lineal sobre un alfabeto del canal Z p, con n ≥ k, es una aplicación lineal inyectiva, C: (Z Z p)k → (Z Z p)n. La imagen de la aplicación C se llama subespacio código, y es un subespacio vectorial de dimensión k de (Z Z p)n. Sus elementos se denominan vectores o palabras código. Los valores de n y de k son la longitud y la dimensión del código, respectivamente. En algunas circunstancias, también se denomina código lineal al subespacio código, denotándolo asimismo por C.

Ejemplo 5.2.2. a) El código control de paridad de longitud ocho está definido por C: (Z Z 2)7 → (Z Z 2 )8 , C(a1, a2, a3,…, a7) = (a1, a2, a3,…, a7, a8), siendo a8 = a1 + a2 + a3 +…+ a7. Su longitud es ocho y su dimensión es siete. b) El código de triple repetición está definido por C: Z 2 → (Z Z 2)3, C(a) = (a, a, a). Su longitud es tres y su dimensión uno. El subespacio código es {(0, 0, 0), (1, 1, 1)}. c) El código de triple paridad está definido por C: (Z Z 2)3 → (Z Z 2 )6 , C(a, b, c) = (a, b, c, a + b, a + c, b + c). La longitud del código es seis y la dimensión es tres. El subespacio código es {(0, 0, 0, 0, 0, 0), (1, 0, 0, 1, 1, 0), (0, 1, 0, 1, 0, 1), (0, 0, 1, 0, 1, 1), (1, 1, 0, 0, 1, 1), (1, 0, 1, 1, 0, 1), (0, 1, 1, 1, 1, 0), (1, 1, 1, 0, 0, 0)}.

Tema 5. Códigos lineales

91

5.3 Matriz generadora Definición 5.3.1. La matriz generadora de un (n, k) código lineal C sobre Z p, G, es la matriz asociada a la aplicación lineal C: (Z Z p)k → (Z Z p)n respecto a las bases canónicas de ambos espacios. Las columnas de la matriz G son las imágenes de los vectores de la base canónica de (Z Z p)k y, como la aplicación es inyectiva, forman una base de la imagen de C, el subespacio código. Ejemplo 5.3.2. La matriz generadora del código control de paridad es

G=

1000000 0100000 0010000 0001000 0000100 0000010 0000001 1111111

La matriz generadora del código de triple repetición es 1 G= 1 1

La matriz generadora del código de triple paridad es 100 010 G= 001 110 101 011

Ejemplo 5.3.3. Consideramos el código lineal binario C: (Z Z 2)4 → (Z 2)7 definido por C(u1, u2, u3, u4) = (u1 + u3, u1, u2, u2 + u3, u2 + u3 + u4, u4, u1 + u2 + u4). La longitud del código es 7 y la dimensión es 4. Calculamos las imágenes por C de los vectores de la base canónica de (Z 2)4, C(1, 0, 0, 0) = (1, 1, 0, 0, 0, 0, 1),

C(0, 1, 0, 0) = (0, 0, 1, 1, 1, 0, 1),

92

Tema 5. Códigos lineales C(0, 0, 1, 0) = (1, 0, 0, 1, 1, 0, 0),

C(0, 0, 0, 1) = (0, 0, 0, 0, 1, 1, 1).

Por tanto su matriz generadora es 1 1 0 G= 0 0 0 1

0 0 1 1 1 0 1

1 0 0 1 1 0 0

0 0 0 0 1 1 1

.

Ejemplo 5.3.4. Consideremos el (7, 4) código lineal binario C con matriz generadora G,

1 1 1 G= 1 1 1 1

1 0 0 0 1 0 1

1 1 0 0 0 1 0

0 1 1 0 0 0 1

;

la aplicación lineal C está definida por C(u1, u2, u3, u4) = (u1 + u2 + u3, u1 + u3 + u4, u1 + u4, u1, u1 + u2, u1 + u3, u1 + u2 + u4), el vector código correspondiente al vector u = (1, 0, 1, 0) es C(u) = (0, 0, 1, 1, 1, 0, 1). Definición 5.3.5. Un (n, k) código lineal C es un código sistemático si las k primeras filas de su matriz generadora G forman la matriz identidad de orden k, Ik. Es decir, G = Ik siendo Q Q una matriz de n – k filas y k columnas. En ese caso, se dice que la matriz generadora del código está en forma estándar o que G es una matriz generadora estándar. Un (n, k) código lineal C es un código separable si entre las filas de su matriz generadora están presentes las filas de Ik, la matriz identidad de orden k. Nota 5.3.6. Si C es un código sistemático, al codificar un vector u = (u1, u2, u3,…, uk) de (Z Z p)k, el vector código correspondiente C(u) = (u1, u2, u3,…, uk, vk+1,…, vn), tiene dos partes claramente diferenciadas. Las primeras k entradas forman el elemento u de (Z p)k, la información que se desea enviar, son los dígitos de información. Las n – k entradas restantes forman la redundancia añadida por el código, se denominan dígitos de control.

Tema 5. Códigos lineales

93

Si C es un código separable, los k dígitos que forman el vector u de (Z p)k aparecen en el vector código correspondiente, no necesariamente ordenados ni en las k primeras coordenadas. Se puede hablar también de dígitos de información y dígitos de control. Todo código sistemático es un código separable. Ejemplo 5.3.7. Los códigos lineales control de paridad, triple repetición y triple paridad son códigos sistemáticos. Ejemplo 5.3.8. El (7, 4) código lineal binario C: (Z Z 2)4 → (Z 2)7definido por C(u1, u2, u3, u4) = (u1 + u2 + u3, u4, u1, u1 + u4, u2, u3, u1 + u2 + u4), tiene matriz generadora G, es un código separable, pero no es sistemático.

1 0 1 G= 1 0 0 1

1 0 0 0 1 0 1

1 0 0 0 0 1 0

0 1 0 1 0 0 1

.

Los cuatro dígitos que forman el vector u aparecen respectivamente en la tercera, quinta, sexta y segunda coordenadas de los vectores código. Ejercicio 5.1. Considera el código binario de triple repetición C: (Z Z 2)3 → (Z 2)9, definido por C(a1, a2, a3) = (a1, a2, a3, a1, a2, a3, a1, a2, a3). Calcula su longitud, dimensión, su matriz generadora y el subespacio código. Ejercicio 5.2. Considera el código binario C: (Z Z 2)4 → (Z 2)9, definido por C(a1, a2, a3, a4) = (a1, a2, a3, a4, a1 + a2, a3 + a4, a1 + a3, a2 + a4, a1 + a2 + a3 + a4). Comprueba que es un código lineal, calcula su longitud, su dimensión y su matriz generadora. Justifica si C un código sistemático o separable. Ejercicio 5.3. Justifica si la siguiente matriz G es una matriz generadora para un código lineal binario. En caso afirmativo, indica cuál es su longitud y su dimensión.

94

Tema 5. Códigos lineales

0 Gt = 1 1 1

1 0 0 0

0 0 1 1

0 1 1 1

1 0 0 0

1 1 0 1

1 1 1 1

0 0 1 0

1 1 . 0 1

5.4 Matriz control de paridad Consideramos una nueva matriz asociada a un código lineal, la matriz control de paridad, que será de gran utilidad para detectar y corregir los errores producidos en las transmisiones. Si aplicamos el punto 4.5.1 del tema Aplicaciones Lineales al subespacio código de un (n, k) código lineal, sabemos que los vectores código son las soluciones de un sistema de (n – k) ecuaciones lineales, homogéneas e independientes. Definición 5.4.1. Una matriz control de paridad H de un (n, k) código lineal C sobre Z p es la matriz de coeficientes de un sistema de (n – k) ecuaciones lineales con n incógnitas, homogéneas e independientes, que caracteriza el subespacio código. Así pues, un mismo código lineal puede tener distintas matrices control de paridad, basta cambiar el sistema de ecuaciones que lo determina por otro equivalente. Recíprocamente una misma matriz H puede ser matriz control de paridad de varios códigos lineales, pero todos ellos tendrán el mismo subespacio código. Definición 5.4.2. Si H es la matriz control de paridad de un (n, k) código lineal C sobre Z p, se llama síndrome del código lineal C a la aplicación lineal S: (Zp)n → (Zp)n-k cuya matriz asociada respecto a las bases canónicas es H, y a S(v), la imagen por S de un vector v de (Zp)n, se le llama síndrome de v. Remarcar que el núcleo de la aplicación lineal S es el subespacio código de C y es una aplicación lineal sobreyectiva porque el rango de H, su matriz asociada, es n – k. Para calcular una matriz control de paridad de un (n, k) código lineal C con matriz generadora G se sigue el método utilizado en el tema 3 para calcular el sistema de ecuaciones

Tema 5. Códigos lineales

95

lineales que caracteriza a un subespacio vectorial. Para ello se tiene en cuenta que los vectores columna de la matriz G forman una base del subespacio código. Ejemplo 5.4.3. Calculemos una matriz control de paridad para el código binario de triple paridad del ejemplo 5.2.2. La matriz generadora del código de triple paridad es

100 010 0 01 G= 110 101 011

.

Por lo tanto el conjunto de vectores columna de G, {(1, 0, 0, 1, 1, 0), (0, 1, 0, 1, 0, 1), (0, 0, 1, 0, 1, 1)}, es una base del subespacio código. Un vector x = (x1, x2, x3,…, x6) de (Z 2)6 pertenece al subespacio código si es combinación lineal de los elementos de la base y eso ocurre cuando

1 rg 0 0 x1

0 1 0 x2

0 0 1 x3

1 1 0 x4

1 0 1 x5

0 1 = rg(G) = 3. 1 x6

Realizamos las siguientes operaciones elementales en la filas de la matriz para hallar una matriz en forma escalonada: F4 + x1F1, F4 + x2F2, F4 + x3F3,

1 0 0 0

0 1 0 0

0 0 1 0 x1 +

1 1 0 x2 + x4

1 0 1 x1 + x3 + x5

0 1 1 x2 + x3 + x6

,

dicha matriz tiene rango tres si todos los elementos de la última fila son nulos, por lo tanto se obtiene el sistema de ecuaciones homogéneo x1 + x2 + x4 = 0,

x1 + x3 + x5 = 0,

x2 + x3 + x6 = 0;

cuya matriz de coeficientes es la matriz H

H=

1 1 0 1 0 0 1 0 1 0 1 0 0 1 1 0 0 1 .

96

Tema 5. Códigos lineales El síndrome del vector (1, 1, 0, 0, 1, 1) es S(1, 1, 0, 0, 1, 1) = (0, 0, 0), es un vector

código. El síndrome del vector (0, 0, 1, 1, 1, 1) es S(0, 0, 1, 1, 1, 1) = (1, 0, 0), y el síndrome de (0, 0, 1, 1, 0, 0) es S(0, 0, 1, 1, 0, 0) = (1, 1, 1), no son vectores código. Ejemplo 5.4.4. Calculemos una matriz control de paridad para el (7, 4) código lineal binario C cuya matriz generadora es G,

1 1 0 G= 0 0 0 1

0 0 1 1 1 0 1

1 0 0 1 1 0 0

0 0 0 0 1 1 1 .

En este caso una base del subespacio código es el conjunto {(1, 1, 0, 0, 0, 0, 1, 1), (0, 0, 1, 1, 1, 0, 1), (1, 0, 0, 1, 1, 0, 0), (0, 0, 0, 0, 1, 1, 1)}. Un vector x = (x1, x2, x3,…, x7) de (Z Z 2)7 pertenece al subespacio código si

rg

G tr x

1 0 = rg 1 0 x1

1 0 0 0 x2

0 1 0 0 x3

0 1 1 0 x4

0 1 1 1 x5

0 0 0 1 x6

1 1 0 = 4. 1 x7

Realizando en la matriz las operaciones elementales F2 ↔ F3, F1 ↔ F2, F2 + F1, F5 + x1F1, F5 + x2F2, F5 + x3F3, F5 + (x1 + x2 + x3 + x5)F4, se obtiene la matriz en forma escalonada equivalente

1 0 0 0 0

0 1 0 0 0

0 0 1 0 0

1 1 1 0 x1 + x2 + x3 + x4

1 1 1 1 0 x1 + x2 +

0 0 0 1 x3 + x5 + x6

0 1 1 1 x1 + x5 + x7

.

El rango es cuatro si todos los elementos de la última fila son nulos, por lo tanto se obtiene el sistema de ecuaciones homogéneo x1 + x2 + x3 + x4 = 0,

x1 + x2 + x3 + x5 + x6 = 0,

y la matriz de coeficientes es H,

H=

1 1 1 1 0 0 0 1 1 1 0 1 1 0 1 0 0 0 1 0 1

.

x1 + x5 + x7 = 0;

Tema 5. Códigos lineales

97

El síndrome del vector (1, 1, 1, 1, 1, 0, 0) es S(1, 1, 1, 1, 1, 0, 0) = (0, 0, 0), el síndrome de (1, 1, 0, 0, 0, 1, 1) es S(1, 1, 0, 0, 0, 1, 1) = (0, 1, 0) y el síndrome de (0, 0, 0, 1, 1, 1, 1) es S(0, 0, 0, 1, 1, 1, 1) = (1, 0, 0). 5.4.5. Notación. Para simplificar la notación, al representar los vectores suprimiremos los paréntesis y las comas entre las componentes. Por ejemplo, el vector (1, 1, 1, 1, 1, 0, 0) se representa como 1111100, el vector (0, 0, 0, 1, 1, 1, 1) como 0001111 y el vector (0, 1, 0) como 010. Ejercicio 5.4. Calcula una matriz control de paridad para los códigos de los ejercicios 5.1, 5.2 y 5.3. Ejercicio 5.5. Calcula una matriz control de paridad para el código lineal ternario con matriz generadora G,

1 2 0 2 1 0 Gt = 0 2 1 1 1 1 . 0 2 1 0 0 2 Ejercicio 5.6. Calcula una matriz control de paridad para el código lineal sobre Z 5 con matriz generadora G,

1 2 4 0 3 Gt = 0 2 1 4 1 2 0 3 1 4

.

5.5 Peso y distancia Hamming Definición 5.5.1. El peso de un vector v de (Z p)n, denotado por w(v), es el número de entradas no nulas de v w(v) = |{i tales que vi ≠ 0; i = 1, 2,…, n}| donde |X| denota el cardinal de un conjunto X (número de elementos que contiene). La distancia Hamming, d(x, y), entre dos vectores x e y de (Z p)n es el peso del vector x – y, d(x, y) = w(x – y).

98

Tema 5. Códigos lineales

Ejemplo 5.5.2. El peso del vector 110101 de (Z Z 2)6 es w(110101) = 4. En el espacio vectorial (Z Z 2)5, el vector 10100 tiene peso 2, w(10100) = 2, y el vector 10111 tiene peso 4, w(10111) = 4. En el espacio vectorial (Z Z 3)4, el vector 0200 tiene peso 1, w(0200) = 1 y el vector 0121 tiene peso 3, w(0121) = 3. El peso del vector 120200 de (Z 3)6 es w(120200) = 3. Ejemplo 5.5.3. La distancia entre los vectores 110101 y 011011 de (Z Z 2)6 es 4 ya que w(110101 – 011011) = w(101110) = 4. La distancia entre los vectores 11001 y 10202 de (Z Z 3 )5 es 3 ya que w(11001 – 10202) = w(01102) = 3. Definición 5.5.4. El peso mínimo de un código lineal C, denotado por w(C), es el menor de los pesos de los vectores código no nulos, w(C) = min {w(v) con v ∈ C, v ≠ 0}. El peso mínimo de un código, con al menos dos vectores, es siempre un valor mayor o igual que uno, ya que el peso de...