miércoles, 8 de mayo de 2013

Block Code

Buenas en esta ocasión les traemos una manera para verificar si un string o texto o cadena de texto se transmitió de manera correcta.

Para esto usaremos específicamente HAMMING BLOCK CODES.

El hamming code nos permite encontrar errores en un texto recibido por medio de unas sencillas técnica que explicaremos a continuación.


Para esta técnica se aplicó específicamente hamming code (7x4). Esto nos indica que será un string de 4 bits que representaran "algo" ya sea números, letras entre otras cosas, y que serán acompañadas con 3 dígitos mas "parity bits".


Para empezar, si son 4 bits estamos delimitados a usar solamente 16 tipos de combinaciones, esto quiere decir que solo podemos aplicar esta técnica solo a 16 cosas.



Para poder sacar los parity bits se sigue la siguiente regla cuando sea (7x4)
P1 = d2 + d3 + d4
P2 = d1 + d3 + d4
P3 = d1 + d2 + d4

Por ejemplo si tratamos de sacar el código + parity de "0111" seria de la siguiente manera
0 = d1
1 = d2
1 = d3
1 = d4

Estos no son sumas en si si no operaciones "exor"
P1 = 1+ 1+1 = 1 (1+1) = 0, (0 + 1) = 1
P2 = 0 + 1 + 1 = 0 (0+1) = 1, (1 + 1) = 0
P3 = 0 + 1 +1 = 0 (0+1) = 1, (1 + 1) = 0

Entonces seria "0111" + "100" =  "01111000" como lo tenemos en la tabla, de igual manera los demás datos.


El siguiente paso es generar nuestra matriz "G" de 4 x7
Para esto se utiliza unos representantes de datos y sus respectivas pariedades, según como se realizó la matriz "G" puede realizar diferentes resultados, en este ejemplo se uso el tradicional que tiene medio mundo.


d1 = 1000 -> 011
d2 = 0100 -> 101
d3 = 0010 -> 110
d4 = 0001- > 111

Para esto generamos un código en python para poder crear esta gráfica "G"

Aquí el código

Aquí el código



Donde final G es nuestra matriz resultante.

Posteriormente se multiplica nuestra matriz "G" con el código del carácter que queremos enviar, en la imagen anterior se puso el siguiente código "1010".

Mensaje codificado = Matriz G x código

Dando como resultado lo siguiente:

Si no se cansa a apreciar el resultado fue el siguiente: "1011010"

Para poder sacarlo se multiplicaba cada uno de los caracteres del código a codificar con cada una de las columnas y al final se sumaban con el método "exor". Ejemplo con la primera columna

1010 x 0111 = (1x0) + (0x1) +(1x1) +(0x1) = 1

Aclarando que la multiplicación solo da uno en caso de que ambos dígitos sean uno

Código de esto

Código de esto

Ya que lo tenemos codificado, para sabe como se verifica si llego correctamente, se crea una matriz "H" de 3 x 7 de una manera fácil y sencilla.

Solo tenemos que sacar la matriz transpuesta de los "parity code" y quitar tanto una columna y fila a los códigos y juntar los resultados para obtener nuestra matriz H.

G = [código / parity ]  H = [parity transpuesta / código (n-t)]

Aquí el código


Aquí el código

ya para finalizar se multiplica nuestro vector recibido por cada una de las filas y obtendremos un arreglo de tres variables. En caso de que todos sean cero, quiere decir que no hay ningún error, pero en cambio si no todos son ceros significa que en esa posición existe un error.


Aquí solo como referencia se agrego un pequeño método para meter ruido , y que tenga una probabilidad del 25% de fallo, o error al transmitir


Eso es todo

Click aquí para el código completo

Posdata:
Al ejecutar el programa se le pide una cantidad de bits como es de 4x7, tecleamos 4. ya que tiene algunos fallos si se utiliza otra cantidad
Se pregunta la cadena a enviar esta tiene que ser de cuatro bits por lo mismo sobre 4x7
Eso es todo


bibliografías:
1-. "Parity-check matrix",From Wikipedia. the free encyclopedia,http://en.wikipedia.org/wiki/Parity-check_matrix

2-. "Hamming (7,4) Code Discussion and Implementation","by Michael Dipperstein",http://michael.dipperstein.com/hamming/

3-. "Hamming_code",From Wikipedia, the fre encyclopedia,http://en.wikipedia.org/wiki/Hamming_code

4-. "Encoding and Decoding with the Hamming Code
",University of WYOMING,año 2006,http://www.uwyo.edu/moorhouse/courses/4600/encoding.pdf

1 comentario:

  1. El formato del reporte deja bastante por desear y la claridad del código tampoco está al máximo, pero por lo menos hiciste la tarea. 4+4.

    ResponderEliminar