https://viterbischool.usc.edu/news/2017/03/viterbi-algorithm-50/ Image Image * Students * Alumni * Parents * Corporate * Giving * Faculty * Search icon About Academics Admission Research Innovation Image About Academics Admission Research Innovation Image Image The Viterbi Algorithm at 50 Adam Smith | March 16, 2017 In a noisy world, it allows you to be heard. [mainimage_andrew_viterbi-2] 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 Share This Story Related Stories A view of the computer center located on the East half of the 12th floor of ISI's South tower.The Early ISI Years: A Firsthand Account from the Hardware Team 27% of the online global population is now using voice search on their mobile devices according to Google but the technology needs to become more trusted. Photo / stockStopping Deepfake Voices [tracking1200-300x150]Is Your Mobile Provider Tracking Your Location? This New Technology Could Stop It. Archimedes Plaza at the USC Viterbi School of Engineering (Photo credit/Noe Montes)34 new hires, including the new biomedical engineering chair, join for fall and spring semesters [emnlp1-300x150]USC Researchers Present 30 Papers at EMNLP 2021 (Left to Right) USC Viterbi Dean Yannis Yortsos, Leonard Silverman, Dr. Allen Ginsburg, Charlotte Ginsburg, Sharon Walker and Scott Willoughby (Photo/Steve Cohn) Celebrating Excellence, Innovation and Longevity USC Viterbi School of Engineering * University of Southern California * Viterbi School of Engineering Information For * Students * Corporate * Giving * Faculty Recent USC Viterbi News * Wide Awake and Dreaming: USC Viterbi's 2023 Master's Commencement Ceremonies * "At Heart, We're Problem Solvers:" USC Viterbi Undergraduate Commencement 2023 * The BME Grad Championing Gender-Affirming Healthcare * "Attention is All You Need": New Ph.D.s Urged to Attend to "Challenges of Earth's Eight Billion People." Read More News USC Viterbi School of Engineering USC Map Visit UsContact Us (c) USC ViterbiPrivacy Notice | Smoke-Free Policy | Notice of Non-discrimination ABOUT THE SCHOOL --------------------------------------------------------------------- * 115 Year Celebration * About Andrew Viterbi * Awards * Diversity Equity & Inclusion * Facts and Numbers * Faculty Directory * Ginsburg Hall * History * Leadership * USC Michelson Center FROM THE DEAN --------------------------------------------------------------------- * Dean's Message * Dean's Report * Initiatives and Priorities * Engineering + * Strategic Plan NEWS | MEDIA | EVENTS --------------------------------------------------------------------- * Events * Keynote Lecture Series * Media Contact & Press Releases * Media Coverage * News * Newsletter * Public Image Archive * Publications * Social Media * Video * Viterbi News Network EXPERIENCE --------------------------------------------------------------------- * Contact Us * Visiting DEPARTMENTS AND ACADEMIC PROGRAMS --------------------------------------------------------------------- * Aerospace and Mechanical Engineering * Astronautical Engineering * Alfred E. Mann Department of Biomedical Engineering * Mork Family Department of Chemical Engineering and Materials Science * Sonny Astani Department of Civil and Environmental Engineering * Thomas Lord Department of Computer Science * Ming Hsieh Department of Electrical and Computer Engineering * Daniel J. Epstein Department of Industrial and Systems Engineering * Engineering in Society Program * Information Technology Program SPECIALIZED GRADUATE PROGRAMS --------------------------------------------------------------------- * Financial Engineering Program * Green Technologies Program * Data Science Program * Progressive Degree Program * Systems Architecting and Engineering Program EXECUTIVE AND CONTINUING EDUCATION --------------------------------------------------------------------- * Aviation Safety and Security Program * Corporate and Professional Programs ONLINE ACCESS --------------------------------------------------------------------- * Graduate Programs - DEN@Viterbi RESOURCES AND INITIATIVES --------------------------------------------------------------------- * Academic Integrity * Accreditation * Awards * Awards Office * Center for Engineering Diversity * Division of Engineering Education * Globalization * Faculty Directory * iPodia * K-12 Outreach * USC Experts Directory * Women in Science and Engineering FIRST YEAR APPLICANTS [Mega-Menu-] MASTER'S APPLICANTS [Mega-Menu-] PHD APPLICANTS [Mega-Menu-] TRANSFER APPLICANTS [Mega-Menu-] RESEARCH ENVIRONMENT --------------------------------------------------------------------- * Search Faculty Research Areas * Departments, Research Institutes and Centers * Research Infrastructure * Research Initiatives * Research Vision * Student Research * Summer Undergraduate Research Experience TECHNOLOGY INNOVATION AND ENTREPRENEURSHIP --------------------------------------------------------------------- * AMI - Alfred E. Mann Institute * Coulter Translational Research Partnership * NSF I-Corps Hub: West Region * Office of Technology Innovation and Entrepreneurship * USC Stevens Center for Innovation ABOUT THE SCHOOL --------------------------------------------------------------------- * 115 Year Celebration * About Andrew Viterbi * Awards * Diversity Equity & Inclusion * Facts and Numbers * Faculty Directory * Ginsburg Hall * History * Leadership * USC Michelson Center FROM THE DEAN --------------------------------------------------------------------- * Dean's Message * Dean's Report * Initiatives and Priorities * Engineering + * Strategic Plan NEWS | MEDIA | EVENTS --------------------------------------------------------------------- * Events * Keynote Lecture Series * Media Contact & Press Releases * Media Coverage * News * Newsletter * Online Events Series * Public Image Archive * Publications * Social Media * USC Viterbi COVID-19 Response * Video * Viterbi News Network EXPERIENCE --------------------------------------------------------------------- * Contact Us * Visiting DEPARTMENTS AND ACADEMIC PROGRAMS --------------------------------------------------------------------- * Aerospace and Mechanical Engineering * Astronautical Engineering * Alfred E. Mann Department of Biomedical Engineering * Mork Family Department of Chemical Engineering and Materials Science * Sonny Astani Department of Civil and Environmental Engineering * Thomas Lord Department of Computer Science * Ming Hsieh Department of Electrical and Computer Engineering * Daniel J. Epstein Department of Industrial and Systems Engineering * Engineering in Society Program * Information Technology Program SPECIALIZED GRADUATE PROGRAMS --------------------------------------------------------------------- * Financial Engineering Program * Green Technologies Program * Data Science Program * Progressive Degree Program * Systems Architecting and Engineering Program EXECUTIVE AND CONTINUING EDUCATION --------------------------------------------------------------------- * Aviation Safety and Security Program * Corporate and Professional Programs ONLINE ACCESS --------------------------------------------------------------------- * Graduate Programs - DEN@Viterbi RESOURCES AND INITIATIVES --------------------------------------------------------------------- * Academic Integrity * Accreditation * Awards * Awards Office * Center for Engineering Diversity * Division of Engineering Education * Globalization * Faculty Directory * iPodia * K-12 Outreach * USC Experts Directory * Women in Science and Engineering FIRST YEAR APPLICANTS [Mega-Menu-] MASTER'S APPLICANTS [Mega-Menu-] PHD APPLICANTS [Mega-Menu-] TRANSFER APPLICANTS [Mega-Menu-] RESEARCH ENVIRONMENT --------------------------------------------------------------------- * Search Faculty Research Areas * Departments, Research Institutes and Centers * Research Infrastructure * Research Initiatives * Research Vision * Student Research * Summer Undergraduate Research Experience TECHNOLOGY INNOVATION AND ENTREPRENEURSHIP --------------------------------------------------------------------- * AMI - Alfred E. Mann Institute * Coulter Translational Research Partnership * NSF I-Corps Hub: West Region * Office of Technology Innovation and Entrepreneurship * USC Stevens Center for Innovation * About + About the School o 115 Year Celebration o About Andrew Viterbi o Awards o Diversity Equity Inclusion o Facts and Numbers o Faculty Directory o History o Ginsburg Hall o Leadership o USC Michelson Center + From the Dean o Dean's Message o Dean's Report o Initiatives and Priorities o Engineering + o Strategic Plan + News | Media | Events o Events o Keynote Lecture Series o Media Contact & Press Releases o Media Coverage o News o Newsletter o Publications o Social Media o Video + Experience o Contact Us o Visiting * Academics + Departments and Academic Programs o Aerospace and Mechanical Engineering o Astronautical Engineering o Biomedical Engineering o Mork Family Department of Chemical Engineering and Materials Science o Sonny Astani Department of Civil and Environmental Engineering o Thomas Lord Department of Computer Science o Ming Hsieh Department of Electrical and Computer Engineering o Engineering in Society Program o Daniel J. Epstein Department of Industrial and Systems Engineering o Information Technology Program + Specialized Graduate Programs o Financial Engineering Program o Green Technologies Program o Informatics Program o Progressive Degree Program o Systems Architecting and Engineering Program + Online Access o Graduate Programs - DEN@Viterbi + Executive and Continuing Education o Aviation Safety and Security Program o Corporate and Professional Programs + Resources and Initiatives o Academic Integrity o Accreditation o Awards o Awards Office o Center for Engineering Diversity o Division of Engineering Education o Globalization o Faculty Directory o iPodia o K-12 Outreach o USC Experts Directory o Women in Science and Engineering * Admission + First Year Applicants + Master's Applicants + PHD Applicants + Transfer Applicants * Research + Search Faculty Research Areas + Departments, Research Institutes and Centers + Research Infrastructure + Research Initiatives + Research Vision + Student Research + Summer Undergraduate Research Experience * Innovation + Alfred E. Mann Institute (AMI) + Competitions + Coulter Translational Research Partnership Program + Entrepreneurship + I-Corps Node + USC Stevens Center for Innovation + Viterbi Startup Garage + Viterbi Student Innovation Institute (VSI2) + Viterbi Venture Fund * Students * Alumni * Corporate * Giving * Faculty