Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-06-23
2003-10-14
Decady, Albert (Department: 2184)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S782000
Reexamination Certificate
active
06634007
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to decoding of error-correcting codes, and in particular, to efficient soft-decision decoding of Reed-Solomon and related codes.
The present invention particularly concerns an algorithmic soft-decision decoding procedure for Reed-Solomon codes, the procedure (i) making optimal use of the “soft-decision” reliability information available from a communication or storage system (channel), while (ii) executing in a time that scales polynomially with the length of the code. Said decoding procedure also extends to the decoding of Bose-Chaudhuri-Hocquenghem (BCH) codes and most algebraic-geometry (AG) codes; significantly outperforming the generalized minimum distance (GMD) decoding of Forney, Jr.
2. Description of Prior and Related Art
2.1. Reed-Solomon Codes
Reed-Solomon (RS) codes are among the most extensively used error-correcting codes today, and their practical importance is well established. See the book S. B. Wicker, V. K. Bhargava, Reed-Solomon Codes and Their Applications, IEEE Press, 1994, and in particular the chapters by K. A. S. Immink, Reed-Solomon codes and the compact disc, ibid, 1994; R. J. McEliece, L. Swanson, Reed-Solomon codes and the exploration of the solar system, ibid, 1994; S. B. Wicker, M. Bartz, Reed-Solomon codes in hybrid automatic repeat-request systems, ibid,. 1994; M. B. Pursley, Reed-Solomon codes in frequency-hop communications, ibid, 1994; D. Sarwate, Reed-Solomon codes and the design of sequences for spread-spectrum multiple-access communications, ibid, 1994; and E. R. Berlekamp, G. Seroussi, P. Tong, A hypersystolic Reed-Solomon decoder, ibid, 1994. See also E. R. Berlekamp, R. E. Peile, S. P. Pope, The application of error control to communications, IEEE Commun. Mag., vol. 25, pp. 44-57, 1987; W. W, Wu, D. Haccoun, R. E. Peile, Y. Hirata, Coding for satellite communication, IEEE J. Select. Areas Commun., vol. SAC-5, pp. 724-785, 1987; Consultative Committee for Space Data Systems, Recommendations for Space Data System Standards, Blue Book, 1984; M. B. Pursley, W. E. Stark, Performance of Reed-Solomon coded frequency-hop spread-spectrum communication in partial band interference, IEEE Trans. Commun., vol. COM-33, pp. 767-774, 1985; and D. Divsalar, R. M. Gagliardi, J. H. Yuen, PPM performance for Reed-Solomon decoding over an optical-RF relay link, IEEE Trans. Commun., vol. COM-32, pp. 302-305, 1984.
Reed-Solomon codes are used in digital audio disks (CD's) and digital versatile disks (DVD's). See S. B. Wicker, V. K. Bhargava, op. cit. and K. A. S. Immink, op. cit.
Reed-Solomon codes are used in satellite communications. See S. B. Wicker, V. K. Bhargava, op. cit., E. R. Berlekamp, R. E. Peile, S. P. Pope, op. cit., and W. W, Wu, et. al. op. cit.
Reed-Solomon codes are used in deep-space telecommunication systems, including multiple deep-space communication standards. See S. B. Wicker, V. K. Bhargava, op. cit., R. J. McEliece, L. Swanson, op. cit, and Consultative Committee for Space Data Systems, op. cit.
Reed-Solomon codes are used in frequency-hop and spread-spectrum systems. See M. B. Pursley, op. cit., D. Sarwate, op. cit, and M. B. Pursley, W. E. Stark, op. cit.
Reed-Solomon codes are used in error-control systems with feedback. See S. B. Wicker, V. K. Bhargava, op. cit. and S. B. Wicker, M. Bartz, op. cit.
Reed-Solomon codes are used in optical communications. See S. B. Wicker, V. K. Bhargava, op. cit. and D. Divsalar, et. al., op. cit.
2.2 Decoding of Reed-Solomon Codes
The decoding of Reed-Solomon codes is one of the most frequently performed tasks in today's communication and storage systems. Since the discovery of Reed-Solomon codes in the early 1960's (see I. S. Reed, G. Solomon, Polynomial codes over certain finite fields, J. Soc. Indust. Appl. Math., vol. 8. pp. 300-304, 1960), a steady stream of work has been directed towards streamlining their decoding algorithms. Today (circa 2000), very efficient techniques are available to accomplish that task. In particular, hard-decision decoders for RS codes have been implemented in hyper-systolic VLSI using algebraic decoding algorithms. Such decoders have been designed to operate at sustained data rates of 820 Mb/s. See E. R. Berlekamp, G. Seroussi, P. Tong, A hypersystolic Reed-Solomon decoder, op. cit.
An important problem in hard-decision decoding of Reed-Solomon codes is that of decoding beyond the error-correction radius (which is equal to one half of the minimum distance of the code). Search techniques have traditionally dominated approaches to this problem. See e.g., R. E. Blahut, Theory and Practice of Error Control Codes, Addison Wesley, 1994. However, for polynomially-bounded decoding complexity, these techniques do not achieve decoding beyond half the minimum distance of the code, in an asymptotic sense.
A breakthrough in this area was achieved by Sudan in 1997. Reference M. Sudan, Decoding of Reed-Solomon codes beyond the error correction bound, J. Compl. vol. 13, pp. 180-193, 1997; and also V. Guruswami, M. Sudan, Improved decoding of Reed-Solomon and algebraic-geometric codes, IEEE Trans. Inform. Theory, vol. 45, pp. 1755-1764, 1999. In the form presented in V. Guruswarni, M. Sudan op. cit., Sudan's algorithm corrects any fraction of up to &tgr;≦1−{square root over (R)} erroneous positions in an RS code of rate R. Thus the error correction capabilities exceed the minimum distance error-correction bound (1−R)/2 for all rates in the interval [0,1]. The present invention makes use of the methods and algorithms developed by V. Guruswami, M. Sudan, op. cit.
2.3 Soft-Decision Decoding
Early in the development of coding theory, it was found convenient to represent communication channels as conveyors of symbols drawn from finite sets. The effects of channel noise were represented by the occasional (random) reception of a symbol other than the one that was transmitted. This abstraction of reality permitted the application of powerful algebraic and combinatoric tools to the code design and decoding problems; Reed-Solomon codes themselves were developed through this abstraction.
In reality, however, channel noise is almost always a continuous phenomenon. What is transmitted may be selected from a discrete set, but what is received comes from a continuum of values. This viewpoint leads to the soft-decision decoder, which accepts a vector of real samples of the noisy channel output and estimates the vector of channel input symbols that was transmitted. Alternatively, a soft-decision decoder can accept any quantization of the real samples of the noisy channel output. By contrast, the hard-decision decoder requires that its input be from the same alphabet as the channel input. It is now well known that soft-decision decoding techniques can provide up to 3 dB more coding gain for the additive white Gaussian channel.
A soft-decision decoder accepts analog values directly from the channel; the demodulator is not forced to decide which of the q possible symbols a given signal is supposed to represent. The decoder is thus able to make decisions based on the quality of a received signal. All of the information on the “noisiness” of a particular received signal is lost when the demodulator assigns a symbol to the signal prior to decoding. It has been estimated that this loss of information results in a 2 to 3 dB loss in performance.
2.4. Soft-decision Decoding of Reed-Solomon Codes
Soft-decision decoding of Reed-Solomon codes is different in many ways from hard-decision decoding. The advantage of soft-decision over hard-decision decoding is adequately established in many works. See, for example, J. G. Proakis, Digital Communications, New York: McGraw-Hill, 1983; C. G. Clark, J. B. Cain, Error Correction Coding for Digital Communication, New York: Plenum, 1981; and U. Cheng, G. K. Huth, Bounds on the bit error probability of a linear cyclic code GF(2
i
) and its extended code, IEEE Trans. Inform. Theory, vol. 34, pp. 776-735, 1988. This later reference al
Koetter Ralf
Vardy Alexander
CodeVector Technology
De'cady Albert
Ingrassia Fisher & Lorenz P.C.
Lamarre Guy
LandOfFree
Algebraic soft decoding of reed-solomon codes does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Algebraic soft decoding of reed-solomon codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algebraic soft decoding of reed-solomon codes will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3127820