Hamming(7,4)

En teoría de la codificación , el código Hamming(7,4) es un código lineal corrector de errores que codifica cuatro bits de datos en siete bits mediante la adición de tres bits de paridad . Pertenece a una familia más amplia de códigos Hamming , pero el término código Hamming suele referirse a este código específico que Richard W. Hamming introdujo en 1950. En aquel entonces, Hamming trabajaba en los Laboratorios Bell Telephone y estaba frustrado con el lector de tarjetas perforadas , propenso a errores , razón por la cual comenzó a trabajar en códigos correctores de errores. ^{[ 1 ]}

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

En información cuántica , el código de Hamming (7,4) se utiliza como base para el código de 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, 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, según se indica en la columna. Por ejemplo, _d₁ está cubierto por p₁ y _{p₂ ,} pero no por p₃ . _Esta tabla tendrá un parecido notable con la matriz de verificación de paridad ( _H ) de la siguiente sección.

Además, si se eliminaran las columnas de paridad de 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 ) que se muestra a continuación.

Así pues, al seleccionar correctamente la cobertura de bits de paridad, se pueden detectar y corregir todos los errores con una distancia de Hamming de 1, que es precisamente el objetivo de utilizar un código de Hamming.

Los códigos de Hamming se pueden calcular en términos de álgebra lineal mediante matrices porque son códigos lineales . Para los códigos de Hamming, se pueden definir dos matrices : la matriz generadora de código 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}}.}

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:

• La página ₁ cubre d ₁ , d ₂ , d ₄
• La página ₂ cubre d ₁ , d ₃ , d ₄
• La página ₃ cubre d ₂ , d ₃ , d ₄

Las filas restantes (3, 5, 6, 7) asignan los datos a su posición en formato codificado, y como solo hay un 1 en esa fila, se trata de una copia idéntica. De hecho, estas cuatro filas son linealmente independientes y forman la matriz identidad (esto se debe a un diseño intencionado, no a una coincidencia).

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

Los cuatro bits de datos —ensamblados como un vector p— se premultiplican por G (es decir,${\displaystyle G^{T}p}$) y se toma módulo 2 para producir 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 añadidos para asegurar una paridad par utilizando las coberturas de bits de datos anteriores. La primera tabla anterior muestra el mapeo entre cada bit de datos y paridad en su posición de bit final (1 a 7) pero esto también se puede presentar en un diagrama de Venn . El primer diagrama en 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 su lugar, se marcan las posiciones de los bits.

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

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

Supongamos que queremos transmitir estos datos ( 1011) a través de un canal de comunicaciones ruidoso . Específicamente, un canal binario simétrico, lo que significa que la corrupción de errores no favorece ni al cero ni al uno (es simétrica en la generación de errores). Además, se supone que todos los vectores fuente 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.

La multiplicación de matrices se realiza módulo 2. De forma equivalente, cada fila del resultado es el bit menos significativo del recuento de población de bits activados que resulta de la operación AND bit a bit entre la fila y la columna.

En el diagrama adjunto, los siete bits de la palabra codificada se insertan en sus respectivas ubicaciones; a simple vista se observa 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 erróneo se puede determinar (incluso si se trata de uno de los bits de paridad) sabiendo que la paridad de estos tres círculos debería ser par.

Si no se produce ningún error durante la transmisión, entonces la palabra clave recibida r es idéntica a la palabra clave 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 (nuevamente, 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}}}$

Dado que 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, al multiplicar el vector de datos 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.

De lo contrario, supongamos que podemos escribir

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

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

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

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

Ahora, si multiplicamos este vector por H :

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

Dado que x son los datos transmitidos, no hay error y, como resultado, el producto de H y x es cero. Por lo tanto,

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

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

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}}}$

El diagrama de la derecha muestra el error de bit (indicado en texto azul) y la paridad incorrecta (indicada en texto rojo) en los círculos rojo y verde. El error de bit se detecta calculando la paridad de los círculos rojo, verde y azul. Si se detecta una paridad incorrecta, el bit de datos que se superpone únicamente con los círculos de paridad incorrecta es el que contiene 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 de azul, indica el bit erróneo.

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 ( véase el código de Hamming#Algoritmo general ) fue diseñado intencionalmente para que el síndrome de 101 corresponda al valor binario de 5, lo que indica que el quinto bit estaba corrupto. 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 coincide ahora, efectivamente, con el valor transmitido x mencionado anteriormente.

Una vez que se ha determinado que el vector recibido está libre de errores o se ha corregido si se produjo algún error (suponiendo que solo son posibles errores de cero o un bit), entonces los datos recibidos deben decodificarse de nuevo en los cuatro bits originales.

Primero, definamos 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}}}$

Es fácil demostrar que este esquema solo corrige errores de un solo bit. Como alternativa, se pueden usar códigos de Hamming para detectar errores de uno o dos bits, simplemente observando que el producto de H es distinto de cero cuando se producen errores. En el diagrama adjunto, los bits 4 y 5 se invirtieron. Esto produce un único círculo (verde) con paridad inválida, pero los errores no se pueden recuperar.

Sin embargo, el código Hamming (7,4) y otros códigos similares no distinguen entre errores de un bit y errores de dos bits. Es decir, los errores de dos bits se presentan igual que los de un bit. Si se aplica una corrección de errores a un error de dos bits, el resultado será incorrecto.

De manera similar, los códigos de 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 de rojo) fuera 1, la comprobación de paridad devolvería el vector nulo, lo que indica que no hay ningún error en la palabra clave.

Dado que la fuente es de solo 4 bits, existen únicamente 16 palabras transmitidas posibles. Se incluye el valor de ocho bits si se utiliza un bit de paridad adicional ( véase el código Hamming(7,4) con un bit de paridad adicional ). (Los bits de datos se muestran en azul; los bits de paridad, en rojo; y el bit de paridad adicional, en verde).

El código Hamming(7,4) está estrechamente relacionado con el retículo E ₇ y, de hecho, puede usarse para construirlo, o más precisamente, su retículo dual E ₇ ^∗ (una construcción similar para E ₇ usa 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) a una palabra clave de Hamming(7,4), y reescalándolo por 1/ √ 2 , se obtiene el retículo 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 retículos y códigos. Por ejemplo, el código de Hamming extendido (8,4), que surge de la adición de un bit de paridad, también está relacionado con el retículo E ₈ . ^{[ 2 ]}

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