Apparatus for computing error correction syndromes
First Claim
1. An apparatus, for use in a Reed-Solomon decoder which decodes a codeword containing N received symbols, N being a positive integer, for calculating syndromes Si '"'"'s iteratively in N iterations, according to:
-
space="preserve" listing-type="equation">S.sub.i = . . . (r.sub.N-1 α
.sup.i +r.sub.N-2) α
.sup.i +r.sub.N-3 !α
.sup.i +. . . +r.sub.1 α
.sup.i !+r.sub.0wherein i is an integer ranging from 0 to 2T-1, T being a predetermined number, rN-j represents a jth received symbol which is fed in synchronization with a symbol clock, j being 1 to N, and α
i denotes an ith root of a code generating polynomial, the apparatus comprising L syndrome calculating cells each of which provides K syndromes, each of K and L being a positive integer not larger than 2T, each syndrome calculating cell including;
storage means containing a first set of K memory means, wherein the storage means sequentially provides contents of the first set of K memory means during each iteration and is initialized to 0 prior to a first iteration;
first input means for sequentially providing K consecutive roots of the code generating polynomial during each iteration;
a multiplier of a finite field GF(2m) for sequentially multiplying the K roots of the code generating polynomial provided from the first input means with the contents of the first set of K memory means provided from the storage means, to thereby provide K multiplication results during each iteration; and
an adder on the finite field GF(2m) for adding the jth received symbol rN-j to each of the K multiplication results during each iteration, to thereby provide the K intermediate values to the storage means during a (j1)th iteration, j1 being 1 to (N-1), or provide the K syndromes to the storage means during an Nth iteration.
1 Assignment
0 Petitions
Accused Products
Abstract
A syndrome calculating device, for use in a Reed-Solomon decoder, for calculating syndromes Si '"'"'s iteratively, according to:
S.sub.i ={. . . (r.sub.N-1 α.sup.i +r.sub.N-2) α.sup.i
+rN-3 !αi +. . . +r1 }αi +r0
wherein rN-j represents a jth received symbol which is fed in synchronization with a symbol clock and αi denotes an ith root of a code generating polynomial, comprises a plurality of syndrome calculating cells, each of which including: a memory block containing K registers, wherein the memory block is initialized to 0 prior to a first iteration; a root input block for sequentially providing K roots of the code generating polynomial during each iteration; a multiplier on a finite field GF(2m) for sequentially multiplying the K roots of the code generating polynomial with the contents of the K registers, to thereby provide K multiplication results during each iteration; and an adder on the finite field GF(2m) for adding rN-j to each of the K multiplication results during a jth iteration, to thereby provide the K intermediate values or the K syndromes.
22 Citations
20 Claims
-
1. An apparatus, for use in a Reed-Solomon decoder which decodes a codeword containing N received symbols, N being a positive integer, for calculating syndromes Si '"'"'s iteratively in N iterations, according to:
-
space="preserve" listing-type="equation">S.sub.i = . . . (r.sub.N-1 α
.sup.i +r.sub.N-2) α
.sup.i +r.sub.N-3 !α
.sup.i +. . . +r.sub.1 α
.sup.i !+r.sub.0wherein i is an integer ranging from 0 to 2T-1, T being a predetermined number, rN-j represents a jth received symbol which is fed in synchronization with a symbol clock, j being 1 to N, and α
i denotes an ith root of a code generating polynomial, the apparatus comprising L syndrome calculating cells each of which provides K syndromes, each of K and L being a positive integer not larger than 2T, each syndrome calculating cell including;storage means containing a first set of K memory means, wherein the storage means sequentially provides contents of the first set of K memory means during each iteration and is initialized to 0 prior to a first iteration; first input means for sequentially providing K consecutive roots of the code generating polynomial during each iteration; a multiplier of a finite field GF(2m) for sequentially multiplying the K roots of the code generating polynomial provided from the first input means with the contents of the first set of K memory means provided from the storage means, to thereby provide K multiplication results during each iteration; and an adder on the finite field GF(2m) for adding the jth received symbol rN-j to each of the K multiplication results during each iteration, to thereby provide the K intermediate values to the storage means during a (j1)th iteration, j1 being 1 to (N-1), or provide the K syndromes to the storage means during an Nth iteration. - View Dependent Claims (2, 3, 4)
-
-
5. An apparatus, for use in a Reed-Solomon decoder which decodes a codeword containing N received symbols, N being a positive integer, for calculating syndromes Si '"'"'s iteratively in N iterations, according to:
-
space="preserve" listing-type="equation">S.sub.i = . . . (r.sub.N-1 α
.sup.i +r.sub.N-2) α
.sup.i +r.sub.N-3 !α
.sup.i +. . . +r.sub.1 α
.sup.i !+r.sub.0wherein i is an integer ranging from 0 to 2T-1T being a predetermined number, rN-j represents a jth received symbol which is fed in synchronization with a symbol clock, j being 1 to N, and α
i denotes an ith root of a code generating polynomial, the apparatus comprising L syndrome calculating cells each of which provides K syndromes, each of K and L being a positive integer not larger than 2T, each syndrome calculating cell including;storage means containing a first set of K memory means, wherein the storage means sequentially provides contents of the first set of K memory means during each iteration and is initialized to 0 prior to a first iteration; first input means for sequentially providing K roots of the code generating polynomial during each iteration; a multiplier of a finite field GF(2m) for sequentially multiplying the K roots of the code generating polynomial provided from the first input means with the contents of the first set of K memory means provided from the storage means, to thereby provide K multiplication results during each iteration; and an adder on the finite field GF(2m) for adding the jth received symbol rN-j to each of the K multiplication results during each iteration, to thereby provide the K intermediate values to the storage means during a (j1)th iteration, j1 being 1 to (N-1), or provide the K syndromes to the storage means during an Nth iteration, wherein the storage means further contains; means for providing each of the K intermediate values of the K syndromes provided from the adder to each of the first set of K memory means to be stored therein; and converting means for sequentially providing the contents of the first set of K memory means. - View Dependent Claims (6, 7, 8, 9, 10)
-
-
11. An apparatus, for use in a Reed-Solomon decoder which decodes a codeword containing N received symbols, N being a positive integer, for calculating syndromes Si '"'"'s iteratively in N iterations, according to:
-
space="preserve" listing-type="equation">S.sub.i = . . . (r.sub.N-1 α
.sup.i +r.sub.N-2) α
.sup.i +r.sub.N-3 !α
.sup.i +. . . +r.sub.1 α
.sup.i !+r.sub.0wherein i is an integer ranging from 0 to 2T-1, T being a predetermined number, rN-j represents a jth received symbol which is fed in synchronization with a symbol clock, j being 1 to N, and α
i denotes an ith root of a code generating polynomial, the apparatus comprising L syndrome calculating cells each of which provides K syndromes, each of K and L being a positive integer not larger than 2T, each syndrome calculating cell including;storage means containing a first set of K memory means, wherein the storage means sequentially provides contents of the first set of K memory means during each iteration and is initialized to 0 prior to a first iteration; first input means for sequentially providing K roots of the code generating polynomial during each iteration; a multiplier of a finite field GF(2m) for sequentially multiplying the K roots of the code generating polynomial provided from the first input means with the contents of the first set of K memory means provided from the storage means, to thereby provide K multiplication results during each iteration; and an adder on the finite field GF(2m) for adding the jth received symbol rN-j to each of the K multiplication results during each iteration, to thereby provide the K intermediate values to the storage means during a (j1)th iteration, j1 being 1 to (N-1). or provide the K syndromes to the storage means during an Nth iteration, wherein the first input means contains; a memory for storing the K roots of the code generating polynomial; and a selection means for sequentially providing the K roots of the code generating polynomial stored at the memory during each iteration. - View Dependent Claims (12, 13)
-
- 14. An apparatus, for use in a Reed-Solomon decoder which decodes a codeword containing N received symbols, N being a positive integer, for calculating syndromes Si '"'"'s iteratively in N iterations, according to
- space="preserve" listing-type="equation">S.sub.i ={. . . (r.sub.N-1 α
.sup.i +r.sub.N-2)α
.sup.i +r.sub.N-3 !α
.sup.i +. . . +r.sub.1 }α
.sup.i +r.sub.0
wherein i is an integer ranging from 0 to 2T-1, T being a predetermined number, rN-j represents a jth received symbol which is fed in synchronization with a symbol clock, j being 1 to N, and α
i denotes an ith root of a code generating polynomial, the apparatus comprising L syndrome calculating cells each of which provides K syndromes, each of L and K being a positive integer not larger than 2T, each syndrome calculating cell including;first storage means containing a first set of K memory means, wherein the first storage means sequentially provides contents of the first set of K memory means during each iteration, and the first set of K memory means is initialized to 0 prior to a first iteration; second storage means containing a second set of K memory means, wherein the second storage means sequentially provides contents of the second set of K memory means during each iteration; first selection means for sequentially providing the contents of the first set of K memory means provided from the first storage means during a (j1)th iteration, j1 being an integer ranging from 1 to (N-1), and sequentially providing the contents of the second set of K memory means provided from the second storage means during an Nth iteration; first input means for sequentially providing K roots of the code generating polynomial during each iteration; a multiplier on a finite field GF(2m) for sequentially multiplying the K roots of the code generating polynomial provided from the first input means with the contents of the first or second set of K memory means provided from the first selection means, to thereby provide K multiplication results during each iteration; and an adder on the finite field GF(2m) for adding the jth received symbol rN-j to each of the K multiplication results during a jth iteration, to thereby provide the K intermediate values to the first and the second storage means during the (j1)th iteration, j1 being 1 to (N-1), and provide the K syndromes to the first and the second storage means during the Nth iteration. - View Dependent Claims (15, 16, 17, 18, 19, 20)
- space="preserve" listing-type="equation">S.sub.i ={. . . (r.sub.N-1 α
Specification