Reed-Solomon decoder and VLSI implementation thereof
OwnerT. K. Truong, Shen-Li Fu +1inventors
InventorsT. K. Truong, Shen-Li Fu, T. C. Cheng
Life of this patent
Estimating the term…
Abstract
A highly efficient Reed-Solomon decoding algorithm and a VLSI implementation thereof are used to correct errors found in data which was previously encoded utilizing Reed-Solomon encoding. The Reed-Solomon decoding algorithm takes advantage of certain desirable features of Euclid's algorithm and of the Berlekamp-Massey algorithm to provide a simplified and computationally efficient algorithm which eliminates the need to perform inverses.
Claims8
A method of using a general purpose computer to correct errors in data stored using Reed-Solomon encoding by solving an error locator polynomial and an error evaluator polynomial using the step of iterating without performing polynomial division and inverses during iteration, wherein the step of iterating comprises:
- a. using a general purpose computer to initially define:
- {overscore (C)}(0)(x)=1, {overscore (D)}(0)(x)=1, {overscore (A)}(0)(x)=1, {overscore (B)}(0)(x)=0, {overscore (l)}(0)=0,
- γ(k)=1 if k≦0;
- b. using a general purpose computer to set k=k+1 If k=d−1, otherwise, defining Δ _ ( k ) = ∑ j = 0 l _ ( k - 1 ) c _ j ( k - 1 ) s k - j ;
- ( 23 )
- c. and using a general purpose computer to let C _ ( k ) ( x ) = γ ( k - 1 ) C _ ( k - 1 ) ( x ) - Δ _ ( k ) A _ ( k - 1 ) ( x ) · x ( 24 ) D _ ( k ) ( x ) = γ ( k - 1 ) D _ ( k - 1 ) ( x ) - Δ _ ( k ) B _ ( k - 1 ) ( x ) · x 14 ( 25 ) A _ ( k ) ( x ) = { x · A _ ( k - 1 ) ( x ) , if Δ _ ( k ) = 0 or if 2 l _ ( k - 1 ) > k - 1 C _ ( k - 1 ) ( x ) , if Δ _ ( k ) ≠ 0 and 2 l _ ( k - 1 ) ≤ k - 1 ( 26 ) , ( 27 ) B _ ( k ) ( x ) = { x · B _ ( k - 1 ) ( x ) , if Δ _ ( k ) = 0 or if 2 l _ ( k - 1 ) > k - 1 D _ ( k - 1 ) ( x ) , if Δ _ ( k ) ≠ 0 and 2 l _ ( k - 1 ) ≤ k - 1 ( 28 ) ( 29 ) l _ ( k ) ( x ) = { l _ ( k - 1 ) , if Δ _ ( k ) = 0 or if 2 l _ ( k - 1 ) > k - 1 k - l _ ( k - 1 ) ( x ) , if Δ _ ( k ) ≠ 0 and 2 l _ ( k - 1 ) ≤ k - 1 ( 30 ) ( 31 ) γ ( k ) = { γ ( k - 1 ) , if Δ _ ( k ) = 0 or if 2 l _ ( k - 1 ) > k - 1 Δ _ ( k ) , if Δ _ ( k ) ≠ 0 and 2 l _ ( k - 1 ) ≤ k - 1 ;
- ( 32 ) ( 33 )
- and
- d. repeating step (a).
A method of using a general purpose computer to correct errors in data stored using Reed-Solomon encoding by solving an error locator polynomial and an error evaluator polynomial using the step of iterating without performing polynomial division and inverses during iteration, comprising the steps of:
- a. using a general purpose computer to determine an error locator polynomial according to the equation:
- σ ( x ) = C _ ( d - 1 ) ( x ) β ;
- ( 47 )
- and
- b. using a general purpose computer to determine an error evaluator polynomial according to the equation:
- P ( x ) = Ω ( x ) - σ ( x ) = D _ ( d - 1 ) ( x ) β - σ ( x ) . ( 48 )
A method for correcting errors in data stored using Reed-Solomon encoding, the method comprising the step of using a dedicated circuit to iterate without performing polynomial division and inverses during iteration, wherein the step of iterating comprises:
- a. using a dedicated circuit to initially define:
- {overscore (C)}(0)(x)=1, {overscore (D)}(0)(x)=1, {overscore (A)}(0)(x)=1, {overscore (B)}(0)(x)=0, {overscore (l)}(0)=0,
- γ(k)=1 if k≦0;
- b. using a dedicated circuit to set k=k+1 if k=d−1, otherwise, defining Δ _ ( k ) = ∑ j = 0 l _ ( k - 1 ) c _ j ( k - 1 ) s k - j ;
- ( 23 )
- c. and using a dedicated circuit to let C _ ( k ) ( x ) = γ ( k - 1 ) C _ ( k - 1 ) ( x ) - Δ _ ( k ) A _ ( k - 1 ) ( x ) · x ( 24 ) D _ ( k ) ( x ) = γ ( k - 1 ) D _ ( k - 1 ) ( x ) - Δ _ ( k ) B _ ( k - 1 ) ( x ) · x 14 ( 25 ) A _ ( k ) ( x ) = { x · A _ ( k - 1 ) ( x ) , if Δ _ ( k ) = 0 or if 2 l _ ( k - 1 ) > k - 1 ( 26 ) C _ ( k - 1 ) ( x ) , if Δ _ ( k ) ≠ 0 and 2 l _ ( k - 1 ) ≤ k - 1 ( 27 ) B _ ( k ) ( x ) = { x · B _ ( k - 1 ) ( x ) , if Δ _ ( k ) = 0 or if 2 l _ ( k - 1 ) > k - 1 ( 28 ) D _ ( k - 1 ) ( x ) , if Δ _ ( k ) ≠ 0 and 2 l _ ( k - 1 ) ≤ k - 1 ( 29 ) l _ ( k ) ( x ) = { l _ ( k - 1 ) , if Δ _ ( k ) = 0 or if 2 l _ ( k - 1 ) > k - 1 ( 30 ) k - l _ ( k - 1 ) , if Δ _ ( k ) ≠ 0 and 2 l _ ( k - 1 ) ≤ k - 1 ( 31 ) γ ( k ) = { γ ( k - 1 ) , if Δ _ ( k ) = 0 or if 2 l _ ( k - 1 ) > k - 1 ( 32 ) Δ _ ( k ) , if Δ _ ( k ) ≠ 0 and 2 l _ ( k - 1 ) ≤ k - 1 ;
- ( 33 )
- and
- d. repeating step (a).
A method for correcting errors in data stored using Reed-Solomon encoding, the method comprising the step of using a dedicated circuit to iterate without performing polynomial division and inverses during iteration, comprising the steps of:
- a. using a dedicated circuit to determine an error locator polynomial according to the equation:
- σ ( x ) = C _ ( d - 1 ) ( x ) β ;
- ( 47 )
- and
- b. using a dedicated circuit to determine an error evaluator polynomial according to the equation:
- P ( x ) = Ω ( x ) - σ ( x ) = D _ ( d - 1 ) ( x ) β - σ ( x ) . ( 48 )
A general purpose computer for correcting errors in data stored using Reed-Solomon encoding, the general purpose computer being configured to solve an error locator polynomial and an error evaluator polynomial by iteration without performing polynomial division and inverses during iteration, wherein the general purpose computer is configured to:
- a. initially define:
- {overscore (C)}(0)(x)=1, {overscore (D)}(0)(x)=1, {overscore (A)}(0)(x)=1, {overscore (B)}(0)(x)=0, {overscore (l)}(0)=0,
- γ(k)=1 if k≦0;
- b. set k=k+1 if k=d−1, otherwise, defining Δ _ ( k ) = ∑ j = 0 l _ ( k - 1 ) c _ j ( k - 1 ) s k - j ;
- ( 23 )
- c. and let C _ ( k ) ( x ) = γ ( k - 1 ) C _ ( k - 1 ) ( x ) - Δ _ ( k ) A _ ( k - 1 ) ( x ) · x ( 24 ) D _ ( k ) ( x ) = γ ( k - 1 ) D _ ( k - 1 ) ( x ) - Δ _ ( k ) B _ ( k - 1 ) ( x ) · x 14 ( 25 ) A _ ( k ) ( x ) = { x · A _ ( k - 1 ) ( x ) , if Δ _ ( k ) = 0 or if 2 l _ ( k - 1 ) > k - 1 C _ ( k - 1 ) ( x ) , if Δ _ ( k ) ≠ 0 and 2 l _ ( k - 1 ) ≤ k - 1 ( 26 ) ( 27 ) B _ ( k ) ( x ) = { x · B _ ( k - 1 ) ( x ) , if Δ _ ( k ) = 0 or if 2 l _ ( k - 1 ) > k - 1 D _ ( k - 1 ) ( x ) , if Δ _ ( k ) ≠ 0 and 2 l _ ( k - 1 ) ≤ k - 1 ( 28 ) ( 29 ) l _ ( k ) ( x ) = { l _ ( k - 1 ) , if Δ _ ( k ) = 0 or if 2 l _ ( k - 1 ) > k - 1 k - l _ ( k - 1 ) ( x ) , if Δ _ ( k ) ≠ 0 and 2 l _ ( k - 1 ) ≤ k - 1 ( 30 ) ( 31 ) γ ( k ) = { γ ( k - 1 ) , if Δ _ ( k ) = 0 or if 2 l _ ( k - 1 ) > k - 1 Δ _ ( k ) , if Δ _ ( k ) ≠ 0 and 2 l _ ( k - 1 ) ≤ k - 1 ;
- ( 32 ) ( 33 )
- and
- d. repeat step (a).
A general purpose computer for correcting errors in data stored using Reed-Solomon encoding, the general purpose computer being configured to solve an error locator polynomial and an error evaluator polynomial by iteration without performing polynomial division and inverses during iteration, wherein the general purpose computer is configured to:
- a. determine an error locator polynomial according to the equation:
- σ ( x ) = C _ ( d - 1 ) ( x ) β ;
- ( 47 )
- and
- b. determine an error evaluator polynomial according to the equation:
- P ( x ) = Ω ( x ) - σ ( x ) = D _ ( d - 1 ) ( x ) β - σ ( x ) . ( 48 )
A device comprising a dedicated circuit configured to correct errors in data stored using Reed-Solomon encoding, a dedicated circuit configured to solve an error locator polynomial and an error evaluator polynomial by iteration without performing polynomial division and inverses during iteration, and further comprising a dedicated circuit configured to:
- a. initially define:
- {overscore (C)}(0)(x)=1, {overscore (D)}(0)(x)=1, {overscore (A)}(0)(x)=1, {overscore (B)}(0)(x)=0, {overscore (l)}(0)=0,
- γ(k)=1 if k≦0;
- b. set k=k+1 if k=d−1, otherwise, defining Δ _ ( k ) = ∑ j = 0 l _ ( k - 1 ) c _ j ( k - 1 ) s k - j ;
- ( 23 )
- c. and let C _ ( k ) ( x ) = γ ( k - 1 ) C _ ( k - 1 ) ( x ) - Δ _ ( k ) A _ ( k - 1 ) ( x ) · x ( 24 ) D _ ( k ) ( x ) = γ ( k - 1 ) D _ ( k - 1 ) ( x ) - Δ _ ( k ) B _ ( k - 1 ) ( x ) · x ( 25 ) A _ ( k ) ( x ) = { x · A _ ( k - 1 ) ( x ) , if Δ _ ( k ) = 0 or if 2 l _ ( k - 1 ) > k - 1 ( 26 ) C _ ( k - 1 ) ( x ) , if Δ _ ( k ) ≠ 0 and 2 l _ ( k - 1 ) ≤ k - 1 ( 27 ) B _ ( k ) ( x ) = { x · B _ ( k - 1 ) ( x ) , if Δ _ ( k ) = 0 or if 2 l _ ( k - 1 ) > k - 1 ( 28 ) D _ ( k - 1 ) ( x ) , if Δ _ ( k ) ≠ 0 and 2 l _ ( k - 1 ) ≤ k - 1 ( 29 ) l _ ( k ) ( x ) = { l _ ( k - 1 ) , if Δ _ ( k ) = 0 or if 2 l _ ( k - 1 ) > k - 1 ( 30 ) k - l _ ( k - 1 ) , if Δ _ ( k ) ≠ 0 and 2 l _ ( k - 1 ) ≤ k - 1 ( 31 ) γ ( k ) = { γ ( k - 1 ) , if Δ _ ( k ) = 0 or if 2 l _ ( k - 1 ) > k - 1 ( 32 ) , ( 33 ) Δ _ ( k ) , if Δ _ ( k ) ≠ 0 and 2 l _ ( k - 1 ) ≤ k - 1 ;
-
- and
- d. repeat step (a).
A device comprising a dedicated circuit configured to correct errors in data stored using Reed-Solomon encoding, a dedicated circuit configured to solve an error locator polynomial and an error evaluator polynomial by iteration without performing polynomial division and inverses during iteration, and further comprising a dedicated circuit configured to:
- a. determine an error locator polynomial according to the equation:
- σ ( x ) = C _ ( d - 1 ) ( x ) β ;
- ( 47 )
- and
- b. determine an error evaluator polynomial according to the equation:
- P ( x ) = Ω ( x ) - σ ( x ) = D _ ( d - 1 ) ( x ) β - σ ( x ) . ( 48 )
Dependencies are inferred from the claim text.