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

El siguiente algoritmo general genera un código de corrección de errores simple (SEC) para cualquier número de bits. La idea principal es elegir los bits de corrección de errores de tal manera que el índice-XOR (el XOR de todas las posiciones de bits que contienen un 1) sea 0. Usamos las posiciones 1, 10, 100, etc. (en binario) como bits de corrección de errores, lo que garantiza que sea posible configurarlos de modo que el índice-XOR de todo el mensaje sea 0. Si el receptor recibe una cadena con índice-XOR 0, puede concluir que no hubo errores; de lo contrario, el índice-XOR indica el índice del bit corrupto.

Se puede deducir un algoritmo a partir de la siguiente descripción:

Numera los bits comenzando desde 1: bit 1, 2, 3, 4, 5, 6, 7, etc.
Escribe los números de bits en binario: 1, 10, 11, 100, 101, 110, 111, etc.
Todas las posiciones de bits que son potencias de dos (tienen un solo bit 1 en la forma binaria de su posición) son bits de paridad: 1, 2, 4, 8, etc. (1, 10, 100, 1000).
Todas las demás posiciones de bits, con dos o más bits 1 en la forma binaria de su posición, son bits de datos.
Cada bit de datos se incluye en un conjunto único de 2 o más bits de paridad, según lo determine la forma binaria de su posición de bit.
1. El bit de paridad 1 cubre todas las posiciones de bits que tienen el bit menos significativo activado: bit 1 (el bit de paridad en sí), 3, 5, 7, 9, etc.
2. El bit de paridad 2 cubre todas las posiciones de bits que tienen activado el segundo bit menos significativo: bits 2-3, 6-7, 10-11, etc.
3. El bit de paridad 4 cubre todas las posiciones de bits que tienen activado el tercer bit menos significativo: bits 4–7, 12–15, 20–23, etc.
4. El bit de paridad 8 cubre todas las posiciones de bits que tienen activado el cuarto bit menos significativo: bits 8–15, 24–31, 40–47, etc.
5. En general, cada bit de paridad abarca todos los bits donde la operación AND bit a bit entre la posición de paridad y la posición del bit es distinta de cero.

Si un byte de datos a codificar es 10011010, entonces la palabra de datos (usando _ para representar los bits de paridad) sería __1_001_1010, y la palabra de código es 011100101010.

La elección de la paridad, par o impar, es irrelevante, pero debe utilizarse la misma elección tanto para la codificación como para la decodificación.

Esta regla general se puede mostrar visualmente:

Aquí solo se muestran 20 bits codificados (5 de paridad y 15 de datos), pero el patrón continúa indefinidamente. La clave de los códigos de Hamming, visible a simple vista, es que cada bit se incluye en un conjunto único de bits de paridad. Para detectar errores, se deben revisar todos los bits de paridad. El patrón de errores, denominado síndrome de error , identifica el bit erróneo. Si todos los bits de paridad son correctos, no hay error. De lo contrario, la suma de las posiciones de los bits de paridad erróneos identifica el bit erróneo. Por ejemplo, si los bits de paridad en las posiciones 1, 2 y 8 indican un error, entonces el bit 1+2+8=11 es erróneo. Si solo un bit de paridad indica un error, ese bit de paridad es el erróneo.

Con $m$ bits de paridad, bits desde 1 hasta $2^{m}-1$ puede cubrirse. Después de descontar los bits de paridad, $2^{m}-m-1$ Los bits se conservan para su uso como datos. A medida que $m$ varía, obtenemos todos los códigos de Hamming posibles:

Códigos de Hamming con paridad adicional (SECDED)

Los códigos de Hamming tienen una distancia mínima de 3, lo que significa que el decodificador puede detectar y corregir un solo error, pero no puede distinguir un error de doble bit de una palabra clave de un error de un solo bit de otra palabra clave. Por lo tanto, algunos errores de doble bit se decodificarán incorrectamente como si fueran errores de un solo bit y, en consecuencia, pasarán desapercibidos, a menos que se intente corregirlos.

Para remediar esta deficiencia, los códigos de Hamming se pueden extender con un bit de paridad adicional. De esta forma, es posible aumentar la distancia mínima del código de Hamming a 4, lo que permite al decodificador distinguir entre errores de un bit y errores de dos bits. Así, el decodificador puede detectar y corregir un error simple y, al mismo tiempo, detectar (pero no corregir) un error doble. Si el decodificador no intenta corregir errores, puede detectar de forma fiable errores de tres bits. Si el decodificador corrige errores, algunos errores de tres bits se confundirán con errores simples y se "corregirán" al valor incorrecto. Por lo tanto, la corrección de errores implica un equilibrio entre la certeza (la capacidad de detectar de forma fiable errores de tres bits) y la resiliencia (la capacidad de seguir funcionando ante errores de un solo bit).

Para k bits de datos, un esquema SECDED requiere:

Sea q la primera potencia de 2 mayor que k .
Sea l el piso (log ₂ ( k )) y h 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 ]}

Dado que [7, 4, 3] = [ n , k , d ] = [2 ^m − 1, 2 ^m − 1 − m , 3]. La matriz de verificación de paridad H de un código de Hamming se construye enumerando todas las columnas de longitud m que son independientes por pares.

Así, H es una matriz cuyo lado izquierdo son todas las n- tuplas no nulas, donde el orden de las n- tuplas en las columnas de la matriz no importa. El lado derecho es simplemente la matriz identidad ( n − k ) .

Entonces G se puede obtener de H tomando la transpuesta del lado izquierdo de H con la matriz identidad k - matriz identidad en el lado izquierdo de G.

La matriz generadora de código $\mathbf {G}$ y la matriz de verificación de paridad $\mathbf {H}$ son:

$\mathbf {G$

y

$\mathbf {H$

Finalmente, estas matrices pueden ser mutadas en códigos no sistemáticos equivalentes mediante las siguientes operaciones: ^{[ 6 ]}

Permutaciones de columnas (intercambio de columnas)
Operaciones elementales de fila (sustituir una fila por una combinación lineal de filas)

Codificación

Ejemplo

De la matriz anterior tenemos 2 ^k = 2 ⁴ = 16 palabras clave. Sea ${\vec {a}}$ sea un vector fila de bits de datos binarios, ${\vec {a}}=[a_{1},a_{2},a_{3},a_{4}],\quad a_{i}\in \{0,1\}$ La palabra clave ${\vec {x}}$ para cualquiera de los 16 vectores de datos posibles ${\vec {a}}$ viene dado por el producto matricial estándar ${\vec {x}}={\vec {a}}G$ donde la operación de suma se realiza módulo 2.

Por ejemplo, dejemos ${\vec {a}}=[1,0,1,1]$ . Utilizando la matriz generadora $G$ De arriba, tenemos (después de aplicar módulo 2 a la suma),

${\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] Código de Hamming con un bit de paridad adicional

El mismo ejemplo [7,4] anterior con un bit de paridad adicional. Este diagrama no corresponde a la matriz H de este ejemplo.

El código Hamming [7,4] se puede extender fácilmente a un código [8,4] añadiendo un bit de paridad adicional sobre la palabra codificada (7,4) (véase Hamming(7,4) ). Esto se puede resumir con las matrices revisadas:

\mathbf {G

y

\mathbf {H

Nótese que H no está en forma estándar. Para obtener G, se pueden utilizar operaciones elementales de fila para obtener una matriz equivalente a H en forma sistemática:

\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}.

Por ejemplo, la primera fila de esta matriz es la suma de la segunda y tercera filas de H en forma no sistemática. Utilizando la construcción sistemática para códigos de Hamming de arriba, la matriz A es evidente y la forma sistemática de G se escribe como

\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}.

La forma no sistemática de G se puede reducir por filas (utilizando operaciones elementales de fila) para que coincida con esta matriz.

La adición de la cuarta fila calcula efectivamente la suma de todos los bits de la palabra clave (datos y paridad) como el cuarto bit de paridad.

Por ejemplo, 1011 se codifica (usando la forma no sistemática de G al comienzo de esta sección) como 01 1 0 011 0, donde los dígitos azules son datos; los dígitos rojos son bits de paridad del código Hamming [7,4]; y el dígito verde es el bit de paridad añadido por el código [8,4]. El dígito verde hace que la paridad de las palabras clave [7,4] sea par.

Finalmente, se puede demostrar que la distancia mínima ha aumentado de 3, en el código [7,4], a 4 en el código [8,4]. Por lo tanto, el código se puede definir como el código de Hamming [8,4].

Para decodificar el código Hamming [8,4], primero verifique el bit de paridad. Si el bit de paridad indica un error, la corrección de un solo error (el código Hamming [7,4]) indicará la ubicación del error, donde "sin error" indica el bit de paridad. Si el bit de paridad es correcto, la corrección de un solo error indicará la operación OR exclusiva (bit a bit) de dos ubicaciones de error. Si las ubicaciones son iguales ("sin error"), entonces no se ha producido un error de doble bit o este se ha cancelado. De lo contrario, se ha producido un error de doble bit.

Véase también

Notas

↑ Véase el Lema 12 de
↑ Hamming (1950) , págs. 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 3 Kythe y Kythe 2012 , pág. 115.
↑ Kythe y Kythe 2012 , pág. 95.
1 2 Moon T. Codificación de corrección de errores: Métodos matemáticos y algoritmos. John Wiley and Sons, 2005. (Cap. 3) ISBN 978-0-471-64800-0

Referencias

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] Véase el Lema 12 de

[FOOTNOTEHamming1950153–154-2] Hamming (1950) , págs. 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 3 Kythe y Kythe 2012 , pág. 115.

[FOOTNOTEKytheKythe201295-5] Kythe y Kythe 2012 , pág. 95.

[Moon-6] 1 2 Moon T. Codificación de corrección de errores: Métodos matemáticos y algoritmos. John Wiley and Sons, 2005. (Cap. 3) ISBN 978-0-471-64800-0

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]