CN102855940A - Syndrome computing method and computing device thereof - Google Patents

Abstract

The invention is suitable for the technical field of solid-state storage, and provides a syndrome computing method and a computing device thereof. The computing method comprises the steps that: received codeword polynomial is used in a modulo operation upon a minimal polynomial; the root of the minimal polynomial is introduced into the remainder obtained in the modulo operation, and partial syndrome in the syndrome is computed; and according to the partial syndrome, the rest syndrome of the syndrome is computed. With the method provided by the invention, power consumption of syndrome computing is reduced, computing device critical path of syndrome is shortened, and the syndrome computing device can work in a high frequency.

Description

The computing method of syndrome and calculation element thereof

Technical field

The present invention relates to the solid state storage technologies field, relate in particular to a kind of computing method and calculation element thereof of syndrome.

Background technology

The solid state hard disc memory technology is memory technology commonly used in the prior art.Because the error correcting capability that flash memory requires error correction circuit to possess is more and more higher, cause the area of error correction circuit and power consumption to increase.Along with the raising of the data rate of solid state hard disc, require the Speed improving of error correction circuit, improving the error correction circuit frequency of operation is to improve a kind of mode of error correction circuit.At present, the computing area power consumption that rems in the syndrome counting circuit of error correction circuit is large, and the critical path path length, has a strong impact on frequency of operation, area and the power consumption of error correction circuit.

It is a codeword polynome that the root substitution that forms the minimal polynomial of generator polynomial receives and the process that calculates the result that existing syndrome calculates, hardware rems codeword polynome first when realizing usually to generator polynomial, then the root of minimal polynomial is updated in the remainder.Take error correcting capability as 60, Galois field is that the BCH error correction circuit of GF (2^15) is example, and the highest order of generator polynomial is 900, and the length of employed linear feedback shift register is 900, and therefore, the critical path of the computing that rems can be long.And in the computing of substitution root, need to split the computing of a plurality of cycles realization substitution roots, otherwise also can cause because critical path is oversize frequency of operation not high.

In summary, existing syndrome computing technique obviously exists inconvenience and defective in actual use, so be necessary to be improved.

Summary of the invention

For above-mentioned defective, the object of the present invention is to provide a kind of computing method and device thereof of syndrome, the power consumption of calculating to reduce syndrome, the calculation element critical path of shortening syndrome can be operated under the high frequency calculation element of syndrome.

In order to realize the foregoing invention purpose, the invention provides a kind of computing method of syndrome, described computing method comprise:

The codeword polynome that receives is carried out the complementation computing to minimal polynomial;

The root of described minimal polynomial is updated in the remainder of described complementation computing acquisition, calculates the part syndrome in the syndrome;

According to described part syndrome, calculate the syndrome of the remaining part in the described syndrome.

Computing method according to described syndrome, be updated in the remainder of described complementation computing acquisition at described root with described minimal polynomial, calculate in the step of the part syndrome in the syndrome, the root of described minimal polynomial is updated in the remainder of described complementation computing acquisition, and sequence number is the part syndrome of odd number in the calculating syndrome;

, calculating in the step of syndrome of the remaining part in the described syndrome according to described part syndrome described, is the part syndrome of odd number according to described sequence number, calculates that sequence number is the part syndrome of even number in the described syndrome.

According to the computing method of described syndrome, sequence number is that the part syndrome of odd number calculates by linear feedback shift register in the described calculating syndrome.

According to the computing method of described syndrome, sequence number is that the part syndrome of even number calculates by the square operation device in the described syndrome.

According to the computing method of described syndrome, described be the part syndrome of odd number according to described sequence number, also comprise after calculating sequence number in the described syndrome and be the step of part syndrome of even number:

Be the part syndrome of odd number and the part syndrome that sequence number is even number according to described sequence number, calculate the step of key equation coefficient.

In order to realize another goal of the invention of the present invention, the present invention also provides a kind of calculation element of syndrome, and described calculation element comprises:

The complementation computing module is used for the codeword polynome that receives is carried out the complementation computing to minimal polynomial;

First's syndrome computing module is used for the root of described minimal polynomial is updated to the remainder that described complementation computing obtains, and calculates the part syndrome in the syndrome;

Second portion syndrome computing module is used for according to described part syndrome, calculates the syndrome of the remaining part in the described syndrome.

According to the calculation element of described syndrome, described first syndrome computing module is used for the root of described minimal polynomial is updated to the remainder that described complementation computing obtains, and sequence number is the part syndrome of odd number in the calculating syndrome;

It is the part syndrome of odd number that described second portion syndrome computing module is used for according to described sequence number, calculates that sequence number is the part syndrome of even number in the described syndrome.

According to the calculation element of described syndrome, described complementation computing module is linear feedback shift register.

According to the calculation element of described syndrome, described second portion syndrome computing module is the square operation device.

According to the calculation element of described syndrome, described calculation element also comprises:

Find the solution the key equation coefficient module, being used for according to described sequence number is the part syndrome of odd number and the part syndrome that sequence number is even number, calculates the key equation coefficient.

The present invention by the codeword polynome that will receive to the minimal polynomial complementation, the frequency of operation that the Effective Raise syndrome calculates; The codeword polynome that receives to the minimal polynomial complementation, and is calculated syndrome based on this remainder, effectively reduce the delay that syndrome calculates; The codeword polynome that receives to the minimal polynomial complementation, and based on this remainder calculating section syndrome, is reduced the calculating of syndrome, reduce area and power consumption.Further, the codeword polynome that receives to the minimal polynomial complementation, and based on this remainder calculating section syndrome, is calculated needed syndrome in real time when finding the solution the key equation coefficient, effectively reduce power consumption.In addition, use the circuit of the square operation of realizing Galois field to calculate in real time needed syndrome when finding the solution the key equation coefficient, described squaring circuit only has tens doors, more effective reduction area and power consumption.

Description of drawings

Fig. 1 is the structural representation of the calculation element of the syndrome that provides of the first embodiment of the present invention;

Fig. 2 is the structural representation of the calculation element of the syndrome that provides of the third embodiment of the present invention;

Fig. 3 is a structural representation of executing the calculation element of the syndrome that example provides of the present invention;

Fig. 4 is the multiplying block diagram of rem computing and substitution root of the calculation element of the syndrome that provides of one embodiment of the present of invention;

Fig. 5 is the rem linear feedback shift register circuit figure of computing of realization that one embodiment of the present of invention provide;

Fig. 6 is the syndrome square operation structure that one embodiment of the invention provides;

Fig. 7 is the computing method process flow diagram of the syndrome that provides during the present invention the 5th implements.

Embodiment

In order to make purpose of the present invention, technical scheme and advantage clearer, below in conjunction with drawings and Examples, the present invention is further elaborated.Should be appreciated that specific embodiment described herein only in order to explain the present invention, is not intended to limit the present invention.

Referring to Fig. 1, the first embodiment of the present invention provides a kind of calculation element 100 of syndrome, and described calculation element 100 comprises:

Complementation computing module 10 is used for the codeword polynome that receives is carried out the complementation computing to minimal polynomial;

First's syndrome computing module 20 is used for the root of described minimal polynomial is updated to the remainder that described complementation computing obtains, and calculates the part syndrome in the syndrome;

Second portion syndrome computing module 30 is used for according to described part syndrome, calculates the syndrome of the remaining part in the described syndrome.

In this embodiment, the defective that the area power consumption is large, frequency of operation is low for current syndrome counting circuit, the calculation element 100 of the syndrome of realizing a kind of area optimised power consumption is provided, can effectively reduce the power consumption that syndrome calculates, and calculation element 100 critical paths of the syndrome of realizing are short, can be operated under the high frequency.Concrete, complementation computing module 10 rems to the minimal polynomial that forms generator polynomial by the codeword polynome that receives with receiving end and realizes the complementation computing that syndrome calculates, first's syndrome computing module 20 is updated to calculating section syndrome in the remainder to the root of generator polynomial again, and second portion syndrome computing module 30 also calculates other a part of syndrome when finding the solution the key equation coefficient.Owing to rem to the minimal polynomial complementation rather than to generator polynomial in the calculation element 100 of syndrome, its corresponding critical path is short, postpones little, reduction computing area and power consumption.

In the second embodiment of the present invention, first's syndrome computing module 20 is used for the root of described minimal polynomial is updated to the remainder that described complementation computing obtains, and sequence number is the part syndrome of odd number in the calculating syndrome;

It is the part syndrome of odd number that second portion syndrome computing module 30 is used for according to described sequence number, calculates that sequence number is the part syndrome of even number in the described syndrome.

The order of employed linear feedback shift register length and generator polynomial is relevant, and critical path is short, postpones littlely, and decoding scheme can be operated in high frequency.The computing of the syndrome substitution root of this device is finished in one-period, postpones little.This device is a calculating section syndrome when syndrome calculates, and other a part of syndrome calculates in real time by squarer, reduces the logical block that syndrome calculates, and reduces area and power consumption.

Referring to Fig. 2, in the third embodiment of the present invention, the calculation element 100 of syndrome also comprises:

Find the solution key equation coefficient module 40, being used for according to described sequence number is the part syndrome of odd number and the part syndrome that sequence number is even number, calculates the key equation coefficient.

The structural representation of the calculation element 100 of the syndrome that provides of one embodiment of the invention referring to Fig. 3, wherein, complementation computing module 10 is linear feedback shift register, and it is that second portion syndrome computing module 30 is the square operation device that first's syndrome computing module 20 substitution roots calculate syndrome module 20.Take error correcting capability as 60, Galois field is that the BCH error correction circuit of GF (2^15) is example for convenience of description, needs 120 syndromes of sequence number from 1 to 120, and only calculating sequence number herein is 60 syndromes of odd number.LFSR(LinearFeedbackShiftingRegister among the figure, linear feedback shift register) complementation module 10 realizes the codeword polynome that receives to the computing that rems of minimal polynomial, and its output is that high order power is 14 polynomial expression.The root of corresponding minimal polynomial is updated in the corresponding remainder polynomid, calculates corresponding syndrome.In order to reduce the use of logic, rem and the substitution root calculates in the syndrome module 20 and only calculated the part syndrome in LFSR complementation module 10.A part of syndrome is that syndrome square operation circuit 30 is realized calculating by second portion syndrome computing module 30 in addition.

Be the calculation element 100 of the syndrome that provides of one embodiment of the invention realize the remming linear feedback shift register circuit figure of computing referring to Fig. 4, the m among the figure is 14.By this figure as seen, after parallel expansion, the critical path of the computing that rems of the calculation element 100 of syndrome can be not oversize yet, can be operated in higher frequency.It is the circuit block diagram of realization syndrome square operation of the calculation element 100 of syndrome referring to Fig. 5.Described square operation circuit is to be the syndrome of i according to sequence number, and calculating sequence number is the syndrome of 2i, and used square operation circuit only has one, and only uses tens logic gates.Fig. 7 is the syndrome square operation structure that one embodiment of the invention provides.

Suppose that remainder b (x) is b (x)=b ₀+ b ₁X+b ₂x ²+ ...+b _N-1x ^N-1, syndrome can be expressed as so:

$S_i=b\left({\&PartialD;}^i\right)=b_0+{\mathrm{<figure-callout\; id="1"\; label="b"\; filenames="HDA00001784757900022.png"\; state="\{\{state\}\}">b</figure-callout>}}_1{\&PartialD;}^i+b_2{\left({\&PartialD;}^i\right)}^2......+b_{N-1}{\left({\&PartialD;}^i\right)}^{N-1},$

In like manner the another one syndrome can be written as:

Because among the scale-of-two BCH, the additive operation of Galois field is XOR, therefore have

Thereby be the syndrome of i according to sequence number, calculating sequence number is the syndrome of 2i.

Take error correcting capability as 60, Galois field is that the BCH error correction circuit of GF (2^15) is example, need 120 syndromes, and the sequence number of syndrome is 1 to 120.Because syndrome is order and divides a plurality of periodical inputs to finding the solution key equation coefficient module 40 that traditional all syndromes that calculates expend a large amount of logical blocks when syndrome calculates.Only calculate half 60 syndrome in the calculation element 100 of syndrome when syndrome calculates, half syndrome calculates in real time by the squaring circuit of realizing the Galois field square operation when finding the solution the key equation coefficient in addition.Described squaring circuit only has tens logic gates, therefore can reduce to a large extent area.Described real-time calculating only refers to just corresponding syndrome to be calculated in the previous cycle of finding the solution the key equation coefficient and needing, and therefore can effectively reduce power consumption.

Referring to Fig. 7, in the of the present invention the 5th implements, provide a kind of computing method of syndrome, described computing method comprise:

Among the step S701, the codeword polynome that receives is carried out the complementation computing to minimal polynomial; This step is realized by complementation computing module 10.

Among the step S702, the root of described minimal polynomial is updated in the remainder that described complementation computing obtains, calculates the part syndrome in the syndrome; This step is realized by first's syndrome computing module 20.

Among the step S703, according to described part syndrome, calculate the syndrome of the remaining part in the described syndrome; This step is realized by second portion syndrome computing module 30.

In one embodiment of the invention, in step S702, first's syndrome computing module 20 is updated to the root of described minimal polynomial in the remainder of described complementation computing acquisition, and sequence number is the part syndrome of odd number in the calculating syndrome; Sequence number is that the part syndrome of odd number calculates by linear feedback shift register in the described calculating syndrome.

Among the step S703, second portion syndrome computing module 30 is the part syndrome of odd number according to described sequence number, calculates that sequence number is the part syndrome of even number in the described syndrome.Sequence number is that the part syndrome of even number calculates by the square operation device in the described syndrome.

In another embodiment of the present invention, after described step S703, also comprise: be the part syndrome of odd number and the part syndrome that sequence number is even number according to described sequence number, calculate the step of key equation coefficient.This step realizes by finding the solution key equation coefficient module 40.

According to the coding principle of BCH code, the codeword polynome behind the coding can be divided exactly by minimal polynomial.Therefore, the complementation computing module 10 of the calculation element 100 of syndrome at first rems the codeword polynome that receives to minimal polynomial, and then first's syndrome computing module 20 is updated to the root of minimal polynomial in the remainder of gained.Equally take error correcting capability as 60, Galois field is that the BCH error correction circuit of GF (2^15) is example, the order maximal value of minimal polynomial is 15, so the length of the linear feedback shift register of the computing that rems is 15, the highest order of remainder is 14, no matter be the computing that rems, or the substitution computing, the critical path of the circuit that uses is all very short, can be operated in higher frequency.In addition, because the highest order of remainder is 14, the computing of substitution root can be finished in one-period, and the delay of the substitution computing that syndrome calculates is one-period.

In sum, the present invention by the codeword polynome that will receive to the minimal polynomial complementation, the frequency of operation that the Effective Raise syndrome calculates; The codeword polynome that receives to the minimal polynomial complementation, and is calculated syndrome based on this remainder, effectively reduce the delay that syndrome calculates; The codeword polynome that receives to the minimal polynomial complementation, and based on this remainder calculating section syndrome, is reduced the calculating of syndrome, reduce area and power consumption.Further, the codeword polynome that receives to the minimal polynomial complementation, and based on this remainder calculating section syndrome, is calculated needed syndrome in real time when finding the solution the key equation coefficient, effectively reduce power consumption.In addition, use the circuit of the square operation of realizing Galois field to calculate in real time needed syndrome when finding the solution the key equation coefficient, described squaring circuit only has tens doors, more effective reduction area and power consumption.

Certainly; the present invention also can have other various embodiments; in the situation that does not deviate from spirit of the present invention and essence thereof; those of ordinary skill in the art work as can make according to the present invention various corresponding changes and distortion, but these corresponding changes and distortion all should belong to the protection domain of the appended claim of the present invention.

Claims (10)

1. the computing method of a syndrome is characterized in that, described computing method comprise:

The codeword polynome that receives is carried out the complementation computing to minimal polynomial;

The root of described minimal polynomial is updated in the remainder of described complementation computing acquisition, calculates the part syndrome in the syndrome;

According to described part syndrome, calculate the syndrome of the remaining part in the described syndrome.

2. the computing method of syndrome according to claim 1, it is characterized in that, be updated in the remainder of described complementation computing acquisition at described root with described minimal polynomial, calculate in the step of the part syndrome in the syndrome, the root of described minimal polynomial is updated in the remainder of described complementation computing acquisition, and sequence number is the part syndrome of odd number in the calculating syndrome;

, calculating in the step of syndrome of the remaining part in the described syndrome according to described part syndrome described, is the part syndrome of odd number according to described sequence number, calculates that sequence number is the part syndrome of even number in the described syndrome.

3. the computing method of syndrome according to claim 2 is characterized in that, sequence number is that the part syndrome of odd number calculates by linear feedback shift register in the described calculating syndrome.

4. the computing method of syndrome according to claim 2 is characterized in that, sequence number is that the part syndrome of even number calculates by the square operation device in the described syndrome.

5. the computing method of syndrome according to claim 2 is characterized in that, described be the part syndrome of odd number according to described sequence number, also comprise after calculating sequence number in the described syndrome and be the step of part syndrome of even number:

Be the part syndrome of odd number and the part syndrome that sequence number is even number according to described sequence number, calculate the step of key equation coefficient.

6. the calculation element of a syndrome is characterized in that, described calculation element comprises:

The complementation computing module is used for the codeword polynome that receives is carried out the complementation computing to minimal polynomial;

First's syndrome computing module is used for the root of described minimal polynomial is updated to the remainder that described complementation computing obtains, and calculates the part syndrome in the syndrome;

Second portion syndrome computing module is used for according to described part syndrome, calculates the syndrome of the remaining part in the described syndrome.

7. the calculation element of syndrome according to claim 6, it is characterized in that, described first syndrome computing module is used for the root of described minimal polynomial is updated to the remainder that described complementation computing obtains, and sequence number is the part syndrome of odd number in the calculating syndrome;

It is the part syndrome of odd number that described second portion syndrome computing module is used for according to described sequence number, calculates that sequence number is the part syndrome of even number in the described syndrome.

8. the calculation element of syndrome according to claim 7 is characterized in that, described complementation computing module is linear feedback shift register.

9. the calculation element of syndrome according to claim 7 is characterized in that, described second portion syndrome computing module is the square operation device.

10. the calculation element of syndrome according to claim 7 is characterized in that, described calculation element also comprises:

Find the solution the key equation coefficient module, being used for according to described sequence number is the part syndrome of odd number and the part syndrome that sequence number is even number, calculates the key equation coefficient.

Images