Forward error correction apparatus and methods
AssigneeLSI Logic Corporation
InventorTan C. Dadurian
Life of this patent
Estimating the term…
Abstract
Forward error correction apparatus and methods are described. A forward error correction system includes multiplier for computing an erasure location polynomial. An erasure location is applied to an input of a input register. An output of a given register in a series of registers and an output of the input register are multiplied to produce a product. The product and an output of the dummy register are added to produce a sum. The sum is applied to an input of a subsequent register immediately following the given register. The subsequent register is treated as the given register and the above-described steps are repeated for each of the erasure locations. A two-buffer method and apparatus for computing an error location polynomial using the Berlekamp error correction algorithm also is described.
Claims12
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.
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.
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;
- (e) treating the subsequent register as the given register and repeating steps (a)-(d) for each of the erasure locations.
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.
Dependencies are inferred from the claim text.