Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-10-24
2004-05-18
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06738947
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method and apparatus for error correction and, more particularly, to an error correction method and apparatus which executes a syndrome operation without deinterleaving information data, which has been interleaved, and performs error correction.
BACKGROUND OF THE INVENTION
A-syndrome operation of error correction processings for the CD-ROM (Compact Disc-Read Only Memory) is described with reference to
FIGS. 4
to
7
.
FIG. 4
is a diagram showing a data format of one sector of the CD-ROM, which is represented on the basis of audio data (L and R stereo signals). L-CH denotes data of the left channel and R-CH denotes data of the right channel. “L” denotes a Least Significant Bit (LSB) and “M” denotes a Most Significant Bit (MSB). Upper three lines denoted by reference numeral
1
show a synchronous pattern representing one sector, and the next
585
lines below numeral
1
, denoted by numeral
2
, show the pattern of data.
FIG. 5
is a map which is formed by selecting only less significant bytes in the data of one sector shown in FIG.
4
. The plane which is composed of only less significant bytes is referred to as a least significant plane. Further, a plane which is composed of only more significant bytes is referred to as a most significant plane. The upper
24
lines denoted by numeral
4
show the header except the synchronous pattern and user data. The next two lines denoted by numeral
5
show P parity and the subsequent two lines denoted by numeral
6
show Q parity. The most significant plane has the same form as that of the least significant plane. The respective planes are subjected to the same ECC (Error Check and Correct). In addition, in the case of the CD-ROM, the ECC is performed for two codeword sequences, i.e., P sequence and Q sequence.
FIGS. 6 and 7
show the data of Q sequence shown in
FIG. 5
, which are rearranged in the direction of row (j). It can be seen that code sequences each having a code length n composed of 45 bytes (j=0-44) are arranged in
26
(i=0-25) rows. When i=0, the syndrome operation is executed with reading data every “44”, i.e., “0”, “44”, “88”, . . . . Similarly when i=1, the operation is executed with reading data every “44”, i.e., “43”, “87”, “131”, . . . . This is given by the following expression:
Q
=43
i
+44
j
mod 1118 (
i
=0-25
, j
=0-44) (Expression 13)
Japanese Published Patent Application No. Hei.5-12814 shows a method of executing syndrome operations in parallel and performing(error correction, without putting the data of Q sequence which have been rearranged in byte units, i.e., interleaved, in their original places, i.e., without deinterleaving the data. In this method, with utilizing the property that ECCs (Error-Correcting Codes) for the most significant plane and the least significant plane are irrelevant to each other, i.e., independent, 1 byte of data is respectively read on the most significant plane and the least significant plane (referred to as page
0
and page
1
in this Published Application) successively from the first data of codeword sequences arranged in the direction of row (j) among data stored at contiguous addresses in a buffer memory, i.e., 2 bytes of data are read, and the operations are executed in parallel by two syndrome operation circuits which are provided so as to respectively correspond to the most significant plane and the least significant plane.
As described above, the prior art error correction apparatus reads 1 byte of data on the most significant plane and the least significant plane, respectively, i.e., reads 2 bytes of data in total, successively from the first data of the interleaved data in each codeword sequence, and executes the operations in the two syndrome operation circuits in parallel, thereby increasing the speed of the operations. However, it is difficult to increase the parallelism of the operation to further increase the speed with this error correction apparatus.
In order to more specifically describe this, assume that in addition to 2 bytes of data as in the prior art, 2 bytes of data at the subsequent addresses are further read. In this case, “0001L” and “0001M” are read in addition to “0000L” and “0000M”, i.e., 4 bytes of data are read in total. Here, “0000L” and “0000M” correspond to “0” shown in FIG.
6
and are the first (j=0) data in the codeword sequence of i=0. On the other hand, “0001L” and “0001M” correspond to “1” shown in FIG.
6
and are the second (j=1) data in the codeword sequence of i=25.
More specifically, since the order in which “0000L” and “0000M” are subjected to the operations is different from the order in which “0001L” and “0001M” are subjected to the operation, their operations cannot be performed in parallel. In addition, when the operation is started from data halfway through the codeword sequence like “0001L” and “0001M”, an error occurs in the syndrome operation result. Thus, it is required to put the interleaved data in the their original places, i.e., deinterleave the data, and then execute the syndrome operation. Accordingly, the parallel operation of the syndrome cannot be performed by merely increasing the number of bytes of read data.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide an error correction method and apparatus for performing a high-speed operation, which can directly execute the operation, without deinterleaving plural bytes of data which are read according to the parallelism of the syndrome operation circuits.
Other objects and advantages of the present invention will become apparent from the detailed description and specific embodiments described are provided only for illustration since various additions and modifications within the spirit and scope of the invention will be apparent to those of skill in the art from the detailed description.
A method for error correction according to a 1st aspect of the present invention comprises a first step of repeating a product-sum operation using (n−s) codewords from an s-th codeword (1≦S≦n−1) halfway through a codeword sequence of a code length n (n is a positive integer) composed of 0th to (n-1)-th codewords, which is taken as an operation start data, to the (n-1)-th codeword, and obtaining a first partial syndrome polynomial; a second step of multiplying the first partial syndrome polynomial by index compensating coefficients to obtain a second partial syndrome polynomial; and a third step of repeating a product-sum operation using s pieces of codewords from the 0th codeword which is a first codeword in the codeword sequence, taken as an operation restart data, to a (s−1)-th codeword on the basis of the second partial syndrome polynomial and obtaining a syndrome polynomial of the codeword sequence. Therefore, the operation can be performed directly without deinterleaving the read data, whereby the high-speed syndrome operation can be realized.
According to a 2nd aspect of the present invention, in the error correction method of the 1st aspect, when the 0th codeword which is the first codeword of the codeword sequence is taken as the operation start data, the product-sum operation is repeatedly performed using n pieces of codewords from the 0th codeword to the (n−1)-th codeword to obtain the syndrome polynomial of the code sequence. Therefore, the high-speed syndrome operation can be performed.
According to a 3rd aspect of the present invention, in the error correction method of the 1st aspect, when the 0th codeword which is the first codeword in the code sequence is taken as the operation start data, the first and second steps are executed to obtain the syndrome polynomial of the codeword sequence. Therefore, the syndrome operation having a high parallelism can be executed.
An apparatus for error correction according to a 4th aspect of the present invention comprises syndrome operation means for repeating a cycle in which a syndrome operation is started taking an s-th code
De'cady Albert
Matsushita Electric - Industrial Co., Ltd.
Torres Joseph D.
Wenderoth , Lind & Ponack, L.L.P.
LandOfFree
Method and apparatus for error correction 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 for error correction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for error correction will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3231570