US5446743A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Coefficient updating method and apparatus for Reed-Solomon decoder
Assignee: Cirrus Logic Inc
•
Filing: 1994-10-18
•
Granted: 1995-08-29
•
Expires: 2014-10-18
Abstract
Abstract A Reed-Solomon decoder (199) processes a codeword containing n m-bit symbols to determine coefficients of an error locator polynomial σ(x), and thereafter generates an error evaluator polynomial ω(x). The decoder comprises a bank (B103) of syndrome registers (103) for storing syndrome values; a bank (B101) of error locator registers (101) for accumulating therein coefficients of an error locator polynomial σ(x); and, a bank (B102) of intermediate registers (102) for accumulating therein coefficients of an intermediate polynomial τ(x). The decoder (199) further includes a register update circuit (50) which, for a given codeword, conducts two-phased error locator iterations in order to update values in the error locator registers and the intermediate registers. In contrast to prior art techniques, the register update circuit (50) of the present invention updates coefficients of the intermediate polynomial τ(x) during the first phase of each error locator iteration, and updates coefficients of the error locator polynomial σ(x) during the second phase of each error locator iteration. In further contrast, the decoder (199) of the present invention requires only one bank of error locator registers (101) and one bank of intermediate registers (102) and facilitates serial data shifting rather than parallel data transfer, thereby reducing circuit real estate.
Inventors
- 👤 Christopher P. Zook
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 14:50
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1004; H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15; H03M13/151; H03M13/35
Claims Analysis
Total Claims: 43
Claim 1
Independent Claim
373 words
A decoder for generating electrical signals indicative of coefficients of an error locator polynomial for a codeword by conducting a plurality of error locator iterations, each error locator iteration having two phases, wherein the decoder comprises: first circuit means for updating, during the first phase of each iteration, electrical signals stored in a bank of intermediate registers, the electrical signals stored in the bank of intermediate registers representing values of updated coefficients of an intermediate polynomial τ n (x), said first circuit means utilizing: electrical signals representing an inverse of a prior discrepancy d.sub.(n-1) -1 generated during a directly preceding error locator iteration, and electrical signals representing values of updated coefficients of the error locator polynomial σ n (x) as updated during the directly preceding error locator iteration for all error locator iterations after a first error locator iteration; second circuit means for generating, during the first phase of each error locator iteration, electrical signals representing a current discrepancy d n , the second circuit means utilizing the electrical signals representing coefficients of the error locator polynomial σ n (x) as updated during the directly preceding error locator iteration for all error locator iterations after the first error locator iteration; an inversion circuit for generating electrical signals representing an inverse d n -1 of the current discrepancy during an error locator iteration, which inverse d n -1 becomes the inverse of the prior discrepancy d n-1 -1 during a directly succeeding error locator iteration; and third circuit means connected to said first and said second circuit means for generating, during the second phase of each error locator iteration, electrical signals representing coefficients of the error locator polynomial σ n+1 (x), the third circuit means utilizing: the electrical signals representing the coefficients of the error locator polynomial σ n (x) as updated during the directly preceding error locator iteration, the electrical signals representing the current discrepancy d n , and the electrical signals representing the coefficients of the intermediate polynomial τ n (x) as updated during the first phase; whereby, at the conclusion of a final error locator iteration for the codeword, electrical signals representing final values for the coefficients of the error locator polynomial are stored in the bank of error locator registers.
Claim 2
Dependent Claim
373 words
A decoder for generating electrical signals indicative of coefficients of an error locator polynomial for a codeword by conducting a plurality of error locator iterations, each error locator iteration having two phases, wherein the decoder comprises: first circuit means for updating, during the first phase of each iteration, electrical signals stored in a bank of intermediate registers, the electrical signals stored in the bank of intermediate registers representing values of updated coefficients of an intermediate polynomial τ n (x), said first circuit means utilizing: electrical signals representing an inverse of a prior discrepancy d.sub.(n-1) -1 generated during a directly preceding error locator iteration, and electrical signals representing values of updated coefficients of the error locator polynomial σ n (x) as updated during the directly preceding error locator iteration for all error locator iterations after a first error locator iteration; second circuit means for generating, during the first phase of each error locator iteration, electrical signals representing a current discrepancy d n , the second circuit means utilizing the electrical signals representing coefficients of the error locator polynomial σ n (x) as updated during the directly preceding error locator iteration for all error locator iterations after the first error locator iteration; an inversion circuit for generating electrical signals representing an inverse d n -1 of the current discrepancy during an error locator iteration, which inverse d n -1 becomes the inverse of the prior discrepancy d n-1 -1 during a directly succeeding error locator iteration; and third circuit means connected to said first and said second circuit means for generating, during the second phase of each error locator iteration, electrical signals representing coefficients of the error locator polynomial σ n+1 (x), the third circuit means utilizing: the electrical signals representing the coefficients of the error locator polynomial σ n (x) as updated during the directly preceding error locator iteration, the electrical signals representing the current discrepancy d n , and the electrical signals representing the coefficients of the intermediate polynomial τ n (x) as updated during the first phase; whereby, at the conclusion of a final error locator iteration for the codeword, electrical signals representing final values for the coefficients of the error locator polynomial are stored in the bank of error locator registers.
Claim 3
Dependent Claim
223 words
An error decoder which executes a plurality of iterations including at least a first iteration and a second iteration of a Reed-Solomon decoding procedure to obtain coefficients of an error locator polynomial, each iteration including a first phase and a second phase, the decoder comprising: a bank of syndrome registers for storing syndrome values at least during the first phase of each iteration; a bank of error locator registers for accumulating therein, during the second phase of the second iteration, updated values for coefficients of the error locator polynomial, the bank of error locator registers having stored therein, during the first phase of the second iteration, values for the coefficients obtained during the second phase of the first iteration; a bank of intermediate registers for accumulating therein, during the first phase of the second iteration, updated values for coefficients of an intermediate polynomial and for storing the updated values for the coefficients of the intermediate polynomial during the second phase of the second iteration; a register update circuit which, during the first phase of the second iteration, accumulates the updated values for the coefficients of the intermediate polynomial in the bank of intermediate registers and which, during the second phase of the second iteration, accumulates the updated values for the coefficients of the error locator polynomial in the bank of error locator registers.
Claim 4
Dependent Claim
223 words
An error decoder which executes a plurality of iterations including at least a first iteration and a second iteration of a Reed-Solomon decoding procedure to obtain coefficients of an error locator polynomial, each iteration including a first phase and a second phase, the decoder comprising: a bank of syndrome registers for storing syndrome values at least during the first phase of each iteration; a bank of error locator registers for accumulating therein, during the second phase of the second iteration, updated values for coefficients of the error locator polynomial, the bank of error locator registers having stored therein, during the first phase of the second iteration, values for the coefficients obtained during the second phase of the first iteration; a bank of intermediate registers for accumulating therein, during the first phase of the second iteration, updated values for coefficients of an intermediate polynomial and for storing the updated values for the coefficients of the intermediate polynomial during the second phase of the second iteration; a register update circuit which, during the first phase of the second iteration, accumulates the updated values for the coefficients of the intermediate polynomial in the bank of intermediate registers and which, during the second phase of the second iteration, accumulates the updated values for the coefficients of the error locator polynomial in the bank of error locator registers.
Claim 5
Dependent Claim
65 words
The decoder of claim 2, wherein the syndrome values are stored in a alpha basis representation in the bank of syndrome registers, wherein the coefficients of the error locator polynomial are accumulated/stored in a beta basis representation in the bank of error locator registers, and wherein the coefficients of the intermediate polynomial are accumulated/stored in a beta basis representation in the bank of intermediate registers.
Claim 6
Dependent Claim
154 words
The decoder of claim 2, wherein the bank of syndrome registers comprises a plurality of syndrome registers, the bank of error locator registers comprises a plurality of error locator registers, and the bank of intermediate registers comprises a plurality of intermediate registers, each syndrome register being paired with one of the error locator registers to form a syndrome/locator register pair and each intermediate register being paired with one of the error locator registers to form an intermediate/locator register pair; and wherein the register update circuit further comprises: a discrepancy determination circuit which adds multiplicative products to obtain a discrepancy value d n-1 during a first phase of a n-1 th iteration and a discrepancy value d n during a first phase of a n th iteration, each multiplicative product being derived from values in a corresponding syndrome/locator register pair; and a discrepancy inversion circuit for determining d n-1 -1 during the n-1 th iteration.
Claim 7
Dependent Claim
95 words
The decoder of claim 4, wherein the discrepancy inversion circuit for determining d n-1 -1 determines d n-1 -1 in the alpha basis representation, and wherein the register update circuit further comprises: a conversion circuit for converting d n from a beta basis representation to a alpha basis representation; a discrepancy register for selectively storing one of d n in the alpha basis representation and d n-1 -1 in the alpha basis representation; and, a multiplier feedback circuit connected to the discrepancy register for repetitively multiplying the value in the discrepancy register by a constant.
Claim 8
Dependent Claim
20 words
The decoder of claim 5, wherein the discrepancy register selectively stores an electrical signal corresponding to an erasure pointer value.
Claim 9
Dependent Claim
45 words
The decoder of claim 4, wherein, during the first phase of the n th iteration, the register update circuit optionally utilizes d n-1 -1 and the values then stored in the bank of error locator register for accumulating the updated values for the intermediate registers.
Claim 10
Dependent Claim
48 words
The decoder of claim 4, wherein, during the second phase of the n th iteration, the register update circuit accumulates the updated values for the coefficients of the error locator polynomial by using the discrepancy value d n and values then stored in the bank of intermediate registers.
Claim 11
Dependent Claim
43 words
The decoder of claim 4, wherein each multiplicative product is a product of a value in a first of the registers in the syndrome/locator register pair and a multiple of a value in a second of the registers in the syndrome/locator register pair.
Claim 12
Dependent Claim
36 words
The decoder of claim 9, wherein the first of the registers is an error locator register of the syndrome/locator register pair and the second of the registers is a syndrome register of the syndrome/locator register pair.
Claim 13
Dependent Claim
91 words
The decoder of claim 10, further comprising: a bank of modified syndrome registers comprising a plurality of syndrome registers connected in paired relationship to a corresponding syndrome register in the bank of syndrome registers, each modified syndrome register being connected to receive a syndrome value from the corresponding syndrome register with which the modified syndrome register is in paired relationship; and a multiplier feedback circuit connected to each modified syndrome register for repetitively multiplying the value in the modified syndrome register by a constant for use in obtaining the multiplicative product.
Claim 14
Dependent Claim
44 words
The decoder of claim 9, wherein each multiplicative product is a product of a value in a first of the registers in the syndrome/locator register pair and an α multiple of a value in a second of the registers in the syndrome/locator register pair.
Claim 15
Dependent Claim
65 words
The decoder of claim 4, wherein the syndrome values are stored in a alpha basis representation in the bank of syndrome registers, wherein the coefficients of the error locator polynomial are accumulated/stored in a beta basis representation in the bank of error locator registers, and wherein the coefficients of the intermediate polynomial are accumulated/stored in a beta basis representation in the bank of intermediate registers.
Claim 16
Dependent Claim
39 words
The decoder of claim 2, wherein there is only one bank of error locator registers for storing the coefficients of the error locator polynomial and only one bank of intermediate registers for storing the coefficients of the intermediate polynomial.
Claim 17
Dependent Claim
190 words
A Reed-Solomon decoder comprising: a bank of syndrome registers for storing syndrome values; a bank of error locator registers for accumulating therein coefficients of an error locator polynomial; a bank of intermediate registers for accumulating therein coefficients of an intermediate polynomial; an iterative register update circuit comprising: a discrepancy determination circuit which adds multiplicative products to obtain a current discrepancy d n during an n th iteration, each multiplicative product being derived from values stored in paired ones of the syndrome registers and the error locator registers; a discrepancy inversion circuit which determines an inverse d n -1 of the discrepancy; an updating multiplier circuit which, during the n th iteration, selectively multiplies a value derived from an inverse d n-1 -1 of the discrepancy of a prior iteration n-1 by the coefficients in the error locator register to obtain values for use in updating the coefficients stored in the intermediate registers and which, after the intermediate registers are updated, multiplies a value derived from the current discrepancy d n by the coefficients in the intermediate registers to obtain values for updating the coefficients stored in the error locator registers.
Claim 18
Dependent Claim
190 words
A Reed-Solomon decoder comprising: a bank of syndrome registers for storing syndrome values; a bank of error locator registers for accumulating therein coefficients of an error locator polynomial; a bank of intermediate registers for accumulating therein coefficients of an intermediate polynomial; an iterative register update circuit comprising: a discrepancy determination circuit which adds multiplicative products to obtain a current discrepancy d n during an n th iteration, each multiplicative product being derived from values stored in paired ones of the syndrome registers and the error locator registers; a discrepancy inversion circuit which determines an inverse d n -1 of the discrepancy; an updating multiplier circuit which, during the n th iteration, selectively multiplies a value derived from an inverse d n-1 -1 of the discrepancy of a prior iteration n-1 by the coefficients in the error locator register to obtain values for use in updating the coefficients stored in the intermediate registers and which, after the intermediate registers are updated, multiplies a value derived from the current discrepancy d n by the coefficients in the intermediate registers to obtain values for updating the coefficients stored in the error locator registers.
Claim 19
Dependent Claim
65 words
The decoder of claim 15, wherein the syndrome values are stored in a alpha basis representation in the bank of syndrome registers, wherein the coefficients of the error locator polynomial are accumulated in a beta basis representation in the bank of error locator registers, and wherein the coefficients of the intermediate polynomial are accumulated in a beta basis representation in the bank of intermediate registers.
Claim 20
Dependent Claim
28 words
The decoder of claim 15, wherein the discrepancy inversion circuit which determines the inverse of the discrepancy determines the inverse of the discrepancy in the alpha basis representation.
Claim 21
Dependent Claim
29 words
The decoder of claim 15, wherein the register update circuit further comprises a conversion circuit for converting d n from a beta basis representation to a alpha basis representation.
Claim 22
Dependent Claim
60 words
The decoder of claim 18, wherein the register update circuit further comprises: a discrepancy register for selectively storing one of the discrepancy in the alpha basis representation and the inverse of the discrepancy in the alpha basis representation; and, a multiplier feedback circuit connected to the discrepancy register for repetitively multiplying the value in the discrepancy register by a constant.
Claim 23
Dependent Claim
43 words
The decoder of claim 15, wherein each multiplicative product is a product of a value in a first of the registers in a syndrome/locator register pair and a multiple of a value in a second of the registers in the syndrome/locator register pair.
Claim 24
Dependent Claim
36 words
The decoder of claim 20, wherein the first of the registers is an error locator register of the syndrome/locator register pair and the second of the registers is a syndrome register of the syndrome/locator register pair.
Claim 25
Dependent Claim
91 words
The decoder of claim 21, further comprising: a bank of modified syndrome registers comprising a plurality of syndrome registers connected in paired relationship to a corresponding syndrome register in the bank of syndrome registers, each modified syndromes register being connected to receive a syndrome value from the corresponding syndrome register with which the modified syndrome register is in paired relationship; and a multiplier feedback circuit connected to each modified syndrome register for repetitively multiplying the value in the modified syndrome register by a constant for use in obtaining the multiplicative product.
Claim 26
Dependent Claim
44 words
The decoder of claim 15, wherein each multiplicative product is a product of a value in a first of the registers in the syndrome/locator register pair and an α multiple of a value in a second of the registers in the syndrome/locator register pair.
Claim 27
Dependent Claim
39 words
The decoder of claim 15, wherein there is only one bank of error locator registers for storing the coefficients of the error locator polynomial and only one bank of intermediate registers for storing the coefficients of the intermediate polynomial.
Claim 28
Dependent Claim
38 words
The decoder of claim 15, wherein the multiplier selectively multiplies either the coefficients in the error locator registers or the coefficients in the intermediate registers by a selected one of the discrepancy or the inverse of the discrepancy.
Claim 29
Dependent Claim
112 words
A slice of an error correction circuit for a Reed-Solomon decoder, the slice comprising: an error locator register for storing therein a coefficient for an error locator polynomial; an intermediate register for storing therein a coefficient for an intermediate polynomial; an updating multiplier circuit which selectively multiplies the coefficient in the error locator register by a first input value to obtain a coefficient for inputting to a first neighboring slice and which, after the intermediate register is updated with a coefficient from a second neighboring slice, multiplies a second input value by the coefficient in the intermediate register to obtain a value for updating the coefficient stored in the error locator register.
Claim 30
Dependent Claim
112 words
A slice of an error correction circuit for a Reed-Solomon decoder, the slice comprising: an error locator register for storing therein a coefficient for an error locator polynomial; an intermediate register for storing therein a coefficient for an intermediate polynomial; an updating multiplier circuit which selectively multiplies the coefficient in the error locator register by a first input value to obtain a coefficient for inputting to a first neighboring slice and which, after the intermediate register is updated with a coefficient from a second neighboring slice, multiplies a second input value by the coefficient in the intermediate register to obtain a value for updating the coefficient stored in the error locator register.
Claim 31
Dependent Claim
44 words
The slice of claim 26, wherein the coefficient of the error locator polynomial is stored in a beta basis representation in the error locator register, and wherein the coefficient of the intermediate polynomial is stored in a beta basis representation in the intermediate register.
Claim 32
Dependent Claim
29 words
The slice of claim 26, further comprising: a syndrome register; a discrepancy-yielding multiplier which multiplies terms derived from values stored in the syndrome register and the error locator register.
Claim 33
Dependent Claim
27 words
The slice of claim 28, wherein the discrepancy-yielding multiplier multiplies a value in the error locator register and a multiple of a value in the syndrome register.
Claim 34
Dependent Claim
58 words
The slice of claim 29, further comprising: a modified syndrome register connected to receive a syndrome value from the syndrome register; and a multiplier feedback circuit connected to the modified syndrome register for repetitively multiplying the value in the modified syndrome register by a constant, an output of the modified syndrome register being connected to the discrepancy-yielding multiplier.
Claim 35
Dependent Claim
43 words
The slice of claim 28, wherein an output of the discrepancy-yielding multiplier is a product of a value in a first of the registers in the slice and an α multiple of a value in a second of the registers in the slice.
Claim 36
Dependent Claim
26 words
The slice of claim 26, wherein the second input value is a discrepancy value and the first input value is an inverse of the discrepancy value.
Claim 37
Dependent Claim
22 words
The slice of claim 32, wherein the discrepancy value and the inverse of the discrepancy value are in the alpha basis representation.
Claim 38
Dependent Claim
41 words
The slice of claim 26, wherein there is only one error locator register in the slice for storing the coefficient of the error locator polynomial and only one intermediate register in the slice for storing the coefficient of the intermediate polynomial.
Claim 39
Dependent Claim
41 words
The slice of claim 26, wherein the updating multiplier selectively multiplies either the coefficient in the error locator register or the coefficient in the intermediate register by a selected one of a discrepancy value or an inverse of the discrepancy value.
Claim 40
Independent Claim
202 words
A method of obtaining an error locator polynomial as part of decoding a Reed-Solomon codeword during a plurality of iterations of a decoder circuit, including at least a prior iteration and a current iteration, each iteration including a first phase and a second phase, the method comprising: loading syndrome values into a bank of syndrome registers and storing the syndrome values in the syndrome registers at least during the first phase of each iteration; storing in a bank of error locator registers, during the first phase of a current iteration, values for coefficients of the error locator polynomial accumulated during a prior iteration; using, during the first phase of a current iteration, the values for the coefficients of the error locator polynomial stored in the bank of error locator registers during the first phase of the current iteration to accumulate updated values for coefficients of an intermediate polynomial, the coefficients of the intermediate polynomial being stored in a bank of intermediate registers; using, during the second phase of the current iteration, the coefficients of the intermediate polynomial then stored in the bank of intermediate registers to accumulate updated values for the coefficients of the error locator polynomial in the error locator registers.
Claim 41
Independent Claim
202 words
A method of obtaining an error locator polynomial as part of decoding a Reed-Solomon codeword during a plurality of iterations of a decoder circuit, including at least a prior iteration and a current iteration, each iteration including a first phase and a second phase, the method comprising: loading syndrome values into a bank of syndrome registers and storing the syndrome values in the syndrome registers at least during the first phase of each iteration; storing in a bank of error locator registers, during the first phase of a current iteration, values for coefficients of the error locator polynomial accumulated during a prior iteration; using, during the first phase of a current iteration, the values for the coefficients of the error locator polynomial stored in the bank of error locator registers during the first phase of the current iteration to accumulate updated values for coefficients of an intermediate polynomial, the coefficients of the intermediate polynomial being stored in a bank of intermediate registers; using, during the second phase of the current iteration, the coefficients of the intermediate polynomial then stored in the bank of intermediate registers to accumulate updated values for the coefficients of the error locator polynomial in the error locator registers.
Claim 42
Independent Claim
262 words
A method of obtaining an error locator polynomial as part of decoding an m-bit Reed-Solomon codeword during m number of iterations of a decoder circuit, including at least a prior iteration and a current iteration, each iteration including a first phase and a second phase, the method comprising: loading m-bit electrical signals indicative of syndrome values into a bank of syndrome registers and storing the syndrome-indicative electrical signals in the syndrome registers at least during the first phase of each iteration; storing in a bank of error locator registers, during the first phase of a current iteration, electrical signals corresponding to values for coefficients of the error locator polynomial accumulated during a prior iteration; using, during the first phase of a current iteration, the electrical signals corresponding to values for the coefficients of the error locator polynomial stored in the bank of error locator registers during the first phase of the current iteration to generate electrical signals corresponding to accumulated updated values for coefficients of an intermediate polynomial, the electrical signals corresponding to coefficients of the intermediate polynomial being stored in a bank of intermediate registers; using, during the second phase of the current iteration, the electrical signals corresponding to the coefficients of the intermediate polynomial then stored in the bank of intermediate registers to generate electrical signals corresponding to accumulated updated values for the coefficients of the error locator polynomial in the error locator registers; using the electrical signals corresponding to accumulated updated values for the coefficients of the error locator polynomial in the error locator registers for correcting the codeword.
Claim 43
Independent Claim
262 words
A method of obtaining an error locator polynomial as part of decoding an m-bit Reed-Solomon codeword during m number of iterations of a decoder circuit, including at least a prior iteration and a current iteration, each iteration including a first phase and a second phase, the method comprising: loading m-bit electrical signals indicative of syndrome values into a bank of syndrome registers and storing the syndrome-indicative electrical signals in the syndrome registers at least during the first phase of each iteration; storing in a bank of error locator registers, during the first phase of a current iteration, electrical signals corresponding to values for coefficients of the error locator polynomial accumulated during a prior iteration; using, during the first phase of a current iteration, the electrical signals corresponding to values for the coefficients of the error locator polynomial stored in the bank of error locator registers during the first phase of the current iteration to generate electrical signals corresponding to accumulated updated values for coefficients of an intermediate polynomial, the electrical signals corresponding to coefficients of the intermediate polynomial being stored in a bank of intermediate registers; using, during the second phase of the current iteration, the electrical signals corresponding to the coefficients of the intermediate polynomial then stored in the bank of intermediate registers to generate electrical signals corresponding to accumulated updated values for the coefficients of the error locator polynomial in the error locator registers; using the electrical signals corresponding to accumulated updated values for the coefficients of the error locator polynomial in the error locator registers for correcting the codeword.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-08-28 | 1999-02-27 | 1999-08-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-08-28 | 2003-02-27 | 2003-08-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-08-28 | 2007-02-27 | 2007-08-29 | $7700.00 | Window Closed / Lapsed |