Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Mobile

Andrew Viterbi and the Viterbi Algorithm



Andrew Viterbi was recently named as a finalist for the 2008 Millennium Technology Prize "for the invention of the Viterbi algorithm, the key building element in modern wireless and digital communications systems, touching the lives of people everywhere."

Viterbi was introduced to communication systems when the was hired by the California Institute of Technology's Jet Propulsion Laboratory (then a center for communications and satellite control systems, soon part of a new National Aeronautics and Space Administration). At the Jet Propulsion Laboratory (JPL), Viterbi specialized in communications technology on a team that designed the telemetry equipment for the first successful U.S. satellite, Explorer 1. The challenge was to develop methods for processing and transmitting information packets from space as accurately and quickly as possible. They confronted two challenges: the satellite's signal was very weak because of the long journey of the signal and a low power transmitter, and the frequency changes created by rapid orbits.

Viterbi continued his studies at the University of Southern California while working at JPL and completed his Ph.D. dissertation on the error-correcting codes. He continued in the academic world, at UCLA's School of Engineering and Applied Science, teaching digital communications and information theory. This time in the late 1960s led to his famous invention, the Viterbi algorithm, and was the period during which he wrote his most important papers on communication theory.

Leading Up to the Viterbi Algorithm

Teaching signal processing was difficult due to the complicated nature of the algorithms used, so Viterbi formulated a more simple way to explain the processing techniques. After realizing the importance of this algorithm, he submitted an article to the IEEE Transactions on Information Theory: Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. The paper was published in 1967 but the algorithm was considered not much more than elegant theoretical work until computing technology became powerful enough to handle the massive calculations needed to apply the work. Thus the Viterbi algorithm didn't find widespread application until the move to digital and wireless communications.

At that time nobody could imagine a general application for the algorithm, so Viterbi followed his lawyer's advice and did not patent it. Instead he founded a company, Linkabit Corporation, with Irwin Jacobs and Leonard Kleinrock, in 1968. The company was a small military contractor for developing satellite communication technology, but it expanded later to the civil sector when mobile satellite telecommunication became feasible.

As the size of the mobile telecommunication technology shrunk and the performance increased in big leaps, Viterbi was surfing the next telecomm wave with a new company, Qualcomm. He left Linkabit with his colleagues in 1985 and founded Qualcomm to produce the OmniTRACS satellite locating service used by long-haul trucking companies, and specialized integrated circuits for digital radio communications such as the Viterbi decoder. Today Qualcomm is better known as the mobile phone technology company that aggressively promoted Viterbi's code division multiple access (CDMA) technology. Its European competitor, GSM, became more popular, but the new 3G (UMTS) mobile communications networks in use today incorporate CDMA technology (also known as WCDMA). Whatever the system, the Viterbi algorithm is at work on every cellular phone in use today.

While working at Qualcomm, Dr. Viterbi continued lecturing at the University of California, San Diego. In 1994, he became a UCSD professor emeritus. He left Qualcomm, where he was vice chairman and chief technology officer, in 2000, and three years later founded his own venture capital company, the Viterbi Group LLC, which advises and invests in early stage companies, predominantly in wireless communications, network infrastructure and imaging.

In 2000 he was ranked 386th on the Forbes 400 list of the richest Americans, with an estimated worth of $640 million. In 2002 Boston Latin School, Viterbi's childhood school, built and equipped a new computer center with funds donated by Dr. Viterbi and in March 2004, the University of Southern California School of Engineering was renamed the Viterbi School of Engineering, in his honour, following his $52 million donation to the school.

When Dr Viterbi retired from Qualcomm in 2000 at the age of 65, he did not retire from active work; far from it. He served from 1997 until 2001 on the U.S. President's Information Technology Advisory Committee and, since 1983, has been active on the MIT Visiting Committee for Electrical Engineering and Computer Science.

He is a member of the USC School of Engineering Board of Councilors, a member of the board of the Burnham Institute and the Scripps Cancer Center in La Jolla, a trustee of the Mathematical Sciences Research Institute in Berkeley and a member of the University of California's President's Council for the National Laboratories.

The Viterbi Algorithm: Details

Viterbi's innovation is the Viterbi algorithm, the mathematical formula that enables clear and practically error-free radio communication over long distances, from moving low power transmitters and receivers.

Considering all possible error sources in radio transmission, it is a wonder that communication succeeds. Whether a radio transmitter is in a spacecraft, mobile phone, missile or truck, there are some basic transmission challenges. Firstly, tracking a moving transmitter can be tricky, because of a phenomenon called Doppler shift. When a transmitter is approaching, carrier frequency increases, just like the sound of the whistle from an approaching train is higher than from a standing train. When the transmitter is moving away, the frequency of the carrier frequency reduces -- again, just like the sound of the train's whistle is lower after passing the observer. If the movement is not constant, tracking the shift in the carrier signal frequency can be tricky, if not impossible.

The second problem is finding the signal from the noise if the signal is sent from far away (like from a spacecraft) or from a low power transmitter (like a cell phone). On any mobile phone network, thousands of phones are sharing the same wavelengths, making reliable data transfer between the individual phone and network very challenging.

The Viterbi algorithm was an elegant solution that solved both problems by redundancy and coding; it is essentially just a fast way of eliminating dead ends in the communication. The principle is simple, but the algorithm itself requires considerable computing power. Each bit in the digital information -- 0 or 1 -- has to be represented by four, eight, or more code symbols. So, 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 received signal is not a clear chain of zeros and ones but is code symbols from which the actual information bits can be reconstructed. Some individual bits can be dropped or distorted, because with the code symbols the missing bits can be guessed with high confidence. There are four states of "guess": very sure, moderately sure, sort of sure and barely sure. The decoder in the receiver evaluates the certainty by comparing the result with neighboring bits and makes the best possible guess. The result is a clear, practically-undamaged message. The key is in a time series of incoming information, with each set of bits tagged in order of arrival.

The algorithm makes it possible to spread a carrier frequency over a wide area of the electromagnetic spectrum. Thousands of low emitting power transmitters can operate in same band range at the same time in small areas without interfering with each other, because their carrier frequencies are coded with different patterns. This principle was first used in military communications and is now the basis of the code division multiple access (CDMA) and UMTS digital cellular communications.

At the time that Dr. Viterbi published his algorithm, computers were not powerful enough to make all calculations required for decoding in real time, but with the growth in computing power, the Viterbi algorithm revolutionized the telecommunications environment by providing a useful tool for error-free communications.

Many methods for error coding and frequency shift elimination were proposed before Viterbi's work. One of the most powerful algebraic error correction codes was invented by Irving Reed and Gus Solomon from USC in 1960. The code was named after them as "RS codes". It was mathematically elegant, but extremely complex and too tricky for everyday use. In the 1990s, RS codes became the standard error correction method on compact discs, fax machines, and numerous other uses.

After Dr. Viterbi proposed his famous algorithm Andreas Polydoros made significant contributions to the decoding of cell phone-like signals using Viterbi's methods. His contribution offered a better way to trace the frequencies of incoming signals and to synchronize them, and he was also able to identify and locate signal groups in marginal reception conditions.

Conclusion

Today the Viterbi algorithm is used in billions of cell phones, magnetic recording, most satellite TV receivers, a variety of cable TV systems, voice recognition, and even DNA sequence analysis. The Transfer Control Protocol and the Internet Protocol (TCP/IP), Wi-Fi and Bluetooth are another uses of the Viterbi algorithm and methods based on it. In short, Viterbi's algorithm is enabling today's exploding wireless world.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.