Corrección de Errores

Teoría de la Información y Métodos de Codificación
Tarea 5

Esta entrada trata de la corrección de errores de transmisión en un canal de comunicación, y particularmente la implementación del algoritmo para corrección de errores llamado Hamming(7, 4), que es un caso específico de los códigos Hamming.

Lo que se intenta hacer con estos códigos de bloques (en este caso bloques de bits), es transformar estos bloques por una cadena de bits un poco más larga, agregando los llamados bits de paridad, que son bits con los que luego es posible recuperarse de un error en la transmisión.

Cuando se transmiten bloques de bits por un canal de transmisión, se pueden presentar dos escenarios distintos. Primero, que el bloque de bits transmitido sea un código válido y no se tenga que hacer otra cosa más que decodificarlo y continuar con el siguiente bloque. Y segundo, que el bloque de bits no haya sido un código válido, y por lo tanto se tanga que recurrir a dos alternativas: (a) pedir al transmisor que vuelva a enviar el bloque, (b) poder recrear el bloque original mediante el código que se recibió.

Lo que nos interesa es conocer el algoritmo para lograr recrear el bloque original, a partir del bloque recibido con errores.

Como podemos ver en la siguiente imagen, nosotros definimos un tamaño de bloque de k bits, el cual entra a la función encargada de codificarla, para dar como resultado un bloque codificado, de n bits, donde n>k. Esto último es por que se habrán agregado los bits de paridad. Y para el caso en especifico que trataré, usamos bloques de 4 bits, que resultan en un código Hamming de 7 bits.

Para el caso de Hamming(7, 4), cuando existe un error en un bit, es posible recuperar el mensaje completo sin ninguna afectación. Y esto es porque cuanto menor sea la distancia entre bloques de código válidos, más difícil es recuperar lo que era la palabra clave correcta.

Este funciona haciendo uso de álgebra lineal simple, haciendo uso de matrices y multiplicaciones de matrices, lo que lo hace más eficiente que hacer uso de listas, ya que el consumo de memoria es menor, así como del procesamiento necesario.

Obtener el código Hamming es sencillo, solo es necesario multiplicar las matrices. Supongamos que tenemos un mensaje de 4 bits x = [1 1 0 1] y deseamos obtener su respectivo código Hamming, entonces hacemos lo siguiente.

$xG = \begin{bmatrix}{1}&&{1}&&{0}&&{1}\end{bmatrix} \begin{bmatrix} {1}&&{0}&&{0}&&{0}&&{0}&&{1}&&{1}\\ {0}&&{1}&&{0}&&{0}&&{1}&&{0}&&{1}\\ {0}&&{0}&&{1}&&{0}&&{1}&&{1}&&{0}\\ {0}&&{0}&&{0}&&{1}&&{1}&&{1}&&{1}\end{bmatrix}$

$xG = \begin{bmatrix}{1}&&{1}&&{0}&&{1}&&{0}&&{0}&&{1}\end{bmatrix}$

Este código de 7 bits es el que se transmite, y una vez recibido por el receptor, este verifica si es válido o no de la siguiente manera.

$Hy = \begin{bmatrix} {0}&&{0}&&{0}&&{1}&&{1}&&{1}&&{1}\\ {0}&&{1}&&{1}&&{0}&&{0}&&{1}&&{1}\\ {1}&&{0}&&{1}&&{0}&&{1}&&{0}&&{1}\end{bmatrix} \begin{bmatrix}{1}\\{1}\\{0}\\{1}\\{0}\\{0}\\{1}\end{bmatrix}$

$Hy = \begin{bmatrix}{0}\\{0}\\{0}\end{bmatrix}$

Cuando la suma de los elementos de esta última matriz no da cero, significa que existe un error. Supongamos que en vez de resultar ser Hy = [0; 0; 0] fuera Hy = [1; 0; 1], estos 3 bits se unen para formar un número binario el cual convertido a decimal sería 5, lo cual indicaría que el bit en la posición 5 es el que tiene el error, y lo que se hace es cambiar el 0 por un 1 o viceversa según sea el caso.

Código y pruebas

La prueba que realicé es sencilla, se trata de generar bloques de 4 bits para ser transmitidos, y comparo si lo que se mando se logró decodificar para obtener el original, y voy contando las veces que salió correcta la transmisión.

Referencias:
University of Wyoming, "Encoding and Decoding with the Hamming Code" [En línea]. [Fecha de consulta: 9 de Mayo, 2013].
Disponible en: http://www.uwyo.edu/moorhouse/courses/4600/encoding.pdf

Muhamad Asvial, "Channel coding, linear block codes, Hamming and cyclic codes" [En línea]. Fecha de consulta: 9 de Mayo, 2013].
Disponible en: http://staff.ui.ac.id/internal/132094574/material/KomDig_8.pdf

Diana Palsetia, "Error Detection and Correction", 2008 [En línea]. [Fecha de consulta: 9 de Mayo, 2013].
Disponible en: http://www.cis.upenn.edu/~palsetia/cit595s08/Lectures08/ErrorCD.pdf