Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-03-17
2004-03-09
Chung, Phung M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S704000
Reexamination Certificate
active
06704902
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a decoding system for decoding an error correction code such as an extended Reed-Solomon code extended by one symbol. More particularly, the invention relates to a decoding system which enables a mixed correction of, for example, a one-extended Reed-Solomon code at one path by integration of means for performing normal correction and erasure correction of an extended symbol.
2. Description of the Related Art
First, an error correction system will be described with reference to FIG.
1
.
Let us consider a case where the number of added parity symbols is p and information I=(I
0
, I
1
, . . . , I
k−1
) of k symbols is transmitted. The information of k symbols is encoded by an encoder (encoding block) so that p parity symbols are added and a code word C=(C
0
, C
1
, . . . , C
n−1
) with a length of n=k+p is obtained.
The code word passes through a transmission path with an error and is received as a received word R=(R
0
, R
1
, . . . , R
n−1
) including an error. When an i-th error is made ei, Ri=Ci+ei. The received word R is decoded by a decoder (decoding block), so that a presumed code word Cp=(Cp
0
, Cp
1
, . . . , Cp
n−1
) is obtained. Presumed information Ip=(Ip
0
, Ip
1
, . . . , Ip
k−1
) is obtained from this code word Cp.
A Reed-Solomon code is one of widely-used error correction codes. In the Reed-Solomon code, when a symbol is expressed by m bits, a maximum code length n max is 2
m
−1. For example, when a symbol is expressed by 8 bits, the maximum code length ‘n max’ becomes 255.
There is also a one-extended Reed-Solomon code in which the code length of the Reed-Solomon code is extended by one symbol, and the maximum code length ‘n max’ becomes 2
m
. For example, in the case where a symbol is expressed by 8 bits, the maximum code length ‘n max’ becomes 256. In the one-extended Reed-Solomon code, while the number of parity symbols p is kept as it is, the information symbols can be made larger than the Reed-Solomon code by one symbol, namely, k+1 symbols.
Next, a decoding method of the Reed-Solomon code will be described. There are three decoding methods, that is, a normal correction in which decoding is performed from onlya received word R, an erasure correction in which decoding is performedby using a received word R and an erasure flag F=(F
0
, F
1
, . . . , F
n−1
) indicating a position of the received word where an error appears to exist, and a mixed correction where the normal correction and the erasure correction are performed at the same time. Here, with reference to
FIGS. 2
to
6
, a decoding method of the mixed correction of the most general Reed-Solomon code will be described.
Here, with respect to a primitive polynomial f(x) on a field GF(2)={0, 1}, a root of f(x)=0 is made &agr;, and an extension field of GF(2) is formed. At this time, if the degree of the primitive polynomial f(x) is made m, one symbol becomes m bits, and the extension field GF(2
m
) is expressed by equation (1).
[Numerical Expression 1]
GF
(2
m
)={0, 1, &agr;, &agr;2, . . . &agr;
x
}, where
x=
2
m
−2 (1)
A generating polynomial g(x) of the Reed-Solomon code used here is expressed by equation (2).
[Numerical Expression 2]
g
(
x
)
=
∏
i
=
0
p
-
1
(
x
-
α
i
)
(
2
)
FIG. 2
shows a flowchart of decoding of the Reed-Solomon code.
First, at step
100
, a received word R=(R
0
, R
1
, . . . , R
n−1
) and an erasure flag F=(F
0
, F
1
, . . . , F
n−1
) are given. The erasure flag F is a flag in which 1 is set for a position in the received word R where it is predicted that an error exists, and 0 is set for other positions where it is predicted that an error does not exist.
Next, at step
101
, the number of erasures &egr; is obtained through equation (3), and an erasure position polynomial E(x) is obtained through equation (4).
[Numerical Expression 3]
&egr;=#{
i|F
i
=1} [for
i
=0~(
n
−1)] (3)
E
(
x
)=Π
Fi=1
(1−&agr;
i
x
) [for
i
=0~(
n
−1)] (4)
Next, at step
102
, using a parity check matrix H as expressed by equation (5), a syndrome S=(S
0
, S
1
, . . . , S
p−1
) is obtained from equation (6). A calculation method of the syndrome S will be described later with reference to FIG.
3
. Then a syndrome polynomial S(x) as expressed by equation (7) is obtained.
[Numerical Expression 4]
H
=
(
1
1
1
⋯
1
1
α
α
2
⋯
α
n
-
1
·
·
·
1
α
p
-
1
α
2
(
p
-
1
)
⋯
α
(
n
-
1
)
(
p
-
1
)
)
(
5
)
t
S=H
t
R
(6)
S
(
x
)=
S
0
+S
1
x+S
2
x
2
+ . . . +S
p−1
x
p−1
(7)
Next, at step
103
, using the erasure position polynomial E(x) and the syndrome polynomial S(x), a modified syndrome polynomial Sm(x) is obtained as expressed by equation (8).
[Numerical Expression 5]
Sm
(
x
)=
S
(
x
)
E
(
x
) mod
x
p
(8)
Next, at step
104
, an error evaluator polynomial &ohgr;(x) and an error locator polynomial &sgr;(x) are obtained by using the modified syndrome polynomial Sm(x). A calculation method of the error evaluator polynomial &ohgr;(x) and the error locator polynomial &sgr;(x) will be described later with reference to FIG.
4
.
Next, at step
105
, the condition of deg &ohgr;(x)<deg &sgr;(x) is judged, and if the condition is false, the procedure proceeds to step
110
, outputs an error signal, and is ended, and if true, it proceeds to step
106
. Here, deg &ohgr;(x) is the degree of the error evaluator polynomial &ohgr;(x) and deg &sgr;(x) is the degree of the error locator polynomial &sgr;(x).
At step
106
, the condition of equation (9) is judged, and if false, the procedure proceeds to step
110
, outputs an error signal, and is ended, and if true, it proceeds to step
107
. Incidentally, a bracket of the right side of equation (9) means that a decimal fraction is omitted. The same thing can be said to subsequent equations.
[Numerical Expression 6]
deg
σ
(
x
)
≤
⌊
p
+
ϵ
2
⌋
(
9
)
At step
107
, an error position is detected by using the error locator polynomial &sgr;(x). A calculation method of the error position will be described later with reference to FIG.
5
. At step
108
, the condition of #roots=deg &sgr;(x) is judged, and if false, the procedure proceeds to step
110
, outputs an error signal, and is ended, and if true, it proceeds to step
109
. Here, the #roots is the number of error positions detected at step
107
.
At step
109
, from the error evaluator polynomial &ohgr;(x), the error locator polynomial &sgr;(x) obtained at step
104
, and the error position i detected at step
107
, an error value ei at the position i is calculated. Further, from the received word R, the error position i, and the error value ei, presumed information Ip=(Cp
0
, Cp
1
, . . . , Cp
k−1
) is calculated and is outputted. A calculation method of the presumed information Ip will be described later with reference to FIG.
6
.
With reference to the flowchart of
FIG. 3
, a method of calculating the syndrome S from the received word R will be described.
First, at step
120
, the received word R=(R
0
, R
1
, . . . , R
n−1
) is received. At step
121
, the respective elements (S
0
, S
1
, . . . , S
p−1
) of the syndrome S are initialized by the element R
0
of the received word R. At step
122
, a counter I is initialized to 1.
Next, at step,
123
, the respective elements of the synd
Shinbashi Tatsuo
Suto Mitsuaki
Chung Phung M.
Sonnenschein Nath & Rosenthal LLP
Sony Corporation
LandOfFree
Decoding system for error correction code does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Decoding system for error correction code, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decoding system for error correction code will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3236888