Page 269 - Anatomy of a Robot

09_200256_CH09/Bergren 4/17/03 11:24 AM Page 254
254 CHAPTER NINE
would happen if that bit were in error. The decoder determines what the hypothetical
history would have looked like in this case. If the hypothetical history looks much bet-
ter, the decoder gives weight to the fact that the input bit may have been in error. Once
the decoder finds the most satisfactory hypothetical history, it outputs that hypotheti-
cal data as the real, corrected, unexpanded data.
As we mentioned before, if the Viterbi decoder cannot correct all the errors, it at least
collects them all in one place. Because it stores up the data history before deciding and
making an output, it will output all the recent errors in a burst as it fails in its task. Even
in failure, this is a key to success. The deinterleaver spreads out the burst of errors so
the RS codes can correct them. Picture the Viterbi decoder giving up, but sweeping its
mistakes into one corner and pointing them out to the RS decoder so they can be cleaned
up there instead.
As a reminder, this version of Viterbi coding pertains to the case where the trans-
mitting Viterbi encoder can expand the data before transmission. The encoder thus
organizes the unexpanded data into expanded data that has some recognizable patterns
in it. These recognizable data patterns are what the decoder looks at to determine if the
received, expanded data is suspicious. The metric the decoder uses to examine data is
the Hamming distance (the total number of bit differences) between the actual received
data and the hypothetical received data.
The Viterbi algorithm comes built in to many standard communication systems. The
single most important thing to keep in mind when using the Viterbi algorithm is that it
comes in varying degrees of strength based on certain parameters. If the parameters can
be varied, the stronger codes will tend to expand the data more.
The following web sites describe Viterbi coding further:
http://pw1.netcom.com/ chip.f/viterbi/tutorial.html (follow the links)
http://ece-classweb.ucsd.edu/Archive/winter02/ece260b/Labs/Project_2/easy_
viterbi.htm
www.cim.mcgill.ca/ latorres/Viterbi/va_main.html

Bandwidth Limited
Sometimes there is no extra bandwidth to work with, and we cannot use Viterbi coding
to expand the data at all. If we want to make some of the transmitted data redundant,
then we must throw away some bandwidth. A bit less of the original data is transmitted,
but the bandwidth is filled up with some redundant data. The overall bandwidth remains
unchanged.
The operator of the communication link must decide how much data bandwidth to
give up. Trellis coding and Viterbi decoding can be used. These codes expand the data