Hamming CodeDetección y corrección de errores con ejemplos

Por: Bryce León Bryce León
Hours Actualizado

⚡ Resumen inteligente

El código Hamming es un código lineal de corrección de errores que añade bits de paridad redundantes en posiciones que son potencias de dos, lo que permite al receptor detectar errores de hasta dos bits y corregir automáticamente cualquier error de un solo bit durante la transmisión de datos.

  • 🧭 Propósito: El código Hamming detecta y corrige los errores de transmisión mediante la inserción de bits de paridad que indican la posición exacta de un bit corrupto.
  • 🔢 Fragmentos redundantes: El número de bits de paridad (p) satisface la regla 2^p ≥ n + p + 1, donde n es el número de bits de datos.
  • 📍 Colocación: Los bits de paridad ocupan las posiciones que son potencias de dos (1, 2, 4 y 8), mientras que los bits de datos llenan las posiciones restantes.
  • 🧮 Hamming(7,4): Una forma común codifica cuatro bits de datos en un total de siete bits utilizando tres bits de paridad.
  • 🧯 Limitación: El código Hamming estándar corrige únicamente los errores de un solo bit; un bit de paridad general adicional añade la detección de errores dobles (SECDED).
  • 🤖 Asistencia de IA: Los decodificadores de aprendizaje automático ayudan a detectar canales ruidosos y patrones de error que los códigos fijos por sí solos podrían pasar por alto.
Descubre más

Detección y corrección de errores del código Hamming con bits de paridad

¿Qué es un error?

TransmitLos datos de entrada pueden corromperse durante la comunicación. Es probable que se vean afectados por ruido externo u otras fallas físicas. En tal caso, los datos de entrada no pueden coincidir con los de salida. Esta discrepancia se conoce como "error".

Los errores de datos pueden provocar la pérdida de información importante o confidencial. La mayor parte de la transferencia de datos en los sistemas digitales se realiza mediante la transferencia de bits, e incluso un pequeño cambio en un solo bit puede afectar el rendimiento de todo el sistema. En una secuencia de datos, si un 1 se cambia por un 0, o un 0 por un 1, se denomina "error de bit".

Tipos de errores

Existen principalmente tres tipos de errores de bits que ocurren cuando se producen datos. transmitdel remitente al receptor. El siguiente diagrama ilustra cómo afecta cada tipo a una secuencia de datos:

Diagrama que compara errores de un solo bit, de múltiples bits y en ráfaga en una secuencia de datos binarios.

  • Errores de un solo bit
  • Errores de varios bits
  • Errores de ráfaga

Errores de un solo bit

Un cambio en un solo bit de toda la secuencia de datos se conoce como "error de un solo bit". La ocurrencia de un error de un solo bit no es muy común. Suele ocurrir en sistemas de comunicación paralelos, ya que los datos se transfieren bit a bit en líneas separadas, por lo que existe una mayor probabilidad de que una línea presente ruido mientras que las demás permanecen intactas.

Errores de bits múltiples

Cuando dos o más bits de una secuencia de datos cambian entre transmitCuando el receptor falla, se conoce como un “error de múltiples bits”.

Este tipo de error se produce tanto en redes de comunicación de datos en serie como en paralelo.

Errores de ráfaga

Un cambio en un conjunto de bits consecutivos en una secuencia de datos se conoce como "error de ráfaga". La duración de un error de ráfaga se mide desde el primer bit modificado hasta el último.

¿Qué son la detección y corrección de errores?

En un sistema de comunicación digital, pueden producirse errores durante la transferencia de datos entre dispositivos. Si estos errores no se detectan ni se corrigen, los datos se pierden. Para una comunicación eficaz, los datos deben transferirse con alta precisión, lo cual se logra identificando primero los errores y luego corrigiéndolos.

Detección de errores es un método para encontrar los errores presentes en los datos transmitted de un transmitter a un receptor en un comunicación de datos .

Los códigos de redundancia se utilizan para encontrar estos errores agregando bits adicionales a los datos cuando se produce un error. transmitExtraídos de la fuente. Estos bits adicionales se denominan “códigos de detección de errores”. Los tres tipos más comunes de códigos de detección de errores son:

  • Comprobación de paridad
  • Comprobación de redundancia cíclica (CRC)
  • Verificación de redundancia longitudinal (LRC)

Comprobación de paridad

  • También se le conoce como control de paridad.
  • Proporciona un mecanismo rentable para la detección de errores.
  • En esta técnica, el bit redundante que se añade a cada unidad de datos se conoce como bit de paridad. Se configura de forma que el número total de 1s en la unidad sea par (paridad par) o impar (paridad impar).

Comprobación de redundancia longitudinal

En esta técnica de detección de errores, un bloque de bits se organiza en una tabla. El método LRC calcula un bit de paridad para cada columna, y este conjunto de bits de paridad se envía junto con los datos originales. El bloque de bits de paridad ayuda al receptor a comprobar la redundancia y detectar errores.

Verificación de redundancia cíclica

La comprobación de redundancia cíclica añade una secuencia de bits redundantes al final de la unidad de datos, de modo que la unidad de datos resultante sea exactamente divisible por un segundo número binario predeterminado.

En el destino, los datos entrantes se dividen por el mismo número. Si no hay resto, se considera que la unidad de datos es correcta y se acepta. De lo contrario, indica que la unidad de datos se dañó durante la transmisión y debe rechazarse.

¿Qué es un Hamming? Code?

El código Hamming es un código lineal útil para detectar hasta dos errores de bit inmediatos y corregir errores de un solo bit. La corrección de errores de este tipo suele operar en la capa de enlace de datos, enmarcando los datos y verificando su integridad entre nodos adyacentes.

En el código Hamming, la fuente codifica el mensaje añadiendo bits redundantes. Estos bits redundantes se insertan y generan en posiciones específicas del mensaje para llevar a cabo el proceso de detección y corrección de errores.

Historia de Hamming Code

  • El código Hamming es una técnica creada por RW Hamming para detectar y corregir errores.
  • Se puede aplicar a unidades de datos de cualquier longitud y utiliza la relación entre los bits de datos y los bits de redundancia.
  • Hamming trabajó en el problema de la corrección de errores y desarrolló un conjunto de algoritmos cada vez más potentes.
  • En 1950, publicó el código Hamming, que todavía se utiliza ampliamente hoy en día en aplicaciones como la memoria ECC.

Aplicaciones del método de Hamming Code

Aquí se muestran algunas aplicaciones comunes del código de Hamming:

  • Satélites
  • Memoria del ordenador (memoria RAM ECC)
  • Módems
  • PlasmaCAM
  • Conectores abiertos
  • alambre blindado
  • Procesadores integrados

ARTÍCULOS RELACIONADOS

Ventajas de Hamming Code

  • El código Hamming es eficaz en redes donde los flujos de datos están expuestos a errores de un solo bit.
  • No solo detecta un error de bit, sino que también ayuda a identificar el bit que contiene el error para que pueda corregirse.
  • La facilidad de uso de los códigos de Hamming los hace muy adecuados para la memoria de las computadoras y la corrección de errores individuales.

Desventajas de Hamming Code

  • Se trata de un código de detección y corrección de errores de un solo bit. Si se detectan varios bits erróneos, el resultado puede alterar otro bit que en realidad era correcto, corrompiendo aún más los datos.
  • El algoritmo del código Hamming solo puede resolver problemas de un solo bit.

Cómo codificar un mensaje en Hamming Code

El proceso que utiliza el remitente para codificar el mensaje consta de los siguientes tres pasos:

  • Calcula el número total de bits redundantes.
  • Determinar la posición de los bits redundantes.
  • Calcula el valor de cada bit redundante.

Cuando los bits redundantes se insertan en el mensaje, la palabra clave completa se envía al receptor.

Paso 1) Calcular el número total de bits redundantes.

Supongamos que el mensaje contiene n bits de datos y p bits redundantes, añadidos de modo que 2p puede indicar al menos (n + p + 1) estados diferentes.

Aquí, (n + p) representa la ubicación de un error en cada una de las (n + p) posiciones de bits, y un estado adicional indica que no hay error. Debido a que p bits de paridad pueden indicar 2p estados, 2p debe ser al menos igual a (n + p + 1).

Paso 2) Coloque las partes redundantes en sus posiciones correctas.

Los p bits redundantes se colocan en posiciones de bits que son potencias de 2, por ejemplo, 1, 2, 4, 8 y 16. Se les denomina p1 (en la posición 1), p2 (en la posición 2), p3 (en la posición 4), y así sucesivamente.

Paso 3) Calcular el valor de cada bit redundante.

Cada bit redundante es un bit de paridad que hace que la cantidad de 1s en su grupo sea par o impar. Los dos tipos de paridad son:

  • Paridad igualitaria: El número total de 1s en las posiciones cubiertas se vuelve par.
  • Paridad impar: El número total de 1s en las posiciones cubiertas se vuelve impar.

Cada bit de paridad cubre un conjunto específico de posiciones, determinado por la representación binaria de los números de posición:

  • p1 Comprueba cada posición cuyo valor binario tenga un 1 en el bit menos significativo: posiciones 1, 3, 5, 7, 9, 11, etc.
  • p2 Comprueba cada posición cuyo valor binario tenga un 1 en el segundo bit desde la derecha: posiciones 2, 3, 6, 7, 10, 11, y así sucesivamente.
  • p3 Comprueba todas las posiciones cuyo valor binario tenga un 1 en el tercer bit desde la derecha: posiciones de la 4 a la 7, de la 12 a la 15, y así sucesivamente.

Ejemplo resuelto (7,4): Consideremos los cuatro bits de datos. 1011Se requieren tres bits de paridad (23 = 8 ≥ 4 + 3 + 1), lo que da como resultado una palabra clave de siete bits dispuesta como p1 p2 d1 p3 d2 d3 d4. Al colocar los datos, las posiciones 3, 5, 6, 7 se convierten en 1, 0, 1, 1. Usando paridad par: p1 cubre las posiciones 1, 3, 5, 7 (bits 1, 0, 1 → p1 = 0); p2 cubre 2, 3, 6, 7 (bits 1, 1, 1 → p2 = 1); p3 cubre 4, 5, 6, 7 (bits 0, 1, 1 → p3 = 0). El transmitLa palabra clave ted es, por lo tanto, 0110011.

Cómo decodificar un mensaje en Hamming Code

El receptor toma el mensaje entrante y realiza recálculos para encontrar y corregir errores. El proceso de recálculo utiliza los siguientes pasos:

  • Cuenta el número de bits redundantes.
  • Coloca correctamente todos los bits redundantes.
  • Realizar la comprobación de paridad.

Paso 1) Contar el número de bits redundantes. Utilice la misma fórmula que para la codificación: 2p ≥ n + p + 1, donde n es el número de bits de datos y p es el número de bits redundantes.

Paso 2) Coloque correctamente todos los bits redundantes. Cada bit redundante se encuentra en una posición de bit que es una potencia de 2; por ejemplo, 1, 2, 4 y 8.

Paso 3) Realizar la comprobación de paridad. Los bits de paridad se recalculan a partir de los bits de datos y los bits redundantes recibidos:

  • p1 = paridad(1, 3, 5, 7, 9, 11, …)
  • p2 = paridad(2, 3, 6, 7, 10, 11, …)
  • p3 = paridad(4–7, 12–15, 20–23, …)

Los bits de paridad recalculados forman un número binario. Si ese número es cero, no hay ningún error; de lo contrario, su valor indica la posición exacta del bit corrupto, que se invierte para corregir el mensaje.

Preguntas Frecuentes

La distancia de Hamming es el número de posiciones de bits en las que difieren dos cadenas binarias de igual longitud. En los códigos de corrección de errores, la distancia de Hamming mínima entre palabras clave válidas determina cuántos errores se pueden detectar o corregir. El código de Hamming estándar tiene una distancia mínima de tres.

El algoritmo Hamming(7,4) codifica cuatro bits de datos en una palabra clave de siete bits añadiendo tres bits de paridad. Corrige cualquier error de un bit y detecta errores de dos bits. La notación (n, k) indica la longitud total de la palabra clave n y el número de bits de datos k.

Un único bit de paridad solo detecta un número impar de errores de bits y no puede localizarlos ni corregirlos. El código Hamming utiliza múltiples bits de paridad en posiciones que son potencias de dos, por lo que identifica con precisión el bit defectuoso y lo corrige automáticamente.

El código Hamming básico corrige los errores de un bit, pero puede corregir erróneamente los errores de dos bits. Al añadir un bit de paridad general que abarca toda la palabra clave, se crea SECDED (corrección de un solo error, detección de doble error), lo que eleva la distancia mínima a cuatro y permite detectar de forma fiable los errores de doble bit.

La detección y corrección de errores se producen principalmente en la capa de enlace de datos del sistema. Modelo OSI, que enmarca los datos y verifica su integridad entre nodos adyacentes. Los protocolos de la capa de transporte agregan verificaciones de extremo a extremo, mientras que el medio físico introduce el ruido contra el cual protegen estos códigos.

El código de Hamming es un código de bloques lineal. Procesa un bloque de bits de tamaño fijo de una sola vez y añade bits de paridad, a diferencia de los códigos convolucionales que codifican una secuencia continua de bits utilizando la memoria de los bits anteriores. Esto hace que el código de Hamming sea simple y rápido.

Los modelos de aprendizaje automático aprenden los patrones de ruido de un canal y predicen posibles errores de bits, mejorando la precisión de la decodificación más allá de los esquemas fijos. Los decodificadores basados ​​en IA para códigos LDPC y polares ahora ayudan a los sistemas modernos de 5G y almacenamiento donde el código Hamming clásico por sí solo resulta insuficiente.

Copiloto de GitHub Puede generar funciones de codificador y decodificador, generar máscaras de bits de paridad y redactar pruebas unitarias a partir de un comentario breve. Verifique las operaciones matemáticas de posición de bits y el grupo de paridad.pings con cuidado, porque la indexación con un desfase de uno es una fuente frecuente de errores en el código generado.

Resumir este post con: