[opendtv] Koetter-Vardy RS decoder (Mark's memo)
- From: "Manfredi, Albert E" <albert.e.manfredi@xxxxxxxxxx>
- To: "OpenDTV (E-mail)" <opendtv@xxxxxxxxxxxxx>
- Date: Mon, 22 Nov 2004 10:37:36 -0500
> - There's a interesting report on improved "coding
> gain" by using the Koetter-Vardy algorithm for
> error correction.
This is really exciting stuff. Koetter-Vardy is a
soft decoding algorithm for Reed Solomon. It provides
answers with associated probablity of being correct,
rather than a single take-it-or-leave-it result. It
can be used with any RS-encoded data. And it can be
implemented in hardware, for real-time decoding.
I've been wondering why this same sort of soft
decoding can't also be done with convolutional
encoding schemes, like trellis codes.
This is the sort of breakthrough that demonstrates
that the 14.9 or 15.1 dB C/N margin threshold for
DTT is *not* a hard limit. The hard limit is 10.47
dB (at 19.39 Mb/s in 5.38 MHz channels). Anything
higher than that is "negotiable," as it were.
Sounds like using Koetter-Vardy alone in a
compatible receiver should already be good for
about 13 dB of min C/N margin in Gaussian fading.
And better than that in Rayleigh channels.
Bert
---------------------------------
http://www.physorg.com/printnews.php?newsid=3D1906
Breakthrough in Coding Theory and Practice
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.
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 is a dramatic advance in error-correction
capability for both information storage and communication
systems," said Paul Siegel, director of UCSD's Center for
Magnetic Recording Research. "On the practical end, the
running time of the algorithm is highly reasonable. As a
consequence, Professor Vardy and his colleague opened the
way for us to achieve a radical improvement in the
performance of 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 holds a joint appointment in two Jacobs School
departments: Computer Science and Engineering, as well as
Electrical and Computer 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.
Source: UCSD Jacobs
This news is brought to you by PhysOrg.com
----------------------------------------------------------------------
You can UNSUBSCRIBE from the OpenDTV list in two ways:
- Using the UNSUBSCRIBE command in your user configuration settings at
FreeLists.org
- By sending a message to: opendtv-request@xxxxxxxxxxxxx with the word
unsubscribe in the subject line.
Other related posts:
