Now Reading
The Viterbi Algorithm at 50 – USC Viterbi

The Viterbi Algorithm at 50 – USC Viterbi

2023-05-11 00:14:13

PHOTO CREDIT: Jeffrey Fiterman. Andrew Viterbi – 50 years after his well-known Viterbi Algorithm was first revealed in IEEE Transactions On Data Idea (1967)

When Andrew Viterbi calls his grandkids, he by no means thinks about the truth that it’s his algorithm – embedded contained in the hardened plastic and steel rectangle of his iPhone – that enables him to listen to each “hi there,” each “I really like you, grandpa.”

There are three billion cellphone calls made inside the U.S. every single day. A complete of 12.4 billion cellphone calls made every single day on planet Earth.

All of them share one distinctive property: the voices are decoded, made clear, throughout nice distances by the Viterbi Algorithm.

The Viterbi Algorithm has been utilized in house communications, voice recognition, knowledge recording, search, DNA sequencing and even HBO’s satellite tv for pc beaming of “The Sopranos” and “Westworld.”

Fifty years in the past, Viterbi, Ph.D. ’62, was on the lookout for a greater solution to clarify advanced convolutional codes to his college students.

“I used to be obsessive about this downside for a number of months,” recounted Viterbi. “It dominated my ideas in daytime and generally even at evening. When the best argument got here collectively in my head whereas I used to be watching my little youngsters, I used to be fairly certain I had solved it, however I didn’t have pen and paper helpful in the intervening time, so I needed to wait till I returned residence to put in writing it up and turn into satisfied that I had certainly succeeded.”

What Viterbi discovered was the quickest, best solution to decipher a message despatched in a loud world. Think about a easy cellphone name: Magic Johnson in Los Angeles calls Phil Jackson in New York Metropolis to recommend a commerce. Magic’s voice – already compressed and translated into digital 1s and 0s – is encoded with redundant bits of 1s and 0s for the journey forward. The explanation? Noise. The sign that represents Magic’s voice travels by the air, combating the noise of wind, rain, radios, televisions, and even cosmic radiation from the Massive Bang. When the encoded sign reaches Phil’s cellphone, a few of these unique 1s and 0s could have been corrupted. Nonetheless, the Viterbi Algorithm inside Phil’s cellphone springs into motion, deciding on the chance that an incoming bit is definitely a 1 or 0 primarily based on the sign’s voltage. As soon as decoded, Magic’s voice is transformed again to an analog sign, broadcast by a tiny speaker in Phil’s cellphone.

All of this occurs in about 10 milliseconds.

In some ways, Viterbi is the mental inheritor to Andrei Markov, the Russian mathematician who denounced Tsar Nicholas II and birthed the mathematical fashions upon which a lot of the fashionable world rests. Each time you Google “finest Thai restaurant” or “Tom Brady Deflategate,” the world’s data is being organized as one huge Markov Chain. Or each time your cellphone predicts the phrase you’re about to kind subsequent? That’s a Markov chain.

What if the earlier flip of a coin may inform the end result of the subsequent? Or in the event you predict tomorrow’s climate primarily based on immediately’s? Every day creates a brand new “state” that can decide the chance of the one to comply with. The Viterbi Algorithm works equally to this, predicting the unique bits – ones and zeros – primarily based on the incoming acquired indicators.

Mentioned Viterbi: “It’s the method of discovering the perfect footpath by a forest the place at each tree you’ve got two selections of the place to go subsequent, solely one in every of which is right. You make the choice after quite a lot of timber forward.”

On its golden anniversary, the Viterbi Algorithm remains to be discovering new and startling functions. For Professor Shri Narayanan, the Niki and C. L. Max Nikias Chair in Engineering: “The Viterbi Algorithm has reworked speech and language processing. Our capability to decode the message conveyed in human speech and language communication indicators has turn into a gasoline for the AI resurgence – not simply in creating novel human machine interfaces, however analytics which might be serving to us perceive and help human well being and nicely being.”

“Dr. Viterbi is just not solely an individual of excellent character,” stated Professor Alan Willner, the Steven and Kathryn Pattern Chair in Engineering, “he additionally basically modified the best way folks solved issues to effectively discover a answer. Certainly, from mobile communications to picture processing to DNA sequencing, it impressed a brand new mind-set.”

See Also




Printed on March sixteenth, 2017

Final up to date on June thirtieth, 2017

Source Link

What's Your Reaction?
In Love
Not Sure
View Comments (0)

Leave a Reply

Your email address will not be published.

2022 Blinking Robots.
WordPress by Doejo

Scroll To Top