Código de Hamming

En informática y telecomunicaciones , los códigos de Hamming son una familia de códigos lineales de corrección de errores . Los códigos de Hamming pueden detectar errores de uno y dos bits, o corregir errores de un bit sin detectar errores no corregidos. Por el contrario, el código de paridad simple no puede corregir errores y solo puede detectar un número impar de bits erróneos. Los códigos de Hamming son códigos perfectos , es decir, alcanzan la tasa más alta posible para códigos con su longitud de bloque y distancia mínima de tres. ^{[ 1 ]} Richard W. Hamming inventó los códigos de Hamming en 1950 como una forma de corregir automáticamente los errores introducidos por los lectores de tarjetas perforadas . En su artículo original, Hamming desarrolló su idea general, pero se centró específicamente en el código Hamming(7,4) , que añade tres bits de paridad a cuatro bits de datos. ^{[ 2 ]}

En términos matemáticos , los códigos de Hamming son una clase de códigos binarios lineales. Para cada entero $r \geq 2$ hay una palabra código con longitud de bloque $n = 2 r - 1$ y longitud de mensaje $k = 2 r - r - 1$ . Por lo tanto, la tasa de los códigos de Hamming es $R = k / n = 1 - r / (2 r - 1)$ , que es la más alta posible para códigos con distancia mínima de tres (es decir, el número mínimo de cambios de bits necesarios para pasar de cualquier palabra código a cualquier otra palabra código es tres) y longitud de bloque $2 r - 1$ . La matriz de verificación de paridad de un código de Hamming se construye enumerando todas las columnas de longitud $r$ que son distintas de cero, lo que significa que el código dual del código de Hamming es el código Hadamard abreviado , también conocido como código Simplex. La matriz de verificación de paridad tiene la propiedad de que cualesquiera dos columnas son linealmente independientes por pares .

Debido a la redundancia limitada que los códigos de Hamming añaden a los datos, solo pueden detectar y corregir errores cuando la tasa de error es baja. Este es el caso de la memoria de la computadora (generalmente RAM), donde los errores de bits son extremadamente raros y los códigos de Hamming se utilizan ampliamente. La memoria con este sistema de corrección se conoce como memoria ECC . En este contexto, se suele utilizar un código de Hamming extendido con un bit de paridad adicional. Los códigos de Hamming extendidos alcanzan una distancia de Hamming de cuatro, lo que permite al decodificador distinguir entre cuando ocurre como máximo un error de un bit y cuando ocurren errores de dos bits. En este sentido, los códigos de Hamming extendidos son correctores de errores simples y detectores de errores dobles, abreviados como SECDED .

Historia

Richard Hamming , el inventor de los códigos Hamming, trabajó en los Laboratorios Bell a finales de la década de 1940 con la computadora Bell Modelo V , una máquina electromecánica basada en relés con tiempos de ciclo en segundos. La entrada de datos se realizaba mediante cinta de papel perforada de siete octavos de pulgada de ancho, con hasta seis agujeros por fila. Durante los días laborables, cuando se detectaban errores en los relés, la máquina se detenía y encendía luces intermitentes para que los operadores pudieran corregir el problema. Fuera del horario laboral y los fines de semana, cuando no había operadores, la máquina simplemente pasaba a la siguiente tarea.

Hamming trabajaba los fines de semana y se sentía cada vez más frustrado por tener que reiniciar sus programas desde cero debido a errores detectados. En una entrevista grabada, Hamming dijo: «Entonces dije: "¡Maldita sea! Si la máquina puede detectar un error, ¿por qué no puede localizar la posición del error y corregirlo?"». ^{[ 3 ]} Durante los años siguientes, trabajó en el problema de la corrección de errores, desarrollando un conjunto de algoritmos cada vez más potentes. En 1950, publicó lo que ahora se conoce como código Hamming, que todavía se utiliza hoy en día en aplicaciones como la memoria ECC .

Códigos anteriores a Hamming

Antes de los códigos de Hamming, se utilizaron varios códigos sencillos de detección de errores, pero ninguno fue tan eficaz como los códigos de Hamming con el mismo consumo de espacio.

Paridad

La paridad añade un bit que indica si el número de unos (posiciones de bits con valor uno) en los datos precedentes era par o impar . Si se modifica un número impar de bits durante la transmisión, el mensaje cambiará de paridad y el error podrá detectarse en ese momento; sin embargo, el bit modificado podría ser el propio bit de paridad. La convención más común es que un valor de paridad de uno indica que hay un número impar de unos en los datos, y un valor de paridad de cero indica que hay un número par de unos. Si el número de bits modificados es par, el bit de verificación será válido y el error no se detectará.

Además, la paridad no indica qué bit contenía el error, incluso cuando puede detectarlo. Los datos deben descartarse por completo y retransmitirse desde cero. En un medio de transmisión ruidoso , una transmisión exitosa podría tardar mucho tiempo o incluso no producirse nunca. Sin embargo, aunque la calidad de la comprobación de paridad es baja, ya que utiliza un solo bit, este método genera la menor sobrecarga.

Código dos de cinco

Un código dos de cinco es un esquema de codificación que utiliza cinco bits que consisten exactamente en tres 0 y dos 1. Esto proporciona ${\binom {5}{3}}=10$ Combinaciones posibles, suficientes para representar los dígitos del 0 al 9. Este esquema puede detectar todos los errores de un solo bit, todos los errores de bits impares y algunos errores de bits pares (por ejemplo, la inversión de ambos bits 1). Sin embargo, aún no puede corregir ninguno de estos errores.

Repetición

Otro código utilizado en ese momento repetía cada bit de datos varias veces para asegurar su correcta transmisión. Por ejemplo, si el bit de datos a enviar es un 1, un código de repetición n = 3 enviará 111. Si los tres bits recibidos no son idénticos, se produjo un error durante la transmisión. Si el canal es suficientemente limpio, la mayoría de las veces solo cambiará un bit en cada triplete. Por lo tanto, 001, 010 y 100 corresponden a un bit 0, mientras que 110, 101 y 011 corresponden a un bit 1, y la mayor cantidad de dígitos iguales ('0' o un '1') indica cuál debería ser el bit de datos. Un código con esta capacidad de reconstruir el mensaje original en presencia de errores se conoce como código corrector de errores . Este código de repetición triple es un código Hamming con m = 2, ya que hay dos bits de paridad y 2 ² − 2 − 1 = 1 bit de datos.

Sin embargo, estos códigos no pueden corregir todos los errores. En nuestro ejemplo, si el canal invierte dos bits y el receptor recibe 001, el sistema detectará el error, pero concluirá que el bit original es 0, lo cual es incorrecto. Si aumentamos el tamaño de la cadena de bits a cuatro, podemos detectar todos los errores de dos bits, pero no corregirlos (la cantidad de bits de paridad es par); con cinco bits, podemos detectar y corregir todos los errores de dos bits, pero no todos los de tres bits.

Además, aumentar el tamaño de la cadena de bits de paridad es ineficiente, ya que reduce el rendimiento en un factor de tres en nuestro caso original, y la eficiencia disminuye drásticamente a medida que aumentamos la cantidad de veces que se duplica cada bit para detectar y corregir más errores.

Descripción

Si se incluyen más bits de corrección de errores en un mensaje, y si estos bits se pueden organizar de manera que distintos bits incorrectos produzcan diferentes resultados de error, entonces se podrían identificar los bits defectuosos. En un mensaje de siete bits, existen siete posibles errores de un solo bit, por lo que tres bits de control de errores podrían especificar no solo que se produjo un error, sino también qué bit lo causó.

Hamming estudió los esquemas de codificación existentes, incluido el de dos de cinco, y generalizó sus conceptos. Para empezar, desarrolló una nomenclatura para describir el sistema, incluyendo el número de bits de datos y bits de corrección de errores en un bloque. Por ejemplo, la paridad incluye un bit para cada palabra de datos, así que, suponiendo palabras ASCII de siete bits, Hamming lo describió como un código (8,7) , con ocho bits en total, de los cuales siete son datos. El ejemplo de repetición sería (3,1) , siguiendo la misma lógica. La tasa de codificación es el segundo número dividido por el primero; para nuestro ejemplo de repetición, 1/3.

Hamming también notó los problemas que surgen al invertir dos o más bits, y describió esto como la "distancia" (ahora llamada distancia de Hamming , en su honor). La paridad tiene una distancia de 2, por lo que se puede detectar la inversión de un bit, pero no corregirla, y cualquier inversión de dos bits será invisible. La repetición (3,1) tiene una distancia de 3, ya que se necesitan invertir tres bits en la misma terna para obtener otra palabra de código sin errores visibles. Puede corregir errores de un bit o detectar, pero no corregir, errores de dos bits. Una repetición (4,1) (cada bit se repite cuatro veces) tiene una distancia de 4, por lo que se puede detectar la inversión de tres bits, pero no corregirla. Cuando se invierten tres bits en el mismo grupo, puede haber situaciones en las que intentar corregirlos produzca una palabra de código incorrecta. En general, un código con distancia k puede detectar, pero no corregir, k − 1 errores.

Hamming estaba interesado en dos problemas a la vez: aumentar la distancia lo máximo posible y, simultáneamente, incrementar la tasa de codificación al máximo. Durante la década de 1940, desarrolló varios esquemas de codificación que supusieron mejoras sustanciales respecto a los códigos existentes. La clave de todos sus sistemas residía en la superposición de los bits de paridad, de modo que estos pudieran verificarse entre sí y, al mismo tiempo, verificar los datos.

Algoritmo general

The following general algorithm generates a single-error correcting (SEC) code for any number of bits. The main idea is to choose the error-correcting bits such that the index-XOR (the XOR of all the bit positions containing a 1) is 0. We use positions 1, 10, 100, etc. (in binary) as the error-correcting bits, which guarantees it is possible to set the error-correcting bits so that the index-XOR of the whole message is 0. If the receiver receives a string with index-XOR 0, they can conclude there were no corruptions, and otherwise, the index-XOR indicates the index of the corrupted bit.

An algorithm can be deduced from the following description:

Number the bits starting from 1: bit 1, 2, 3, 4, 5, 6, 7, etc.
Write the bit numbers in binary: 1, 10, 11, 100, 101, 110, 111, etc.
All bit positions that are powers of two (have a single 1 bit in the binary form of their position) are parity bits: 1, 2, 4, 8, etc. (1, 10, 100, 1000)
All other bit positions, with two or more 1 bits in the binary form of their position, are data bits.
Each data bit is included in a unique set of 2 or more parity bits, as determined by the binary form of its bit position.
1. Parity bit 1 covers all bit positions which have the least significant bit set: bit 1 (the parity bit itself), 3, 5, 7, 9, etc.
2. Parity bit 2 covers all bit positions which have the second least significant bit set: bits 2–3, 6–7, 10–11, etc.
3. Parity bit 4 covers all bit positions which have the third least significant bit set: bits 4–7, 12–15, 20–23, etc.
4. Parity bit 8 covers all bit positions which have the fourth least significant bit set: bits 8–15, 24–31, 40–47, etc.
5. In general each parity bit covers all bits where the bitwise AND of the parity position and the bit position is non-zero.

If a byte of data to be encoded is 10011010, then the data word (using _ to represent the parity bits) would be __1_001_1010, and the code word is 011100101010.

The choice of the parity, even or odd, is irrelevant but the same choice must be used for both encoding and decoding.

This general rule can be shown visually:

Shown are only 20 encoded bits (5 parity, 15 data) but the pattern continues indefinitely. The key thing about Hamming codes that can be seen from visual inspection is that any given bit is included in a unique set of parity bits. To check for errors, check all of the parity bits. The pattern of errors, called the error syndrome, identifies the bit in error. If all parity bits are correct, there is no error. Otherwise, the sum of the positions of the erroneous parity bits identifies the erroneous bit. For example, if the parity bits in positions 1, 2 and 8 indicate an error, then bit 1+2+8=11 is in error. If only one parity bit indicates an error, the parity bit itself is in error.

With $m$ parity bits, bits from 1 up to $2^{m}-1$ can be covered. After discounting the parity bits, $2^{m}-m-1$ bits remain for use as data. As $m$ varies, we get all the possible Hamming codes:

Hamming codes with additional parity (SECDED)

Hamming codes have a minimum distance of 3, which means that the decoder can detect and correct a single error, but it cannot distinguish a double bit error of some codeword from a single bit error of a different codeword. Thus, some double-bit errors will be incorrectly decoded as if they were single bit errors and therefore go undetected, unless no correction is attempted.

To remedy this shortcoming, Hamming codes can be extended by an extra parity bit. This way, it is possible to increase the minimum distance of the Hamming code to 4, which allows the decoder to distinguish between single bit errors and two-bit errors. Thus the decoder can detect and correct a single error and at the same time detect (but not correct) a double error. If the decoder does not attempt to correct errors, it can reliably detect triple bit errors. If the decoder does correct errors, some triple errors will be mistaken for single errors and "corrected" to the wrong value. Error correction is therefore a trade-off between certainty (the ability to reliably detect triple bit errors) and resiliency (the ability to keep functioning in the face of single bit errors).

For k data bits, a SECDED scheme requires:

Let q be the first power of 2 greater than k.
Let l be floor(log₂(k)) and h be l + 1.
Si k ≤ q - l - 1 , los bits adicionales requeridos son l . De lo contrario, el recuento requerido es h .

Este código Hamming extendido fue popular en los sistemas de memoria de las computadoras, comenzando con el IBM 7030 Stretch en 1961, ^{[ 4 ]} donde se conoce como SECDED (o SEC-DED, abreviatura de corrección de error simple, detección de error doble ). ^{[ 5 ]} Las formas comunes para sistemas de memoria incluyen (39,32) y (72,64). (Si bien es más eficiente usar una longitud de palabra de código de la forma 2 ^m - 1, los tamaños de palabra de datos de las computadoras existentes que son potencias de 2 impiden esta elección, aunque los sistemas de comunicación y almacenamiento de datos sí la aprovechan). Las computadoras servidor en el siglo XXI, si bien generalmente mantienen el nivel de protección SECDED, ya no usan el método de Hamming, sino que se basan en diseños con palabras de código más largas (128 a 256 bits de datos) y árboles de verificación de paridad balanceados modificados. ^{[ 4 ]} El código Hamming (72,64) todavía es popular en algunos diseños de hardware, incluidas las familias de FPGA de Xilinx . ^[⁴^]

[7,4] Código de Hamming

Representación gráfica de los cuatro bits de datos y los tres bits de paridad, y qué bits de paridad se aplican a qué bits de datos.

En 1950, Hamming introdujo el código Hamming [7,4]. Este codifica cuatro bits de datos en siete bits mediante la adición de tres bits de paridad. Como se explicó anteriormente, puede detectar y corregir errores de un solo bit o bien detectar (pero no corregir) errores de uno o dos bits.

Con la adición de un bit de paridad global, se convierte en el código Hamming extendido [8,4] y puede detectar y corregir errores de un solo bit, así como detectar (pero no corregir) errores de dos bits.

Construcción de G y H

La matriz $\mathbf {G$ se denomina matriz generadora (canónica) de uncódigo lineal ( n , k ),

y $\mathbf {H$ se denomina matriz de verificación de paridad .

Esta es la construcción de G y H en forma estándar (o sistemática). Independientemente de la forma, G y H para códigos de bloques lineales deben satisfacer

$\mathbf {H} \,\mathbf {G} ^{\text{T}}=\mathbf {0}$ , una matriz de ceros. ^{[ 6 ]}

Since [7, 4, 3] = [n, k, d] = [2^m − 1, 2^m − 1 − m, 3]. The parity-check matrixH of a Hamming code is constructed by listing all columns of length m that are pair-wise independent.

Thus H is a matrix whose left side is all of the nonzero n-tuples where order of the n-tuples in the columns of matrix does not matter. The right hand side is just the (n − k)-identity matrix.

So G can be obtained from H by taking the transpose of the left hand side of H with the identity k-identity matrix on the left hand side of G.

The code generator matrix $\mathbf {G}$ and the parity-check matrix $\mathbf {H}$ are:

$\mathbf {G$

and

$\mathbf {H$

Finally, these matrices can be mutated into equivalent non-systematic codes by the following operations:^[6]

Column permutations (swapping columns)
Elementary row operations (replacing a row with a linear combination of rows)

Encoding

Example

From the above matrix we have 2^k = 2⁴ = 16 codewords. Let ${\vec {a}}$ be a row vector of binary data bits, ${\vec {a}}=[a_{1},a_{2},a_{3},a_{4}],\quad a_{i}\in \{0,1\}$ . The codeword ${\vec {x}}$ for any of the 16 possible data vectors ${\vec {a}}$ is given by the standard matrix product ${\vec {x}}={\vec {a}}G$ where the summing operation is done modulo-2.

For example, let ${\vec {a}}=[1,0,1,1]$ . Using the generator matrix $G$ from above, we have (after applying modulo 2, to the sum),

${\vec {x}}={\vec {a}}G={\begin{pmatrix}1&0&1&1\end{pmatrix}}{\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&0&1\\0&0&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}={\begin{pmatrix}1&0&1&1&2&3&2\end{pmatrix}}={\begin{pmatrix}1&0&1&1&0&1&0\end{pmatrix}}$

[8,4] Hamming code with an additional parity bit

The same [7,4] example from above with an extra parity bit. This diagram is not meant to correspond to the matrix H for this example.

The [7,4] Hamming code can easily be extended to an [8,4] code by adding an extra parity bit on top of the (7,4) encoded word (see Hamming(7,4)). This can be summed up with the revised matrices:

\mathbf {G

and

\mathbf {H

Note that H is not in standard form. To obtain G, elementary row operations can be used to obtain an equivalent matrix to H in systematic form:

\mathbf {H} =\left({\begin{array}{cccc|cccc}0&1&1&1&1&0&0&0\\1&0&1&1&0&1&0&0\\1&1&0&1&0&0&1&0\\1&1&1&0&0&0&0&1\end{array}}\right)_{4,8}.

For example, the first row in this matrix is the sum of the second and third rows of H in non-systematic form. Using the systematic construction for Hamming codes from above, the matrix A is apparent and the systematic form of G is written as

\mathbf {G} =\left({\begin{array}{cccc|cccc}1&0&0&0&0&1&1&1\\0&1&0&0&1&0&1&1\\0&0&1&0&1&1&0&1\\0&0&0&1&1&1&1&0\end{array}}\right)_{4,8}.

The non-systematic form of G can be row reduced (using elementary row operations) to match this matrix.

The addition of the fourth row effectively computes the sum of all the codeword bits (data and parity) as the fourth parity bit.

For example, 1011 is encoded (using the non-systematic form of G at the start of this section) into 01100110 where blue digits are data; red digits are parity bits from the [7,4] Hamming code; and the green digit is the parity bit added by the [8,4] code. The green digit makes the parity of the [7,4] codewords even.

Finally, it can be shown that the minimum distance has increased from 3, in the [7,4] code, to 4 in the [8,4] code. Therefore, the code can be defined as [8,4] Hamming code.

To decode the [8,4] Hamming code, first check the parity bit. If the parity bit indicates an error, single error correction (the [7,4] Hamming code) will indicate the error location, with "no error" indicating the parity bit. If the parity bit is correct, then single error correction will indicate the (bitwise) exclusive-or of two error locations. If the locations are equal ("no error") then a double bit error either has not occurred, or has cancelled itself out. Otherwise, a double bit error has occurred.

Notes

↑See Lemma 12 of
↑Hamming (1950), pp. 153–154.
↑Thompson, Thomas M. (1983), From Error-Correcting Codes through Sphere Packings to Simple Groups, The Carus Mathematical Monographs (#21), Mathematical Association of America, pp. 16–17, ISBN 0-88385-023-0
1 2 3Kythe & Kythe 2012, p. 115.
↑Kythe & Kythe 2012, p. 95.
1 2Moon T. Error correction coding: Mathematical Methods and Algorithms. John Wiley and Sons, 2005.(Cap. 3) ISBN 978-0-471-64800-0

References

Hamming, Richard Wesley (1950). "Códigos de detección y corrección de errores" ( PDF) . Bell System Technical Journal . 29 (2): 147– 160. doi : 10.1002/j.1538-7305.1950.tb00463.x . hdl : 10945/46756 . S2CID 61141773. Archivado (PDF) del original el 9 de octubre de 2022.
Moon, Todd K. (2005). Codificación de corrección de errores . Nueva Jersey : John Wiley & Sons . ISBN 978-0-471-64800-0.
MacKay, David JC (septiembre de 2003). Teoría de la información, inferencia y algoritmos de aprendizaje . Cambridge : Cambridge University Press . ISBN 0-521-64298-1.
DK Bhattacharryya, S. Nandi. "Una clase eficiente de códigos SEC-DED-AUED". Simposio Internacional de Arquitecturas Paralelas, Algoritmos y Redes de 1997 (ISPAN '97) . págs. 410–415 . doi : 10.1109/ISPAN.1997.645128 .
"Desafío matemático de abril de 2013: Códigos de corrección de errores" (PDF) . Equipo directivo de swissQuant Group . Abril de 2013. Archivado (PDF) del original el 12 de septiembre de 2017.
Kythe, Dave K.; Kythe, Prem K. (2012). «Códigos de Hamming extendidos» . Teoría de la codificación algebraica y estocástica . CRC Press. págs. 95–116 . ISBN 978-1-351-83245-8.

Enlaces externos

Explicación visual de los códigos de Hamming
Script CGI para calcular distancias de Hamming (de R. Tervo, UNB, Canadá)
Herramienta para calcular el código de Hamming

[1] See Lemma 12 of

[FOOTNOTEHamming1950153–154-2] Hamming (1950), pp. 153–154.

[3] Thompson, Thomas M. (1983), From Error-Correcting Codes through Sphere Packings to Simple Groups, The Carus Mathematical Monographs (#21), Mathematical Association of America, pp. 16–17, ISBN 0-88385-023-0

[FOOTNOTEKytheKythe2012115-4] 1 2 3Kythe & Kythe 2012, p. 115.

[FOOTNOTEKytheKythe201295-5] Kythe & Kythe 2012, p. 95.

[Moon-6] 1 2Moon T. Error correction coding: Mathematical Methods and Algorithms. John Wiley and Sons, 2005.(Cap. 3) ISBN 978-0-471-64800-0

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]