November 9, 2004

UC San Diego Scientist Wins Award From IEEE Information
Theory Society For Breakthrough In Coding Theory And Practice

By Doug Ramsey

The Board of Governors of the IEEE Information Theory Society has selected an article by professors from the University of California, San Diego (UCSD) and the University of Illinois at Urbana-Champaign (UIUC) as the top publication in information theory during the past two years. The article developed an improved decoding algorithm for error-correcting codes that are used today in communication and storage devices ranging from computer hard drives to deep-space probes.

Alexander Vardy

UIUC's Ralf Koetter and UCSD's Alexander Vardy received the award for their work on "Algebraic Soft-Decision Decoding of Reed-Solomon Codes," published in the November 2003 issue of IEEE Transactions on Information Theory (vol. 49, no. 11, pp. 2809-2825). The article described the first truly efficient and effective soft-decision decoding algorithm for Reed-Solomon codes, thereby solving a long-standing open problem in coding theory and practice.

"Decoding is always a matter of probability," Vardy said. "There had been a mismatch between the probabilistic domain of the channel and the algebraic domain of the decoder. In a sense, what we had to do was to achieve a happy marriage of probability and algebra."

“This paper represents a major step forward in the field of error-correction coding, with implications for both information storage and data communication systems,” said Paul Siegel, director of UCSD’s Center for Magnetic Recording Research. “The new decoding algorithm is not only a conceptual breakthrough, but also practical from the implementation point-of-view. As a consequence, the work of Koetter and Vardy offers a way to dramatically improve the performance of many systems using Reed-Solomon codes.”

Although they pre-date turbo codes and other recent codes, Reed-Solomon codes remain in widespread use. About 75% of error-correction circuits in operation today decode Reed-Solomon codes. For example, every CD player and most computer hard drives use these codes. The cited paper adapted a new decoding technique, developed by Venkatesan Guruswami and Madhu Sudan at MIT, and used it to design a soft-decision decoding algorithm, i.e., an algorithm that fully utilizes the probabilistic information available at the receiver. The Koetter-Vardy soft-decision decoding algorithm results in substantial coding gains in practice [up to 1.5 decibels on additive white Gaussian noise channels, and much more on Rayleigh-fading channels]. Due to these gains and feasible complexity, the new algorithm has the potential to make today's standard decoding algorithms obsolete.

The Koetter-Vardy algorithm has already passed one practical test with flying colors. Ham radio operators used it to decode 'moonbounce' messages bounced off the Moon and back to Earth using low-power amplifiers and receivers. "This is where I started being so favorably impressed," said Princeton's Joe Taylor, a ham radio operator and a Nobel Laureate. "The KV algorithm is fully 2 dB better than what I have been using, and the advantage holds up over a wide range of signal-to-noise ratios. The use of the KV Reed-Solomon decoder in my moonbounce program has been a spectacular success. Many dozens, perhaps hundreds, of Earth-Moon-Earth contacts are being made with it every day now, all over the world."

Vardy says that the article cited by the Information Theory Society opened up many more avenues of research in his lab and elsewhere. "Several groups in both academia and industry are now working in this area, including people at Caltech, MIT, University of Toronto, University of Minnesota and, of course, UIUC and UCSD," said Vardy. "We have presented several recent papers at conferences and are preparing at least three or four of them for journal submission."

Prof. Vardy is based in the Electrical and Computer Engineering department, with a joint appointment in Computer Science and Engineering. The Russian-born scientist received his Ph.D. from Tel-Aviv University in 1991. After two years at the IBM Almaden Research Center, he taught at the University of Illinois (UIUC) before joining the Jacobs School faculty in 1999. His work in coding theory has already been recognized by numerous awards, including the Xerox Award for faculty research, the Packard Foundation Fellowship, and the NSF Career Award. He is an Editor for the SIAM Journal on Discrete Mathematics. From 1995 until 2001, he served as an Associate Editor for Coding Theory and then as the Editor-in-Chief of the IEEE Transactions on Information Theory. He is affiliated with three UCSD research centers: CMRR, the Center for Wireless Communications (CWC), and the California Institute for Telecommunications and Information Technology [Cal-(IT)²].

Media Contact: Doug Ramsey, (858) 822-5825