Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-09-10
2002-09-03
Chung, Phung M. (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S784000
Reexamination Certificate
active
06446233
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to apparatus and methods of forward error correction.
Forward error correction techniques typically are used in digital communication systems (e.g., a system for reading information from a storage medium, such as an optical disk) to increase the rate at which reliable information may be transferred and to reduce the rate at which errors occur. Various errors may occur as data is being read from a storage medium, including data errors and erasures. Many forward error correction techniques use an error correction code to encode the information and to pad the information with redundancy (or check) symbols. Encoded information read from a storage medium may be processed to correct errors and erasures.
Reed-Solomon (RS) encoding is a common error correction coding technique used to encode digital information which is stored on storage media. A RS (n, k) code is a cyclic symbol error correcting code with k symbols of original data that have been encoded. An (n-k)-symbol redundancy block is appended to the data. The RS code represents a block sequence of a Galois field GF(2
m
) of 2
m
binary symbols, where m is the number of bits in each symbol. Constructing the Galois field GF(2
m
) requires a primitive polynomial p(x) of degree m and a primitive element &bgr;, which is a root of p(x). The powers of &bgr; generate all non-zero elements of GF(2
m
). There also is a generator polynomial g(x) which defines the particular method of encoding. A RS decoder performs Galois arithmetic to decode the encoded data. In general, RS decoding involves generating syndrome symbols, computing (e.g., using a Berlekamp computation process) the coefficients &sgr;
i
of an error location polynomial &sgr;(x), using a Chien search process to determine the error locations based upon the roots of &sgr;(x), and determining the value of the errors and erasures. After the error locations have been identified and the values of the errors and erasures have been determined, the original data that was read from the storage medium may be corrected, and the corrected information may be transmitted for use by an application (e.g., a video display or an audio transducer).
SUMMARY OF THE INVENTION
In one aspect, the invention features an apparatus for computing the coefficients of a k-th degree erasure polynomial, comprising: k registers for storing k coefficient values of the erasure polynomial, each register having an input and an output; a dummy register having an input coupled to receive a coefficient value from the output of one of the k registers and having an output; an input register location having an input and an output; a multiplier having a first input coupled to the output of the input register, a second input coupled to receive a coefficient value from one of the k registers, and an output; and an adder having a first input coupled to the output of the multiplier, a second input coupled to the output of the dummy register, and an output coupled to the input of the k registers.
The input of the input register preferably is coupled to a memory configured to store a value representative of the root of the erasure polynomial. A controller configured to initialize each of the k registers to 1 and to initialize the dummy register to 0 may be provided. A multiplexer may be coupled between the output of the k registers and the input of the dummy register and the second input of the multiplier. A demultiplexer may be coupled between the inputs of the k registers and the output of the adder.
In another aspect, the invention features a method of computing the coefficients of a k-th degree erasure polynomial corresponding to k known erasure locations, comprising: (a) multiplying an erasure location and the output of a given register in a series of k registers to produce a product; (b) if there is a register immediately preceding the given register in the series of registers, adding the product to the output of the preceding register to produce a sum; (c) applying the sum (or the product, if a sum was not produced) to the input of the given register; (d) repeating steps (a)-(c) for each of the registers in the series; (e) clocking each of the registers in the series to transmit register input values to register outputs; and (f) repeating steps (a)-(e) for each of the erasure locations.
The output of a first register may be initialized to 1, and the outputs of the remaining registers may be initialized to 0.
In another aspect, the invention features a method of computing the coefficients of a k-th degree erasure polynomial corresponding to k known erasure locations, comprising: (a) applying an erasure location to an input of a input register; (b) multiplying an output of a given register in a series of registers and an output of the input register to produce a product; (c) adding the product and an output of the dummy register to produce a sum; (d) applying the sum to an input of a subsequent register immediately following the given register; and (e) treating the subsequent register as the given register and repeating steps (a)-(d) for each of the erasure locations.
The output of each of the registers in the series may be initialized to 1, the dummy register may be initialized to 0, and the input of a first of the series of registers may be initialized to an erasure location.
The invention also features an apparatus for the Berlekamp computation of the coefficients of an error location polynomial, comprising: first and second polynomial containers each configured to store n coefficients of a polynomial; first and second multiplexers each having n inputs coupled to receive a respective coefficient from the first and second polynomial containers, respectively, and each having an output; an adder having a first input coupled to the output of the first multiplexer, a second input, and an output; a multiplier having a first input coupled to the output of the second multiplexer, a second input, and an output coupled to the second input of the adder; and a demultiplexer having an input coupled to the output of the adder, a first output coupled to store a polynomial coefficient in the first polynomial container, and a second output coupled to store a polynomial coefficient in the second polynomial container.
A memory may have an output coupled to the second input of the multiplier and may be configured to stored intermediate values computed during implementation of a Berlekamp method of computing the coefficients of the error location polynomial. A controller may be configured to switch the identities of the first and second polynomial containers.
Among the advantages of the invention are the following. The invention provides hardware support that significantly increases the rate at which error and erasure polynomials may be computed using a relatively small number of hardware components. The invention therefore enables forward error correction techniques to be implemented in a high speed digital signal processing chip. The invention provides a relatively simple micro-sequencer-based forward error corrector design that may be implemented with a relatively small number of circuit components, and provides improved programming functionality.
Other features and advantages will become apparent from the following description, including the drawings and the claims.
REFERENCES:
patent: 4162480 (1979-07-01), Berlekamp
patent: 4644543 (1987-02-01), Davis, Jr.
patent: 5170399 (1992-12-01), Cameron et al.
patent: 5323402 (1994-06-01), Vaccaro et al.
patent: 5592404 (1997-01-01), Zook
patent: 5602857 (1997-02-01), Zook et al.
patent: 5642367 (1997-06-01), Kao
patent: 5680340 (1997-10-01), Glover et al.
patent: 5694330 (1997-12-01), Iwamura et al.
patent: 5774648 (1998-06-01), Kao et al.
patent: 5818855 (1998-10-01), Foxcroft
patent: 5883907 (1999-03-01), Hoekstra
patent: 6061826 (2000-05-01), Thirumoorthy et al.
patent: 6209115 (2001-03-01), Truong et al.
Chung Phung M.
LSI Logic Corporation
LandOfFree
Forward error correction apparatus and methods does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Forward error correction apparatus and methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Forward error correction apparatus and methods will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2837110