GATE 2021 EC – Question 44
A digital transmission system uses a $(7,4)$ systematic linear Hamming code for transmitting data over a noisy channel. If three of the message-codeword pairs in this code $(\mathbf m_i;\ \mathbf c_i)$, where $\mathbf c_i$ is the codeword corresponding to the $i^{th}$ message $\mathbf m_i$, are known to be $(1100;\ 0101100)$, $(1110;\ 0011110)$ and $(0110;\ 1000110)$, then which of the following is a valid codeword in this code?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) 0001011
Explanation
In each pair the last four bits are the message, so a codeword is $[p_1p_2p_3\,|\,m_1m_2m_3m_4]$. By linearity $c(0010)=c(1100)\oplus c(1110)=0110010$, $c(0100)=c(0110)\oplus c(0010)=1110100$ and $c(1000)=c(1100)\oplus c(0100)=1011000$. The parity rows of a Hamming code must be distinct and of weight at least 2, so the remaining row for $0001$ is the only one left, $110$, i.e. $c(0001)=1100001$. The message $1011$ is $1000\oplus0010\oplus0001$, whose parity is $101\oplus011\oplus110=000$, giving $0001011$, which is option C. Options A, B and D have the wrong parity bits.