Data processing system and method
View Patent ↗Embodiments of the present invention relate to a data processing system comprising a first arithmetic unit comprising at least one finite field multiplier and at least one finite field adder for selectively performing at least two finite field arithmetic calculations; the data processing system comprising means to use a previous finite field arithmetic calculation result in a current finite field arithmetic calculation to determine at least part of a polynomial.
1. A data processing system for determining at least one of locations and magnitudes of errors in a received code word via respective coefficients of at least part of one of an error-locator polynomial and an error-evaluator polynomial of degree t in at least part of an inversion-free Berlekamp-Massey algorithm, wherein t is an integer, the system comprising:
a plurality of arithmetic units, each arithmetic unit comprising a finite field multiplier circuit and at least one finite field adder circuit, the finite field multiplier circuit having an output coupled to an input of said at least one finite field adder circuit for selectively performing at least two finite field arithmetic calculations between values associated with said received code word presented at two inputs to the finite field multiplier circuit and a further value associated with said received code word presented at two inputs to the finite field adder circuit, one of said inputs to the finite field adder circuit being coupled to the output of the finite field multiplier circuit and the other of said inputs to the finite field adder circuit being adapted to receive further input data, such that the data processing system includes no more than (t+1) finite field multiplier circuits;
memory for storing a previous finite field arithmetic calculation result of a first arithmetic unit of the plurality of arithmetic units for use in a current finite field arithmetic calculation of the first arithmetic unit; and
at least one finite field adder circuit for combining respective finite field arithmetic calculation results of respective current finite field arithmetic calculations of at least two of the arithmetic units.
2. A data processing system as claimed in claim 1 in which a first arithmetic operation of the at least two arithmetic operations comprises a first finite field multiplication operation.
3. A data processing system as claimed in claim 2 in which the first finite field multiplication operation comprises calculating at least a first multiplication of δσ (i−1) (x) in a first clock cycle, where σ (i−1) (x) is an error locator polynomial at step (i−1) and δ is a previous step discrepancy, wherein i is an integer.
4. A data processing system as claimed in claim 3 , wherein the error locator polynomial σ(x) is calculated in 6t clock cycles relative to a start of processing of the received code word.
5. A data processing system as claimed in claim 2 in which the finite field arithmetic operation comprises calculating at least a second multiplication operation of Δ (i) xλ (i−1) (x) in a second clock cycle, where Δ (i) is a step discrepancy at step i and λ (i−1) (x) is an auxiliary polynomial at step (i−1), wherein i is an integer.
6. A data processing system as claimed in claim 1 in which a second arithmetic operation of the at least two arithmetic operations comprises a finite field addition operation.
7. A data processing system as claimed in claim 6 in which the finite arithmetic addition operation comprises calculating at least part of δσ (i−1) (x)+Δ (i) xλ (i−1) (x) as the current finite field arithmetic operation using δσ (i−1) (x) as at least part of the previous finite field arithmetic operation, where σ (i−1) (x) is an error locator polynomial at step (i−1), δ is a previous step discrepancy, Δ (i) is a step discrepancy at step i and λ (i−1) (x) is an auxiliary polynomial at step (i−1).
8. A data processing system as claimed in claim 1 further comprising the plurality of arithmetic units operable substantially in parallel to calculate respective coefficients of at least part of at least a first polynomial.
9. A data processing system as claimed in claim 8 in which the first polynomial comprises at least where δσ (i−1) (x)+Δ (i)xλ (i−1) (x), where σ (i−1) (x) is an error locator polynomial at step (i−1), δ is a previous step discrepancy, Δ (i) is a step discrepancy at step (i−1), δ is a previous step discrepancy, Δ (i) is a step i and λ (i−1) (x) is an auxiliary polynomial at step (i−1).
10. A data processing system as claimed in claim 9 , wherein the error locator polynomial σ(x) is calculated in 6t clock cycles relative to a start of processing of the received code word.
11. A data processing system as claimed in claim 1 in which the at least two arithmetic calculations comprises a second finite field multiplication operation in a third clock cycle.
12. A data processing system as claimed in claim 11 in which the second finite field multiplication operation comprises calculating at least one coefficient of a second polynomial.
13. A data processing system as claimed in claim 11 in which the second arithmetic operation comprises calculating at least S i−j+1 σ j (i) , wherein S i−j+1 is coefficient i−j+1 of a syndrome polynomial and σ j (i) is a coefficient j of an error locator polynomial at step i.
14. A data processing system as claimed in claim 13 in which the second arithmetic operation comprises calculating at least part of Δ (i+1) =S i +1 σ 0 (i) +S i σ 1 (i) + . . . +S i−t+1 σ t (i) , where Δ (i+1) is a step discrepancy at step (i+1) and S i is coefficient i of a syndrome polynomial.
15. A data processing system as claimed in claim 1 comprising at least (t+1) such arithmetic units operable substantially in parallel, each unit producing respective coefficients of at least one of a first polynomial, σ (i) (x)=δσ (i−1) x+Δ (i) xλ (i−1) (x), and a step discrepancy, Δ (i+1) =S i+1 σ 0 (i) +S i σ 1 (i) + . . . +S i−t+1 σ t (i) , where σ (i−1)) (x) is an error locator polynomial at step (i−i), δ is a previous step discrepancy, Δ (i−1) (x) is a step discrepancy at step i, λ (i−1) (x) is an auxiliary polynomial at step (i−1) and S i is coefficient of a syndrome polynomial.
16. A data processing system as claimed in claim 1 in which the first arithmetic unit is arranged to calculate at least a respective part of at least part of a further polynomial.
17. A data processing system as claimed in claim 16 in which the further polynomial is an error evaluator polynomial.
18. A data processing system as claimed in claim 16 in which calculating the further polynomial comprises calculating
Ω
(
x
)
=
S
(
x
)
σ
(
x
)
mod
x
2
t
=
(
S
0
+
S
1
x
+
…
+
S
2
t
-
1
x
2
t
-
1
)
·
(
σ
0
+
σ
1
x
+
…
+
σ
t
x
t
)
mod
x
2
t
=
Ω
0
+
Ω
1
x
+
…
+
Ω
t
-
1
x
t
-
1
,
where
Ω
i
=
S
i
σ
0
+
S
i
-
1
σ
1
+
…
+
S
i
-
t
+
1
σ
t
-
1
,
where
i
=
0
,
1
,
…
,
t
-
1
,
and where Ω(x) is an error evaluator polynomial, s(x) is a syndrome polynomial and σ(x) is an error locator polynomial.
19. A data processing system as claimed in claim 18 wherein Ω(x) is calculated in t clock cycles relative to a start of processing of the received code word.
20. A data processing system as claimed in claim 16 in which the at least a respective part of at least part of the further polynomial comprises calculating:
Ω i =Ω i (t−1) , where
Ω i (j) =S i σ 0 , for j=0; and
Ω i (j) =Ω (j−1) +S i−j σ j , for 1 ≦j≦i,
where Ω i is coefficient i of an error evaluator polynomial Ω(x), S i is coefficient i of a syndrome polynomial S(x) and σ i is coefficient i of an error locator polynomial σ(x).
21. A data processing system as claimed in claim 20 wherein Ω(x) is calculated in t clock cycles relative to a start of processing of the received code word.
22. A data processing system as claimed in claim 1 , further comprising (2t+1) finite field adder circuits.