Detección y corrección de errores

En matemáticas, informática y teoría de la información, la detección y corrección de errores es una importante práctica para el mantenimiento e integridad de los datos a través de diferentes procedimientos y dispositivos como medios de almacenamiento confiables.^[1]​Se considera como precursor de este tipo de tecnologías el Acme Comodity and Phrase Code usado en los telegramas

Para limpiar los errores de transmisión introducidos por la atmósfera de la Tierra (izquierda), los científicos de Goddard aplicaron la corrección de errores Reed-Solomon (derecha), que se usa comúnmente en CD y DVD. Los errores típicos incluyen píxeles faltantes (blanco) y señales falsas (negro). La franja blanca indica un breve período en el que se pausó la transmisión.

Introducción

La comunicación entre varias computadoras produce continuamente un movimiento de datos, generalmente por canales no diseñados para este propósito (línea telefónica), y que introducen un ruido externo que produce errores en la transmisión.

Por lo tanto, debemos asegurarnos que si dicho movimiento causa errores, éstos puedan ser detectados. El método para detectar y corregir errores es incluir en los bloques de datos transmitidos bits adicionales denominados redundancia.

Se han desarrollado dos estrategias básicas para manejar los errores:

• Incluir suficiente información redundante en cada bloque de datos para que se puedan detectar y corregir los bits erróneos. Se utilizan códigos de corrección de errores.

• Incluir sólo la información redundante necesaria en cada bloque de datos para detectar los errores. En este caso el número de bits de redundancia es menor. Se utilizan códigos de detección de errores.

Si consideramos un bloque de datos formado por m bits de datos y r de redundancia, la longitud final del bloque será n, donde n = m + r.

Tipo de códigos detectores

Paridad simple (paridad horizontal)

Consiste en añadir un bit de más a la cadena que queremos enviar, y que nos indicará si el número de unos (bits puestos a 1) es par o es impar. Si es par incluiremos este bit con el valor = 0, y si no es así, lo incluiremos con valor = 1.

Ejemplo de generación de un bit de paridad simple: Queremos enviar la cadena “1110100”: 1º Contamos la cantidad de unos que hay: 4 unos 2º El número de unos es par por tanto añadimos un bit con valor = 0 3º La cadena enviada es 11101000 

El receptor ahora, repite la operación de contar la cantidad de “unos” que hay (menos el último bit) y si coincide, es que no ha habido error.

Problemas de este método:

Hay una alta probabilidad de que se cuelen casos en los que ha habido error, y que el error no sea detectado, como ocurre si se cambian dos números en la transmisión en vez de uno.

Un ejemplo de polinomio generador usado normalmente en las redes WAN es: ${\displaystyle g(x)=x^{16}+x^{12}+x^{5}+1}$ 

Los cálculos que realiza el equipo transmisor para calcular su CRC (Ciclic redundancy Check) son:

1. Añade tantos ceros por la derecha al mensaje original como el grado del polinomio generador
2. Divide el mensaje con los ceros incluidos entre el polinomio generador
3. El resto que se obtiene de la división se suma al mensaje con los ceros incluidos
4. Se envía el resultado obtenido

Estas operaciones generalmente son incorporadas en el hardware para que pueda ser calculado con mayor rapidez, pero en la teoría se utilizan los polinomios para facilitar los cálculos.

Ejemplo de obtención del CRC: Datos: Mensaje codificado en binario: 1101001 Polinomio generador: ${\displaystyle x^{4}+x+1}$  Operaciones: 1º Obtener el polinomio equivalente al mensaje: ${\displaystyle x^{6}+x^{5}+x^{3}+1}$  2º Multiplicar el mensaje por ${\displaystyle x^{4}}$  (añadir 4 ceros por la derecha): ${\displaystyle x^{10}+x^{9}+x^{7}+x^{4}}$  3º Dividir en binario el mensaje por el polinomio generador y sacar el resto: ${\displaystyle x^{2}+1}$  4º Concatenar el mensaje con el resto (en módulo 2 también): ${\displaystyle x^{10}+x^{9}+x^{7}+x^{4}+x^{2}+1}$  5º Transmitir el mensaje 

El equipo receptor debe comprobar el código CRC para detectar si se han producido o no errores.

Ejemplo de los cálculos del receptor: 1º Mediante el protocolo correspondiente acuerdan el polinomio generador 2º Divide el código recibido entre el polinomio generador 3º Comprueba el resto de dicha operación 3.1 Si el resto es cero, no se han producido errores 3.2 Procesar el mensaje 3.1 Si el resto es distinto de cero, significa que se han producido errores 3.2 Reenviar el mensaje 3.2 Intentar corregir los errores mediante los códigos correctores 

En resumen, este método requiere de un polinomio generador que, elegido correctamente, puede llegar a detectar gran cantidad de errores:

• Errores simples: todos
• Errores dobles: todos
• Errores en las posiciones impares de los bits: todos
• Errores en ráfagas con una longitud menor que el grado del polinomio generador: todos
• Otras ráfagas: un porcentaje elevado y cercano al 100%

Suma de comprobación

Artículo principal: Suma de verificación

Es un método sencillo pero eficiente sólo con cadenas de palabras de una longitud pequeña, es por esto que se suele utilizar en cabeceras de tramas importantes u otras cadenas importantes y en combinación con otros métodos.

Funcionalidad: consiste en agrupar el mensaje a transmitir en cadenas de una longitud determinada L no muy grande, de por ejemplo 16 bits. Considerando a cada cadena como un número entero numerado según el sistema de numeración ${\displaystyle 2^{L}-1}$ . A continuación se suma el valor de todas las palabras en las que se divide el mensaje, y se añade el resultado al mensaje a transmitir, pero cambiado de signo.

Con esto, el receptor lo único que tiene que hacer es sumar todas las cadenas, y si el resultado es 0 no hay errores.

Ejemplo: Mensaje 101001110101 1º Acordar la longitud de cada cadena: 3 2º Acordar el sistema de numeración: ${\displaystyle 2^{3}-1=7}$  3º Dividir el mensaje: 101 001 110 101 4º Asociar cada cadena con un entero: 5 1 6 5 5º Sumar todos los valores y añadir el número cambiado de signo: -17 6º Enviar 5 1 6 5 -17 codificado en binario 

El receptor: 1º Suma todos los valores; si la suma es 0, procesa el mensaje; si no, se ha producido un error. 

Este método al ser más sencillo es óptimo para ser implementado en software ya que se puede alcanzar velocidades de cálculo similares a la implementación en hardware

Distancia de Hamming basada en comprobación

 

Hipercubo binario de dimensión cuatro.

Si queremos detectar d bit erróneos en una palabra de n bits, podemos añadir a cada palabra de n bits d+1 bits predeterminados al final, de forma que quede una palabra de n+d+1 bits con una distancia mínima de Hamming de d+1. De esta manera, si uno recibe una palabra de n+d+1 bits que no encaja con ninguna palabra del código (con una distancia de Hamming x <= d+1 la palabra no pertenece al código) detecta correctamente si es una palabra errónea. Aún más, d o menos errores nunca se convertirán en una palabra válida debido a que la distancia de Hamming entre cada palabra válida es de al menos d+1, y tales errores conducen solamente a las palabras inválidas que se detectan correctamente. Dado un conjunto de m*n bits, podemos detectar x <= d bits errores correctamente usando el mismo método en todas las palabras de n bits. De hecho, podemos detectar un máximo de m*d errores si todas las palabras de n bits son transmitidas con un máximo de d errores.

Ejemplo

Palabras a enviar:

1. 000001
2. 000001
3. 000010

Codificadas con distancia mínima de Hamming = 2

000001 0000

000001 0011

000010 1100

Si las palabras recibidas tienen una distancia de Hamming < 2, son palabras incorrectas.

Lista de los métodos de corrección y detección de errores

• Dígito verificador
• FEC (Forward Error Correction)
• Código Binario de Golay
• Código Hamming
• Bit de paridad
• Reed-Solomon

Véase también

• Corrección de errores cuántica
• Recuperación de datos
• Corrupción de datos
• Automatic Repeat Request

Referencias

1. G. J. Simmons, "A survey of Information Authentication". Contemporary Cryptology, The science of information integrity, ed. GJ Simmons, IEEE Press, New York, (1992)

Enlaces externos

• Otros códigos utilizados

•   Datos: Q1062839