CN101951265A - Method and device for computing error location polynomial in decoding through binary BCH (Bose-Chaudhuri-Hocquenghem) code - Google Patents

Abstract

The invention discloses a method and a device for computing an error location polynomial in decoding through a binary BCH (Bose-Chaudhuri-Hocquenghem) code. The method comprises the following steps of: (1) starting iteration from an even number according to a computed syndrome, initializing a step-length initial value i and computing the initial parameter of the error location polynomial; (2) computing the ith iterated error location polynomial and an i+2nd iterated correction term; (3) judging and computing the parameter of the next iterative computation; (4) setting the step length of value buil-up constant of i to be 2, i.e. i<=i+2; (5) comparing the value of iteration times with 2t-1, selecting to continue iteration according to a comparison result, and turning to the step (2), or ending the iteration and turning to a step (6) for processing; and (6) outputting the i-2nd iterated error location polynomial, and finishing the computation. The invention also greatly reduces the power consumption of a decoding circuit while reducing the binary BCH decoding delay.

Description

The binary system BCH code is the polynomial method and apparatus in mistake in computation position in decoding

Technical field

The present invention relates to binary system Bose-Chaudhuri Hocquenghem error correction codes encoding and decoding technique field, particularly relate to a kind of in the decode procedure of binary system Bose-Chaudhuri Hocquenghem error correction codes the polynomial method and apparatus in mistake in computation position.

Background technology

Bose-Chaudhuri Hocquenghem error correction codes (also being BCH code) is a kind of error correction that is used for, and is specially adapted to the circular test sign indicating number that random error is proofreaied and correct.Propose jointly by R.C.Bose, D.K.Chaudhuri and A.Hocquenghem.It treats information source the information sequence of sending out is divided into message groups for one group by fixing κ position, and (the binary digit group of n＞κ) is called code word each message groups independence conversion to be grown into n again.The process that message groups is transformed into code word calls coding, and its inverse process is called decoding.

BCH code has tight algebraic process, is to study a most thorough class sign indicating number at present, and be a kind of error correcting code the most frequently used in communication and the storage system.Between its generator polynomial and the minimum distance confidential relation is arranged, people can be easy to construct BCH code according to desired error correcting capability t, and their decoder is also realized easily.General BCH code decoder is to realize (setting t and be the number of the random error that BCH code can correct) by following step in the prior art:

1) calculates syndrome S by the code word R that receives (x) _q(1≤q≤2t);

2) according to syndrome S _qCalculate error location polynomial σ (x);

3) solve the root of error location polynomial σ (x) with chien search (Chien search) method, obtain errors present, thereby determine error pattern E (x);

4) by the code word V (x) after R (x)-E (x) obtains correcting.

Wherein the 2nd step adopt usually 2t time little iteration of hardware complexity the contrary BM method of nothing (inversionless Berlekamp-Massey iBM) realizes, this method is as described below:

Initial condition:

D ^(-1)＝0，σ ^(-1)(x)＝τ ^(-1)(x)＝1，δ ⁽⁰⁾＝1，Δ ⁽⁰⁾＝S ₁

for?i＝0?to?2t-1

$\left\{\begin{array}{c}{\mathrm{\&sigma;}}^{\left(i\right)}\left(x\right)={\mathrm{\&delta;}}^{\left(i\right)}\&CenterDot;{\mathrm{\&sigma;}}^{(i-1)}\left(x\right)+{\mathrm{\&Delta;}}^{\left(i\right)}x{\mathrm{\&tau;}}^{(i-1)}\left(x\right)\\ {\mathrm{\&Delta;}}^{(i+1)}=S_{i+2}\&CenterDot;{\mathrm{\&sigma;}}_0^{\left(i\right)}+S_{i+1}\&CenterDot;{\mathrm{\&sigma;}}_1^{\left(i\right)}+...+S_{i+2-v_i}\&CenterDot;{\mathrm{\&sigma;}}_{v_i}^{\left(i\right)}\end{array}\right.---\left(1\right)$

ifΔ ⁽ⁱ⁾＝0?or?2D ^(i-1)≥i+1

D ⁽ⁱ⁾＝D ^(i-1)，δ ⁽ⁱ⁺¹⁾＝δ ⁽ⁱ⁾，τ ⁽ⁱ⁾(x)＝xτ ^(i-1)(x)

else

D ⁽ⁱ⁾＝i+1-D ^(i-1)，δ ⁽ⁱ⁺¹⁾＝Δ ⁽ⁱ⁾，τ ⁽ⁱ⁾(x)＝σ ^(i-1)(x)

σ wherein ⁽ⁱ⁾(x) be the error location polynomial of the i time iteration, v _iBe σ ⁽ⁱ⁾(x) number of times, σ _j ⁽ⁱ⁾(0≤j≤v _i) be σ ⁽ⁱ⁾(x) coefficient; Δ ⁽ⁱ⁾Be the correction term of the i time iteration, δ ⁽ⁱ⁾Be the i time last non-vanishing correction term before the iteration; τ ⁽ⁱ⁾(x) be the Auxiliary polynomial of the i time iteration, D ⁽ⁱ⁾Be auxiliary time number variable.

But this does not have the increase of the serial line unit of contrary BM method along with t the realization of prior art at present, and N is with t ²For radix increases, then the speed of BCH code decoder more and more restricts the computing time in this device, and along with error correcting capability t requires under the more and more higher situation, this method increases the BCH decoding delay greatly, has also increased the power consumption of decoding circuit simultaneously greatly.

Summary of the invention

The object of the present invention is to provide a kind of binary system BCH code polynomial method and apparatus in mistake in computation position in decoding, it has also reduced the power consumption of decoding circuit greatly when reducing binary system BCH decoding delay.

A kind of binary system BCH code polynomial method in mistake in computation position in decoding for realizing that the object of the invention provides comprises the following steps:

Step S100, according to the syndrome that calculates, iteration is from even number, the polynomial initial parameter of initialization step-length initial value i and mistake in computation position;

Step S200 calculates the error location polynomial of the i time iteration and the correction term of the i+2 time iteration;

Step S300 judges and calculates the next iteration parameters calculated;

Step S400 is 2 step-length with the value growth constant of i, promptly

Step S500 compares the value and the 2t-1 of iterations, and selects to continue iteration according to comparative result and change step S200, and perhaps finishing iteration is changeed step S600 processing;

Step S600 with the error location polynomial output of the i-2 time iteration, finishes.

More preferably, described step S100 comprises the following steps:

According to the syndrome S that calculates ₁, iteration is initially from-2, initialization iterations i=0, and the polynomial initial parameter in initialization mistake in computation position, i.e. the number of times variables D is assisted in initialization ⁽²⁾=0; The error location polynomial σ of the-2 iteration ⁽²⁾(x)=1; The Auxiliary polynomial τ of the-2 iteration ⁽²⁾(x)=x ^-1The 0th iteration last non-vanishing correction term δ before ⁽⁰⁾=1; The correction term Δ of the 0th iteration ⁽⁰⁾=S ₁

More preferably, described step S200 comprises the following steps:

Calculate the error location polynomial σ of the i time iteration ⁽ⁱ⁾(x) and the correction term Δ of the i+2 time iteration ⁽ⁱ⁺²⁾, be shown below;

$\left\{\begin{array}{c}{\mathrm{\&sigma;}}^{\left(i\right)}\left(x\right)={\mathrm{\&delta;}}^{\left(i\right)}\&CenterDot;{\mathrm{\&sigma;}}^{(i-2)}\left(x\right)+{\mathrm{\&Delta;}}^{\left(i\right)}{x}^2{\mathrm{\&tau;}}^{(i-2)}\left(x\right)\\ {\mathrm{\&Delta;}}^{(i+2)}=S_{i+3}\&CenterDot;{\mathrm{\&sigma;}}_0^{\left(i\right)}+S_{i+2}\&CenterDot;{\mathrm{\&sigma;}}_1^{\left(i\right)}+...+S_{i+3-v_i}\&CenterDot;{\mathrm{\&sigma;}}_{v_i}^{\left(i\right)}\end{array}\right..$

More preferably, described step S300 comprises the following steps:

Step S310 judges the correction term Δ of the i time iteration ⁽ⁱ⁾Whether equal 0, perhaps formula 2D ^(i-2)Whether 〉=i+1 sets up;

If step S320 is the correction term Δ of the i time iteration ⁽ⁱ⁾Equal 0, perhaps 2D ^(i-2)〉=i+1 sets up, then D ⁽ⁱ⁾=D ^(i-2), δ ⁽ⁱ⁺²⁾=δ ⁽ⁱ⁾, τ ⁽ⁱ⁾(x)=x ²τ ^(i-2)(x);

If step S330 is the correction term Δ of the i time iteration ⁽ⁱ⁾Be not equal to zero, and 2D ^(i-2)〉=i+1 is false, then D ⁽ⁱ⁾=i+1-D ^(i-2), δ ⁽ⁱ⁺²⁾=Δ ⁽ⁱ⁾, τ ⁽ⁱ⁾(x)=σ ^(i-2)(x).

More preferably, described step S500 comprises the following steps:

Whether the value that judge to increase step-length and be the i after 2 is less than 2t-1; If the value of i less than 2t-1, then forwards step S200 to, carry out the next round iterative computation; If the value of i is not less than 2t-1, then carry out step S600; Wherein, t is the number of the random error that can correct of BCH code.

For realizing that the object of the invention also provides a kind of binary system BCH code polynomial device in mistake in computation position in decoding, comprise 3 GF (2 ^m) Galois field multiplier; 2 GF (2 ^m) the finite field adder; The registers group of 2 groups of each (t+1) individual m positions; The multiplexed selector of 2 m positions; The register of 4 m positions.

The invention has the beneficial effects as follows: BCH code of the present invention is the polynomial method and apparatus in mistake in computation position in decoding, characteristic according to the binary system Bose-Chaudhuri Hocquenghem error correction codes, only needed t iteration can be in the hope of contrary BM method of the nothing of the multinomial σ (x) that makes mistake and device, be N≤t * (t+3)/2 its computing time, the computing time of half can be saved than the method for prior art, it is along with error correcting capability t requires under the more and more higher situation, the relative prior art of this method has also reduced the power consumption of decoding circuit greatly when reducing the BCH decoding delay.

Description of drawings

Fig. 1 is embodiment of the invention binary system BCH code polynomial method flow diagram in mistake in computation position in decoding;

Fig. 2 is the structural representation of embodiment of the invention binary system BCH code polynomial device in mistake in computation position in decoding.

Wherein:

101GF (2 ^m) Galois field multiplier

102GF (2 ^m) Galois field multiplier

103GF (2 ^m) Galois field multiplier

104GF (2 ^m) the finite field adder

105GF (2 ^m) the finite field adder

The registers group of the individual m of 106 (t+1) position

The registers group of the individual m of 107 (t+1) position

108 multiplexed selectors

109 multiplexed selectors

The register of 110m position

The register of 111m position

The register of 112m position

The register of 113m position

Embodiment

In order to make purpose of the present invention, technical scheme and advantage clearer,, binary system BCH code of the present invention polynomial method and apparatus in mistake in computation position in decoding is further elaborated below in conjunction with drawings and Examples.Should be appreciated that specific embodiment described herein only in order to explanation the present invention, and be not used in qualification the present invention.

The binary system BCH code of the embodiment of the invention is the polynomial method and apparatus in mistake in computation position in decoding, characteristic according to the binary system Bose-Chaudhuri Hocquenghem error correction codes, obtaining a kind of needs t iteration can be in the hope of the device of the contrary BM method of the nothing of the multinomial σ (x) that makes mistake and this method of realization, it is binary system BCH code polynomial method and apparatus in mistake in computation position in decoding, be N≤t * (t+3)/2, can save the computing time of half its computing time.

The binary system BCH code of the embodiment of the invention is the polynomial method in mistake in computation position in decoding, is to obtain according to following theoretical derivation:

In the existing theory, to the binary system Bose-Chaudhuri Hocquenghem error correction codes, the Δ in contrary BM (IBM) method of described nothing ⁽ⁱ⁾Equal zero during at i for odd number, this characteristic is at a lot of error control coding (Error Control Coding, ECC) document (as: 1. " Error control coding--From theory to practice ", By Peter Sweeney, Publisher:Wiley Number Of Pages:240 Publication Date:2002-05-13ISBN-10/ASIN:047084356X, ISBN-13/, AN:9780470843567Binding:Hardcover, p151,6.12 chapters and sections; 2. " error correcting code---principle and method (revised edition) ", author: king Xin Meixiao state town, publishing house: publishing house of Xian Electronics Science and Technology University; ISBN:7560601634; Publication date: April calendar year 2001; The page number: through proof, therefore, give unnecessary details no longer one by one in embodiments of the present invention 282).

If i is even number (following derivation all is based upon under this condition), (i-2) inferior iteration result obtains the error location polynomial σ of the i-2 time iteration ^(i-2)(x), the Auxiliary polynomial τ of the i-2 time iteration ^(i-2)(x), the auxiliary number of times variables D of the i-2 time iteration ^(i-2), σ ^(i-1)(x) coefficient δ ^(i-1)Correction term Δ with the i-2 time iteration ^(i-1), then, the correction term Δ of the i-1 time iteration is arranged then because of being odd number (i-1) ^(i-1)=0, according to formula (1)～formula (3), thereby (i-1) inferior iteration result is as the formula (4):

$\left\{\begin{array}{c}{\mathrm{\&sigma;}}^{(i-1)}\left(x\right)={\mathrm{\&delta;}}^{(i-1)}\&CenterDot;{\mathrm{\&sigma;}}^{(i-2)}\left(x\right)\\ {\mathrm{\&tau;}}^{(i-1)}\left(x\right)=x{\mathrm{\&tau;}}^{(i-2)}\left(x\right)\\ D^{(i-1)}=D^{(i-2)}\\ {\mathrm{\&delta;}}^{\left(i\right)}={\mathrm{\&delta;}}^{(i-1)}\\ {\mathrm{\&Delta;}}^{\left(i\right)}=S_{i+1}\&CenterDot;{\mathrm{\&sigma;}}_0^{(i-2)}+S_i\&CenterDot;{\mathrm{\&sigma;}}_1^{(i-1)}+...+S_{i+1-v_{i-1}}\&CenterDot;{\mathrm{\&sigma;}}_{v_{i-1}}^{(i-1)}\end{array}\right.---\left(4\right)$

Because the error location polynomial σ of the i-1 time iteration ^(i-1)(x) just at the error location polynomial σ of the i-2 time iteration ^(i-2)(x) basic superior constant δ ^(i-1), so σ ^(i-1)(x) and σ ^(i-2)(x) root is identical, thus σ ^(i-1)(x) number of times equals σ ^(i-2)(x) number of times, i.e. v _I-1=v _I-2What it should be noted that when the mistake in computation multinomial embodiment of the invention is concerned about is wrong root of polynomial, and σ ^(i-1)(x) and σ ^(i-2)(x) root is identical, so can directly use σ _j ^(i-2)(0≤j≤v _i) alternative σ _j ^(i-1)(0≤j≤v _i), promptly use σ ^(i-2)(x) coefficient substitutes σ ^(i-1)(x) coefficient, Δ simultaneously ⁽ⁱ⁾Calculating also do corresponding replacement, this is to not influence of iteration result, because new σ ^(i-1)(x) coefficient and Δ ⁽ⁱ⁾Compare simultaneously divided by constant δ with original value ^(i-1), the influence in next step iteration also only is divided by constant δ so ^(i-1), and can not influence wrong root of polynomial among next step iteration result.Therefore the result of (i-1) inferior iteration can revise as the formula (5):

$\left\{\begin{array}{c}{\mathrm{\&sigma;}}^{(i-1)}\left(x\right)={\mathrm{\&sigma;}}^{(i-2)}\left(x\right)\\ {\mathrm{\&tau;}}^{(i-1)}\left(x\right)=x{\mathrm{\&tau;}}^{(i-2)}\left(x\right)\\ D^{(i-1)}=D^{(i-2)}\\ {\mathrm{\&delta;}}^{\left(i\right)}={\mathrm{\&delta;}}^{(i-1)}\\ {\mathrm{\&Delta;}}^{\left(i\right)}=S_{i+1}\&CenterDot;{\mathrm{\&sigma;}}_0^{(i-2)}+S_i\&CenterDot;{\mathrm{\&sigma;}}_1^{(i-2)}+...+S_{i+1-v_{i-2}}\&CenterDot;{\mathrm{\&sigma;}}_{v_{i-2}}^{(i-2)}\end{array}\right.---\left(5\right)$

According to prior art, the result of the i time iteration is as follows:

$\left\{\begin{array}{c}{\mathrm{\&sigma;}}^{\left(i\right)}\left(x\right)={\mathrm{\&delta;}}^{\left(i\right)}\&CenterDot;{\mathrm{\&sigma;}}^{(i-1)}\left(x\right)+{\mathrm{\&Delta;}}^{\left(i\right)}x{\mathrm{\&tau;}}^{(i-1)}\left(x\right)\\ {\mathrm{\&Delta;}}^{(i+1)}=0\end{array}\right.$

IfΔ ⁽ⁱ⁾＝0?or?2D ^(i-1)≥i+1 (6)

D ⁽ⁱ⁾＝D ^(i-1)，δ ⁽ⁱ⁺¹⁾＝δ ⁽ⁱ⁾，τ ⁽ⁱ⁾(x)＝xτ ^(i-1)(x)

else

D ⁽ⁱ⁾＝i+1-D ^(i-1)，δ ⁽ⁱ⁺¹⁾＝Δ ⁽ⁱ⁾，τ ⁽ⁱ⁾(x)＝σ ^(i-1)(x)

And the like, the result of (i+1) inferior iteration is as follows:

$\left\{\begin{array}{c}{\mathrm{\&sigma;}}^{(i+1)}\left(x\right)={\mathrm{\&sigma;}}^{\left(i\right)}\left(x\right)\\ {\mathrm{\&tau;}}^{(i+1)}\left(x\right)=x{\mathrm{\&tau;}}^{\left(i\right)}\left(x\right)\\ D^{(i+1)}=D^{\left(i\right)}\\ {\mathrm{\&delta;}}^{(i+2)}={\mathrm{\&delta;}}^{(i+1)}\\ {\mathrm{\&Delta;}}^{(i+2)}=S_{i+3}\&CenterDot;{\mathrm{\&sigma;}}_0^{\left(i\right)}+S_{i+2}\&CenterDot;{\mathrm{\&sigma;}}_1^{\left(i\right)}+...+S_{i+3-v_i}\&CenterDot;{\mathrm{\&sigma;}}_{v_i}^{\left(i\right)}\end{array}\right.---\left(7\right)$

With the iteration of formula (6) and (7) substitution the i time formula (6) as a result, obtain the i time final iteration result as the formula (8):

$\left\{\begin{array}{c}{\mathrm{\&sigma;}}^{\left(i\right)}\left(x\right)={\mathrm{\&delta;}}^{\left(i\right)}\&CenterDot;{\mathrm{\&sigma;}}^{(i-2)}\left(x\right)+{\mathrm{\&Delta;}}^{\left(i\right)}{x}^2{\mathrm{\&tau;}}^{(i-2)}\left(x\right)\\ {\mathrm{\&Delta;}}^{(i+2)}=S_{i+3}\&CenterDot;{\mathrm{\&sigma;}}_0^{\left(i\right)}+S_{i+2}\&CenterDot;{\mathrm{\&sigma;}}_1^{\left(i\right)}+...+S_{i+3-v_i}\&CenterDot;{\mathrm{\&sigma;}}_{v_i}^{\left(i\right)}\end{array}\right.$

IfΔ ⁽ⁱ⁾＝0?or?2D ^(i-2)≥i+1 (8)

D ⁽ⁱ⁾＝D ^(i-2)，δ ⁽ⁱ⁺²⁾＝δ ⁽ⁱ⁾，τ ⁽ⁱ⁾(x)＝x ²τ ^(i-2)(x)

else

D ⁽ⁱ⁾＝i+1-D ^(i-2)，δ ⁽ⁱ⁺²⁾＝Δ ⁽ⁱ⁾，τ ⁽ⁱ⁾(x)＝σ ^(i-2)(x)

Iteration result according to the i time analogizes, δ ⁽ⁱ⁾And Δ ⁽ⁱ⁾Can obtain by (i-2) inferior iteration of new algorithm fully.Can draw according to above-mentioned derivation,, and know the σ as a result of (i-2) inferior iteration if i is an even number ^(i-2)(x), τ ^(i-2)(x), D ^(i-2), δ ⁽ⁱ⁾And Δ ⁽ⁱ⁾Then do not need to calculate the result of (i-1) inferior iteration, directly can calculate the result of i iteration according to (i-2) result of inferior iteration, and calculate the required correlated variables of (i+2) iterative computation, promptly only need carry out the iterative computation of iteration when being denoted as even number, thereby can save the computing time of half.

Above-mentioned derivation requires primary iteration to be masked as even number, and the primary iteration of prior art is masked as-1, therefore, in the embodiment of the invention, expands iteration forward one time, is about to the primary iteration sign and is set at-2.

By with the original initializer substitution formula (5) in i=0 and (1) formula, and the original initializer in the convolution (1), obtain new initializer as the formula (9):

D ^(-2)＝0，σ ^(-2)(x)＝1，τ ^(-2)(x)＝x ^-1，δ ⁽⁰⁾＝1，Δ ⁽⁰⁾＝S ₁ (9)

Wherein, x be used for representing polynomial, to σ (x), σ _j(0≤j≤t) is its coefficient, and then σ (x) can be expressed as σ (x)=σ ₀x ⁰+ σ ₁x ¹+ σ ₂x ²+ ... + σ _tx ^t, σ wherein _j, x ∈ GF (2 ^m), the code word size of this BCH code is n=2 ^m-1

And, according to formula (5), set up suc as formula the condition of (10):

σ ^(2t-1)(x)＝σ ^(2t-2)(x) (10)

The σ as a result of (2t-2) inferior iteration then ^(2t-2)(x) be final error location polynomial.

According to above derivation, obtain embodiment of the invention BCH code polynomial method in mistake in computation position in decoding, as shown in Figure 1, comprise the following steps:

Step S100, according to the syndrome that calculates, iteration is from even number, the polynomial initial parameter of initialization step-length initial value i and mistake in computation position;

According to the syndrome S that calculates ₁, iteration is initially from-2, initialization iterations i=0, and the polynomial initial parameter in initialization mistake in computation position, i.e. the number of times variables D is assisted in initialization ⁽²⁾=0; The error location polynomial σ of the-2 iteration ⁽²⁾(x)=1; The Auxiliary polynomial τ of the-2 iteration ⁽²⁾(x)=x ^-1The 0th iteration last non-vanishing correction term δ before ⁽⁰⁾=1; The correction term Δ of the 0th iteration ⁽⁰⁾=S ₁

Step S200 calculates the error location polynomial of the i time iteration and the correction term of the i+2 time iteration;

Calculate the error location polynomial σ of the i time iteration ⁽ⁱ⁾(x) and the correction term Δ of the i+2 time iteration ⁽ⁱ⁺²⁾, as the formula (11);

$\left\{\begin{array}{c}{\mathrm{\&sigma;}}^{\left(i\right)}\left(x\right)={\mathrm{\&delta;}}^{\left(i\right)}\&CenterDot;{\mathrm{\&sigma;}}^{(i-2)}\left(x\right)+{\mathrm{\&Delta;}}^{\left(i\right)}{x}^2{\mathrm{\&tau;}}^{(i-2)}\left(x\right)\\ {\mathrm{\&Delta;}}^{(i+2)}=S_{i+3}\&CenterDot;{\mathrm{\&sigma;}}_0^{\left(i\right)}+S_{i+2}\&CenterDot;{\mathrm{\&sigma;}}_1^{\left(i\right)}+...+S_{i+3-v_i}\&CenterDot;{\mathrm{\&sigma;}}_{v_i}^{\left(i\right)}\end{array}\right.---\left(11\right)$

Step S300 judges and calculates the next iteration parameters calculated;

Step S300 comprises the following steps:

Step S310 judges the correction term Δ of the i time iteration ⁽ⁱ⁾Whether equal 0, perhaps formula 2D ^(i-2)Whether 〉=i+1 sets up;

If step S320 is the correction term Δ of the i time iteration ⁽ⁱ⁾Equal 0, perhaps 2D ^(i-2)〉=i+1 sets up, then

D ⁽ⁱ⁾＝D ^(i-2)，δ ⁽ⁱ⁺²⁾＝δ ⁽ⁱ⁾，τ ⁽ⁱ⁾(x)＝x ²τ ^(i-2)(x)； (12)

If step S330 is the correction term Δ of the i time iteration ⁽ⁱ⁾Be not equal to zero, and 2D ^(i-2)〉=i+1 is false, then

D ⁽ⁱ⁾＝i+1-D ^(i-2)，δ ⁽ⁱ⁺²⁾＝Δ ⁽ⁱ⁾，τ ⁽ⁱ⁾(x)＝σ ^(i-2)(x) (13)

Step S400 is 2 step-length with the value growth constant of i, promptly

Step S500, the value and the 2t-1 of comparison iterations, and according to comparative result selection continuation iteration or finishing iteration;

Whether the value that judge to increase step-length and be the i after 2 is less than 2t-1; If the value of i less than 2t-1, then forwards step S200 to, carry out the next round iterative computation; If the value of i is not less than 2t-1, then carry out step S600; Wherein, t is the number of the random error that can correct of BCH code.

Step S600 is with the error location polynomial σ of the i-2 time iteration ⁽ⁱ⁾(x) output is finished.

As a kind of embodiment, the binary system BCH code of the embodiment of the invention is the polynomial method in mistake in computation position in decoding, can be achieved as follows:

Because it is even number forever that the iteration of required calculating indicates i, then establish i=2i ' (0＜=i '＜=t-1) substitution formula (11), then the result of the i time iteration can be revised as formula (14):

$\left\{\begin{array}{c}{\mathrm{\&sigma;}}^{\left(2i^{\&prime;}\right)}\left(x\right)={\mathrm{\&delta;}}^{\left(2i^{\&prime;}\right)}\&CenterDot;{\mathrm{\&sigma;}}^{\left(2(i^{\&prime;}-1)\right)}\left(x\right)+{\mathrm{\&Delta;}}^{\left(2i^{\&prime;}\right)}{x}^2{\mathrm{\&tau;}}^{\left(2(i^{\&prime;}-1)\right)}\left(x\right)\\ {\mathrm{\&Delta;}}^{\left(2(i^{\&prime;}+1)\right)}=S_{2i^{\&prime;}+3}\&CenterDot;{\mathrm{\&sigma;}}_0^{\left(2i^{\&prime;}\right)}+S_{2i^{\&prime;}+2}\&CenterDot;{\mathrm{\&sigma;}}_1^{\left(2i^{\&prime;}\right)}+...+S_{2i^{\&prime;}+3-v_{2i^{\&prime;}}}\&CenterDot;{\mathrm{\&sigma;}}_{v_{2i^{\&prime;}}}^{\left(2i^{\&prime;}\right)}\end{array}\right.$

if?Δ ^(2i′)＝0?or?2D ^(2(i′-1))≥2i′+1 (14)

D ^(2i′)＝D ^(2(i′-1))，δ ^(2(i′+1))＝δ ^(2i′)，τ ^(2i′)(x)＝x ²τ ^(2(i′-1))(x)

else

D ^(2i′)＝2i′+1-D ^(2(i′-1))，δ ^(2(i′+1))＝Δ ^(2i′)，τ ^(2i′)(x)＝σ ^(2(i′-1))(x)

Because do not need to calculate the result of odd number time iteration, in the embodiment of the invention, iterations i can be reduced by half, also be the inferior iteration of i ' in the new method after the corresponding iterations of the inferior iteration of 2i ' in the above-mentioned iterative process reduces by half.

The binary system BCH code of the embodiment of the invention is the polynomial method in mistake in computation position in decoding, finishes wrong polynomial calculating by t iteration, and wherein t is repairable wrong figure place.Be N≤t * (t+3)/2, saved the computing time of half compared to existing technology the computing time of the binary system BCH code of the embodiment of the invention polynomial method in mistake in computation position in decoding.

Correspondingly, the present invention also provides a kind of binary system BCH code polynomial device in mistake in computation position in decoding, as shown in Figure 2, comprises 3 GF (2 ^m) (GF (2 for Galois field multiplier ^m) multiplier) 101,102,103; 2 GF (2 ^m) (GF (2 for the finite field adder ^m) adder) 104,105; The registers group (Buffer) 106,107 of 2 groups of each (t+1) individual m positions; The multiplexed selector (MUX) 108,109 of 2 m positions; The register of 4 m positions (Register) 110,111,112,113.

The binary system BCH code of the embodiment of the invention is the polynomial device in mistake in computation position in decoding, realizes that iteration step length is 2 t iteration, establishes σ _j ⁽ⁱ⁾' s is σ ⁽ⁱ⁾(x) coefficient, τ _j ⁽ⁱ⁾' s is τ ⁽ⁱ⁾(x) (device of the embodiment of the invention is to τ for coefficient ⁽ⁱ⁾(x) coefficient has been expanded one

Be used for representing τ ⁽ⁱ⁾(x) initial value x ^-1, but at calculating process also

Do not need for

Prepare memory register, because only under initial condition

Through after iteration

Then

${{\mathrm{\&sigma;}}_j}^{\left(i\right)}=\left\{\begin{array}{cc}{\mathrm{\&delta;}}^{\left(i\right)}\&CenterDot;{\mathrm{\&sigma;}}_0^{(i-2)},& \mathrm{for\; j}=0\\ {\mathrm{\&delta;}}^{\left(i\right)}\&CenterDot;{\mathrm{\&sigma;}}_j^{(i-2)}+{\mathrm{\&Delta;}}^{\left(i\right)}{\mathrm{\&tau;}}_{j-2}^{(i-2)},& \mathrm{for}1\&le;j\&le;v_i\end{array}\right.$ (20)

${\mathrm{\&Delta;}}_j^{(i+2)}=\left\{\begin{array}{cc}0,& \mathrm{for\; j}=0\\ {\mathrm{\&Delta;}}_{j-1}^{(i+2)}+S_{i+4-j}\&CenterDot;{\mathrm{\&sigma;}}_{j-1}^{\left(i\right)},& \mathrm{for}1\&le;j\&le;v_i\end{array}\right.$

In the 0th cycle in (i+2) iteration, obtain

${\mathrm{\&Delta;}}^{(i+2)}={\mathrm{\&Delta;}}_{v_i}^{(i+2)}+S_{i+3-v_i}\&CenterDot;{\mathrm{\&sigma;}}_{v_i}^{\left(i\right)}$

$=...---\left(21\right)$

$=S_{i+3}\&CenterDot;{\mathrm{\&sigma;}}_0^{\left(i\right)}+S_{i+2}\&CenterDot;{\mathrm{\&sigma;}}_1^{\left(i\right)}+...+S_{i+3-v_i}\&CenterDot;{\mathrm{\&sigma;}}_{v_i}^{\left(i\right)}$

In Fig. 2, registers group 106 is used to store the wrong multinomial σ that each iterative computation is come out ⁽ⁱ⁾(x) coefficient; Registers group 107 is used to store the Auxiliary polynomial τ that each iterative computation is come out ⁽ⁱ⁾(x) coefficient; Register 110 is used to store the last non-vanishing correction term δ before the iteration the i time ⁽ⁱ⁾Register 111 is used to store the i time correction term Δ ⁽ⁱ⁾Register 112 is used to be stored in the correction term Δ of the i+2 time iteration that j clock cycle of the i time iteration calculate ⁽ⁱ⁺²⁾Median

Register 113 is used to store the wrong polynomial coefficient that j clock cycle of the i time iteration calculate

Galois field multiplier 101 is used for realization formula (20)

Function; Galois field multiplier 102 is used for realization formula (20)

Function, they and finite field adder 104 are together in the perfect (20)

Calculating, the result of calculation in each cycle is saved in the register 113, the result of register 113 deposits relevant register in the registers group 106 in after participating in finishing the computing of Galois field multiplier 103 successively; Galois field multiplier 103 is used for realization formula (20)

Calculating, the result that each computing cycle calculates is kept at register 112 after by 105 additions of finite field adder; In the 0th cycle of the i+2 time iteration, in the Galois field multiplier 103 realization formulas (21) With the correction term Δ that obtains the i+2 time complete iteration after the preceding intermediate object program addition ⁽ⁱ⁺²⁾, and be saved in the register 111; Multiplexed selector 108 is used for according to condition " Δ ⁽ⁱ⁾Equal 0, perhaps 2D ^(i-2)〉=i+1 " whether become Rob Roy to select τ in the i time iteration ⁽ⁱ⁾(x) coefficient τ _j ⁽ⁱ⁾If the value of ' s is condition establishment, then τ _j ⁽ⁱ⁾=τ _J-2 ^(i-2), otherwise τ _j ⁽ⁱ⁾=σ _j ^(i-2), and with new τ _j ⁽ⁱ⁾Be saved in the corresponding registers of registers group 107; Multiplexed selector 109 is used for selecting according to multiplexed selector 108 identical conditions the value δ of the last non-vanishing correction term of the i+2 time iteration ⁽ⁱ⁺²⁾If condition is set up, then δ ⁽ⁱ⁺²⁾=δ ⁽ⁱ⁾, otherwise δ ⁽ⁱ⁺²⁾=Δ ⁽ⁱ⁾, and be saved in the register 110 in last clock cycle of each iteration.

The binary system BCH code of the embodiment of the invention is the polynomial method and apparatus in mistake in computation position in decoding, characteristic according to the binary system Bose-Chaudhuri Hocquenghem error correction codes, only needed t iteration can be in the hope of contrary BM method of the nothing of the multinomial σ (x) that makes mistake and device, be N≤t * (t+3)/2 its computing time, the computing time of half can be saved than the method for prior art, it is along with error correcting capability t requires under the more and more higher situation, the relative prior art of this method has also reduced the power consumption of decoding circuit greatly when reducing the BCH decoding delay.

Should be noted that at last that obviously those skilled in the art can carry out various changes and modification to the present invention and not break away from the spirit and scope of the present invention.Like this, if of the present invention these revise and modification belongs within the scope of claim of the present invention and equivalent technologies thereof, then the present invention also is intended to comprise these changes and modification.

Claims (7)

1. a binary system BCH code polynomial method in mistake in computation position in decoding is characterized in that, comprises the following steps:

Step S100, according to the syndrome that calculates, iteration is from even number, the polynomial initial parameter of initialization step-length initial value i and mistake in computation position;

Step S200 calculates the error location polynomial of the i time iteration and the correction term of the i+2 time iteration;

Step S300 judges and calculates the next iteration parameters calculated;

Step S400 is 2 step-length with the value growth constant of i, promptly

Step S500 compares the value and the 2t-1 of iterations, and selects to continue iteration according to comparative result and change step S200, and perhaps finishing iteration is changeed step S600 processing;

Step S600 with the error location polynomial output of the i-2 time iteration, finishes.

2. binary system BCH code according to claim 1 is the polynomial method in mistake in computation position in decoding, it is characterized in that, described step S100 comprises the following steps:

According to the syndrome S1 that calculates, iteration is initially from-2, initialization iterations i=0, and the polynomial initial parameter in initialization mistake in computation position, i.e. the number of times variables D is assisted in initialization ⁽²⁾=0; The error location polynomial σ of the-2 iteration ⁽²⁾(x)=1; The Auxiliary polynomial τ of the-2 iteration ⁽²⁾(x)=x ^-1The 0th iteration last non-vanishing correction term δ before ⁽⁰⁾=1; The correction term Δ of the 0th iteration ⁽⁰⁾=S ₁

3. binary system BCH code according to claim 2 is the polynomial method in mistake in computation position in decoding, it is characterized in that, described step S200 comprises the following steps:

Calculate the error location polynomial σ of the i time iteration ⁽ⁱ⁾(x) and the correction term Δ of the i+2 time iteration ⁽ⁱ⁺²⁾, be shown below;

$\left\{\begin{array}{c}{\mathrm{\&sigma;}}^{\left(i\right)}\left(x\right)={\mathrm{\&delta;}}^{\left(i\right)}\&CenterDot;{\mathrm{\&sigma;}}^{(i-2)}\left(x\right)+{\mathrm{\&Delta;}}^{\left(i\right)}{x}^2{\mathrm{\&tau;}}^{(i-2)}\left(x\right)\\ {\mathrm{\&Delta;}}^{(i+2)}=S_{i+3}\&CenterDot;{\mathrm{\&sigma;}}_0^{\left(i\right)}+S_{i+2}\&CenterDot;{\mathrm{\&sigma;}}_1^{\left(i\right)}+...+S_{i+3-v_i}\&CenterDot;{\mathrm{\&sigma;}}_{v_i}^{\left(i\right)}\end{array}\right..$

4. binary system BCH code according to claim 3 is the polynomial method in mistake in computation position in decoding, it is characterized in that, described step S300 comprises the following steps:

Step S310 judges the correction term Δ of the i time iteration ⁽ⁱ⁾Whether equal 0, perhaps formula 2D ^(i-2)Whether 〉=i+1 sets up;

If step S320 is the correction term Δ of the i time iteration ⁽ⁱ⁾Equal 0, perhaps 2D ^(i-2)〉=i+1 sets up, then

D ⁽ⁱ⁾＝D ^(i-2)，δ ⁽ⁱ⁺²⁾＝δ ⁽ⁱ⁾，τ ⁽ⁱ⁾(x)＝x ²τ ^(i-2)(x)；

If step S330 is the correction term Δ of the i time iteration ⁽ⁱ⁾Be not equal to zero, and 2D ^(i-2)〉=i+1 is false, then

D ⁽ⁱ⁾＝i+1-D ^(i-2)，δ ⁽ⁱ⁺²⁾＝Δ ⁽ⁱ⁾，τ ⁽ⁱ⁾(x)＝σ ^(i-2)(x)。

5. binary system BCH code according to claim 4 is the polynomial method in mistake in computation position in decoding, it is characterized in that, described step S500 comprises the following steps:

Whether the value that judge to increase step-length and be the i after 2 is less than 2t-1; If the value of i less than 2t-1, then forwards step S200 to, carry out the next round iterative computation; If the value of i is not less than 2t-1, then carry out step S600; Wherein, t is the number of the random error that can correct of BCH code.

6. a binary system BCH code polynomial device in mistake in computation position in decoding is characterized in that, comprises 3 GF (2 ^m) Galois field multiplier (101,102,103); 2 GF (2 ^m) finite field adder (104,105); The registers group (106,107) of 2 groups of each (t+1) individual m positions; The multiplexed selector of 2 m positions (108,109); The register of 4 m positions (110,111,112,113).

7. binary system BCH code according to claim 6 is the polynomial device in mistake in computation position in decoding, it is characterized in that:

Registers group (106) is used to store the wrong multinomial σ that each iterative computation is come out ⁽ⁱ⁾(x) coefficient;

Registers group (107) is used to store the Auxiliary polynomial τ that each iterative computation is come out ⁽ⁱ⁾(x) coefficient;

Register (110) is used to store the last non-vanishing correction term δ before the i+2 time iteration that the i time iterative computation come out ⁽ⁱ⁺²⁾

Register (111) is used to store the correction term Δ of the i+2 time iteration that the i time iterative computation come out ⁽ⁱ⁺²⁾

Register (112) is used to be stored in the correction term Δ of the i+2 time iteration that j clock cycle of the i time iteration calculate ⁽ⁱ⁺²⁾Median

Register (113) is used to store the wrong polynomial coefficient that j clock cycle of the i time iteration calculate

Galois field multiplier (101) is used for realizing following formula

Function;

Galois field multiplier (102) is used for realizing following formula Function;

Galois field multiplier (101), Galois field multiplier (102) and finite field adder (104) are finished in the following formula together

Calculating, the result of calculation in each cycle is saved in the register (113), the result of register (113) deposits relevant register in the registers group (106) in after participating in finishing the computing of Galois field multiplier (103) successively;

Galois field multiplier (103) is used for realizing following formula

Calculating, be kept at register (112) after the value addition of the result that each computing cycle calculates by finite field adder (105) and register (112);

${{\mathrm{\&sigma;}}_j}^{\left(i\right)}=\left\{\begin{array}{cc}{\mathrm{\&delta;}}^{\left(i\right)}\&CenterDot;{\mathrm{\&sigma;}}_0^{(i-2)},& \mathrm{for\; j}=0\\ {\mathrm{\&delta;}}^{\left(i\right)}\&CenterDot;{\mathrm{\&sigma;}}_j^{(i-2)}+{\mathrm{\&Delta;}}^{\left(i\right)}{\mathrm{\&tau;}}_{j-2}^{(i-2)},& \mathrm{for}1\&le;j\&le;v_i\end{array}\right.$

${\mathrm{\&Delta;}}_j^{(i+2)}=\left\{\begin{array}{cc}0,& \mathrm{for\; j}=0\\ {\mathrm{\&Delta;}}_{j-1}^{(i+2)}+S_{i+4-j}\&CenterDot;{\mathrm{\&sigma;}}_{j-1}^{\left(i\right)},& \mathrm{for}1\&le;j\&le;v_i\end{array}\right.$

In the 0th cycle of the i+2 time iteration, Galois field multiplier (103) realization formula

${\mathrm{\&Delta;}}^{(i+2)}={\mathrm{\&Delta;}}_{v_i}^{(i+2)}+S_{i+3-v_i}\&CenterDot;{\mathrm{\&sigma;}}_{v_i}^{\left(i\right)}$

$=...$

$=S_{i+3}\&CenterDot;{\mathrm{\&sigma;}}_0^{\left(i\right)}+S_{i+2}\&CenterDot;{\mathrm{\&sigma;}}_1^{\left(i\right)}+...+S_{i+3-v_i}\&CenterDot;{\mathrm{\&sigma;}}_{v_i}^{\left(i\right)}$

In

With the correction term Δ that obtains the i+2 time complete iteration after the preceding intermediate object program addition that is kept in the register (112) ⁽ⁱ⁺²⁾, and be saved in the register (111);

Multiplexed selector (108) is used for according to condition " Δ ⁽ⁱ⁾Equal 0, perhaps 2D ^(i-2)〉=i+1 " whether become Rob Roy to select τ in the i time iteration ⁽ⁱ⁾(x) coefficient τ _j ⁽ⁱ⁾If the value of ' s is condition establishment, then τ _j ⁽ⁱ⁾=τ _J-2 ^(i-2), otherwise τ _j ⁽ⁱ⁾=σ _j ^(i-2), and with new τ _j ⁽ⁱ⁾Be saved in the corresponding registers of registers group (107);

Multiplexed selector (109) is used for selecting according to the identical condition of multiplexed selector (108) the value δ of the last non-vanishing correction term of the i+2 time iteration ⁽ⁱ⁺²⁾If condition is set up, then δ ⁽ⁱ⁺²⁾=δ ⁽ⁱ⁾, otherwise δ ⁽ⁱ⁺²⁾=Δ ⁽ⁱ⁾, and be saved in the register (110) in last clock cycle of each iteration.

Images