“For the invention of the Viterbi algorithm, the key building element in modern wireless and digital communications systems, touching the lives of people everywhere."

INVENTOR OF THE VITERBI ALGORITHM

Andrea Viterbi was born in Bergamo, Italy, in 1935. This was a turbulent time in Europe and in 1938 the regime of Benito Mussolini passed new racial laws targeting Italy’s small, integrated Jewish population. Viterbi’s family was in danger and his father, Achille Viterbi, closed his ophthalmologist’s practice and prepared for their escape to the United States of America. The Viterbis left in August 1939 and landed in New York, but after two years the family settled in Boston, Massachusetts.

In the English-speaking world, Andrea was regarded as a female name, so his name was changed to Andrew. Andrew grew up as an American boy, attended the Boston Latin School, and then entered the famous technology university, MIT, just across the river. He entered as a freshman in 1952 to study electrical engineering.

At MIT he progressed rapidly and in just five years he earned both his bachelor’s and master’s degrees in Electrical Engineering. They were conferred in 1957, the year of Sputnik, and the Cold War was underway. The USA, falling behind in the space race, acquired many young talented engineers to develop required technology to further its goal of conquering space. Viterbi, a new MIT graduate, was hired by the California Institute of Technology’s Jet Propulsion Laboratory (then a centre for communications and satellite control systems, soon part of a new National Aeronautics and Space Administration) to develop communications systems. He and his family moved to California, where he met Erna Finci, a refugee from Sarajevo, Yugoslavia, and fell in love.

At the Jet Propulsion Laboratory (JPL), Viterbi specialized in communications technology on a team that designed the telemetry equipment for the first successful U.S. satellite, Explorer 1. The challenge was to develop methods for processing and transmitting information packets from space as accurately and quickly as possible. They confronted two challenges: the satellite’s signal was very weak because of the long journey of the signal and a low power transmitter, and the frequency changes created by rapid orbits.

Viterbi continued his studies at the University of Southern California while working at JPL and completed his Ph.D. dissertation on the error correcting codes. He continued in the academic world, at UCLA's School of Engineering and Applied Science, teaching digital communications and information theory. This time in the late 1960s led to his famous invention, the Viterbi algorithm, and was the period during which he wrote his most important papers on communication theory.

The Viterbi Algorithm

Teaching signal processing was difficult due to the complicated nature of the algorithms used, so Viterbi formulated a more simple way to explain the processing techniques. After realizing the importance of this algorithm, he submitted an article to the IEEE Transactions on Information Theory: "Error bounds for convolutional codes and an asymptotically optimum decoding algorithm". The paper was published in 1967 but the algorithm was considered not much more than elegant theoretical work until computing technology became powerful enough to handle the massive calculations needed to apply the work. Thus the Viterbi algorithm didn’t find widespread application until the move to digital and wireless communications.

At that time nobody could imagine a general application for the algorithm, so Viterbi followed his lawyer’s advice and did not patent it. Instead he founded a company, Linkabit Corporation, with Irwin Jacobs and Leonard Kleinrock, in 1968. The company was a small military contractor for developing satellite communication technology, but it expanded later to the civil sector when mobile satellite telecommunication became feasible.

As the size of the mobile telecommunication technology shrunk and the performance increased in big leaps, Viterbi was surfing the next telecomm wave with a new company, Qualcomm. He left Linkabit with his colleagues in 1985 and founded Qualcomm to produce the OmniTRACS satellite locating service used by long-haul trucking companies, and specialized integrated circuits for digital radio communications such as the Viterbi decoder. Today Qualcomm is better known as the mobile phone technology company that aggressively promoted Viterbi's code division multiple access (CDMA) technology. Its European competitor, GSM, became more popular, but the new 3G (UMTS) mobile communications networks in use today incorporate CDMA technology (also known as WCDMA). Whatever the system, the Viterbi algorithm is at work on every cellular phone in use today.


After the algorithm

While working at Qualcomm, Dr. Viterbi continued lecturing at the University of California, San Diego. In 1994, he became a UCSD professor emeritus. He left Qualcomm, where he was vice chairman and chief technology officer, in 2000, and three years later founded his own venture capital company, the Viterbi Group LLC, which advises and invests in early stage companies, predominantly in wireless communications, network infrastructure and imaging.

In 2000 he was ranked 386th on the Forbes 400 list of the richest Americans, with an estimated worth of $640 million. In 2002 Boston Latin School, Viterbi’s childhood school, built and equipped a new computer centre with funds donated by Dr. Viterbi and in March 2004, the University of Southern California School of Engineering was renamed the Viterbi School of Engineering, in his honour, following his $52 million donation to the school.

When Dr Viterbi retired from Qualcomm in 2000 at the age of 65, he did not retire from active work; far from it. He served from 1997 until 2001 on the U.S. President’s Information Technology Advisory Committee and, since 1983, has been active on the MIT Visiting Committee for Electrical Engineering and Computer Science.

He is a member of the USC School of Engineering Board of Councilors, a member of the board of the Burnham Institute and the Scripps Cancer Center in La Jolla, a trustee of the Mathematical Sciences Research Institute in Berkeley and a member of the University of California’s President’s Council for the National Laboratories.

He and his wife established The Andrew and Erna Viterbi Chair in Communications at USC in 1998. And he is still teaching at the Viterbi School of Engineering.

His legacy goes on. Viterbi’s daughter Audrey is a Ph.D. engineer involved in communications (and a co-founder of Viterbi Group), son Alan is an entrepreneur, and son Alexander is an expert in digital cinema.


The Viterbi algorithm – the detail

Viterbi’s innovation is the Viterbi algorithm, the mathematical formula that enables clear and practically error-free radio communication over long distances, from moving low power transmitters and receivers.

Considering all possible error sources in radio transmission, it is a wonder that communication succeeds. Whether a radio transmitter is in a spacecraft, mobile phone, missile or truck, there are some basic transmission challenges. Firstly, tracking a moving transmitter can be tricky, because of a phenomenon called Doppler shift. When a transmitter is approaching, carrier frequency increases, just like the sound of the whistle from an approaching train is higher than from a standing train. When the transmitter is moving away, the frequency of the carrier frequency reduces – again, just like the sound of the train’s whistle is lower after passing the observer. If the movement is not constant, tracking the shift in the carrier signal frequency can be tricky, if not impossible.

The second problem is finding the signal from the noise if the signal is sent from far away (like from a spacecraft) or from a low power transmitter (like a cell phone). On any mobile phone network, thousands of phones are sharing the same wavelengths, making reliable data transfer between the individual phone and network very challenging.

The Viterbi algorithm was an elegant solution that solved both problems by redundancy and coding; it is essentially just a fast way of eliminating dead ends in the communication. The principle is simple, but the algorithm itself requires considerable computing power. Each bit in the digital information – 0 or 1 – has to be represented by four, eight or more code symbols. So, additional “redundant” information is added at the transmitter, in a process called error correction coding. The result coming into a receiver is a pulsing, miscellaneous stream of bits, ones and zeros.

The received signal is not a clear chain of zeros and ones but is code symbols from which the actual information bits can be reconstructed. Some individual bits can be dropped or distorted, because with the code symbols the missing bits can be guessed with high confidence. There are four states of ‘guess’: very sure, moderately sure, sort of sure and barely sure. The decoder in the receiver evaluates the certainty by comparing the result with neighboring bits and makes the best possible guess. The result is a clear, practically- undamaged message. The key is in a time series of incoming information, with each set of bits tagged in order of arrival.

The algorithm makes it possible to spread a carrier frequency over a wide area of the electromagnetic spectrum. Thousands of low emitting power transmitters can operate in same band range at the same time in small areas without interfering with each other, because their carrier frequencies are coded with different patterns. This principle was first used in military communications and is now the basis of the code division multiple access (CDMA) and UMTS digital cellular communications.

At the time that Dr. Viterbi published his algorithm, computers were not powerful enough to make all calculations required for decoding in real time, but with the growth in computing power, the Viterbi algorithm revolutionized the telecommunications environment by providing a useful tool for error-free communications.

Many methods for error coding and frequency shift elimination were proposed before Viterbi’s work. One of the most powerful algebraic error correction codes was invented by Irving Reed and Gus Solomon from USC in 1960. The code was named after them as “RS codes”. It was mathematically elegant, but extremely complex and too tricky for everyday use. In the 1990s, RS codes became the standard error correction method on compact discs, fax machines and numerous other uses.

After Dr. Viterbi proposed his famous algorithm Andreas Polydoros made significant contributions to the decoding of cell phone-like signals using Viterbi’s methods. His contribution offered a better way to trace the frequencies of incoming signals and to synchronize them, and he was also able to identify and locate signal groups in marginal reception conditions.

Today the Viterbi algorithm is used in billions of cell phones, magnetic recording, most satellite TV receivers, a variety of cable TV systems, voice recognition, and even DNA sequence analysis. The Transfer Control Protocol and the Internet Protocol (TCP/IP), Wi-Fi and Bluetooth are another uses of the Viterbi algorithm and methods based on it. In short, Viterbi’s algorithm is enabling today's exploding wireless world.



Business

Viterbi founded Linkabit Corp. with Irwin Jacobs and Leonard Kleinrock in 1968 to commercialize their innovations. The company was at the beginning practically a contractor to the US military forces and NASA, but gradually the technology was applicable to civil markets, too, and large businesses were soon able to establish low-cost data communications networks linking thousands of locations across the country. Many space and microwave technology companies came in the business to manufacture and operate these systems.

Viterbi and his colleagues left the Linkabit Corp. in 1985 to start another the same year. Qualcomm grew rapidly from small business to a world leader in digital wireless communications products and services. Core to its success is Viterbi's code division multiple access (CDMA) technology, that lets many users share the same radio frequencies and increases system capacity many times over analog system capacity, eliminating the problems of congested radio waves. It also is critical to the success of today's exploding wireless industry.

As the Viterbi algorithm and related methods are used nearly all cellular phones and many other wireless communication applications, it is used nowadays in huge range of different companies.


Further reading

http: //en.wikipedia.org/wiki/Andrew_Viterbi
http: //en.wikipedia.org/wiki/Viterbi_algorithm
http: /web.archive.org/web/20050308104709/http://www.ieee.org/organizations/history_center/oral_historie s/transcripts/viterbi.html
http: //viterbi.usc.edu/about/viterbi/viterbi_algorithm.htm

Andrew J. Viterbi and Jim K. Omura (1979). Principles of Digital Communication and Coding (Communications and Information Theory). ISBN 978-0070675162.

Robert E. Kalman, G. I. Marchuk, A. E. Ruberti, and Andrew J. Viterbi (1987). Recent Advances in Communication and Control Theory (Series in Communication and Control Systems). ISBN 978-0911575460.

CV - Dr. Andrew VITERBI

Citizen of the United States of America
Born 9 March, 1935 at Bergamo, Italy
Married, three children

1939 Emigrated with his family to the United States as a refugee
1952 Entered MIT
1957 Gained BS and MS in Electrical Engineering
1962 Received Ph.D. in digital communications from the University of Southern California
1963 - 1973 Professor in the UCLA School of Engineering and Applied Science
1968 Founded Linkabit Corporation with Irwin Jacobs and Leonard
Kleinrock
1975 - Adjunct Professor of Electrical Engineering and Computer Science at the University of
California, San Diego
1985 Founded Qualcomm Inc. with Irwin Jacobs in 1985
2003 Founded The Viterbi Group, the venture capital company.


Notable prizes and awards

1975 Christopher Columbus International Award from the Italian National Research Council
1980 Aerospace Communications Award from AIAA (jointly with Irwin Jacobs)
1984 IEEE Alexander Graham Bell Medal
1973 Elected Life Fellow of IEEE
1978 Elected as member of the U.S. National Academy of Engineering
1990 Marconi Prize
1996 Elected as member of the U.S. National Academy of Sciences
1996 Elected as member of the American Academy of Arts and Sciences
2004 The University of Southern California School of Engineering was renamed the Viterbi School
of Engineering in his honor
2005 The Benjamin Franklin Medal from the Franklin Institute
2007 IEEE / Royal Society of Edinburgh Wolfson James Clerk Maxwell Award

Press release images