Page 268 - Anatomy of a Robot

09_200256_CH09/Bergren 4/17/03 11:24 AM Page 253
COMMUNICATIONS 253
machine creates the output data. The state machine changes states depending on the
flow of input data bits. Each one and zero from the unexpanded data does two things:
Changes states The state machine changes state for each one and zero coming
in from the unexpanded data input.
Outputs data Each time the state machine receives an input bit and changes
state, it outputs some data. In general, more bits are output than are input, so the
Viterbi encoder expands the data.

Since more than just two states exist in the Viterbi state machine, each state change
excludes some states in favor of the two states that are the only possible results of the
change. If, for example, the state machine has four states, then a one or a zero can only
make the state machine change to one of two different states. The other two states are
prohibited changes. This is the key to how the Viterbi decoder corrects errors.

Viterbi Decoder It’s a great oversimplification, but here’s a brief explanation of how
the Viterbi decoder corrects errors. The Viterbi decoder knows a priori how the Viterbi
encoder functions. Since the decoder knows the behavior of the encoder, it can detect
suspicious data altered by the noise in the channel. The random changes caused by the
noise cannot fully mimic the activity of the encoder. Thus, the decoder can detect signs
of tampering.
The decoder accepts input bits coming directly out of the channel through the demod-
ulator. The decoder also has a state machine that changes states based on the received
data bits. As the expanded input data is received, the decoder state machine does two
things:

Changes state As expanded data bits are received from the demodulator, they
are decoded to determine the next state of the decoder state machine. The history
of the state changes is accumulated back a few cycles.
Outputs data As the decoder state machine changes states, it triggers an exam-
ination of the historical state change data. If the historical data all makes sense,
then the decoder outputs the unexpanded data that is stored in the historical data.
In general, the output has fewer bits than the input. This is how the Viterbi decoder
retrieves the original unexpanded data.

The decoder does not output any unexpanded data until it is satisfied it has combed
errors out of the input stream. It will save up data until this is the case. The decoder
looks back over the recent history of state changes to see if those changes make sense.
If the history looks suspicious, the Viterbi decoder considers the fact that one or more
of the received data bits may have been wrong. One by one, the decoder looks into
recent history, examines each recent input bit that was received, and considers what