Logo: University of Southern California

Viterbi Algorithm

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.”