jueves, 9 de mayo de 2013

Hamming

Para esta tarea yo decidí realizar el código Hamming(7,4)

En mi caso usaré (7, 4), que significa que codifica 4 bits de datos en 7 bits adicionando 3 bits de paridad. Este código Hamming permite corregir los errores de un bit o detectar todos los errores de un bit y dos bits.

Por ejemplo para codificar la siguiente matriz:



Entonces vamos a codificar una palabra "x" de 4 bits por ejemplo x = [1,0,1,1].
Para obtener el código de 7 bits se hace la multiplicación de G * x y se puede obtener el código correspondiente:







Tenemos que "1011" se codificó en "1011010", entonces podemos verificar que el código se ha enviado correctamente, Si se recibe una palabra y de la longitud 7, anticipamos primera comprobación para ver si y es una palabra en clave, si es así, se recupera el mensaje original como los primeros 4 bits de y. Para esto se utiliza H la matriz de 3 × 7 :



Para buscar los errores se multiplica la "y" transpuesta por la H, y se obtiene una matriz de 1x3, que si es 0 en todas las posiciones significa que no  hay error, si hay algún 1 ya hay un error.


Pero si en vez de transmitirse 1011010 se transmite por ejemplo 1111010 se obtiene lo siguiente que nos indica la posición donde hubo una falla y la podemos arreglar:










Para este experimento tome en cuenta tres factores:

  • La probabilidad de fallo al enviar el bit, esto quiere decir que porcentaje tiene de probabilidad de que el bit se envíe de manera correcta y de manera incorrecta.
  • El numero de replicas, es el numero de veces que se corre el experimento.
  • La cantidad de bits que cambian en la palabra, es el número de bits que puede cambiar la palabra.
Replicas 10000
Bits que cambian 1
Probabilidad de fallo .3

Replicas 10000
Bits que cambian 2
Probabilidad de fallo .5


En la primera gráfica podemos ver que se corrigen más datos que los que no esto es porque se esta cambiando solo un bit y el algoritmo es muy bueno haciendo esto, y vemos que esta muy abajo lo de mandado sin errores y los que se mandan ta cual también representan gran parte de los datos ya que se estaba usando una probabilidad de 0.3.
En la segunda gráfica se puede ver que como se aumento la cantidad de bits que se cambian también afecto mucho en la corrección ya que ahora la mayoría se mandan con errores sin corregir, y muy pocos se logran recuperar totalmente, además de que se aumentó la probabilidad a 0.5.

El código que hace lo ya explicado es el siguiente:



Referencias

Elisa Schaeffer - Error correcting codes
Encoding and Decoding with the Hamming Code

1 comentario: