Information Theory and Coding - Codes: The Guide to Secrecy from Ancient to Modern Times - page 454

Now suppose that we want to decode the received vector r =(1 , 0 , 1 , 0 , 1 , 0 , 0)
using syndrome decoding. Thus, we calculate S ( r )= r P t =(0 , 0 , 1) , which
is the last column of P . Hence, we need only correct the last entry of r to
get the correct codeword c =(1 , 0 , 1 , 0 , 1 , 0 , 1) . The reason for this is that the
error vector can have weight at most 1 , so if the syndrome is nonzero, then the
correction must be in the position corresponding to the column that the syndrome
represents. This simple decoding method is explained in what follows.

Decoding with Hamming Codes : Decoding with Ham(n , 2) can be done
with ease. Since Ham(r , 2) is a perfect single-error correcting code, the nonzero
coset leaders are the vectors,

r j =(0 , 0 ,..., 1 , 0 ,..., 0) ,

where the onlynonzero term is a 1 in exactlythe j th position for j =
1 , 2 ,..., 2 r

2 . Thus, calculating the syndrome via the parity-

− 1= N in F

check matrix P , we get

S ( r j )= r j P t ,
which is exactlythe transpose of the j th column of P . Hence, the syndrome
explicitlyand directlyidentifies the error location within the received vector.
Therefore, this allows a special, simpler syndrome decoding than in the general
case, as follows.

Syndrome Decoding of Hamming Codes

1. For a received vector, r , calculate the syndrome S ( r )= r P t .
2. If S ( r )= 0 , then r is the correct codeword.

= 0 , then S ( r ) is the transpose of a unique column of P , the j th
one, say. To get the correct codeword, add 1 to position j of r .

3. If S ( r )

We illustrated the above at the end of Example 11.11. The Hamming codes
are clearlya special case of the general linear codes discussed earlier, since they
can correct onlyone error. Theywere discovered byHamming in 1950 (see
[117]) and byGolayin 1949 (see [105]-[107]). The latter is responsible for one
of the most singular and important codes in the historyof error correction.

Golay Codes
In his 1949 paper, Golaypresented a binar, linear, perfect [23 , 12 , 7]-code,
named the G 23 -code, that satisfies rather amazing properties. In his search for

a perfect code Golayobserved that

23
j

=2 11 = 23
0

+ 23
1

+ 23
2

+ 23
3

=2 23 − 12 ,

3

j =0