2010 Medal of Honor Winner: Andrew J. Viterbi

Photo: Brad Swonetz

The ranks of first-rate inventors are chock-full of characters who are brash, egotistical, and temperamental. And for quite a few, even those adjectives are stretched to their euphemistic limits.

So meeting Andrew J. Viterbi can be something of a shock. He speaks softly, responds patiently. It’s not that he’s shy; it’s a soothing kind of quiet, the kind that makes a guest comfortable. He’s dressed nicely—in gray slacks and a dress shirt—but not formally; he rarely wears a tie. He’s mostly bald, with a round face and eyes that crinkle when he smiles, which is frequently. He looks like someone’s grandfather (which indeed he is; he has five grandchildren).

”Success comes to all kinds of personalities,” says Viterbi’s friend Carver Mead, the Caltech professor, integrated circuit pioneer, and oft-quoted tech visionary. ”But it sure is nice when it comes to people like Andrew, who aren’t just in it to beat their own chests.”

It’s not easy to reconcile the mild-mannered Viterbi with the tech titan who made fundamental contributions to Wi-Fi, 3G cellular and digital-satellite communications, speech recognition, and DNA analysis. Who cofounded Qualcomm. And, oh yeah, came up with one of the most important mathematical concepts of the 20th century: the Viterbi algorithm, a means of separating information from background noise. It’s that last one, the algorithm, that was singled out in the citation for the IEEE Medal of Honor, Viterbi’s most recent accolade.

Viterbi’s tale isn’t one of an aggressively ambitious engineer trying to shake up the world, make a fortune, or claw his way to the top of his profession. It’s the story of an unusually bright and hardworking professor who wanted to explain a difficult concept in clear and simple terms in order to better teach his students.

The son of Jewish-Italian immigrants, Viterbi did well in both math and English at the venerable Boston Latin School. His father, a doctor, encouraged him to be an engineer, remembering the impact electrical power had made when it first came to Bergamo, the Italian town where Andrew was born. Viterbi won a scholarship to MIT and graduated with bachelor’s and master’s degrees in electrical engineering in 1957. His father’s medical practice was struggling, and the family needed Viterbi’s financial support, although he wanted to go on to a Ph.D. and teach.

He had enjoyed working at Raytheon as a co-op student, but deplored the way engineers were treated. ”Engineers were not people trusted to make any decisions,” he recalls. He’d heard that things were different on the West Coast, where some engineers even got private offices. So he applied for and got a job at the Jet Propulsion Laboratory, in Pasadena, Calif. Signing on with a lab that was affiliated with a university seemed like the next best thing to the academic career he really wanted.

At JPL, he started off working on telemetry for guided missiles, helping develop a then-new device called the phase-lock loop, which tunes into a carrier signal in spite of surrounding noise. After the Soviet launch of Sputnik and the beginning of the space race, Viterbi’s efforts shifted to space communications systems, but the underlying focus on signals and noise didn’t change. Simultaneously he worked on his Ph.D. at the University of Southern California.

In the fall of 1963, doctorate in hand, Viterbi finally made it to academia, joining the University of California, Los Angeles. Teaching classes in communications and information theory, he couldn’t have been happier.

Then came the algorithm.

Photo: Brad Swonetz

The Viterbi algorithm looks for the most likely sequence of states and keeps track only of the most likely path leading up to a given state [shown in blue] rather than all possible paths. Click on the image for the full illustration view.

It was March 1966. Viterbi was struggling with yet another class of graduate students, who just couldn’t grasp a key set of concepts in information theory. The troublesome algorithms, known as sequential decoding of convolutional codes, extracted data from a signal corrupted with noise. Essentially, the algorithms decided if a bit was a 0 or a 1 by looking down a decision tree. When it became clear that the data had been corrupted, the software would go back one or more steps and try a different path.

The students didn’t get it. Viterbi decided that the reason the algorithms were so hard to understand was that the proof of the theorems was too complex. So he set out to find a simpler proof.

After several months of obsessing over the problem, it hit him: It wasn’t the proof that needed to be simplified; it was the algorithms themselves. Instead of going down a tree over and over again, Viterbi envisioned a trellis, in which the software considers the bits surrounding a particular bit in question to decide whether that bit is a 0 or a 1. The software assigns a probability of the accuracy of its decision to each bit based on the voltage of the received signal that conveys that bit. Based on the probabilities, the algorithm then decides whether that particular bit is a 0 or a 1. Unlike the earlier convolutional code algorithms, the software needs to keep track of only the paths leading up to a limited number of states, typically more than four but not more than 1000, a far more effective method than following each path until it dead-ends. Viterbi published his results in the IEEE Transactions on Information Theory in 1967, and his paper became a classic.

”After you see this approach, you wonder why nobody thought of it before,” says Robert G. Gallager, an MIT professor emeritus and an eminent scholar in communications theory. ”But that’s what the best inventions are. After you see them, they are obvious.”

The algorithm did what Viterbi wanted—it simplified the course material for his students. But he sensed it could do a lot more—for example, enabling the extraction of weaker signals from noisier environments. That in turn could mean lower-power transmitters, smaller antennas on the receiving end, or both. But to be useful, it would require both computer memory and processing power to calculate and track all the probabilities. Extracting the weakest signal from the greatest amount of noise would mean keeping track of about 1000 states at once; to do that, you’d need the processing power of a mainframe computer.

Viterbi and his colleagues did some further tinkering with the algorithm. They discovered that by keeping track of just 64 states, you could create a device that was four times as good as an uncoded transmission, or twice as good as coding systems in use at that time. That meant that the transmission power could be one-fourth the strength, or the receiving dish one-fourth the size, or the range twice as far, as similar uncoded systems. Within a few years, the falling price of electronic components made possible devices that tracked 256 states.

In 1968 Viterbi joined two engineers from his JPL days—Irwin Jacobs, then at the University of California, San Diego, and Leonard Kleinrock, then at UCLA—and started consulting on applications of his algorithm. They called their firm Linkabit.

The company worked on various defense and commercial satellite modems and terminals. It also built a satellite signal scrambler called Videocipher for the cable channel HBO; the technology continued to be used to scramble pay-TV signals until the end of 2008. In 1973, Viterbi left UCLA and joined Linkabit full time. Seven years later, M/A-Com acquired the company and eventually sold off its various pieces. Viterbi and Jacobs stuck around until 1985, when they decided to start all over with a new business they named Qualcomm. They weren’t exactly sure what this company would do, just that it would be something in commercial communications.

Then, recalls Viterbi, ”along came this interesting fellow, Allen Salmasi.” With backing from a rich uncle in Paris, the Iranian émigré had founded a company called OmniNet. Salmasi envisioned a mobile satellite network that would let trucking dispatchers track trucks in real time and send messages to the drivers. He hired Qualcomm to build it.

The time was right. A number of companies had launched satellite TV businesses, but the service wasn’t catching on, so they were eager to lease their transponders. There was just one problem: Those satellite downlinks were licensed for fixed reception, not mobile use. The only way around the rule was if the mobile application did not interfere with fixed services.

Qualcomm’s solution was to use spread-spectrum communications. The engineers figured that if they combined their signal with a broader signal that looked like noise, the fixed satellite networks would ignore it. They then used the Viterbi algorithm to help extract the original signal from the noise. The Federal Communications Commission gave Qualcomm an experimental license to try out the idea.

In 1988, Qualcomm was in the midst of testing the system with 600 trucks when Salmasi’s company started falling apart. Viterbi and his colleagues, rather than letting the effort fold, decided to acquire OmniNet in 1988. Within three years, the trucking system, called OmniTracs, was turning a profit. It’s still used around the world by long-haul truckers.

Following the launch of OmniTracs, the scrappy start-up took on the mobile phone industry. In an era when analog cellphones still ruled, the company introduced a digital spread-spectrum network (also based on the Viterbi algorithm, of course) to efficiently extract the right digital bits from a host of simultaneous transmissions in which everything looks like noise. (Today all 2G and 3G digital standards use the Viterbi algorithm.) Viterbi and his colleagues also figured out a way to have each handset and tower analyze the quality of its own signals as well as the other conversations being transmitted around it; the tower would then adjust power usage until the handset was transmitting just enough signal to work.

Qualcomm cofounder Jacobs says that it was a long uphill battle for the company to convince the world that its technology, code-division multiple access, or CDMA, was commercially viable, and even the usually patient Viterbi sometimes got frustrated. ”A couple of professors at Stanford were being quoted in the press saying that CDMA violated the laws of physics,” Jacobs says. ”[Viterbi] did get into a bit of an interchange with one of them.” For his part Viterbi recalls those years as intense but ”very exciting. Things were happening. Hardware was being built. Maybe we were whistling in the dark, but the technology worked.”

His daughter, Audrey, theorizes that this battle was perhaps ”the most exciting period of his career. My father is always up for a challenge; that’s what motivates him.” Eventually, Qualcomm’s CDMA won out. In 1993, the Telecommunications Industry Association, a trade group that represents about 600 telecom companies, incorporated it into its wireless cellular standard. Today a form of it is used in 3G cellular systems throughout the world.

Viterbi retired from Qualcomm in 2000, with hundreds of millions of dollars in stock. He now had the time and the resources to do just about anything. And what he really wanted, he decided, was to do more to help up-and-coming engineers.

These days, Viterbi’s helping to groom the next generation of tech entrepreneurs through his investment firm, the Viterbi Group, which consists of Viterbi, his daughter Audrey, and an assistant. Not surprisingly, he focuses on communications start-ups, many of which are adapting the fundamental algorithm he discovered to new purposes. He’s not trying to control his technology, he explains; it’s just the area he knows best. To date, the group has invested in 30 companies and currently has some US $10 million invested in 10 companies.

One of his earliest investments was in VoiceSignal Technologies, which used the Viterbi algorithm for voice recognition systems in cellphones, including the iPhone. Nuance Communications acquired VoiceSignal in 2007. He was also an early investor in Provigent, a company that produces systems for microwave point-to-point transmission; Flarion Technologies, a company with a 4G phone technology that was eventually acquired by Qualcomm; and TransChip, a camera-on-a-chip manufacturer purchased by Samsung. While Viterbi may be a money man for these companies, his technical advice and industry contacts are invaluable to the start-up teams. Rajiv Laroia, Flarion’s founder, says that when his company was still just a struggling New Jersey start-up, Viterbi’s stamp of approval conferred instant credibility. ”He is a god in the field of communications,” says Laroia.

Viterbi has also made generous donations to engineering education at USC (where the school of engineering now bears his name); MIT; the Technion–Israel Institute of Technology, in Haifa; Boston Latin School; and two private high schools.

”The future of this nation is scientific literacy,” Viterbi says. ”What else do we have to sell? We have innovation and we have a lot of bright kids.”

Maybe one of those bright kids will grow up, challenge the established way of doing things, and change the world of technology. Just like Andrew Viterbi.

This article originally appeared in print as "Andrew Viterbi’s Fabulous Formula."