código hammam

En informática y telecomunicaciones , los códigos Hamming son una familia de códigos lineales de corrección de errores . Los códigos 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 sólo puede detectar un número impar de bits erróneos. Los códigos Hamming son códigos perfectos , es decir, logran 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 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 suma tres bits de paridad a cuatro bits de datos. ^[2]

En términos matemáticos , los códigos Hamming son una clase de código lineal binario. Para cada número entero $r \geq 2$ hay una palabra de código con una longitud de bloque $n = 2 r - 1$ y una longitud de mensaje $k = 2 r - r - 1$ . Por lo tanto, la tasa de códigos 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 bits necesarios para pasar de cualquier palabra de código a cualquier otra palabra de código es tres) y la longitud del bloque es $2 r - 1$ . La matriz de verificación de paridad de un código Hamming se construye enumerando todas las columnas de longitud $r$ distintas de cero, lo que significa que el código dual del código 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 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 error es baja. Este es el caso de la memoria de los ordenadores (normalmente la RAM), donde los errores de bits son extremadamente raros y los códigos Hamming son muy utilizados, y una RAM con este sistema de corrección es una RAM ECC ( memoria ECC ). En este contexto, a menudo se utiliza un código Hamming extendido que tiene un bit de paridad adicional. Los códigos Hamming extendidos alcanzan una distancia de Hamming de cuatro, lo que permite al decodificador distinguir entre cuándo ocurre como máximo un error de un bit y cuándo ocurre cualquier error de dos bits. En este sentido, los códigos Hamming extendidos son de corrección de error simple y detección de error doble, 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 en la computadora Bell Modelo V , una máquina electromecánica basada en relés con tiempos de ciclo en segundos. La entrada se realizaba mediante 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 parpadeaba las luces para que los operadores pudieran corregir el problema. Durante los períodos fuera de horario 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 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: "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 hoy 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

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

Paridad

La paridad agrega un solo bit que indica si el número de unos (posiciones de bits con valores de uno) en los datos anteriores era par o impar . Si se cambia un número impar de bits en la transmisión, el mensaje cambiará de paridad y el error podrá detectarse en este punto; sin embargo, el bit que cambió puede haber sido 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 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 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 nunca ocurrir. 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 dos de cinco es un esquema de codificación que utiliza cinco bits que constan exactamente de tres ceros y dos unos. 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 bits impares y algunos errores de bits 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 en uso en ese momento repetía cada bit de datos varias veces para garantizar que se enviara correctamente. Por ejemplo, si el bit de datos a enviar es 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 está lo suficientemente limpio, la mayoría de las veces solo cambiará un bit en cada triplete. 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, indicando la mayor cantidad de dígitos iguales ('0' o '1') qué el bit de datos debería ser. 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 triple repetición 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, dichos códigos no pueden reparar correctamente todos los errores. En nuestro ejemplo, si el canal invierte 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 con un mensaje, y si esos bits se pueden organizar de manera que diferentes bits incorrectos produzcan diferentes resultados de error, entonces se podrían identificar bits defectuosos. 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 no sólo que ocurrió un error sino también qué bit lo causó.

Hamming estudió los esquemas de codificación existentes, incluidos dos de cinco, y generalizó sus conceptos. Para empezar, desarrolló una nomenclatura para describir el sistema, incluida la cantidad 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 palabras ASCII con siete bits, Hamming describió esto 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 al invertir dos o más bits, y lo describió como la "distancia" (ahora se llama distancia de Hamming , en su honor). La paridad tiene una distancia de 2, por lo que se puede detectar un cambio de bit pero no corregirlo, y cualquier cambio de dos bits será invisible. La repetición (3,1) tiene una distancia de 3, ya que es necesario 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 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 corregir producirá 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 tanto como fuera posible y al mismo tiempo aumentar la velocidad del código tanto como fuera posible. Durante la década de 1940 desarrolló varios esquemas de codificación que supusieron mejoras espectaculares con respecto a 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 con los datos.

Algoritmo general

El siguiente algoritmo general genera un código de corrección de error único (SEC) para cualquier número de bits. La idea principal es elegir los bits de corrección de errores de modo 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 error. -bits de corrección, que garantiza que es posible configurar los bits de corrección de errores para 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.

Un algoritmo se puede deducir de la siguiente descripción:

Numere 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 bits que son potencias de dos (tienen un único 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 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 determinado por 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 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 bits que tienen configurado 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 el tercer bit menos significativo configurado: bits 4 a 7, 12 a 15, 20 a 23, etc.
4. El bit de paridad 8 cubre todas las posiciones de bits que tienen el cuarto bit menos significativo configurado: 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 del bit son distintos 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 sería 011100101010.

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

Esta regla general se puede mostrar visualmente:

Se muestran sólo 20 bits codificados (5 de paridad, 15 de datos), pero el patrón continúa indefinidamente. La clave de los códigos Hamming que se puede ver mediante inspección visual es que cualquier bit determinado está incluido en un conjunto único de bits de paridad. Para comprobar si hay errores, verifique 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 está en error. Si sólo un bit de paridad indica un error, el bit de paridad en sí está en error.

Con $m$ bits de paridad se pueden cubrir bits desde 1 hasta . Después de descontar los bits de paridad, quedan bits para su uso como datos. Como $m$ varía, obtenemos todos los códigos Hamming posibles: $2^{m}-1$ $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 corregirlos.

Para remediar esta deficiencia, los códigos Hamming se pueden ampliar con un bit de paridad adicional. De esta manera, 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. Así, el decodificador puede detectar y corregir un único error y al mismo tiempo detectar (pero no corregir) un doble error.

Si el decodificador no intenta corregir los errores, puede detectar de forma fiable errores de triple bit. Si el decodificador corrige los 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 una compensación entre certeza (la capacidad de detectar de manera confiable errores de tres bits) y resiliencia (la capacidad de seguir funcionando frente a errores de un solo bit).

Este código Hamming extendido fue popular en los sistemas de memoria de las computadoras, comenzando con IBM 7030 Stretch en 1961, ^[4] donde se lo conoce como SECDED (o SEC-DED, abreviado de corrección de error simple, detección de error doble ). ^[5] Las computadoras servidor en el siglo XXI, aunque normalmente mantienen el nivel de protección SECDED, ya no usan el método de Hamming, sino que confían 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) sigue siendo popular en algunos diseños de hardware, incluidas las familias de FPGA Xilinx . ^[4]

[7,4] Código 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]. Codifica cuatro bits de datos en siete bits sumando tres bits de paridad. Como se explicó anteriormente, puede detectar y corregir errores de un solo bit o puede detectar (pero no corregir) errores de uno y dos bits.

Con la adición de un bit de paridad general, se convierte en el código Hamming extendido [8,4] que es SECDED 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 llama 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{pmatriz}}$

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

Ésta 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 verificación de paridad H de un código Hamming se construye enumerando todas las columnas de longitud m que son independientes por 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 ) .

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

La matriz del generador de código y la matriz de verificació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 se pueden transformar en códigos no sistemáticos equivalentes mediante las siguientes operaciones: ^[6]

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

Codificación

Ejemplo

De la matriz anterior tenemos 2 ^k = 2 ⁴ = 16 palabras en código. Sea un vector de fila de bits de datos binarios, . La palabra clave para cualquiera de los 16 vectores de datos posibles viene dada por el producto matricial estándar donde la operación de suma se realiza 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, dejemos . Usando la matriz generadora de arriba, tenemos (después de aplicar el módulo 2 a la suma), ${\vec {a}}=[1,0,1,1]$ $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] anterior con un bit de paridad adicional. Este diagrama no pretende corresponder a la matriz H de este ejemplo.

El código Hamming [7,4] se puede extender fácilmente a un código [8,4] agregando un bit de paridad adicional encima de la palabra codificada (7,4) (consulte 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}.

Tenga en cuenta 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 fila de H en forma no sistemática. Utilizando la construcción sistemática de los códigos de Hamming anterior, 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 (usando operaciones elementales de filas) para que coincida con esta matriz.

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

Por ejemplo, 1011 está codificado (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 iguala la paridad de las palabras en código [7,4].

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 [8,4] código Hamming.

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 única (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 única indicará la 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 se ha cancelado. De lo contrario, se ha producido un error de doble bit.

Ver también

Notas

^ Ver 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 hasta grupos simples, The Carus Mathematical Monographs (n.° 21), Asociación Matemática de América, págs. 16-17, ISBN 0-88385-023-0
^ abc Kythe y Kythe 2017, pag. 115.
^ Kythe y Kythe 2017, pag. 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) . Revista técnica del sistema Bell . 29 (2): 147–160. doi :10.1002/j.1538-7305.1950.tb00463.x. S2CID 61141773. Archivado (PDF) desde el original el 9 de octubre de 2022.
Luna, 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 : Prensa de la Universidad de Cambridge . ISBN 0-521-64298-1.
DK Bhattacharryya, S. Nandi. "Una clase eficiente de códigos SEC-DED-AUED". 1997 Simposio Internacional sobre Arquitecturas, Algoritmos y Redes Paralelas (ISPAN '97) . págs. 410–415. doi :10.1109/ISPAN.1997.645128.
"Mathematical Challenge abril de 2013 Códigos de corrección de errores" (PDF) . Equipo de liderazgo 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 Hamming extendidos". Teoría de codificación algebraica y estocástica . Prensa CRC. págs. 95-116. ISBN 978-1-351-83245-8.

enlaces externos

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