Error correction code circuit with reduced hardware complexity

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
6Forward
Citations 
0
Petitions 
3
Assignments
First Claim
1. A processing circuit of a microprocessor for processing an input data to generate an output data, the microprocessor comprising a Galois field multiplier electrically connected to the processing circuit for, performing a Galois field multiplication upon a plurality of processing data being processed by the processing circuit, the processing circuit comprising:
 a first register for storing the input data;
a plurality of processing units each being cascaded in series, a starting processing unit of the processing units electrically connected to the first register, each processing unit comprising an input port, an output port, a Galois field adder electrically connected between the input port and the output port, and a second register electrically connected to the Galois field adder; and
a controller for controlling operation of the processing circuit;
wherein the controller controls each processing unit to transmit processing data requiring Galois field multiplication to the Galois field multiplier, and the processing data outputted from the Galois field multiplier are transmitted back to each corresponding processing unit.
3 Assignments
0 Petitions
Accused Products
Abstract
An error correction code circuit with reduced hardware complexity is positioned inside a microprocessor. The microprocessor has a Galois field multiplier for performing a Galois field multiplication on data processed by the error correction code circuit. The error correction code circuit has a first register for storing an input data, a plurality of calculation units, a third register for storing an output data corresponding to the input data, and a controller for controlling operation of the error correction code circuit. Each calculation unit has a Galois field adder, and a second register electrically connected to the Galois field adder. The controller transmits data of each calculation unit to the same Galois field multiplier for a corresponding Galois field multiplication, and the result outputted by the Galois field multiplier is transmitted back to the error correction code circuit.
16 Citations
View as Search Results
Parallel finite field vector operators  
Patent #
US 8,347,192 B1
Filed 03/08/2010

Current Assignee
Altera Corporation

Sponsoring Entity
Altera Corporation

ERROR CORRECTION CIRCUIT AND MEMORY SYSTEM INCLUDING THE SAME  
Patent #
US 20190042360A1
Filed 03/27/2018

Current Assignee
SK Hynix Inc.

Sponsoring Entity
SK Hynix Inc.

BITFLIPPING DECODER FOR GLDPC CODES WITH SYNDROMEDECODING FOR COMPONENT CODES  
Patent #
US 20190068219A1
Filed 03/09/2018

Current Assignee
SK Hynix Inc.

Sponsoring Entity
SK Hynix Inc.

Processor for realizing at least two categories of functions  
Patent #
US 10,372,359 B2
Filed 05/10/2017

Current Assignee
ChengDu HaiCun IP Technology LLC

Sponsoring Entity
ChengDu HaiCun IP Technology LLC

Configurable processor with inpackage lookup table  
Patent #
US 10,445,067 B2
Filed 11/28/2018

Current Assignee
Hangzhou Haicun Information Technology Co. Ltd.

Sponsoring Entity
Hangzhou Haicun Information Technology Co. Ltd.

Bitflipping decoder for GLDPC codes with syndromedecoding for component codes  
Patent #
US 10,707,899 B2
Filed 03/09/2018

Current Assignee
SK Hynix Inc.

Sponsoring Entity
SK Hynix Inc.

Shared galois field multiplier  
Patent #
US 6,701,336 B1
Filed 11/12/1999

Current Assignee
Maxtor Corporation

Sponsoring Entity
Maxtor Corporation

Forward error correction apparatus and methods  
Patent #
US 6,725,416 B2
Filed 02/04/2003

Current Assignee
Avago Technologies International Sales Pte Limited

Sponsoring Entity
LSI Logic Corporation

Arithmetic processor for finite field and module integer arithmetic operations  
Patent #
US 6,349,318 B1
Filed 10/14/1999

Current Assignee
Certicom Corporation

Sponsoring Entity
Certicom Corporation

Configurable encoder and method for generating a ReedSolomon codeword  
Patent #
US 6,353,909 B1
Filed 05/11/1999

Current Assignee
Ikanos Communications Incorporated

Sponsoring Entity
Globespan Virata Inc.

Reedsolomon coding device and method thereof  
Patent #
US 6,378,104 B1
Filed 10/30/1997

Current Assignee
Texas Instruments Inc.

Sponsoring Entity
Texas Instruments Inc.

Programmable, reconfigurable DSP implementation of a ReedSolomon encoder/decoder  
Patent #
US 6,385,751 B1
Filed 12/15/1999

Current Assignee
Texas Instruments Inc.

Sponsoring Entity
Texas Instruments Inc.

Apparatus for providing error correction data in a digital data transfer system  
Patent #
US 6,173,429 B1
Filed 03/14/1997

Current Assignee
TRW Limited

Sponsoring Entity
Harris Corporation

Errors and erasures correcting reedsolomon decoder  
Patent #
US 5,715,262 A
Filed 07/12/1995

Current Assignee
Avago Technologies General IP PTE Limited

Sponsoring Entity
LSI Logic Corporation

Apparatus for determining error evaluator polynomial for use in a ReedSolomon decoder  
Patent #
US 5,787,100 A
Filed 02/28/1997

Current Assignee
WiLAN Inc.

Sponsoring Entity
Daewoo Electronics

Apparatus for computing error correction syndromes  
Patent #
US 5,805,617 A
Filed 11/25/1996

Current Assignee
Daewoo Electronics

Sponsoring Entity
Daewoo Electronics

17 Claims
 1. A processing circuit of a microprocessor for processing an input data to generate an output data, the microprocessor comprising a Galois field multiplier electrically connected to the processing circuit for, performing a Galois field multiplication upon a plurality of processing data being processed by the processing circuit, the processing circuit comprising:
a first register for storing the input data; a plurality of processing units each being cascaded in series, a starting processing unit of the processing units electrically connected to the first register, each processing unit comprising an input port, an output port, a Galois field adder electrically connected between the input port and the output port, and a second register electrically connected to the Galois field adder; and a controller for controlling operation of the processing circuit; wherein the controller controls each processing unit to transmit processing data requiring Galois field multiplication to the Galois field multiplier, and the processing data outputted from the Galois field multiplier are transmitted back to each corresponding processing unit.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
 13. A data processing method of a microprocessor, the microprocessor comprising:
a processing circuit for processing an input data to generate an output data, the processing circuit comprising; a first register for storing the input data; a plurality of processing units each being cascaded, a beginning processing unit of the processing units electrically connected to the first register, each processing unit comprising an input port, an output port, a Galois field adder electrically connected between the input port and the output port, and a second register electrically connected to the Galois field adder; and a controller for controlling operation of the processing circuit; and a Galois field multiplier electrically connected to the processing circuit for performing Galois field multiplication upon a plurality of processing data handled by the processing circuit; the data processing method comprising; controlling each processing unit to transmit processing data required the Galois field multiplication to the Galois field multiplier, and transmitting the processing data outputted from the Galois field multiplier back to each corresponding processing unit.  View Dependent Claims (14, 17)
 15. The data processing method of claim 15 wherein the microprocessor is used for processing a ReedSolomon error correction code that has a plurality of symbols.
1 Specification
1.Field of the Invention
The present invention relates to an error correction code (ECC) circuit, and more particularly, to an ECC circuit with reduced hardware complexity.
2.Description of the Prior Art
An error correction code (ECC) has been widely used to prevent digital data from being affected by noise interference. For example, the error correction code such as a wellknown ReedSolomon code is applied to a broad spectrum of fields. Digital communication systems such as a mobile communication system, and a satellite communication system, as well as digital data storage devices such as the optical disk use the error correction code to confirm accuracy of the transmitted data and to correct error bits of the transmitted data. Please refer to
Please refer to
R(x)=Q(x)*G(x)=I(x)·X^{n−k}+r(x)=I(x)·X^{n−k}+I(x)·mod·G(x)
The “mod” shown in the above equation stands for a modulo division. The degree of the generator polynomial G(x) is n, that is, the generator polynomial G(x) corresponds to n roots. The generator polynomial G(x) is represented by the following equation.
where α^{i }corresponds to an element in the Galois field GF(2^{8}).
Therefore, when each root α^{i }is applied to the above equation, the remainder is equal to 0. However, if the code word 16 contains error data E(x), the polynomial R(x) becomes the following equation.
R(x)=Q(x)*G(x)+E(x)
It is obvious that if each root α^{i }is applied to the above equation, the remainder corresponding to each root will not be equal to 0. The remainder corresponding to the root α^{i }becomes a syndrome corresponding to the root α^{i}. Each symbol of the code word 16 is sequentially inputted into the syndrome generator 26. The adder 40 performs Galois field addition, and stores result in the register 36. Each multiplier 38 individually corresponds to one root α^{i }of the generator polynomial G(x), and is used to perform Galois field multiplication on the data stored in the register 36 according to the corresponding α^{i}. Then, the Galois field addition is performed on the result of the multiplier 38 with the following symbol of the code word 16. The above operation is repeated until each symbol of the code word 16 has been processed. At this time, each register 36 stores one symbol of the code word 16. If each symbol is equal to 0, there is no error bit in the code word 16. After the syndrome generator 26 has finished calculating the syndromes, the polynomial generator 28 shown in
P(x)=C_{m}*X^{m}+C_{m−1}*X^{m−1}+. . . . . . +1,2*m=k
The error locating circuit 30 is capable of calculating locations of the error bits according to the coefficients of the error location polynomial P(x) and the prior art Chien search algorithm. The error locating circuit 30 has a plurality of adders 40, a plurality of multipliers 38, and a plurality of registers 36. In the beginning, each register 36 individually stores a coefficient of the error location polynomial P(x) as an initial value, and each multiplier 38 individually corresponds to α^{m}, α^{m−1}, . . . . . . , α^{1}. Each multiplier 38 performs a Galois field multiplication on data stored in a corresponding register 36, and the multiplication result updates the corresponding register 36. Finally, the data stored in each register 36 are added together by adders 40 to determine whether the addition result is a predetermined value (1 or 0 for example). Therefore, the error locating circuit 30 can find out which symbol in the code word 16 is erroneous. The abovementioned encoder 14, syndrome generator 26, and the error locating circuit 30 have been widely used in handling error correction codes. The detailed operating principles and algorithms are not related to the primary objective of the present invention, and the lengthy description for the wellknown operating principles and algorithms is skipped for simplicity.
Because the ECC is calculated in the Galois field, either the encoder 14 or the decoder 24 has to apply the Galois field addition and Galois field multiplication to an input data to generate the corresponding ECC. Therefore, the multipliers 38 and the adders 40 shown in
It is therefore a primary objective of the claimed invention to provide an ECC circuit with reduced hardware complexity to solve the abovementioned problems.
Briefly summarized, the preferred embodiment of the claimed invention discloses a processing circuit of a microprocessor for processing an input data to generate an output data. The microprocessor comprises a Galois field multiplier electrically connected to the processing circuit for performing a Galois field multiplication upon a plurality of processing data being processed by the processing circuit. The processing circuit comprises a first register for storing the input data, a plurality of processing units each being cascaded in series, and a controller for controlling operation of the processing circuit. A starting processing unit of the processing units is electrically connected to the first register. Each processing unit comprises an input port, an output port, a Galois field adder electrically connected between the input port and the output port, and a second register electrically connected to the Galois field adder. The controller controls each processing unit to transmit processing data requiring Galois field multiplication to the Galois field multiplier, and the processing data outputted from the Galois field multiplier are transmitted back to each corresponding processing unit.
It is an advantage of the claimed invention that each processing unit of the claimed processing circuit has no multiplier. When processing data requiring the Galois field multiplication, the processing data is transmitted from the processing unit to an external Galois field multiplier. The processing circuit, therefore, has low power consumption and a small size without any multipliers located inside each processing unit. In addition, each processing unit of the claimed processing circuit has a plurality of switches. The claimed processing circuit can control the on/off statuses of the switches to form different circuits for different purposes. Therefore, the different circuits share the same circuit elements to achieve the objective of sharing hardware resource. The calculations related to the ReedSolomon code can be fulfilled through a small amount of circuit elements so that the processing circuit needs only a small space to locate the circuit elements. In addition, the claimed circuit uses buffers to form a pipeline structure to handle different input data simultaneously. Not only is the processing efficiency improved, but also the critical path is shortened.
These and other objectives of the claimed 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.
Please refer to
Please refer to
When the first switch 62 connects nodes S1, S2, and the second switch 64 connects nodes E1, E3, the equivalent circuit of the processing module 46 is shown in
When the first switch 62 of the processing module 46 shown in
P(x)=C_{10}*X^{10}+C_{9}*X^{9}+. . . . . . +C_{2}*X^{2}+C_{1}*X^{1}+1
Then, each element α^{0}, α^{1}, . . . , α^{255 }is applied to the polynomial P(x). If the P (α^{n}) is not equal to 0, the n^{th }symbol within the code word 16 is erroneous. In the beginning, the registers 58 respectively store the coefficients C_{10}˜C_{1}.While the prior art Chien search is executed, the Galois field multiplier 44 sequentially performs the Galois field multiplication on each element α^{1}, . . . , α^{255 }and the registers 58 storing coefficients C_{10}˜C_{1}, and transmits the multiplication result back to the registers 58. That is, the registers 58 respectively store C_{10}(α^{10}),C_{9}(α^{9}), . . . . . . , C_{1}(α^{1}) . Then, the adders 60 are used to perform successive addition operations on the data stored in the registers 58. The output register 68 will record C_{10·}α^{10}+C_{9·}α^{9}+. . . . . . +C_{1·}α^{1}, that is, P(α)−1. If the 1^{st }symbol is correct, the P(α^{1})is equal to 0. In other words, the P(α^{1})−1 is equal to 1 after the wellknown XOR logic operation. In the following operation, the Galois field multiplier 44 sequentially performs the Galois field multiplication on each element α^{1}, . . . , α^{255 }and the registers 58 storing coefficients C_{10}α^{10}, C_{9}, α^{9}, . . . . . . , C_{1}α^{1}, and transmits the multiplication result back to the registers 58. The registers 58 now respectively record (C_{10·}α^{10})_{·}α^{10}, (C_{9·}α^{9})_{·}α^{9}, . . . . . . , (C_{1·}α^{1})_{·}α^{1}, that is, (C_{10·}α^{2})^{10}, (C_{9·}α^{2})^{9}, . . . . . . , (C_{1·}α^{2})^{1}. Therefore, the output register 68 finally stores P(α^{2})−1 to determine whether the 2^{nd }symbol is erroneous or not. With repetitions of the above operation, each symbol is sequentially checked to find out which symbol within the received code word 16 has error bits. It is obvious that the output register 68 records P(x)−1. After the data stored in the output register 68 is compared with 1, the locations of error symbols within the code word 16 are determined. However, when the adders 60 perform successive addition operations on the data stored in the registers 58 to generate a result result P(x)−1, an additional addition operation is performed to the result, that is, the overall operation becomes P(x)−1 XOR 1. The output register 68 records P(x) now. Similarly, the result stored in the output register 68 is compared with 0 to determine whether the corresponding symbol is erroneous. The circuit structure according to the present invention, therefore, is capable of achieving the same goal of the prior art Chien search algorithm according to different conditions. The Galois field multiplier 44, in the preferred embodiment, handles the multiplication operations performed by multipliers 38 shown in
With regard to the processing module 46, the input data stored in the input register 66 has to pass a plurality of processing units 56 to generate a corresponding output data, and the output data is finally recorded in the output register. If the error correction code of the input data is defined to include many symbols, the controller 48 needs to enable a corresponding amount of processing units 56. However, when the total amount of processing units 56 increases, the total number related to required calculations for generating the output data increases. Therefore, a critical path corresponding to the output data increases. The claimed processing circuit uses at least a buffer positioned between two processing units 56 for partitioning the original critical path into shorter critical paths. For example, if the claimed processing circuit has one buffer, the buffer can separate the processing units 56 into a first block and a second block. The first block is used to process an input data stored in the input register 66, and stores a first result in the buffer. The first result stored in the buffer is used as an input data of the second block for generating the output data corresponding to the input data of the first block. While the second block is active to process the first result generated from the first block, the input register 66 of the first block is capable of receiving a new input data and processing the new input data. In other words, the first and second blocks form a pipeline structure to handle different input data simultaneously. The critical path is shortened to be half of the original one. Not only is the processing efficiency of the processing module 46 improved, but also the shortened critical path reduces the probability of generating error result when the processing module 46 operates. In the preferred embodiment, the Galois field multiplier 44 is a hardware circuit for performing the Galois field multiplication. However, the Galois field multiplier 44 can be implemented by a software lookup table, which comprises multiplication results related to the Galois field multiplication. Therefore, the Galois field multiplication is performed through the software lookup table for obtaining the same function as the hardware circuit.
In contrast to the prior art, each processing unit of the claimed processing circuit has an adder and a register. When processing data requiring the Galois field multiplication, the processing data is transmitted from the processing unit to an external Galois field multiplier. The processing circuit, therefore, has low power consumption and a small size without any multipliers located inside each processing unit. In addition, each processing unit of the claimed processing circuit has a plurality switches. The claimed processing circuit can control the on/off statuses of the switches to form different circuits for different purposes. That is, the different circuits share the same circuit elements to achieve the objective of sharing hardware resource. To sum up, calculations related to the ReedSolomon code can be fulfilled through a small amount of circuit elements so that the processing circuit needs small space to locate the circuit elements. In addition, the claimed circuit uses buffers to form a pipeline structure to handle different input data simultaneously. Not only is the processing efficiency improved, but also the critical path is shortened.
Those skilled in the art will readily observe that numerous modifications and alterations of the device 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.