PHOTO CREDIT: Jeffrey Fiterman. Andrew Viterbi – 50 years after his famous Viterbi Algorithm was first published in IEEE Transactions On Information Theory (1967)
When Andrew Viterbi calls his grandkids, he never thinks about the fact that it’s his algorithm – embedded inside the hardened plastic and metal rectangle of his iPhone – that allows him to hear every “hello,” every “I love you, grandpa.”
There are three billion cell phone calls made within the U.S. every day. A total of 12.4 billion cellphone calls made every day on planet Earth.
All of them share one unique property: the voices are decoded, made clear, across great distances by the Viterbi Algorithm.
The Viterbi Algorithm has been used in space communications, voice recognition, data recording, search, DNA sequencing and even HBO’s satellite beaming of “The Sopranos” and “Westworld.”
Fifty years ago, Viterbi, Ph.D. ’62, was looking for a better way to explain complex convolutional codes to his students.
“I was obsessed with this problem for several months,” recounted Viterbi. “It dominated my thoughts in daytime and sometimes even at night. When the right argument came together in my head while I was watching my little children, I was reasonably sure I had solved it, but I did not have pen and paper handy at the moment, so I had to wait until I returned home to write it up and become convinced that I had indeed succeeded.”
What Viterbi found was the quickest, easiest way to decipher a message sent in a noisy world. Consider a simple phone call: Magic Johnson in Los Angeles calls Phil Jackson in New York City to suggest a trade. Magic’s voice – already compressed and translated into digital 1s and 0s – is encoded with redundant bits of 1s and 0s for the journey ahead. The reason? Noise. The signal that represents Magic’s voice travels through the air, fighting the noise of wind, rain, radios, televisions, and even cosmic radiation from the Big Bang. When the encoded signal reaches Phil’s cellphone, some of those original 1s and 0s may have been corrupted. However, the Viterbi Algorithm inside Phil’s phone springs into action, deciding on the probability that an incoming bit is actually a 1 or 0 based on the signal’s voltage. Once decoded, Magic’s voice is converted back to an analog signal, broadcast by a tiny speaker in Phil’s cellphone.
All of this happens in about 10 milliseconds.
In many ways, Viterbi is the intellectual heir to Andrei Markov, the Russian mathematician who denounced Tsar Nicholas II and birthed the mathematical models upon which most of the modern world rests. Every time you Google “best Thai restaurant” or “Tom Brady Deflategate,” the world’s information is being organized as one enormous Markov Chain. Or whenever your phone predicts the word you’re about to type next? That’s a Markov chain.
What if the previous flip of a coin could inform the outcome of the next? Or if you predict tomorrow’s weather based on today’s? Each day creates a new “state” that will determine the probability of the one to follow. The Viterbi Algorithm works similarly to this, predicting the original bits – ones and zeros – based on the incoming received signals.
Said Viterbi: “It’s the process of finding the best footpath through a forest where at every tree you have two choices of where to go next, only one of which is correct. You make the decision after looking at a number of trees ahead.”
On its golden anniversary, the Viterbi Algorithm is still finding new and startling applications. For Professor Shri Narayanan, the Niki and C. L. Max Nikias Chair in Engineering: “The Viterbi Algorithm has transformed speech and language processing. Our ability to decode the message conveyed in human speech and language communication signals has become a fuel for the AI resurgence – not just in creating novel human machine interfaces, but analytics that are helping us understand and support human health and well being.”
“Dr. Viterbi is not only a person of outstanding character,” said Professor Alan Willner, the Steven and Kathryn Sample Chair in Engineering, “he also fundamentally changed the way people solved problems to efficiently find a solution. Indeed, from cellular communications to image processing to DNA sequencing, it inspired a new way of thinking.”
Published on March 16th, 2017
Last updated on June 30th, 2017
