Digital Signal Processing Reference
In-Depth Information
data bits at the output of the encoder. The duration of this influence strongly
depends on the internal memory (i.e. number of possible register states) of the
encoder.
The coding rate of the encoder is a crucial factor and gives the fe-coder its
error correcting capabilities. If the coding rate is R
k/l
,
l
encoded bits are
produced for each
k
bits of information at the input. From this moment on, the
reader is encouraged to reason in terms of bit-sequences instead of individual
bits. For a certain sequence length, the resulting number of possible output
data sequences is 2
l
−
k
times larger than the number of bit combinations at the
input. However, starting from a certain internal register state of the encoder,
only a small
subset
of all possible output sequences can be produced by the
fec algorithm at any moment during the encoding process. Of course, the
decoder at the other end of the transmission chain is more than fully aware of
this fact.
Suppose that both encoder and decoder start with the same register states. Dur-
ing the transmission of the encoded sequence, noise accumulates on the signal.
As a result, the demapper in the receiver makes an incorrect decision and some
erroneous bits show up somewhere in the received data sequence. At the same
moment, the decoding algorithm
8
in the receiver tracks the same path of states
followed by the encoder and tries to recover the original 'unencoded' infor-
mation. At the location of an invalid data bit, the received sequence shortly
diverges from the path followed by the original sequence, and then remerges
back to the correct path (Figure 2.3). The decoding algorithm, which is still
tracking the succession of states followed by the encoder, perfectly knows the
allowed subset
of sequences that can be produced by the encoder when the reg-
isters are in a particular state. Therefore, the decoding algorithm tracks back
from the moment that an error is detected and tries to recover the sequence with
the largest possibility of being originally transmitted. This is obviously the se-
quence from the - at that moment - allowed subset which has the smallest
possible divergence ('distance') from the received sequence. The probability
of error depends on the minimum distance between the allowed sequences in a
particular subset of the encoder.
This observation explains the nonlinear performance of error-coding tech-
niques: When the sequence tracking algorithm in the decoder fails to recover
the correct sequence, the internal registers will be trapped in an erroneous state.
However, all future decisions of the decoder rely on the fact that the register
states of encoder and decoder are synchronized. One single uncorrected error
will propagate and generates a burst of consecutive errors.
=
8
The most popular decoding algorithm used for fec codes is the Viterbi algorithm [Vit67].
