Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-02-02
2003-05-27
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S785000
Reexamination Certificate
active
06571368
ABSTRACT:
BACKGROUND OF THE INVENTION
A Reed-Solomon code is an algebraic transformation for encoding a message so that it can be sent through a noisy environment and recovered accurately, even though errors are introduced into the message. Reed-Solomon codes have been used for wide variety of applications such as satellite communications, compact disc playback and asynchronous digital subscriber line (“ADSL”) communications. A discussion of the wide range of applications for Reed-Solomon codes is found in Stephen B. Wicker and Vijay K. Bhargava,
Reed
-
Solomon Codes and Their Applications
(IEEE Press 1994).
The mathematical foundation for Reed-Solomon encoding is a finite field known as a Galois Field (“GF”). An introduction to finite field algebra is found in Shu Lin and Daniel J. Costello, Jr.,
Error Control Coding: Fundamentals and Applications
, pp. 15 et seq. (Prentice-Hall 1983) (“Lin & Costello”). A Galois Field of 2
m
elements (“GF(2
m
)”) is generated from a “primitive” polynomial. Adding or multiplying two of the largest elements of the field together produces a smaller element, because the field is finite. Galois Field GF(2
m
) addition is modulo-2 addition and is indicated by ⊕.
Reed-Solomon encoding takes place in a field of 2
m
elements. A Reed-Solomon encoded message is divided into code words or segments of 2
m
−1 or fewer symbols, each symbol represented by m bits. A code word having fewer than 2
m
−1 symbols is referred to as a shortened code. The “symbols” represent elements of the finite field which, after a fashion, can be added or multiplied together. By one convention, the elements of the field are denoted 0, 1, &agr;, &agr;
2
. . . &agr;
2
m
−2
, where &agr; and the primitive polynomial p(x) are related by the equation p(&agr;)=0.
One of the useful properties of a Reed-Solomon code is that it is well adapted to parallel processing. Efforts have been made to design parallel processors or systolic arrays to decode Reed-Solomon codes, including efforts by Shao and Reed. Howard M. Shao, T. K. Truong, Leslie J. Deutsch, Joseph H. Yueng and Irving S. Reed, “A VLSI Design of a Pipeline Reed-Solomon Decoder,” IEEE Transactions on Computers, Vol. C-34, No. 5, pp. 393-401 (May 1985); Howard M. Shao and Irving S. Reed, “On the VLSI Design of the Reed-Solomon Decoder Using Systolic Arrays,” IEEE Transactions on Computers, Vol. C-37, No. 10, pp. 1273-78 (October 1988). Another well-known decoder was designed by Elwyn Berlekamp and his colleagues. Elwyn Berlekamp, Gadiel Seroussi, Po Tong, “A Hypersystolic Reed-Solomon Decoder,” Chapter 10 in Wicker & Bhargava,
Reed
-
Solomon Codes and Their Applications
, p. 205 et seq. (“Chapter 10”); E. R. Berlekamp, G. Seroussi, and P. Tong, Hypersystolic Reed-Solomon Decoder, U.S. Pat. No. 4,958,348, issued Sep. 18, 1990.
Reed-Solomon decoding generally involves four steps. In the first two steps, a syndrome polynomal S(x) is generated and the key equation &Lgr;(x)S(x)=&OHgr;(x) mod x
2t
is solved to obtain an error location polynomial &Lgr;(x) and an error evaluator polynomial &OHgr;(x). Step three is to evaluate these polynomials to determine which symbols are affected by errors and what are the error values, resulting in an error polynomial E(x). Finally, the error polynomial is combined with the received polynomial R(x) (which is buffered during steps one to three) to produce a reconstructed message without errors.
One of the tools for generating error location and error evaluator ploynomals is Euclid's algorithm. However, Euclid's algorithm involves division in a finite field or multiplication by a multiplicative inverse. A significant contribution of Shao and Reed was to implement a modified Euclid's algorithm to find an error-location polynomial without computation of inverse elements. Berlekamp uses cross-multiplication instead of division in his extended Euclid's algorithm. Chapter 10, pp. 221-22. In addition, Berlekamp introduces a “hypersystolic” architecture, by which he means that clock signals are part of the data that passes from one computation cell to another, thereby reducing the dependence of parallel processing computation cells on synchronized propagation of a clock signal. Use of cross-multiplication increases processing time or the number of multipliers required in each cell. Hypersystolic architecture increases the number of steps required to produce a result, as data passes in a special serial sequence up and down each of Berlekamp's towers and from one tower to the next, twice through each cell.
An advantageous design would directly apply Euclid's algorithm using a single divider, sharing the results, and thereby minimizing the number of dividers required. A shared divider design for the second step of Reed-Solomon decoding would enable parallel processing of each symbol or term of a code word. The number of clock cycles required to apply Euclid's algorithm would be minimized, resulting in either faster processing or use of a slower clock speed with resulting cost reductions.
Another aspect of an advantageous design would be to evaluate both the error location and error evaluator polynomial simultaneously in a minimum number of cycles. The overall objective is to minimize the complexity and number of computation cells, thereby reducing the foot print of the decoder circuit, reducing its cost and speeding signal processing.
SUMMARY OF THE INVENTION
One aspect of the present invention is a method and device for calculation of syndromes, useful in decoding a Reed-Solomon (N, K) encoded message with m-bit symbols, including a set of 2t syndrome calculation cells coupled to inputs and outputs, where the syndrome calculation cells include a syndrome register coupled to an output, a constant multiplier with its input coupled to the syndrome register, an adder with inputs coupled to the serial input and the constant multiplier, and a mux with its inputs coupled to “0” and to the adder and its output coupled to the syndrome register, where the mux is responsive to a syndrome calculate signal.
A second aspect of the present invention is a method and device to divide polynomials over a Galois Field, useful in decoding a Reed-Solomon (N, K) encoded message with m-bit symbols, including a dividend polynomial array of first cells, the first cells coupled with the next lower order first cell, a divisor polynomial array of second cells, the second cells coupled with the next lower order second cell, a shared divider for calculating the highest order first cell divided by the highest order second cell, its output coupled to the first cells, and logic to calculate a quotient of the highest order first cell divided by the highest order second cell and a remainder polynomial of the dividend polynomial minus said quotient times the divisor polynomial. The present invention is adapted to produce a quotient and remainder in a single clock cycle. It may include a product polynomial array of third cells, the third cell coupled to its next lower order third cell and to the shared divider. The present invention can be practiced with only one multiplier per first cell and no multipliers in the second and third cells.
Another aspect of the present invention is a method and device to apply Euclid's algorithim to decode a Reed-Solomon (N, K) encoded message of m-bit symbols and corresponding syndromes, where N<=2
m
−1 and N−K=2t, including a dividend polynomial array of first cells, the first cells coupled to the next lower order first cells, a divisor polynomial array of second cells, the second cells coupled to the same and next higher order first cells and to the next lower order second cell, an array of third cells, the third cell coupled to the same order first and second cells and to the next lower order third cell, a shared divider with its inputs coupled to the highest order first and second cells and its output coupled to the first cells, and logic to calculate a quotient of the highest order first cell divided by the h
Baker Stephen M.
Haynes Mark A.
Haynes Beffel & Wolfeld LLP
Macronix International Co. Ltd.
LandOfFree
Systolic Reed-Solomon decoder does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Systolic Reed-Solomon decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systolic Reed-Solomon decoder will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3061158