The Viterbi Algorithm
Yielding Clear Communications
The Viterbi Algorithm — theoretical basis for such wide-ranging applications
as cell phones, DNA analysis and speech recognition — is essentially a fast way
of eliminating dead ends.
Imagine you’re a detective trying to determine the point of origin for a suspect
arriving at the Seattle airport. He is from abroad and has been there for no more
than an hour.
You know during this period that four domestic flights arrived from four cities
served by flights from 30 others. One way to determine the suspect’s origin would
be to go back to all 30 and make inquiries. The alternative: identify which of
the four closest cities he arrived from, then investigate only places with connections
to that one.
The algorithm Andrew J. Viterbi invented in 1966, and published the following
year, is much more subtle and flexible than this simple illustration. But the
basic situation and strategy are the same. For an algorithm is merely a precise
rule (or set of rules) specifying how to solve some problem. A user starts with
the result of a set of changes that happened in a series — not a random series,
but one governed by known, rigidly formulated rules.
The algorithm takes the result and backtracks, throwing away all the branches
that, by the rules, couldn’t have lead to the observed result.
When he created his system, Dr. Viterbi specifically focused on electronic signals
encoding messages. To transmit messages so they won’t be degraded or lost by noise,
additional “redundant” information is added at the transmitter, in a process called
error correction coding. The result coming into a receiver is a pulsing, miscellaneous
stream of bits, ones and zeros. The signals aren’t clear zeros and ones, but values
on a sliding scale that the receiver has to designate as zeros and ones, as best
it can.
Thanks to the Viterbi Algorithm, this sliding confusion of radio waves can yield
a clear, undamaged message. The key rests in a time series of incoming information,
with each set of bits tagged by its order of arrival.
The element sample — up to 15 time sequences deep in the latest, most sophisticated
versions — is probed for a message by working back in time. Instead of analyzing
all possible messages in this stack, the algorithm swiftly finds the most probable
one, throwing away more and more possibilities with each layer.
At the time Dr. Viterbi published his algorithm, computers weren’t up to the
task of even a relatively shallow decoding. With the growth in computing power,
the Viterbi Algorithm swiftly came of age as a powerful, useful tool for ensuring
static-free voice communications over satellite links, with cell phones its current
showcase “killer application.”
