Detección y corrección de errores
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 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 al receptor. Las técnicas de detección de errores permiten detectar tales errores, mientras que la corrección de errores permite la reconstrucción de los datos originales en muchos casos.
Definiciones
Detección de errores es la detección de errores causados por ruido u otras deficiencias durante la transmisión del transmisor al receptor.
Corrección de errores es la detección de errores y la reconstrucción de los datos originales sin errores.
Historia
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 escribieron en puntadas, los copistas, para estimar la cantidad de trabajo, tenían que contar las letras. Esto también ayudó a garantizar la precisión en la transmisión del texto con la producción de copias posteriores. Entre los siglos VII y X EC, un grupo de escribas judíos formalizaron y ampliaron esto para crear la Masorah Numérica para asegurar la 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. Los estándares se volvieron tales que una desviación incluso en una sola letra en un rollo de la Torá se consideraba inaceptable. La efectividad 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 BCE-75 EC.
El desarrollo moderno de los códigos de corrección de errores se atribuye a Richard Hamming en 1947. Una descripción del código de Hamming apareció en Una teoría matemática de la comunicación de Claude Shannon y fue rápidamente generalizado por Marcel J. E. Golay.
Introducción
Todos los esquemas de corrección y detecció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 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 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 método determinista. algoritmo. Si solo 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 verificación recibidos; si los valores no coinciden, se ha producido un error en algún momento durante la transmisión. 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 canales 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 se pueden distinguir 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 se pueden determinar 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.
Tipos de corrección de errores
Hay tres tipos principales de corrección de errores.
Solicitud de repetición automática
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 reconocimiento 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 tiempo predeterminado. número 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 secundario, lo que posiblemente resulte en un aumento de la latencia debido a las retransmisiones y requiere el mantenimiento de búferes 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.
Por ejemplo, ARQ se usa en enlaces de datos de radio de onda corta en forma de ARQ-E, o combinado con multiplexación como ARQ-M.
Corrección de errores hacia adelante
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 haya una cantidad de errores (hasta la capacidad de el código que se está utilizando) se introducen, ya sea durante el proceso de transmisión o en el almacenamiento. Dado que el receptor no tiene que solicitar al remitente la retransmisión de los datos, no se requiere un canal secundario en la corrección de errores hacia adelante. Los códigos de corrección de errores se utilizan en la comunicación de capa inferior, como la red celular, la comunicación de fibra óptica de alta velocidad y Wi-Fi, así como para el almacenamiento confiable en medios como la memoria flash, el disco duro y la RAM.
Los códigos de corrección de errores generalmente se distinguen entre códigos convolucionales y códigos de bloque:
- Códigos conversos se procesan de forma bit-by-bit. Son especialmente adecuados para la implementación en hardware, y el decodificador Viterbi permite una decodificación óptima.
- Bloquear códigos se procesan de forma cuadrada. Los primeros ejemplos de códigos de bloques son códigos de repetición, códigos Hamming y códigos de verificación de paridad multidimensionales. They were followed by a number of efficient codes, Reed–Solomon codes being the most notable due to their current widespread use. Los códigos Turbo y los códigos de verificación de paridad de baja densidad (LDPC) son construcciones relativamente nuevas que pueden proporcionar una eficiencia casi óptima.
El teorema de Shannon es un teorema importante en la corrección de errores de reenvío y describe la tasa de información máxima a la que es posible una comunicación confiable en 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 fuente y n 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 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.
Esquemas híbridos
Hybrid ARQ es una combinación de ARQ y corrección de errores de reenvío. Hay dos enfoques básicos:
- Los mensajes se transmiten siempre con datos de paridad FEC (y redundancia de detección de errores). Un receptor descifra un mensaje usando la información de paridad, y solicita la retransmisión utilizando ARQ solamente si los datos de paridad no eran suficientes para la decodificación exitosa (identificado a través de un cheque de integridad fallido).
- Los mensajes se transmiten sin datos de paridad (sólo con información de detección de errores). Si un receptor detecta un error, solicita información FEC del transmisor utilizando ARQ, y lo utiliza para reconstruir el mensaje original.
Este último enfoque es particularmente atractivo en un canal de borrado cuando se usa un código de borrado sin tarifa.
Esquemas de detección de errores
La mayoría de las veces, la detección de errores se realiza mediante una función hash adecuada (o específicamente, una suma de verificació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 volver a calcular la etiqueta y compararla con la proporcionada.
Existe una gran variedad de diferentes diseños de funciones hash. Sin embargo, algunos son de uso particularmente generalizado 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 de ráfaga).
Codificación de distancia mínima
Un código de corrección de errores aleatorios basado en la 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.
Códigos de repetición
Un código de repetición es un esquema de codificación que repite los bits en 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 – ha ocurrido 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 estaciones de transmisión de números.
Bit de paridad
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 usar 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.
Bits de paridad agregados a cada "palabra" enviadas se denominan comprobaciones de redundancia transversal, mientras que las que se añaden al final de un flujo de "palabras" se denominan comprobaciones de redundancia longitudinal. Por ejemplo, si cada una de una serie de "palabras" tiene un bit de paridad agregado, que muestra si hubo un número par o impar de unos en esa palabra, se detectará cualquier palabra con 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 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 y, en algunos casos, corregir más errores.
También existen otras técnicas de agrupación de bits.
Suma de comprobación
Una suma de control 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 negada por medio de una operación de complemento a uno antes de la transmisión para detectar mensajes involuntarios de todos cero.
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 de Damm, el algoritmo de Luhn y el algoritmo de Verhoeff, están diseñados específicamente para detectar errores comúnmente introducidos por humanos al escribir o recordar números de identificación.
Comprobación de redundancia cíclica
Una comprobació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 malintencionadamente. Se caracteriza por la especificación de un polinomio generador, que se utiliza como divisor en una división polinomial larga sobre un campo finito, tomando los datos de entrada como dividendos. El resto se convierte en el resultado.
Un CRC tiene propiedades que lo hacen adecuado para detectar errores de ráfaga. 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.
Función hash criptográfica
La salida de una función hash criptográfica, también conocida como resumen de mensaje, puede proporcionar garantías sólidas sobre la integridad de los datos, ya sea que los cambios en 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 que no coincida. Además, dado algún valor hash, normalmente no es factible encontrar algunos datos de entrada (que no sean los proporcionados) 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 mensajes (MAC) para mayor seguridad. Sin conocer la clave, no es posible que el atacante calcule fácil o convenientemente el valor hash clave correcto para un mensaje modificado.
Código de corrección de error
Cualquier código de corrección de errores se puede utilizar para la detección de errores. Un código con distancia mínima de Hamming, d, puede detectar hasta d − 1 error 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 el número mínimo de errores a detectar.
Los códigos con distancia de Hamming mínima d = 2 son casos degenerados de códigos de corrección de errores y se pueden usar para detectar errores individuales. El bit de paridad es un ejemplo de un código de detección de un solo error.
Aplicaciones
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 de reenvío (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.
Internet
En una pila típica de TCP/IP, el control de errores se realiza en varios niveles:
- Cada marco Ethernet utiliza la detección de errores CRC-32. Los fragmentos con errores detectados son descartados por el hardware receptor.
- El encabezado IPv4 contiene una suma de comprobación que protege el contenido del encabezado. Los paquetes con sumas de comprobación incorrectas se bajan dentro de la red o en el receptor.
- La suma de comprobación se omitió de la cabecera 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 un chequeo opcional que cubre la carga útil y la información de dirección en los encabezados UDP y IP. Los paquetes con cheques incorrectos son descartados por la pila de red. La suma de comprobación es opcional en IPv4, y se requiere en IPv6. Cuando se omite, se asume la capa de enlace de datos proporciona el nivel deseado de protección de errores.
- TCP proporciona una suma de comprobación para proteger la carga útil y abordar la información en los encabezados TCP y IP. Los paquetes con sumas de comprobación incorrectas son descartados por la pila de red, y eventualmente 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 salida.
Telecomunicaciones en el espacio profundo
El desarrollo de los códigos de corrección de errores estuvo estrechamente relacionado con la historia de las misiones en el espacio profundo debido a la dilución extrema de la potencia de la señal en las distancias interplanetarias y la disponibilidad limitada 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 digital de errores se implementó en forma de códigos convolucionales (descodificados de manera subóptima) y códigos Reed-Muller. El código Reed-Muller se adaptaba bien al ruido al que estaba sujeta la nave espacial (que coincidía aproximadamente con una curva de campana), y se implementó para la nave espacial Mariner y se usó en misiones entre 1969 y 1977.
Las misiones Voyager 1 y Voyager 2, que comenzaron en 1977, se diseñaron para generar imágenes en color e información científica de Júpiter y Saturno. Esto resultó en un aumento de los requisitos de codificación y, por lo tanto, la nave espacial fue compatible con códigos convolucionales (decodificados de manera óptima por Viterbi) que podrí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 embarcaciones utilizaron la codificación V2 RSV.
El Comité Consultivo para Sistemas de Datos Espaciales actualmente recomienda 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 desgracia con las misiones espaciales y son reemplazados por códigos más poderosos 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 tratar de encontrar un sistema de corrección de errores único para todos será un problema constante. Para 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.
Transmisión por satélite
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 restricciones 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.
Almacenamiento de datos
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. Una pista de paridad capaz de detectar errores de un solo bit estaba presente en el primer almacenamiento de datos de 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 dañados. 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 sector y para recuperar datos corruptos de sectores defectuosos y almacenar esos datos en los sectores de repuesto. 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 de RAID, admiten la depuración y la recuperación de datos, lo que permite detectar los bloques defectuosos y (con suerte) recuperarlos antes de que se utilicen. Los datos recuperados se pueden volver a escribir exactamente en la misma ubicación física, en bloques de repuesto en otro lugar en la misma pieza de hardware, o los datos se pueden volver a escribir en el hardware de reemplazo.
Memoria de corrección de errores
La memoria dinámica de acceso aleatorio (DRAM) puede proporcionar una protección más sólida contra errores leves al depender de códigos de corrección de errores. Dicha memoria de corrección de errores, conocida como memoria ECC o protegida por EDAC, es particularmente deseable para aplicaciones de misión crítica, como 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 de corrección de errores tradicionalmente usan códigos Hamming, aunque algunos usan redundancia modular triple. El intercalado permite distribuir el efecto de un solo rayo cósmico que altera potencialmente múltiples bits físicamente vecinos a través de 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 (p. ej., un solo error) en una palabra en particular entre accesos, se puede corregir (p. ej., 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.
Además del hardware que proporciona las funciones 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 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 verificación de errores dentro de un sistema informático; además de recopilar y reportar los eventos relacionados con la memoria ECC, también admite otros errores de suma de verificación, incluidos los detectados en el bus PCI. Algunos sistemas también admiten la limpieza de memoria para detectar y corregir errores antes de que se vuelvan irrecuperables.