Back to results
US 7,249,310 B1Granted
Error evaluator for inversionless Berlekamp-Massey algorithm in Reed-Solomon decoders
AssigneeMarvell International Ltd.
InventorsWeishi Feng, Zhan Yu
Life of this patent
Estimating the term…
Abstract
An error correcting Reed-Solomon decoder includes an error locator polynomial generator that generates an error locator polynomial and a scratch polynomial based on an inversionless Berlekamp-Massey algorithm (iBMA). An error location finder communicates with the error locator polynomial generator and generates error locations. An error values finder communicates with the error locator polynomial generator and generates error values directly from the error locator polynomial and the scratch polynomial.
Claims33
An error correcting Reed-Solomon decoder comprising:
- an error locator polynomial generator that generates an error locator polynomial and a scratch polynomial based on an inversionless Berlekamp-Massey algorithm (iBMA);
- an error location finder that communicates with said error locator polynomial generator and that generates error locations;
- and
- an error values finder that communicates with said error locator polynomial generator and that generates error values directly from said error locator polynomial and said scratch polynomial.
1 more element
An error correcting Reed-Solomon decoder comprising:
- error locator polynomial generating means for generating an error locator polynomial and a scratch polynomial based on an inversionless Berlekamp-Massey algorithm (iBMA);
- error location finding means that communicates with said error locator polynomial generating means for generating error locations;
- and
- error values finding means that communicates with said error locator polynomial generating means for generating error values directly from said error locator polynomial and said scratch polynomial.
1 more element
A method for performing error correction comprising:
- generating an error locator polynomial and a scratch polynomial based on an inversionless Berlekamp-Massey algorithm (iBMA);
- identifying error locations using said error locator polynomial;
- and
- identifying error values directly from said error locator polynomial and said scratch polynomial.
1 more element
An error correcting Reed-Solomon decoder, comprising:
- a syndrome calculator that calculates syndrome values;
- an error locator polynomial generator that communicates with said syndrome calculator and that generates an error locator polynomial;
- an error location finder that communicates with at least one of said syndrome calculator and said error locator polynomial generator and that generates error locations;
- and
- an error values finder that communicates with at least one of said syndrome calculator, said error location finder and said error locator polynomial generator and that generates error values without calculating an error evaluator polynomial,
- wherein said the error values are calculated using an error value relationship set forth below:
- Y
- l
- =
- Λ
- 0
-
- Δ
- B
-
- X
- l
- -
- (
- m
- 0
- +
- 2
-
-
- t
- -
- 1
- )
- X
- l
-
- B
- (
- 2
-
-
- t
- )
-
- (
- X
- l
- -
- 1
- )
-
- Λ
- ′
-
- (
- X
- l
- -
- 1
- )
- .
- wherein Λ0 is a coefficient of a 0-th degree term of an error locator polynomial Λ(x), m0 and t are integers defining Reed-Solomon code, ΔB is a discrepancy value, α is a primitive element of GF(q), B(2t)(x) is a scratch polynomial, and Λ′(x) is a derivative of said error locator polynomial Λ(x).
55 more elements
An error correcting Reed-Solomon decoder, comprising:
- syndrome calculating means for calculating syndrome values;
- error locator polynomial generating means that communicates with said syndrome calculating means for generating an error locator polynomial;
- error location finding means that communicates with at least one of said syndrome calculating means and said error locator polynomial generating means for generating error locations;
- and
- error values finding means that communicates with at least one of said syndrome calculating means, said error location finding means and said error locator polynomial generating means for generating error values without calculating an error evaluator polynomial,
- wherein said the error values are calculated using an error value relationship set forth below:
- Y
- l
- =
- Λ
- 0
-
- Δ
- B
-
- X
- l
- -
- (
- m
- 0
- +
- 2
-
-
- t
- -
- 1
- )
- X
- l
-
- B
- (
- 2
-
-
- t
- )
-
- (
- X
- l
- -
- 1
- )
-
- Λ
- ′
-
- (
- X
- l
- -
- 1
- )
- .
- wherein Λ0 is a coefficient of a 0-th degree term of an error locator polynomial Λ(x), m0 and t are integers defining Reed-Solomon code, ΔB is a discrepancy value, α is a primitive element of GF(q), B(2t)(x) is a scratch polynomial, and Λ′(x) is a derivative of the error locator polynomial Λ(x).
55 more elements
A method for performing error correction in a Reed-Solomon decoder, comprising:
- calculating syndrome values;
- generating an error locator polynomial based on said syndrome values;
- identifying error locations using said error locator polynomial;
- and
- identifying error values without calculating an error evaluator polynomial;
- and
- calculating said the error values using an error value relationship set forth below:
- Y
- l
- =
- Λ
- 0
-
- Δ
- B
-
- X
- l
- -
- (
- m
- 0
- +
- 2
-
-
- t
- -
- 1
- )
- X
- l
-
- B
- (
- 2
-
-
- t
- )
-
- (
- X
- l
- -
- 1
- )
-
- Λ
- ′
-
- (
- X
- l
- -
- 1
- )
- .
- wherein Λ0 is a coefficient of a 0-th degree term of an error locator polynomial Λ(x), m0 and t are integers defining Reed-Solomon code, ΔB is a discrepancy value, α is a primitive element of GF(q), B(2t)(x) is a scratch polynomial, and Λ′(x) is a derivative of the error locator polynomial Λ(x).
56 more elements
Dependencies are inferred from the claim text.