Page 341 - Satellite Communications, Fourth Edition

Error Control Coding 321

values in a lookup table, (tabulated against known error patterns), and the
most likely match found. This is termed maximum likelihood decoding.
The Hamming codes described in the next section enables a single
error to be corrected, and in fact the syndrome gives the bit position of
the error. Suppose for example the codeword [1010010] as previously
determined is transmitted but a bit error occurs in the fifth bit from the
left, so that the received codeword is [1010110]. Applying Eq. (11.7)

1 1 1
1 1 0
1 0 1
s 5 [1 0 1 0 1 1 0]G0 1 1W
1 0 0
0 1 0
0 0 1

[100]

The fact that the syndrome is not zero indicates that an error has
occurred. For the case of Hamming codes discussed in Sec. 11.3, and of
which this is an example, the syndrome also shows which bit is in error.
The syndrome [100] corresponds to the fifth column (from the left) of the
parity check matrix H and this indicates that it is the fifth bit that is
in error. In general, with the Hamming code, if the syndrome corre-
sponds to column m then bit m is the one in error, and this can be
“flipped” to the correct value.

11.3 Cyclic Codes
Cyclic codes are a subclass of linear block codes. They possess the prop-
erty that a cyclic shift of a codeword is also a codeword. For example, if
a codeword consists of the elements {c c c c c c c }, then {c c c c 5
4
5
2
1
3
2
4
6
7
3
c c c } is also a codeword. The advantage of cyclic codes is that they are
6
1
7
easily implemented in practice through the use of shift registers and
modulo-2 adders. Cyclic codes are widely used in satellite transmission,
and the properties of the most important of these are summarized in the
following sections. Only certain combinations of k and n are permitted
in these codes. As pointed out in Taub and Schilling (1986), a code is an
invention, and these codes are named after their inventors.
11.3.1 Hamming codes
m
For an integer m 2, the k and n values are related as n 2 1 and
k n m. Thus some of the permissible combinations are shown in
Table 11.2: