$$ \text{Number of codewords} = M \\ \text{Length of code} = N = 2^m - 1 \\ \text{Dimension of code} = K = N - M \\ C(N, K) \\ \text{Generation matrix} = G_{[K \times n]} = \big [ I_{[k \times k]} \lvert A_{[k \times (n-k)]} \big ] \\ \text{Parity check matrix} = H_{[n - K \times n]} = \big [ A^T_{[n-k \times k]} \lvert I_{[(n-k) \times (n-k)]} \big ] \\ \text{Encoder} = c = x G \\ \text{syndrome} = s = y H^T = (c+e)H^T = eH^T $$

As an example, hamming code (7, 4) can be:

$$ G = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{bmatrix} $$

$$ H = \begin{bmatrix} 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 \end{bmatrix} $$

Syndrome decoding consist in taking the word with fewest number of errors.

1

1. Assume that a message contains 4 information bits, and that the transmission has a bit error probability of p. Derive expressions for the probability, \(P_w\), that a received message has undetected errors in the following cases:
   1. No parity bits are used (Hint: The probability is simply the probability that the received message contains errors)
   2. A (7,4) Hamming code is used and the decoder is error-correcting, i.e. able to correct one error
   3. The (7,4) Hamming code is used for error detection only, i.e. it is sure to detect up to two errors – and some more, but leave that out in your calculation

Calculate the probabilities for undetected errors for the two cases for p = \(10^{-3}, 10^{-4}, 10^{-5} \) and \(10^{-6}\).

1.1

Symbol probability is:

$$ P_w = 1 - (1 - P_b)^k \\ k = \log_2 M \\ M = \text{Number of different N-tuples (codewords)} $$

$$ p = 10^{-3} \Rightarrow P_w = 0.0394 = 3.9 \cdot 10^{-3} \\ p = 10^{-4} \Rightarrow P_w = 0.00399 = 3.9 \cdot 10^{-4} \\ p = 10^{-5} \Rightarrow P_w = 0.000394 = 3.9 \cdot 10^{-5} \\ p = 10^{-6} \Rightarrow P_w = 0.0000394 = 3.9 \cdot 10^{-6} \\ $$

1.2

Bounded distance decoder has the next \(P_w\):

$$ P_w = 1 - \sum_{j=0}^{T} \big ( {N \atop j} \big ) p^j (1 - p)^{N-j} = \sum_{j=T+1}^{N} \big ( {N \atop j} \big ) p^j (1 - p)^{N-j} \\ N = \text{Length of codeword} \\ T = \text{Number of errors that is capable to correct} $$

$$ p = 10^{-3} \Rightarrow P_w = 2.093 \cdot 10^{-5} \\ p = 10^{-4} \Rightarrow P_w = 2.093 \cdot 10^{-7} \\ p = 10^{-5} \Rightarrow P_w = 2.093 \cdot 10^{-9} \\ p = 10^{-6} \Rightarrow P_w = 2.093 \cdot 10^{-11} \\ $$

import math

T = 1 # Number of errors capable to decode without error
N = 7 # Length of codeword

comb = lambda x, y: (math.factorial(x)) / (math.factorial(y) * math.factorial(x - y))

def p_w_2 (T, N, p):
    result = 0
    for j in range(T+1, N):
        result += comb(N,j) * math.pow(p, j) * math.pow(1-p, N - j)
    return result

1.3

Sames as previous section, but with T = 2:

$$ p = 10^{-3} \Rightarrow P_w = 3.489 \cdot 10^{-8} \\ p = 10^{-4} \Rightarrow P_w = 3.489 \cdot 10^{-11} \\ p = 10^{-5} \Rightarrow P_w = 3.489 \cdot 10^{-14} \\ p = 10^{-6} \Rightarrow P_w = 3.489 \cdot 10^{-17} \\ $$

2

2. In this problem we shall consider the (7,4) Hamming code and some modifications:
   1. Determine the H matrix for the Hamming (7,4)-code. What do you notice about the 7 rows in the matrix? (Hint: It may help to interpret them as binary numbers)
   2. Extending the structure in the H matrix for the (7,4)-code, you are able to define the family of all Hamming codes. What is H for a (15,11)-code?
   3. Look at the 16 codewords of the Hamming (7,4) code. Four of these may be selected as rows in a matrix G which gives systematic encoding. Use this matrix to calculate the codeword for x = (1 0 1 1).
   4. Suppose that the received words are (0101100), (1111100), and (0111110). For each of these words, determine the syndrome bits and the restored information messages. Assuming that the last word was transmitted as (0101100), check the restored code word. What happened?
   5. Prove that the code is cyclic, i.e. a cyclic shift of a codeword gives another codeword (Hint: Look at the table of codewords).
   6. From the codewords, remove all words with an odd number of ones. Show that the remaining words form a (7,3) linear code (Hint: You could state the matrix G for this code and show that it gives the remaining words by a proper choice of the 3 information bits). This process is known as expurgation and a clever choice may improve the minimum distance as here.
   7. Another modification is extension of the (7,4) code with an extra parity check. What is the minimum distance of the (8,4) Extended Hamming code? Give a simple H matrix for the code, now with 4 columns, Give a G matrix for a systematic version of the code (Hint: Use the answer in point c).

1.1 1.2 1.3

There are multiple hamming code. The vectors in the generation matrix must be linearly independent. 1011 -> 1011000