Theory of Coding: Maximum-Likelihood Decoding

First define the code $C_1$ as listed in the problem, consisting of eight codewords.

In [1]:
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.

In [6]:
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.

In [67]:
def bit5(num, pos):
    # assume num is codeword in form a1a2a3a4a5 where each a is bit
    return (num & (1 << 5-pos)) >> 5-pos
In [68]:
print format(C1[4], '05b')
for b in range(1, 6):
    print bit5(C1[4], b)
10011
1
0
0
1
1

1: Parity check for $C_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$$

In [69]:
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

2: Designing $C_2$

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$$.

In [70]:
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$.

In [97]:
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,

In [98]:
def weight(n):
    return bin(n).count("1")
In [100]:
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.

3: Designing a code in $\mathbb{B}^4$

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.

$$a_3 = a_1 ; a_4 = a_1 + a_2$$
In [103]:
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
In [111]:
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
In [112]:
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