1. No category

Chapter 8
Códigos correctores de errores.
Francesc Comellas - José Luis A. Yebra
En este capı́tulo veremos una aplicación de Algebra Lineal de gran interés práctico
y que sólo requiere conocimientos elementales de espacios vectoriales y aritmética
módulo dos. Se trata de la codificación de datos para detectar y corregir errores. Entre
los numerosos ejemplos de aplicación de la codificación citaremos la transmisión de
datos entre satélites y estaciones terrestes, las comunicaciones intercontinentales y
la grabación de datos en discos, ya sean estos de ordenador o musicales.
Espacios Vectoriales.
8.1
Matrices.
Operaciones módulo 2.
Introducción
El 17 de octubre de 1992 y en su seccción habitual del
periódico AVUI, Ramon Solsona comentaba el programa
SETI que la NASA habı́a puesto en marcha entonces
para captar posibles emisiones procedentes de seres inteligentes de otros planetas de nuestra galaxia. Con su
conocida ironı́a, desgrana la hipótesis de que estos seres
se nos han avanzado y escribe:
‘Una cosa similar sucede en la estrella 102-GT,
a la que, por algún fenómeno desconocido de la estratosfera, llega con gran nı́tidez el clamor de los
estadios de fútbol. Los cientı́ficos de 102-GT apenas
han podido entender algo; únicamente tres palabras:
gaaal (o gueeeul o goool o guuul), aiii, fedalti
(o fenalti o pedalti) y unos silbidos que ellos desprecian porque los atribuyen a interferencias.
Figura 1: El satélite Voyager 2.
Contrastemos este eventual hecho con las últimas imágenes transmitidas por Voyager 2 de una
calidad extraordinaria. Las imágenes son de Neptuno y una de sus lunas, Tritón. Tienen 800 por
800 pı́xeles con 256 niveles de gris. Se pueden representar con 5.120.000 bits, se transmiten a 21.6
kilobits por segundo y una imagen tarda unos 100 segundos en ser emitida.
Aunque cada uno de los impulsos transmitidos ha tardado unas 42 horas en viajar de Neptuno
hasta la Terra, y pese a que durante todo este tiempo las señales han estado sometidas al viento
Figure 8.1: Tritón, una luna de Neptuno, se encuentra a unos 4.5 1010 km de la Sagrada Familia
solar y a diversas interferencias, no se ha perdido la información de ninguno de los pı́xeles. ¿Por
qué los cientı́ficos de 102-GT interpretan tan mal los gritos que con perfecta nitidez se hacen al
Camp Nou y en cambio nosotros, a pesar de la debilidad de las señales, recibimos con absoluta
precisión una imagen muy complicada?
Aparte de consideraciones sobre el carácter imaginario de una de las transmisiones, o sobre la
diferente tecnologı́a empleada en ambas para emitir y recibir las señales, una diferencia esencial
entre ellas es que, mientras que la primera no esta codificada para la corrección de errores, la
sgunda sı́ lo está.
8.2
Códigos correctores de errores
El objetivo de la codificación és la protección de la información, a fin de detectar y corregir los
errores que hayan podido surgir durante su transmisión.
El esquema de la Figura 2 ilustra la situación deseada en la transmisión de un mensaje con
codificación.
Missatge
Missatge
es
e
erf
Int
Inte
rfer
Codificació
ènc
ci
rèn
s
rèncie
e
Interf
ies
Decodificació
Missatge
Codificat
Missatge
Codificat
Distorsionat
Figure 8.2: Codificació utòpica.
Sin las etapas de codificación y decodificación el mensaje recibido serı́a una distorsión del
mensaje transmitido, y por lo tanto normalmente inútil. La codificación y posterior decodificación
permite recuperar exactamente el mensaje original si la distorsión es limitada. El precio que se
paga es una cierta redundancia (el mensaje a transmitir será algo más largo) y un pequeño retraso
debido al tiempo requerido por la codificación y la decodificación. En realidad, y sin darnos
cuenta, efectuamos los procesos de codificar y decodificar más frecuentemente de lo que creemos.
Por ejemplo, cuando hablamos con otras personas muchas veces repetimos partes de frases para
que la conversación sea más inteligible. O bien, durante una conversación telefónica, es habitual
repetir letra a letra una palabra que no se ha entendido, al estilo de: ‘P de Portugal, R de Rússia,
E d’Europa, S de Suècia y O de Orense’.
32
Formulación matemática
Para el estudio matemático de la codificación, consideraremos un alfabeto que tendrá únicamente
dos sı́mbolos, por ejemplo el 0 y el 1, a los que llamaremos dı́gitos. A diferencia de lo que ocurre
con nuestro lenguaje habitual, ahora todas las palabras que formemos con este alfabeto tendrán
el mismo número de dı́gitos, n, que se denomina longitud de la palabra.
Designaremos por V n al conjunto de todas las palabras diferentes de longitud n, es decir con
n dı́gitos. Ası́, por ejemplo, V 3 és:
V 3 = {000, 001, 010, 011, 100, 101, 110, 111}
La primera idea básica para codificar consiste en utilizar como palabras válidas de nuestro mensaje,
no todas las de V 3 sino únicamente las de un subconjunto C ⊂ V 3 . Una cosa similar pasa en
nuestro lenguaje, pues no todas las combinaciones posibles de letras del alfabeto son palabras
admitidas, como por ejemplo coxrt o zruttllm. Es precisamente este hecho el que nos permitirá
detectar y corregir errores, de forma análoga a cuando en un texto vemos escrito carretpra, con
lo que immediatamente somos capaces de ver que se trata de un error tipográfico y que lo que en
realidad se querı́a escribir era carretera 1 . Por ejemplo, si únicamente queremos enviar las ordenes
arriba, abajo, izquierda y derecha en la tabla siguiente se muestran tres posibilidades diferentes. El
Código
C1 = V 2
C2 = V 3
C3 = V 6
C4 = V 6
Arriba
00
000
000000
000000
Abajo
01
011
111000
001111
Izquierda
10
101
001110
110011
Derecha
11
110
110011
111100
Table 8.1: Códigos
código C1 es el más corto, pero como utiliza todas las palabras de V 2 no permite corregir ningún
error. Por ejemplo, si se transmite arriba (00) y se produce un error en el primer dı́gito, el
mensaje recibido, 10, se interpretará como izquierda.
El código C2 , sin embargo, permite detectar qualquier error que afecte a un único dı́gito.
Observemos primeramente que C2 se obtiene a partir de C1 añadiendo a cada palabra un dı́gito
más que se denomina dı́gito de paridad: 0 si en C1 habı́a un número par de unos y 1 si el número
de unos era impar. Por ello ahora todas las palabras del código C2 tienen un número par de
unos. De esta forma, si cuando se transmite una palabra se produce un error en un único dı́gito,
la palabra resultante tendrá un número impar de unos y por lo tanto no pertenecerá al código
C2 . Ası́ habremos detectado el error. Este código no nos permite su corrección. En la práctica,
la detección (sin corrección) de errores sólo tiene sentido si el receptor puede pedir al emisor que
vuelva a enviar el mensaje.
Finalmente, el código C4 , el triple de largo que el C1, permite no sólo detectar errores sino
incluso corregirlos (siempre y cuando sólo haya habido uno por palabra). Ello es posible gracias a
que hay mucha más redundancia o, más precisamente, a que las palabras del código se diferencian
entre si de tal manera que un único error se puede arreglar.
A continuación entraremos en mayor detalle gracias a una formulación matemática conveniente
de las ideas expresadas anteriormente.
Llamaremos distancia entre dos palabras al número de dı́gitos en que difieren y distancia
mı́nima de un código a la menor distancia entre sus palabras. Per ejemplo, en el código C2 la
distancia entre qualquier par de palabras es 2, por tanto ésta es la distancia mı́nima del código,
mientras que en el código C3 hay palabras a distancia 3, 4 y 5, por lo que la distancia mı́nima en
este código es 3.
1 Es mucho menos probable que los errores sean dos y que se quisiera escribir carrera. Del contexto -redundancia
adicional- podrı́amos deducirlo.
33
Ejercicio 8.1 Determinar que pares de palabras de C3 están a distancia 3, a distància 4 y a
distància 5.
Ejercicio 8.2 Determinar la distancia mı́nima del código C4 .
Si sólo deseamos detectar errores, un código de distancia mı́nima d permite detectar hasta
d − 1 errores, ya que en él al modificar menos de d dı́gitos de una palabra código la palabra que
se obtiene no puede ser otra palabra código.
Pero no debemos olvidar que nuestro objetivo es más ambicioso: corregir los errores. ¿Cómo?
Veamos primero un ejemplo. Supongamos que estemos utilizando el código C4 y que a causa
de las dichosas interferencies recibimos 001011. Basta comparar esta palabra con las del código
para percatarse de que se ha producido algún error, ya que no coincide con ninguna de ellas.
Se puede haber producido un error al transmitir la palabra 001111, o bien tres al transmitir la
000000 o la 110011, o incluso cinco si la palabra era 111100. Si admitimos que los errores no son
muy frecuentes, lo más verosı́mil es que se haya producido un único error en la transmisión de
la palabra 001111. Este sera nuestro principio de decodificación: buscar el vecino más próximo.
De esta forma, un código permite corregir hasta e errores si 2e + 1 ≤ d, la distancia mı́nima del
código (Figura 3).
V
n
Paraules del codi
d
n
Altres paraules de V
d
e
e
Figure 8.3: Un código C puede corregir e errores si su distancia mı́nima d es tal que d ≥ 2e + 1.
Ejercicio 8.3 ¿Se pueden detectar y/o corregir una modificación en 1,2 y 3 dı́gitos de una palabra
código de C4 ?.
8.2.1
Códigos lineales
El conjunto V n puede ser visto como (Z2 )n . Si consideramos en él las operacions suma dı́gito a
dı́gito módulo 2 (101100 + 001010 = 100110) y producto por un escalar (los escalares a considerar
son los de Z2 es decir el 0 y el 1), entonces el conjunto V n es un espacio vectorial sobre el cuerpo
Z2 .
Ejercicio 8.4 Dados v = (1, 1, 0, 0, 1, 0)T y w = (0, 1, 1, 0, 1, 1)T de (Z2 )6 , determinar (a) v + w
(b) −v (c) λv para todo λ ∈ Z2 .
En este contexto, un código lineal es simplemente un subespacio vectorial de (Z2 )n . Ası́, C1 ,
C2 y C4 son códigos lineales, mientras que C3 no lo es.
34
Ejercicio 8.5 ¿Por qué C3 no es un código lineal ?
El espacio (Z2 )n tiene 2n elementos y sus subespacios tienen 2k elementos, 0 ≤ k ≤ n. Mientras
que la dimensión de (Z2 )n , es decir n, es la longitud del código, k recibe el nombre de dimensión
del código, ya que es su dimensión como subespacio vectorial de (Z2)n . Por ejemplo, C2 que tiene
4 = 22 elementos y por tanto dimensión 2, admite como base 011 y 101 -estamos utilizando la
abreviación 011 para (0, 1, 1)T -:
0(011) + 0(101) = 000
1(011) + 0(101) = 011
0(011) + 1(101) = 101
1(011) + 1(101) = 110
Trabajar con códigos lineales presenta numerosas ventajas. Una de ellas es que resulta mucho
más fácil calcular su distancia mı́nima. Mientras que en general habrı́a que calcular la distancia
entre todos los pares de palabras del código, para un código lineal es fácil comprobar que su
distancia mı́nima es igual al número de unos de la palabra que tiene menos (sin considerar la que
sólo tiene ceros).
Ejercicio 8.6 Construye un código lineal de cuatro palabras de longitud 8 que pueda corregir dos
errores.
8.2.2
Matriz generadora y matriz de comprobación de paridad de un
código
Recordemos que en un espacio vectorial de dimensión n, es habitual especificar un subespacio
vectorial de dimensión k de una de las dos maneras siguientes:
1. Por medio de una base del subespacio, es decir como el conjunto de vectores que son combinación lineal de k vectores linealmente independentes del subespacio.
2. Como el nucleo de una aplicación lineal de rango n − k definida en ese espacio vectorial, es
decir como el conjunto de vectores que satisfacen (n − k) equaciones lineales homogéneas e
independentes.
La primera se utilizará para la codificación de mensajes y la segunda para la decodificación.
Codificación
En el primer caso, si C está generado por g1, g2 , . . . , gk y G es la matriz k × n cuyas filas son (las
coordenadas de) g1, g2 , . . . , gk , los vectores c de C se obtendrán calculando
cT = (c1 , c2 , . . . , cn ) = (m1 , m2, . . . , mk )G = mT G
Esta equación recibe el nombre de regla de codificación ya que permite obtener cada palabra
código c a partir del mensaje m = (m1 , m2 , . . . , mk ), el cual está formado por los coeficientes de
la combinación lineal c = m1 g1 + m2 g2 + . . . + mk gk .
Por ejemplo,
C2 podemos considerar g1 = (101) y g2 = (011), para los que se
¶
µ para el código
1 0 1
y:
obtiene G =
0 1 1
µ
1
µ 0
1
(10)
0
(00)
0
1
0
1
¶
1
= (000)
1 ¶
1
= (101)
1
µ
1
µ 0
1
(11)
0
(01)
0
1
0
1
¶
1
= (011)
1 ¶
1
= (110)
1
35
Ahı́ se puede ver la regla de codificación:
(mensaje)G = (palabra código)
Por otra parte se puede observar que mientras que el mensaje a transmitir tiene k dı́gitos, la
palabra código tiene n. Los n − k dı́gitos que se han añadido a los k originales constituyen la
redundancia que permitirá corregir errores y se denominan genéricamente dı́gitos de paridad.
Decodificación
Decodificar un mensaje significa comprobarlo para determinar si ha habido errores, corregirlos en
caso de haberse producido y finalmente extraer el mensaje original. Discutiremos en primer lugar
la comprobación del mensaje sobre el ejemplo anterior. Sea H = (1 1 1) una matriz 1 × 3. Esta
matriz tiene rango 1 y como rang(H) + dim Ker(H) = 3 resulta que dim Ker(H) = 2. Es fácil
comprobar que g1 = (101) y g2 = (011) generan precisamente el nucleo de H . Basta observar
que Hv es igual al número de unos que tiene el vector v módulo 2. Por ello la matriz H es
conocida como matriz de comprobación de paridad. Para los vectores del código Hv vale 0. Ası́
C2 = {v ∈ (Z2 )3 | Hv = 0}.
En general, H será una matriz (n − k) × n de rango (n − k) para la que se tendrá:
½
= 0 ⇔ v ∈ C es decir v es una palabra código
Hv =
6= 0 ⇔ v 6∈ C es decir v no es una palabra código
Por este motivo la matriz H se utilizará para decodificar los mensajes. Observese que que ahora
los vectores de C aparecen como aquellos que satisfacen (n − k) ecuaciones lineales homogéneas
independientes.
Ejercicio 8.7 Hallar HGT .
8.2.3
Una codificación más realista
Hasta ahora únicamente hemos podido codificar cuatro instrucciones. Con cuatro instrucciones
ya se pueden hacer algunas cosas, pero para gobernar remotamente una nave espacial conviene
añadir unas cuantas más. Ası́ que utilizaremosr los diez números del 0 al 9 y las seis instrucciones
de dirección arriba, abajo, adelante, atrás, izquierda y derecha. Asignemos a cada una
de estas instrucciones un número correlativo del10 al 15. A partir de los 16 números en base 2
ası́
 obtenidos se generan las
 dieciseis palabras del código mediante la matriz generadora. G =
1 0 0 0 0 1 1
 0 1 0 0 1 0 1 


 0 0 1 0 1 1 0  Ası́, por ejemplo, el código correspondiente a abajo es
0 0 0 1 1 1 1
abajo = 1110 → 10112 → (1011)G = (1011010)
O bien, si quisiéramos que la nave se desplazase a la izquierda catorce unidades, deberı́amos
enviar el mensaje:
izquierda 1 4 = 1410 110 410 → 1110200012 01002 → 111000000011110100101
La Tabla 2, incompleta, muestra algunas de las palabras del código C(7, 4).
Ejercicio 8.8 Ejercicio 8.9 Completar la tabla anterior.
Codificar el siguiente mensaje:
adelante 7 izquierda 13 arriba 17
36
Instrucción
0
1
2
3
4
5
6
7
8
9
arriba
abajo
adelante
atrás
izquierda
derecha
Valor
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Binari
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
código
0000000
0001111
0010110
0011001
0100101
0101010
0110011
1011010
1110000
1111111
Table 8.2: Palabras del código C(7, 4).
Es fácil comprobar que este código tiene distancia mı́nima d = 3, por lo que permite corregir
únicamente un error en cada palabra.
La matriz decodificadora se puede obtenir a partir de los cuatro vectores fila de G . Se ha de
verificar:
Hg1 = 0 Hg2 = 0 Hg3 = 0 Hg4 = 0

0 0
Ası́ una posible matriz H (de las muchas que satisfacen estas condiciones) es  0 1
1 0
Veamos como podemos utilizarla para decodificar cada palabra recibida w corrigiendo
error.
0 1 1 1
1 0 0 1
1 0 1 0
el eventual
1. Calculemos Hw.
2. Si Hw = 0 sabemos que la palabra recibida w es una palabra del código. No ha habido
ningún error, por lo que bastará leer la tabla para conocer la instrucción transmitida.
3. Si Hw 6= 0, la palabra recibida w no és una palabra del código. Se ha producido algún error
que ha alterado la palabra código transmitida v :
↓ε
v −→ v + ε = w
donde, con la hipótesis de que únicamente se ha producido un error, ε es un vector de la
forma ε = (00 . . . 010 . . . 0) es decir todas sus componentes son nulas salvo una, la de lugar
i, que vale 1. De esta forma v y w sólo se diferencian en el dı́gito que ocupa el lugar i, pero
precisamente:
Hw = H(v + ε) = Hv + Hε = Hε = h(i) (= columna i de H )
ya que v es una palabra del código. Ası́, cuando Hw 6= 0 basta buscar la columna de H que
coincide con el resultado Hw para determinar el lugar i del error. Es más, con la matriz
H elegida podemos observar que cada columna expresa, en base 2, el lugar que ocupa. Ası́,
Hw da directamente la posición donde se ha producido el error y por tanto que dı́gito de w
hay corregir.
Ejemplo:
37

1
1 
1


1
Si la palabra recibida es w = 1010111, se obtiene Hw =  1  y como 1102 = 610 , el error se
0
ha producido en el dı́gito sexto. En consequencia, la palabra código transmitida era v = 1010101,
es decir la instrucción arriba.
Ejercicio 8.10 Decodificar el siguiente mensaje:
11011111000011101011101011101100101
Ejercicio 8.11 Si en la transmisión del mensaje codificado del ejercicio 8 (que tiene 56 dı́gitos)
se produjesen errores en los dı́gitos que ocupan los lugares 7, 13 y 17, ¿podrı́amos corregirlos?.
¿Por qué ?
Ejercicio 8.12 ¿Y si los errores fuesen en los dı́gitos 8 y 14 ?
Uso de MAPLE
Para realizar los ejercicios propuestos utilizando MAPLE se ha adaptado una parte de la libreria
linalg para su uso con aritmética módulo 2. También se han definido las matrices G y H del
código C7,4 que se designan por G7 y H7. En el apéndice se encuentra el listado completo. Para
acceder a él hay que hacer:
> with(linalg):read ‘codes.m‘;
Las nuevas operaciones son:
add2, scalarmul2 y multiply2
cuya forma de operar es análoga a la de linalg pero módulo 2.
distance(v1,v2)
que calcula la distancia entre dos vectores v1 y v2.
38
Ejercicio avanzado
En el marco del programa SETI, el radiotelescopio de Arecibo (Puerto
Rico) de 305 m de diámetro, ha transmitido al espacio una imagen
(Figura 4), codificada de una forma sencilla para que pueda ser interpretada por los seres inteligentes que eventualmente la capten. Un
fragmento de esta imagen ha sido comprimido y después codificado con
el código C(7, 4). Desgraciadamente, también se ha alterado alguno de
los bits. El resultado es:
0111100011101011100100111100101010111110111100000
1111111001100101110101001100011101101000101001100
1011010000100101001010110011110110010101011000101
1010001101010111100101101110101101000101111100110
1001001100110010110100001001
Figura 4: ¿Qué quiere decir esto?
El trozo escogido tiene 12 × 21 pı́xeles. Cada pı́xel puede tomar dos
valores: negro (0) o blanco (1). La compresión del mensaje, previa a su
codificación, se ha hecho ası́: Se ha considerado la imagen como si fuera
una lista de 252 dı́gitos comenzando arriba a la izquierda y yendo siempre
de arriba hacia abajo y de izquierda a derecha. Si el pı́xel tiene valor 1 se
escribe 1, si tiene valor 0 se mira cuantos pı́xeles siguen de valor cero i se
escribe 0 y cuatro bits que expresan, en binario, el número de ceros que
hay en total (contando también el primero y hasta un máximo de 16).
Por ejemplo, el mensaje 000000000011000000000000010 se comprimido
a 010101101101100001, es decir 0 seguido de 10102 = 10, porque hay
10 ceros, después los dos 1, otro cero y 11012 = 13 (ya que después de
los dos unos hay trece ceros), un 1 y finalmente 0 seguido de 00012 = 1
para indicar el último cero. Una vez comprimida, la imagen se codifica
utilizando el código C(7, 4) y por tanto de cada cuatro bits se obtienen
siete. Después alguno de los bits ha sido alterado. Observese que, gracias
a la compresión, el mensaje final codificado solo tiene 224 bits (menos
que el original, pese al incremento que supone la utilización del código
corrector C(7, 4)).
El ejercicio consiste en recuperar e identificar el trozo de imagen
original.
39
Bibliography
[GO91] Goldie, C.M. y Pinch, R.G.E. Communication Theory. Cambridge University Press, 1991;
ISBN 0 521 40606 4.
[GR91] Gribbin, J. Is anyone out there?. New Scientist, 25 de Maig de 1991, pp. 29-32.
[HE89] Henbest, N. Neptune: Voyager’s last picture show. New Scientist, 9 de Setembre de 1989,
pp. 45–48.
[HE92a] Henbest, N. SETI: the search continues. New Scientist, 10 d’Octubre de 1992, pp. 12-13.
[HE92b] Henbest, N. When will Earthlings see the light?. New Scientist, 12 de Desembre de 1992,
p. 48.
[LA86] Laeser, P.L.; McLaughlin, W.I. y Wolff, D.M. Engineering Voyager 2’s Encounter with
Uranus. Scientific American, Novembre 1986, vol. 255, pp. 34–43.
[SO92] Solsona, R. Ells també ens espien. AVUI, dissabte 17 d’Octubre de 1992, p. 52.
40