En la teoría de la codificación , Hamming (7,4) es un código de corrección de errores lineal que codifica cuatro bits de datos en siete bits agregando tres bits de paridad . Es miembro de una familia más grande de códigos de Hamming , pero el término código de Hamming a menudo se refiere a este código específico que Richard W. Hamming introdujo en 1950. En ese momento, Hamming trabajaba en Bell Telephone Laboratories y estaba frustrado con la propensión a errores. lector de tarjetas perforado , por lo que comenzó a trabajar en códigos de corrección de errores. [1]
Hamming (7,4) -Código | |
---|---|
Lleva el nombre de | Richard W. Hamming |
Clasificación | |
Tipo | Código de bloque lineal |
Longitud del bloque | 7 |
Longitud del mensaje | 4 |
Velocidad | 4/7 ~ 0.571 |
Distancia | 3 |
Tamaño del alfabeto | 2 |
Notación | [7,4,3] 2- código |
Propiedades | |
código perfecto | |
El código Hamming agrega tres bits de verificación adicionales a cada cuatro bits de datos del mensaje. El algoritmo de Hamming (7,4) puede corregir cualquier error de un solo bit o detectar todos los errores de un solo bit y de dos bits. En otras palabras, la distancia mínima de Hamming entre dos palabras de código correctas cualesquiera es 3, y las palabras recibidas se pueden decodificar correctamente si están a una distancia de como máximo una de la palabra de código que fue transmitida por el remitente. Esto significa que para situaciones de medio de transmisión donde no ocurren errores de ráfaga , el código de Hamming (7,4) es efectivo (ya que el medio tendría que ser extremadamente ruidoso para que dos de los siete bits se inviertan).
En información cuántica , Hamming (7,4) se utiliza como base para el código Steane , un tipo de código CSS utilizado para la corrección de errores cuánticos .
Objetivo
El objetivo de los códigos de Hamming es crear un conjunto de bits de paridad que se superponen de modo que se pueda detectar y corregir un error de un solo bit en un bit de datos o un bit de paridad. Si bien se pueden crear múltiples superposiciones, el método general se presenta en los códigos de Hamming .
Un poco # 1 2 3 4 5 6 7 Bit transmitido sí No sí No sí No sí No sí sí No No sí sí No No No sí sí sí sí
Esta tabla describe qué bits de paridad cubren qué bits transmitidos en la palabra codificada. Por ejemplo, p 2 proporciona una paridad par para los bits 2, 3, 6 y 7. También detalla qué bit transmitido está cubierto por qué bit de paridad leyendo la columna. Por ejemplo, d 1 está cubierto por p 1 y p 2 pero no p 3. Esta tabla tendrá un parecido sorprendente con la matriz de verificación de paridad ( H ) en la siguiente sección.
Además, si se eliminaron las columnas de paridad de la tabla anterior
sí sí No sí sí No sí sí No sí sí sí
entonces también será evidente la semejanza con las filas 1, 2 y 4 de la matriz generadora de código ( G ) a continuación.
Por lo tanto, al elegir correctamente la cobertura de bits de paridad, todos los errores con una distancia de Hamming de 1 pueden detectarse y corregirse, que es el punto de usar un código de Hamming.
Matrices de Hamming
Los códigos de Hamming se pueden calcular en términos de álgebra lineal a través de matrices porque los códigos de Hamming son códigos lineales . Para los propósitos de los códigos de Hamming, se pueden definir dos matrices de Hamming : la matriz generadora de código G y la matriz de verificación de paridad H :
Como se mencionó anteriormente, las filas 1, 2 y 4 de G deberían resultar familiares, ya que asignan los bits de datos a sus bits de paridad:
- p 1 cubre d 1 , d 2 , d 4
- p 2 cubre d 1 , d 3 , d 4
- p 3 cubre d 2 , d 3 , d 4
Las filas restantes (3, 5, 6, 7) asignan los datos a su posición en forma codificada y solo hay 1 en esa fila, por lo que es una copia idéntica. De hecho, estas cuatro filas son linealmente independientes y forman la matriz de identidad (por diseño, no por coincidencia).
Además, como se mencionó anteriormente, las tres filas de H deberían resultarle familiares. Estas filas se utilizan para calcular el vector de síndrome en el extremo receptor y si el vector de síndrome es el vector nulo (todos ceros), la palabra recibida no tiene errores; si no es cero, el valor indica qué bit se ha invertido.
Los cuatro bits de datos, ensamblados como un vector p , se multiplican previamente por G (es decir, Gp ) y se toman en módulo 2 para producir el valor codificado que se transmite. Los 4 bits de datos originales se convierten en siete bits (de ahí el nombre "Hamming (7,4)") con tres bits de paridad añadidos para garantizar una paridad uniforme utilizando las coberturas de bits de datos anteriores. La primera tabla anterior muestra el mapeo entre cada bit de datos y paridad en su posición de bit final (1 a 7) pero esto también se puede presentar en un diagrama de Venn . El primer diagrama de este artículo muestra tres círculos (uno para cada bit de paridad) y encierra bits de datos que cubre cada bit de paridad. El segundo diagrama (mostrado a la derecha) es idéntico pero, en cambio, las posiciones de los bits están marcadas.
Para el resto de esta sección, los siguientes 4 bits (mostrados como un vector de columna) se utilizarán como ejemplo de ejecución:
Codificación de canal
Supongamos que queremos transmitir estos datos ( 1011
) a través de un canal de comunicaciones ruidoso . Específicamente, un canal simétrico binario, lo que significa que la corrupción de errores no favorece ni a cero ni a uno (es simétrico al causar errores). Además, se supone que todos los vectores fuente son equiprobables. Tomamos el producto de G y p , con entradas módulo 2, para determinar la palabra de código transmitida x :
Esto significa que 0110011
se transmitiría en lugar de transmitir 1011
.
Los programadores preocupados por la multiplicación deben observar que cada fila del resultado es el bit menos significativo del Conteo de población de los bits establecidos que resultan de que la fila y la columna se combinen con un AND bit a bit en lugar de multiplicarlas.
En el diagrama adyacente, los siete bits de la palabra codificada se insertan en sus respectivas ubicaciones; A partir de la inspección, queda claro que la paridad de los círculos rojo, verde y azul es uniforme:
- el círculo rojo tiene dos unos
- el círculo verde tiene dos unos
- el círculo azul tiene cuatro unos
Lo que se mostrará en breve es que si, durante la transmisión, se invierte un bit, la paridad de dos o los tres círculos será incorrecta y el bit con error se puede determinar (incluso si es uno de los bits de paridad) sabiendo que la paridad de los tres círculos deben ser uniformes.
Comprobación de paridad
Si no se produce ningún error durante la transmisión, entonces la palabra de código r recibida es idéntica a la palabra de código transmitida x :
Los multiplica receptor H y r para obtener el síndrome vector z , que indica si se ha producido un error, y si es así, para los que poco palabra de código. Realizando esta multiplicación (nuevamente, entradas módulo 2):
Dado que el síndrome z es el vector nulo , el receptor puede concluir que no se ha producido ningún error. Esta conclusión se basa en la observación de que cuando el vector de datos se multiplica por G , un cambio de base se produce en un subespacio vectorial que es el núcleo de H . Mientras no ocurra nada durante la transmisión, r permanecerá en el núcleo de H y la multiplicación producirá el vector nulo.
Error de corrección
De lo contrario, suponga que se ha producido un error de un solo bit. Matemáticamente, podemos escribir
módulo 2, donde e i es el vector unitario , es decir, un vector cero con un 1 en el, contando desde 1.
Por lo tanto, la expresión anterior significa un error de un solo bit en el lugar.
Ahora, si multiplicamos este vector por H :
Dado que x son los datos transmitidos, no tienen error y, como resultado, el producto de H y x es cero. Por lo tanto
Ahora, el producto de H con elvector de base estándar selecciona esa columna de H , sabemos que el error ocurre en el lugar donde ocurre esta columna de H.
Por ejemplo, suponga que hemos introducido un error de bit en el bit # 5
El diagrama de la derecha muestra el error de bit (mostrado en texto azul) y la paridad incorrecta creada (mostrada en texto rojo) en los círculos rojo y verde. El error de bit se puede detectar calculando la paridad de los círculos rojo, verde y azul. Si se detecta una paridad incorrecta, el bit de datos que se superpone solo a los círculos de paridad incorrecta es el bit con el error. En el ejemplo anterior, los círculos rojo y verde tienen mala paridad, por lo que el bit correspondiente a la intersección de rojo y verde, pero no azul, indica el bit con error.
Ahora,
que corresponde a la quinta columna de H . Además, el algoritmo general utilizado ( ver código Hamming # Algoritmo general ) fue intencional en su construcción, de modo que el síndrome de 101 corresponde al valor binario de 5, lo que indica que el quinto bit estaba dañado. Por lo tanto, se ha detectado un error en el bit 5 y se puede corregir (simplemente invierta o niegue su valor):
De hecho, este valor recibido corregido coincide ahora con el valor x transmitido desde arriba.
Descodificación
Una vez que se ha determinado que el vector recibido está libre de errores o se ha corregido si se produjo un error (suponiendo que solo son posibles errores de un bit o cero), los datos recibidos deben decodificarse nuevamente en los cuatro bits originales.
Primero, defina una matriz R :
Entonces el valor recibido, p r , es igual a Rr . Usando el ejemplo de ejecución de arriba
Errores de bits múltiples
No es difícil demostrar que solo los errores de un solo bit pueden corregirse utilizando este esquema. Alternativamente, los códigos de Hamming se pueden usar para detectar errores de bit simple y doble, simplemente notando que el producto de H es distinto de cero siempre que se hayan producido errores. En el diagrama adyacente, los bits 4 y 5 se invirtieron. Esto produce solo un círculo (verde) con una paridad no válida, pero los errores no se pueden recuperar.
Sin embargo, los códigos Hamming (7,4) y Hamming similares no pueden distinguir entre errores de un solo bit y errores de dos bits. Es decir, los errores de dos bits tienen el mismo aspecto que los errores de un bit. Si se realiza la corrección de errores en un error de dos bits, el resultado será incorrecto.
De manera similar, los códigos de Hamming no pueden detectar o recuperarse de un error arbitrario de tres bits; Considere el diagrama: si el bit en el círculo verde (de color rojo) fuera 1, la verificación de paridad devolvería el vector nulo, lo que indica que no hay error en la palabra de código.
Todas las palabras en clave
Dado que la fuente tiene solo 4 bits, solo hay 16 palabras transmitidas posibles. Se incluye el valor de ocho bits si se utiliza un bit de paridad adicional ( consulte el código Hamming (7,4) con un bit de paridad adicional ). (Los bits de datos se muestran en azul; los bits de paridad se muestran en rojo; y el bit de paridad adicional se muestra en amarillo).
Datos | Hamming (7,4) | Hamming (7,4) con bit de paridad adicional (Hamming (8,4)) | ||
---|---|---|---|---|
Transmitido | Diagrama | Transmitido | Diagrama | |
0000 | 00 0 0 000 | 00 0 0 000 0 | ||
1000 | 11 1 0 000 | 11 1 0 000 1 | ||
0100 | 10 0 1 100 | 10 0 1 100 1 | ||
1100 | 01 1 1 100 | 01 1 1 100 0 | ||
0010 | 01 0 1 010 | 01 0 1 010 1 | ||
1010 | 10 1 1 010 | 10 1 1 010 0 | ||
0110 | 11 0 0 110 | 11 0 0 110 0 | ||
1110 | 00 1 0 110 | 00 1 0 110 1 | ||
0001 | 11 0 1 001 | 11 0 1 001 0 | ||
1001 | 00 1 1 001 | 00 1 1 001 1 | ||
0101 | 01 0 0 101 | 01 0 0 101 1 | ||
1101 | 10 1 0 101 | 10 1 0 101 0 | ||
0011 | 10 0 0 011 | 10 0 0 011 1 | ||
1011 | 01 1 0 011 | 01 1 0 011 0 | ||
0111 | 00 0 1 111 | 00 0 1 111 0 | ||
1111 | 11 1 1 111 | 11 1 1 111 1 |
E 7 celosía
El código de Hamming (7,4) está estrechamente relacionado con la celosía E 7 y, de hecho, se puede usar para construirla, o más precisamente, su celosía dual E 7 ∗ (una construcción similar para E 7 usa el código dual [ 7,3,4] 2 ). En particular, tomando el conjunto de todos los vectores x en Z 7 con x congruente (módulo 2) a una palabra de código de Hamming (7,4), y reescalando por 1 / √ 2 , da la celosía E 7 ∗
Este es un ejemplo particular de una relación más general entre celosías y códigos. Por ejemplo, el código extendido (8,4) -Hamming, que surge de la adición de un bit de paridad, también está relacionado con la red E 8 . [2]
Referencias
- ^ "Historia de los códigos de Hamming" . Archivado desde el original el 25 de octubre de 2007 . Consultado el 3 de abril de 2008 .
- ^ Conway, John H .; Sloane, Neil JA (1998). Empaquetaduras, celosías y grupos de esferas (3ª ed.). Nueva York: Springer-Verlag. ISBN 0-387-98585-9.
enlaces externos
- Un problema de programación sobre el código Hamming (7,4)