next up previous
Next: Pictorial view of the Up: Block codes -- the Previous: Block codes -- the

Decoding the (7,4) Hamming code

When we invent a more complex encoder, the task of decoding the received vector tex2html_wrap_inline3083 becomes less straightforward. (The reader who is eager to see the denoument of the plot may skip ahead to section 1.2.5.)

If we assume that the channel is a binary symmetric channel and that all source vectors are equiprobable, a priori, then clearly the optimal decoder is one that identifies the source vector tex2html_wrap_inline3074 whose encoding tex2html_wrap_inline3236 differs from the received vector tex2html_wrap_inline3083 in the fewest bits. Is there an efficient way of finding this source vector?

In the special case of a linear code and a binary symmetric channel the decoding task can be re-expressed as syndrome decoding. The first four received bits tex2html_wrap_inline3269, purport to be the four source bits; and the received bits tex2html_wrap_inline3271 purport to be the parities of the source bits, as defined by the generator matrix tex2html_wrap_inline3253. So why not evaluate the three parity check bits for the received bits tex2html_wrap_inline3275, and see if they match the three received bits tex2html_wrap_inline3271? The differences (modulo 2) between these two triplets are called the ` ' of the received vector. If the syndrome is zero, that is, all three parity checks agree with the corresponding received bits, then the received vector is a codeword, and the most probable decoding is given by reading out its first four bits. If the syndrome is non-zero, then we are certain that the noise sequence for the present block was non-zero, and the syndrome is our pointer to the most probable underlying error pattern.

The operation of finding the syndrome vector can be described by a linear operation. If we define the tex2html_wrap_inline3279 matrix tex2html_wrap_inline3281 such that the matrix of equation (1.2) is
equation2107
where tex2html_wrap_inline3283 is the tex2html_wrap_inline3285 identity matrix, then the syndrome vector is tex2html_wrap_inline3287, where the parity check matrix tex2html_wrap_inline3289 is given by tex2html_wrap_inline3291; in the case of modulo 2 arithmetic, -1 = 1, so
equation2117
Since the received vector tex2html_wrap_inline3083 is given by tex2html_wrap_inline3268 and tex2html_wrap_inline3299=0, the syndrome decoding problem is then to find the most probable noise vector tex2html_wrap_inline3123 satisfying the equation
equation2129


next up previous
Next: Pictorial view of the Up: Block codes -- the Previous: Block codes -- the

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