Consideremos un modelo simple de sistema de comunicaciones para el envío y recepción de mensajes codificados (ver la Figura 8.1).
Figura8.1Codificar y Decodificar Mensajes
Mensajes sin codificar pueden estar compuestos de letras o caracteres, pero típicamente consisten de \(m\)-tuplas binarias. Estos mensajes se codifican en palabras de un código, que son \(n\)-tuplas binarias, a través de un mecanismo llamado codificador. El mensaje es transmitido y luego decodificado. Consideraremos la aparición de errores durante la transmisión. Un error occure si hay un cambio en uno o más bits de la palabra del código. Un protocolo decodificador es un método que ya sea convierte \(n\)-tupla arbitraria recibida en un mensaje decodificado coherente o da un mensaje de error para esa \(n\)-tupla. Si el mensaje recibido es una palabra del código (una de las \(n\)-tuplas permitidas), entonces el mensaje decodificado debe ser el mensaje que fue codificado en la palabra del código. Para tuplas recibidas que no están en el código, el protocolo dará una indicación de error, o, si somos más astutos, tratará de corregir el error y reconstruir el mensaje original. Nuestro objetivos es transmitir mensajes libres de errores de la forma más barata y rápida posible.
Ejemplo8.2
Un posible mecanismo de codificación sería enviar el mensaje múltiples veces y comparar las copias recibidas entre ellas. Supongamos que el mensaje a codificar es una \(n\)-tupla binaria \((x_{1}, x_{2}, \ldots, x_{n})\text{.}\) El mensaje se codifica en una \(3n\)-tupla binaria simplemente repitiendo el mensaje tres veces:
Para decodificar el mensaje, escogemos como el \(i\)-ésimo dígito el que aparezca en la \(i\)-ésima posición de al menos dos de las tres transmisiones. Por ejemplo, si el mensaje original es \((0110)\text{,}\) entonces el mensaje transmitido será \((0110\; 0110\; 0110)\text{.}\) Si hay un error de transmisión en el quinto dígito, entonces la palabra recibida será \((0110\; 1110\; 0110)\text{,}\) la que será correctamente decodificada como \((0110)\text{.}\) 2 Adoptaremos la convención de numerar los dígitos de izquierda a derecha en las \(n\)-tuplas binarias. Este método de repetición-triple automáticamente detecta y corrige todos los errores individuales, pero es lento e ineficiente: para enviar un mensaje que consista de \(n\) bits, se requieren \(2n\) bits adicionales, y solo podemos detectar y corregir errores individuales. Veremos que es posible encontrar mecanismos de codificación que codifiquen un mensaje de \(n\) bits en uno de \(m\) bits con \(m\) mucho menor a \(3n\text{.}\)
Ejemplo8.3
La paridad, un mecanismo de codificación usual, es mucho más eficiente que la simple repetición. El código ASCII (American Standard Code for Information Interchange) usa 8-tuplas binarias, dando lugar a \(2^{8} = 256\) 8-tuplas posibles. Pero, solo se necesitan 7 bits pues solo hay \(2^7 = 128\) caracteres ASCII. ¿Qué se puede o debe hacer con el bit restante? Usando los ocho dígitos, podemos detectar un error individual de transmisión. Por ejemplo, los códigos ASCII para A, B, y C son
El bit puede ser usado para controlar errores en los otros siete bits. Se pone como 0 o 1 de manera que el número total de bits 1 en la representación del caracter sea par. Usando paridad, los códigos para A, B, y C se convierten en
Supongamos que se envía una A y ocurre un error de transmisión en el sexto bit de manera que se recibe \((0100\; 0101)\text{.}\) Sabemos que se produjo un error pues se recibió un número impar de unos, y podemos pedir que la palabra sea retransmitida. Cuando se usa para detectar errores, el bit de más a la izquierda se llama bit de control de paridad.
Por lejos el mecanismo más común de detección de errores en los computadores está basado en la adición de un bit de paridad. Típicamente, un computador guarda la información en \(m\)-tuplas llamadas palabras. Largos comunes para las palabras son 8, 16, y 32 bits. Un bit en la palabra se reserva como bit de control de paridad, y no se usa para almacenar información. Este bit se pone como 0 o 1, dependiendo del número de unos de la palabra.
Agregar un control de paridad permite la detección de todos los errores únicos pues cualquier cambio a un solo bit, ya sea aumenta o disminuye en uno el número de unos, y en cualquier caso cambia la paridad de par a impar, de manera que la nueva palabra no es una palabra del código.
El sistema de paridad es fácil de implementar, pero tiene dos desventajas. En primer lugar, errores múltiples no son detectables. Supongamos que se envía una A y se alteran el primer y séptimo dígitos en la transmisión. La palabra recibida resulta ser una palabra del código, pero será decodificada como una C en lugar de una A. En segundo lugar, no tenemos la habilidad de corregir errores. Si la 8-tupla \((1001\; 1000)\) es recibida, sabemos que ha ocurrido un error, pero no tenemos idea cuál es el bit que se ha cambiado. Investigaremos ahora un mecanismo de codificación que no solo nos permita detectar errores de transmisión, sino que nos permita corregirlos.
Palabra
Palabra Recibida
Transmitida
000
001
010
011
100
101
110
111
000
0
1
1
2
1
2
2
3
111
3
2
2
1
2
1
1
0
Cuadro8.4Un código de repetición
Ejemplo8.5
Supongamos que nuestro mensaje original es 0 o 1, y que 0 se codifica en (000) y 1 se codifica en (111). Si ocurre solo un error durante la transmisión, entonces podemos detectar y corregir este error. Por ejemplo, si se recibe un 101, entonces el segundo bit debe haber sido cambiado de 1 a 0. La palabra transmitida debe haber sido (111). Este método detecterá y corregirá todos los errores únicos.
En la Tabla 8.4, presentamos todas las posibles palabras que pueden ser recibidas para las palabras transmitidas (000) y (111). La Tabla 8.4 también muestra el número de bits en los que cada 3-tupla difiere de la palabra original.
El mecanismo de codificación presentado en el Ejemplo 8.5 no es una solución completa del problema pues no toma en cuenta la posibilidad de múltiples errores. Por ejemplo, ya sea un (000) o un (111) se podría enviar y se podría recibir un (001). No tenemos forma de decidir a partir de la palabra recibida si se cometió un solo error en el tercer bit o dos errores, uno en el primer bit y uno en el segundo. Sin importar el mecanismo de codificación usado, un mensaje incorrecto puede ser recibido. Podríamos transmitir un (000), tener errores en los tres bits, y recibir la palabra (111) del código. Es importante explicitar las suposiciones hechas sobre la probabilidad y distribución de los errores de transmisión de manera que, en una aplicación particular, se sabrá si un cierto mecanismo de detección de errores es apropiado. Supondremos que los errores de transmisión son infrecuentes, y, que cuando ocurren, ocurren de forma independiente en cada bit; es decir, si \(p\) es la probabilidad de un error en un bit y \(q\) es la probabilidad de error en otro bit, entonces la probabilidad de errores en ambos bits al mismo tiempo, es \(pq\text{.}\) También supondremos que una \(n\)-tupla recibida se decodificará en la palabra del código que esté más cerca; es decir, suponemos que el receptor usa decodificación de probabilidad máxima. 3 Esta sección requiere conocimientos de probabilidad, pero puede saltarse sin pérdida de continuidad.
Figura8.6Canal binario simétrico
Un canal binario simétrico es un modelo que consiste de un transmisor capaz de enviar una señal binaria, ya sea un 0 o un 1, junto a un receptor. Sea \(p\) la probabilidad de que la señal se recibe correctamente. Entonces \(q = 1 - p\) es la probabilidad de recepción incorrecta. Si se envía un 1, entonces la probabilidad de recibir un 1 es \(p\) y la probabilidad de recibir un 0 es \(q\) (Figura 8.6). La probabilidad de que no ocurra ningún error durante la transmisión de una palabra binaria del código de largo \(n\) es \(p^{n}\text{.}\) Por ejemplo, si \(p=0.999\) y se envía un mensaje consistente de 10,000 bits, entonces la probabilidad de una transmisión perfecta es
Si una \(n\)-tupla binaria \((x_{1}, \ldots, x_{n})\) es transmitida por un canal binario simétrico con probabilidad \(p\) de que no ha ocurrido error en cada coordenada, entonces la probabilidad de que no haya errores en exactamente \(k\) coordenadas es
Fijemos \(k\) coordenadas diferentes. Calculemos primero la probabilidad de que un error ha ocurrido en este conjunto fijo de coordenadas. La probabilidad de que haya ocurrido un error en una en particular de estas \(k\) coordenadas es \(q\text{;}\) la probabilidad de que ningún error haya ocurrido en una de las restantes \(n-k\) coordenadas es \(p\text{.}\) La probabilidad de cada una de estos \(n\) eventos independientes es \(q^{k}p^{n-k}\text{.}\) El número posible de patrones de error con exactamente \(k\) errores es igual a
el número de combinaciones de \(k\) cosas elegidas entre un total de \(n\text{.}\) Cada uno de estos patrones de error tiene probabilidad \(q^{k}p^{n-k}\) de ocurrir; luego, la probabilidad de todos estos patrones de error es
Si vamos a desarrollar códigos eficientes para detectar y corregir errores, necesitaremos herramientas matemáticas más sofisticadas. La teoría de grupos permitirá métodos más rápidos y eficientes para codificar y decodificar mensajes. Un código es un código de bloque \((n, m)\) si la información que se codificará se puede dividir en bloques de \(m\) dígitos binarios, cada uno de los cuales puede ser codificado en \(n\) dígitos binarios. Más específicamente, un código de bloque \((n, m)\) consiste de una función codificadora
Una palabra del código es cualquier elemento en la imagen de \(E\text{.}\) También requerimos que \(E\) sea 1-1 de manera que dos bloques de información no sean codificados en la misma palabra del código.
Ejemplo8.9
El código de paridad desarrollado para detectar errores individuales en caracteres ASCII es un código de bloque \((8,7)\text{.}\) La función codificadora es
donde \(x_8 = x_7 + x_6 + \cdots + x_1\) con la suma en \({\mathbb Z}_2\text{.}\)
Sean \({\mathbf x} = (x_1, \ldots, x_n)\) y \({\mathbf y} = (y_1, \ldots, y_n)\) \(n\)-tuplas binarias. La distancia de Hamming o distancia, \(d({\mathbf x}, {\mathbf y})\text{,}\) entre \({\mathbf x}\) e \({\mathbf y}\) es el número de bits en que \({\mathbf x}\) e \({\mathbf y}\) difieren. La distancia entre dos palabras del código es el mínimo número de errores de transmisión necesarios para transformar una de las palabras en la otra. La distancia mínima para un código, \(d_{\min}\text{,}\) es el mínimo de todas las distancias \(d({\mathbf x}, {\mathbf y})\text{,}\) donde \({\mathbf x}\) e \({\mathbf y}\) son palabras distintas del código. El peso, \(w({\mathbf x})\text{,}\) de una palabra de un código binario \({\mathbf x}\) es el número de unos en \({\mathbf x}\text{.}\) Claramente, \(w({\mathbf x}) = d({\mathbf x}, {\mathbf 0})\text{,}\) donde \({\mathbf 0} = (00 \cdots 0)\text{.}\)
Ejemplo8.10
Sean \({\mathbf x} = (10101)\text{,}\) \({\mathbf y} = (11010)\text{,}\) y \({\mathbf z} = (00011)\) todas las palabras en un código \(C\text{.}\) Entonces tenemos las siguientes distancias de Hamming:
La siguiente proposición lista algunas propiedades básicas sobre el peso de una palabra del código y la distancia entre dos palabras del código. La demostración se deja como ejercicio.
Proposición8.11
Sean \({\mathbf x}\text{,}\) \({\mathbf y}\text{,}\) y \({\mathbf z}\) \(n\)-tuplas binarias. Entonces
Los pesos en un código particular son usualmente mucho más fáciles de calcular que las distancias de Hamming entre todas las palabras del código. Si un código se construye cuidadosamente, podemos sacar provecho de este hecho.
Supongamos que \({\mathbf x} = (1101)\) e \({\mathbf y} = (1100)\) son palabras en algún código. Si transmitimos (1101) y un error ocurre en el bit de más a la derecha, entonces se recibirá (1100). Como (1100) es una palabra del código, el decodificador decodificará (1100) como el mensaje transmitido. Este código claramente no es muy apropiado para la detección de errores. El problema es que \(d({\mathbf x}, {\mathbf y}) = 1\text{.}\) Si \({\mathbf x} = (1100)\) e \({\mathbf y} = (1010)\) son palabras del código, entonces \(d({\mathbf x}, {\mathbf y}) = 2\text{.}\) Si \({\mathbf x}\) se transmite y ocurre un solo error, entonces \({\mathbf y}\) nunca puede ser recibido. La Tabla 8.12 entrega las distancias entre todas las palabras del código de 4-bits en que los primeros tres bits son de información y el cuarto es un bit de control de paridad. Podemos ver que la distancia mínima acá es 2; luego, el código es apto como código de detección de un error.
0000
0011
0101
0110
1001
1010
1100
1111
0000
0
2
2
2
2
2
2
4
0011
2
0
2
2
2
2
4
2
0101
2
2
0
2
2
4
2
2
0110
2
2
2
0
4
2
2
2
1001
2
2
2
4
0
2
2
2
1010
2
2
4
2
2
0
2
2
1100
2
4
2
2
2
2
0
2
1111
4
2
2
2
2
2
2
0
Cuadro8.12Distancias entre palabras de código de 4-bit
Para determinar exactamente cuáles son las capacidades de detección y corrección de errores de un código, debemos analizar la distancia mínima para el código. Sean \({\mathbf x}\) e \({\mathbf y}\) palabras del código. Si \(d({\mathbf x}, {\mathbf y}) = 1\) y ocurre un error donde difieren \({\mathbf x}\) e \({\mathbf y}\text{,}\) entonces \({\mathbf x}\) se transforma en \({\mathbf y}\text{.}\) La palabra recibida es \({\mathbf y}\) y no se produce ningún mensaje de error. Ahora supongamos que \(d({\mathbf x}, {\mathbf y}) = 2\text{.}\) Entonces un único error no puede transformar \({\mathbf x}\) en \({\mathbf y}\text{.}\) Por lo tanto, si \(d_{\min} = 2\text{,}\) tenemos la habilidad de detectar errores únicos. Pero, supongamos que \(d({\mathbf x}, {\mathbf y}) = 2\text{,}\) \({\mathbf y}\) es enviado, y se recibe una palabra \({\mathbf z}\) que no está en el código tal que
Entonces el decodificador no puede decidir entre \({\mathbf x}\) e \({\mathbf y}\text{.}\) Si bien estamos concientes de que se cometió un error, no sabemos cuál fue ese error.
Supongamos que \(d_{\min} \geq 3\text{.}\) Entonces el algoritmo de decodificación de máxima probabilidad corrige todos los errores únicos. Comenzando con una palabra \({\mathbf x}\) del código, un error de un único bit en la transmisión da \({\mathbf y}\) con \(d({\mathbf x}, {\mathbf y}) = 1\text{,}\) pero \(d({\mathbf z}, {\mathbf y}) \geq 2\) para cualquier otra palabra \({\mathbf z} \neq {\mathbf x}\) del código. Si no necesitamos corregir errores, entonces podemos detectar más de un error cuando un código tiene distancia mínima mayor o igual a 3.
Teorema8.13
Sea \(C\) un código con \(d_{\min} = 2n + 1\text{.}\) Entonces \(C\) puede corregir cualquiera \(n\) o menos errores. Alternativamente, \(2n\) o menos errores cualquiera pueden ser detectados con \(C\text{.}\)
Supongamos que se envía una palabra \({\mathbf x}\) del código y que se recibe la palabra \({\mathbf y}\) con a lo más \(n\) errores. Entonces \(d( {\mathbf x}, {\mathbf y}) \leq n\text{.}\) Si \({\mathbf z}\) es cualquier palabra del código distinta de \({\mathbf x}\text{,}\) entonces
Luego, \(d({\mathbf y}, {\mathbf z} ) \geq n+1\) e \({\mathbf y}\) será decodificada correctamente como \({\mathbf x}\text{.}\) Ahora supongamos que se transmite \({\mathbf x}\) recibiéndose \({\mathbf y}\) y que al menos uno pero no más de \(2n\) errores han ocurrido. Entonces \(1 \leq d( {\mathbf x}, {\mathbf y} ) \leq 2n\text{.}\) Como la distancia mínima entre palabras del código es \(2n +1\text{,}\) \({\mathbf y}\) no puede ser una palabra del código. Así, el código puede detectar entre hasta \(2n\) errores.
Ejemplo8.14
En la Tabla 8.15, las palabras \({\mathbf c}_1 = (00000)\text{,}\) \({\mathbf c}_2 = (00111)\text{,}\) \({\mathbf c}_3 = (11100)\text{,}\) y \({\mathbf c}_4 = (11011)\) determinan un código corrector de un error.
00000
00111
11100
11011
00000
0
3
3
4
00111
3
0
4
3
11100
3
4
0
3
11011
4
3
3
0
Cuadro8.15Distancias de Hamming para un código corrector de errores
La teoría moderna de códigos comenzó en 1948 con la publicación de C. Shannon, titulada “A Mathematical Theory of Information” [7]. En su artículo, Shannon ofreció un ejemplo de un código algebraico, y el Teorema de Shannon estableció precisamente qué tan bueno puede llegar a ser un código. Richard Hamming comenzó a trabajar con códigos lineales en Bell Labs a finales de los 1940s y principios de los 1950s después de sufrir la frustración de que los programas que corría no eran capaces de recuperarse de simples errores generados por ruido. La teoría de códigos ha crecido tremendamente en las décadas siguientes a estos trabajos. The Theory of Error-Correcting Codes, de MacWilliams y Sloane [5], publicado en 1977, ya contenía más de 1500 citas. Códigos lineales (códigos de bloque \((32, 6)\) de Reed-Muller) fueron usados en las sondas espaciales Mariner de la NASA. Sondas espaciales posteriores como los Voyager han usado los llamados códigos de convolución. Actualmente, hay investigación activa respecto a códigos Goppa, que dependen fuertemente de geometría algebraica.
