Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-08-21
2004-06-29
Ton, David (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S759000
Reexamination Certificate
active
06757862
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to a method and apparatus for error correction coding of digital data. The invention has application, for example, in data storage and retrieval systems such as disk drives and flash memory.
BACKGROUND OF THE INVENTION
In digital data storage and retrieval systems such as disk drives and flash memory systems it is common to include error detection and correction capabilities, for example utilizing an error correction code (ECC) or the like. Such error detection and correction provides a degree of fault tolerance for the data storage and retrieval system, which is particularly useful where increasing operating speeds and storage densities can in some circumstances increase the rate likelihood of data reading and/or writing errors.
One way of providing an error detection and correction capability involves arranging the digital data into data blocks and generating a code (e.g. an ECC) for each block from the data in that block. The code is generated so that a change to the data in the data block will result in a different code value if a subsequent code is generated from the changed data. A first code value is generated from the data prior to an operation such as writing the data to storage, and a second code value is generated from the data when it is read from the storage, for example. A comparison of the first and second code values will then indicate whether any change to the data had occurred during the writing/storage/reading operation. Typically the first code is stored along with the data block so it is available for comparison with the second code value generated from the retrieved data. A difference between the first and second code values indicates that an error has occurred during the operation(s) carried out between the generation of the two code values, and the error has resulted in an alteration to the data in the data block.
Many error detection systems use coding which is generated from the parity of the data in the data block, and portions thereof Preferably the code is generated and structured to also allow correction of certain types of errors, which is an error correction code (ECC), rather than simply an error detection code. An ECC typically enables detection of an error in a data block, and in the case of a single bit error (SBE) identification of the position of the erroneous bit in the block. Therefore, if a single bit error occurs, the use of a typical ECC enables detection of the error and the position thereof, allowing the erroneous bit to be corrected (toggled). It is possible to provide error correction coding to allow for correction of multiple bit errors, however for most applications the computational and storage overhead for such coding is considered unnecessary.
In addition to computational and storage overhead, another consideration for optimal error correction coding is the time required to generate and compare the codes at the time of reading the data. Commonly used ECC systems require the entire data block to be retrieved before the ECC generating algorithm can be initiated. In this case, the entire time required to generate and check the ECC must be added to the data retrieval time before the data block is available for use. It is preferable if the ECC can be generated whilst the data of the data block is being retrieved, particularly in the case of data retrieval systems which are serial in nature.
SUMMARY OF THE INVENTION
In accordance with the principles of the present invention, there is provided a method for determining an error correction code for a block of digital data comprising a sequence of data units. The method first initializes the error correction code and then, for each data unit in the sequence, performs first and second operations on the error correction code according to the value of the data unit and the sequence position of the data unit.
The error correction code determination method builds the error correction code using one data unit (e.g. one byte) at a time from the data block, and is therefore adapted for use with systems in which the data block may be supplied serially.
The first and second operations can be performed with the use of pre-generated lookup tables. The lookup tables are adapted for the size of data unit and sequence length of the data block.
In one form of the invention, the first operation comprises determining whether a given data unit value has an odd or even parity and, according to the parity determination, modifying the error correction code using a first mask word determined according to the sequence position of the given data unit. The first mask word can be obtained from a first predetermined lookup table using the sequence position of the given data unit.
The second operation may comprise modifying the error correction code using a second mask word obtained from a second predetermined lookup table according to the value of the given data unit.
Preferably the error correction code is modified using exclusive-OR operations with the first and second mask words.
Preferably the parity of the given data unit value is determined using a third predetermined lookup table.
In a preferred form of the invention, the first operation comprises determining the parity of the given data unit using the third lookup table and, if the given data unit parity is of a first value, obtaining a first mask word from the first predetermined lookup table corresponding to the given data unit sequence position, and modifying the error correction code by performing an exclusive-OR operation with the first mask word.
The present invention also provides an error correction code generator for generating an error correction code for a data block comprising a sequence of data units. The error correction code generator includes a first stored lookup table having first mask words representing a correspondence between each possible data unit sequence position of the data block and bit modifications for the error correction code. The error correction code generator also includes a second stored lookup table having second mask words representing a correspondence between each possible data unit value and bit modifications for the error correction code. The error correction code generator further includes a data processor coupled to access the first and second lookup tables and coupled to receive the sequence of data units comprising the data block. The data processor is operative to initialize the error correction code and, for each data unit in the data block sequence, modify the error correction code utilizing the first and second lookup tables.
Preferably, for each data unit in the data block sequence, the data processor determines the parity of the data unit and, if the given data unit parity is of a first value, obtains a first mask word from the first stored lookup table corresponding to the given data unit sequence position, and modifies the error correction code by performing an exclusive-OR operation with the first mask word.
The error correction code generator preferably also includes a third stored lookup table comprising a correspondence between parity values and each possible data unit value, the data processor being coupled to access the third stored lookup table, wherein the data processor determines the parity of each data unit of the data block by consulting the third lookup table using the value of the data unit.
Preferably, for each data unit in the data block sequence, the data processor obtains a second mask word from the second stored lookup table, and modifies the error correction code by performing an exclusive-OR operation with the second mask word.
The present invention further provides a method for generating an error correction code for a data block comprising a sequence of data units, the method comprising:
initializing the error correction code; and
for each data unit in the data block sequence:
performing a first modification to the error correction code utilizing a first stored lookup table having first mask words representing a correspondence between
Handspring, Inc.
Stattler Johansen & Adeli LLP
Ton David
LandOfFree
Method and apparatus for digital data error correction coding 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 digital data error correction coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for digital data error correction coding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3364931