And here we go : the ending part of our series. Here we are going to implement the error correction using Hamming code.
Brief recap
Hamming codes are a family of linear error-correcting codes that generalize the Hamming (7,4) - code invented by Richard Hamming in 1950.
For each integer r ≥ 2 there is a code with block length n = 2^r−1 and message length k = 2^r−r−1.
(n, k)=(2^r−1, 2^r−r−1)
Hamming code's main goal is to increase the hamming distance, and increase the code rate.
Important: with this configuration the algorithm is only able to correct a single error. However, an error is corrected in the encoded message, thus even if there was en error in parity bits we will be able to detect and correct it.
Thus formula for each parity bit is the following:
first parity bit = i1 XOR i2 XOR i3 (where i is a symbol from original message)
second parity bit = i2 XOR i3 XOR i4
third parity bit = i2 XOR i3 XOR i4
We then calculate the error syndrome which will help us detect erroneous symbol.
S1 = first parity bit XOR i1 XOR i2 XOR i3
S2 = second parity bit XOR i2 XOR i3 XOR i4
S3 = third parity bit XOR i1 XOR i2 XOR i4
Error syndrome = (s1, s2, s3)
And here is the magic: we look for our error syndrome value and detect the error in our message.
where i is a symbol in initial message, and r is a parity bit.
The logic is quite straightforward: we divide our initial message (converted into a set of 0s and 1s using Shanon or Huffman algorithm) by blocks of 4 add parity bits and send it. If there were transmission errors out system will be capable of detecting errors in the received message and correct them.
In the previous article we implemented noise generation. Therefore, if you want to launch the experiment you need to encode your binary message (actually add parity bits) and launch noise generation. You then need to launch decoder on the noisy data and compare the output to the initial message. If everything is working correctly we will have exactly the same messages on input and output sides.
Here's the code:
import sys
K = 4
def encode(s):
"""Read in K=4 bits at a time and write out those plus parity bits"""
while len(s) >= K:
nybble = s[0:K]
sys.stdout.write(hamming(nybble))
s = s[K:]
def hamming(bits):
"""Return given 4 bits plus parity bits for bits (1,2,3), (2,3,4) and (1,3,4)"""
t1 = parity(bits, [0,1,2])
t2 = parity(bits, [1,2,3])
t3 = parity(bits, [0,1,3])
return bits + str(t1) + str(t2) + str(t3)
def parity(s, indicies):
"""Compute the parity bit for the given string s and indicies"""
sub = ""
for i in indicies:
sub += s[i]
return str.count(sub, "1") % 2
sequence = raw_input("Enter your encoded msg")
encode(sequence)
print
syndrome_dict = {'000': -1, '001': 6, '010': 5,
'011': 3, '100': 4, '101': 0, '110': 2, '111': 1}
def get_syndrome(bits):
number_of_blocks = len(bits)/7
entire_msg =""
for i in range (0, number_of_blocks):
end = (i+1)*7 - 1
r3 = int(bits[end])
r2 = int(bits[end-1])
r1 = int(bits[end-2])
s1 = r1^parity(bits, [7*i,7*i + 1,7*i + 2])
s2 = r2^parity(bits, [7*i+1,7*i + 2,7*i + 3])
s3 = r3^parity(bits, [7*i,7*i + 1,7*i + 3])
ss = str(s1)+str(s2)+str(s3)
print ("Syndrome is:")
print (ss)
correct_msg = list(bits)
index = -1
if syndrome_dict[ss] != -1:
index = 7*i + syndrome_dict[ss]
else:
index = -1
print ("Error index")
print (index)
print (bits[index])
if correct_msg[index] == '0':
correct_msg[index]= '1'
elif correct_msg[index] == '1':
correct_msg[index] = '0'
correct_msg = correct_msg[:4]
correct_msg = "".join(correct_msg)
entire_msg += correct_msg
print ("The correct msg")
print entire_msg
sequence2 = raw_input("Enter your msg")
get_syndrome(sequence2)
raw_input("Press Enter to exit")As usual, link to the github.
To sum up, here is the complete list of steps that we have implemented and that you may implement yourself to set your error-prone message transmission system up and running.*
Encode your textual message using Huffman algorithm (or Shannon algorithm if you want)
Apply Hamming encoder on the generated array of 0s and 1s
Apply noise generator on the encoded message
Apply Hamming decoder on the noisy data
Apply Huffman decoded on the decoded noisy data
Compare initial and newly generated strings (they should be different)
Apply error correction algorithm on the noisy data
Apply Hamming decoder on the corrected message
Apply Huffman decoded on the decoded message
Compare input and output strings (they should now be equal).
Great! We now can proudly claim that we have implemented a good telecommunication system that is resistant to the noise on unsafe communication channels.
Let the force be with you!
Comments