Multi-code Chien's search circuit for BCH codes with various values of m in GF(2
The present invention discloses a multi-code Chien's search circuit for BCH codes with various values of m in GF(2 m ). The circuit includes: a combined matrix unit, a number of first multiplexers, a number of registers and a number of second multiplexers. By designing the Chien's search circuit having several Chien's search matrices, with peripheral components, it is able to achieve applications for different code rates, different code lengths and even different m in GF(2 m ).
1. A multi-code Chien's search circuit for Bose-Chaudhuri-Hocquenghem (BCH) codes with various exponents (m) in Galois Field (GF) (2 m ), comprising:
a combined matrix unit, for providing a plurality of Chien's search matrices, receiving a plurality of inputted values, multiplying the inputted values by partial or all elements in one or more Chien's search matrix to get first operation values and second operation values, outputting the first operation values, and outputting the second operation values according to different properties of the inputted values via one of a plurality of line groups;
a plurality of first multiplexers, each first multiplexer connected with one line in each line group and receiving specific second operation values, for choosing the second operation values from the corresponding line group according to different properties of the inputted values, and outputting the second operation values;
a plurality of registers, each register connected with a specific first multiplexer, for receiving the second operation values, and outputting the second operation values in a next clock cycle after the plurality of registers receive the second operation values from the plurality of first multiplexers; and
a plurality of second multiplexers, each second multiplexer connected with a specific register, receiving a value of a specific coefficient except a constant coefficient in an error location polynomial and the second operation values from the register, for outputting the value of the specific coefficient as the inputted value to the combined matrix unit in the first iterative operation of Chien's search, and outputting the second operation values to the combined matrix unit as the inputted values in the rest iterative operations of Chien's search,
wherein values of specific coefficients of the error location polynomial for the same Chien's search matrix and the second operation values obtained by processing the values of specific coefficients have the same properties of the inputted values.
2. The Chien's search circuit according to claim 1 , wherein the Chien's search matrix has a form of [A y A Ω ], where
where
A
y
=
[
A
11
A
21
…
A
p
1
A
12
A
22
…
A
p
2
⋮
⋮
⋱
⋮
A
1
t
A
2
t
…
A
pt
]
,
A
Ω
=
[
A
1
p
0
…
0
0
A
2
p
…
0
⋮
⋮
⋱
⋮
0
0
…
A
tp
]
,
and
A
ij
=
[
α
0
ij
α
1
ij
…
α
m
-
1
ij
α
0
ij
+
1
α
1
ij
+
1
…
α
m
-
1
ij
+
1
⋮
⋮
⋱
⋮
α
0
ij
+
m
-
1
α
1
ij
+
m
-
1
…
α
m
-
1
ij
+
m
-
1
]
,
where p is a number of parallel computations that the Chien's search circuit has; t is an error correction ability corresponding to the BCH code; α 0 , α 1 , . . . and α m-1 form a standard basis in GF(2 m ); 1≦i≦p; 1≦j≦t.
3. The Chien's search circuit according to claim 2 , wherein different Chien's search matrices corresponds to different values of m and/or t.
4. The Chien's search circuit according to claim 2 , wherein each Chien's search matrix is equally divided into a plurality of portions in the row direction with the number of portions being the same as the number of the error correction ability of the corresponding BCH code; each portion has sub-matrices in the corresponding A y and A Ω .
5. The Chien's search circuit according to claim 4 , wherein each portion of one Chien's search matrix is aligned with that of another Chien's search matrix sequentially by a method.
6. The Chien's search circuit according to claim 5 , wherein the method is aligning in one side, aligning centrally, or offsetting a certain amount from one side.
7. The Chien's search circuit according to claim 5 , wherein the locations where are not covered by the portions of the Chien's search matrix are set to be elements of 0 in the combined matrix unit.
8. The Chien's search circuit according to claim 5 , wherein the Chien's search matrices are separated by elements of 0.
9. The Chien's search circuit according to claim 1 , wherein there are common sub-expressions in partial elements in two Chien's search matrices and one Chien's search matrix utilizes the common sub-expressions of the other Chien's search matrix.
10. The Chien's search circuit according to claim 1 , wherein the first operation value further adds to a value of a constant coefficient of the error location polynomial; if the sum is 0, the corresponding element, α up+i where 1≦i≦p, is a root of the error location polynomial.