Error-Correcting Codes

In this entry I talk about Hamming Code that is a code for error-correcting using linear algebra, just multiplying a matrix with a message module 2 to encode a message and to verify the integrity of the message we just verify multiplying with a matrix and as a result we receive a vector in binary that tell us in which bit of the message transmitted is incorrect.

To start experimenting first we need the next code, made it by me.

	from random import randint
	import numpy as np
	#Method to encode message
	def encode(message):
	#Create a list with the string of the message
	message = list(message)
	for m in xrange(len(message)):
	#Convert the string to integer
	message[m] = int(message[m])
	#Create a matrix with the values of the message
	message = np.matrix([message])
	#DEBUG
	print message
	print "> Encoding ..."
	#Matrix to encode the message
	g = np.matrix([[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]])
	#Multiply the message with the matrix to encode the message with module 2
	return ( message * g ) % 2
	#Method to decode message
	def decode(message):
	#DEBUG
	print "> Decoding ..."
	#Matrix to decode the message
	h = np.matrix([[0, 0, 0, 1, 1, 1, 1],
	[0, 1, 1, 0, 0, 1, 1],
	[1, 0, 1, 0, 1, 0, 1]])
	#Multiply the message with the matrix to verify the message with module 2
	hy = ( h * message.T) % 2
	#Get the integer value of the binary as result of the previous operation
	error = getNumber(hy)
	#If we get 0 we don't have any error
	if error == 0:
	#DEBUG
	print "Message decoded: %s " % matrixString(message)
	#Return the message
	return message
	#Otherwise we get an error in one or more index's
	else:
	#DEBUG
	print "Error in index: ",error
	print message
	#Transpose matrix as a easy way to manipulate the matrix
	message = message.T
	#DEBUG
	print "Message before error: %s " % matrixString(message)
	#Modify the error in the index of the message adding a one with module 2
	message[error-1] = ( message[error-1] + 1 ) % 2
	#DEBUG
	print "Message after error: %s " % matrixString(message)
	#Return the message with the original form
	return message.T
	#Method to add some noise in the message
	def noise(message, noise_ratio):
	#Get the shape of the matrix
	aux, len = message.shape
	#Transpose matrix as a easy way to manipulate the matrix
	message = message.T
	#Iterate the message
	for i in xrange(len):
	#Using a random number and the noise ratio we modify the message adding one module 2
	if randint(1,10) <= ( noise_ratio * 10 ):
	message[i] = ( message[i] + 1 ) % 2
	#DEBUG
	print message[i]
	#Return the message with the original form
	return message.T
	#Method to convert a binary method in a integer
	def getNumber(hy):
	return int( '0b%s' % matrixString(hy), 2)
	#Method to convert matrix in string
	def matrixString(matrix):
	len, aux = matrix.shape
	value = ''
	for i in xrange(len):
	value +='%s' % str(matrix[i]).replace('[','').replace(']','')
	return value
	def main():
	#Ask for a message
	message = raw_input("Give a message to code >")
	#Ask for a noise ratio
	noise_ratio = float(raw_input("Give a noise ratio >"))
	#Message encoded
	message_encoded = encode(message)
	#Adding some noise in the message encoded
	message_encoded = noise(message_encoded, noise_ratio)
	#DEBUG
	print "Message encoded: ",message_encoded
	#Message Decoded
	message_decoded = decode(message_encoded)
	main()

view raw hamming.py hosted with ❤ by GitHub

This is an image to demostrate how it works. Below of the image I explained more about the inputs and outputs of the program.

First we gave a message in this case I used '1111' with a noise ratio of 30%, then we encode the message and add some noise. We have message encoded in this case is '1011111' with an error in the second bit and the message corrected is '1111111', and just discarting the last 3 values then the real message transmitted is '1111'.

There are some errors detected in the current program the hamming code because the current code just can detect one error.

To solve this we can implement the extended hamming code, that just adding an extra bit of parity.

References

Encoding and Decoding with the Hamming Code

http://www.uwyo.edu/moorhouse/courses/4600/encoding.pdf