Nova Patents
EP0806838A1

Polynomial evaluator for use in a reed-solomon decoder

Abstract

An apparatus, for use in a Reed-Solomon decoder, evaluates a polynomial P(X) iteratively, by substituting α-(N-j) for X in a jth iteration, to thereby provide a jth evaluation result P(α-(N-j)), wherein j is an integer ranging from 1 to N, N being a predetermined positive integer, and α is a primitive element in a finite field GF(2m). The apparatus comprises: a FIFO buffer having T registers, T being a predefined positive integer; a root input block for sequentially providing a first group of T elements in the finite field during the jth iteration; a multiplier for sequentially multiplying the contents of the FIFO buffer with the first group of T elements in the finite field provided from the root input block, to thereby provide a jth set of T evaluating terms during the jth iteration; a multiplexor for providing T initial evaluating terms to the FIFO buffer during an initialization and providing the jth set of T evaluating terms to the FIFO buffer during the jth iteration, to be stored therein; an addition block for determining a sum of the T evaluating terms of the jth set, to thereby provide a jth sum; and an output block for adding a 0th coefficient of the polynomial to the jth sum, to thereby provide the jth evaluation result during the jth iteration.

EP0806838A1, drawing sheet 1
Sheet 1 of 18

Term

Term ended

Projected expiry passed 26 November 2016, 9.8 years ago.

  1. Priority
  2. Filed
  3. Published
  4. Projected expiry
  5. Today

13 claims: 6 independent, 7 dependent

  1. 1
    An apparatus, for use in a Reed-Solomon decoder, for evaluating a polynomial P(X) iteratively, by substituting α -(N-j) for X in a jth iteration, to thereby provide a jth evaluation result P(α -(N-j) ), wherein j is an integer ranging from 1 to N, N being a predetermined positive integer, and α is a primitive element in a finite field GF(2 m ), said apparatus comprising:a FIFO buffer having T memory means, T being a predefined positive integer;updating means for sequentially multiplying the contents of the FIFO buffer with a first group of T elements in the finite field, to thereby provide a jth set of T evaluating terms during the jth iteration;means for generating T initial evaluating terms;means for selectively providing the T initial evaluating terms or the jth set of T evaluating terms provided from the updating means to the FIFO buffer, to be stored therein;first addition means for determining a sum of the T evaluating terms of the jth set, to thereby provide a jth sum;and second addition means, during the jth iteration, for adding a 0th coefficient of the polynomial to the jth sum, to thereby provide the jth evaluation result.
  2. 2
    An apparatus, for use in a Reed-Solomon decoder, for evaluating a polynomial P(X) iteratively, by substituting α -(N-j) for X in a jth iteration, to thereby provide a jth evaluation result P(α -(N-j) ), wherein j is an integer ranging from 1 to N, N being a predetermined positive integer, and α is a primitive element in a finite field GF(2 m ), said apparatus comprising:a FIFO buffer having T memory means, T being a predefined positive integer;means for initializing the FIFO buffer with T initial evaluating terms by sequentially providing the T initial evaluating terms to the FIFO buffer;updating means for sequentially multiplying the contents of the FIFO buffer with a first group of T elements in the finite field, to thereby provide a jth set of T evaluating terms during the jth iteration;means for sequentially providing the jth set of T evaluating terms during the jth iteration, to the FIFO buffer, to be stored therein;first addition means for determining a sum of the T evaluating terms of the jth set, to thereby provide a jth sum;and second addition means, during the jth iteration, for adding a 0th coefficient of the polynomial to the jth sum, to thereby provide the jth evaluation result.
  3. 3
    An apparatus, for use in a Reed-Solomon decoder, for evaluating a polynomial P(X) iteratively, by substituting α -(N-j) for X in a jth iteration, to thereby provide a jth evaluation result P(α -(N-j) ), wherein j is an integer ranging from 1 to N, N being a predetermined positive integer, and α is a primitive element in a finite field GF(2 m ), said apparatus comprising:a FIFO buffer having T memory means, T being a predefined positive integer;updating means for sequentially multiplying the contents of the FIFO buffer with a first group of T elements in the finite field, to thereby provide a jth set of T evaluating terms during the jth iteration;means for generating T initial evaluating terms;means for selectively providing the T initial evaluating terms or the jth set of T evaluating terms to the FIFO buffer, to be stored therein;and addition means for determining a sum of the T evaluating terms of the jth set, to thereby provide the jth evaluation result.
  4. 10
    The apparatus of any one of claims 1 to 9, wherein the updating means includes:first input means for sequentially providing the first group of T elements in the finite field during the jth iteration;and means for sequentially multiplying the contents of the FIFO buffer with the first group of T elements in the finite field provided from the first input means, to thereby provide the jth set of T evaluating terms during the jth iteration.
  5. 11
    The apparatus of any of claims 1 and 2, and 4 to 7 wherein the first addition means includes:an adder for adding an evaluating term provided from the multiplication means with a feedback value, to thereby provide a partial sum or the jth sum;selection means for selectively providing the partial sum provided from the adder or 0;and memory means for storing the partial sum or 0 provided from the selection means and providing the partial sum or 0 as the feedback value to the adder.
  6. 13
    The apparatus of any one of claims 1 and 2, and 5 to 7 further comprising means for deciding whether the evaluation result equals 0, to thereby provide an error signal.
Independent claims6