Method and apparatus of Reed-Solomon encoding-decoding

Details Method and apparatus of Reed-Solomon encoding-decoding Method and apparatus of Reed-Solomon encoding-decoding

1999-10-20

2003-04-15

Decady, Albert (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S784000

Reexamination Certificate

active

06550035

ABSTRACT:

FIELD OF THE INVENTION
The present invention pertains to a Reed-Solomon encoding device and method and a Reed-Solomon decoding device and method for use as error correction codes of recording media and digital transmission.
BACKGROUND OF THE INVENTION
Reed-Solomon codes (hereinafter referred to as RS codes) have high encoding efficiency and are very effective in eliminating burst errors. Consequently, they are mainly used as outside codes of recording media and digital transmission. Also, with advancements in IC technology, it has become possible to fabricate encoding/decoding ICs as single chips corresponding to codes with a relatively high correction power for 8-byte or higher correction. As a result, its application range has expanded rapidly.
RS codes are characterized by a very high degree of design flexibility pertaining to the forming method of encoding. For example, even for a Galois field GF(2
m
) that is frequently used in RS codes, usually, as a condition of its field formation polynomial, the period should be 2m−1. Consequently, there exist various types. In addition, there is a wide range for selecting the roots of the code forming polynomial that realizes the same correction power. That is, if the root of the field formation polynomial is &agr;, then as a condition for realizing a correction of t bytes, the root of the code forming polynomial can be selected from a group of at least 2t consecutive powers of &agr;, that is, (&agr;
b
, &agr;
b+1
, &agr;
b+2
, . . . &agr;
b+2t−1
). Here, b may be any integer. Consequently, there exists a significant number of different RS codes for the same t-byte correction.
From the standpoint of system development, such design flexibility is desirable. However, from the standpoint of standardization, this is undesirable. The requirement for correction power, etc., usually dictates the need for a Galois field GF(2
8
) with 2
8
elements. However, there are various other parameters. The code length and correction power, of course, depend on the specific requirements. Among the trivial differences, the greatest influence is the difference in the field formation polynomial. For example, if RS encoding/decoding devices are formed to correspond to two systems and the field formation polynomials are different, then the multipliers of their Galois fields will also be different. Consequently, compatibility is impossible. In particular, when efforts are made to correspond to that which has a higher correction power, the proportion of the multiplier of the aforementioned Galois field in the circuit scale becomes larger. In the prior art, one must prepare multipliers of Galois fields corresponding to the two systems. This leads to an increase in the cost of the device.
In practice, even in the same digital transmission field, the field formation polynomial used in satellite communications and those used in satellite broadcasting are different. This is mainly because standardization is difficult due to differences in jurisdiction between the communication field and the broadcasting field. Also, when the aforementioned standards were set up, there was little need for a common field formation polynomial.
In recent years, however, during discussions regarding the unification of communication and broadcasting, the aforementioned need became clearer. However, it is very hard to make changes to realize complete standardization. Also, for the RS codes adopted for recording media, manufacturers usually lead the development, and in few cases is the same field formation polynomial adopted for recording media developed by different manufacturers.
FIG. 11
is a schematic diagram illustrating a conventional RS encoding/decoding device handling two or more RS codes, that is, for handling RS
a
code, RS
b
code, . . . RS
x
code. It has multipliers (
10
a
)-(
10
x
) of Galois fields GF
a
(2
m
), GF
b
(2
m
), . . . GF
x
(2
m
) corresponding to field formation polynomials, respectively, and multiplication coefficient memory units (
11
a
)-(
11
x
) that store a collection of multiplication coefficients of Galois fields {&agr;
a[l]
}, {&bgr;
b[l]
}, . . . {&khgr;
x[k]
}, corresponding to the code forming polynomials, respectively. The conventional RS encoding/decoding device also has inverse element arithmetic circuits
12
a
-
12
x
corresponding to the codes for division.
In the following, in order to simplify the explanation, conventional RS encoding/decoding device
1
that handles two RS codes, that is, RS
a
code and RS
b
code will be used. Here, for both RS
a
code and RS
b
code, the correction power corresponds to a correction of t bytes.
FIG. 12
is a diagram illustrating surplus arithmetic circuit
202
that forms conventional RS encoding/decoding device
1
. In surplus arithmetic circuit
202
, collection of multiplication coefficients of Galois fields {&agr;
ao[i]
}, i=0-L is contained in said collection of multiplication coefficients of Galois fields {&agr;
a[i]
}, and collection of multiplication coefficients of Galois fields {&bgr;
be[j]
}, j=0-L is contained in said collection of multiplication coefficients of Galois fields {&bgr;
b[j]
}. Here, L is 2t−1 or 2t (same in the following).
As shown in
FIG. 12
, surplus arithmetic circuit
202
of the polynomial has multipliers
203
-
0
~
203
-L, multipliers
208
-
0
~
208
-L, switches
204
-
0
~
204
-L, registers
205
-
0
~
205
-L, adders
206
-
1
~
206
-L, and adder
207
.
Switches
204
-
0
~
204
-L select multipliers
203
-
0
~
203
-L in the case of RS
a
encoding and multipliers
208
-
0
~
208
-L in the case of RS
b
encoding.
Usually, RS decoding device is composed of syndrome arithmetic circuit, error location polynomial and evaluation polynomial arithmetic circuit, error location detecting circuit, evaluation value detecting circuit, and correction execution circuit. Of those, for said error location polynomial arithmetic circuit and evaluation polynomial arithmetic circuit, the known methods include the Euclidean algorithm method and the Barlekamp-Massey method.
FIG. 13
is a diagram illustrating a conventional constitutional example of syndrome arithmetic circuit
209
corresponding to said two RS codes. Here, the collection of multiplication coefficients of Galois fields {&agr;
as[i]
}, i=0-L is contained in said {&agr;
a[i]
}, and the collection of multiplication coefficients of Galois fields {&bgr;
bs[j]
}, j=0-L is contained in said {&bgr;
b[j]
}.
As shown in
FIG. 13
, syndrome arithmetic circuit
209
has multipliers
213
-
0
~
213
-L, switches
214
-
0
~
214
-L, registers
215
-
0
~
215
-L, adders
216
-
0
~
216
-L, and multipliers
217
-
0
~
217
-L.
Switches
214
-
0
~
214
-L select multipliers
213
-
0
~
213
-L in the case of RS
a
encoding and multipliers
217
-
0
~
217
-L in the case of RS
b
encoding.
FIG. 14
is a diagram illustrating an example of the conventional constitution of polynomial division circuit
221
, one of the major elements of the error location polynomial and evaluation polynomial arithmetic circuit, corresponding to said two RS codes.
As shown in
FIG. 14
, polynomial division circuit
221
has switches
222
-
0
~
222
-L, multipliers
223
-
0
~
223
-L, multipliers
228
-
0
~
228
-L, registers
225
-
0
~
225
-L, registers
224
-
0
~
224
-L, adders
226
-
0
~
226
-L, registers
227
,
229
, inverse element arithmetic circuits
231
,
232
, multipliers
230
,
231
, and switch
234
.
Switches
222
-
0
~
222
-L select multipliers
223
-
0
~
223
-L in the case of RS
a
encoding and multipliers
228
-
0
~
228
-L in the case of RS
b
encoding. Also, switch
234
selects multiplier
230
in the case of RS
a
encoding and multiplier
231
in the case of RS
b
encoding.
FIG. 15
is a diagram illustrating an example of the conventional constitution of polynomial multiplier
241
, a major eleme

Affiliated with

Also associated with

Rating

Method and apparatus of Reed-Solomon encoding-decoding does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus of Reed-Solomon encoding-decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus of Reed-Solomon encoding-decoding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3115129