En teoría de la información y 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 al ruido del canal y, por lo tanto, se pueden introducir 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 otros impedimentos 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 libres de errores.
En la antigüedad clásica, a los copistas de la Biblia hebrea se les pagaba por su trabajo de acuerdo con el número de puntos (líneas de verso). Como los libros en prosa de la Biblia casi nunca se escribían en puntos, los copistas, para estimar 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 Masorah numérica para garantizar la 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 central 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 través de los siglos, demostrada por el descubrimiento de los Rollos del Mar Muerto en 1947-1956, que datan de aproximadamente el año 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 generalizado 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 los datos que se ha determinado que están dañados. 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 (libres de errores) y adjunta un número fijo de bits de comprobación (o datos de paridad ), que se derivan de los bits de datos mediante algún algoritmo de codificación. Si se requiere la 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 comprobación recibidos; si los valores no coinciden, se ha producido un error en algún momento durante la transmisión. Si se requiere la corrección de errores, un receptor puede aplicar el algoritmo de descodificación a los bits de datos recibidos y a los bits de comprobación recibidos para recuperar los datos originales libres de 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.
Para que el control de errores tenga un buen rendimiento, es necesario seleccionar el esquema en función de las características del canal de comunicación. Los modelos de canal más comunes incluyen modelos sin memoria , en los que los errores se producen de forma aleatoria y con una cierta probabilidad, y modelos dinámicos, en los que los errores se producen principalmente en ráfagas . En consecuencia, los códigos de detección y corrección de errores se pueden distinguir, en general, 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 en ráfagas.
Si no se pueden determinar las características del canal o si son muy variables, se puede combinar un esquema de detección de errores con un sistema de retransmisión de datos erróneos. Esto se conoce como solicitud de repetición automática (ARQ) y se utiliza principalmente 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 de reconocimiento negativo y tiempos de espera para lograr una transmisión de datos confiable. Un reconocimiento es un mensaje que envía el receptor para indicar que ha recibido correctamente una trama de datos .
Generalmente, 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.
Hay tres tipos de protocolos ARQ: 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 de retorno , lo que genera una posible latencia mayor debido a las retransmisiones y requiere el mantenimiento de buffers y temporizadores para las retransmisiones, lo que en caso de congestión de la red puede generar tensión en el servidor y en 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 combinado con multiplexación como ARQ-M .
La corrección de errores de reenvío (FEC) es un proceso de adición de datos redundantes , como un código de corrección de errores (ECC), a un mensaje para que pueda ser recuperado por un receptor incluso cuando se introducen varios errores (hasta la capacidad del código que se utiliza), ya sea durante el proceso de transmisión o en 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 de reenvío. 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 el almacenamiento confiable en medios como memoria flash , disco duro y RAM . [13]
Los códigos de corrección de errores generalmente se distinguen entre códigos convolucionales y códigos de bloque :
El teorema de Shannon es un teorema importante en la corrección de errores hacia adelante y describe la tasa máxima de información 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 límite superior estricto se expresa en términos de la 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 de origen y n símbolos codificados.
La tasa máxima de código 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 era solo de naturaleza existencial y no mostraba cómo construir códigos que fueran óptimos y tuvieran algoritmos de codificación y decodificación eficientes .
ARQ híbrido es una combinación de ARQ y corrección de errores hacia adelante. Existen dos enfoques básicos: [10]
El último enfoque es particularmente atractivo en un canal de borrado cuando se utiliza un código de borrado sin velocidad .
La detección de errores se realiza más comúnmente utilizando una función hash adecuada (o específicamente, una suma de comprobación , una 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 al recalcular la etiqueta y compararla con la proporcionada.
Existe una amplia variedad de diseños de funciones hash diferentes. Sin embargo, algunos son de uso especialmente extendido debido a su simplicidad o a su idoneidad para detectar ciertos tipos de errores (por ejemplo, el rendimiento de la comprobación de redundancia cíclica para detectar errores de 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 es posible que no proteja contra un ataque de preimagen .
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 para 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 ha producido 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 estaciones de números . [14] [15]
Un bit de paridad es un bit que se agrega a un grupo de bits de origen para garantizar que la cantidad 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 un solo error o cualquier otro número impar (es decir, tres, cinco, etc.) en la salida. Una cantidad 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 añade 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 contenga un solo error. Sin embargo, no se sabrá en qué parte de la palabra se encuentra 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 había un número par o impar de unos en esa posición de bit enviada en el grupo más reciente, se puede determinar la posición exacta del error y corregirlo. Sin embargo, solo se garantiza que este método sea eficaz 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.
La 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 ser anulada mediante una operación de complemento a uno antes de la transmisión para detectar mensajes no intencionales con todos ceros.
Los esquemas de suma de comprobación incluyen bits de paridad, dígitos de verificación y comprobaciones de redundancia longitudinal . Algunos esquemas de suma de comprobación, como el algoritmo de Damm , el algoritmo de Luhn y el algoritmo de Verhoeff , están diseñados específicamente para detectar errores que suelen introducir los seres humanos al escribir o recordar números de identificación.
Una comprobación de redundancia cíclica (CRC) es una función hash no segura diseñada para detectar cambios accidentales en los datos digitales de las redes informáticas. No es adecuada para detectar errores introducidos de forma maliciosa. Se caracteriza por la especificación de un polinomio generador , que se utiliza como divisor en una división larga de polinomios 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 de ráfaga . Los CRC son particularmente fáciles de implementar en hardware y, por lo tanto, se utilizan 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 fuertes 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. Es probable que cualquier modificación de los datos se detecte a través de un valor hash no coincidente. Además, dado un valor hash, normalmente no es factible encontrar algunos datos de entrada (distintos del dado) que produzcan el mismo valor hash. Si un atacante puede cambiar no solo el mensaje sino también el valor hash, entonces se puede usar un hash con clave o un código de autenticación de mensaje (MAC) para mayor seguridad. Sin conocer la clave, no es posible que el atacante calcule fácil o convenientemente el valor hash con clave correcto para un mensaje modificado.
Las firmas digitales pueden brindar garantías sólidas sobre la integridad de los datos, ya sea que los cambios en los datos sean accidentales o introducidos de manera maliciosa. Las firmas digitales son quizás más conocidas por ser parte del protocolo HTTPS para navegar de forma segura por la web.
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 la distancia mínima para la detección de errores puede ser adecuado si se desea un límite estricto en la cantidad mínima de errores que se deben detectar.
Los códigos con una distancia de Hamming mínima d = 2 son casos degenerados de códigos de corrección de errores y pueden utilizarse para detectar errores únicos. El bit de paridad es un ejemplo de un código de detección de errores únicos.
Las aplicaciones que requieren baja latencia (como las conversaciones telefónicas) no pueden utilizar la solicitud de repetición automática (ARQ), sino que deben utilizar la corrección de errores de reenvío (FEC). Cuando un sistema ARQ descubre un error y lo retransmite, los datos reenviados llegan demasiado tarde para poder utilizarse.
Las aplicaciones en las que el transmisor olvida inmediatamente la información tan pronto como la 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 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 transferencias de dinero digital) deben utilizar 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 códigos de corrección de errores. [16]
En una pila TCP/IP típica , el control de errores se realiza en múltiples niveles:
El desarrollo de 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 las 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, la corrección de errores digitales se implementó en forma de códigos convolucionales (descodificados 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 coincidía 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 dio lugar a mayores requisitos de codificación y, por lo tanto, las naves espaciales fueron respaldadas por códigos convolucionales ( decodificados óptimamente 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 Reed-Solomon-Viterbi (RSV) concatenado permitió una corrección de errores muy potente y permitió el viaje extendido de la nave espacial a Urano y Neptuno . Después de las actualizaciones del sistema ECC en 1989, ambas naves utilizaron la codificación V2 RSV.
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 del código RSV de la Voyager 2 como mínimo. Los códigos concatenados están perdiendo popularidad en las misiones espaciales y se están sustituyendo por códigos más potentes, como los códigos Turbo o los códigos LDPC .
Los distintos tipos de misiones espaciales y orbitales que se llevan a cabo sugieren que tratar de encontrar un sistema de corrección de errores que sirva para todos será un problema constante. En las misiones cercanas a la Tierra, la naturaleza del ruido en el canal de comunicación es diferente del 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 para transpondedores satelitales 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 de los transpondedores 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 fiabilidad 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 por grupos no solo detecta sino que también corrige errores de un solo bit. Algunos formatos de archivo , en particular los formatos de archivo , incluyen una suma de comprobación (generalmente 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 las lecturas de sectores, y para recuperar datos dañados 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 limpieza y la resilverización de datos , lo que permite detectar bloques defectuosos y (con suerte) recuperarlos antes de que se utilicen. [21] Los datos recuperados se pueden reescribir exactamente en la misma ubicación física, en bloques de repuesto en otra parte del mismo hardware, o los datos se pueden reescribir en hardware de reemplazo.
La memoria dinámica de acceso aleatorio (DRAM) puede proporcionar una mayor protección contra errores leves al basarse en códigos de corrección de errores. Este tipo de 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 para aplicaciones extraterrestres debido al aumento de la radiación en el espacio.
Los controladores de memoria con corrección de errores tradicionalmente utilizan códigos Hamming , aunque algunos utilizan redundancia modular triple . El entrelazado permite distribuir el efecto de un único rayo cósmico que potencialmente perturba múltiples bits físicamente vecinos en múltiples palabras al asociar bits vecinos a diferentes palabras. Siempre que una perturbación de un solo evento (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 de proporcionar hardware con las características necesarias para que funcione la memoria ECC, los sistemas operativos suelen contener funciones de generación de informes relacionadas que se utilizan para proporcionar notificaciones cuando se recuperan errores de software de forma transparente. Un ejemplo es el subsistema EDAC del núcleo Linux (anteriormente conocido como Bluesmoke ), que recopila los datos de los componentes habilitados para la 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 comprobación, incluidos los detectados en el bus PCI . [23] [24] [25] Algunos sistemas [ especifican ] también admiten la limpieza de memoria para detectar y corregir errores de forma temprana antes de que se vuelvan irrecuperables.