I am trying to implement my own version of Hamming code with even parity (as shown here, except I'm starting counting the bits from left to right, rather than right to left) in Python.
My code is as follows:
# Python program to demonstrate Hamming code
def calcCheckBits(m):
# Use the formula 2 ^ r >= m + r + 1 to calculate the number of redundant bits.
# Iterate over 0 ... m and return the value that satisfies the equation.
for i in range(m):
if(2**i >= m + i + 1):
print("Number of redundant bits: " + str(i))
return i
def posCheckBits(data, r):
# Check bits are placed at the positions that correspond to the power of 2.
j = 0
k = 1
m = len(data)
res = ''
# If position is power of 2, then insert '0'; else, append the data.
for i in range(1, m + r + 1):
if(i == 2**j):
print("If " + str(i) + " == " + str(2**j))
res = res + '0'
print("check bit placed at position " + str(i))
print("res = " + res)
j += 1
else:
res = res + data[k - 1]
print("appending data at position " + str(i))
print("res = " + res)
k += 1
print("res: " + res)
return res
def determineCheckBits(data, r):
# Check bits are placed at the positions that correspond to powers of 2.
j = 0
m = len(data)
res = data
activatedBitCounter = 0
# If position i is a power of 2, then find the value of the check bit; else, do nothing.
for i in range(1, m + r + 1):
if(i == 2**j):
contributedToBy = [] # the bits that have i in their sum of powers of 2
print("If " + str(i) + " == " + str(2**j))
# Find the values that i is contributed to by (that is, the values where i contributes to its decomposition into a sum of powers of 2)
print("Now finding the values where " + str(i) + " contributes to its decomposition into a sum of powers of 2.")
for y in range(3, m + r + 1):
powers = []
z = 1
while z <= y:
if z & y:
powers.append(z)
z <<= 1
print("The list of powers is " + str(powers))
print("The powers of 2 that sum to " + str(y) + " are ")
for l in range(len(powers)):
print(powers[l])
if(i in powers):
contributedToBy.append(y)
print("The bits that have " + str(i) + " in their sum of powers of 2 are ")
for l in range(len(contributedToBy)):
print(contributedToBy[l])
for l in contributedToBy:
if(int(res[l - 1]) == 1):
activatedBitCounter += 1
# Check if the number of activated bits is odd.
# If so, then, since we want even parity, set the checkbit to 1; else, set to 0.
if((activatedBitCounter % 2) != 0):
res[i] = 1
print("activatedBitCounter is " + str(activatedBitCounter) + " so set bit " + str(i) + " of res to 1")
print("res is now " + str(res))
else:
res[i] = 0
print("activatedBitCounter is " + str(activatedBitCounter) + " so set bit " + str(i) + " of res to 0")
print("res is now " + str(res))
activatedBitCounter = 0 # reset counter
j += 1 # Append j by 1 to move onto next power
else:
print("else, position " + str(i) + " is not a power of 2, so res = " + res)
print("Final res value from function determineCheckBits: " + res)
return res
# Enter the data to be transmitted
data = '1100011' # codeword
print("data is: " + data)
# Calculate the number of parity bits required
m = len(data)
r = calcCheckBits(m)
# Determine the positions of check bits
arr = posCheckBits(data, r)
# Determine the check bits
arr = determineCheckBits(arr, r)
The transmitted codeword in this case is 1100011.
Each bit whose ordinal position is a power of 2 (1, 2, 4, 8) is a check bit and forces the parity of some 'collection' of bits including itself. Parity may be forced to be either even or odd.
A data bit contributes to the parity of all the bits in its decomposition into a sum of powers of 2. For example:
3 = 2 + 1
7 = 4 + 2 + 1
11 = 8 + 2 + 1
Making a list of these:
1 is contributed to by 3, 5, 7, 9, 11
2 is contributed to by 3, 6, 7, 10, 11
4 is contributed to by 5, 6, 7
8 is contributed to by 9, 10, 11
We then put the data bits in their positions and calculate each check bit.
For example, for 1100011, using even parity:
1 is contributed to by 3, 5, 7, 9, 11, and if we look at these bits for check 1, we have a 1 at bits 3, 5, and 11, which is odd (1 + 1 + 1 = 3), so since we want even parity, we set the bit 1 to 1. Skipping to 8, we see that 8 is contributed to by 9, 10, 11, and if we look at these bits for check 4, we have a 1 at bits 10 and 11, which is even (1 + 1 = 2), so since want even parity, we set the bit 8 to 0. This is how we get 11111000011.
The code above should produce 11111000011 from the input 1100011.
As you can see in the code, I've added a bunch of print statements for debugging. The problem is that this python code just randomly stops outputting anything at
The powers of 2 that sum to 3 are
1
2
as seen here:
It's just stuck there.
This is very perplexing, because if I execute only the part of the code that contains this print statement, it seems to work fine:
def testPowers(m, r):
# If position i is power of 2, then find the value of the parity bit; else, do nothing.
j = 0
for i in range(1, m + r + 1):
if(i == 2**j):
contributedToBy = [] # the bits that have i in their sum of powers of 2
print("If " + str(i) + " == " + str(2**j))
# Find the values that i is contributed to by (that is, the values where i contributes to its decomposition into a sum of powers of 2)
print("Now finding the values where " + str(i) + " contributes to its decomposition into a sum of powers of 2.")
for y in range(3, m + r + 1):
powers = []
z = 1
while z <= y:
if z & y:
powers.append(z)
z <<= 1
print("The powers of 2 that sum to " + str(y) + " are ")
for l in range(len(powers)):
print(powers[l])
if(i in powers):
contributedToBy.append(y)
print("The bits that have " + str(i) + " in their sum of powers of 2 are ")
for l in range(len(contributedToBy)):
print(contributedToBy[l])
m = 7
r = 4
testPowers(m, r)
I've only just started learning Python, so I honestly have no idea what's going wrong. Why isn't my code working, and how do I fix it?
I think I fixed the indentation error with z <<= 1
, as Tim Roberts suggested, but now I get another error.
# Python program to demonstrate Hamming code
def calcCheckBits(m):
# Use the formula 2 ^ r >= m + r + 1 to calculate the number of redundant bits.
# Iterate over 0 ... m and return the value that satisfies the equation.
for i in range(m):
if(2**i >= m + i + 1):
print("Number of redundant bits: " + str(i))
return i
def posCheckBits(data, r):
# Check bits are placed at the positions that correspond to the power of 2.
j = 0
k = 1
m = len(data)
res = ''
# If position is power of 2, then insert '0'; else, append the data.
for i in range(1, m + r + 1):
if(i == 2**j):
print("If " + str(i) + " == " + str(2**j))
res = res + '0'
print("check bit placed at position " + str(i))
print("res = " + res)
j += 1
else:
res = res + data[k - 1]
print("appending data at position " + str(i))
print("res = " + res)
k += 1
print("res: " + res)
return res
def determineCheckBits(data, r):
# Check bits are placed at the positions that correspond to powers of 2.
j = 0
m = len(data)
res = data
activatedBitCounter = 0
# If position i is a power of 2, then find the value of the check bit; else, do nothing.
for i in range(1, m + r + 1):
if(i == 2**j):
contributedToBy = [] # the bits that have i in their sum of powers of 2
print("If " + str(i) + " == " + str(2**j))
# Find the values that i is contributed to by (that is, the values where i contributes to its decomposition into a sum of powers of 2)
print("Now finding the values where " + str(i) + " contributes to its decomposition into a sum of powers of 2.")
for y in range(3, m + r + 1):
powers = []
z = 1
while z <= y:
if z & y:
powers.append(z)
z <<= 1
print("The list of powers is " + str(powers))
print("The powers of 2 that sum to " + str(y) + " are ")
for l in range(len(powers)):
print(powers[l])
if(i in powers):
contributedToBy.append(y)
print("The bits that have " + str(i) + " in their sum of powers of 2 are ")
for l in range(len(contributedToBy)):
print(contributedToBy[l])
for l in contributedToBy:
if(int(res[l - 1]) == 1):
activatedBitCounter += 1
# Check if the number of activated bits is odd.
# If so, then, since we want even parity, set the checkbit to 1; else, set to 0.
if((activatedBitCounter % 2) != 0):
res[i] = 1
print("activatedBitCounter is " + str(activatedBitCounter) + " so set bit " + str(i) + " of res to 1")
print("res is now " + str(res))
else:
res[i] = 0
print("activatedBitCounter is " + str(activatedBitCounter) + " so set bit " + str(i) + " of res to 0")
print("res is now " + str(res))
activatedBitCounter = 0 # reset counter
j += 1 # Append j by 1 to move onto next power
else:
print("else, position " + str(i) + " is not a power of 2, so res = " + res)
print("Final res value from function determineCheckBits: " + res)
return res
# Enter the data to be transmitted
data = '1100011' # codeword
print("data is: " + data)
# Calculate the number of parity bits required
m = len(data)
r = calcCheckBits(m)
# Determine the positions of check bits
arr = posCheckBits(data, r)
# Determine the check bits
arr = determineCheckBits(arr, r)
Error:
appending data at position 11
res = 00101000011
res: 00101000011
If 1 == 1
Now finding the values where 1 contributes to its decomposition into a sum of powers of 2.
The list of powers is [1, 2]
The powers of 2 that sum to 3 are
1
2
The list of powers is [4]
The powers of 2 that sum to 4 are
4
The list of powers is [1, 4]
The powers of 2 that sum to 5 are
1
4
The list of powers is [2, 4]
The powers of 2 that sum to 6 are
2
4
The list of powers is [1, 2, 4]
The powers of 2 that sum to 7 are
1
2
4
The list of powers is [8]
The powers of 2 that sum to 8 are
8
The list of powers is [1, 8]
The powers of 2 that sum to 9 are
1
8
The list of powers is [2, 8]
The powers of 2 that sum to 10 are
2
8
The list of powers is [1, 2, 8]
The powers of 2 that sum to 11 are
1
2
8
The list of powers is [4, 8]
The powers of 2 that sum to 12 are
4
8
The list of powers is [1, 4, 8]
The powers of 2 that sum to 13 are
1
4
8
The list of powers is [2, 4, 8]
The powers of 2 that sum to 14 are
2
4
8
The list of powers is [1, 2, 4, 8]
The powers of 2 that sum to 15 are
1
2
4
8
The bits that have 1 in their sum of powers of 2 are
3
5
7
9
11
13
15
Traceback (most recent call last):
File "/Users/x/testMultiParts.py", line 106, in <module>
arr = determineCheckBits(arr, r)
File "/Users/x/testMultiParts.py", line 73, in determineCheckBits
if(int(res[l - 1]) == 1):
IndexError: string index out of range
Again, the other program doesn't have this error:
If 1 == 1
Now finding the values where 1 contributes to its decomposition into a sum of powers of 2.
The powers of 2 that sum to 3 are
1
2
The powers of 2 that sum to 4 are
4
The powers of 2 that sum to 5 are
1
4
The powers of 2 that sum to 6 are
2
4
The powers of 2 that sum to 7 are
1
2
4
The powers of 2 that sum to 8 are
8
The powers of 2 that sum to 9 are
1
8
The powers of 2 that sum to 10 are
2
8
The powers of 2 that sum to 11 are
1
2
8
The bits that have 1 in their sum of powers of 2 are
3
5
7
9
11
# Python program to demonstrate Hamming code
def calcCheckBits(m):
# Use the formula 2 ^ r >= m + r + 1 to calculate the number of redundant bits.
# Iterate over 0 ... m and return the value that satisfies the equation.
for i in range(m):
if(2**i >= m + i + 1):
print("Number of redundant bits: " + str(i))
return i
def posCheckBits(res, r):
# Check bits are placed at the positions that correspond to the power of 2.
j = 0
k = 1
m = len(data)
res = ''
# If position is power of 2, then insert '0'; else, append the data.
for i in range(1, m + r + 1):
if(i == 2**j):
print("If " + str(i) + " == " + str(2**j))
res = res + '0'
print("check bit placed at position " + str(i))
print("res = " + res)
j += 1
else:
res = res + data[k - 1]
print("appending data at position " + str(i))
print("res = " + res)
k += 1
print("res: " + res)
return res
def determineCheckBits(res, r):
# Check bits are placed at the positions that correspond to powers of 2.
j = 0
res = list(data)
m = len(res)
activatedBitCounter = 0
print("At the beginning, res is " + str(res))
print("At the beginning, m is " + str(m))
# If position i is a power of 2, then find the value of the check bit; else, do nothing.
for i in range(1, m + r + 1):
if(i == 2**j):
contributedToBy = [] # the bits that have i in their sum of powers of 2
print("If " + str(i) + " == " + str(2**j))
# Find the values that i is contributed to by (that is, the values where i contributes to its decomposition into a sum of powers of 2)
print("Now finding the values where " + str(i) + " contributes to its decomposition into a sum of powers of 2.")
for y in range(3, m + r + 1):
powers = []
z = 1
while z <= y:
if z & y:
powers.append(z)
z <<= 1
print("The list of powers is " + str(powers))
print("The powers of 2 that sum to " + str(y) + " are ")
for l in range(len(powers)):
print(powers[l])
if(i in powers):
contributedToBy.append(y)
print("The bits that have " + str(i) + " in their sum of powers of 2 are ")
for l in range(len(contributedToBy)):
print(contributedToBy[l])
for l in contributedToBy:
if(int(res[l - 1]) == 1):
activatedBitCounter += 1
# Check if the number of activated bits is odd.
# If so, then, since we want even parity, set the checkbit to 1; else, set to 0.
if((activatedBitCounter % 2) != 0):
res[i] = '1'
print("activatedBitCounter is " + str(activatedBitCounter) + " so set bit " + str(i) + " of res to 1")
print("res is now " + str(res))
else:
res[i] = '0'
print("activatedBitCounter is " + str(activatedBitCounter) + " so set bit " + str(i) + " of res to 0")
print("res is now " + str(res))
activatedBitCounter = 0 # reset counter
j += 1 # Append j by 1 to move onto next power
else:
print("else, position " + str(i) + " is not a power of 2, so res = " ''.join(res))
res = ''.join(res)
print("Final res value from function determineCheckBits: " + res)
return res
# Enter the data to be transmitted
data = '1100011' # codeword
print("data is: " + data)
# Calculate the number of parity bits required
m = len(data)
r = calcCheckBits(m)
# Determine the positions of check bits
arr = posCheckBits(data, r)
# Determine the check bits
arr = determineCheckBits(arr, r)
Error:
res = 00101000011
res: 00101000011
At the beginning, res is ['1', '1', '0', '0', '0', '1', '1']
At the beginning, m is 7
If 1 == 1
Now finding the values where 1 contributes to its decomposition into a sum of powers of 2.
The list of powers is [1, 2]
The powers of 2 that sum to 3 are
1
2
The list of powers is [4]
The powers of 2 that sum to 4 are
4
The list of powers is [1, 4]
The powers of 2 that sum to 5 are
1
4
The list of powers is [2, 4]
The powers of 2 that sum to 6 are
2
4
The list of powers is [1, 2, 4]
The powers of 2 that sum to 7 are
1
2
4
The list of powers is [8]
The powers of 2 that sum to 8 are
8
The list of powers is [1, 8]
The powers of 2 that sum to 9 are
1
8
The list of powers is [2, 8]
The powers of 2 that sum to 10 are
2
8
The list of powers is [1, 2, 8]
The powers of 2 that sum to 11 are
1
2
8
The bits that have 1 in their sum of powers of 2 are
3
5
7
9
11
Traceback (most recent call last):
File "/Users/x/testMultiParts.py", line 108, in <module>
arr = determineCheckBits(arr, r)
File "/Users/x/testMultiParts.py", line 75, in determineCheckBits
if(int(res[l - 1]) == 1):
IndexError: list index out of range
Ok, I think I got it!
# Python program to demonstrate Hamming code
def calcCheckBits(m):
# Use the formula 2 ^ r >= m + r + 1 to calculate the number of redundant bits.
# Iterate over 0 ... m and return the value that satisfies the equation.
for i in range(m):
if(2**i >= m + i + 1):
print("Number of redundant bits: " + str(i))
return i
def posCheckBits(res, r):
# Check bits are placed at the positions that correspond to the power of 2.
j = 0
k = 1
m = len(data)
res = ''
# If position is power of 2, then insert '0'; else, append the data.
for i in range(1, m + r + 1):
if(i == 2**j):
print("If " + str(i) + " == " + str(2**j))
res = res + '0'
print("check bit placed at position " + str(i))
print("res = " + res)
j += 1
else:
res = res + data[k - 1]
print("appending data at position " + str(i))
print("res = " + res)
k += 1
print("res: " + res)
return res
def determineCheckBits(arr, r):
# Check bits are placed at the positions that correspond to powers of 2.
j = 0
res = list(arr)
m = len(data)
activatedBitCounter = 0
print("At the beginning, res is " + str(res))
print("At the beginning, m is " + str(m))
# If position i is a power of 2, then find the value of the check bit; else, do nothing.
for i in range(1, m + r + 1):
if(i == 2**j):
contributedToBy = [] # the bits that have i in their sum of powers of 2
print("If " + str(i) + " == " + str(2**j))
# Find the values that i is contributed to by (that is, the values where i contributes to its decomposition into a sum of powers of 2)
print("Now finding the values where " + str(i) + " contributes to its decomposition into a sum of powers of 2.")
for y in range(3, m + r + 1):
powers = []
z = 1
while z <= y:
if z & y:
powers.append(z)
z <<= 1
print("The list of powers is " + str(powers))
print("The powers of 2 that sum to " + str(y) + " are ")
for l in range(len(powers)):
print(powers[l])
if(i in powers):
contributedToBy.append(y)
print("The bits that have " + str(i) + " in their sum of powers of 2 are ")
for l in range(len(contributedToBy)):
print(contributedToBy[l])
for l in contributedToBy:
print("contributedToBy is " + str(contributedToBy))
print("res is " + str(res))
print("res[l - 1] is " + res[l - 1])
if(int(res[l - 1]) == 1):
activatedBitCounter += 1
# Check if the number of activated bits is odd.
# If so, then, since we want even parity, set the checkbit to 1; else, set to 0.
if((activatedBitCounter % 2) != 0):
res[i - 1] = '1'
print("activatedBitCounter is " + str(activatedBitCounter) + " so set bit " + str(i) + " of res to 1")
print("res is now " + str(res))
else:
res[i - 1] = '0'
print("activatedBitCounter is " + str(activatedBitCounter) + " so set bit " + str(i) + " of res to 0")
print("res is now " + str(res))
activatedBitCounter = 0 # reset counter
j += 1 # Append j by 1 to move onto next power
else:
print("else, position " + str(i) + " is not a power of 2, so res = " ''.join(res))
res = ''.join(res)
print("Final res value from function determineCheckBits: " + res)
return res
# Enter the data to be transmitted
data = '1100011' # codeword
print("data is: " + data)
# Calculate the number of parity bits required
m = len(data)
r = calcCheckBits(m)
# Determine the positions of check bits
arr = posCheckBits(data, r)
# Determine the check bits
arr = determineCheckBits(arr, r)
Output:
res = 00101000011
res: 00101000011
At the beginning, res is ['0', '0', '1', '0', '1', '0', '0', '0', '0', '1', '1']
At the beginning, m is 7
If 1 == 1
Now finding the values where 1 contributes to its decomposition into a sum of powers of 2.
The list of powers is [1, 2]
The powers of 2 that sum to 3 are
1
2
... skip to 8 == 8
:
If 8 == 8
Now finding the values where 8 contributes to its decomposition into a sum of powers of 2.
The list of powers is [1, 2]
The powers of 2 that sum to 3 are
1
2
The list of powers is [4]
The powers of 2 that sum to 4 are
4
The list of powers is [1, 4]
The powers of 2 that sum to 5 are
1
4
The list of powers is [2, 4]
The powers of 2 that sum to 6 are
2
4
The list of powers is [1, 2, 4]
The powers of 2 that sum to 7 are
1
2
4
The list of powers is [8]
The powers of 2 that sum to 8 are
8
The list of powers is [1, 8]
The powers of 2 that sum to 9 are
1
8
The list of powers is [2, 8]
The powers of 2 that sum to 10 are
2
8
The list of powers is [1, 2, 8]
The powers of 2 that sum to 11 are
1
2
8
The bits that have 8 in their sum of powers of 2 are
8
9
10
11
contributedToBy is [8, 9, 10, 11]
res is ['1', '1', '1', '1', '1', '0', '0', '0', '0', '1', '1']
res[l - 1] is 0
contributedToBy is [8, 9, 10, 11]
res is ['1', '1', '1', '1', '1', '0', '0', '0', '0', '1', '1']
res[l - 1] is 0
contributedToBy is [8, 9, 10, 11]
res is ['1', '1', '1', '1', '1', '0', '0', '0', '0', '1', '1']
res[l - 1] is 1
contributedToBy is [8, 9, 10, 11]
res is ['1', '1', '1', '1', '1', '0', '0', '0', '0', '1', '1']
res[l - 1] is 1
activatedBitCounter is 2 so set bit 8 of res to 0
res is now ['1', '1', '1', '1', '1', '0', '0', '0', '0', '1', '1']
else, position 91 is not a power of 2, so res = 1 is not a power of 2, so res = 1 is not a power of 2, so res = 1 is not a power of 2, so res = 1 is not a power of 2, so res = 0 is not a power of 2, so res = 0 is not a power of 2, so res = 0 is not a power of 2, so res = 0 is not a power of 2, so res = 1 is not a power of 2, so res = 1
else, position 101 is not a power of 2, so res = 1 is not a power of 2, so res = 1 is not a power of 2, so res = 1 is not a power of 2, so res = 1 is not a power of 2, so res = 0 is not a power of 2, so res = 0 is not a power of 2, so res = 0 is not a power of 2, so res = 0 is not a power of 2, so res = 1 is not a power of 2, so res = 1
else, position 111 is not a power of 2, so res = 1 is not a power of 2, so res = 1 is not a power of 2, so res = 1 is not a power of 2, so res = 1 is not a power of 2, so res = 0 is not a power of 2, so res = 0 is not a power of 2, so res = 0 is not a power of 2, so res = 0 is not a power of 2, so res = 1 is not a power of 2, so res = 1
Final res value from function determineCheckBits: 11111000011
And so we have 11111000011, as required!
I cleaned up the last part by changing it back to
else:
print("else, position " + str(i) + " is not a power of 2, so res = " + str(res))
This seems to clean up the output:
res is now ['1', '1', '1', '1', '1', '0', '0', '0', '0', '1', '1']
else, position 9 is not a power of 2, so res = ['1', '1', '1', '1', '1', '0', '0', '0', '0', '1', '1']
else, position 10 is not a power of 2, so res = ['1', '1', '1', '1', '1', '0', '0', '0', '0', '1', '1']
else, position 11 is not a power of 2, so res = ['1', '1', '1', '1', '1', '0', '0', '0', '0', '1', '1']
Final res value from function determineCheckBits: 11111000011
You're going to kick yourself. When you Ctrl-C to terminate the program, did you notice where it was looping?
The list of powers is [1, 2]
The powers of 2 that sum to 3 are
1
2
^CTraceback (most recent call last):
File "x.py", line 107, in <module>
arr = determineCheckBits(arr, r)
File "x.py", line 60, in determineCheckBits
while z <= y:
KeyboardInterrupt
If you'll look at that loop, you'll see that z
never increments, so it loops forever. That's because line 63:
z <<= 1
is indented in one too many indents. If you fix that, it moves on. It does eventually get a different error, but that will be for another question.
EDIT
Other problems. In determineCheckBits
, you are treating res
as if it is a list of ints, trying to assign elements by index. It is not, it is a string. So, at the beginning, change:
res = data
to
res = list(data)
Towards the bottom, change
res[i] = 1
to
res[i] = '1'
and do the same 4 lines later with 0. Then, change the last 5 lines to:
else:
print("else, position " + str(i) + " is not a power of 2, so res = " + ''.join(res))
res = ''.join(res)
print("Final res value from function determineCheckBits: " + res)
return res
and I think you will have happiness.