Error correction device

Details Error correction device Error correction device

2000-11-17

2004-10-05

Moise, Emmanuel L. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S746000, C714S784000, C714S785000

Reexamination Certificate

active

06802040

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to error correction devices and particularly to error correction devices successively providing error correction for a code in each direction for a data block including a product code.
2. Description of the Background Art
In environments transmitting digital data, such as digital transmission systems, peripheral apparatuses for computers and the like, error correction codes are typically used to more reliably transmit digital data. In particular, in recent years an error correction code having a high correction capability is used as a digital data receiving and decoding side is enhanced in data processing capability.
A representative one of such error correction codes is a product code, which has two long-distance codes with large code length and redundancy.
FIG. 13
schematically shows a manner in which such a product code is added to digital data (information symbol).
With reference to
FIG. 13
, the product code is typically a combination of error correction codes provided in different directions, i.e., vertical and horizontal directions. More specifically, the product code is configured of a parity PO corresponding to an external code added to the information symbol in the vertical direction and a parity PI corresponding to an internal code added to the information symbol and parity PO in the horizontal direction.
Each error correction code is often a Reed-Solomon code (hereinafter referred to as an RS code) capable of byte-by-byte error correction. In the
FIG. 13
example, the error correction code in the PO direction is an RS code having a code length n
0
(=208), an information length k
0
(=192) and a minimal distance d
0
(=17), and the error correction code in the PI direction is an RS code having a code length n
i
(=182) an information length k
i
(=172) and a minimal distance d
i
(=11).
Theoretically, there are established relationships of d
i
≧2t
i
+1 and d
0
≧2t
0
+1, wherein t
i
and to are each a number of errors that can be corrected.
If a receiving and decoding apparatus decodes or corrects errors of a data block including a product code with RS error correction codes added in two directions, error correction in each direction is typically repeated, again and again.
FIG. 14
is a block diagram simply showing a data transmission path in an error correction process of such a first conventional error correction device.
With reference to
FIG. 14
, digital data read for example from a DVD is transmitted on a data bus
51
, provided in the form of a data block including a product code, as shown in
FIG. 13
, and it is thus stored temporarily in a buffer memory
52
. Buffer memory
52
typically has a large capacity of no less than 4 Mbit to store a plurality of product-code blocks at one time. As such, a dynamic random access memory (DRAM), a synchronous dynamic random access memory (SDRAM) or the like is mainly used as buffer memory
52
as it has a large capacity, occupies a small area and is not costly.
Then the data stored in buffer memory
52
are successively read and an error correction circuit
53
provides error correction for the code in each direction. Correcting errors with a Reed-Solomon code typically follows the following 4-step procedure:
(1) Calculate a syndrome from received data;
(2) Obtains an error location polynomial and an error estimation polynomial from the syndrome;
(3) Obtain an error location from the error location polynomial; and
(4) Obtain an error count value from the error location polynomial, the error estimation polynomial and the error location, and corrects the obtained error count value.
If a Reed-Solomon code having a high correction capability is used to correct an error, Euclidean algorithm obtaining the greatest common divider of two polynomials may be applied as one technique of obtaining an error location polynomial and an error estimation polynomial from a syndrome in step (2).
FIG. 15
is a schematic block diagram showing a configuration of error correction circuit
53
. Error correction circuit
53
is configured of a syndrome calculation circuit
54
provided for calculating a syndrome from data input, a Euclidean execution circuit
55
provided for obtaining an error location polynomial and an error estimation polynomial from a syndrome, a Chien search execution circuit
56
obtaining an error location and an error count value from an error location polynomial and an error estimation polynomial, and a correction circuit
57
providing a correction based on an error location and an error count value.
In the
FIG. 13
product-code block, for example, the horizontal, PI-system data is subjected to a calculation of a syndrome, a calculation of an error location polynomial and an error count value polynomial by means of a Euclidean method, and a calculation of an error location and an error value by means of a Chien search method, and on buffer memory
52
an error is corrected.
Then, the vertical, PO-system data is subjected to a calculation of a syndrome, a calculation of an error location polynomial and an error count value polynomial by means of a Euclidean method, and a calculation of an error location and an error value by means of a Chien search method, and on buffer memory
52
an error is corrected.
Such a process is repeated for each system to correct an error in an information symbol. If this error correction process is repeated more frequently, more errors can be corrected in general.
In the
FIG. 14
example, a buffer memory
52
comprises, for instance, a dynamic random access memory (D)RAM). Horizontal, PI-system data stored in the buffer memory
52
can be accessed in burst and thus read rapidly. However, vertical, PO-system data are accessed randomly and thus read in a long period of time, disadvantageously resulting in a reduced correction rate.
To overcome this disadvantage, there is provided a second conventional error correction device having a configuration illustrated in FIG.
16
, shown in a schematic block diagram.
As shown in
FIG. 16
, the second conventional error correction device has added thereto a storage element
58
formed of a static random access memory (SRAM) rapidly accessible for both of data in a vertical direction and data in a horizontal direction. In accessing horizontal, PI-system data stored in buffer memory
52
, the data of a product code block are all written to storage element
58
. More specifically, there is proposed that if the vertical, PO-system data is accessed, a product code block stored in storage element
58
is accessed to allow the vertical, PO-system data to also be accessed rapidly.
In the conventional example as shown in
FIG. 16
, however, storage element
58
corresponding to an SRAM is enormously increased in capacity, disadvantageously resulting in an increased circuit area and an increased power consumption.
SUMMARY OF THE INVENTION
The present invention contemplates an error correction device capable of rapid error correction while minimizing a storage element in capacity.
The present invention provides an error correction device including a first storage element, a first error correction operation circuit and a second error correction operation circuit.
The first storage element stores a product-code block having added thereto error correction codes provided in different directions. The first error correction operation circuit receives from the first storage element data in the product code block arranged in a first direction, and corrects an error in the first direction. The second error correction operation circuit receives from the first error correction circuit the data corrected by the first error correction circuit, and successively corrects an error in a second direction.
Thus the present invention can provide an error correction device capable of rapid error correction while minimizing circuit area and power consumption.


REFERENCES:
patent: 5920578 (1999-07-01), Zook
patent: 5974580 (1999-10-01

Affiliated with

Also associated with

Rating

Error correction 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 Error correction device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error correction device will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3316965