ANDREA VITERBI

Andrea Viterbi was born in Bergamo, Italy, in 1935. This was a turbulent time in Europe and the Viterbis left in August 1939 and landed in New York. 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. 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 led to his invention, in the late 1960s, of his famous algorithm, the Viterbi algorithm, and was the period during which he wrote his most important papers on communication theory.

In 2000 Viterbi 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.

Read the whole story (PDF)
Andrew Viterbi in wikipedia
Andrew Viterbi interviewed by the National Academy of Sciences

Innovation

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.

The algorithm was published in 1967

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.

What is Viterbi algorithm?

The algorithm 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.

From 1967 to the 21st century

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.

Applications

Solving transmission problems

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.

Enabling wireless world

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.