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. 

viterbi2

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.

 

uscviterbi

 

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.

viterbi

More Information

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

 

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on, Twitter, FacebookGoogle+ or Linkedin

 

Banner


Facebook Open Sources Natural Language Processing Model
26/09/2019

Facebook has made a new natural language processing model called RoBERTA available as open source. The model is an optimized version of Google's BERT model.



CodeSearchNet Challenge To Improve Semantic Code Search
27/09/2019

As developers we are only too aware of the difficulty of finding relevant code using a natural language query. Now GitHub has released a large dataset of code and natural language comment  with t [ ... ]


More News

 

graphics

 



 

Comments




or email your comment to: comments@i-programmer.info

Last Updated ( Monday, 11 January 2016 )