New Coding Scheme Improves Reed-Solomon Error Correction

[Gregg Lengling]

In analog communications, error correction depends on the ability of humans "decoding" the sound or picture to separate the desired information from the noise. In digital communications, this function is accomplished through the use of forward error correction coding. Coding spreads out the data (in amplitude steps, time or both) to allow to it to be recovered even if portions of it are obliterated by noise or interference. Improvements in coding algorithms allow weaker signals to be decoded at the same data rate or higher data rates at the same signal to noise ratio. Such an improvement was the subject of an article recognized by the Board of Governors of the IEEE Information Theory Society as the top publication in information theory during the past two years.


The article, by Ralf Koetter, a professor at the University of Illinois at Urbana-Champaign (UIUC) and Alexander Vardy, a professor at the University of California, San Diego was titled, "Algebraic Soft-Decision Decoding of Reed-Solomon Codes." The article describes an efficient and effective soft-decision decoding algorithm for Reed-Solomon codes. Professor Vardy explained, "Decoding is always a matter of probability. 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."


The Koetter-Vardy algorithm can offer up to 1.5 dB of coding gain on white Gaussian noise channels and "much more" on Rayleigh-fading channels (where no direct or reflected signal is dominant). Ham Radio operators have used the algorithm for communications bounced off the surface of the moon. Ham radio operator Joe Taylor, a Nobel Laureate at Princeton University, said, "This is where I started being so favorably impressed. 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."


In addition to communications, the KV algorithm could be used to improve the performance of CD players and the many computer hard drives that use Reed-Solomon encoding. It will be interesting to see if the KV algorithm finds use in terrestrial DTV applications to improve on the Reed-Solomon coding already used in the ATSC DTV system.