Código de Hamming

En informática y telecomunicaciones , los códigos de Hamming son una familia de códigos de corrección de errores lineales . 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 elaboró su idea general, pero se centró específicamente en el código Hamming(7,4) que agrega 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ódigo lineal binario. Para cada entero $r \geq 2$ hay una palabra de 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 códigos de Hamming es $R = k / n = 1 - r / (2 r - 1)$ , que es la más alta posible para códigos con una distancia mínima de tres (es decir, el número mínimo de cambios de bit necesarios para ir de cualquier palabra de código a cualquier otra palabra de código es tres) y una longitud de bloque $2 r - 1$ . La matriz de comprobación de paridad de un código de Hamming se construye enumerando todas las columnas de longitud $r$ que no sean 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 comprobación de paridad tiene la propiedad de que dos columnas cualesquiera son linealmente independientes por pares .

Debido a la redundancia limitada que los códigos Hamming añaden a los datos, sólo pueden detectar y corregir errores cuando la tasa de errores es baja. Este es el caso de la memoria de ordenador (normalmente RAM), donde los errores de bit son extremadamente raros y los códigos Hamming son ampliamente utilizados, y una RAM con este sistema de corrección es una RAM ECC ( memoria ECC ). En este contexto, se suele utilizar un código Hamming extendido que tiene un bit de paridad extra. Los códigos Hamming extendidos alcanzan una distancia Hamming de cuatro, lo que permite al decodificador distinguir entre cuando se produce como máximo un error de un bit y cuando se produce cualquier error de dos bits. En este sentido, los códigos Hamming extendidos son de corrección de un solo error y de detección de doble error, abreviados como SECDED .

Historia

Richard Hamming , el inventor de los códigos Hamming, trabajó en Bell Labs a finales de los años 40 en el ordenador Bell Model V , una máquina electromecánica basada en relés con tiempos de ciclo en segundos. La entrada se introducía en una cinta de papel perforada , de siete octavos de pulgada de ancho, que tenía 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 para que los operadores pudieran corregir el problema. Durante los períodos fuera del horario laboral y los fines de semana, cuando no había operadores, la máquina simplemente pasaba al siguiente trabajo.

Hamming trabajaba los fines de semana y cada vez le frustraba más tener que reiniciar sus programas desde cero debido a los errores detectados. En una entrevista grabada, Hamming dijo: "Y 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 siguientes años, trabajó en el problema de la corrección de errores, desarrollando una serie de algoritmos cada vez más potentes. En 1950, publicó lo que ahora se conoce como código Hamming, que sigue utilizándose hoy en día en aplicaciones como la memoria ECC .

Códigos anteriores a Hamming

Antes de los códigos Hamming se utilizaron varios códigos simples de detección de errores, pero ninguno fue tan efectivo como los códigos Hamming en el mismo espacio adicional.

Paridad

La paridad añade un único bit que indica si el número de unos (posiciones de bit con valores de uno) en los datos anteriores era par o impar . Si se cambia un número impar de bits durante la transmisión, el mensaje cambiará de paridad y el error se puede detectar en este punto; sin embargo, el bit que cambió puede haber sido el bit de paridad en sí. 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 cambiados es par, el bit de verificación será válido y no se detectará el error.

Además, la paridad no indica qué bit contiene 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 tal vez nunca ocurra. Sin embargo, si bien la calidad de la verificación de paridad es deficiente, ya que utiliza solo un bit, este método genera la menor sobrecarga.

Código dos de cinco

Un código de dos de cinco es un esquema de codificación que utiliza cinco bits que consisten en exactamente tres 0 y dos 1. Esto proporciona 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 bit impares y algunos errores de bit pares (por ejemplo, la inversión de ambos bits 1). Sin embargo, todavía no puede corregir ninguno de estos errores. ${\binom {5}{3}}=10$

Repetición

Otro código que se utilizaba en aquella época repetía cada bit de datos varias veces para garantizar que se enviaba correctamente. Por ejemplo, si el bit de datos que se iba a enviar era un 1, un código de repetición n = 3 enviaría 111. Si los tres bits recibidos no eran idénticos, se produjo un error durante la transmisión. Si el canal estaba lo suficientemente limpio, la mayoría de las veces solo cambiaría un bit en cada triple. Por lo tanto, 001, 010 y 100 corresponden cada uno a un bit 0, mientras que 110, 101 y 011 corresponden a un bit 1, y la mayor cantidad de dígitos que son iguales ('0' o '1') indican 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 de corrección de errores . Este código de repetición triple es un código de 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 reparar correctamente todos los errores. En nuestro ejemplo, si el canal cambia dos bits y el receptor obtiene 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 podemos 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 errores de tres bits.

Además, aumentar el tamaño de la cadena de bits de paridad es ineficiente, ya que reduce el rendimiento tres veces en nuestro caso original, y la eficiencia cae drásticamente a medida que aumentamos el número 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 esos bits se pueden organizar de manera que distintos bits incorrectos produzcan distintos resultados de error, se podrían identificar los bits incorrectos. En un mensaje de siete bits, hay siete posibles errores de un solo bit, por lo que tres bits de control de errores podrían especificar potencialmente no solo que se produjo un error, sino también qué bit lo causó.

Hamming estudió los esquemas de codificación existentes, incluido el dos de cinco, y generalizó sus conceptos. Para empezar, desarrolló una nomenclatura para describir el sistema, que incluía el número de bits de datos y bits de corrección de errores en un bloque. Por ejemplo, la paridad incluye un solo bit para cualquier palabra de datos, por lo que, suponiendo que las palabras ASCII tuvieran siete bits, Hamming las 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 código es el segundo número dividido por el primero, para nuestro ejemplo de repetición, 1/3.

Hamming también notó los problemas con la inversión de dos o más bits, y describió esto como la "distancia" (ahora se llama la distancia de Hamming , en su honor). La paridad tiene una distancia de 2, por lo que una inversión de bit puede detectarse pero no corregirse, y cualquier inversión de dos bits será invisible. La repetición (3,1) tiene una distancia de 3, ya que se deben invertir tres bits en el mismo triple para obtener otra palabra de código sin errores visibles. Puede corregir errores de un bit o puede 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 invertir tres bits puede detectarse, pero no corregirse. Cuando se invierten tres bits en el mismo grupo, puede haber situaciones en las que intentar corregir producirá la palabra de código incorrecta. En general, un código con una distancia k puede detectar, pero no corregir, k − 1 errores.

Hamming se interesó en dos problemas a la vez: aumentar la distancia tanto como fuera posible y, al mismo tiempo, aumentar la tasa de codificación tanto como fuera posible. Durante la década de 1940, desarrolló varios esquemas de codificación que supusieron mejoras espectaculares respecto de los códigos existentes. La clave de todos sus sistemas era que los bits de paridad se superpusieran, de modo que pudieran comprobarse entre sí y también los datos.

Algoritmo general

El siguiente algoritmo general genera un código de corrección de un solo error (SEC) para cualquier número de bits. La idea principal es elegir los bits de corrección de errores de manera que el índice XOR (el XOR de todas las posiciones de bit 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 configurar los bits de corrección de errores de manera 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 corrupciones y, de lo contrario, el índice XOR indica el índice del bit dañado.

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

Numera los bits empezando por 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 bit 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 determina la forma binaria de su posición de bit.
1. El bit de paridad 1 cubre todas las posiciones de bit que tienen el bit menos significativo establecido: bit 1 (el bit de paridad en sí), 3, 5, 7, 9, etc.
2. El bit de paridad 2 cubre todas las posiciones de bit que tienen establecido el segundo bit menos significativo: bits 2-3, 6-7, 10-11, etc.
3. El bit de paridad 4 cubre todas las posiciones de bit que tienen establecido el tercer bit menos significativo: bits 4–7, 12–15, 20–23, etc.
4. El bit de paridad 8 cubre todas las posiciones de bit que tienen establecido el cuarto bit menos significativo: bits 8–15, 24–31, 40–47, etc.
5. En general, cada bit de paridad cubre todos los bits donde el AND bit a bit de la posición de paridad y la posición de bit es distinto 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:

Se muestran solo 20 bits codificados (5 de paridad, 15 de datos), pero el patrón continúa indefinidamente. La clave de los códigos de Hamming que se puede ver a simple vista es que cualquier bit dado está incluido en un conjunto único de bits de paridad. Para comprobar si hay errores, compruebe todos los bits de paridad. El patrón de errores, llamado 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, el bit de paridad en sí es erróneo.

Con $m$ bits de paridad, se pueden cubrir los bits desde 1 hasta . Después de descontar los bits de paridad, quedan bits para usar como datos. A medida que $m$ varía, obtenemos todos los códigos de Hamming posibles: $Estilo de visualización 2^{m}-1$ $Estilo de visualización 2^{m}-m-1}$

Códigos Hamming con paridad adicional (SECDED)

Los códigos 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 alguna palabra de código de un error de un solo bit de una palabra de código diferente. Por lo tanto, algunos errores de doble bit se decodificarán incorrectamente como si fueran errores de un solo bit y, por lo tanto, no se detectarán, a menos que no se intente ninguna corrección.

Para solucionar este inconveniente, los códigos Hamming se pueden ampliar con un bit de paridad adicional. De esta forma, es posible aumentar la distancia mínima del código Hamming a 4, lo que permite al decodificador distinguir entre errores de un solo bit y errores de dos bits. De esta forma, 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 manera confiable errores de tres bits. Si el decodificador corrige errores, algunos errores triples se confundirán con errores simples y se "corregirán" con el valor incorrecto. Por lo tanto, la corrección de errores es un equilibrio entre la certeza (la capacidad de detectar de manera confiable errores de tres bits) y la resiliencia (la capacidad de seguir funcionando ante errores de un solo bit).

Este código Hamming extendido fue popular en los sistemas de memoria de computadora, comenzando con IBM 7030 Stretch en 1961, ^[4] donde se lo conoce como SECDED (o SEC-DED, abreviatura de corrección de error único, detección de error doble ). ^[5] 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, confiando en cambio en los diseños con palabras de código más largas (128 a 256 bits de datos) y árboles de verificación de paridad balanceada modificados. ^[4] El código Hamming (72,64) aún es popular en algunos diseños de hardware, incluidas las familias FPGA de Xilinx . ^[4]

[7,4] Código de Hamming

Representación gráfica de los cuatro bits de datos y 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 código 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 puede detectar (pero no corregir) errores tanto de un solo bit como de dos bits.

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

Construcción de G y H

La matriz se denomina matriz generadora (canónica) de un código lineal ( n , k ), $\mathbf {G} :={\begin{pmatrix}{\begin{array}{c|c}I_{k}&-A^{\text{T}}\\\end{array}}\end{pmatrix}}$

y se llama matriz de verificación de paridad . $\mathbf {H} :={\begin{pmatrix}{\begin{array}{c|c}A&I_{nk}\\\end{array}}\end{pmatrix}}$

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 todos ceros. ^[6]

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

Por lo tanto, H es una matriz cuyo lado izquierdo son todas las n -tuplas distintas de cero, 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 ) .

Por lo tanto, G puede obtenerse a partir de H tomando la transpuesta del lado izquierdo de H con la matriz identidad k en el lado izquierdo de G.

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

$\mathbf {G} :={\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}}_{4,7}$

$\mathbf {H} :={\begin{pmatrix}1&1&0&1&1&0&0\\1&0&1&1&0&1&0\\0&1&1&1&0&0&1\end{pmatrix}}_{3,7}.$

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

Permutaciones de columnas (intercambio de columnas)
Operaciones elementales de filas (reemplazar una fila con una combinación lineal de filas)

Codificación

Ejemplo

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

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

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

El mismo ejemplo [7,4] de arriba con un bit de paridad adicional. Este diagrama no pretende corresponderse con la matriz H de este ejemplo.

El código Hamming [7,4] se puede ampliar 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} :={\begin{pmatrix}1&1&1&0&0&0&0&1\\1&0&0&1&1&0&0&1\\0&1&0&1&0&1&0&1\\1&1&0&1&0&0&1&0\end{pmatrix}}_{4,8}

\mathbf {H} :={\begin{pmatrix}1&0&1&0&1&0&1&0\\0&1&1&0&0&1&1&0\\0&0&0&1&1&1&1&0\\1&1&1&1&1&1&1&1\end{pmatrix}}_{4,8}.

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 la tercera fila de H en forma no sistemática. Si se utiliza la construcción sistemática de los 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 de fila elementales) para que coincida con esta matriz.

La adición de la cuarta fila calcula efectivamente la suma de todos los bits de la palabra código (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) en 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 agregado por el código [8,4]. El dígito verde hace que la paridad de las palabras de código [7,4] sea uniforme.

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 puede definirse como código 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 error simple (el código Hamming [7,4]) indicará la ubicación del error, y "sin error" indicará el bit de paridad. Si el bit de paridad es correcto, entonces la corrección de error simple indicará la operación exclusiva-o (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 se ha cancelado a sí mismo. 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), Desde códigos de corrección de errores hasta empaquetamientos de esferas y grupos simples, The Carus Mathematical Monographs (#21), Mathematical Association of America, págs. 16-17, ISBN 0-88385-023-0
^ abc Kythe y Kythe 2017, pág. 115.
^ Kythe y Kythe 2017, pág. 95.
^ ab Moon T. Codificación de corrección de errores: métodos y algoritmos matemáticos. 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. S2CID 61141773. Archivado (PDF) desde el original el 2022-10-09.
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 sobre arquitecturas paralelas, algoritmos y redes (ISPAN '97) de 1997. 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 del grupo swissQuant. Abril de 2013. Archivado (PDF) desde el original el 12 de septiembre de 2017.
Kythe, Dave K.; Kythe, Prem K. (28 de julio de 2017). "Códigos de Hamming extendidos". Teoría de 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 Hamming