Codigo hamming

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Familia de códigos lineales de corrección de errores

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 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 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. 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 agrega tres bits de paridad a cuatro bits de datos.

En términos matemáticos, los códigos de Hamming son una clase de código lineal binario. Para cada número entero $r \geq 2$ hay una palabra clave con longitud de bloque $n = 2 r - 1$ y longitud del 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 el mayor 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 $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 no son cero, lo que significa que el código dual de el código Hamming es el código Hadamard abreviado. 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 agregan 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 bit 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 usa un código de Hamming extendido que tiene un bit de paridad extra. Los códigos de Hamming extendidos logran una distancia de Hamming de cuatro, lo que permite que el decodificador distinga 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 de 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 fines de la década de 1940 en la computadora Bell Model V, una máquina electromecánica basada en relés con tiempos de ciclo en segundos. La entrada se introdujo en una cinta de papel perforada, de siete octavos de pulgada de ancho, que tenía hasta seis orificios por fila. Durante los días de semana, cuando se detectaban errores en los relés, la máquina se detenía y las luces parpadeaban 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 los errores detectados. En una entrevista grabada, Hamming dijo: "Entonces dije: 'Maldita sea, si la máquina puede detectar un error, ¿por qué no puede ubicar la posición del error y corregirlo?" #39;". Durante los años siguientes, 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 en uso 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 de Hamming, pero ninguno fue tan eficaz como los códigos de Hamming en la misma sobrecarga de espacio.

Paridad

La paridad agrega un solo 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 en 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 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 llevar 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 consisten exactamente en tres 0 y dos 1. Esto proporciona diez combinaciones posibles, suficientes para representar los dígitos del 0 al 9. Este esquema puede detectar todos los errores de bits individuales, todos los errores de bits impares y algunos errores de bits pares (por ejemplo, el volteo de ambos bits 1). Sin embargo, todavía no puede corregir ninguno de estos errores.

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 un 1, un n = 3 código de repetición 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 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, siendo la mayor cantidad de dígitos iguales ('0' o un & #39;1') que indica cuál debe 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 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, reduce el rendimiento tres veces en nuestro caso original, y la eficiencia cae 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 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 los 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 solo que ocurrió un error sino también qué bit causó el error.

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 asumiendo palabras ASCII con 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 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 cambiar dos o más bits y describió esto como la "distancia" (ahora se llama distancia de Hamming, en honor a él). 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 se deben voltear 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 el volteo de tres bits, pero no se corrige. 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 distancia k puede detectar pero no corregir errores k − 1.

Hamming estaba interesado en dos problemas a la vez: aumentar la distancia tanto como fuera posible y, al mismo tiempo, aumentar la tasa de código tanto como fuera posible. Durante la década de 1940 desarrolló varios esquemas de codificación que fueron mejoras dramáticas en los códigos existentes. La clave de todos sus sistemas era que los bits de paridad se superpusieran, de modo que lograran verificarse entre sí y también con 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 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 el error -bits de corrección, lo 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 corrupción, y de lo contrario, el índice-XOR indica el índice del bit corrupto.

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

Número de los bits a partir de 1: bit 1, 2, 3, 4, 5, 6, 7, etc.
Escriba el número de bits en binario: 1, 10, 11, 100, 101, 110, 111, etc.
Todas las posiciones de bits que son poderes de dos (tienen un solo 1 bit en la forma binaria de su posición) son bits de paridad: 1, 2, 4, 8, etc. (1, 10, 100, 1000)
Todas las posiciones de bits, con dos o más 1 bits 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, determinado por la forma binaria de su posición bit.
1. Parity bit 1 cubre todas las posiciones de bits que tienen mínimo conjunto de bits significativos: bit 1 (la paridad en sí misma), 3, 5, 7, 9, etc.
2. Parity bit 2 cubre todas las posiciones de bits que tienen segundo mínimo importante bit set: bits 2-3, 6-7, 10-11, etc.
3. Parity bit 4 cubre todas las posiciones de bits que tienen tercero set mínimo significativo: bits 4–7, 12–15, 20–23, etc.
4. Parity bit 8 cubre todas las posiciones de bits que tienen cuarto set mínimo significativo: bits 8–15, 24–31, 40–47, etc.
5. En general, cada bit de paridad cubre todos los bits donde el bitwise AND de la posición de paridad y la posición del bit no es 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 se debe utilizar la misma elección tanto para la codificación como para la decodificación.

Esta regla general se puede mostrar visualmente:

bits de datos codificados		p1	p2	d1	p4	d2	d3	d4	p8	d5	d6	d7	d8	d9	d10	d11	p16	d12	d13	d14	d15
Posición de bits		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	...
Paridad bit cobertura	p1
	p2
	p4
	p8
	p16

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 partir de una inspección visual es que cualquier bit dado se incluye 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 un error. Si solo un bit de paridad indica un error, el bit de paridad mismo tiene un error.

Con $m$ bits de paridad, bits de 1 hasta 1 $2^{m}-1$ puede ser cubierto. Después de descartar los bits de paridad, $2^m-m-1$ bits permanecen para su uso como datos. As $m$ varies, obtenemos todos los códigos posibles de Hamming:

Parity bits	Total bits	bits de datos	Nombre	Tasa
2	3	1	Hamming(3,1) (Código de repetición triple)	1/3
3	7	4	Hamming(7,4)	4/7 ■ 0,571
4	15	11	Hamming(15,11)	11/15 ♥ 0,73
5	31	26	Hamming(31,26)	26/31 Entendido 0.839
6	63	57	Hamming(63,57)	57/63 ♥ 0,9005
7	127	120	Hamming(127,120)	120/127 ♥ 0,9445
8	255	247	Hamming(255,247)	247/255
...
$m$	${displaystyle n=2^{m}-1}$	${displaystyle k=2^{m}-m-1}$	Hamming $(2^m-1,2^m-m-1)$	$(2^m - m - 1)/(2^m-1)$

Códigos de 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 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, por lo tanto, no se detectarán, a menos que no se intente corregirlos.

Para remediar esta deficiencia, los códigos de 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 que el decodificador distinga entre errores de un solo bit y errores de dos bits. Así, el decodificador puede detectar y corregir un solo error y al mismo tiempo detectar (pero no corregir) un doble error.

Si el decodificador no intenta corregir los errores, puede detectar errores de tres bits de forma fiable. Si el decodificador corrige errores, algunos errores triples se confundirán con errores simples y se "corregirán" al valor incorrecto. Por lo tanto, la corrección de errores es un equilibrio entre la certeza (la capacidad de detectar errores de tres bits de forma fiable) y la 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, donde se conoce como SECDED (o SEC-DED, abreviado de corrección de error único, detección de doble error). Las computadoras de servidor en el siglo XXI, aunque generalmente mantienen el nivel de protección SECDED, ya no usan el método de Hamming, sino que confían en los diseños con palabras clave más largas (128 a 256 bits de datos) y árboles de verificación de paridad balanceados modificados. El código Hamming (72,64) sigue siendo popular en algunos diseños de hardware, incluidas las familias de FPGA de Xilinx.

[7,4] Código Hamming

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

En 1950, Hamming introdujo el código [7,4] Hamming. Codifica cuatro bits de datos en siete bits agregando tres bits de paridad. Puede detectar y corregir errores de un solo bit. Con la adición de un bit de paridad general, también puede detectar (pero no corregir) errores de doble bit.

Construcción de G y H

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

y ${mathbf {H}}:={begin{pmatrix}{begin{array}{c|c}A&I_{{n-k}}\end{array}}end{pmatrix}}$ se llama 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 bloque lineales deben satisfacer

${mathbf {H}},{mathbf {G}}^{{text{T}}}={mathbf {0}}$ , una matriz de queros.

Puesto 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 distintas de cero donde el orden de las n-tuplas en las columnas de matriz no importa. El lado derecho es solo la matriz de identidad (n − k).

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

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

${displaystyle 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&1end{pmatrix}}_{4,7}}$

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

Finalmente, estas matrices se pueden transformar en códigos no sistemáticos equivalentes mediante las siguientes operaciones:

Permutaciones de columnas (swapping columns)
Operaciones de fila elemental (replazando una fila con una combinación lineal de filas)

Codificación

Ejemplo

De la matriz anterior tenemos 2^k = 2⁴ = 16 palabras clave. Vamos ${vec {a}}$ ser un vector de fila de bits de datos binarios, ${displaystyle {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 ${displaystyle {vec {a}}}$ es dado por el producto matriz estándar $vec{x}=vec{a}G$ donde se realiza la operación de reposición modulo-2.

Por ejemplo, vamos ${displaystyle {vec {a}}=[1,0,1,1]}$ . Utilizando la matriz del generador $G$ de arriba, tenemos (después de aplicar el modulo 2, a la suma),

${displaystyle {vec {x}}={vec {a}}G={begin{pmatrix}1&0&1&1end{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&2end{pmatrix}}={begin{pmatrix}1&0&1&1&0&1&0end{pmatrix}}}$

[7,4] Código Hamming con un bit de paridad adicional

El mismo [7,4] ejemplo de arriba con un bit de paridad extra. Este diagrama no está destinado a corresponder a la matriz H para 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) (ver 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 usar 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&1end{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. Usando la construcción sistemática de los códigos de Hamming de arriba, la matriz A es aparente 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&0end{array}}right)_{{4,8}}.

La forma no sistemática de G se puede reducir por filas (usando operaciones elementales por filas) 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 está codificado (utilizando la forma no sistemática de G al comienzo de esta sección) en 0110 0110 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 de 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 de 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 un solo error (el código Hamming [7,4]) indicará la ubicación del error, con "sin error" indicando el bit de paridad. Si el bit de paridad es correcto, entonces la corrección de un solo error indicará el (bit a bit) exclusivo-o 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.

Contenido relacionado

Más resultados...