Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-03-20
2003-06-03
Chung, Phung M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S784000, C714S785000
Reexamination Certificate
active
06574771
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an error correcting apparatus, and more particularly, to a Galois field processor having a dual parallel data path for a Bose Chaudhuri Hocquenghem/Reed-Solomon (BCH/RS) decoder capable of improving the performance of a decoder using a dual data path in the BCH/RS decoder.
2. Description of the Related Art
With the development of digital technology, techniques for recovering from errors generated in channels or media have been developed. Various error correction techniques have been reported and developed. Among the techniques, a Bose Chaudhuri Hocquenghem/Reed-Solomon (BCH/RS) code, which is a type of linear block code, is most widely used due to its excellent error correction capability and efficient encoding and decoding procedures. The decoding procedure of the BCH/RS code is more complicated than its encoding procedure. As the number of systems which require high speed digital data processing increases, decoding hardware increasingly requires architecture in which high speed digital processing can be performed.
However, previously known decoding hardware architectures do not readily process data at speeds as high as required. The main functions of a BCH/RS decoder includes 1) calculating from a transmitted code a syndrome having information on the presence of errors, 2) calculating the coefficients of an error location polynomial from the calculated syndrome, 3) calculating the roots of the error location polynomial, 4) searching for an error value, and 5) recovering the error using the error location polynomial roots and the error value.
In this approach, calculating the roots of the error location polynomial requires the most complicated process and hardware. Therefore, this is typically regarded as the most important step in determining the high speed operation and the error correction ability of the BCH/RS decoder. Various approaches to performing this step have been reported. The Euclidian algorithm and the feedback shift register (FSR) synthesis algorithm suggested by Massey-Berlekamp are commonly used in no less than three symbols of multiple error correction. However, since a plurality of multipliers and long latency are required when the Euclidian algorithm is realized as hardware, the Massey-Berlekamp algorithm is commonly used when a high speed correction is required.
The number of multipliers and inverse circuits and the latency during execution processes also vary in the Massey-Berlekamp algorithm according to how the algorithm is realized. This significantly affects the size and the performance of the hardware.
SUMMARY OF THE INVENTION
To solve the above problem, it is an object of the present invention to provide a Galois field processor having a dual parallel data path for a Bose Chaudhuri Hocquenghem/Reed-Solomon (BCH/RS) decoder, which has a small area and operates at a high speed and where the latency during execution processes can be minimized.
Accordingly, to achieve the above object, there is provided a Galois field processor having a dual parallel data path for a Bose Chaudhuri Hocquenghem/Reed-Solomon (BCH/RS) decoder. The processor of the invention includes a syndrome register block having an even-degree syndrome register block for storing even-degree syndrome values from among the syndrome values transmitted by a syndrome generating block and an odd-degree syndrome register block for storing odd-degree syndrome values from among the syndrome values transmitted by the syndrome generating block. A correction polynomial register block includes an even-degree correction polynomial coefficient register block for receiving an even-degree coefficient output and storing even-degree coefficients of a correction polynomial, and an odd-degree correction polynomial coefficient register block for receiving an odd-degree coefficient output and storing odd-degree coefficients of the correction polynomial. A connection polynomial register block includes: (i) an even-degree modified connection polynomial coefficient register block for receiving the even-degree coefficient output and storing the even-degree coefficients of a modified connection polynomial, (ii) an odd-degree modified connection polynomial coefficient register block for receiving the odd-degree coefficient output and storing the odd-degree coefficients of the modified connection polynomial, (iii) an even-degree connection polynomial coefficient register block for receiving the even-degree coefficient output and the output of the even-degree modified connection polynomial coefficient register block and outputting the even-degree coefficients of a connection polynomial, and (iv) an odd-degree connection polynomial coefficient register block for receiving the odd-degree coefficient output and the output of the odd-degree modified connection polynomial coefficient register block and outputting the odd-degree coefficients of the connection polynomial. A discrepancy register block receives delta output and storing a discrepancy value for updating the connection polynomial so as to continuously generate syndromes equal to previously known syndromes. A dual mode Galois field data path (DMGFDP) includes a first data path for (i) receiving the respective outputs of the syndrome register block, the correction polynomial register block, the connection polynomial register block and the discrepancy register block, (ii) performing first predetermined operations related to the even-degree coefficients of the correction and connection polynomials, and (iii) outputting the even-degree coefficient result of the first predetermined operations. The DMGFDP also includes a second data path for (i) performing second predetermined operations related to the odd-degree coefficients of the correction and connection polynomials and (ii) outputting the odd-degree coefficient result of the second predetermined operations. The DMGFDP also includes a delta output unit for performing third predetermined operations related to the even-degree and odd-degree coefficients of the connection polynomial and outputting the delta output result of the third predetermined operations. An output unit synthesizes the output of the even-degree connection polynomial coefficient register block with the output of the odd -degree connection polynomial coefficient register block and outputs the synthesis results as the coefficients of an error location polynomial, according to a control signal.
In one embodiment, the first data path includes a first register fetch unit which includes: (i) a first input register for selecting, storing and outputting one of the output of the discrepancy register block, the output of the even-degree connection polynomial coefficient register block, and the data of a first bypass bus, (ii) a second input register for selecting, storing and outputting one of the output of the discrepancy register block and the output of the even-degree syndrome register block, and (iii) a third input register for selecting, storing and outputting one of the output of the even-degree correction polynomial coefficient register, the output of the even-degree connection polynomial coefficient register block, and the output of the odd-degree connection polynomial coefficient register block. A first execute unit includes a first multiplier for multiplying the output of the second input register with the output of the third input register and a first adder for adding the output of the first input register to the output of the first multiplier. A first output register selects and stores one of the output of the first multiplier and the output of the first adder and outputs the selected one of the output of the first multiplier and the output of the first adder as the even-degree coefficient output, and provides input data to the first input register through the first bypass bus.
In one embodiment, the second data path includes a second register fetch unit which includes (i) a fourth input register for receiving, storing, and outputting the output of the odd-deg
Chung Phung M.
Mills & Onello LLP
Samsung Electronics Co,. Ltd.
LandOfFree
Galios field processor having dual parallel data path for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Galios field processor having dual parallel data path for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Galios field processor having dual parallel data path for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3103836