We saw the Hamming code in Worksheet Exercise 8 on the first day of class, though we didn’t name it at the time. Here is a summary of its construction. It encodes 4-bit messages as 7-bit codewords by adding 3 parity bits. The parity bits are placed in positions 5, 6, and 7 of the codeword, while the message bits are placed in positions 1, 2, 3, and 4. The parity bits are computed as follows: To send a 4-bit message, you first create three additional bits as follows:
The 5th bit is a parity bit for the last three bits (it is 0 if there are an even number of 1s among the last three bits, and 1 if there are an odd number of 1s).
Give a representation of the Hamming code as a map from \(\{0,1\}^4\) to \(\{0,1\}^7\) using the bitwise XOR or addition modulo 2 operation. E.g. something like \(C(m_1, m_2, m_3, m_4) = (m_1, m_2, m_3, m_4, p_1, p_2, p_3)\) where \(p_1, p_2, p_3\) are expressions in terms of the message bits.
By experimenting with different codewords, conjecture a relationship between the distance of two codewords and the Hamming weight of their sum. How does this suggest we might compute the minimum distance of a linear code?
Use your representation of the first problem to find a lower bound on the Hamming weight of codewords corresponding to message vectors of weight 3 or 4.
