Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-02-24
2001-12-18
Moise, Emmanuel L. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S769000, C714S781000, C714S804000, C714S805000
Reexamination Certificate
active
06332206
ABSTRACT:
This application is based on application No. H10-43219 filed in Japan, the contents of which are hereby incorporated by reference.
BACKGROUND OF THE INVENTION
(1) Field of the Invention
The present invention relates to an apparatus that corrects errors in decoded data. In particular, the invention relates to an apparatus for correcting errors in two-dimensional block code at high speed.
(2) Description of the Prior Art
When a data storage device uses a magnetic or optical disc as a storage medium, scratches or dirt on the disc can cause data errors. To enable such errors to be corrected, codes specifically for this purpose are added when recording data onto the storage medium. These codes are commonly called error correction codes or parity data. During the reproduction of recorded data, errors are detected using the error correction codes and the detected errors are corrected. Hereafter, the processing for adding these error correction codes and the processing for correcting errors will collectively be called “error-related processing”. To improve the performance of error-related processing, many systems use Reed-Solomon codes as the error correction codes and product code as the data structure.
FIG. 1
shows an example of product code. Information composed of k1*k2 bytes is assigned ml bytes of parity data in the horizontal (row) direction (hereinafter the “C1 series” or “C1 direction”) and m2 bytes of parity data in the vertical (column) direction (hereinafter the “C2 series” or “C2 direction”). The combination of the information, the C1 parity data and the C2 parity data compose one block. This block is the largest unit for which error correction can be performed. This block is n1*n2 bytes in size. Usually, the information and the parity data will be stored in a memory such as a DRAM (Dynamic Random Access Memory) by incrementing the address in the memory by one in the C1 direction. As a result, the data that composes the code sequences in the C1 direction is stored in storage areas with consecutive addresses. Conversely, the code sequences in the C2 direction is stored in storage areas with non-consecutive addresses. Note that the separate codes that compose the product data will be called “data” or “data elements” in the following explanation.
FIG. 2
shows the flow of the error correction performed for the code sequences in the C1 direction. Error correction is first performed for the code sequence in the first row. The processing then proceeds to the second and following rows and is repeated a total of n
2
times. This means that data is scanned and error correction is performed for one entire row at a time. The term “scan” here also refers to the reading order used when reading the data that is to be subjected to error detection and error correction from the storage areas. In this text, the term “error detection” refers to processing that does not include error correction. The term “error correction” meanwhile can refer both to error correction and to the error detection that precedes it.
FIG. 3
shows the flow of the error correction performed on the C2 code sequences. Error correction is first performed for the code sequence in the first column. The processing then proceeds to the second and following columns and is repeated a total of n
1
times. This means that data is scanned and error correction is performed for one entire column at a time.
FIG. 4
is a block diagram showing the composition of a conventional error correction apparatus that performs error correction with the flow described above. In this example, there are 100 bytes of information numbered d1 to d100 and 10 bytes of parity data numbered p1 to p10. Together these form one code sequence.
The information and parity data are read from the memory and sequentially inputted into the syndrome generating unit
900
. The syndrome generating unit
900
performs a predetermined calculation whenever one data element is inputted and, when all of the information d1~d100 and parity data p1~p10 that compose one code sequence have been inputted, generates ten syndromes. If non-zero data is present in any of these syndromes, this means that an error is present in the code sequence, so that the error position-error value calculating unit
901
uses the syndromes to calculate the error position and the error value. Here, the “error position” is information showing the position of the erroneous data element in the code sequence, while the “error value” shows the size of the error. Finally, the error data updating unit
902
uses the error position and error value to read the error data from the memory and to correct the error, before writing the updated value back into the same position in the memory. This processing is then repeated for another code sequence.
As described above, a conventional error correction apparatus scans and performs error correction one row at a time for code sequences in the C1 direction and one column at a time for code sequences in the C2 direction. In this way, error correction is performed for every code sequence that composes a block.
In recent years, there have been increasing demands for improvements in the processing speed of data storage devices such as modern optical disc drives. Conventional error correction apparatuses, however, are unable to satisfy these demands.
To meet such demands, it would conceivably be possible to use plurality of error correction apparatuses in parallel within a single data storage device. Such an arrangement would however require a large-scale circuit and would reduce cost performance.
SUMMARY OF THE INVENTION
In view of the stated problems, it is a primary object of the present invention to provide an error correcting apparatus that can perform the processing required for error correction at high speed with a small-scale circuit.
This primary object can be achieved by an error correcting apparatus that repeatedly performs calculations that are required for error correction on code sequences in a row direction and a column direction in block code of R rows and L columns, the error correcting apparatus including: a storing unit for storing the block code; a calculating unit for performing calculations for correcting errors in the block code in units of one of (a) one row and (b) one column; and a transfer unit, including a row direction transferring unit for repeatedly reading code sequences on R1 (where R1 is an integer such that 2≦R1<R) rows in the block code from the storing unit and transferring the read code sequences to the calculating unit until all R rows have been read and transferred, the row direction transferring unit transferring the code sequences on the R1 rows from the storing unit to the calculating unit by repeatedly reading and transferring sections of L1 consecutive codes (where L1 is an integer such that 2≦L1<L) on the R1 rows in order, shifting a read position by L1 codes after reading L1 consecutive codes on each of the R1 rows, wherein when codes have been transferred by the row direction transferring unit, the calculating unit performs the calculations for the code sequences on the R1 rows in parallel, treating the received codes as L1-code-wide sections of the code sequences on different rows in the R1 rows.
With the stated construction, error correction in the row direction is performed in parallel for a plurality of code sequences. A zigzag scanning order is followed for a plurality of small blocks that are obtained by dividing the code sequences on a plurality of rows in the row direction. This is to say, the error correction proceeds in parallel by repetitively scanning only part of the code sequences on different rows. Compared with when error correction that scans the entire code sequence on one line at a time is performed, the present method can use a lower average speed when inputting into the error correction circuit for each row and can use smaller circuitry, such as for the queue buffer in the error correction circuit for each line, even when codes are read and error correction is performed at the same rate
Hashimoto Yuichi
Nakatsuji Fumio
Matsushita Electrical Industrial Co. Ltd.
Moise Emmanuel L.
Price and Gess
LandOfFree
High-speed error correcting apparatus with efficient data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High-speed error correcting apparatus with efficient data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-speed error correcting apparatus with efficient data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2575623