Detección y corrección de errores para niños

Para corregir los errores de transmisión introducidos por la atmósfera de la Tierra (izquierda), los científicos de Goddard aplicaron la corrección de errores Reed-Solomon (derecha), que se usa comúnmente en CD y DVD. Los errores típicos incluyen píxeles faltantes (blanco) y señales falsas (negro). La franja blanca indica un breve período en el que se pausó la transmisión.

En el mundo de las matemáticas, la informática y la teoría de la información, la detección y corrección de errores es una práctica muy importante. Ayuda a mantener la información segura y completa cuando se mueve entre diferentes lugares o se guarda en dispositivos. Imagina que es como un sistema de seguridad para tus datos. Un ejemplo temprano de estas ideas se vio en los códigos usados para los telegramas.

¿Qué es la Detección y Corrección de Errores?

¿Por qué ocurren errores en la información?

Cuando las computadoras se comunican, envían mucha información. A veces, esta información viaja por canales que no son perfectos, como las líneas telefónicas. Estos canales pueden tener "ruido" o interferencias externas. Este ruido puede cambiar la información original, causando errores en lo que se transmite.

Por eso, es muy importante asegurarse de que, si ocurren errores, podamos darnos cuenta. Y, si es posible, ¡corregirlos!

¿Cómo se detectan y corrigen los errores?

Para detectar y corregir errores, se añade información extra a los datos que se envían. Esta información extra se llama "redundancia". Piensa en ello como añadir una copia de seguridad o una forma de verificar que todo llegó bien.

Existen dos estrategias principales para manejar estos errores:

• Códigos de corrección de errores: Añaden suficiente información extra para que no solo se detecten los errores, sino que también se puedan arreglar. Es como tener un borrador y una goma de borrar.
• Códigos de detección de errores: Añaden menos información extra. Solo sirven para saber si hay un error. Si se detecta un error, la información se suele pedir de nuevo. Es como saber que algo está mal, pero sin poder arreglarlo directamente.

Si un bloque de información tiene m bits de datos (la información real) y r bits de redundancia (la información extra), el tamaño total del bloque será n. Así, n es igual a m más r.

Un Viaje en el Tiempo: La Historia de la Corrección de Errores

Los primeros guardianes de la información

Hace mucho tiempo, en la antigüedad, los copistas que escribían a mano la Biblia hebrea eran muy cuidadosos. Contaban las letras para asegurarse de que sus copias fueran exactas. Esto era importante para que el texto sagrado no cambiara con el tiempo.

Entre los siglos VII y X, un grupo de escribas judíos, llamados masoretas, hicieron esto aún más formal. Crearon la Masora Numérica. Contaban palabras por línea, sección y libro. Incluso anotaban el punto medio de un libro. Su objetivo era garantizar que cada copia fuera perfecta. ¡Si una sola letra estaba mal, el rollo se consideraba inaceptable! La exactitud de su método se demostró con el descubrimiento de los Pergaminos del Mar Muerto (escritos entre el 150 a.C. y el 75 d.C.), que eran muy parecidos a las copias posteriores.

El nacimiento de los códigos modernos

El desarrollo moderno de los códigos de corrección de errores comenzó en 1947. Richard Hamming fue una figura clave en esto. Poco después, Claude Shannon describió el código de Hamming en su importante obra "Una teoría matemática de la comunicación". Luego, J. J. Golay lo hizo aún más general.

Cómo Funcionan los Códigos de Detección y Corrección

Añadiendo información extra

Todos los sistemas de detección y corrección de errores funcionan añadiendo algo de "redundancia" a un mensaje. Esta redundancia son datos adicionales. El receptor usa estos datos extra para verificar si el mensaje llegó completo y sin cambios. También pueden ayudar a recuperar la información que se perdió o se dañó.

Los sistemas pueden ser "sistemáticos" o "no sistemáticos".

• En un sistema sistemático, el que envía la información manda los datos originales y le añade unos "bits de verificación". Estos bits se calculan con un algoritmo especial. Si el receptor quiere detectar errores, aplica el mismo algoritmo y compara el resultado. Si no coinciden, ¡hay un error! Si necesita corregir errores, usa un algoritmo de decodificación para recuperar los datos originales.
• En un sistema no sistemático, el mensaje original se transforma en un mensaje codificado que contiene la misma información, pero con más bits.

Tipos de errores y canales de comunicación

El buen funcionamiento de un sistema de control de errores depende del tipo de canal de comunicación.

• Algunos canales tienen errores que ocurren al azar, como si fueran "sin memoria".
• Otros canales tienen errores que ocurren en "ráfagas", es decir, muchos errores seguidos.

Por eso, hay códigos para "errores aleatorios" y códigos para "errores en ráfagas". Algunos códigos pueden manejar ambos.

Si no se sabe cómo es el canal o si cambia mucho, se puede combinar la detección de errores con un sistema para pedir que se reenvíen los datos si hay un error. Esto se llama solicitud de repetición automática (ARQ) y se usa mucho en Internet. Otra opción es la solicitud de repetición automática híbrida (HARQ), que mezcla ARQ con la corrección de errores.

Métodos Comunes de Detección de Errores

Paridad simple

Este método es sencillo. Consiste en añadir un bit extra al final de la información que queremos enviar. Este bit nos dice si el número de "unos" (bits con valor 1) en la cadena es par o impar.

• Si el número de "unos" es par, el bit de paridad es 0.
• Si el número de "unos" es impar, el bit de paridad es 1.

Ejemplo: Queremos enviar "1110100". 1. Contamos los "unos": hay 4 "unos". 2. Como 4 es un número par, añadimos un bit de paridad con valor 0. 3. La cadena enviada es "11101000".

El receptor cuenta los "unos" en la parte original del mensaje. Si el resultado coincide con el bit de paridad, ¡no hubo error!

Problemas de este método: Es posible que ocurran errores que no se detecten. Por ejemplo, si dos bits cambian de valor durante la transmisión, el número de "unos" podría seguir siendo el mismo, y el error pasaría desapercibido.

Verificación de Redundancia Cíclica (CRC)

La CRC es un método más avanzado. Se basa en polinomios y es muy bueno para detectar errores. Se usa mucho en redes de área extensa (WAN).

El equipo que envía la información hace lo siguiente: 1. Añade ceros al final del mensaje original. La cantidad de ceros depende del "grado" del polinomio generador. 2. Divide el mensaje (con los ceros) entre el polinomio generador. 3. El "resto" de esta división se suma al mensaje original (con los ceros). 4. El resultado final es lo que se envía.

Estas operaciones suelen hacerse con hardware para que sean muy rápidas.

Ejemplo de obtención del CRC: Datos:

• Mensaje en binario: 1101001
• Polinomio generador: x⁴+x+1

Operaciones: 1. Se obtiene el polinomio equivalente al mensaje: x⁶+x⁵+x³+1 2. Se multiplica el mensaje por x⁴ (se añaden 4 ceros al final): x¹⁰+x⁹+x⁷+x⁴ 3. Se divide el mensaje por el polinomio generador y se obtiene el resto: x²+1 4. Se une el mensaje con el resto: x¹⁰+x⁹+x⁷+x⁴+x²+1 5. Se transmite el mensaje.

El equipo receptor comprueba el código CRC para ver si hay errores: 1. Acuerdan el mismo polinomio generador. 2. Dividen el código recibido entre el polinomio generador. 3. Comprueban el resto: * Si el resto es cero, ¡no hay errores! Se procesa el mensaje. * Si el resto es diferente de cero, ¡hay errores! Se puede pedir que se reenvíe el mensaje o intentar corregirlos.

Este método es muy efectivo y puede detectar:

• Todos los errores simples.
• Todos los errores dobles.
• Todos los errores en posiciones impares de los bits.
• Todos los errores en ráfagas (errores seguidos) con una longitud menor que el grado del polinomio.
• Un porcentaje muy alto de otras ráfagas de errores.

Suma de comprobación

La suma de verificación es un método más simple. Es eficiente para cadenas de información cortas. Por eso, se usa a menudo en partes importantes de los mensajes, como las cabeceras, y se combina con otros métodos.

Funciona así: 1. El mensaje se divide en cadenas de una longitud fija (por ejemplo, 16 bits). 2. Cada cadena se considera un número. 3. Se suman todos estos números. 4. El resultado de la suma, pero con el signo cambiado, se añade al mensaje que se va a enviar.

El receptor solo tiene que sumar todas las cadenas (incluyendo el número añadido). Si el resultado es 0, ¡no hay errores!

Ejemplo: Mensaje: 101001110101 1. Longitud de cada cadena: 3 bits. 2. Dividir el mensaje: 101 001 110 101 3. Asociar cada cadena con un número: 5 1 6 5 4. Sumar los valores y añadir el número con signo cambiado: 5 + 1 + 6 + 5 = 17. Se añade -17. 5. Se envía 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, hay un error.

Este método es más sencillo y se puede implementar fácilmente en software, logrando velocidades de cálculo similares a las de hardware.

Distancia de Hamming

Hipercubo binario de dimensión cuatro.

La Distancia de Hamming es una forma de medir cuántos bits son diferentes entre dos palabras de código. Si queremos detectar d errores en una palabra de n bits, podemos añadir d+1 bits extra al final. Esto hace que la "distancia mínima de Hamming" entre cualquier palabra válida sea de al menos d+1.

Si se recibe una palabra que no coincide con ninguna palabra válida (es decir, su distancia de Hamming es menor o igual a d), se detecta que hay un error. Además, si hay d o menos errores, la palabra nunca se convertirá en una palabra válida, lo que asegura que los errores se detecten correctamente.

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 menor que 2, significa que son incorrectas.

Aplicaciones de la Detección y Corrección de Errores

¿Cuándo usar cada método?

• Las aplicaciones que necesitan ser muy rápidas (como las conversaciones telefónicas) no pueden usar solicitud de repetición automática (ARQ). Si hay un error y se pide reenviar los datos, estos llegarían demasiado tarde. Por eso, deben usar corrección de errores hacia adelante (FEC), que corrige los errores al instante.
• Las aplicaciones donde el emisor "olvida" la información tan pronto como la envía (como la mayoría de las cámaras de televisión) tampoco pueden usar ARQ. Deben usar FEC, porque si ocurre un error, los datos originales ya no están disponibles para ser reenviados.
• Las aplicaciones que usan ARQ necesitan un "canal de retorno" (una forma de que el receptor le diga al emisor que reenvíe los datos). Si no hay canal de retorno, no se puede usar ARQ.
• Las aplicaciones que necesitan tasas de error extremadamente bajas (como las transferencias de dinero digital) deben usar ARQ. Esto se debe a que, aunque FEC es bueno, siempre existe una pequeña posibilidad de errores que no se puedan corregir.

La ingeniería de confiabilidad y la inspección también usan la teoría de los códigos de corrección de errores.

Internet

En Internet, el control de errores se realiza en varios niveles para asegurar que la información llegue correctamente:

• Cada paquete de datos trama Ethernet usa CRC-32 para detectar errores. Los paquetes con errores se descartan.
• El encabezado IPv4 tiene una suma de control para proteger su contenido. Los paquetes con sumas de verificación incorrectas se descartan.
• El encabezado IPv6 no tiene una suma de verificación propia, porque se asume que las capas inferiores ya se encargan de la detección de errores.
• El UDP tiene una suma de verificación opcional que cubre los datos y la información de dirección. Los paquetes con errores se descartan.
• El TCP usa una suma de verificación para proteger los datos y la información de dirección. Los paquetes con errores se descartan y se retransmiten usando ARQ.

Comunicación en el espacio profundo

El desarrollo de los códigos de corrección de errores ha sido clave para las misiones espaciales. Las señales se debilitan mucho en las distancias interplanetarias.

• Las primeras misiones enviaban datos sin codificar.
• A partir de 1968, se usaron códigos de corrección de errores digitales, como los códigos convolucionales y los códigos Reed-Muller. El código Reed-Muller era bueno para el tipo de ruido que afectaba a las naves espaciales. Se usó en las misiones Mariner entre 1969 y 1977.
• Las misiones Voyager 1 y Voyager 2 (desde 1977) necesitaban enviar imágenes a color y mucha información científica. Usaron códigos convolucionales y un código Golay. La Voyager 2 también usó un código Reed-Solomon. La combinación de Reed-Solomon-Viterbi (RSV) permitió una corrección de errores muy potente, haciendo posible que las naves llegaran a Urano y Neptuno.
• Hoy en día, se usan códigos más potentes como los códigos Turbo o los códigos LDPC.

Es un desafío constante encontrar el mejor sistema de corrección de errores para cada misión espacial. El ruido cerca de la Tierra es diferente al que experimenta una nave en el espacio profundo. Además, cuanto más lejos está la nave, más difícil es corregir el ruido.

Radiodifusión por satélite

La demanda de canales de televisión (incluyendo alta definición) y datos por satélite sigue creciendo. La capacidad de los satélites es limitada. La capacidad de un satélite depende del tipo de modulación y de cuánta capacidad se usa para la FEC (Corrección de errores hacia adelante).

Almacenamiento de datos

Los códigos de detección y corrección de errores son muy importantes para que los dispositivos de almacenamiento de datos sean confiables.

• En 1951, las primeras cintas magnéticas ya tenían una pista de paridad para detectar errores.
• Los discos compactos (CD) usan códigos Reed-Solomon para corregir errores causados por arañazos.
• Los discos duros modernos usan códigos Reed-Solomon para detectar y corregir errores pequeños al leer. También para recuperar datos dañados y guardarlos en sectores de repuesto.
• Los sistemas RAID usan varias técnicas para recuperar datos si un disco duro falla por completo.
• Sistemas de archivos como ZFS o Btrfs pueden detectar y (con suerte) recuperar bloques de datos defectuosos antes de que se usen.

Memoria con corrección de errores

Las memorias DRAM (memoria de acceso aleatorio dinámica) pueden protegerse mejor contra errores usando códigos de corrección de errores. Este tipo de memoria, llamada memoria ECC, es muy útil para aplicaciones importantes como la informática científica, financiera o médica. También es crucial para aplicaciones en el espacio, donde hay más radiación.

Los controladores de memoria ECC suelen usar códigos Hamming. El "intercalado" ayuda a distribuir el efecto de un solo rayo cósmico que podría alterar varios bits. Así, si un error no supera un límite, puede corregirse, y el sistema de memoria parece no tener errores.

Los sistemas operativos también suelen avisar cuando se recuperan errores de software de forma transparente. Por ejemplo, el subsistema EDAC del kernel de Linux recopila datos de componentes con comprobación de errores.

Métodos Comunes de Corrección y Detección de Errores

Aquí tienes una lista de algunos métodos importantes:

• Dígito verificador
• FEC (Forward Error Correction)
• Código Binario de Golay
• Código Hamming
• Bit de paridad
• Reed-Solomon

Ver también

• Corrección de errores cuántica
• Recuperación de datos
• Corrupción de datos
• Automatic Repeat Request

Véase también

En inglés: Error detection and correction Facts for Kids