Hamming(7,4)

En la teoría de la codificación , Hamming(7,4) es un código de corrección de errores lineal que codifica cuatro bits de datos en siete bits mediante la adición de tres bits de paridad . Es un miembro de una familia más grande de códigos Hamming , pero el término código Hamming a menudo se refiere a este código específico que Richard W. Hamming introdujo en 1950. En ese momento, Hamming trabajaba en Bell Telephone Laboratories y estaba frustrado con el código propenso a errores. lector de tarjetas perforadas , razón por la cual comenzó a trabajar en códigos de corrección de errores. ^[1]

El código Hamming agrega tres bits de verificación adicionales a cada cuatro bits de datos del mensaje. El algoritmo de Hamming (7,4) puede corregir cualquier error de un solo bit o detectar todos los errores de un solo bit y de dos bits. En otras palabras, la distancia mínima de Hamming entre dos palabras de código correctas es 3, y las palabras recibidas pueden decodificarse correctamente si están a una distancia máxima de uno de la palabra de código que fue transmitida por el remitente. Esto significa que para situaciones de medios de transmisión donde no ocurren errores de ráfaga , el código de Hamming (7,4) es efectivo (ya que el medio tendría que ser extremadamente ruidoso para que dos de los siete bits se voltearan).

En información cuántica , el Hamming (7,4) se utiliza como base para el código Steane , un tipo de código CSS utilizado para la corrección de errores cuánticos .

El objetivo de los códigos de Hamming es crear un conjunto de bits de paridad que se superpongan para que se pueda detectar y corregir un error de un solo bit en un bit de datos o un bit de paridad. Si bien se pueden crear superposiciones múltiples, el método general se presenta en los códigos de Hamming .

Esta tabla describe qué bits de paridad cubren qué bits transmitidos en la palabra codificada. Por ejemplo, p ₂ proporciona una paridad par para los bits 2, 3, 6 y 7. También detalla qué bit transmitido está cubierto por qué bit de paridad al leer la columna. Por ejemplo, d ₁ está cubierto por p ₁ y p ₂ pero no por p _3. Esta tabla tendrá un parecido sorprendente con la matriz de comprobación de paridad ( H ) de la siguiente sección.

Por lo tanto, al seleccionar correctamente la cobertura de bits de paridad, todos los errores con una distancia de Hamming de 1 pueden detectarse y corregirse, que es el punto de usar un código de Hamming.

Representación gráfica de los 4 bits de datos d ₁ a d ₄ y 3 bits de paridad p ₁ a p ₃ y qué bits de paridad se aplican a qué bits de datos

Posición de bit de los bits de datos y paridad

Mapeo en el ejemplo x . La paridad de los círculos rojo, verde y azul es pareja.

Un error de bit en el bit 5 provoca una mala paridad en los círculos rojo y verde

Se introduce un error de bit en el bit 4 y 5 (que se muestra en texto azul) con una paridad mala solo en el círculo verde (que se muestra en texto rojo)