Page 343 - Satellite Communications, Fourth Edition

Error Control Coding 323

experience errors as a result of impulse-type noise or impulse-type inter-
ference. Reed-Solomon (R-S) codes are designed to correct errors under
these conditions. Instead of encoding directly in bits, the bits are grouped
into symbols, and the datawords and codewords are encoded in these
symbols. Errors affecting a group of bits are most likely to affect only
one symbol that can be corrected by the R-S code.
Let the number of bits per symbol be k; then the number of possible
k
symbols is q 2 (referred to as a q-ary alphabet). Let K be the number
of symbols in a dataword and N be the number of symbols in a codeword.
Just as in the block code where k-bit datawords were mapped into n-bit
codewords, with the R-S code, datawords of K symbols are mapped into
codewords of N symbols. The additional N K redundant symbols are
derived from the message symbols but are not part of the message. The
K
N
number of possible codewords is 2 , but only 2 of these will contain
datawords, and these are the ones that are transmitted. It follows that
the rest of the codewords are redundant, but only in the sense that they
do not contribute to the message. If errors occur in transmission, there
is high probability that they will convert the permissible codewords
into one or another of the redundant words that the decoder at the
receiver is designed to recognize as an error. It will be noted that the
term high probability is used. There is always the possibility, however
remote, that enough errors occur to transform a transmitted codeword
into another legitimate codeword even though this was not the one
transmitted.
It will be observed that the wording of the preceding paragraph
parallels that given in Sec. 11.2 on block codes, except that here the
coding is carried out on symbols. Some of the design rules for the
R-S codes are
k
q 2
N q 1

2t N K
Here, t is the number of symbol errors that can be corrected. A simple
example will be given to illustrate these. Let k 2; then q 4, and these
four symbols may be labeled A, B, C,and D. In terms of the binary sym-
bols (bits) for this simple case, we could have A 00, B 01, C 10,
and D 11. One could imagine the binary numbers 00, 01, 10, and 11
being stored in memory locations labeled A, B, C,and D.
The number of symbols per codeword is N q 1 3. Suppose that
t 1; then the rule 2t N K gives K 1; that is, there will be one
K
symbol per dataword. Hence the number of datawords is q 4 (i.e., A,
N 3
B, C,or D), and the number of codewords is q 4 64. These will
P , BP P , CP P , and DP P ,
include permissible words of the form AP 1 2 3 4 5 6 7 8