miércoles, 8 de mayo de 2013

Tarea #5 - Codigo Hamming - Python

Codigo hamming
Liga al repo

Teoria segun wikipedia
Antes de los códigos Hamming se utilizaron ciertos códigos detectores de error, como lo fueron el código linteing, pero ninguno llegó a ser tan eficaz como los de Hamming. A continuación se describen algunos de estos códigos.

Paridad 

La paridad consiste en añadir un bit, denominado bit de paridad, que indique si el número de los bits de valor 1 en los datos precedentes es par o impar. Si un solo bit cambiara por error en la transmisión, el mensaje cambiará de paridad y el error se puede detectar (nótese que el bit donde se produzca el error puede ser el mismo bit de paridad). La convención más común es que un valor de paridad 1 indica que hay un número impar de unos en los datos, y un valor de paridad de 0 indica que hay un número par de unos en los datos.


y un vídeo que me ayudo mucho para esta tarea: (TIENEN QUE VERLO - OBLIGATORIO)


Implementación

Lo primero que se hace es "auto-completar" la cadena binaria respetando los espacios de la paridad.
Lo que hice fue agregar un "*" en el lugar que tiene que ser respetado, lo hago de esta manera para que mas adelante me sea mas fácil trabajar.



Ahora que ya tenemos la cadena auto-completada, se tiene que formar un fila por cada elemento de paridad detectado; supondremos que llegaste a esta entrada sabiendo como se hace o viendo el vídeo en el apartado de Teoría



Con las filas de paridad ya definidas, lo que sigue es checar si existe "error" en cada ellas. Para ello si procesan de forma individual y se suman sus bits; si la suma es cero o numero par, esa fila se etiqueta con un 0 si la suma salio impar se etiqueta con un uno.
Los unos significan que existe error y por lo tanto se tiene que modificar un bit de la entrada original para que la sumatoria cambie. El objetivo es que todas las sumas de las columnas sean ceros o números pares.



Mientras haya errores osea sumatorias impares, si repite el proceso.



Al final solo quitamos los espacios de paridad y listo



Código completo


Resultados

Referencias
http://elisa.dyndns-web.com/~elisa/teaching/comp/info/correct.pdf
http://codigojavaoracle.com/redes/codigo-hamming-detectar-errores-por-paridad/