Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-11-12
2004-02-10
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06691277
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a Reed-Solomon decoder, and more particularly to a polynomial evaluation circuit used to determine error-locator polynomial roots in a Reed-Solomon decoder.
2. State of the Art
Error correction is the process of detecting bit errors and correcting them in a system which transmits information in a binary format. Error correction is implemented by decoding a codeword including information and parity bits to facilitate the detection and correction of the bit errors.
There are several types of error correcting codes used to encode information bits for error detection and/or correction. In particular, the Reed-Solomon error correcting code is a widely implemented code since it has increased error correction capability compared to other known error correcting codes. A typical notation for this type of code is RS(m,d) wherein m is the codeword length and d is the number of information bytes in the codeword.
Reed-Solomon codes are constructed from symbols or bytes (where one byte is equal to p-bits) from a finite or Galois Field (GF) of elements. For instance, a GF(2
p
) is a finite field of 2
p
codewords, where m=2
p
−1 is the codeword length. The elements of a Reed-Solomon error correcting code which are defined over a Galois field can be represented as polynomials having associated powers and coefficients.
In general, a Reed-Solomon error detection and correction system includes an encoder portion for encoding d information bytes into a codeword of m bytes and a decoder portion for receiving the Reed-Solomon codeword of m bytes for detecting and correcting any errors.
FIG. 1
shows one prior art decoder system architecture which can be generally described as a Reed-Solomon forward error correction decoder. A Reed-Solomon decoder includes several stages for evaluating the received codewords to obtain information for performing the error correction/detection. For instance, as shown in
FIG. 1
, an error polynomial stage determines an error-locator polynomial. This stage is followed by an error locator stage which functions to determine the roots of the error-locator polynomial. The results provided by the error-locator polynomial are then used in the remainder of the decoding system to perform error correction.
Reed-Solomon codes can be characterized as being unshortened or shortened code. In the case of an unshortened code, the number of codewords in the Reed-Solomon code is the same number of possible elements in the Galois Field that the RS code is defined over. In the case of an shortened code, the number of codewords in the Reed-Solomon code is less than the number of possible elements in the Galois Field that the RS code is defined over. Put into mathematical terms, a RS(m,d) unshortened code defined over the Galois Field GF(2
p
), where m=2
p
−1, has a total codeword length of m bytes where d of the bytes are information bytes. A shortened RS(n,k) code, where RS(n,k)=RS(m, m−n+k), defined over the Galois Field GF(2
p
), where m=2
p
−1, has a total codeword length of n bytes with k information bytes.
In the prior art as described in “On the VLSI Design of a Pipeline Reed-Solomon Decoder Using Systolic Arrays”, H. M. Shao, I. S. Reed, IEEE Transactions on Computers, vol. C-37, No. 10, pp. 1273-1280, October 1988, and in “Error Control Coding: Fundamentals and Applications”, D. J. Costello, S. Lin, New Jersey: Prentice-Hall, 1983, several error-locator polynomial roots determination circuits are proposed.
FIGS. 1B and 1C
described in “On the VLSI Design of a Pipeline Reed-Solomon Decoder Using Systolic Arrays” show two determination circuits. The circuits include cell(1)−cell(d−1), each utilizing feedback multipliers
10
in the critical timing data path
11
of the circuit. The feedback multipliers
10
represent a significant combinational logic operation of a field element
12
and a coefficient stored in the register device
13
. Cell(1)−cell(d−1) shown in
FIG. 1C
are implemented with the same cell structure as shown in FIG.
1
B.
As a result of the manner in which each of the prior art circuits are implemented the overall performance of the determination circuits shown in
FIGS. 1B and 1C
are degraded. More specifically, the optimal number of clock cycles to determine the error-locator polynomial roots in a real time RS decoder with unshortened code which receives back-to-back input frames (one frame=m data bytes) is m or less clock cycles. Similarly, the optimal number of clock cycles to determine the error-locator polynomial roots in a real time RS decoder with shortened code which receives back-to-back input frames (one frame=n data bytes) is n or less clock cycles. However, since each of the prior art circuit designs include a computation intensive logical multiplication step in a critical timing path it takes more than the above irritated optimal amount of time to determine the error-locator polynomial roots.
The present invention determines the error-locator polynomial roots faster than prior art methods by using a high speed pre-computing stage and eliminating the logical multiplication operation from the critical path.
SUMMARY OF THE INVENTION
The present invention is a system and method of determining error-locator polynomial roots in a Reed-Solomon decoder by evaluating a set of expanded error-locator polynomials. A first embodiment of the system and method are implemented to facilitate decoding of an unshortened Reed-Solomon (RS) error correcting code and a second embodiment of the system and method are implemented to facilitate decoding of a shortened RS code.
The improved system and method of evaluating an error-locator polynomial to determine the error locator roots of the polynomial in a Reed-Solomon decoder includes a pre-computing logical operation step followed by a feedback logical operation step. The pre-computing step obviates the need to include constant Galois Field multipliers in the critical path in the polynomial evaluation circuit thereby resulting in fast error locator root determination.
In the system and method used in a Reed-Solomon (RS) decoder to determine roots of error locator polynomials, a first pre-computation operation is performed to obtain a p-bit polynomial solution value in a first clock cycle and second parallel feedback logical operations are performed to obtain a p-bit polynomial solution value in each subsequent clock cycle. The system excludes constant Galois Field multipliers from the critical timing path of the system so as to facilitate high speed error-locator polynomial root determination. In the case of an unshortened RS(m,d) decoder defined over the Galois Field GF(2
p
) where GF(2
p
) is a finite field of 2
p
elements and m=2
p
−1, final root location values are obtained in m cycles. In the case of a shortened RS(n,d) decoder defined over the Galois Field GF(2
p
) where GF(2
p
) is a finite field of 2
p
elements and m=2
p
−1 and n<m, final root location values are obtained in n cycles.
In accordance with one embodiment of the method of error-locator polynomial root determination which is implemented using a RS(m,d) unshortened code defined over a Galois Field GF (2
p
) where m=2
p
−1 is the codeword length in bytes, d is the number of information bytes, and t=(m−d)/2 is the number of bytes which can be corrected per codeword. During a first clock cycle, t pre-compute parallel logical operations are performed between t p-bit coefficient values and t p-bit root values to determine a set of t p-bit pre-computed partial resultant values which are stored in t registers and are summed to determine a p-bit value representing a polynomial solution to one of a set of expanded error-locator polynomials. In each of the (m−1) clock cycles subsequent the first clock cycle, a new set of t p-bit partial root location values are determined, stored, and summed to determine (m−1) p-b
Deol Gurjeet Kaur
Deol Inderpal
Golnabi Habibollah
Baker Stephen M.
Deol Gurjeet Kaur
Zawilski Peter
LandOfFree
High speed pre-computing circuit and method for finding the... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High speed pre-computing circuit and method for finding the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High speed pre-computing circuit and method for finding the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3322697