Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-12-08
2001-01-16
Moise, Emmanuel L. (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S762000, C714S768000, C714S785000, C708S492000
Reexamination Certificate
active
06175941
ABSTRACT:
The present invention relates generally to a manner by which to correct errors contained in digital data, such as the data forming elements of a block of block-encoded data. More particularly, the present invention relates to apparatus, and an associated method, for performing error correction upon a block of block-encoded data.
Operation of an embodiment of the present invention provides both the speed-advantages associated with hardware-implemented error-correction apparatus and also the flexibility associated with software-implemented error-correction apparatus. That is to say, an embodiment of the present invention exhibits the speed of a hardware implementation, and also the adaptability associated with a software implementation.
In one implementation, error correction is provided for blocks of data retrieved from a data storage and transmission system in which data stored at a computer mass storage device, such as a disk drive or the like, is retrieved during system operation. The data blocks are encoded by Reed-Solomon ECC (error correcting code). Effectuation of error correction is provided by two ALUs (arithmetic logic units) operating in parallel. The ALUs are at least selectively provided with instructions retrieved by a sequencer from a memory device. Instructions stored in the memory device are replaceable to provide for system flexibility while the parallel operation of the ALUs provide for high-speed error-correction operations.
BACKGROUND OF THE INVENTION
Advancements in digital technologies have permitted the development, and implementation, of many new products. Products pertaining to, and including, digital processing circuitry, are exemplary of products possible as a result of such advancements.
Repetitive functions can be carried out by digital processing circuitry at rates significantly more rapidly than the manual performance of such functions. The rapid rate at which the digital processing circuitry is able to repeatedly perform such functions has permitted activities, previously considered impractical, to be readily implementable.
Processing of large amounts of data is, e.g., advantageously effectuated through the use of a product, including, or formed of, digital processing circuitry. For instance, in a computer system, data is transferred between peripheral devices and a CPU (central processing unit). In processing of the data, data is read from, or written to, data storage locations in successive read and write operations.
The data that is processed is in digital form. That is to say, the data is stored in the form of binary bits. The binary bits forming the data are transferred when reading or writing the data to effectuate the processing operations. Errors are sometimes introduced during the transfer of the data. The errors are introduced as a result of, for example, channel distortion or noise. The effects of the data storage locations at which the data is stored can also introduce errors into the data.
To ensure data integrity, the errors in the data must typically be corrected. Encoding techniques are sometimes utilized to encode data prior to its transfer. Such encoding of the data facilitates error correction of the data, subsequent to its transfer. Decoding of the data is performed to recreate the value of the data prior to its encoding and transfer.
Various encoding schemes have been developed and used to encode data. Block-encoding schemes by which blocks of digital data are encoded, for example, are oftentimes utilized in mass storage systems. Reed-Solomon coding is exemplary of a block-encoding scheme sometimes utilized to encode digital data. Standardized encoding schemes have been set forth, for instance, for the encoding of blocks of data stored on the optical storage devices, such as CD-ROM storage devices. In such storage devices, data is formatted into blocks formed of two-dimensional arrays of data. The blocks of data include ECC (error correction code) as a portion thereof. The ECC is utilized during error-correction operations to detect data errors contained in the block of data.
Error-correction operations however, are computationally-intensive. As products and systems in which data is transferred cause data transfer to be effectuated at quicker rates, the rates at which error-correction operations must be performed correspondingly must be increased. Some conventional error-correction operations are performed by execution of the ECC error-correction algorithms by a general-purpose microprocessor or a specialized, ECC-processor. The use of software algorithms to effectuate ECC error-correction operations permit system flexibility as the software algorithms can be substituted with others depending upon the error-correction operations to be performed. That is to say, software implementations of ECC operations are easily alterable, or replaceable. But, execution of a software algorithm is inherently serial. Rates at which error-correction operations utilizing conventional software algorithms, executable by processors, are relatively slow because of the necessary, serial execution of the algorithms.
Other, conventional ECC operations are hardware-implemented. That is to say, dedicated hardware is provided to implement error-correction operations. Such hardware implementations are more readily able to perform error-correction operations at high data rates. But, hardware implementations are not adaptable to changes.
Conventional, software-implemented error-correction apparatus and methods, while advantageously flexible, are relatively slow. And, conventional, hardware-implemented error-correction apparatus and methods, while relatively fast, are relatively inflexible.
A manner by which to utilized the advantages of both software- and hardware-implemented error-correction apparatus and methods would therefore be advantageous.
It is in light of this background information related to error-correction operations that the significant improvements of the present invention have evolved.
SUMMARY OF THE INVENTION
The present invention, accordingly, advantageously provides apparatus, and an associated method, for performing error correction upon a block of block-encoded data.
An embodiment of the present invention advantageously provides both the speed-advantages associated with hardware-implemented error-correction operations and also the flexibility associated with software-implemented error-correction operations. Thereby, a manner is provided by which to effectuate error-correction operations at increased rates while also permitting flexibility to permit alteration in the manner by which error-correction operations are performed.
In an exemplary implementation, error correction is provided for blocks of data retrieved from a data storage and transmission system, such as a system in which data stored at a CD-ROM device is retrieved during system operation. Each of the blocks of data are encoded utilizing an ECC (error correction code), e.g., a Reed-Solomon, RS1, ECC. Error-correction operations are performed by two ALUs (arithmetic logic units) operating in parallel and together in conjunction with a sequencer. The sequencer retrieves instructions from a memory device and provides such instructions to the ALUs, at least selectively, thereby to effectuate error-correction operations. By operating the two ALUs in parallel, error-correction operations are effectuated quickly. And, because instructions determinative of operation of the ALUs stored in the memory device are replaceable, system flexibility is provided.
In these and other aspects, therefore, apparatus, and an associated method, error-corrects a block digital data encoded according to a selected encoding technique. A finite-field ALU is coupled selectively to receive an error-location indication and an error-syndrome indication. The finite-field ALU performs finite-field mathematical calculations. An integer ALU is operable in parallel with the finite-field ALU. The integer ALU performs address calculations such as to determine the addresses of errors in a buffer and to determine add
Poeppelman Alan D.
Rutherford Mark D.
LSI Logic Corporation
Moise Emmanuel L.
LandOfFree
Error correction apparatus and associated method utilizing... 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 apparatus and associated method utilizing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error correction apparatus and associated method utilizing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2536881