CN102594370A - High-efficient low-delay parallel Chien search method and device - Google Patents
High-efficient low-delay parallel Chien search method and device Download PDFInfo
- Publication number
- CN102594370A CN102594370A CN2012100461297A CN201210046129A CN102594370A CN 102594370 A CN102594370 A CN 102594370A CN 2012100461297 A CN2012100461297 A CN 2012100461297A CN 201210046129 A CN201210046129 A CN 201210046129A CN 102594370 A CN102594370 A CN 102594370A
- Authority
- CN
- China
- Prior art keywords
- group
- constant multiplier
- parallel
- galois field
- money
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Images
Landscapes
- Detection And Correction Of Errors (AREA)
- Error Detection And Correction (AREA)
Abstract
The invention discloses a high-efficient low-delay parallel Chien search method and device. The method comprises the following steps: sending the coefficient of an error polynomial, which is registered in a coefficient register set, to an initial constant multiplier set in a clock cycle, and further outputting the output result of the initial constant multiplier set and the output intermediate result of a public parallel constant multiplier set into the public parallel constant multiplier set through an initial value selector set to perform parallel Galois field multiplication operation on n positions of a code block; then respectively performing Galois field summing operation on the Galois field multiplication operation results in the corresponding positions in the n positions of the code block in a multi-input adder set; further comparing the Galois field summing operation result with the coefficient sigma 0 of the error polynomial in a comparator set and judging the positions of effective errors in the n positions of the code block; and in the process, simultaneously storing the corresponding result of the public parallel constant multiplier set for being output to the public parallel constant multiplier set through the initial value selector set from the beginning of the second-round Chien search. According to the method disclosed by the invention, the search period can be shortened, the method is compatible with a variety of error correction capabilities, and the construction cost of a circuit is saved.
Description
Technical field
The present invention relates to digital communicating field, relate in particular to parallel money search method of a kind of efficient low delay and device, can be widely used in the error correction decode technology.
Background technology
Error-correcting code technique is widely used at aspects such as data communication, storage, and common error correcting code has now: RS (Reed-Solomon, Read-Solomon) sign indicating number, BCH code, Hamming code, and wherein: Hamming code can only be corrected a bit-errors because code distance is less; RS sign indicating number, BCH code can carry out the error correction of many bits, thereby use very extensively.In the decode procedure of error correcting codes such as RS sign indicating number, BCH code, need be according to error location polynomial (hereinafter to be referred as wrong multinomial), the position that utilizes the money search to find error code to take place.
The money searching algorithm is through all positions in the traversal code block, the final position of confirming wrong generation.The money searching algorithm is promptly for accepting code polynomial r (x)=r
0+ r
1X ... + r
N-1x
N-1Pursue bit decoding, wherein, at galois field GF (2
m) middle n=2
m-1.In order to translate r
N-1, decoder check α
N-1Whether is the errors present number, the α reciprocal that just checks it is the root of error location polynomial σ (x).If α is the root of σ (x), σ is arranged then
0+ σ
1α+σ
2α
2+ ... + σ
tα
t=0, wherein t is the rank of error location polynomial.Thus, decoder will be constructed σ
1α, σ
2α
2..., σ
tα
t, and then judge them with whether equal σ
0Usually, to translate r like needs
N-i, will check α
iWhether satisfy σ
0+ σ
1α
i+ σ
2(α
i)
2+ ... + σ
t(α
i)
t=0; According to the additional calculation rule of galois field, whether check just satisfies σ
1σ+σ
2σ
2+ ... + σ
2σ
2=σ
0
Traditional money search method needs search check by turn, specifically adopts the mode of serial process, also is the data that a clock cycle can only handle a bit, and regular software decode system etc. adopt this method to the not high application system of rate request more.But for the high data communication system of data transmission rate request, this has seriously restricted transmission speed.
In order to improve the transmission rate of data; Document " 10-and 40-Gb/s Forward Error Correction Devices for Optical Communications-By Leiei Song, Meng-Lin Yu and Michael S.Shaffer " has been mentioned a kind of parallel money search method.This method adopts tree multiplier to realize parallel money search, for GF (2
m) binary system BCH code (n, the k) (n=2 in territory
m-1), it is from highest order r
N-1(n=2
m-1) begin to walk abreast money search.Though this method has been accomplished parallel money search; Improved efficient than traditional serial money search circuit; But because it adopts the mode of tree multiplier, degree of parallelism is big more, and the multiplier of cascade is dark more; Thereby the time-delay of the critical path of circuit is just big more, is not suitable for the money searching requirement of high degree of parallelism thus.
For head it off, paper " Small Area Parallel Chien Search Architectures for Long BCH Codes-By Yanni Chen and Keshab K.Parhi " has been announced a kind of new parallel money search method.The multiplier that this method increases is relatively independent, not cascade, thus the time-delay of circuit critical path is fixed, do not receive the influence of degree of parallelism.Simultaneously, this circuit compatibility property is good, is applicable to any shortening sign indicating number under the same territory.But this money search method is the same with before money search method, remains from high-order r
N-1(n=2
m-1) begin to decipher, its search cycle is long.For example, as if the coding and decoding of carrying out the binary system BCH code for 1K information, for the code word size 2 that satisfies BCH code
m-1, adopt GF (2
14) territory and when adopting 32 parallel-by-bit account forms, just need 2 if accomplish the money search of a code word
14/ 32=512 clock cycle is so can not satisfy the requirement of real-time decoding error correction equally.
In addition, Zhang Jun mentions a kind of shortening BCH code (2184 to BCH code (4095,3591) in paper " cascaded code technology in the optical fiber communication and realization research thereof "; 2040) parallel money search circuit; The multiplier of this circuit also is independently, and its critical path delay is little, does not receive the influence of degree of parallelism; And search for from the highest order that shortens sign indicating number, solved long problem of search cycle thus.But this circuit exists big not enough when compatible various error correcting, and when other error correcting capabilities of need compatibility, the reconstruct entire circuit causes resource cost bigger thus fully.
Because codec need adapt to various application scenarios; And but these occasions not only require difference to the error correction figure place; And the proportion that redundant digit accounts for block of information also there are different restrictions (the Flash chip specification that goes out such as current various manufacturers is all different); So high error correction figure place can not directly compatiblely be hanged down the error correction figure place, thereby too high to the codec chip cost of different error correcting capabilities design different sizes.Thus, be necessary to design a kind of general money search method, to realize compatibility to various error correcting.
Summary of the invention
In view of this, the present invention provides parallel money search method of a kind of efficient low delay and device, is intended to solve existing long problem of money search method search cycle; And realize that further short-period error correction can join, solve the problem of poor compatibility.
For solving above technical problem, technical scheme provided by the invention is: a kind of parallel money search method of efficient low delay may further comprise the steps:
In a clock cycle, with the wrong polynomial factor sigma that is deposited with in the coefficient register group
1, σ
2..., σ
tSend into initial constant multiplier group A
i(among 1≤i≤t), again the output result of initial constant multiplier group and the intermediate object program of public parallel constant multiplier group output are outputed to relatively independent public parallel constant multiplier group B through first value selector group
Ij(among the 1≤i≤t, 1≤j≤w), n the position of the realizing code-aiming block galois field multiplying that walks abreast, code length n>=2 wherein, t is specific error correction requirement, w is a degree of parallelism;
Galois field multiplication result with the correspondence position in n the position of code block carries out the galois field summation operation in many input summers group respectively;
With galois field summation operation result and wrong polynomial factor sigma
0In comparator bank, compare the effective errors present in n the position of judgement code block;
In the said process,, be used for taking turns the money search and output to public parallel constant multiplier group through first value selector group since second simultaneously with the accordingly result storage of public parallel constant multiplier group.
More excellently, the galois field multiplication result with correspondence position in n the position of code block is stored in the scratch-pad register group.
The money search is taken turns since second in more excellent ground, through first value selector group the storing value in the scratch-pad register group is delivered in the public parallel constant multiplier group as initial value, with the galois field multiplying that walks abreast of next n position of realization code-aiming block;
Respectively the galois field multiplication result of correspondence position is carried out the galois field summation operation by many input summers group again;
And by comparator bank with galois field summation operation result and wrong polynomial factor sigma
0Make comparisons the effective errors present in n the position of judgement epicycle money search.
N=2 is chosen on more excellent ground
m(n, k t), choose front 2 to-1 long BCH code on this yard collection
m-1-a-l position is zero code word entirely, removes wherein front 2
m-1-a-l position zero as after the code word, constitute shorten sign indicating number (a+l, a, t) sign indicating number, wherein m is a positive integer, m>=3, k is the information bit length of non-shortening binary system BCH code, a is effective information bit length, redundant digit is l=mt.
On this basis; The corresponding parallel money searcher that a kind of efficient low delay is provided of the present invention; Comprise coefficient register group, initial constant multiplier group, first value selector group, relatively independent public parallel constant multiplier group, many input summers group and comparator bank, wherein:
The coefficient register group is used for the polynomial factor sigma of storage errors
1, σ
2..., σ
t
Initial constant multiplier group A
i(1≤i≤t), be used in a clock cycle, reception is deposited with the wrong polynomial coefficient in the coefficient register group and carries out corresponding computing;
Just the value selector group is used for the output result of initial constant multiplier group and the intermediate object program of public parallel constant multiplier group output are optionally outputed to public parallel constant multiplier group;
Public parallel constant multiplier group B
Ij(1≤i≤t, 1≤j≤w), n the position that is used to the to realize code-aiming block galois field multiplying that walks abreast, wherein, and code length n>=2, t is specific error correction requirement, w is a degree of parallelism; Simultaneously, the accordingly result of this public parallel constant multiplier group is stored, and is used for taking turns the money search since second and outputs to public parallel constant multiplier group through first value selector group;
Many input summers group is used for respectively the galois field multiplication result of the correspondence position of n position of code block is carried out the galois field summation operation;
Comparator bank is used for galois field summation operation result and wrong polynomial factor sigma
0Relatively, the effective errors present in n the position of judgement code block.
More excellent ground comprises the scratch-pad register group, is used for storing the galois field multiplication result of n position correspondence position of code block.
More excellent ground, first value selector group can be used for taking turns the money search, the storing value output in the selection scratch-pad register group, the galois field multiplying so that next n position of public parallel constant multiplier group code-aiming block walks abreast since second; Respectively the galois field multiplication result of correspondence position is carried out the galois field summation operation by many input summers group afterwards; And by comparator bank with galois field summation operation result and wrong polynomial factor sigma
0Make comparisons the effective errors present in n the position of judgement epicycle money search.
More excellent ground is the parallel money searcher of the compatible short error correcting capability of long error correcting capability, and it is provided with a plurality of initial constant multiplier groups, wherein the corresponding a kind of error correction demand of each initial constant multiplier group.
More excellent ground comprises error correction requirement selector group, is used to select the result of calculation of the initial constant multiplier group of corresponding error correction demand to output to just among the value selector group.
More excellent ground is the parallel money searcher of the compatible long error correcting capability of short error correcting capability, and the multiplier number in its public parallel constant multiplier group is t
Max* w is individual, wherein t
MaxBe maximum error correcting capability.
Compared with prior art; Parallel money search method of the efficient low delay that the present invention adopts a kind of parallel processing and compatible technique to combine and device; It establishes initial constant multiplier group and relatively independent public parallel constant multiplier group through structure; And import the public parallel constant multiplier group that is used for corresponding round money search through first value selector group selection difference initial value and carry out corresponding multiplying; Can carry out the money search to the code length that shortens sign indicating number easily, save the search of high l position thus, shorten the search cycle greatly; On the other hand; When the compatible various error correcting of needs, constructed circuit to long error correcting capability after, only need increase a spot of multiplier and just can implement with some selectors; And do not need the reconstruct entire circuit; So just can accomplish compatibility, and also can realize the purpose of the compatible long error correcting capability of short error correcting capability, thereby practice thrift production cost widely through the multiplier number that increases in the public parallel constant multiplier group to short error correcting capability.
Description of drawings
Fig. 1 is the flow chart of the efficient low delay parallel processing of the present invention money search method embodiment;
Fig. 2 is the circuit theory diagrams of the efficient low delay parallel processing of the present invention money searcher embodiment one;
Fig. 3 is the circuit theory diagrams of the efficient low delay parallel processing of the present invention money searcher embodiment two.
Embodiment
Core concept of the present invention is; Structure is established initial constant multiplier group and relatively independent public parallel constant multiplier group in advance; And import the public parallel constant multiplier group that is used for corresponding round money search through first value selector group selection difference initial value and carry out corresponding multiplying; Can carry out the money search to the code length that shortens sign indicating number easily, shorten the search cycle greatly thus; In addition, money search method of the present invention is compatible good with device, when multiple error correction requires for compatibility, can pass through resource multiplex, reduces device area widely, reaching the purpose that reduces cost, thereby on whole cost and autgmentability, increases.
, clearly explanation full and accurate for ease of the embodiment of the invention is carried out are at first to the present invention relates to notion and operation principle describes.
1, shortens the sign indicating number notion
For galois field GF (2
m) binary system BCH code (n, k, the t) (n=2 in territory
m-1), n is a code length; K is the information bit length of non-shortening binary system BCH code; T is the error correction requirement, promptly maximum number of errors, and m is a positive integer, m>=3.In the actual encoding and decoding, because information bit length adds that the length (being effective code word size n ') of redundant digit does not often satisfy the code word size n=2 of binary system BCH
m-1, the method that usually adopts is to add zero of l position in the high position of information bit, makes the code word size behind the coding satisfy n '+l=n=2
m-1 relation.Thus, the binary system BCH code (n ', k ', t) (n '=n-l, k '=k-l) just is called the BCH code of shortening.
2, the parallel money search principle of efficient low delay
The parallel money search of efficient low delay among the present invention is carried out the money search according to the length that shortens sign indicating number exactly, has so just saved the search of high l position; Make the iteration cycle of money search shorten to n '/w; Wherein w is a degree of parallelism, has shortened the money search cycle greatly thus, makes a concrete analysis of as follows:
Because under the different error correction conditions, the highest order that shortens sign indicating number is different, the cycle of money search iteration is also different with initial value, therefore should need to require t to construct one group of initial constant multiplier A according to specific error correction by parallel money search method
i(1≤i≤t), and constructed one group of public parallel constant multiplier B
Ij(1≤i≤t, 1≤j≤w).Each public parallel constant multiplier B
IjRelatively independent, promptly there is not cascade between each public parallel constant multiplier, make the time-delay of total combinational logic not receive the influence of degree of parallelism.Public parallel constant multiplier group B
Ij(1≤i≤w, after the relevant multiplication result addition of 1≤j≤t) with the polynomial factor sigma of mistake
0Make comparisons and just can judge whether relevant bits makes mistakes, if comparative result is for equating that then this position of expression is wrong; Otherwise, error-free.
The parallel money search method of the efficient low delay that the present invention relates to and device can be directed against the error correction of binary system BCH code, and any t or the t that can correct in the information of a position are individual with interior random error.For information bit length k, add the redundant digit length l, code length is n=k+l, makes this code length not satisfy BCH code (n, k, code word size 2 t) usually
m-1.Like this, the present invention can choose n=2
m-1 long BCH code is chosen a sub-set (front 2 on this yard collection
m-1-a-l position is zero code word entirely) and remove some part (front 2 of front
m-1-a-l position zero) as code word, constitute thus and shorten sign indicating number (a+l, an a; T) sign indicating number, wherein m is any positive integer more than or equal to 3, k is the information bit length of non-shortening binary system BCH code; A is effective information bit length (promptly shortening the information digit of sign indicating number), and redundant digit is l=mt.
Existing from r
N-1(n=2
m-1) money search method of beginning parallel search needs 2 when adopting the search of w parallel-by-bit
m/ w clock cycle; And parallel money search method of the efficient low delay of the present invention and device only need (a+l)/w clock cycle.For GF (2
14) shortening sign indicating number (8528,8192,24) under the territory, existing from r
N-1(n=2
m-1) money search method of beginning parallel search needs 512 clock cycle when adopting 32 parallel-by-bits to calculate; And parallel money search method of efficient low delay of the present invention and device only need 267 clock cycle.
The parallel money search method of the efficient low delay after the present invention improves and device can satisfy the requirement of compatible multiple error correction.Since under different error correction conditions, the initial constant multiplier A of structure
i(difference of 1≤i≤t), and public parallel constant multiplier B
Ij(1≤i≤t, the number of 1≤j≤w) only with degree of parallelism and error correction require relevant, the obvious constant multiplier B that needs of the identical duration error correcting capability of degree of parallelism
IjNumber than short error correcting capability need many.Therefore, during the compatible weak point of long error correcting capability error correcting capability, only need to add initial value counting circuit and certain control circuit, promptly only need be directed against the different initial constant multiplier of error correction increase in demand A
i, increase by a group selector again and get final product.If during the compatible length of short error correcting capability error correcting capability, then increase public parallel constant multiplier B by rule
IjNumber, make its number satisfy t
Max* w gets final product.
In order to make those skilled in the art understand technical scheme of the present invention better, the present invention is done further detailed description below in conjunction with accompanying drawing and specific embodiment.
Referring to Fig. 1, a preferred embodiment of the parallel money search method of the efficient low delay of expression the present invention.The parallel money search method of this efficient low delay mainly may further comprise the steps:
(1) in a clock cycle, with the polynomial factor sigma of mistake
1, σ
2..., σ
tDeliver to initial constant multiplier group; Again the intermediate object program of the output result of initial constant multiplier group and public parallel constant multiplier group output is outputed to relatively independent public parallel constant multiplier group through first value selector group and multiply each other, the individual position of n (wherein n>=2) of the realizing code-aiming block galois field multiplying that walks abreast; Simultaneously, deposit, output to public parallel constant multiplier group through first value selector group for use in taking turns the money search since second for the correlated results of the galois field multiplying of correspondence position in n the position of code block.
(2) the galois field multiplication result of the correspondence position in the n of the code-aiming block position carries out summation operation respectively.
(3) with said summation operation result and wrong multinomial coefficient σ
0Making comparisons, judge the effective errors present in n the position of said code block, is errors present when promptly equating.
(4) wherein: take turns money search since second, the value of preserving in the register is delivered to public parallel constant multiplier group as initial value multiply each other, the galois field multiplying that walks abreast of next n position of realization code-aiming block; Galois field multiplication result with correspondence position carries out summation operation again, according to said summation operation result and wrong multinomial coefficient σ
0Make comparisons the effective errors present in n the position of judgement epicycle money search.
The present invention takes turns the money search from second and begins, and the value of preserving in the scratch-pad register group is delivered to public parallel constant multiplier group as initial value multiply each other, and can make technical scheme of the present invention more perfect.Its reason is: because code word size n is very big, can not search for once taking turns; The general parallel figure place w=32 that selects; Promptly one take turns and only searched 32; And the first round search time to be result with initial constant multiplier send into public parallel constant multiplier group walk abreast galois field computing, second takes turns that to begin be that intermediate object program with storing is sent into public parallel constant multiplier group.So on this kind meaning, no matter have only a kind of error correction demand or compatible multiple error correction demand, this all is a basic step, and is indispensable.
Fig. 1 demonstrates a complete flow process of the parallel money search method of the efficient low delay of the present invention, specifically comprises the steps:
S101, the polynomial coefficient of mistake delivered in the initial constant multiplier group carry out the galois field multiplying, so that obtain the multiplication result of initial constant.
S102, through first value selector group: when first round money search, select the result of initial constant multiplier to output to public parallel constant multiplier group as initial value; Take turns the intermediate object program that money search begins to select to preserve in the scratch-pad register group second and output to public parallel constant multiplier group as initial value.
The galois field multiplying that walks abreast of S103, n the position of in public parallel constant multiplier group, realizing code-aiming block.
The corresponding intermediate object program of S104, the constant multiplier group that will walk abreast computing is preserved, and outputs to public parallel constant multiplier group as initial value through first value selector group so that take turns money search beginning second; This mode can certainly consider serial mode, but its efficient is lower for parallel preserving type.Usually, the corresponding intermediate object program with parallel constant multiplier group computing is kept in the scratch-pad register group; Also can consider this intermediate object program is kept in the readable and writable memory (RAM), but, not advise using because the product circuit area of this method of employing is big, cost is higher.
S105, the galois field multiplication result of n position of code block is carried out the galois field summation operation.
S106, with galois field summation operation result and wrong polynomial factor sigma
0Make comparisons the effective errors present in n the position of judgement code block.
S107, judge whether to carry out next round money search, if return step S102; Otherwise, after the completion search, withdraw from.
In the present embodiment, can choose n=2
m(n, k t), choose front 2 to-1 long BCH code on this yard collection
m-1-a-l position is zero code word entirely, removes wherein front 2
m-1-a-l position zero as after the code word, constitute shorten sign indicating number (a+l, a, t) sign indicating number, wherein m is a positive integer, m>=3, k is the information bit length of non-shortening binary system BCH code, a is effective information bit length, redundant digit is l=mt.Like this, establish initial constant multiplier group and relatively independent public parallel constant multiplier group through structure after, just can begin to carry out the money search from the highest order of this shortening sign indicating number, saved the search of high l position thus, thereby shortened the search cycle widely.
On this basis, the present invention provides a kind of parallel money searcher of efficient low delay simultaneously, further specifically describes below.
Embodiment one
Referring to Fig. 2, the circuit theory diagrams of parallel money searcher first embodiment of the efficient low delay of expression the present invention.The said device of this embodiment is a basic model of the present invention, is adapted to have only a kind of situation of error correction requirement.This device comprises first registers group (coefficient register group), 11, the first constant multiplier group (initial constant multiplier group), 12, one selector group (first value selector group) 13, second registers group (scratch-pad register group), 14, the second constant multiplier group (public parallel constant multiplier group) 15, the group of input summer more than one 16 and a comparator bank 17, and wherein: the function and the course of work of each device are following:
The first constant multiplier group 12, promptly initial constant multiplier A
i, the polynomial coefficient calculations result of mistake is cascaded to an input of selector group 13;
The second constant multiplier group 15, promptly public parallel constant multiplier group B
Ij(1≤i≤t, 1≤j≤w), it is input as the output r of selector group 13;
Many input summers group 16 is to constant multiplier B
Ij(1≤i≤t, the correlated results of 1≤j≤w) is sued for peace;
The parallel money searcher of the efficient low delay that present embodiment one relates to can be directed against the error correction of binary system BCH code, can correct any t or t in the information of a position with interior random error.
Realization circuit as shown in Figure 2, the concrete search procedure of this device is: at first with the polynomial factor sigma of mistake
1, σ
2..., σ
72Be stored in first registers group 11, then with σ
kSend into the first constant multiplier group 12 and carry out multiplying; Through selector group 13 the output result of the first constant multiplier group 12 and the intermediate object program of the second constant multiplier group, 15 outputs optionally are input to the second constant multiplier group 15 again, in order to realize calculating σ
k(α
i)
k, the most relevant multiplication result of calculation of the second constant multiplier group 15 is sent into each adder summation to realize
The result and the wrong multinomial coefficient σ of summation
0Compare and can judge whether this position makes mistakes, if equate that expression is wrong root of polynomial, make mistakes in this position, otherwise error-free.In this process, the relevant intermediate object program with 15 outputs of the second constant multiplier group is stored in second registers group 14 simultaneously, is used for the search of next round money.When selector group 13 is searched at first round money, select the result of the output first constant multiplier 12, take turns the money search since second and all export the intermediate object program value of preserving in second registers group 14.
Embodiment two
Referring to Fig. 3, the circuit theory diagrams of parallel money searcher second embodiment of the efficient low delay of expression the present invention.The parallel money searcher that present embodiment two can be joined for a kind of short-period error correction can satisfy compatible multiple error correction requirement.The parallel money searcher that said short-period error correction can be joined comprises first registers group 11, the first constant multiplier group 121,122,123......, first selector group (first value selector) 13, second selector group (error correction requires the selector group) 18, second registers group 14, the second constant multiplier group 15, the group of input summer more than one 16 and a comparator bank 17.Present embodiment two has increased second selector group 18 and a plurality of first constant multiplier groups, and other part is identical with embodiment one, below the concise and to the point device of implementing increase in two of describing.
When the compatible weak point of long error correcting capability error correcting capability, need to add initial value counting circuit and certain control circuit: (1) is at first to different error correction increase in demand constant multiplier A
i, the error correction increase in demand constant multiplier group 122 that promptly basis increases newly on the basis of original constant multiplier group 121, constant multiplier group 123......; (2) increase by one group of second selector group 18 again, be used for selecting the result who imports constant multiplier group 121 or constant multiplier group 122 or other constant multiplier group to output to first selector group 13, detailed circuit is seen Fig. 3.
If during the compatible length of short error correcting capability error correcting capability, then needing more increase public parallel constant multiplier B by rule
Ij, make the multiplier number in its parallel constant multiplier group satisfy t
Max* w, t wherein
MaxError correcting capability for maximum.
That is to say that when the multiple error correction of compatibility required, money searcher of the present invention only need be constructed a spot of multiplier and some selectors after having constructed circuit according to long error correcting capability, just can accomplish the compatibility to short error correcting capability; And increase constant multiplier B by rule
IjAfter, also can realize the compatible long error correcting capability of short error correcting capability.
This shows that the present invention does not need the reconstruct entire circuit, thereby practiced thrift production cost widely when realizing that error correcting capability is compatible.
Only be preferred implementation of the present invention below, should be pointed out that above-mentioned preferred implementation should not be regarded as limitation of the present invention, protection scope of the present invention should be as the criterion with claim institute restricted portion.For those skilled in the art, do not breaking away from the spirit and scope of the present invention, can also make some improvement and retouching, these improvement and retouching also should be regarded as protection scope of the present invention.
Claims (10)
1. the parallel money search method of an efficient low delay is characterized in that, may further comprise the steps:
In a clock cycle, with the wrong polynomial factor sigma that is deposited with in the coefficient register group
1, σ
2..., σ
tSend into beginning constant multiplier group A
i(among 1≤i≤t), again the output result of initial constant multiplier group and the intermediate object program of public parallel constant multiplier group output are outputed to relatively independent public parallel constant multiplier group B through first value selector group
Ij(among the 1≤i≤t, 1≤j≤w), n the position of the realizing code-aiming block galois field multiplying that walks abreast, code length n>=2 wherein, t is specific error correction requirement, w is a degree of parallelism;
Galois field multiplication result with the correspondence position in n the position of code block carries out the galois field summation operation in many input summers group respectively;
With galois field summation operation result and wrong polynomial factor sigma
0In comparator bank, compare the effective errors present in n the position of judgement code block;
In the said process,, be used for taking turns the money search and output to public parallel constant multiplier group through first value selector group since second simultaneously with the accordingly result storage of public parallel constant multiplier group.
2. the parallel money search method of efficient low delay as claimed in claim 1 is characterized in that, the galois field multiplication result of correspondence position in n the position of code block is stored in the scratch-pad register group.
3. the parallel money search method of efficient low delay as claimed in claim 2 is characterized in that,
Take turns money search since second, the storing value in the scratch-pad register group is delivered in the public parallel constant multiplier group as initial value, with the galois field multiplying that walks abreast of next n position of realization code-aiming block through first value selector group;
Respectively the galois field multiplication result of correspondence position is carried out the galois field summation operation by many input summers group again;
And by comparator bank with galois field summation operation result and wrong polynomial factor sigma
0Make comparisons the effective errors present in n the position of judgement epicycle money search.
4. like the parallel money search method of claim 1,2 or 3 described efficient low delays, it is characterized in that, choose n=2
m(n, k t), choose front 2 to-1 long BCH code on this yard collection
m-1-a-l position is zero code word entirely, removes wherein front 2
m-1-a-l position zero as after the code word, constitute shorten sign indicating number (a+l, a, t) sign indicating number, wherein m is a positive integer, m>=3, k is the information bit length of non-shortening binary system BCH code, a is effective information bit length, redundant digit is l=mt.
5. the parallel money searcher of an efficient low delay is characterized in that, comprises coefficient register group, initial constant multiplier group, first value selector group, relatively independent public parallel constant multiplier group, many input summers group and comparator bank, wherein:
The coefficient register group is used for the polynomial factor sigma of storage errors
1, σ
2..., σ
t
Initial constant multiplier group A
i(1≤i≤t), be used in a clock cycle, reception is deposited with the wrong polynomial coefficient in the coefficient register group and carries out corresponding computing;
Just the value selector group is used for the output result of initial constant multiplier group and the intermediate object program of public parallel constant multiplier group output are optionally outputed to public parallel constant multiplier group;
Public parallel constant multiplier group B
Ij(1≤i≤t, 1≤j≤w), n the position that is used to the to realize code-aiming block galois field multiplying that walks abreast, wherein, and code length n>=2, t is specific error correction requirement, w is a degree of parallelism; Simultaneously, the accordingly result of this public parallel constant multiplier group is stored, and is used for taking turns the money search since second and outputs to public parallel constant multiplier group through first value selector group;
Many input summers group is used for respectively the galois field multiplication result of the correspondence position of n position of code block is carried out the galois field summation operation;
Comparator bank is used for galois field summation operation result and wrong polynomial factor sigma
0Relatively, the effective errors present in n the position of judgement code block.
6. like the parallel money searcher of the said efficient low delay of claim 5, it is characterized in that, comprise the scratch-pad register group, be used for storing the galois field multiplication result of n position correspondence position of code block.
7. like the parallel money searcher of the said efficient low delay of claim 6; It is characterized in that; First value selector group; Can be used for taking turns the money search, the storing value output in the selection scratch-pad register group, galois field multiplying so that next n position of public parallel constant multiplier group code-aiming block walks abreast since second; Respectively the galois field multiplication result of correspondence position is carried out the galois field summation operation by many input summers group afterwards; And by comparator bank with galois field summation operation result and wrong polynomial factor sigma
0Make comparisons the effective errors present in n the position of judgement epicycle money search.
8. like the parallel money searcher of each said efficient low delay of claim 5～7; It is characterized in that; Be the parallel money searcher of the compatible short error correcting capability of long error correcting capability, it is provided with a plurality of initial constant multiplier groups, wherein the corresponding a kind of error correction demand of each initial constant multiplier group.
9. like the parallel money searcher of the said efficient low delay of claim 8, it is characterized in that, comprise error correction requirement selector group, be used to select the result of calculation of the initial constant multiplier group of corresponding error correction demand to output to just among the value selector group.
10. like the parallel money searcher of the said efficient low delay of claim 5～7, it is characterized in that be the parallel money searcher of the compatible long error correcting capability of short error correcting capability, the multiplier number in its public parallel constant multiplier group is t
Max* w is individual, wherein t
MaxBe maximum error correcting capability.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2012100461297A CN102594370B (en) | 2012-02-27 | 2012-02-27 | High-efficient low-delay parallel Chien search method and device |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2012100461297A CN102594370B (en) | 2012-02-27 | 2012-02-27 | High-efficient low-delay parallel Chien search method and device |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN102594370A true CN102594370A (en) | 2012-07-18 |
| CN102594370B CN102594370B (en) | 2013-11-27 |
Family
ID=46482625
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN2012100461297A Expired - Fee Related CN102594370B (en) | 2012-02-27 | 2012-02-27 | High-efficient low-delay parallel Chien search method and device |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN102594370B (en) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN106067825A (en) * | 2016-07-01 | 2016-11-02 | 建荣集成电路科技(珠海)有限公司 | BCH pre-search circuit, BCH decoding circuit, BCH pre-searching method and BCH error correction method |
| CN111694692A (en) * | 2020-06-24 | 2020-09-22 | 山东云海国创云计算装备产业创新中心有限公司 | Data storage erasure method, device and equipment and readable storage medium |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20030140302A1 (en) * | 2002-01-23 | 2003-07-24 | Litwin, Louis Robert | Chien search cell for an error-correcting decoder |
| CN101079640A (en) * | 2007-07-12 | 2007-11-28 | 中兴通讯股份有限公司 | Reed-Solomon code decoder |
| CN101252361A (en) * | 2007-10-11 | 2008-08-27 | 深圳市中兴集成电路设计有限责任公司 | Area compact type BCH paralleling decoding circuit supporting pre searching |
-
2012
- 2012-02-27 CN CN2012100461297A patent/CN102594370B/en not_active Expired - Fee Related
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20030140302A1 (en) * | 2002-01-23 | 2003-07-24 | Litwin, Louis Robert | Chien search cell for an error-correcting decoder |
| CN101079640A (en) * | 2007-07-12 | 2007-11-28 | 中兴通讯股份有限公司 | Reed-Solomon code decoder |
| CN101252361A (en) * | 2007-10-11 | 2008-08-27 | 深圳市中兴集成电路设计有限责任公司 | Area compact type BCH paralleling decoding circuit supporting pre searching |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN106067825A (en) * | 2016-07-01 | 2016-11-02 | 建荣集成电路科技(珠海)有限公司 | BCH pre-search circuit, BCH decoding circuit, BCH pre-searching method and BCH error correction method |
| CN106067825B (en) * | 2016-07-01 | 2017-10-13 | 建荣集成电路科技(珠海)有限公司 | BCH pre-searchs circuit, BCH decoding circuits, BCH pre-searching methods and BCH error correction methods |
| CN111694692A (en) * | 2020-06-24 | 2020-09-22 | 山东云海国创云计算装备产业创新中心有限公司 | Data storage erasure method, device and equipment and readable storage medium |
| CN111694692B (en) * | 2020-06-24 | 2022-04-22 | 山东云海国创云计算装备产业创新中心有限公司 | Data storage erasure method, device and equipment and readable storage medium |
Also Published As
| Publication number | Publication date |
|---|---|
| CN102594370B (en) | 2013-11-27 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN101227194B (en) | Circuit, encoder and method for encoding parallel BCH | |
| CN102546089B (en) | Method and device for implementing cycle redundancy check (CRC) code | |
| CN101277119B (en) | Method for complexing hardware of Reed Solomon code decoder as well as low hardware complex degree decoding device | |
| CN107239362B (en) | Parallel CRC (Cyclic redundancy check) code calculation method and system | |
| CN105322973B (en) | A kind of RS code coder and coding method | |
| CN108282265B (en) | Error correction encoding method, apparatus, device and computer readable storage medium | |
| CN102970049B (en) | Based on parallel circuit and the RS decoding circuit of money searching algorithm and Fu Ni algorithm | |
| CN102160031A (en) | system and method to execute a linear feedback-shift instruction | |
| CN101296053A (en) | Method and system for calculating cyclic redundancy check code | |
| CN102820892A (en) | Circuit for parallel BCH (broadcast channel) coding, encoder and method | |
| CN103986475A (en) | Parallel decomposition of reed solomon umbrella codes | |
| CN102594370B (en) | High-efficient low-delay parallel Chien search method and device | |
| Chu et al. | A fully parallel BCH codec with double error correcting capability for NOR flash applications | |
| CN101425875B (en) | Decoder | |
| CN101848001B (en) | Data length expanding method of BCH (broadcast Channel) coding and decoding in Flash controller | |
| CN102761340A (en) | Broadcast channel (BCH) parallel coding circuit | |
| CN103763064A (en) | CRC code generating method and circuit applicable to ultra-high-speed communication system | |
| CN101001089B (en) | Money search method and device in error correction decode | |
| CN110570171B (en) | Transaction pool node synchronization method, electronic device and computer-readable storage medium | |
| CN103916138B (en) | A kind of money search circuit and ECC decoding apparatus and method based on the money search circuit | |
| CN102684710B (en) | Viterbi decoding method of tail-biting convolutional code based on SSE (Streaming Simd Extensions) | |
| CN103138881B (en) | Decoding method and equipment | |
| US10009041B2 (en) | BCH decorder in which folded multiplier is equipped | |
| US10067821B2 (en) | Apparatus and method for cyclic redundancy check | |
| CN102546109A (en) | RS (Reed-Solomon) decoding device and method for 10G Ethernet Passive Optical Network (EPON) |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| ASS | Succession or assignment of patent right |
Owner name: SHENZHEN STATEMICRO ELECTRONICS CO., LTD. Free format text: FORMER OWNER: CHENGDU STATEMICRO ELECTRONICS CO., LTD. Effective date: 20150121 |
|
| C41 | Transfer of patent application or patent right or utility model | ||
| COR | Change of bibliographic data |
Free format text: CORRECT: ADDRESS; FROM: 610041 TO: 518063 SHENZHEN, GUANGDONG PROVINCE |
|
| TR01 | Transfer of patent right |
Effective date of registration: 20150121 Address after: 518063 Guangdong city of Shenzhen province Nanshan District Gao Xin Road No. 015 building six layer A in micro research Patentee after: SHENZHEN STATE MICROELECTRONICS Co.,Ltd. Address before: 3 building, A1 building, A District, Tianfu Software Park, Chengdu hi tech Zone, Sichuan, 610041 Patentee before: CHENGDU STATE MICROELECTRONIC Co.,Ltd. |
|
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20131127 |
|
| CF01 | Termination of patent right due to non-payment of annual fee |