Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1997-10-30
2002-04-23
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S774000
Reexamination Certificate
active
06378104
ABSTRACT:
FIELD OF THE INVENTION
This invention pertains to a Reed-Solomon coding and decoding device, as well as a method for use as the error correction code of recording media and digital transmission.
BACKGROUND OF THE INVENTION
The Reed-Solomon code (referred to as RS code hereinafter) has a high coding efficiency and good performance against burst error. Consequently, it is mainly used as the outer code of recording media and in digital transmission. Also, with the progress in IC technology, it becomes possible to realize coding/decoding IC on a single chip for handling codes with a relatively high correction power for 8-byte correction or higher, and the application range expands rapidly.
The RS code is characterized by the fact that the freedom is very high with respect to the construction method of coding. For example, for the Galois field GF(2
8
) used frequently in the RS code, usually, the period may be 2
8
−1 as a condition of the field generation polynomial, and hence various types exist. In addition, there is a very wide range of selection of the root of the code generation polynomial that realizes the same correction power. That is, supposing that the root of the field generation polynomial is &agr;, for the condition for realizing correction of the t-byte, as the root of the code generation polynomial, a group of at least 2t consecutive powers of &agr;, that is, {&agr;
b
, &agr;
b+1
, &agr;
b+2
, . . . , &agr;
b+2t−1
} is selected. Here, it is possible to select any integer as the value of b. Consequently, there is a significant number of RS codes that are different from each other and that have the same t-byte correction.
From the viewpoint of system development, such a level of freedom is preferred. From the viewpoint of standardization, this level is not sufficient. From the demand on the correction power, etc., usually, a Galois field GF(2
8
) having 2
8
elements is usually adopted, while the other parameters may take different values. It is natural that the code length and correction power depend on the specifications demanded. Among the cited differences, that having the most significant influence is the difference of the field generation polynomial. For example, when RS coding/decoding devices corresponding to two schemes are formed, because their field generation polynomials are different from each other, their multipliers of the Galois field are also different from each other. Consequently, there is no way to share them. In particular, in order to meet a higher correction power, the proportion of the aforementioned multiplier of the Galois field in the circuit scale is large. In the conventional method, the multipliers of the Galois field corresponding to the two schemes have to be respectively equipped, so that the price of the device is boosted, which is a disadvantage.
As a matter of fact, even in the same field of digital transmission, the field generation polynomial adopted for satellite communications and the field generation polynomial adopted for satellite broadcasts are different. This is mainly due to the difficulty in standardization due to the difference in management between field of communications and the broadcast field. Also, at the time of standardization, there was a low necessity to share the field generation polynomial.
In recent years, studies have made it more and more clear that it is necessary to unify communications and broadcasts. However, once the standardization is completed, it becomes very difficult to change it. Also, the RS code adopted for the recording media is usually developed by the producers, yet in few cases, the same field generation polynomial is adopted by different recording media developed by different producers.
FIG. 11
is a schematic diagram illustrating the conventional RS coding/decoding device that can handle two or more RS codes, that is, RS
a
code, RS
b
code, RS
x
code. It is equipped with multipliers
10
a
-
10
x
of Galois fields GF
a
(2
m
) , GF
b
(2
m
), . . . GF
x
(2
m
) corresponding to the various field generation polynomials, respectively, as well as multiplication coefficient memory units
11
a
-
11
x
that store sets of Galois field multiplication coefficient {&agr;
a[I]
}, {&bgr;
b[J]
}, . . . , &khgr;
x{[K]
} respectively. The conventional RS coding/decoding device also has inverse element operation circuits
12
a
-
12
x
for division operations corresponding to the various codes.
In the following description, in order to simplify the description, conventional RS coding/decoding device
1
for handling two RS codes, that is, the RS
a
code and RS
b
code, will be described. In this case, for both the RS
a
code and RS
b
code, the correction power is taken as a t-byte correction.
FIG. 12
is a diagram illustrating the polynomial remainder operation circuit
202
that forms conventional RS coding/decoding device
1
. In remainder operation circuit
202
, the set of Galois field multiplication coefficient {&agr;
ae[i]
}, i=0−L is contained in the aforementioned Galois field's multiplication coefficient set {&agr;
a[I]
}, and the Galois field's multiplication coefficient set {&bgr;
be[j]
}, j=0−L is contained in the aforementioned set of Galois field multiplication coefficient {&bgr;
b[J]
}. L is 2t−1 or 2t (same in the following).
As shown in
FIG. 12
, the polynomial operation circuit
202
has multipliers
203
-
0
to
203
-L, multipliers
208
-
0
to
208
-L, switches
204
-
0
to
204
-L, registers
205
-
0
to
205
-L, adders
206
-
0
to
206
-L, and adder
207
.
Switches
204
-
0
-
204
-L select multipliers
203
-
0
to
203
-L in the case of RS
a
coding, and they select multipliers
208
-
0
to
208
-L in the case of RS
b
coding.
The RS decoding device usually comprises a syndrome operation circuit, error-position polynomial and evaluating polynomial operation circuit, error-position detector, evaluation value detector, and correction execution circuit. Among these, for the aforementioned error-position polynomial operation circuit and evaluating polynomial operation circuit, the Euclid and the Berlekamp-Massey algorithm are known algorithms.
FIG. 13
is a conventional structural example of syndrome operation circuit
209
that can handle the aforementioned two RS codes. In this case, the set of Galois field multiplication coefficient {&agr;
as[I]
}, I=0~L is contained in said {&agr;
a[I]
}, and the Galois field's multiplication coefficient assembly {&bgr;
bs[j]
}, j=0~L is contained in said {&bgr;
b[J]
}.
As shown in
FIG. 13
, syndrome operation circuit
209
has multipliers
213
-
0
to
213
-L, switches
214
-
0
to
214
-L, registers
215
-
0
to
214
-L, adders
216
-
0
to
216
-L, and multipliers
217
-
0
to
217
-L.
Switches
214
-
0
to
214
-L select multipliers
213
-
0
to
213
-L in the case of RS
a
coding, and they select multipliers
217
-
0
to
217
-L in the case of RS
b
coding.
FIG. 14
is a diagram illustrating a conventional structural example of polynomial divider
221
, one of the principal structural elements of the operation circuit of the error-position polynomial and evaluation polynomial that can handle the aforementioned two RS codes.
As shown in
FIG. 14
, polynomial divider
221
has switches
222
-
0
to
222
-L, multipliers
223
-
0
to
223
-L, multipliers
228
-
0
to
228
-L, registers
225
-
0
to
225
-L, registers
224
-
0
to
224
-L, adders
226
-
0
-
226
-L, registers
227
,
229
, inverse element operation circuits
231
,
232
, multipliers
230
,
231
, and switch
234
.
Switches
222
-
0
to
222
-L select multipliers
223
-
0
to
223
-L in the case of RS
a
coding, and they select multipliers
228
-
0
to
228
-L in the case of RS
b
coding. Also, switch
234
selects multiplier
230
in the case of RS
a
coding, and selects
Baker Stephen M.
Peterson Bret J.
LandOfFree
Reed-solomon coding device and method thereof 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 coding device and method thereof, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reed-solomon coding device and method thereof will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2904922