First define the code $C_1$ as listed in the problem, consisting of eight codewords.
C1 = [0b00000,
0b00111,
0b01001,
0b01110,
0b10011,
0b10100,
0b11010,
0b11101]
Verify that this works. The format string specifies that we should zero-pad the output, it should be five characters wide, and use the binary (base 2) representation.
for each in C1:
print format(each, '05b') # print leading zeros, width 5, binary representation
00000 00111 01001 01110 10011 10100 11010 11101
Python seems more painful for bitwise math than I'd like. Perhaps there is an easier way to return a specific bit in the string, but for our purposes it's easiest to AND with a 1 in the proper spot, then move that bit over to the right and return it only. We could do it as a boolean (if it's greater than zero) but that would probably increase the complexity of working with the return value. So we'll just do the math instead.
def bit5(num, pos):
# assume num is codeword in form a1a2a3a4a5 where each a is bit
return (num & (1 << 5-pos)) >> 5-pos
print format(C1[4], '05b')
for b in range(1, 6):
print bit5(C1[4], b)
10011 1 0 0 1 1
Verify that every codeword $a_1a_2a_3a_4a_5$ in $C_1$ satisifies the following two parity-check equations: $$a_4 = a_1 + a_3$$ $$a_5 = a_1 + a_2 + a_3$$
for word in C1:
print bit5(word, 4) == bit5(word, 1) ^ bit5(word, 3), bit5(word, 5) == bit5(word, 1) ^ bit5(word, 2) ^ bit5(word, 3)
True True True True True True True True True True True True True True True True
Let $C_2$ be the following code in $\mathbb{B}^6$. The first three positions are the information positions, and every codeword $a_1a_2a_3a_4a_5a_6$ satisifies the parity-check equations $$a_4 = a_2$$ $$a_5 = a_1 + a_2$$ $$a_6 = a_1 + a_2 + a_3$$.
def bit6(num, pos):
# assume num is codeword in form a1a2a3a4a5a6 where each a is bit
return (num & (1 << 6-pos)) >> 6-pos
(a) List the codewords of $C_2$.
C2 = []
for info in range(0, 8):
word = info << 3
C2.append(word + \
(bit6(word, 2) << 2) + \
((bit6(word, 1) ^ bit6(word, 2)) << 1) + \
bit6(word, 1) ^ bit6(word, 2) ^ bit6(word, 3))
print format(C2[-1], '06b')
000000 001001 010111 011110 100011 101010 110100 111101
(b) Find the minimum distance of the code $C_2$.
From the text:
The distance between two binary words is the number of positions in which the words differ... The minimum distance in a code is the smallest distance among all the distances between two pairs of codewords.
We calculate the distance as the weight of the sum of the two words. So we add each pair of codewords in $C_2$ (using bitwise XOR). To calculate their weight in Python,
def weight(n):
return bin(n).count("1")
mindist = 999
for w1 in range(0, 8):
for w2 in range(0,8):
if w1 == w2:
continue
dist = weight(C2[w1] ^ C2[w2])
mindist = min(dist, mindist)
print mindist
2
(c) How many errors in any codeword of $C_2$ are sure to be detected? Explain.
The minimum distance of 2 means that we will detect any one error, but sometimes two errors can go undetected. This is because two errors (bit flips) may in fact change the codeword into another "valid" codeword.
Design a code in $\mathbb{B}^4$ where the first two positions are information positions. Give the parity-check equations, list the codewords, and find the minimum distance.
def bit4(num, pos):
# assume num is codeword in form a1a2a3a4 where each a is bit
# in "real" code we would have made all of these one function where width is a parameter
return (num & (1 << 4-pos)) >> 4-pos
C3 = []
for info in range(0,4):
word = info << 2
C3.append(word + \
(bit4(word, 1) << 1) + \
(bit4(word, 1) ^ bit4(word, 2)))
print format(C3[-1], '04b')
0000 0101 1011 1110
mindist = 999
for w1 in range(0, 4):
for w2 in range(0,4):
if w1 == w2:
continue
dist = weight(C2[w1] ^ C2[w2])
mindist = min(dist, mindist)
print mindist
2