Hamming Code

Encoding and decoding with the Hamming Code

Hola a todos mis compañeros y gente que visita el blog, esta entrada trata sobre la detección de errores en la transmisión de datos, mediante Hamming Code.

En los protocolos de comunicación, como RS232, es muy común observar el uso de bits de paridad, los bits de paridad (0 o 1) nos sirven en un sistema para realizar detección de errores en una transmisión. Existen diversos motivos por los que puede haber un error en una transmisión, ya sea que se pierda el control de flujo de información, que la transmisión de datos sea intermitente, problemas de congestión, etc. Es por eso que un bloque de bits se transmite con una paridad específica, con la intención de encontrar errores en una transmisión.

Bien, en nuestro caso encontraremos estos errores mediante Hamming Code, a continuación explico el proceso a detalle.

Los pilares que considero en Hamming Code son: 

1 - Multiplicación de matrices. 

2 - Aritmética de módulo 2. 

Se dice aritmética de módulo 2 porque solamente se emplean 2 dígitos para representar este sistema numérico, básicamente es lenguaje binario; la aritmética es porque vamos a realizar operaciones de adición y multiplicación.

La adición de módulo 2 se realiza de la siguiente manera (noten que es un XOR):

0+0 = 0

0+1 = 1

1+0 = 0

1+1 = 1

Mientras que la multiplicación de módulo 2 se realiza de la siguiente manera (noten que es el operador lógico AND):

0+0 = 0

0+1 = 0

1+0 = 0

1+1 = 1

3 - Paridad

La ya mencionada paridad se presenta en 2 sabores; paridad par y paridad impar. Una cadena de bits tiene una paridad par si contiene un número par de 1 (la suma número 2 de los bits es 0), de lo contrario tiene paridad impar (la suma número 2 de los bits es 1).

Codificación

Los códigos de Hamming tradicionales son códigos (7, 4). Esto quiere decir que codifica 4 bits de datos en siete bloques de bits, como podrán imaginarse, los bits "extra" del bloque, son bits de paridad (todos los bits de paridad son paridad par).

Supongamos que tenemos los bits de datos: d1, d2, d3 y d4.

Podemos obtener nuestros bits de paridad de la siguiente manera:

p1 = d2+d3+d4

p2 = d1+d3+d4

p3 = d1+d2+d4

La operación para obtener los bits de paridad es un XOR, como lo vimos anteriormente, por ejemplo si tenemos un bloque de bits de datos = 0110, el procedimiento para obtener p1 es:

p1 = d2 + d3 + d4 = p1 = 1+1+0 = p1 = 0

Luego p2 es: 0+1+0 = 1

Luego p3 es: 0+1+0 = 1

De manera que nuestro bloque de bits, más nuestros 3 bits de paridad quedan así:  "0110011"

Lo siguiente que vamos a hacer es generar una matriz "G" de 4x7.  Esto lo hacemos con la intención de transformar nuestra cadena de bits (4 bits) en un código Hamming de 7 bits (en una palabra: codificar).

Seguido a esto, vamos a definir los 4 vectores de bits de datos, vamos a llamarlos d1,d2,d3 y d4

d1 = [1 0 0 0]
d2 = [0 1 0 0]
d3 = [0 0 1 0]
d4 = [0 0 0 1]

Ya que los definí, ahora vamos a obtener nuestros vectores pero ahora de bits de paridad, para obtenerlos solo tenemos que recurrir a las ecuaciones antes mencionadas:

p1 = d2+d3+d4

p2 = d1+d3+d4

p3 = d1+d2+d4

Quedando de la siguiente manera nuestros vectores de bits de paridad:

p1 = [0 1 1 1]
p2 = [1 0 1 1]
p3 = [1 1 0 1]

Ahora que contamos con los vectores de bits de datos y los vectores de bits de paridad, voy a formar la matriz generadora "G". Para formar la matriz G es muy sencillo, solo se tienen que acomodar los vectores anteriores en el siguiente orden [p1, p2, p3, d1, d2, d3, d4]; es decir, primero los vectores de bits de paridad, luego los vectores de bits de datos.
Me queda una matriz como la siguiente:

     p1  p2  p3  d1  d2  d3  d4
     ---------------------------
    |                          |
    |0   1   1   1   0   0   0 |  
G = |1   0   1   0   1   0   0 |
    |1   1   0   0   0   1   0 |
    |1   1   1   0   0   0   1 |
    |                          |

Bien, ya tenemos lo necesario para codificar, tomemos de ejemplo la cadena de bits "1010", vamos a codificarla con nuestro generador, lo que tenemos que hacer es multiplicar nuestro vector [1010] por el generador[G] que acabamos de hacer (por eso mencioné anteriormente que uno de los pilares para la codificación Hamming es la multiplicación de matrices).

            |                          |
            |0   1   1   1   0   0   0 |  
|1 0 1 0| X |1   0   1   0   1   0   0 | = | 1 0 1 1 0 1 0 |
            |1   1   0   0   0   1   0 |
            |1   1   1   0   0   0   1 |
            |                          |

Así pués, tenemos el código Hamming: "1011010" de la cadena "1010", con esto podemos concluir que la codificación dependerá de la matriz generadora que hagamos.

Implementé en python el proceso de "encoding", el código es el siguiente:

Decodificación

El primer paso para la decodificación es comprobar los bits de paridad para ver si existe algún error. Si suponemos que en vez de la cadena "1011010" que recibimos anteriormente con la matriz generadora, hubieramos recibido esta otra "1011011". Los bits de paridad podríamos obtenerlos de forma aritmética con las ecuaciones ya antes mencionadas:
p₁ = d₂ + d₃ + d₄ = 0 + 1 + 1 = 0
p₂ = d₁ + d₃ + d₄ = 1 + 1 + 1 = 1
p₃ = d₁ + d₂ + d₄ = 1 + 0 + 1 = 0

Y si sabemos que los bits de paridad de nuestra cadena son los primeros 3, tenemos que "101" y "010" son todo lo contrario, osea cada bit de paridad resultante es erróneo.

A continuación vamos a construir una matriz de verificación de paridad (de 3x7), precisamente para verificar los posibles errores en la transmisión. La matriz H está dada por:

            |                          |
            |1   0   0   0   1   1   1 |  
       H =  |0   1   0   1   0   1   1 | 
            |0   0   1   1   1   0   1 |
            |                          |

Existe una matriz llamada "síndrome" que es la que nos da el resultado si existen o no errores en la codificación. Existen 2 propiedades de la matriz "síndrome", si los valores de la matriz "síndrome" son todos ceros significa que los datos codificados están libre de errores.

Para obtener nuestra matriz "síndrome", tan solo tenemos que la matriz H por nuestro código obtendido en el proceso anteriormente abordado.

No alcancé a implementar la parte de decodificación, pero intentaré terminar la entrada porque la actividad me pareció interesante.
Por mi parte es todo.

Liga a mi git: https://github.com/eddypre/M-todosCodificaci-n

Bibliografía

http://en.wikipedia.org/wiki/Parity-check_matrix
http://michael.dipperstein.com/hamming/#example2
http://elisa.dyndns-web.com/~elisa/teaching/comp/info/correct.pdf

Cualquier duda o aclaración pueden dejarla en la caja de comentarios. 

Saludos a todos!