PROFILPELAJAR.COM

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

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 textual.

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 solo 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.

Historia

En la antigüedad clásica, los copistas de la Biblia hebrea eran pagados por su trabajo según el número de líneas de verso. Como los libros en prosa de la Biblia casi nunca se escribieron en puntadas, los copistas, para estimar la cantidad de trabajo, tenían que contar las letras.^[2] Esto también ayudó a garantizar la precisión en la transmisión del texto con la producción de copias posteriores.^[3]^[4] Entre los siglos VII y X d. C., un grupo de escribas judíos formalizó y amplió esto para crear la Masora Numérica para garantizar una reproducción precisa del texto sagrado. Incluía conteos del número de palabras en una línea, sección, libro y grupos de libros, anotando el punto medio de un libro, estadísticas de uso de palabras y comentarios.^[2] Los estándares se volvieron tales que una desviación incluso en una sola letra en un rollo de la Torá se consideraba inaceptable.^[5] La efectividad de su método de corrección de errores fue verificada por la precisión de la copia a través de los siglos demostrada por el descubrimiento de los Pergaminos del Mar Muerto en 1947–1956, que datan de c. 150 a. C.-75 d. C..^[6]

El desarrollo moderno de los códigos de corrección de errores se atribuye a Richard Hamming en 1947.^[7] Una descripción del código de Hamming apareció en A Mathematical Theory of Communication de Claude Shannon^[8] y fue generalizado rápidamente por J. J. Golay.^[9]

Principios

Todos los esquemas de detección y corrección de errores agregan algo de redundancia (es decir, algunos datos adicionales) a un mensaje, que los receptores pueden usar para verificar la consistencia del mensaje entregado y para recuperar datos que han sido enviados que pueden perderse. Los esquemas de detección y corrección de errores pueden ser sistemáticos o no sistemáticos. En un esquema sistemático, el transmisor envía los datos originales (sin errores) y adjunta un número fijo de "bits de verificación" (o "datos de paridad"), que se derivan de los bits de datos mediante algún algoritmo de codificación. Si se requiere detección de errores, un receptor puede simplemente aplicar el mismo algoritmo a los bits de datos recibidos y comparar su salida con los bits de verificación recibidos; si los valores no coinciden, se ha producido un error en algún momento durante la transmisión. Si se requiere corrección de errores, un receptor puede aplicar el algoritmo de decodificación a los bits de datos recibidos y a los bits de verificación recibidos para recuperar los datos originales sin errores. En un sistema que utiliza un código no sistemático, el mensaje original se transforma en un mensaje codificado que lleva la misma información y que tiene al menos tantos bits como el mensaje original.

Un buen rendimiento de control de errores requiere que el esquema se seleccione en función de las características del canal de comunicación. Los modelos de canal comunes incluyen modelos sin memoria donde los errores ocurren aleatoriamente y con cierta probabilidad, y modelos dinámicos donde los errores ocurren principalmente en ráfagas. En consecuencia, los códigos de detección y corrección de errores pueden distinguirse generalmente entre "detección/corrección de errores aleatorios" y "detección/corrección de errores en ráfagas". Algunos códigos también pueden ser adecuados para una combinación de errores aleatorios y errores de ráfaga.

Si las características del canal no pueden determinarse o son muy variables, se puede combinar un esquema de detección de errores con un sistema para retransmisiones de datos erróneos. Esto se conoce como solicitud de repetición automática (ARQ) y se usa principalmente en Internet. Un enfoque alternativo para el control de errores es solicitud de repetición automática híbrida (HARQ), que es una combinación de ARQ y codificación de corrección de errores.

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: $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:

Añade tantos ceros por la derecha al mensaje original como el grado del polinomio generador
Divide el mensaje con los ceros incluidos entre el polinomio generador
El resto que se obtiene de la división se suma al mensaje con los ceros incluidos
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:  $x^{4}+x+1$ 

Operaciones:

1.º Obtener el polinomio equivalente al mensaje:  $x^{6}+x^{5}+x^{3}+1$ 

2.º Multiplicar el mensaje por  $x^{4}$  (añadir 4 ceros por la derecha):  $x^{10}+x^{9}+x^{7}+x^{4}$ 

3.º Dividir en binario el mensaje por el polinomio generador y sacar el resto:  $x^{2}+1$ 

4.º Concatenar el mensaje con el resto (en módulo 2 también):  $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 solo 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 $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:  $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

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:

000001
000001
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.

Aplicaciones

Las aplicaciones que requieren baja latencia (como conversaciones telefónicas) no pueden usar la solicitud de repetición automática (ARQ); deben usar corrección de errores hacia adelante (FEC). Cuando un sistema ARQ descubre un error y lo retransmite, los datos reenviados llegarán demasiado tarde para poder utilizarse.

Las aplicaciones en las que el transmisor olvida inmediatamente la información tan pronto como se envía (como la mayoría de las cámaras de televisión) no pueden usar ARQ; deben usar FEC porque cuando ocurre un error, los datos originales ya no están disponibles.

Las aplicaciones que usan ARQ deben tener un canal de retorno; las aplicaciones que no tienen canal de retorno no pueden usar ARQ.

Las aplicaciones que requieren tasas de error extremadamente bajas (como las transferencias de dinero digital) deben usar ARQ debido a la posibilidad de errores incorregibles con FEC.

La ingeniería de confiabilidad e inspección también hace uso de la teoría de los códigos de corrección de errores.^[10]

Internet

En una pila típica TCP/IP, el control de errores se realiza en varios niveles:

Cada trama Ethernet utiliza la detección de errores CRC-32. Las tramas con errores detectados son descartadas por el hardware del receptor.
El encabezado IPv4 contiene una suma de control que protege el contenido del encabezado. Los paquetes con sumas de verificación incorrectas se descartan dentro de la red o en el receptor.
Se omitió la suma de verificación del encabezado IPv6 para minimizar los costos de procesamiento en el enrutamiento de red y porque se supone que la tecnología actual de capa de enlace proporciona suficiente detección de errores (véase también RFC 3819).
UDP tiene una suma de verificación opcional que cubre la carga útil y la información de direccionamiento en los encabezados UDP e IP. Los paquetes con sumas de verificación incorrectas son descartados por la pila de red. La suma de comprobación es opcional en IPv4 y obligatoria en IPv6. Cuando se omite, se supone que la capa de enlace de datos proporciona el nivel deseado de protección contra errores.
TCP proporciona una suma de verificación para proteger la carga útil y la información de direccionamiento en los encabezados TCP e IP. Los paquetes con sumas de verificación incorrectas son descartados por la pila de la red y finalmente se retransmiten usando ARQ, ya sea explícitamente (como a través de apretón de manos de tres vías) o implícitamente debido a un tiempo de espera.

Telecomunicaciones en el espacio profundo

El desarrollo de los códigos de corrección de errores estuvo estrechamente ligado a la historia de las misiones al espacio profundo, debido a la extrema dilución de la potencia de la señal en distancias interplanetarias y a la limitada disponibilidad de energía a bordo de las sondas espaciales. Mientras que las primeras misiones enviaban sus datos sin codificar, a partir de 1968 se implementó la corrección digital de errores en forma de códigos convolucionales (descodificados de forma subóptima) y códigos Reed-Muller.^[11] El código Reed-Muller se adaptaba bien al ruido al que estaba sometida la nave espacial (aproximadamente coincidente con una curva de campana), y se implementó para la nave espacial Mariner y se utilizó en las misiones entre 1969 y 1977.

Las misiones Voyager 1 y Voyager 2, que comenzaron en 1977, se diseñaron para proporcionar imágenes en color e información científica de Júpiter y Saturno,.^[12] lo que aumentó los requisitos de codificación, por lo que las naves se apoyaron en códigos convolucionales (descodificados óptimamente por Viterbi) que podían concatenarse con un código Golay exterior (24,12,8). La nave Voyager 2 soportaba además una implementación de un código Reed-Solomon. El código Reed-Solomon-Viterbi (RSV) concatenado permitía una corrección de errores muy potente y posibilitó el viaje prolongado de la nave espacial a Urano y Neptuno. Tras la actualización de los sistemas ECC en 1989, ambas naves utilizaron el código RSV V2.

El Comité Consultivo de Sistemas de Datos Espaciales recomienda actualmente el uso de códigos de corrección de errores con un rendimiento similar al código RSV de la Voyager 2 como mínimo. Los códigos concatenados están cayendo cada vez más en desuso en las misiones espaciales y son sustituidos por códigos más potentes, como los códigos Turbo o los códigos LDPC.

Los diferentes tipos de misiones espaciales y orbitales que se llevan a cabo sugieren que intentar encontrar un sistema de corrección de errores que sirva para todo será un problema constante. En las misiones cercanas a la Tierra, la naturaleza del ruido en el canal de comunicación es diferente de la que experimenta una nave espacial en una misión interplanetaria. Además, a medida que aumenta la distancia entre la nave y la Tierra, el problema de la corrección del ruido se hace más difícil.

Radiodifusión por satélite

La demanda de ancho de banda de transpondedor por satélite sigue creciendo, impulsada por el deseo de emitir televisión (incluidos nuevos canales y televisión de alta definición) y datos IP. La disponibilidad de transpondedores y las restricciones de ancho de banda han limitado este crecimiento. La capacidad del transpondedor viene determinada por el esquema de modulación seleccionado y la proporción de capacidad consumida por la FEC (Corrección de errores hacia adelante).

Almacenamiento de datos

Los códigos de detección y corrección de errores se utilizan a menudo para mejorar la fiabilidad de los soportes de almacenamiento de datos.^[13] En 1951, la primera cinta magnética de almacenamiento de datos contaba con una pista de paridad capaz de detectar errores de un solo bit. El código rectangular óptimo utilizado en las cintas de grabación codificadas en grupo no sólo detecta, sino que también corrige los errores de un solo bit. Algunos formatos de archivo, sobre todo los de archivo, incluyen una suma de comprobación (casi siempre CRC32) para detectar la corrupción y el truncamiento y pueden emplear archivos de redundancia o paridad para recuperar porciones de datos dañados. Los códigos Reed-Solomon se utilizan en discos compactos para corregir errores causados por arañazos.

Los discos duros modernos utilizan códigos Reed-Solomon para detectar y corregir errores menores en la lectura de sectores, y para recuperar datos corruptos de sectores que fallan y almacenarlos en los sectores de reserva.^[14] Los sistemas RAID utilizan diversas técnicas de corrección de errores para recuperar datos cuando un disco duro falla por completo. Los sistemas de archivos como ZFS o Btrfs, así como algunas implementaciones RAID, soportan la limpieza de datos y el resilvering, lo que permite detectar bloques defectuosos y (con suerte) recuperarlos antes de que se utilicen.^[15] Los datos recuperados pueden reescribirse exactamente en la misma ubicación física, en bloques de repuesto en la misma pieza de hardware, o los datos pueden reescribirse en hardware de repuesto.

Memoria con corrección de errores

Las memorias dinámicas de acceso aleatorio (DRAM) pueden ofrecer una mayor protección frente a los errores blandos mediante códigos de corrección de errores. Este tipo de memoria con corrección de errores, conocida como memoria protegida ECC o EDAC, es especialmente deseable para aplicaciones de misión crítica, como la informática científica, financiera, médica, etc., así como para aplicaciones extraterrestres debido al aumento de la radiación en el espacio.

Los controladores de memoria con corrección de errores utilizan tradicionalmente códigos Hamming, aunque algunos emplean redundancia modular triple. El intercalado permite distribuir el efecto de un solo rayo cósmico que pueda alterar varios bits físicamente vecinos entre varias palabras, asociando los bits vecinos a palabras diferentes. Siempre que una perturbación de evento único (SEU) no supere el umbral de error (por ejemplo, un error único) en una palabra concreta entre accesos, puede corregirse (por ejemplo, mediante un código de corrección de errores de un solo bit), y puede mantenerse la ilusión de un sistema de memoria sin errores.^[16]

Además de las funciones de hardware necesarias para el funcionamiento de la memoria ECC, los sistemas operativos suelen incluir funciones de notificación relacionadas que se utilizan para avisar cuando los errores de software se recuperan de forma transparente. Un ejemplo es el subsistema EDAC del kernel de Linux (anteriormente conocido como Bluesmoke), que recopila los datos de los componentes habilitados para la comprobación de errores dentro de un sistema informático; además de recopilar y notificar los eventos relacionados con la memoria ECC, también admite otros errores de suma de comprobación, incluidos los detectados en el bus PCI.^[17]^[18]^[19] Algunos sistemas[especificar] también admiten la depuración de memoria para detectar y corregir errores antes de que sean irrecuperables.

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

Véase también

Referencias

↑ G. J. Simmons, "A survey of Information Authentication". Contemporary Cryptology, The science of information integrity, ed. GJ Simmons, IEEE Press, New York, (1992)
↑ ^a ^b «Masorah». Jewish Encyclopedia.
↑ Pratico, Gary D.; Pelt, Miles V. Van (2009). Basics of Biblical Hebrew Grammar: Second Edition. Zondervan. ISBN 978-0-310-55882-8.
↑ Mounce, William D. (2007). Greek for the Rest of Us: Using Greek Tools Without Mastering Biblical Languages. Zondervan. p. 289. ISBN 978-0-310-28289-1.
↑ Mishneh Torah, Tefillin, Mezuzah, and Sefer Torah, 1:2. Example English translation: Eliyahu Touger. The Rambam's Mishneh Torah. Moznaim Publishing Corporation.
↑ Brian M. Fagan (5 de diciembre de 1996). «Dead Sea Scrolls». The Oxford Companion to Archaeology. Oxford University Press. ISBN 0195076184.
↑ Thompson, Thomas M. (1983), From Error-Correcting Codes through Sphere Packings to Simple Groups, The Carus Mathematical Monographs (#21), The Mathematical Association of America, p. vii, ISBN 0-88385-023-0 .
↑ Shannon, C.E. (1948), «A Mathematical Theory of Communication», Bell System Technical Journal 27 (3): 379-423, PMID 9230594, doi:10.1002/j.1538-7305.1948.tb01338.x, hdl:10338.dmlcz/101429 .
↑ Golay, Marcel J. E. (1949), «Notes on Digital Coding», Proc.I.R.E. (I.E.E.E.) 37: 657 .
↑ Ben-Gal I.; Herer Y.; Raz T. (2003). «Self-correcting inspection procedure under inspection errors». IIE Transactions (IIE Transactions on Quality and Reliability, 34(6), pp. 529-540.). Archivado desde el original el 13 de octubre de 2013. Consultado el 10 de enero de 2014.
↑ K. Andrews et al., The Development of Turbo and LDPC Codes for Deep-Space Applications, Proceedings of the IEEE, Vol. 95, No. 11, Nov. 2007.
↑ Huffman, William Cary; Pless, Vera S. (2003). Fundamentals of Error-Correcting Codes. Cambridge University Press. ISBN 978-0-521-78280-7. (requiere registro).
↑ Kurtas, Erozan M.; Vasic, Bane (3 de octubre de 2018). Advanced Error Control Techniques for Data Storage Systems (en inglés). CRC Press. ISBN 978-1-4200-3649-7.
↑ Scott A. Moulton. «My Hard Drive Died». Archivado desde el original el 2 de febrero de 2008.
↑ Qiao, Zhi; Fu, Song; Chen, Hsing-Bung; Settlemyer, Bradley (2019). «Building Reliable High-Performance Storage Systems: An Empirical and Analytical Study». 2019 IEEE International Conference on Cluster Computing (CLUSTER): 1-10. ISBN 978-1-7281-4734-5. S2CID 207951690. doi:10.1109/CLUSTER.2019.8891006.
↑ «Using StrongArm SA-1110 in the On-Board Computer of Nanosatellite». Tsinghua Space Center, Tsinghua University, Beijing. Archivado desde el original el 2 de octubre de 2011. Consultado el 16 de febrero de 2009.
↑ Jeff Layton. «Error Detection and Correction». Linux Magazine. Consultado el 12 de agosto de 2014.
↑ «EDAC Project». bluesmoke.sourceforge.net. Consultado el 12 de agosto de 2014.
↑ «Documentation/edac.txt». Linux kernel documentation. kernel.org. 16 de junio de 2014. Archivado desde el original el 5 de septiembre de 2009. Consultado el 12 de agosto de 2014.