| 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.
More InformationRelated ArticlesHow Error Correcting Codes Work Network Coding Speeds Up Wireless by 1000%
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, Facebook, Google+ or Linkedin.
Comments
or email your comment to: comments@i-programmer.info |
|||
| Last Updated ( Monday, 11 January 2016 ) |
