Abstract:
An error correction device includes: a decoding unit, coupled to a main memory, for reading data from the main memory and performing an error detection on the data to generate a plurality of error values and a plurality of error addresses corresponding to the error values; an error buffer, coupled to the decoding unit, for temporarily storing the error values and the error addresses; an error classifying unit, coupled to the error buffer, for selecting a subclass according to the error address, wherein the subclass includes a plurality of specific error values and a plurality of specific error addresses corresponding to the specific error values; and an error correction unit, coupled to the error classifying unit and the main memory, for performing an error correction on the data stored in the main memory according to the specific error values and specific error addresses.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     1. Field of the Invention  
         [0002]     The invention relates to an error correction device and method thereof, and more particularly, to an error correction device and method capable of improving the efficiency of the system memory.  
         [0003]     2. Description of the Prior Art  
         [0004]     In general, when reading data from a DVD disc, the data in the DVD disc are first read by the pickup head of an optical disc drive. Then, the analog signal processor transforms the analog signals generated by the pickup head into digital signals, (e.g., eight-to-fourteen modulation signals). The eight-to-fourteen modulation signals are then processed by an EFM+ demodulator to form row data. Finally, these row data are stored in a memory.  
         [0005]     Please refer to  FIG. 1 , which is a block diagram of a conventional DVD error correction device  100 . As shown in  FIG. 1 , the error correction device  100  comprises a decoding unit  110  and an error correction unit  120 . In this case, the error correction unit  120  is coupled to the decoding unit  110 , and both the decoding unit  110  and the error correction unit  120  access data in the memory  130  through a bus  140 . When the data, which are written into the memory  130 , are sufficient to form an error correction code block (ECC block), the decoding unit  110  (e.g., a Reed Soloman Product-like Code (RSPC) decoder) reads the data from the memory  130  through the bus  140  and performs an inner-code parity (PI) decoding operation on the data. Then, the decoding unit  110  passes error addresses and error values to the error correction unit  120  according to the Pi decoding results. The error correction unit  120  performs calculation according to the error values and the error addresses, such that the error correction unit  120  can correct some errors of the data stored in the memory  130  through the bus  140 .  
         [0006]     Subsequently, the decoding unit  110  again reads the data from the memory  130  through the bus  140  and performs an outer-code parity (PO) decoding operation on the data. Then, the decoding unit  110  passes error addresses and error values to the error correction unit  120  according to the PO decoding results. The error correction unit  120  performs calculation according to the error values and the error addresses, such that the error correction unit  120  can again correct some errors of the data stored in the memory  130  through the bus  140 . After some repetitions, the data of the DVD, which are stored in the memory  130 , can be completely corrected for following use.  
         [0007]     Please refer to  FIG. 2 , which is a diagram of a typical ECC block  200 . As shown in  FIG. 2 , the ECC block  200  is a 182 byte×208 byte block, where in the Pi direction (the horizontal direction) it has 182 bytes and in the PO direction (the vertical direction) it has 208 bytes. Please note that a row in the Pi direction is called a Pi codeword, and a column in the PO direction is called a PO codeword. In addition, the Pi and PO regions represent different correction codes. As mentioned previously, the Pi and PO are utilized by the decoding unit  110  to correct the errors of the DVD data.  
         [0008]     However, the memory  130  is often implemented by a dynamic random access memory (DRAM). It is well known that when the DRAM  130  accesses data, if a change row operation needs to be performed, additional memory clocks must be consumed to perform some additionally operations (e.g., row activating and row pre-charging operations). However, when the ECC block  200  is being stored into the memory  130 , the data are written in the Pi direction (e.g., as the above-mentioned row data). In order to illustrate more clearly, please refer to  FIG. 3 , which is a diagram of mapping between the logical structure of the ECC block  200  and the physical addressing of the memory  130 . As shown in  FIG. 3 , the data of the ECC block  200  are row-by-row written into continuous positions of the memory  130 . Because one Pi codeword corresponds to 182 bytes, the Pi codeword at most occupies two rows of the DRAM  130 , due to its 1024-byte row width. Therefore, when the Pi decoding operation is performed to execute the data correction operation, it is not necessary that the above-mentioned change row operation be performed for so many iterations. But, when the PO decoding operation is performed to execute the data correction operation, because data of a PO codeword is bound to distribute among multiple rows of the DRAM  130 , the change row operation is performed many times. Obviously, frequent change row operations occupy many memory clock periods and result in poor efficiency of the memory  130 .  
       SUMMARY OF THE INVENTION  
       [0009]     It is therefore one of the objectives of the claimed invention to provide an error correction and method thereof capable of improving the utilization efficiency of the system memory.  
         [0010]     According to an exemplary embodiment of the claimed invention, an error correction device is disclosed. The error correction device comprises: a decoding unit, coupled to a main memory, for reading a data from the main memory and performing an error detection on the data to generate a plurality of error values and a plurality of error addresses corresponding to the error values; an error buffer, coupled to the decoding unit, for temporarily storing the error values and the error addresses; an error classifying unit, coupled to the error buffer, for selecting a subclass according to the error address, wherein the subclass includes a plurality of specific error values and a plurality of specific error addresses corresponding to the specific error values; and  
         [0011]     an error correction unit, coupled to the error classifying unit and the main memory, for performing an error correction on the data stored in the main memory according to the specific error values and specific error addresses.  
         [0012]     According to another exemplary embodiment of the claimed invention, an error correction method is disclosed. The error correction method comprises: reading a data from a main memory and performing an error detection on the data to generate a plurality of error values and error addresses corresponding to the plurality of error values; temporarily storing the plurality of error values and the plurality of error addresses; selecting a subclass from the plurality of error addresses, wherein the subclass comprises a plurality of specific error values and a plurality of specific error addresses corresponding to the plurality of specific error values; and performing an error correction on the data stored in the main memory according to the specific error values and specific error addresses.  
         [0013]     These and other objectives of the present invention will no doubt become obvious to those of ordinary skill in the art after reading the following detailed description of the preferred embodiment that is illustrated in the various figures and drawings. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0014]      FIG. 1  is a block diagram of a conventional DVD error correction device.  
         [0015]      FIG. 2  is a diagram of a typical ECC block.  
         [0016]      FIG. 3  is a diagram of mapping between the logical structure of the ECC block shown in  FIG. 2  and the physical addressing of the memory shown in  FIG. 1 .  
         [0017]      FIG. 4  is a block diagram of a DVD error correction device according to an embodiment of the present invention.  
         [0018]      FIG. 5  is a flow chart illustrating the operation of the error correction device according to an embodiment of the present invention.  
         [0019]      FIG. 6  is a diagram of the error classifying unit and the error buffer shown in  FIG. 4 . 
     
    
     DETAILED DESCRIPTION  
       [0020]     Please refer to  FIG. 4 , which is a block diagram of a DVD error correction device  400  according to an embodiment of the present invention. As shown in  FIG. 4 , the error correction device  400  comprises a decoding unit  410 , an error buffer  420  coupled to the decoding unit  410 , an error classifying unit  430  coupled to the error buffer  420 , and an error correction unit  440  coupled to the error classifying unit  430 . In addition, the decoding unit  410  and the error correction unit  440  are coupled to the memory  450  through the bus  460  in order to access data of the memory  450 . The functions and the operations of the error correction device  400  are illustrated in the following disclosure.  
         [0021]     Please refer to  FIG. 5 , which is a flow chart illustrating the operation of the error correction device  400  according to an embodiment of the present invention. The flow comprises following steps:  
         [0022]     Step  500 : The decoding unit  410  reads an ECC block from the memory  450  and performs a Pi or PO decoding operation to determine a plurality of error values and a plurality of error addresses corresponding to the plurality of error values;  
         [0023]     Step  510 : The error buffer  420  receives the error values and error addresses and temporarily stores the error values and error addresses;  
         [0024]     Step  520 : The error classifying unit  430  selects a subclass from the error addresses; and  
         [0025]     Step  530 : The error correction unit  440  corrects the errors of the data stored in the memory  450  according to the subclass.  
         [0026]     In this embodiment, first, the decoding unit  410  reads an ECC block from the memory  450  through the bus  460  and performs the above-mentioned Pi or PO decoding operation on the ECC block. Because the disc data stored in the memory  450  may contain many errors, the decoding unit  410  can perform the Pi or PO decoding operation to determine the error values and corresponding error addresses according to the decoding results (step  500 ).  
         [0027]     Then, the decoding unit  410  temporarily stores the error values and error addresses into the error buffer  420  (step  510 ). When the amount of the error values and the error addresses, which are written into the error buffer  420 , reaches a threshold, the error classifying unit  430  performs a classifying operation according to the row addresses of the memory  450  that corresponds to the error addresses. For example, the error classifying unit  430  can gather the error addresses, which correspond to a same row of the memory  450 , in a subclass. Therefore, multiple subclasses are determined. Then, these subclasses are outputted to the error correction unit  440  (step  520 ).  
         [0028]     Lastly, the error correction unit  440  can correct errors of the DVD disc data stored in the memory  450  according to the error values and errors addresses in the subclasses (step  530 ). As is known, the error correction unit  440  utilizes error values and error data stored in the error addresses of the memory  450  to perform certain logical or arithmetic operation (for example, an XOR operation) on the error values and error data to recover correct data. Then, the correct data are written into the error addresses of the memory  450  through the bus  460  in order to overwrite the original error data stored in the memory  450 , such that the goal of error correction can be achieved.  
         [0029]     Because the error addresses of a specific subclass correspond to the same row of the memory  450 , when the error correction unit  440  corrects the errors according to the error addresses of the specific subclass, there is no need to perform the aforementioned change-row operations, and time consuming actions such as repetitive activating and pre-charging operations of the memory can be avoided. Only when the error correction of one subclass is completely through, a change row operation of the memory  450  is required for the error correction unit  440  to perform error correction of another subclass. In other words, the potentially once every error correction of occurrence of change row operation in the conventional art can be dramatically reduced to once every subclass, because the error addresses corresponding to the same row are well classified into subclasses, as described in the above embodiment. This can save the operational time of the memory  450 , and the efficiency of the memory  450  can be increased.  
         [0030]     Please note, in order to optimize the utilization of the error correction device  400 , the error correction device  400  can be designed such that when the decoding unit  410  decodes a predetermined amount of data, or the number of the error addresses stored in the error buffer  420  reaches a predetermined number, the error classifying unit  430  is activated to start classifying the error addresses stored inside the error buffer  420 . Of course, the error correction device  400  can be also designed such that only when all error addresses are determined, the error classifying unit  430  is utilized to classify all the error addresses. Indeed, such operations can ensure that the change-row operation is minimized. However, this requires a huge storage space of the error buffer  420 . In other words, under this setting, the error buffer  420  needs to have the capacity for storing all error addresses.  
         [0031]     For example, assume that the ECC block is stored into contiguous positions of the memory  450  row by row in the Pi direction. Please refer to  FIG. 6 , which is an embodiment diagram of the error classifying unit  430  and the error buffer  420  shown in  FIG. 4 . As shown in  FIG. 6 , the error classifying unit  430  comprises a buffer column pointer array  431 , a buffer row pointer  432 , an error buffer addressing device  433 , and a classifying determiner  434 . The error buffer addressing device  433  is coupled to the buffer column pointer array  431  and the buffer row pointer  432 , and is utilized to perform the addressing operation on the error buffer  420 , so that in subsequent operations, the error values and the error addresses stored in the error buffer  420  can be accessed smoothly.  
         [0032]     Then, when the error correction operation is to be performed, the classifying determiner  430  reads the error values and error addresses stored in the error buffer  420  and classifies the error addresses according to their corresponding row of the memory  450 . As mentioned previously, the classifying determiner  430  can continuously output error values and error addresses corresponding to the same row for the error correction unit  440  to perform the error correction operation on the data of the memory  450 . Alternatively, the classifying determiner  430  can more coarsely classify the error addresses stored in the error buffer  420 . For example, the classifying determiner  430  can classify the error addresses stored in the error buffer  420  according their addresses of the memory  450  as multiple subclasses, each collecting four rows of addresses of the memory  450 . Then, when the error correction operation is being performed, the classifying determiner  430  outputs the subclasses such that the error correction unit  440  can correct the data of the memory  450 . Because the addresses in a subclass still to certain degree correlate with one another, the change-row operations can be saved when the error correction operation is being performed.  
         [0033]     In the following disclosure, an embodiment is used to illustrate the function and efficiency of the present invention. However, the amounts and the error correction method in the following disclosure only serve as an example, but not a limitation of the present invention.  
         [0034]     Please note, in this embodiment, it is assume that the PO decoding operation can at most correct 16 errors at one time, and the error buffer can temporarily store 256 error values and error addresses. In other words, the error buffer  420  is sufficient to store 16 PO codewords and the row width of the memory  450  is 1024 bytes (i.e., one row of the memory  450  can store 1024 bytes).  
         [0035]     First, because all errors contained in 16 PO codewords will not exceed 256 error values and error addresses, all errors can be stored inside the error buffer  420 , which, in this embodiment, is a 16 byte×16 byte array. Furthermore, in this embodiment, the error classifying unit  430  is designed to gather every 16 rows of the ECC block as a subclass, therefore totaling 13 subclasses.  
         [0036]     In other words, when the error correction operation is being performed, the error classifying unit  430  sequentially finds out the errors stored in the error buffer  420  corresponding to each subclass, preferably by identifying specific error addresses. Then, the error classifying unit  430  transfers the errors to the error correction unit  440 . Therefore, the error correction unit  440  performs the error correction operation on the data of the memory  450  according to the outputted subclass. Notably, because the decoding unit  410  determines the errors in a column of the ECC block and stores them into the error buffer  420  in the order of these errors locating in said buffer, a full search of the error buffer  420  is not required when the error classifying unit  430  determines a subclass from the errors stored in the error buffer  420 . For each row of the error buffer  420 , which, in this embodiment, stores errors found in the same column of the ECC block, once the error classifying unit  430  identifies an error address outside the subclass currently under search, the search for this row of the error buffer  420  ends, leaving the rest of the error(s) in this row un-searched, and the search for the next row of the error buffer  420  starts. By doing so the search effort by the error classifying unit  430  can be further saved.  
         [0037]     Because each subclass corresponds to 16 rows of the ECC block, which translates into 2912 bytes of data and occupies at most 4 memory rows, in this embodiment only four change-row operations, at most, are needed for error correction of each subclass. Consequently, at most 4*1 3=52 change-row operations are needed for error correction of the entire error buffer  420 .  
         [0038]     Averagely speaking, an ECC block roughly contains errors with the amount of 11.35 error buffers  420 . Therefore, roughly 52*12=624 change-row operations are needed for correcting all errors. In contrast to the conventional art, where in the worst case 1 6*1 82=2912 change-row operations may be needed, the present invention obviously has higher memory efficiency.  
         [0039]     Please note, the above-mentioned error correction method is not limited to uses beneficiary to the error correction in the PO direction. In practice, the error correction method can also used in the error correction in the Pi direction. Assuming that the Pi decoding operation can at most correct 10 errors at one time, and the error classifying unit  430  gathers 5 Pi codewords as a subclass before transferring the subclasses to the error correction unit  440 , then because five Pi codewords translates into 910 bytes, which is less than the row width of the memory  450 , a subclass at most occupies two memory rows. In other words, at most two change-row operations are needed for correcting errors of a subclass. Consequently, at most 2*42=84 change-row operations are needed for correcting errors of the entire ECC block. In contrast to the conventional art, where in the worst case 208*2=416 change-row operations may be needed, the present invention obviously has higher memory efficiency.  
         [0040]     Therefore, one can alter the size of the storage spaces of the error buffer  420  and the timing of activating the error classifying unit  430  according to design choice, and still conforms to the spirit of the present invention. In addition, as is well known, the error correction device  400  mentioned in the above disclosure and the components thereof can be realized by ASICs, processors cooperating with firmware or software program codes, or a combination of the two, and still conforms to the spirit of the present invention.  
         [0041]     Please note, in the above disclosure, the present invention error correction device and related method thereof are applied in the field of DVD data extraction. However, the present invention can be applied in any field of technology that implements memory error correction. In other words, the aforementioned DVD application serves only as a preferred embodiment, but not a limitation, of the present invention.  
         [0042]     As is made clear by the above disclosure, the present invention can gather error addresses corresponding to the same memory row address, and sequentially handle the error addresses corresponding to the same memory row address. Therefore, the present invention can reduce the amount of the change-row operations of the DRAM. This saves the consumed memory clocks of change-row operations so that the memory efficiency is increased.  
         [0043]     Those skilled in the art will readily observe that numerous modifications and alterations of the device and method may be made while retaining the teachings of the invention. Accordingly, the above disclosure should be construed as limited only by the metes and bounds of the appended claims.