Logo: University of Southern California

Teaching the Viterbi Algorithm

March 27, 2007 — The fifth iteration of the USC Viterbi School’s annual Viterbi Lecture began on a somewhat lighter note than the previous four.

“This talk is not to be taken seriously,” intoned Robert McEliece, world-renowned information theorist and the Allen Puckett

Andrew Viterbi, left, for whom the lecture is named, shakes hands with guest speaker Robert McEliece of the California Institute of Technology.
Professor of Electrical Engineering at Caltech.  He was speaking to an audience of alumni, students, professors and more than a few other world-renowned information theorists.  And while the lecture, sponsored by the USC Ming Hsieh Department of Electrical Engineering, frequently triggered gales of laughter that swept across USC’s Gerontology Auditorium, McEliece was quite serious when he quickly added to his deadpan opening: 

“My job as a professor is to communicate to the students whatever I know.”

Instead of exploring the arcane mathematics relating to reliable storage or faster transmission of information, or other matters from the frontiers of information and communications science, the title of McEliece’s talk was “Learning to Teach the Viterbi Algorithm.”

It was clear that he had struck a chord that resonated with his audience, for at the reception preceding the lecture, many were talking about learning the Viterbi Algorithm, teaching it, or both. The fact that so many engineering students today must learn the algorithm and so many professors must teach it is testimony to how important and enduring Andrew Viterbi’s algorithm has become.

An algorithm is a precise set or rules or systematic steps used to solve a problem.  The Viterbi Algorithm, a mathematical system for encoding digital messages, seems daunting to most newcomers when they first look at it.  But once someone grasps the

L-R: Andrew Viterbi, Robert McElece, EE Systems Chair Sandy Sawchuk and EE Electrophysics Chair Dan Dapkus.
concept, it looks obvious, even trivial, and the algorithm becomes a powerful tool for solving a wide range of problems.  It is used today in such applications as cell phones, DNA analysis and speech recognition.

McEliece set the stage with a humorous limerick from  the book Shift Register Sequences written by one of the other world-renowned information theorists present, the Viterbi School’s own Solomon Golomb, university professor of electrical engineering and holder of the Viterbi Chair in Communications:

A message of content and clarity
Has gotten to be quite a rarity
To avoid the terror
Of serious error
Use bits of appropriate parity

McEliece punctuated his talk with diagrams and clever flash animations that showed how the algorithm worked.

Next, McEliece used a physical model of a Viterbi Algorithm trellis that employed yarn of varying lengths and colors.

The highlight of the lecture, however, was a highly entertaining 20-minute movie,The Trellis, that Edwin Soedarmadji, one of

In this scene from McEliece's video, Tiffany Hope, Tanya Mounsey and Cassandra Jean use the Viterbi Algorithm to discover Tanya’s secret admirer.
McEliece’s graduate students, had made.  The movie was about three female students, one of whom had received a series of mysterious gifts, and it followed the three as they successfully used the Viterbi Algorithm to determine the identity of the secret admirer. 

Near the end, the movie included a cameo appearance by Andrew Viterbi himself, which evoked “oohs” and “ahhs” from the audience and a satisfying conclusion to the evening.