Hamming(7,4)

Código de corrección de errores lineal

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

En teoría de 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 miembro de una familia más grande de códigos de Hamming , pero el término código de 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 lector de tarjetas perforadas propenso a errores , por lo que comenzó a trabajar en códigos de corrección de errores. ^[1]

El código de Hamming añade tres bits de control 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 se pueden decodificar correctamente si están a una distancia de como máximo 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 se invirtieran dos de los siete bits).

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 .

Meta

El objetivo de los códigos de Hamming es crear un conjunto de bits de paridad que se superpongan de modo que se pueda detectar y corregir un error de un solo bit en un bit de datos o en un bit de paridad. Si bien se pueden crear múltiples superposiciones, 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 verificación de paridad ( H ) en la siguiente sección.

Además, si se eliminaran las columnas de paridad en la tabla anterior

Entonces también será evidente la semejanza con las filas 1, 2 y 4 de la matriz generadora de código ( G ) a continuación.

Entonces, al elegir correctamente la cobertura del bit de paridad, se pueden detectar y corregir todos los errores con una distancia de Hamming de 1, que es el objetivo de utilizar un código Hamming.

Matrices de Hamming

Los códigos de Hamming se pueden calcular en términos de álgebra lineal a través de matrices porque los códigos de Hamming son códigos lineales . Para los fines de los códigos de Hamming, se pueden definir dos matrices de Hamming : la matriz generadora de códigos G y la matriz de verificación de paridad H :

${\displaystyle \mathbf {G^{T}} :={\begin{pmatrix}1&1&0&1\\1&0&1&1\\1&0&0&0\\0&1&1&1\\0&1&0&0\\0&0&1&0\\0&0&0&1\\\end{pmatrix}},\qquad \mathbf {H} :={\begin{pmatrix}1&0&1&0&1&0&1\\0&1&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}.}$

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

Como se mencionó anteriormente, las filas 1, 2 y 4 de G deberían resultar familiares, ya que asignan los bits de datos a sus bits de paridad:

• p ₁ cubre d ₁ , d ₂ , d ₄
• p ₂ cubre d ₁ , d ₃ , d ₄
• p ₃ cubre d ₂ , d ₃ , d ₄

Las filas restantes (3, 5, 6, 7) asignan los datos a su posición en forma codificada y solo hay una en esa fila, por lo que es una copia idéntica. De hecho, estas cuatro filas son linealmente independientes y forman la matriz de identidad (por diseño, no por coincidencia).

Como ya se mencionó anteriormente, las tres filas de H deberían resultar familiares. Estas filas se utilizan para calcular el vector de síndrome en el extremo receptor y, si el vector de síndrome es el vector nulo (todos ceros), la palabra recibida no tiene errores; si no es cero, el valor indica qué bit se ha invertido.

Los cuatro bits de datos (ensamblados como un vector p ) se multiplican previamente por G (es decir, Gp ) y se toman en módulo 2 para obtener el valor codificado que se transmite. Los 4 bits de datos originales se convierten en siete bits (de ahí el nombre "Hamming(7,4)") con tres bits de paridad agregados para asegurar una paridad uniforme utilizando las coberturas de bits de datos anteriores. La primera tabla anterior muestra la asignación entre cada bit de datos y paridad en su posición de bit final (del 1 al 7), pero esto también se puede presentar en un diagrama de Venn . El primer diagrama de este artículo muestra tres círculos (uno para cada bit de paridad) y encierra los bits de datos que cubre cada bit de paridad. El segundo diagrama (que se muestra a la derecha) es idéntico pero, en cambio, las posiciones de los bits están marcadas.

Durante el resto de esta sección, se utilizarán los siguientes 4 bits (mostrados como un vector de columna) como ejemplo de ejecución:

${\displaystyle \mathbf {p} ={\begin{pmatrix}d_{1}\\d_{2}\\d_{3}\\d_{4}\\\end{pmatrix}}={\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}}$

Codificación de canales

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

Supongamos que queremos transmitir estos datos ( 1011) a través de un canal de comunicaciones ruidoso . En concreto, un canal binario simétrico, lo que significa que la corrupción de errores no favorece ni al cero ni al uno (es simétrico en la generación de errores). Además, se supone que todos los vectores de origen son equiprobables. Tomamos el producto de G y p , con entradas módulo 2, para determinar la palabra clave transmitida x :

${\displaystyle \mathbf {x} =\mathbf {G^{T}} \mathbf {p} ={\begin{pmatrix}1&1&0&1\\1&0&1&1\\1&0&0&0\\0&1&1&1\\0&1&0&0\\0&0&1&0\\0&0&0&1\\\end{pmatrix}}{\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}2\\3\\1\\2\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}}$

Esto significa que 0110011se transmitiría en lugar de transmitir 1011.

Los programadores preocupados por la multiplicación deben observar que cada fila del resultado es el bit menos significativo del recuento de población de bits del conjunto resultante de la operación AND bit a bit de la fila y la columna en lugar de multiplicarlas.

En el diagrama adyacente, los siete bits de la palabra codificada se insertan en sus respectivas ubicaciones; de la inspección se desprende claramente que la paridad de los círculos rojo, verde y azul es par:

• El círculo rojo tiene dos 1
• El círculo verde tiene dos 1
• El círculo azul tiene cuatro 1.

Lo que se demostrará en breve es que si, durante la transmisión, se invierte un bit, la paridad de dos o de los tres círculos será incorrecta y el bit con error se puede determinar (incluso si es uno de los bits de paridad) sabiendo que la paridad de los tres círculos debe ser par.

Comprobación de paridad

Si no se produce ningún error durante la transmisión, la palabra de código recibida r es idéntica a la palabra de código transmitida x :

${\displaystyle \mathbf {r} =\mathbf {x} }$

El receptor multiplica H y r para obtener el vector de síndrome z , que indica si se ha producido un error y, en caso afirmativo, para qué bit de la palabra clave. Realizando esta multiplicación (de nuevo, entradas módulo 2):

${\displaystyle \mathbf {z} =\mathbf {H} \mathbf {r} ={\begin{pmatrix}1&0&1&0&1&0&1\\0&1&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}{\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}2\\4\\2\end{pmatrix}}={\begin{pmatrix}0\\0\\0\end{pmatrix}}}$

Como el síndrome z es el vector nulo , el receptor puede concluir que no se ha producido ningún error. Esta conclusión se basa en la observación de que cuando el vector de datos se multiplica por G , se produce un cambio de base hacia un subespacio vectorial que es el núcleo de H. Mientras no ocurra nada durante la transmisión, r permanecerá en el núcleo de H y la multiplicación dará como resultado el vector nulo.

Corrección de errores

De lo contrario, supongamos que podemos escribir

${\displaystyle \mathbf {r} =\mathbf {x} +\mathbf {e} _{i}}$

módulo 2, donde e _i es el vector unitario , es decir, un vector cero con un 1 en el , contando desde 1. ${\displaystyle i_{th}}$ ${\displaystyle i^{th}}$

${\displaystyle \mathbf {e} _{2}={\begin{pmatrix}0\\1\\0\\0\\0\\0\\0\end{pmatrix}}}$

Por lo tanto, la expresión anterior significa que hay un solo error de bit en ese lugar. ${\displaystyle i^{th}}$

Ahora, si multiplicamos este vector por H :

${\displaystyle \mathbf {Hr} =\mathbf {H} \left(\mathbf {x} +\mathbf {e} _{i}\right)=\mathbf {Hx} +\mathbf {He} _{i}}$

Como x es el dato transmitido, no tiene errores y, como resultado, el producto de H y x es cero.

${\displaystyle \mathbf {Hx} +\mathbf {He} _{i}=\mathbf {0} +\mathbf {He} _{i}=\mathbf {He} _{i}}$

Ahora, el producto de H con el vector base estándar selecciona esa columna de H , sabemos que el error ocurre en el lugar donde ocurre esta columna de H. ${\displaystyle i^{th}}$

Por ejemplo, supongamos que hemos introducido un error de bit en el bit n.° 5.

${\displaystyle \mathbf {r} =\mathbf {x} +\mathbf {e} _{5}={\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}+{\begin{pmatrix}0\\0\\0\\0\\1\\0\\0\end{pmatrix}}={\begin{pmatrix}0\\1\\1\\0\\1\\1\\1\end{pmatrix}}}$

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

El diagrama de la derecha muestra el error de bit (que se muestra en texto azul) y la paridad incorrecta creada (que se muestra en texto rojo) en los círculos rojo y verde. El error de bit se puede detectar calculando la paridad de los círculos rojo, verde y azul. Si se detecta una paridad incorrecta, el bit de datos que se superpone solo a los círculos de paridad incorrecta es el bit con el error. En el ejemplo anterior, los círculos rojo y verde tienen paridad incorrecta, por lo que el bit correspondiente a la intersección de rojo y verde, pero no azul, indica el bit con error.

Ahora,

${\displaystyle \mathbf {z} =\mathbf {Hr} ={\begin{pmatrix}1&0&1&0&1&0&1\\0&1&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}{\begin{pmatrix}0\\1\\1\\0\\1\\1\\1\end{pmatrix}}={\begin{pmatrix}3\\4\\3\end{pmatrix}}={\begin{pmatrix}1\\0\\1\end{pmatrix}}}$

que corresponde a la quinta columna de H . Además, el algoritmo general utilizado ( ver código Hamming#Algoritmo general ) fue intencional en su construcción para que el síndrome de 101 corresponda al valor binario de 5, lo que indica que el quinto bit estaba dañado. Por lo tanto, se ha detectado un error en el bit 5 y se puede corregir (simplemente invirtiendo o negando su valor):

${\displaystyle \mathbf {r} _{\text{corrected}}={\begin{pmatrix}0\\1\\1\\0\\{\overline {1}}\\1\\1\end{pmatrix}}={\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}}$

Este valor recibido corregido, de hecho, ahora coincide con el valor x transmitido desde arriba.

Descodificación

Una vez que se ha determinado que el vector recibido está libre de errores o se ha corregido si ocurrió un error (asumiendo que solo son posibles errores de cero o un bit), entonces los datos recibidos deben decodificarse nuevamente en los cuatro bits originales.

Primero, defina una matriz R :

${\displaystyle \mathbf {R} ={\begin{pmatrix}0&0&1&0&0&0&0\\0&0&0&0&1&0&0\\0&0&0&0&0&1&0\\0&0&0&0&0&0&1\\\end{pmatrix}}}$

Entonces el valor recibido, p _r , es igual a Rr . Usando el ejemplo de ejecución anterior

${\displaystyle \mathbf {p_{r}} ={\begin{pmatrix}0&0&1&0&0&0&0\\0&0&0&0&1&0&0\\0&0&0&0&0&1&0\\0&0&0&0&0&0&1\\\end{pmatrix}}{\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}}$

Errores de bits múltiples

Se introduce un error de bit en los bits 4 y 5 (mostrado en texto azul) con una paridad incorrecta solo en el círculo verde (mostrado en texto rojo)

No es difícil demostrar que con este esquema sólo se pueden corregir errores de un solo bit. Alternativamente, se pueden utilizar códigos de Hamming para detectar errores de un solo bit y de dos bits, simplemente observando que el producto de H es distinto de cero siempre que se hayan producido errores. En el diagrama adyacente, se invirtieron los bits 4 y 5. Esto produce sólo un círculo (verde) con una paridad no válida, pero los errores no son recuperables.

Sin embargo, el código Hamming (7,4) y otros similares no pueden distinguir entre errores de un solo bit y errores de dos bits. Es decir, los errores de dos bits aparecen de la misma manera que los errores de un bit. Si se realiza una corrección de errores en un error de dos bits, el resultado será incorrecto.

De manera similar, los códigos Hamming no pueden detectar ni recuperarse de un error arbitrario de tres bits; considere el diagrama: si el bit en el círculo verde (coloreado en rojo) fuera 1, la verificación de paridad devolvería el vector nulo, lo que indica que no hay ningún error en la palabra de código.

Todas las palabras clave

Dado que la fuente tiene solo 4 bits, solo hay 16 palabras posibles de transmitir. Se incluye el valor de ocho bits si se utiliza un bit de paridad adicional ( consulte el código Hamming(7,4) con un bit de paridad adicional ). (Los bits de datos se muestran en azul; los bits de paridad se muestran en rojo; y el bit de paridad adicional se muestra en verde).

mi7enrejado

El código Hamming(7,4) está estrechamente relacionado con la red E 7 y, de hecho, se puede utilizar para construirla, o más precisamente, su red dual E ₇ ^∗ (una construcción similar para E ₇ utiliza el código dual [7,3,4] ₂ ). En particular, tomando el conjunto de todos los vectores x en Z ⁷ con x congruente (módulo 2) con una palabra clave de Hamming(7,4), y reescalando por 1/ √ 2 , se obtiene la red E ₇ ^∗

${\displaystyle E_{7}^{*}={\tfrac {1}{\sqrt {2}}}\left\{x\in \mathbb {Z} ^{7}:x{\bmod {2}}\in [7,4,3]_{2}\right\}.}$

Este es un ejemplo particular de una relación más general entre redes y códigos. Por ejemplo, el código (8,4)-Hamming extendido, que surge de la adición de un bit de paridad, también está relacionado con la red E 8 . ^[2]

Referencias

1. "Historia de los códigos Hamming". Archivado desde el original el 25 de octubre de 2007. Consultado el 3 de abril de 2008 .
2. Conway, John H. ; Sloane, Neil JA (1998). Empaquetamientos de esferas, redes y grupos (3.ª ed.). Nueva York: Springer-Verlag. ISBN 0-387-98585-9.

Enlaces externos

• Un problema de programación sobre el Código Hamming (7,4)