En la teoría de la información y la teoría de la codificación con aplicaciones en informática y telecomunicaciones , la detección y corrección de errores ( EDAC ) o el control de errores son técnicas que permiten la entrega confiable de datos digitales a través de canales de comunicación no confiables . Muchos canales de comunicación están sujetos a ruido de canal y, por lo tanto, pueden introducirse errores durante la transmisión desde la fuente a un receptor. Las técnicas de detección de errores permiten detectar dichos errores, mientras que la corrección de errores permite la reconstrucción de los datos originales en muchos casos.
La detección de errores es la detección de errores causados por ruido u otras deficiencias durante la transmisión del transmisor al receptor.
La corrección de errores es la detección de errores y la reconstrucción de los datos originales sin errores.
En la antigüedad clásica, a los copistas de la Biblia hebrea se les pagaba por su trabajo según el número de puntadas (versos). Como los libros en prosa de la Biblia casi nunca se escribían con puntadas, los copistas, para calcular la cantidad de trabajo, tenían que contar las letras. [1] Esto también ayudó a garantizar la precisión en la transmisión del texto con la producción de copias posteriores. [2] [3] 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 recuentos 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. [1] Los estándares llegaron a ser tales que una desviación incluso en una sola letra en un rollo de la Torá se consideraba inaceptable. [4] La eficacia de su método de corrección de errores fue verificada por la precisión de la copia a lo largo de los siglos demostrada por el descubrimiento de los Rollos del Mar Muerto en 1947-1956, que datan de c. 150 a. C.-75 d. C. [5]
El desarrollo moderno de los códigos de corrección de errores se atribuye a Richard Hamming en 1947. [6] Una descripción del código de Hamming apareció en A Mathematical Theory of Communication de Claude Shannon [7] y fue rápidamente generalizada por Marcel JE Golay . [8]
Todos los esquemas de detección y corrección de errores añaden cierta redundancia (es decir, algunos datos adicionales) a un mensaje, que los receptores pueden utilizar para comprobar la coherencia del mensaje entregado y recuperar datos que se ha determinado que están corruptos. 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 común 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 generalmente se pueden distinguir entre detección/corrección de errores aleatorios y detección/corrección de errores en ráfaga . 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 utiliza sobre todo en Internet. Un enfoque alternativo para el control de errores es la solicitud de repetición automática híbrida (HARQ), que es una combinación de ARQ y codificación de corrección de errores.
Hay tres tipos principales de corrección de errores: [9]
La solicitud de repetición automática (ARQ) es un método de control de errores para la transmisión de datos que utiliza códigos de detección de errores, mensajes de reconocimiento y/o reconocimiento negativo y tiempos de espera para lograr una transmisión de datos confiable. Un acuse de recibo es un mensaje enviado por el receptor para indicar que ha recibido correctamente una trama de datos .
Por lo general, cuando el transmisor no recibe el acuse de recibo antes de que se agote el tiempo de espera (es decir, dentro de un período de tiempo razonable después de enviar la trama de datos), retransmite la trama hasta que se recibe correctamente o el error persiste más allá de un número predeterminado de retransmisiones. .
Tres tipos de protocolos ARQ son ARQ de parada y espera , ARQ de retroceso N y ARQ de repetición selectiva .
ARQ es apropiado si el canal de comunicación tiene una capacidad variable o desconocida , como es el caso de Internet. Sin embargo, ARQ requiere la disponibilidad de un canal trasero , lo que produce un posible aumento de la latencia debido a las retransmisiones y requiere el mantenimiento de buffers y temporizadores para las retransmisiones, lo que en el caso de congestión de la red puede ejercer presión sobre el servidor y la capacidad general de la red. [10]
Por ejemplo, ARQ se utiliza en enlaces de datos de radio de onda corta en forma de ARQ-E , o se combina con multiplexación como ARQ-M .
La corrección de errores hacia adelante (FEC) es un proceso de agregar datos redundantes , como un código de corrección de errores (ECC), a un mensaje para que un receptor pueda recuperarlo incluso cuando se cometen varios errores (hasta la capacidad del código). utilizados), ya sea durante el proceso de transmisión o durante el almacenamiento. Dado que el receptor no tiene que pedirle al remitente la retransmisión de los datos, no se requiere un canal de retorno en la corrección de errores hacia adelante. Los códigos de corrección de errores se utilizan en comunicaciones de capa inferior, como redes celulares , comunicaciones de fibra óptica de alta velocidad y Wi-Fi , [11] [12] , así como para almacenamiento confiable en medios como memoria flash , disco duro y RAM . [13]
Los códigos de corrección de errores suelen distinguirse entre códigos convolucionales y códigos de bloque :
El teorema de Shannon es un teorema importante en la corrección directa de errores y describe la velocidad de información máxima a la que es posible una comunicación confiable a través de un canal que tiene una cierta probabilidad de error o relación señal-ruido (SNR). Este estricto límite superior se expresa en términos de capacidad del canal . Más específicamente, el teorema dice que existen códigos tales que al aumentar la longitud de codificación la probabilidad de error en un canal discreto sin memoria puede hacerse arbitrariamente pequeña, siempre que la tasa de código sea menor que la capacidad del canal. La tasa de código se define como la fracción k/n de k símbolos fuente yn símbolos codificados.
La tasa de código máxima real permitida depende del código de corrección de errores utilizado y puede ser menor. Esto se debe a que la prueba de Shannon fue sólo de naturaleza existencial y no mostró cómo construir códigos que sean óptimos y que tengan algoritmos de codificación y decodificación eficientes .
ARQ híbrido es una combinación de ARQ y corrección de errores directa. Hay dos enfoques básicos: [10]
Este último enfoque es particularmente atractivo en un canal de borrado cuando se utiliza un código de borrado sin tasa .
La detección de errores se realiza más comúnmente utilizando una función hash adecuada (o específicamente, una suma de verificación , verificación de redundancia cíclica u otro algoritmo). Una función hash agrega una etiqueta de longitud fija a un mensaje, lo que permite a los receptores verificar el mensaje entregado recalculando la etiqueta y comparándola con la proporcionada.
Existe una gran variedad de diseños diferentes de funciones hash. Sin embargo, algunos son de uso particularmente extendido debido a su simplicidad o su idoneidad para detectar ciertos tipos de errores (por ejemplo, el rendimiento de la verificación de redundancia cíclica en la detección de errores en ráfaga ).
Un código de corrección de errores aleatorios basado en una codificación de distancia mínima puede proporcionar una garantía estricta sobre la cantidad de errores detectables, pero puede no proteger contra un ataque previo a la imagen .
Un código de repetición es un esquema de codificación que repite los bits a lo largo de un canal para lograr una comunicación sin errores. Dado un flujo de datos a transmitir, los datos se dividen en bloques de bits. Cada bloque se transmite un número predeterminado de veces. Por ejemplo, para enviar el patrón de bits 1011 , el bloque de cuatro bits se puede repetir tres veces, produciendo así 1011 1011 1011 . Si este patrón de doce bits se recibió como 1010 1011 1011 (donde el primer bloque es diferente a los otros dos), se produjo un error.
Un código de repetición es muy ineficiente y puede ser susceptible a problemas si el error ocurre exactamente en el mismo lugar para cada grupo (por ejemplo, 1010 1010 1010 en el ejemplo anterior se detectaría como correcto). La ventaja de los códigos de repetición es que son extremadamente simples, y de hecho se utilizan en algunas transmisiones de números a estaciones . [14] [15]
Un bit de paridad es un bit que se agrega a un grupo de bits de origen para garantizar que el número de bits establecidos (es decir, bits con valor 1) en el resultado sea par o impar. Es un esquema muy simple que se puede utilizar para detectar errores únicos o cualquier otro número impar (es decir, tres, cinco, etc.) en la salida. Un número par de bits invertidos hará que el bit de paridad parezca correcto aunque los datos sean erróneos.
Los bits de paridad añadidos a cada palabra enviada se denominan comprobaciones de redundancia transversal , mientras que los añadidos al final de un flujo de palabras se denominan comprobaciones de redundancia longitudinal . Por ejemplo, si a cada una de una serie de palabras de m bits se le agrega un bit de paridad, que muestra si había un número par o impar de unos en esa palabra, se detectará cualquier palabra que tenga un solo error. Sin embargo, no se sabrá en qué parte de la palabra está el error. Si, además, después de cada flujo de n palabras se envía una suma de paridad, cada bit de la cual muestra si hubo un número par o impar de unos en esa posición de bit enviada en el grupo más reciente, la posición exacta del error se puede determinar y corregir el error. Sin embargo, solo se garantiza que este método sea efectivo si no hay más de 1 error en cada grupo de n palabras. Con más bits de corrección de errores, se pueden detectar más errores y, en algunos casos, corregirlos.
También existen otras técnicas de agrupación de bits.
Una suma de comprobación de un mensaje es una suma aritmética modular de palabras de código de mensaje de una longitud de palabra fija (por ejemplo, valores de bytes). La suma puede negarse mediante una operación de complemento a uno antes de la transmisión para detectar mensajes de ceros no intencionados.
Los esquemas de suma de comprobación incluyen bits de paridad, dígitos de control y comprobaciones de redundancia longitudinal . Algunos esquemas de suma de verificación, como el algoritmo Damm , el algoritmo Luhn y el algoritmo Verhoeff , están diseñados específicamente para detectar errores comúnmente introducidos por humanos al escribir o recordar números de identificación.
Una verificación de redundancia cíclica (CRC) es una función hash no segura diseñada para detectar cambios accidentales en datos digitales en redes informáticas. No es adecuado para detectar errores introducidos maliciosamente. Se caracteriza por la especificación de un polinomio generador , que se utiliza como divisor en una división larga del polinomio sobre un campo finito , tomando los datos de entrada como dividendo . El resto se convierte en el resultado.
Un CRC tiene propiedades que lo hacen muy adecuado para detectar errores en ráfagas . Los CRC son particularmente fáciles de implementar en hardware y, por lo tanto, se usan comúnmente en redes informáticas y dispositivos de almacenamiento como unidades de disco duro .
El bit de paridad puede verse como un CRC de 1 bit de caso especial.
La salida de una función hash criptográfica , también conocida como resumen de mensaje , puede proporcionar sólidas garantías sobre la integridad de los datos , ya sea que los cambios de los datos sean accidentales (por ejemplo, debido a errores de transmisión) o introducidos maliciosamente. Cualquier modificación de los datos probablemente se detectará mediante un valor hash que no coincide. Además, dado algún valor hash, normalmente no es factible encontrar algunos datos de entrada (distintos del proporcionado) que produzcan el mismo valor hash. Si un atacante puede cambiar no solo el mensaje sino también el valor hash, entonces se puede utilizar un hash con clave o un código de autenticación de mensaje (MAC) para mayor seguridad. Sin conocer la clave, al atacante no le resulta posible calcular fácil o cómodamente el valor hash clave correcto para un mensaje modificado.
Se puede utilizar cualquier código de corrección de errores para la detección de errores. Un código con una distancia de Hamming mínima , d , puede detectar hasta d − 1 errores en una palabra de código. El uso de códigos de corrección de errores basados en una distancia mínima para la detección de errores puede ser adecuado si se desea un límite estricto en el número mínimo de errores a detectar.
Los códigos con una distancia mínima de Hamming d = 2 son casos degenerados de códigos de corrección de errores y pueden usarse para detectar errores únicos. El bit de paridad es un ejemplo de código de detección de error único.
Las aplicaciones que requieren baja latencia (como conversaciones telefónicas) no pueden utilizar la solicitud de repetición automática (ARQ); deben utilizar la corrección de errores directa (FEC). Cuando un sistema ARQ descubre un error y lo retransmite, los datos reenviados llegarán demasiado tarde para ser utilizables.
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 utilizar ARQ; deben usar FEC porque cuando ocurre un error, los datos originales ya no están disponibles.
Las aplicaciones que utilizan 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 digitales) deben utilizar ARQ debido a la posibilidad de errores incorregibles con FEC.
La ingeniería de fiabilidad e inspección también utiliza la teoría de los códigos de corrección de errores. [dieciséis]
En una pila TCP/IP típica , el control de errores se realiza en varios niveles:
El desarrollo de códigos de corrección de errores estuvo estrechamente relacionado con 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 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, la corrección de errores digitales se implementó en forma de códigos convolucionales (decodificados de manera subóptima) y códigos Reed-Muller . [17] El código Reed-Muller se adaptaba bien al ruido al que estaba sujeta la nave espacial (aproximadamente coincidiendo con una curva de campana ), y se implementó para la nave espacial Mariner y se utilizó en misiones entre 1969 y 1977.
Las misiones Voyager 1 y Voyager 2 , que comenzaron en 1977, fueron diseñadas para proporcionar imágenes en color e información científica de Júpiter y Saturno . [18] Esto resultó en mayores requisitos de codificación y, por lo tanto, la nave espacial estaba respaldada por códigos convolucionales (óptimamente decodificados por Viterbi ) que podían concatenarse con un código Golay externo (24,12,8) . La nave Voyager 2 también admitió una implementación de un código Reed-Solomon . El código concatenado Reed-Solomon-Viterbi (RSV) permitió una corrección de errores muy poderosa y permitió el viaje prolongado de la nave espacial a Urano y Neptuno . Después de las actualizaciones del sistema ECC en 1989, ambas naves utilizaron codificación V2 RSV.
El Comité Consultivo para 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 cada vez menos favorecidos en las misiones espaciales y son reemplazados por códigos más potentes como los códigos Turbo o los códigos LDPC .
Los diferentes tipos de misiones orbitales y al espacio profundo que se llevan a cabo sugieren que tratar de encontrar un sistema de corrección de errores único para todos será un problema constante. Para 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 una nave espacial aumenta su distancia de la Tierra, el problema de corregir el ruido se vuelve más difícil.
La demanda de ancho de banda de transpondedor satelital continúa creciendo, impulsada por el deseo de ofrecer televisión (incluidos nuevos canales y televisión de alta definición ) y datos IP. La disponibilidad de transpondedores y las limitaciones de ancho de banda han limitado este crecimiento. La capacidad del transpondedor está determinada por el esquema de modulación seleccionado y la proporción de capacidad consumida por FEC.
Los códigos de detección y corrección de errores se utilizan a menudo para mejorar la confiabilidad de los medios de almacenamiento de datos. [19] Una pista de paridad capaz de detectar errores de un solo bit estaba presente en el primer almacenamiento de datos en cinta magnética en 1951. El código rectangular óptimo utilizado en cintas de grabación codificadas en grupo no solo detecta sino que también corrige errores de un solo bit. Algunos formatos de archivo , particularmente los formatos de archivo , incluyen una suma de verificación (más a menudo CRC32 ) para detectar corrupción y truncamiento y pueden emplear archivos de redundancia o paridad para recuperar partes de datos corruptos. Los códigos Reed-Solomon se utilizan en discos compactos para corregir errores causados por rayones.
Los discos duros modernos utilizan códigos Reed-Solomon para detectar y corregir errores menores en lecturas de sectores y para recuperar datos corruptos de sectores defectuosos y almacenar esos datos en los sectores de repuesto. [20] Los sistemas RAID utilizan una variedad de 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 , admiten la depuración y recuperación de datos, lo que permite detectar y (con suerte) recuperar bloques defectuosos antes de utilizarlos. [21] Los datos recuperados pueden reescribirse exactamente en la misma ubicación física, para ahorrar bloques en otros lugares de la misma pieza de hardware, o los datos pueden reescribirse en hardware de reemplazo.
La memoria dinámica de acceso aleatorio (DRAM) puede proporcionar una protección más sólida contra errores leves al confiar en códigos de corrección de errores. Esta memoria de corrección de errores, conocida como memoria protegida ECC o EDAC , es particularmente deseable para aplicaciones de misión crítica, como la informática científica, financiera, médica, etc., así como 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 utilizan triple redundancia modular . El entrelazado permite distribuir el efecto de un solo rayo cósmico que potencialmente altera múltiples bits físicamente vecinos en varias palabras al asociar bits vecinos a diferentes palabras. Siempre que un error de evento único (SEU) no exceda el umbral de error (por ejemplo, un solo error) en cualquier palabra en particular entre accesos, se puede corregir (por ejemplo, mediante un código de corrección de errores de un solo bit), y se puede mantener la ilusión de un sistema de memoria libre de errores. [22]
Además del hardware que proporciona las funciones necesarias para que funcione la memoria ECC, los sistemas operativos suelen contener funciones de informes relacionadas que se utilizan para proporcionar notificaciones 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 datos de componentes habilitados para verificación de errores dentro de un sistema informático; Además de recopilar e informar los eventos relacionados con la memoria ECC, también admite otros errores de suma de verificación, incluidos los detectados en el bus PCI . [23] [24] [25] Algunos sistemas [ especifique ] también admiten la depuración de memoria para detectar y corregir errores temprano antes de que se vuelvan irrecuperables.