Question 4.5: For a 12-bit data string of 101100010010, determine the numb......
For a 12-bit data string of 101100010010, determine the number of Hamming bits required, arbitrarily place the Hamming bits into the data string, determine the logic condition of each Hamming bit, assume an arbitrary single-bit transmission error, and prove that the Hamming code will successfully detect the error.
Substituting m = 12 into Equation 2, the number of Hamming bits is
2^{n} ≥ m + n + 1 (2)
for n = 4 \qquad\qquad 2^{4}=16 ≥ 12 + 4 + 1 = 17
Because 16 < 17, four Hamming bits are insufficient:
for n = 5 \qquad\qquad 2^{5}=32 ≥ 12 + 5 + 1 = 18
Because 32 > 18, five Hamming bits are sufficient, and a total of 17 bits make up the data stream (12 data plus five Hamming).
Arbitrarily placing five Hamming bits into bit positions 4, 8, 9, 13, and 17 yields
\begin{matrix}bit \,\, position \quad17&16&15&14&13&12&11&10&9&8&7&6&5&4&3&2&1 \\[0.2cm] \qquad\qquad\qquad H & 1 & 0 & 1 & H & 1 &0 & 0 & H &H& 0& 1 & 0& H&0 & 1 &0\end{matrix}To determine the logic condition of the Hamming bits, express all bit positions that contain a logic 1 as a five-bit binary number and XOR them together:
\qquad\qquad\qquad\begin{matrix} \underline {Bit\,\,position} \\ 2 \\6 \\ \overline{XOR}\\12 \\\overline{XOR}\\ 14 \\\overline{XOR} \\16\\ \overline{XOR} \end{matrix} \qquad \begin{matrix} \underline {Binary\,\, number} \\ 00010 \\00110 \\ \overline{00100}\\01100 \\\overline{01000}\\ 01110 \\\overline{00110} \\10000\\ \overline{10110}& \,\, = Hamming \,\,bits \end{matrix} \qquad\qquad b_{17}=1,\qquad b_{13}=0,\qquad b_{9}=1,\qquad b_{8}=1,\qquad b_{4}=0The 17-bit Hamming code is
\begin{matrix} \qquad H&&&& H&&&& H& H&&&& H\\ \qquad 1& 1& 0 &1 &0& 1& 0& 0& 1& 1& 0& 1& 0& 0& 0& 1& 0 \end{matrix}Assume that during transmission, an error occurs in bit position 14. The received data stream is
\begin{matrix} \qquad\qquad 1 &1 &0\,\,\, \underbrace{\underline{\,0\,}}_\text{error}\,\,\, 0& 1 &0& 0& 1& 1& 0& 1& 0& 0& 0& 1& 0 \end{matrix}At the receiver, to determine the bit position in error, extract the Hamming bits and XOR them with the binary code for each data bit position that contains a logic 1:
\qquad\qquad\qquad\begin{matrix} \underline {Bit\,\,position} \\ Hamming\,\,bits \\2 \\ \overline{XOR}\\6 \\\overline{XOR}\\ 12 \\\overline{XOR} \\16\\ \overline{XOR} \end{matrix} \qquad \begin{matrix} \underline {Binary\,\, number} \\ 10110 \\00010 \\ \overline{10100}\\00110 \\\overline{10010}\\ 01100 \\\overline{11110} \\10000\\ \overline{01110}& \,\, = 14 \end{matrix}Therefore, bit position 14 contains an error.