next up previous
Next: Summary of Hamming code Up: Pictorial view of the Previous: Encoding

Decoding

The received vector can be written into the picture in the same way. We look at each of the three circles to see if its parity is even. The fact that all codewords differ from each other in at least three bits means that if the noise has flipped any one or two bits, some of these parity checks will be violated.

Let us consider noise patterns of weight one, i.e., restrict attention to the case where just one bit is flipped. For example, if tex2html_wrap_inline3312, then the received pattern will be as shown in figure 1.10a.

   figure1368
Figure: Pictorial representation of decoding of the Hamming (7,4) code. The bits that are flipped relative to figure 1.9b are labelled by tex2html_wrap_inline3314. The violated parity checks are highlighted by dashed circles. One of the seven bits is the most probable suspect to account for each `syndrome', i.e., each pattern of violated and satisfied parity checks.

This figure shows highlighted the two circles in which the parity is not even. The bit tex2html_wrap_inline3316 that was flipped lies at the intersection of these two circles and outside the third circle, and so it is readily identified as the only single bit capable of explaining the syndrome.

Similarly figure 1.10b shows what happens if one of the parity bits, tex2html_wrap_inline3318, is flipped by the noise. Just one of the checks is violated, readily identifying this bit as the only single bit capable of explaining the syndrome.

And if the central bit tex2html_wrap_inline3320 is received flipped, figure 1.10c shows that all three checks are violated, so the centre bit is readily identified as the suspect bit.

  figure1382
Figure: Transmitting 10000 source bits over a binary symmetric channel with f=0.1 using a (7,4) Hamming code. The probability of decoded bit error is about 7%. [Dilbert image Copyright©1997 United Feature Syndicate, Inc., used with permission.]


next up previous
Next: Summary of Hamming code Up: Pictorial view of the Previous: Encoding

David J.C. MacKay
Sat May 10 23:05:10 BST 1997