[opendtv] Re: Koetter-Vardy RS decoder (Mark's memo)
- From: "Allen Le Roy Limberg" <allimberg@xxxxxxxxxxxx>
- To: <opendtv@xxxxxxxxxxxxx>
- Date: Mon, 22 Nov 2004 14:39:07 -0500
If the R-S code doesn't have to locate byte errors, twice as many byte
errors per R-S codeword can be corrected using an alternative decoding
algorithm. The rumor is that work is being done on using soft trellis
decoding for locating byte errors. I believe this practice is mentioned in
the revised ATSC document A/54.
Al
----- Original Message -----
From: "Manfredi, Albert E" <albert.e.manfredi@xxxxxxxxxx>
To: "OpenDTV (E-mail)" <opendtv@xxxxxxxxxxxxx>
Sent: Monday, November 22, 2004 10:37 AM
Subject: [opendtv] Koetter-Vardy RS decoder (Mark's memo)
> > - 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.
>
>
----------------------------------------------------------------------
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:
