Detección y corrección de errores

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 acuse de recibo y/o acuse de recibo 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 .

Normalmente, cuando el transmisor no recibe la confirmación antes de que se agote el tiempo de espera (es decir, dentro de un plazo 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.

Existen 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 capacidad variable o desconocida , como ocurre en Internet. Sin embargo, ARQ requiere la disponibilidad de un canal de retorno , puede aumentar la latencia debido a las retransmisiones y requiere el mantenimiento de búferes y temporizadores para las retransmisiones, lo que, en caso de congestión de la red , puede sobrecargar 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 combinado con multiplexación como ARQ-M .

La corrección de errores hacia adelante (FEC) es un proceso que añade datos redundantes, como un código de corrección de errores (ECC), a un mensaje para que el receptor pueda recuperarlo incluso cuando se introducen varios errores (hasta el límite de la capacidad del código utilizado), ya sea durante la transmisión o en el almacenamiento. Dado que el receptor no tiene que solicitar al emisor 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 el almacenamiento fiable en medios como memoria flash , disco duro y RAM . ^{[ 13 ]}

Los códigos de corrección de errores se suelen distinguir entre códigos convolucionales y códigos de bloque :

• Los códigos convolucionales se procesan bit a bit. Son especialmente adecuados para su implementación en hardware, y el decodificador Viterbi permite una decodificación óptima .
• Los códigos de bloques se procesan bloque a bloque . Los primeros ejemplos de códigos de bloques son los códigos de repetición , los códigos de Hamming y los códigos de verificación de paridad multidimensionales . Posteriormente surgieron varios códigos eficientes, siendo los códigos de Reed-Solomon los más destacados debido a su uso generalizado actual. 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 fundamental 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 fiable en un canal con una determinada 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 establece 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 codificación sea inferior a la capacidad del canal. La tasa de codificación se define como la fracción k/n de k símbolos fuente y n símbolos codificados.

La tasa de codificación máxima permitida depende del código corrector de errores utilizado y puede ser menor. Esto se debe a que la demostración de Shannon era de naturaleza existencial y no mostraba cómo construir códigos que fueran óptimos y que contaran con algoritmos de codificación y decodificación eficientes .

El ARQ híbrido es una combinación de ARQ y corrección de errores hacia adelante. Hay dos enfoques básicos: ^{[ 10 ]}

• Los mensajes siempre se transmiten con datos de paridad FEC (y redundancia de detección de errores). El receptor decodifica un mensaje utilizando la información de paridad y solicita la retransmisión mediante ARQ solo si los datos de paridad no fueron suficientes para una decodificación exitosa (identificado mediante una comprobación de integridad fallida).
• Los mensajes se transmiten sin datos de paridad (solo con información de detección de errores). Si un receptor detecta un error, solicita información FEC al transmisor mediante ARQ y la utiliza para reconstruir el mensaje original.

Este último enfoque resulta particularmente atractivo en un canal de borrado cuando se utiliza un código de borrado sin tasa .

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 el número de errores detectables, pero puede 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 través de un canal para lograr una comunicación sin errores. Dado un flujo de datos para transmitir, estos 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 recibe como 1010 1011 1011 (donde el primer bloque es diferente de 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 añade a un grupo de bits de origen para asegurar que el número de bits activados (es decir, bits con valor 1) en el resultado sea par o impar. Es un método muy sencillo que permite detectar errores simples o cualquier otro número impar (por ejemplo, tres, cinco, etc.) en la salida. Un número par de bits alterados 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 una secuencia 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 indica si había un número par o impar de unos en esa palabra, se detectará cualquier palabra con un único error. Sin embargo, no se sabrá en qué parte de la palabra se encuentra el error. Si, además, después de cada secuencia de n palabras se envía una suma de paridad, donde cada bit indica si había un número par o impar de unos en esa posición de bit en el grupo más reciente, se puede determinar la posición exacta del error y corregirlo. No obstante, este método solo está garantizado para ser efectivo si no hay más de un 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 verificación de un mensaje es una suma aritmética modular de las palabras clave del mensaje, que tienen una longitud fija (por ejemplo, valores en bytes). Esta suma puede ser negada mediante una operación de complemento a uno antes de la transmisión para detectar mensajes con solo ceros que no se hayan producido intencionadamente.

Los sistemas de suma de verificación incluyen bits de paridad, dígitos de control y comprobaciones de redundancia longitudinal . Algunos sistemas 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 que suelen cometer los 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 datos digitales en redes informáticas. No es adecuada 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 de polinomios sobre un campo finito , tomando los datos de entrada como dividendo . El resto se convierte en el resultado.

Un CRC posee propiedades que lo hacen idóneo para detectar errores en 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 discos duros .

El bit de paridad puede considerarse un caso especial de CRC de 1 bit.

El resultado de una función hash criptográfica , también conocida como resumen de mensaje , ofrece una gran garantía de integridad de los datos, tanto si las modificaciones son accidentales (por ejemplo, debido a errores de transmisión) como si se introducen de forma maliciosa. Cualquier modificación de los datos probablemente se detectará mediante un valor hash incorrecto. Además, dado un valor hash, suele ser imposible encontrar datos de entrada (distintos del proporcionado) que produzcan el mismo valor. Si un atacante puede modificar no solo el mensaje, sino también el valor hash, puede utilizar un hash con clave o un código de autenticación de mensajes (MAC) para mayor seguridad. Sin conocer la clave, al atacante le resulta imposible calcular fácilmente el valor hash correcto para un mensaje modificado.

Las firmas digitales ofrecen una sólida garantía sobre la integridad de los datos, tanto si las modificaciones son accidentales como si se introducen de forma maliciosa. Las firmas digitales son especialmente conocidas por formar parte del protocolo HTTPS, que permite navegar por internet de forma segura.

Cualquier código corrector de errores puede utilizarse 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 clave. El uso de códigos correctores de errores basados ​​en la distancia mínima para la detección de errores puede ser adecuado si se desea establecer un límite estricto en el número mínimo de errores a detectar.

Los códigos con una distancia de Hamming mínima d = 2 son casos degenerados de códigos correctores de errores y pueden utilizarse para detectar errores individuales. El bit de paridad es un ejemplo de código de detección de errores individuales.

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

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

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 atenuació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 (decodificados de forma subóptima) y códigos Reed-Muller . ^{[ 18 ]} El código Reed-Muller se ajustaba bien al ruido al que estaba sujeta la nave espacial (aproximadamente a 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 . ^{[ 19 ]} Esto resultó en mayores requisitos de codificación, y por lo tanto, las naves espaciales fueron soportadas por códigos convolucionales ( decodificados de Viterbi de forma óptima ) que podían concatenarse con un código Golay (24,12,8) externo . La nave Voyager 2 admitió además 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 posibilitó 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 para 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 cayendo en desuso en las misiones espaciales y se están reemplazando por códigos más potentes, como los códigos Turbo o los códigos LDPC .

Los distintos tipos de misiones orbitales y de exploración del espacio profundo sugieren que encontrar un sistema de corrección de errores universal seguirá siendo un problema constante. En las misiones cercanas a la Tierra, la naturaleza del ruido en el canal de comunicación difiere de la que experimenta una nave espacial en una misión interplanetaria. Además, a medida que la nave espacial se aleja de la Tierra, el problema de corregir el ruido se vuelve más complejo.

La demanda de ancho de banda para transpondedores satelitales sigue 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 restringido este crecimiento. La capacidad del transpondedor viene determinada por el esquema de modulación seleccionado y la proporción de capacidad consumida por la corrección de errores hacia adelante (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. ^{[ 20 ]} En 1951, la primera cinta magnética de almacenamiento de datos incluía 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 solo detecta sino que también corrige errores de un solo bit. Algunos formatos de archivo , en particular los formatos de archivo comprimido , incluyen una suma de comprobación (generalmente CRC-32) para detectar corrupción y truncamiento, y pueden emplear archivos de redundancia o paridad para recuperar porciones de datos corruptos. 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 las lecturas de sectores, y para recuperar datos corruptos de sectores defectuosos y almacenarlos en los sectores de reserva. ^{[ 21 ]} 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 , admiten la limpieza y reconstrucción de datos , lo que permite detectar bloques defectuosos y (con suerte) recuperarlos antes de que se utilicen. ^{[ 22 ]} Los datos recuperados pueden reescribirse exactamente en la misma ubicación física, en bloques de reserva en otra parte del mismo hardware, o pueden reescribirse en hardware de reemplazo.

La memoria de acceso aleatorio dinámico (DRAM) puede ofrecer una mayor protección contra errores transitorios gracias al uso de códigos de corrección de errores. Este tipo de memoria, conocida como ECC o memoria protegida por EDAC , resulta especialmente útil para aplicaciones críticas, como la computación científica, las finanzas, la medicina, etc., así como para aplicaciones extraterrestres debido a la mayor radiación en el espacio.

Los controladores de memoria con corrección de errores tradicionalmente utilizan códigos de Hamming , aunque algunos emplean redundancia modular triple . El entrelazado permite distribuir el efecto de un único rayo cósmico que potencialmente perturba múltiples bits físicamente vecinos entre varias palabras, asociando los bits vecinos a diferentes palabras. Siempre que una perturbación por evento único (SEU) no supere el umbral de error (por ejemplo, un solo error) en cualquier palabra particular entre accesos, puede corregirse (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. ^{[ 23 ]}

Además del hardware que proporciona las características necesarias para que funcione la memoria ECC, los sistemas operativos suelen contener funciones de informes relacionadas que se utilizan para proporcionar notificaciones cuando se recuperan errores leves 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 e informar de los eventos relacionados con la memoria ECC, también admite otros errores de suma de comprobación, incluidos los detectados en el bus PCI . ^{[ 24 ] [ 25 ] [ 26 ]} Algunos sistemas también admiten la limpieza de memoria para detectar y corregir errores tempranamente antes de que se vuelvan irrecuperables.