USC News

Menu Search
Science/Technology

Andrew Viterbi: He’s got algorithm

There wasn’t much to celebrate on the morning of Monday, Sept. 29, 2008: Congress was about to reject the first incarnation of a $700 billion bank bailout engineered by the Treasury and the Federal Reserve; the Dow Jones index was plunging, on its way to closing 777 points down; and the stick of fear was stuck firmly between the spokes of credit markets around the world.

Nonetheless, at the White House, USC trustee Andrew J. Viterbi PhD ’62 was the surprised recipient of a presidential high-five.

Appearances to the contrary, this was not a moment of inappropriate levity. It may have been the most appropriate signal then-President George W. Bush sent all day. For it was a badly needed reminder of what really matters.

Viterbi was at the White House to receive this country’s highest honor in science and technology: the National Medal of Science. Holder of the USC Presidential Chair in engineering, he becomes the third USC scholar in three years to receive a national medal, after USC Thornton School of Music Distinguished Professor Morten Lauridsen (National Medal of Arts) and University Professor Kevin Starr (National Humanities Medal).

It is a rare and possibly unprecedented triple for an American university.

While Starr’s award recognized his towering status among California historians, and Lauridsen’s medal celebrated his mastery in choral composition, Viterbi’s honor carried special importance on a day of financial panic.

Qualcomm, the company he co-founded, is worth nearly 70 times its initial public offering price in 1991. The company has created wealth for thousands of employees and shareholders – real wealth, not funny-money, debt-bubble riches.

More importantly, Qualcomm’s core technology for mobile phone communications has bettered the lives of billions. That technology relies on a method Viterbi developed for separating information from background noise. All four international standards for third-generation digital cellular communications use the Viterbi Algorithm, as do most digital satellite communication systems.

And Viterbi himself personifies America’s traditional strength. The son of immigrants forced out of their home country, he found educational and financial opportunities in a new land and made the most of them.

The year 2008 was a very good one for Viterbi. In addition to receiving the National Medal of Science, he was one of four finalists for the Millennium Technology Prize, the world’s largest technology award, presented every second year by the Technology Academy Finland for “a technological innovation that significantly improves the quality of human life, today and in the future.”

“Few people in any field can say that they have truly enhanced the world in which we live,” said USC President Steven B. Sample at the time the National Medal awards were announced.

“Andrew Viterbi is one of the few, one of the elite, whose intellect and imagination have helped advance human understanding. This is a tremendous honor for Andy and a well-deserved recognition of his historic accomplishments.”

Andrew Viterbi has been a Trojan in different times and ways throughout his life. He was a doctoral student here. Now, in addition to serving as a university trustee, he sits on the board of councilors for the USC Viterbi School of Engineering, which was named in his honor in 2004. He holds a faculty appointment in the school, and early on he helped attract several illustrious researchers to USC.

Viterbi’s association with Troy began in 1957. At the time, USC was the only institution that would let him pursue a Ph.D. and keep his job in the communications research group at Pasadena’s Jet Propulsion Laboratory (JPL). Soon to be married to Erna Finci, and with visions of growing a family, he could not afford the luxury of full-time graduate study.

It was a wise decision on both sides. Viterbi formed the first link between JPL and USC, starting a fortuitous chain of events. Based partly on Viterbi’s recommendation, the late Zohrab Kaprielian, then chairman of the electrical engineering department, invited Solomon Golomb, an applied mathematician who was one of JPL’s brightest stars, to join the USC faculty in 1963.

Golomb’s recruitment soon attracted JPL’s Lloyd Welch, William (Bill) Lindsey and other top communications engineers, including Rand Corporation’s Irving Reed. These scholars became the nucleus of an upwardly bound engineering school at USC that now ranks among the top 10 in the nation.

Viterbi himself had been one of JPL’s best young scientists. He could have enjoyed a long and brilliant career in the nascent space program, but he had wanted to be a professor since his childhood days in Boston, when he gazed across the river at Massachusetts Institute of Technology. The only child in an Italian Jewish family forced to leave its native country by the so-called racial laws that targeted Jews and other minorities, he sailed with his parents from Europe just two weeks before the start of World War II, thanks to a tip from someone close to the German diplomatic corps.

Later, in one of those breakdowns in communication that Viterbi’s work has made archaic, Jewish families around Europe began to disappear, unable to save themselves or to warn others with a simple phone call.

Safe in Boston, the child refugee struggled with English in kindergarten. The Viterbi family tried to adjust to a new world and to a double prejudice against Jews and Italians. Achille Viterbi, Andrew’s father, had a limited medical practice. Private schools and expensive tutors were out of the question. But the teenage Andrew excelled in the sciences, and after graduating fourth in his class at Boston Latin High School, he won a scholarship that would finally let him cross the river.

Viterbi earned bachelor’s and master’s degrees in electrical engineering at MIT. He then took a leap that, in hindsight, launched his career. In June 1957, he moved his parents across the country and took a job – his first out of college – at JPL.

Within three months, the place was in ferment from the Soviet Union’s launch of Sputnik I, the first man-made object to orbit the Earth. Edward Teller, father of the hydrogen bomb, declared that the United States had lost a battle more important and greater than Pearl Harbor. Putting up an American satellite became a moral imperative, with JPL the key battleground.

Viterbi soon became known for combining excellent mathematical skills with a rare nose for crucial problems.

“If Andy was working on a particular problem, you could bet that it was of practical importance,” says Lindsey, now a professor of electrical engineering at USC. “He always worked on problems that interested more than just a few communication scientists. It is my recollection that most of the papers published by Andy led to contributions of engineering significance.”

Viterbi simply says: “The most interesting problems come out of the real world.”

He quickly built a reputation as a hard worker. Lindsey remembers struggling with Viterbi on a particularly hard problem one Friday. The following Monday, Viterbi walked in with a solution. He had figured out the problem at the beach as he and Erna watched their two small children, Audrey and Alan, playing in the sand.

Seven months after Viterbi’s arrival, the scientists at JPL had their answer to Sputnik. Officially it was called Explorer I. Inside JPL it had a different name – Deal – a reference to the loser’s reaction in a card game when the winner wants to cash in his chips and go home.

“We were in the position of wanting another deal of the cards,” Golomb says.

Deal turned up a flush for JPL. The January 31, 1958, launch went flawlessly. Photographers from Life swarmed the control room. Golomb and Viterbi wound up in the magazine.

The satellite had been the work of a small army of engineers and designers whose contributions had far-reaching impacts. By making sure that the satellite and mission control could communicate reliably, Viterbi’s small team had solved much more than the problem at hand. It had laid a big part of the foundation for modern wireless communication.

Welch, who is now emeritus professor of engineering at USC, says: “Up until that time, most communications systems were analog. We were working on digital communications. I think that we advanced the theory quite a bit.”

Viterbi had not forgotten his childhood dream of entering academia. In 1962, he completed his Ph.D. in digital communications at USC, and he became a professor at UCLA the following year.

Ironically, it was the move away from applied research and into academia that led to the most applicable of his discoveries. In the mid-’60s, after struggling to teach some hard concepts in message-coding theory, Viterbi decided to look for an approach that his students would understand. The result was the Viterbi Algorithm.

The algorithm relies on complex probability theory and dynamic programming, and its power was not immediately understood when Viterbi published his seminal paper in 1967. In essence, a Viterbi decoder seeks to retrieve the original voice or data message from a coded digital stream (coding is the addition of redundant bits to protect messages against errors due to noise and interference).

Most previous decoders relied on a “hard decision” method: As each bit came in, the decoder had to decide on the spot if the bit was a zero or a one. Frequently, the message was so muddled that the decision was no more than a guess.

The Viterbi Algorithm looks at all possibilities, or paths, for a digital message. It labels each bit with the probability that the bit is a zero or a one. This way, the algorithm suspends judgment on any one bit until more bits can be studied. Then it picks out a path by working backwards in time through the tree of possibilities and finding the most likely route.

The beauty of the algorithm is its ability to rule out many paths very quickly. There are 1,024 possible paths for a message just 10 bits long. For a real-world digital message of millions of bits, analyzing all possible paths in their entirety is next to impossible.

Within a couple of years, Jerry Heller at JPL and Dave Forney at Motorola published papers demonstrating the power of the Viterbi Algorithm. The applications were so obvious that Viterbi formed a company, Linkabit, to sell Viterbi decoders and consulting services. Linkabit’s co-founder was a University of California, San Diego, engineering professor named Irwin Jacobs. (A third partner, UCLA professor Leonard Kleinrock, was initially part of the group.)

At first the company won military contracts for digital communications. It was becoming clear that digital was a far better anti-jamming technology than analog. In the early 1980s, Linkabit joined a larger company and ventured into commercial satellites, descramblers and other business and consumer applications.

Then in 1985, the parent company began to fall apart – luckily for Viterbi. He and Jacobs quit within weeks of each other and regrouped three months later to form Qualcomm. The legendary wireless chipset company was launched with seven employees over a dry cleaner’s shop in San Diego.

Viterbi confesses to not quite knowing at first what Qualcomm was going to sell. Its first major venture was OmniTRACS, a two-way satellite communication system for trucking fleets. It was ingenious, profitable and the first commercial application of spread spectrum technology. The military had been using spread spectrum for years to prevent jamming. In its most basic form, it involved “spreading” the signal frequency over a wide band.

The trucking market was limited. But Viterbi had proposed applying spread spectrum to cellular phones as early as 1982. By the late ’80s, one of Qualcomm’s top researchers, Klein Gilhousen, along with Viterbi, Jacobs and others, perfected a spread spectrum method they called CDMA (Code Division Multiple Access).

Technically, CDMA was vastly superior to anything on the market. That was just what the cell phone industry did not want to hear. Manufacturers and phone companies were already invested in a different standard.

“Industry likes to take incremental steps rather than bold new initiatives,” Viterbi says. “When we went to them with a CDMA approach, they pretty much all sent us away. Pac Tel was the only one that really listened.”

That changed after a demonstration of CDMA in 1991, when Qualcomm sent 100 mobile users driving around Mission Bay in San Diego and invited cell phone executives to test the system – “at the end of which they agreed to standardize it,” Viterbi recalls.

Qualcomm’s troubles were not quite over, however. Once it became clear that CDMA was the hot new thing, Swedish cell phone maker Ericsson filed suit, claiming that it had patents that could block adoption of the standard.

Unbeknownst to Ericsson, Viterbi and Qualcomm had a secret weapon from deep in their past: Solomon Golomb of USC. Aside from knowing everything about coding and cell phone standards, Golomb was fluent in Swedish.

Golomb read memos from Ericsson engineers that directly contradicted the company’s claims, and testified effectively as an expert witness for Qualcomm. Ultimately, the conflict between Qualcomm and Ericsson was settled in a manner that led to a collaboration to further promote CDMA.

The links between Qualcomm and USC extend further. Under then-dean of engineering Leonard (Len) Silverman, the school signed up Qualcomm as the first customer for what has become one of the best and biggest distance learning programs in the country, USC’s Distance Education Network. The very first long-distance learning students were Qualcomm’s engineers.

“USC engineering and I grew up together,” Viterbi likes to say. “Zohrab [Kaprielian] created it. I like to say that Len grew the distance learning nationwide just to service my company,” he adds, laughing, “but we were his first customers. And Max [Nikias]’s boundless energy and great vision have propelled us into the top 10.”

Now USC’s executive vice president and provost, C. L. Max Nikias was dean of engineering in 2004, when Andrew and Erna Viterbi pledged $52 million to the school’s endowment. It was the catalyst for a $300 million fundraising campaign that passed its goal in 2008.

“We now have a proud legacy to honor, uphold and advance; the responsibility humbles us,” Nikias said when the gift was made. Five years later, Viterbi says: “The achievements of the faculty and the student body’s success measures, including the quality of the entering class, have gone up. I’m very pleased with it all.

“It’s been a 50-year process, starting with Zohrab Kaprielian. It was one little engineering building back then, and now it’s a campus with really very first-rate facilities across the board.”

The USC Viterbi School placed eighth this year in the rankings of U.S. News & World Report. Pointing to several big strides, including a sharp increase in undergraduate student retention and dozens of new faculty appointments, Viterbi says, “We deserve our standing, and possibly we should be even higher.”

He also praises current dean Yannis C. Yortsos for his new “Engineering+” curriculum, which will prepare USC Viterbi graduates to tackle problems that bridge engineering and healthcare, energy research and even the social sciences.

“More and more, engineers have to recognize that it’s more than just the equation and the design feature,” he says. “They have to be responsive to the needs of society.”

The school’s namesake is the ultimate Engineer+, says Yortsos: “He is a great role model for academic excellence, entrepreneurship and philanthropy, and a powerful inspiration for faculty and students at the USC Viterbi School.”

Viterbi adds that despite his links to several other universities and research centers, he and Erna feel that USC stands alone.

“There’s a certain warmth in one’s feelings for fellow Trojans that goes beyond the rah-rah feeling common at most universities,” he says.

At a lunch celebrating Viterbi’s gift, Golomb toasted his old friend: “It is a wonderful legacy for future generations of engineering students at USC to go through a school named for one of the great pioneers in the history of engineering, and who demonstrated that one and the same person could be a brilliant researcher, a successful entrepreneur, a generous benefactor and an upholder of the highest standards of ethical conduct and integrity – and he’s also a real nice guy.”

Four years later, the president of the United States agreed.

 

More stories about: ,

Andrew Viterbi: He’s got algorithm

Top stories on USC News