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:

	#!/usr/bin/python
	import numpy as np
	import matplotlib.pyplot as plt
	from pylab import *
	import random
	#DEBUG = True
	DEBUG = False
	def graficar(rep, sr, e, c):
	fig = plt.figure()
	tres = fig.add_subplot(122)
	l1,l2 = tres.plot(e,rep,'r',c, rep,'g')
	tres.set_xlabel('tamano de transmision')
	tres.set_ylabel('tiempo')
	tres.set_title("Caso tipico vs Dist Uniforme")
	tres.grid(True)
	fig.legend((l1, l2), ('Tipico', 'Uniforme'), 'upper left')
	plt.savefig('hola.png')
	class Experimento:
	def __init__(self, error, rep, num_bits):
	self.num_rep = rep #repeticiones del experimento
	self.error = error #porcentaje de error
	self.num_bits = num_bits #numero de bits que cambian en la palabra
	self.palabra_original = None
	self.correcciones = 0
	self.errores = 0
	self.sin_ruido = 0
	def canal(self):
	"""genera ruido
	"""
	c = 0
	palabra_nueva =np.copy(self.palabra_original)
	for i in range(len(self.palabra_original)):
	if random.random() <= self.error:
	print palabra_nueva[i]
	if palabra_nueva[i] == 0:
	palabra_nueva[i] = 1
	c = c + 1
	if c == self.num_bits:
	break
	return palabra_nueva
	def exp(self):
	"""experimentos
	"""
	self.sin_ruido = 0
	self.errores = 0
	self.correcciones = 0
	for i in range(self.num_rep):
	#repeticiones
	palabra = []
	for j in range(4):
	palabra.append(random.randrange(0,2))
	#se transmite la palabra con o sin errores
	hamm = Hamming(palabra)
	self.palabra_original = hamm.codifica()
	self.palabra_nueva = self.canal()
	Hy = hamm.decodifica(self.palabra_nueva)
	pos = "".join(map(str, Hy)[::-1])
	pos = int(str(pos),2)
	if (self.palabra_nueva == self.palabra_original).all():
	self.sin_ruido += 1
	else:
	self.palabra_nueva[pos-1] = 0
	if (self.palabra_nueva == self.palabra_original).all():
	self.correcciones += 1
	else:
	self.errores += 1
	def imprimir(self):
	"""Imprime el estado del experimento
	"""
	print "Numero de repeticiones %s" %self.num_rep
	print "Porcentaje de error %s" %self.error
	print "Bits que pueden cambiar %s" %self.num_bits
	print "Errores corregidos %s" %self.correcciones
	print "Errores transmitidos no corregidos %s" %self.errores
	print "Mensajes sin ruido %s" %self.sin_ruido
	return self.sin_ruido, self.errores, self.correcciones
	class Hamming:
	def __init__(self, palabra):
	self.G = np.array([[1,1,1,0,0,0,0],
	[1,0,0,1,1,0,0],
	[0,1,0,1,0,1,0],
	[1,1,0,1,0,0,1]])
	self.x = palabra
	self.y = None
	self.H = np.array([[1,0,1,0,1,0,1],
	[0,1,1,0,0,1,1],
	[0,0,0,1,1,1,1]])
	self.Hy = None
	def codifica(self):
	self.y = np.dot(self.x, self.G)%2
	#debug
	if DEBUG:
	print "Palabra correcta %s" %self.y
	pass
	return self.y
	def decodifica(self, y):
	#modificando para el ejemplo
	self.Hy = np.dot(self.H,y)%2
	#debug
	if DEBUG:
	print "Palabra recibida %s" %self.y
	print "Comprobacion %s" %self.Hy
	return self.Hy
	def main():
	"""funcion principal
	"""
	sr_a = []
	e_a = []
	c_a = []
	re = []
	f = open("experimento.tex", "w")
	for rep in range(0, 1000, 10):
	prueba = Experimento(0.9, rep, 1)
	prueba.exp()
	sr, e, c = prueba.imprimir()
	sr_a.append(sr)
	e_a.append(e)
	c_a.append(c)
	re.append(rep)
	f.write("%s %s %s %s\n" %(rep, sr, e, c))
	graficar(rep, sr, e, c)
	f.close()
	if __name__ == "__main__":
	main()

view raw gistfile1.py hosted with ❤ by GitHub

Referencias

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