Reed Solomon error correcting circuit and method and device...

Details Reed Solomon error correcting circuit and method and device... Reed Solomon error correcting circuit and method and device...

1999-03-10

2002-04-16

Baker, Stephen M. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

Reexamination Certificate

active

06374384

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a Reed-Solomon error-correcting circuit that is used as a system of error correction, and also to the Euclidian algorithm and apparatus that are used in systems of error correction such as BHC error-correcting systems and Reed-Solomon error correcting systems.
2. Description of the Related Art
Error correcting systems such as BHC error-correcting systems and Reed-Solomon error-correcting systems are used as error correcting systems in various fields such as recording media like optical fibers and digital transmission systems like digital satellite broadcasting systems. Of recent years, as the scale of recording and transmission has become greater, error-correcting circuits that accommodate high-speed processing have been developed.
So far, as a Reed-Solomon error-correcting circuit that accommodates high-speed processing, there has been known the one disclosed in Japanese Patent Laid-Open Publication No. 3-195216.
This Reed-Solomon error-correcting circuit comprises, as shown in
FIG. 18
, a syndrome generating circuit
1
(equivalent to the syndrome generating circuit in the Reed-Solomon error-correction circuit of the present invention), an error-locator-polynomial deriving circuit
2
(equivalent to the error-locator-polynomial/error-evaluator-polynomial calculating circuit within the error correcting circuit in the Reed-Solomon error-correcting circuit of the present invention), an error-location detecting circuit
3
and an error-pattern detecting circuit
4
and an AND gate
5
and an EXOR gate
6
(equivalent to the correcting circuit within the error correcting circuit in the Reed-Solomon error-correcting circuit of the present invention), and a delay circuit
7
(equivalent to the memory in the Reed-Solomon error-correcting circuit of the present invention).
The error-locator-polynomial deriving circuit in this Reed-Solomon error-correcting circuit requires, as described in the embodiment of the patent disclosure, a great number of Galois-field calculating circuits installed between the registers of the shift registers, in order to accommodate high-speed processing. Therefore, there is a problem that the scale of hardware is large.
Also, in order to limit internal delays and increases in power consumption due to large-scale hardware, a high-speed clock is not used, and a received symbol clock is used for operation. Therefore, one packet of time is taken for processing in the error-locator-polynomial deriving circuit.
Therefore, there is required, at least, parallel operation with three-step pipelined processing by the syndrome generating circuit, the error-locator-polynomial deriving circuit, and the error-location detecting circuit, error-pattern detecting circuit, AND gate, and EXOR gate. Therefore, the delay circuit must hold three packets of data, so that the scale of hardware becomes still larger.
Next, the operation of the above circuit is described. In error correcting systems such as BHC error-correcting systems and Reed-Solomon error-correcting systems, first a syndrome equation S(z)=s
k−1
z
k−1
+s
k−2
z
k−2
+ . . . +s
0
based on the received signal is obtained on the receiver side. In the Reed-Solomon error-correcting circuit described above, the syndrome generating circuit performs this operation.
If there exists no error in the signal, then the coefficients S
k−1
to s
0
of the syndrome equation S(z) become s
k−1
=s
k−2
= . . . =s
0
=0, that is, the syndrome equation becomes S(z)=0. If there exist some errors in the signal, the syndrome equation becomes S(z)≠0.
If there exist some errors in the received signal, so that the syndrome signal becomes S(z)≠0, then, the error-locator-polynomial &sgr;(z) is obtained from the syndrome equation S(z). In the Reed-Solomon error-correcting circuit described above, the error-locator-polynomial deriving circuit performs this operation.
Finally, errors are corrected by using the error-locator-polynomial &sgr;(z).
Generally, in order to obtain the error-locator-polynomial &sgr;(z) from the syndrome equation S(z), an Euclid's algorithm is used. In the past, as the Euclid's algorithm, the one described in “Development of Error correcting methods and LSI for optical disk drives,”
Computer Architecture,
67-3 (Sep. 16, 1987) is known.
A description is given in the following with the Reed-Solomon error-correcting method based on a report of the Committee on Digital Broadcasting Systems in the Council of Electronic Communication.
Code generating polynomial:
g
(
z
)=(
z+&agr;
0)(
z+&agr;
1)(
z+&agr;
2) . . . (
z+&agr;
15), (&agr;=02
h
).
Field generating polynomial: x8+x4+x3+x2+1.
Packet length: 204 bytes.
Information bytes therein: 188 bytes.
Error correcting number: 8 bytes.
In the Euclid's algorithm of the Reed-Solomon error-correcting system described above, initial setting for the polynomials A(z), B(z), L(z), and M(z) is made from the syndrome equation
S
(
z
)=
s
15
z
15
+s
14
Z
14
+ . . . +s
0
based on the signal decoded with the Reed-Solomon code, where s
15
, . . . , s
0
are elements of the Galois field GF(
28
) . Then the error-locator-polynomial &sgr;(z) is obtained through Galdis-field operations. Operations on Galois fields are described in Hideki Imai,
Coding Theory,
Chapter 3, Institute of Electronics and Communication Engineers of Japan.
In the following is described the Euclid's algorithm in a prior example in conjunction with figures.
FIG. 19
is a flowchart illustrating the method of initial setting in a prior exemplary Euclid's algorithm.
FIG. 20
is a flowchart illustrating a general Euclid's algorithm after initial setting.
In the Euclid's algorithm in the prior example, according to the method of initial setting illustrated in
FIG. 19
, initial setting for the polynomials A(z), B(z), L(z), and M(z) is performed from the syndrome equation
S
(
z
)=
s
15
z
15
+s
14
Z
14
+ . . . +s
0
based on a signal decoded with the Reed-Solomon error correcting code, where s
15
, . . , s
0
are elements of the Galois field GF(
28
). Then, according to the general Euclid algorithm after the initial setting illustrated in
FIG. 20
, Galois-field operations are performed to obtain the error-locator-polynomial &sgr;(z). In the Galois-field operations, processing for reducing the degrees of the polynomials A(z) and B(z) is performed. When at least one of the degrees of the polynomials A(z) and B(z) becomes equal to or less than 7, the processing is terminated.
In the following is described an example of the Euclid's algorithm in the prior example illustrated in
FIGS. 19
,
20
.
In the following, a first example of operations in the Euclid's algorithm in the prior example is described. This example of operations is in the case where s
15
, . . , s
8
≠0 for the coefficients of the syndrome equation S(z). In this example of operations, after sixth operations on the Galois field, the error-locator-polynomial &sgr;(z) is obtained.
First example of operations in prior Euclidean algorithm. Syndrome.
S
(
z
)=85
z
15
+EBz
14
+E
9
z
13
+A
9
z
12
+F
8
z
11
+AEz
10
+C
4
z
9
+14
z
8
+A
7
z
7
+72
z
6
+A
0
z
5
+58
z
4
+91
z
3
+51
z
2
+5
Fz+FF
After initial setting.
A
⁡
(
z
)
=
z
16
B
⁡
(
z
)
=
85
⁢
z
15
+
EBz
14
+
E9z
13
+
A9z
12
+
F8z
11
+
AEz
10
+
C4z
9
+
14
⁢
z
8
+
A7z
7
+
72
⁢
z
6
+
A0z
5
+
58
⁢
z
4
+
91
⁢
z
3
+
51
⁢
z
2
+
5
⁢
Fz
+
FF
L
⁡
(
Z
)
=

⁢
0
M
⁡
(
Z
)
=

⁢
1
After first Galois-field operations.
A
⁡
(
z
)
=
EBz
15
+
E9z
14
+
A9z
13
+
F8z
12
+
AEz
11
+
C4z
10
+
14
⁢
z
9
+
A7z
8
+
72
⁢
z
7
+
A0z
6
+
58
⁢
z
5
+
91
⁢
z
4
+
51
⁢
z
3
+
5
⁢
Fz
2
+
FFz
B
⁡
(
z
)
=
85
⁢
z
15
+
EBz
14
+
E9z
13
+

Affiliated with

Also associated with

Rating

Reed Solomon error correcting circuit and method and device... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Reed Solomon error correcting circuit and method and device..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reed Solomon error correcting circuit and method and device... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2873045