Dynamic magnetic information storage or retrieval – General processing of a digital signal – Data verification
Reexamination Certificate
2001-06-26
2004-04-27
Hudspeth, David (Department: 2651)
Dynamic magnetic information storage or retrieval
General processing of a digital signal
Data verification
C714S784000
Reexamination Certificate
active
06728052
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to an error correcting coding method used with the recording/reproducing apparatus.
The Reed-Solomon code is used for the recording/reproducing apparatus such as the magnetic disk device, the magneto-optic disk device and the compact disk device. The magnetic disk device uses the Reed-Solomon code on the finite field GF(2
8
) including 2
8
elements which is a set wherein the four rules of arithmetic are defined (except for “division by 0”) mutually by the elements, where GF is an abbreviation of Galois Field. The error correcting coding and the error correcting process for the recording/reproducing apparatus are performed with eight bits of the Reed-Solomon code as one symbol providing a unit for calculation.
In the Reed-Solomon code, it is known that the code having the maximum number t of correction symbols can be configured by setting the number of redundant symbols to 2t. The length of the sector providing a unit for performing each recording/reproducing operation is 512 symbols. In view of the fact that the length of the Reed-Solomon code that can be configured on GF(2
8
) is 255 (=2
8
−1) symbols or less, data are divided (interleaved) into three or more blocks and then an error correcting code is provided for each block.
One of the advantages of the Reed-Solomon code is that the symbol positions for calculation are arranged, from the most significant place of the code, as &agr;
n-1
, &agr;
n-2
, . . . , &agr;
2
, &agr;
1
, &agr;
0
(&agr;: primitive root of finite field), so that the symbol position for calculation can be regularly calculated by the multiplier alone at the time of the Chien search for the error position for decoding. The Chien search is a method for searching for a solution of an equation by substituting the elements into the equation sequentially.
SUMMARY OF THE INVENTION
Consider the case in which the Reed-Solomon code on GF(2
8
) is used for a recording system of 512 symbols per sector. In view of the fact that the code length is not more than 2
8
−1=255 symbols and the relation holds that 512/255>2, the problem is that the number of interleaves cannot be reduced below 3.
As long as the maximum number of correction symbols per sector is constant, the smaller the number of interleaves, the higher the error correcting ability of the code.
With the error correcting coding method according to this invention, an elliptic code on GF(2
m
) is used to configure a code longer than 2
m
−1 and therefore the number of interleaves can be reduced.
For configuring the code having the maximum number t of correction symbols by the elliptic code, the number of redundant symbols is set to 2t+1. The number of redundant symbols for this code is 287−256=31, and therefore the maximum number of correction symbols is given as 15 (15×2+1=31). The use of this code makes it possible to configure 512 bytes per sector in two interleaves. The principle of the error correcting coding method according to this invention will be explained below.
Assume that E(C, GF(2
m
)) for the elliptic curve C: y
2
+a
1
xy+a
3
y+a
0
x
3
+a
2
x
2
+a
4
x+a
6
=0 on GF(2
m
) indicates the following set, &egr; is the number of elements of E (C, GF (2
m
)) and a
0
, a
1
, a
2
, a
3
, a
4
, a
6
are constants.
E
(
C, GF
(2
m
))={(&agr;, &bgr;)&egr;
GF
(2
m
)
2
|&bgr;
2
+a
1
&agr;&bgr;+a
3
&bgr;+a
0
&agr;
3
+a
2
&agr;
2
+a
4
&agr;+a
6
=0} (1)
∪{o: point at infinity}
where if the points associated with E(C, GF(2
m
))\{o} are assigned the numbers p
(1)
, p
(2)
, . . . , p
(&egr;−1)
, the code word of the elliptic code is defined as a column vector w satisfying Hw=0 for the matrix H of equation (2).
H
=
(
h
i
,
j
)
1
≤
i
≤
n
-
k
1
≤
j
≤
n
,
h
i
,
j
=
v
i
-
1
(
P
(
j
)
)
,
(
v
0
(
x
,
y
)
=
1
,
v
1
(
x
,
y
)
=
x
,
v
2
(
x
,
y
)
=
y
,
v
j
+
2
=
v
1
(
x
,
y
)
v
j
(
x
,
y
)
for
j
≥
1
)
(
2
)
Especially, the code length n coincides with &egr;−1. The elliptic curve C which satisfies the relation n>2
m
−1 can be found by total search of the values of the coefficient a
j
.
With the definition of equation (2), however, the code word cannot be calculated by other than the method of solving an equation, and therefore the process is very complicated. The calculation can be facilitated by regular matrix operation of the code word by rewriting the equation (2) as follows.
Specifically, assume that the vector with k symbols arranged in column before coding is w
0
. When H satisfies equation (3), Gw
0
constitutes a code word for the matrix G of equation (4). As a matter of fact, the relation is obtained that H(Gw
0
)=M
−1
(MH) (Gw
0
)=M
−1
((MH)G)w
0
=0.
∃M: square matrix s.t. MH=(H
1
|I) (3)
G
=
[
I
H
1
]
(
4
)
, where I represents an identity matrix. If H
1
can be calculated from equation (5), the redundant symbol of the corresponding code word Gw
0
can be calculated from w
0
.
Gw
0
=
[
I
H
1
]
w
0
=
[
w
0
H
1
w
0
]
(
5
)
Equation (6) can be obtained from equation (3). As long as M is calculated and stored in advance, therefore, H
1
can be calculated. Thus, the redundant symbol of the code word Gw
0
can also be calculated from w
0
.
H
1
=
(
h
i
,
j
*
)
1
≤
i
≤
n
-
k
,
1
≤
j
≤
k
,
h
i
,
j
*
=
v
i
-
1
(
P
(
j
)
)
,
(
V
0
(
x
,
y
)
V
1
(
x
,
y
)
⋮
V
n
-
k
-
1
(
x
,
y
)
)
=
M
(
v
0
(
x
,
y
)
v
1
(
x
,
y
)
⋮
v
n
-
k
-
1
(
x
,
y
)
)
(
6
)
In order to give the regularity to E(C, GF(2
m
))\{o}, an arithmetic circuit for realizing the calculation +
0
as defined in equation (7) is built in and used.
O+
o
P=P+
o
O=P
for
P&egr;E
(
C,GF
(2
m
)),
(
x
1
,y
1
)+
o
(
x
1
,y
1
+a
1
x
1
+a
3
)=0,
(
x
1
,y
1
)+
o
(
x
2
,y
2
)=(
x
3
,y
3
) (
x
1
≠x
2
or
y
2
≠y
1
+a
1
x
1
+a
3
)
{
x
3
=
λ
2
+
a
1
λ
+
a
2
+
x
1
+
x
2
,
y
3
=
(
λ
+
a
1
)
x
3
&LeftBracketingBar;
ν
&RightBracketingBar;
-
a
3
,
{
λ
=
x
1
2
+
a
4
+
a
1
y
1
a
1
x
1
+
a
3
,
ν
=
x
1
3
+
a
1
x
1
+
a
3
y
1
a
1
x
1
+
a
3
(
x
1
=
x
2
and
y
2
≠
y
1
+
a
1
x
1
+
a
3
)
{
λ
=
x
1
3
+
a
4
+
a
1
y
1
a
1
x
1
+
a
3
,
ν
=
x
1
3
+
a
4
x
1
+
a
3
y
1
a
1
x
1
+
a
3
(
x
1
≠
x
2
)
(
7
)
For the element P of E(C, GF (2
m
)), P +
0
, . . . , +
0
P (involving Ps in the number of m) is expressed as [m] P.
The recording/reproducing apparatus according to this invention based on the aforementioned principle is for recording in a recording medium the interleaved data with an error correcting code added thereto and reproducing the recorded data from the recording medium, the apparatus comprising an error correcting decoding circuit for generating an error correcting code using an elliptic code on a finite field GF(2
m
) (m: positive integer).
REFERENCES:
patent: 5408477 (1995-04-01), Okada et al.
patent: 5422895 (1995-06-01), Nguyen et al.
patent: 6052820 (2000-04-01), Yoshida
patent: 10232099 (1998-09-01), None
patent: 11119191 (1999-04-01), None
patent: 11139698 (1999-05-01), None
Kondo Masaharu
Takashi Terumi
Antonelli Terry Stout & Kraus LLP
Hitachi , Ltd.
Hudspeth David
Rodriquez Glenda P.
LandOfFree
Recording/reproducing apparatus, error correcting coding... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Recording/reproducing apparatus, error correcting coding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Recording/reproducing apparatus, error correcting coding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3239133