Viterbi Receives 2016 Draper Prize
Written by Harry Fairhead
Monday, 11 January 2016

Unless you are into coding theory you may never have heard of Andrew Viterbi, but it is 100% certain that you have made use of his decoding algorithm.

I have a confession to make. When I was studying coding theory, the Viterbi algorithm was introduced and we spent a long time studying and even implementing it. However for reasons I cannot explain I assumed that this was an old algorithm known for a long time and refreshed because of the electronics age.

I couldn't have been more wrong.

Andrew JamesViterbi with wife Ema

The Viterbi Algorithm was invented in 1967 by Andrew James Viterbi. Born in Bergamo Italy, he moved to the US in 1938 and changed his original name, Andrea to Andrew. Viterbi taught at UCLA and USCD and is currently Professor of Electrical Engineering at the  University of Southern California's Viterbi School of Engineering, which was named in recognition of his \$52 million gift.

How could a professor manage to gift so much money?

The simple answer is that, along with Dr Irwin Jacobs, he founded Qualcomm - yes the company that makes ARM chips among other things. Originally Qualcomm started out creating communications devices such as mobile phones and modems.

There are many innovations that Viterbi is responsible for, including - CDMA used by mobiles phones everywhere - but the one he is best known for is the Viterbi algorithm.

This is a maximum likelihood decoder for convolutional or trellis codes. Convolutional codes were a huge breakthrough and they are responsible for making possible higher speed acoustic modems, ADSL, satellite communication and broadcasting, mobile phones, and even storage devices such as disk drives. These error correcting codes can be used to send data over low power and noisy channels with one-thousandth or better than the error rate of a single coded signal.

The Viterbi Algorithm is a decoder for convolutional codes and it is an application of dynamic programming. More generally, the Viterbi Algorithm is the maximum likelihood estimator of the states of a hidden Markov chain.

At first the algorithm was thought to be too difficult to be practical, but today there are software and hardware implementations. If you are unlucky you might see a "Viterbi Decoder Error" from a satellite receiver if the signal is very noisy. Arguably the algorithm isn't well enough known in software circles because it is often regarded as something to do with hardware. There are probably more applications for it just waiting to be thought of. Amazingly the algorithm wasn't patented on the advice of a lawyer. How times have changed!

Viterbi has received many prizes for his work - notably the National Medal of Science and the IEEE Medal of Honor. The latest, the Charles Stark Draper prize, comes with an award of \$500,000.

The citation states;

"Andrew J. Viterbi developed the Viterbi algorithm as a method for enhancing error-correcting code used in telecommunication. His publication of the algorithm in the IEEE Transactions on Information Theory in 1967 helped to usher in the age of cell phones by focusing on only the most likely computing paths for telecommunication signals, ultimately making it easier to eliminate static in transmissions. The Viterbi algorithm has had the greatest impact in digital cellular phones—whether GSM, CDMA, TDMA, 3G, or 4G LTE, they all employ at least one Viterbi algorithm for channel decoding—but soon after its discovery, it was put to use in other applications such as cable, DSL modems, and Ethernet. The Viterbi algorithm has also been instrumental in interplanetary communication signals, allowing for greater signal strength in deep space missions such as Mars Pathfinder, Mars Exploration Rover and the Cassini probe to Saturn.”

The Draper Prize will be presented at a gala dinner event in Washington, D.C., on February 16, 2016.

Telecommunications Pioneer Andrew J. Viterbi to Receive the 2016 Charles Stark Draper Prize for Engineering

Oral-History:Andrew Viterbi

#### Related Articles

How Error Correcting Codes Work

Claude Shannon

Coding Theory

Network Coding Speeds Up Wireless by 1000%

Information Theory

 Vint Cerf Awarded IEEE Medal of Honor03/02/2023Considered the highest honor in the field of Electrical Engineering, the IEEE Medal of Honor was inaugurated in 1917 and is awarded annually to a single recipient for exceptional contributions or [ ... ] + Full Story Bing+GPT: This Is Not A Search Engine08/02/2023I have been waiting for the day that AI could take over search and now it seems to be here. The real question, however, is whether or not Bing+GPT is actually a search engine? The answer seems to be a [ ... ] + Full Story More News