The Viterbi Algorithm

It isn't every day that a school is named after an algorithm. Okay, that's probably not exactly the case with the University of Southern California's Viterbi School of Engineering. But there is the Viterbi algorithm and there is the Viterbi School of Engineering. And, for that matter, there is the Viterbi Lecture series, which takes place at the Viterbi School of Engineering. So what came first -- the chicken or the Viterbi?

Not being one to normally josh about serious things such as algorithms and engineering schools, I can probably get by with a humor this time around. Why? Because Robert McEliece, a world-renowned information theorist and professor at Caltech, got away with a bit of levity of his own at the recent fifth annual Viterbi Lecture. When kicking off his lecture, McEliece turned to the following limrick penned by USC Professor Solomon Golomb and author of the book Shift Register Sequences:

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

Okay, the joke (such as it is) is that the Viterbi algorithm is an error-correction scheme for noisy digital communication links. It is widely used these days with cell phones, satellites, deep-space communications, 802.11 wireless LANs, speech recognition, keyword spotting, computational linguistics, and and the like. In a nutshell, Viterbi is an algorithm to compute the optimal (most likely) state sequence in a hidden Markov model given a sequence of observed outputs. I'll leave it at that, since there are lots of sources -- including this one -- that explain the algorithm in detail. I'd probably just confuse matters matters anyway.

Finally, there's even a Perl implementation on CPAN.

Posted by Jon Erickson at 09:45 AM  Permalink