US 7,689,893 B1 · Iterative reed-solomon error-correction decoding

Abstract

Systems and methods are provided to correct errors occurring in a decision-codeword that is generated by a detector. A decoder determines whether errors in the decision-codeword are of a degree that exceeds the correction capability of a Reed-Solomon error-correction code. If they are, the decoder iteratively modifies the decision-codeword to reduce the number of errors therein. In each iteration, the decoder generates an error indicator using one or more error indicators from a previous iteration and uses the error indicator to perform error detection and correction operations.

Claims24

Dependent claims

A method of correcting errors in a decision-codeword by employing a Reed Solomon error-correction code RS(n,k) having a correction capability t=(n−k)/2, the method comprising:

determining whether errors in the decision-codeword are of a degree that exceeds a Reed Solomon error-correction code's correction capability, by using an error indicator for the decision-codeword;
modifying the decision-codeword to produce a modified decision-codeword if the degree of the errors exceeds the correction capability;
and
generating an error indicator for the modified decision-codeword using the error indicator for the decision-codeword.

1 more element

A method of correcting errors in a decision-codeword by employing a Reed Solomon error-correction code RS(n,k) having a correction capability t=(n−k)/2 and generating an error indicator for a modified decision-codeword using an error indicator for the decision-codeword, the method comprising:

computing quotient polynomials QΛ, QxΛ, QB, QxB, Qx2B;
computing remainder polynomials rΛ, rxΛ, rB, rxB, rx2B;
computing quantities d1, d2, and d3, where
d
1
=
⁢
∑
i
=
0
t
⁢
⁢
[
S
n
-
k
-
i
(
e
l
)
⁡
(
Q
Λ
)
i
]
,
d
2
=
⁢
∑
i
=
0
t
⁢
⁢
[
S
n
-
k
-
i
(
e
l
)
⁡
(
Q
x
⁢
⁢
Λ
)
i
]
,
⁢
and
d
3
=
⁢
∑
i
=
0
t
⁢
⁢
[
S
n
-
k
-
i
(
e
l
)
⁡
(
Q
x
⁢
⁢
B
)
i
]
;
⁢
computing a quantity D=determinant
[
r
x
⁢
⁢
Λ
r
xB
d
2
d
3
]
;
and
computing quantities a, b, and c, where
a
=
⁢
(
r
Λ
⁢
d
3
+
r
xB
⁢
d
1
)
⁢
D
-
1
,
b
=
⁢
{
(
d
1
+
ad
2
)
⁢
d
3
-
1
⁢
⁢
if
⁢
⁢
d
3
≠
0
(
r
Λ
+
ar
x
⁢
⁢
Λ
)
⁢
r
xB
-
1
⁢
⁢
otherwise
;
⁢
and
c
=
⁢
r
Λ
⁢
r
B
-
1
.

194 more elements

A system for correcting errors in a decision-codeword by employing a Reed Solomon error-correction code RS(n,k) having a correction capability t=(n−k)/2 and having means for generating an error indicator for a modified decision-codeword using an error indicator for the decision-codeword, the method comprising:

means for computing quotient polynomials QΛ, QxΛ, QB, QxB, Qx2B;
means for computing remainder polynomials rΛ, rxΛ, rB, rxB, rx2B;
means for computing quantities d1, d2, and d3, where
d
1
=
⁢
∑
i
=
0
t
⁢
⁢
[
S
n
-
k
-
i
(
e
l
)
⁡
(
Q
Λ
)
i
]
,
d
2
=
⁢
∑
i
=
0
t
⁢
⁢
[
S
n
-
k
-
i
(
e
l
)
⁡
(
Q
x
⁢
⁢
Λ
)
i
]
,
⁢
and
d
3
=
⁢
∑
i
=
0
t
⁢
⁢
[
S
n
-
k
-
i
(
e
l
)
⁡
(
Q
x
⁢
⁢
B
)
i
]
;
⁢
means for computing a quantity
D
=
determinant
⁡
[
r
x
⁢
⁢
Λ
r
xB
d
2
d
3
]
;
and
means for computing quantities a, b, and c, where
a
=
⁢
(
r
Λ
⁢
d
3
+
r
xB
⁢
d
1
)
⁢
D
-
1
,
b
=
⁢
{
(
d
1
+
ad
2
)
⁢
d
3
-
1
⁢
⁢
if
⁢
⁢
d
3
≠
0
(
r
Λ
+
ar
x
⁢
⁢
Λ
)
⁢
r
xB
-
1
⁢
⁢
otherwise
;
⁢
and
c
=
⁢
r
Λ
⁢
r
B
-
1
.

198 more elements

A system for correcting errors in a decision-codeword by employing a Reed Solomon error-correction code RS(n,k) having a correction capability t=(n−k)/2, in which an error indicator generation circuit that generates an error indicator for a modified decision-codeword using an error indicator for the decision-codeword, the error indicator generation circuit comprising:

a quotient computation circuit that computes quotient polynomials QΛ, QxΛ, QB, QxB, Qx2B;
a remainder computation circuit that computes remainder polynomials rΛ, rxΛ, rB, rxB, rx2B;
a circuit that computes quantities d1, d2, and d3, where
d
1
=
⁢
∑
i
=
0
t
⁢
⁢
[
S
n
-
k
-
i
(
e
l
)
⁡
(
Q
Λ
)
i
]
,
d
2
=
⁢
∑
i
=
0
t
⁢
⁢
[
S
n
-
k
-
i
(
e
l
)
⁡
(
Q
x
⁢
⁢
Λ
)
i
]
,
⁢
and
d
3
=
⁢
∑
i
=
0
t
⁢
⁢
[
S
n
-
k
-
i
(
e
l
)
⁡
(
Q
x
⁢
⁢
B
)
i
]
;
⁢
a determinant computation circuit that computes a quantity
D
=
determinant
⁡
[
r
x
⁢
⁢
Λ
r
xB
d
2
d
3
]
;
and
a circuit that computes quantities a, b, and c, where
a
=
⁢
(
r
Λ
⁢
d
3
+
r
xB
⁢
d
1
)
⁢
D
-
1
,
b
=
⁢
{
(
d
1
+
ad
2
)
⁢
d
3
-
1
⁢
⁢
if
⁢
⁢
d
3
≠
0
(
r
Λ
+
ar
x
⁢
⁢
Λ
)
⁢
r
xB
-
1
⁢
⁢
otherwise
;
⁢
and
c
=
⁢
r
Λ
⁢
r
B
-
1
.

198 more elements

Dependencies are inferred from the claim text.

Facts

Application

11/956,861Filed 14 Dec 2007 · continuation

Priority

13 Apr 2004

Granted

30 Mar 2010

Term ends

Not estimatedThe source records don’t support an estimate.

Classification7 codes

H03M 13/15
Linear codes: cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial,…
H03M 13/1515
Using error location or error correction polynomials: reed-Solomon codes
H03M 13/153
Determination and particular use of error location polynomials: using the Berlekamp-Massey algorithm
H03M 13/1545
Using error location or error correction polynomials: determination of error locations, e.g. Chien search or other methods or arrangements for the…

Abstract

Claims24

Dependent claims

A method of correcting errors in a decision-codeword by employing a Reed Solomon error-correction code RS(n,k) having a correction capability t=(n−k)/2, the method comprising:

determining whether errors in the decision-codeword are of a degree that exceeds a Reed Solomon error-correction code's correction capability, by using an error indicator for the decision-codeword;
modifying the decision-codeword to produce a modified decision-codeword if the degree of the errors exceeds the correction capability;
and
generating an error indicator for the modified decision-codeword using the error indicator for the decision-codeword.

1 more element

computing quotient polynomials QΛ, QxΛ, QB, QxB, Qx2B;
computing remainder polynomials rΛ, rxΛ, rB, rxB, rx2B;
computing quantities d1, d2, and d3, where
d
1
=
⁢
∑
i
=
0
t
⁢
⁢
[
S
n
-
k
-
i
(
e
l
)
⁡
(
Q
Λ
)
i
]
,
d
2
=
⁢
∑
i
=
0
t
⁢
⁢
[
S
n
-
k
-
i
(
e
l
)
⁡
(
Q
x
⁢
⁢
Λ
)
i
]
,
⁢
and
d
3
=
⁢
∑
i
=
0
t
⁢
⁢
[
S
n
-
k
-
i
(
e
l
)
⁡
(
Q
x
⁢
⁢
B
)
i
]
;
⁢
computing a quantity D=determinant
[
r
x
⁢
⁢
Λ
r
xB
d
2
d
3
]
;
and
computing quantities a, b, and c, where
a
=
⁢
(
r
Λ
⁢
d
3
+
r
xB
⁢
d
1
)
⁢
D
-
1
,
b
=
⁢
{
(
d
1
+
ad
2
)
⁢
d
3
-
1
⁢
⁢
if
⁢
⁢
d
3
≠
0
(
r
Λ
+
ar
x
⁢
⁢
Λ
)
⁢
r
xB
-
1
⁢
⁢
otherwise
;
⁢
and
c
=
⁢
r
Λ
⁢
r
B
-
1
.

194 more elements

means for computing quotient polynomials QΛ, QxΛ, QB, QxB, Qx2B;
means for computing remainder polynomials rΛ, rxΛ, rB, rxB, rx2B;
means for computing quantities d1, d2, and d3, where
d
1
=
⁢
∑
i
=
0
t
⁢
⁢
[
S
n
-
k
-
i
(
e
l
)
⁡
(
Q
Λ
)
i
]
,
d
2
=
⁢
∑
i
=
0
t
⁢
⁢
[
S
n
-
k
-
i
(
e
l
)
⁡
(
Q
x
⁢
⁢
Λ
)
i
]
,
⁢
and
d
3
=
⁢
∑
i
=
0
t
⁢
⁢
[
S
n
-
k
-
i
(
e
l
)
⁡
(
Q
x
⁢
⁢
B
)
i
]
;
⁢
means for computing a quantity
D
=
determinant
⁡
[
r
x
⁢
⁢
Λ
r
xB
d
2
d
3
]
;
and
means for computing quantities a, b, and c, where
a
=
⁢
(
r
Λ
⁢
d
3
+
r
xB
⁢
d
1
)
⁢
D
-
1
,
b
=
⁢
{
(
d
1
+
ad
2
)
⁢
d
3
-
1
⁢
⁢
if
⁢
⁢
d
3
≠
0
(
r
Λ
+
ar
x
⁢
⁢
Λ
)
⁢
r
xB
-
1
⁢
⁢
otherwise
;
⁢
and
c
=
⁢
r
Λ
⁢
r
B
-
1
.

198 more elements

a quotient computation circuit that computes quotient polynomials QΛ, QxΛ, QB, QxB, Qx2B;
a remainder computation circuit that computes remainder polynomials rΛ, rxΛ, rB, rxB, rx2B;
a circuit that computes quantities d1, d2, and d3, where
d
1
=
⁢
∑
i
=
0
t
⁢
⁢
[
S
n
-
k
-
i
(
e
l
)
⁡
(
Q
Λ
)
i
]
,
d
2
=
⁢
∑
i
=
0
t
⁢
⁢
[
S
n
-
k
-
i
(
e
l
)
⁡
(
Q
x
⁢
⁢
Λ
)
i
]
,
⁢
and
d
3
=
⁢
∑
i
=
0
t
⁢
⁢
[
S
n
-
k
-
i
(
e
l
)
⁡
(
Q
x
⁢
⁢
B
)
i
]
;
⁢
a determinant computation circuit that computes a quantity
D
=
determinant
⁡
[
r
x
⁢
⁢
Λ
r
xB
d
2
d
3
]
;
and
a circuit that computes quantities a, b, and c, where
a
=
⁢
(
r
Λ
⁢
d
3
+
r
xB
⁢
d
1
)
⁢
D
-
1
,
b
=
⁢
{
(
d
1
+
ad
2
)
⁢
d
3
-
1
⁢
⁢
if
⁢
⁢
d
3
≠
0
(
r
Λ
+
ar
x
⁢
⁢
Λ
)
⁢
r
xB
-
1
⁢
⁢
otherwise
;
⁢
and
c
=
⁢
r
Λ
⁢
r
B
-
1
.

198 more elements

Dependencies are inferred from the claim text.

Iterative reed-solomon error-correction decoding

Life of this patent

Abstract

Claims24

Iterative reed-solomon error-correction decoding

Life of this patent

Abstract

Claims24