CN102045073B - Method and device for decoding broadcast channel (BCH) code - Google Patents

Abstract

The embodiment of the invention provides a method and device for decoding a broadcast channel (BCH) code. The method comprises the steps: computing a syndrome according to a receiving code; solving the polynomial of an error position according to the syndrome by an iterative algorithm; confirming the error position according to the polynomial of the error position by a money type search algorithm; and correcting an error value on the confirmed error position to obtain a recovering code. The method and device for decoding the BCH code of the embodiment can optimize a parallel bench mark (BM) iterative algorithm on the resource and the speed by improving the riBM algorithm.

Description

BCH code decoding method and device

Technical Field

The present invention relates to the field of communications technologies, and in particular, to a BCH code decoding method and apparatus.

Background

NAND flash memories currently have significant advantages in power consumption, speed, data reliability, weight, and silence, and the advantages of NAND flash memories become more attractive as the market share of lightweight and thin notebook computers throughout the PC (personal computer) is continuously increasing, and Solid State Disks (SSD) based on NAND flash memories are gradually coming into these applications.

NAND flash memory can be divided into two large architectures: single Level cell SLC (single Level cell) and multi Level cell MLC (multi Level cell), wherein MLC has a larger capacity due to its lower cost, but its working performance is not as stable as SLC, and the bit error rate of accessing data by using MLC NAND Flash Memory (MLC NAND Flash Memory) is about 10 according to statistics^-5In order to ensure the accuracy of reading data, an error Correction code (ecc) technology is used to correct multiple bit (bit) random errors.

For the realization of BCH coding and decoding, decoding is difficult, and the following are commonly used in all decoding algorithms: peterson algorithm, Berlekamp-Massey iterative algorithm (BM method for short), euclidean algorithm. The Peterson algorithm is suitable for decoding with less error correction number, and the calculated amount of the Peterson algorithm is the largest in the three algorithms; the BM algorithm and the Euclid algorithm are suitable for decoders with large error correction numbers, and the Euclid algorithm is easier to understand than the BM iterative algorithm, but has larger operand and is more complex than the hardware structure of the BM iterative algorithm. In addition, considering the particularity of the binary BCH code, a BM iterative algorithm which is fast in decoding speed and most commonly used is adopted in the design.

The inventor finds that, in the process of implementing the present invention, in a BM iterative algorithm, the BM iterative algorithm includes a commonly used iBM (inversion Berl-Massey) algorithm and a riBM (correlation inversion Berl-Massey) algorithm, where the riBM algorithm is a derivation and improvement of a iBM algorithm, and a key path thereof is shortened to half of the original one, so that VLSI design performance is greatly improved, but the riBM algorithm is a parallel BM iterative algorithm which is proposed for an RS (Reed Solomon) code and is suitable for FPGA design, and since an RS code is a special case of a BCH code, a decoding process thereof is more complicated than the BCH code, and therefore, if the riBM algorithm is applied to a decoding process of a general BCH code, a great waste of resources is caused.

Disclosure of Invention

The embodiment of the invention provides a BCH code decoding method and device, which can realize BCH code decoding on the premise of occupying less FPGA resources and ensuring high speed.

The above object of the embodiment of the present invention is achieved by the following technical solutions:

a BCH code decoding method, the method comprising: calculating a syndrome from the received code; calculating an error location polynomial from the syndrome using an iterative algorithm; determining an error location from the error location polynomial using a chien search algorithm; and correcting the error value at the determined error position to obtain a recovery code. Wherein computing an error location polynomial from the syndrome using an iterative algorithm comprises: setting an initial value of an error position polynomial under zero iteration and an initial value of an auxiliary polynomial of the error position polynomial under zero iteration to be zero; setting an initial value of an error value polynomial under zero iteration and an initial value of an auxiliary polynomial of the error value polynomial under zero iteration as coefficients of the syndrome; setting an initial value of an error position polynomial under zero iteration zero power and an initial value of an auxiliary polynomial of the error position polynomial under zero iteration zero power as 1; setting an initial value of an iteration coefficient to be 0 under zero iteration; setting an initial value of an iteration limiting condition to be 1 under zero iterations; calculating an auxiliary polynomial of the error value polynomial, an auxiliary polynomial of the error position polynomial, an iteration coefficient and an iteration limiting condition according to the set initial value; calculating an error value polynomial according to the set initial value and according to the auxiliary polynomial of the error value polynomial, the auxiliary polynomial of the error position polynomial, the iteration coefficient and the iteration limiting condition obtained by calculation; and calculating the error position polynomial according to the set initial value and the error value polynomial, the auxiliary polynomial of the error position polynomial, the iteration coefficient and the iteration limiting condition obtained by the calculation to obtain the error position polynomial.

An apparatus for BCH code decoding, the apparatus comprising: a first calculation unit for calculating a syndrome from the received code; a second calculation unit for calculating an error location polynomial from the syndrome using an iterative algorithm; a determining unit for determining an error location according to the error location polynomial using a chien search algorithm; and the error correction unit is used for correcting the error value on the error position determined by the determination unit to obtain a recovery code. Wherein the second calculation unit includes: the setting module is used for setting the initial value of the error position polynomial under zero iteration and the initial value of the auxiliary polynomial of the error position polynomial under zero iteration to be zero; setting an initial value of an error value polynomial under zero iteration and an initial value of an auxiliary polynomial of the error value polynomial under zero iteration as coefficients of the syndrome; setting an initial value of an error position polynomial under zero iteration zero power and an initial value of an auxiliary polynomial of the error position polynomial under zero iteration zero power as 1; setting an initial value of an iteration coefficient to be 0 under zero iteration; setting an initial value of an iteration limiting condition to be 1 under zero iterations; the control module is used for calculating an auxiliary polynomial of the error value polynomial, an auxiliary polynomial of the error position polynomial, an iteration coefficient and an iteration limiting condition according to the initial value set by the setting module; the first calculation module is used for calculating an error value polynomial according to the initial value set by the setting module and the calculation result of the control module; and the second calculation module is used for calculating the error position polynomial according to the initial value set by the setting module and the calculation results of the control module and the first calculation module to obtain the error position polynomial.

According to the BCH code decoding method and device provided by the embodiment of the invention, two-point optimization is carried out on the riBM decoding method according to the characteristics of a BCH binary code system, namely when the iteration r is odd, the difference value lambda r) is constantly 0, so that 2t iterations of iteration can be reduced to t iterations; and error correction is required by the error value polynomial omega (r) in decoding the RS code, while for the binary BCH code, the correction value must be 1, so the error value polynomial omega (r) can be simplified. Therefore, the embodiment of the invention realizes the difficulty in the BCH decoding method under the conditions of occupying less FPGA resources and ensuring high-speed realization, namely solving the error position polynomial according to the syndrome, and optimizing the parallel BM iterative algorithm in terms of resources and speed by improving the ribM algorithm.

Drawings

The accompanying drawings, which are included to provide a further understanding of the invention and are incorporated in and constitute a part of this application, illustrate embodiment(s) of the invention and together with the description serve to explain the principles of the invention. In the drawings:

FIG. 1 is a flowchart of a BCH code decoding method according to an embodiment of the present invention;

FIG. 2 is a flow chart of step 102 of the embodiment shown in FIG. 1;

FIG. 3 is a block diagram of a BCH code decoding apparatus according to an embodiment of the present invention;

FIG. 4 is a schematic circuit diagram of a first computing module according to an embodiment of the invention;

FIG. 5 is a simplified schematic diagram of the first calculation module shown in FIG. 4;

FIG. 6 is a schematic diagram of a circuit configuration of a plurality of first computing modules according to an embodiment of the present invention;

FIG. 7 is a schematic diagram of a circuit configuration of a control module according to an embodiment of the present invention;

FIG. 8 is a schematic circuit diagram of a second computing module according to an embodiment of the present invention;

FIG. 9 is a simplified schematic diagram of a second calculation module shown in FIG. 6;

FIG. 10 is a schematic diagram of a plurality of second computing modules according to an embodiment of the present invention;

FIG. 11 is a circuit diagram of a second computing unit according to an embodiment of the invention.

Detailed Description

In order to make the objects, technical solutions and advantages of the embodiments of the present invention more apparent, the embodiments of the present invention are described in further detail below with reference to the embodiments and the accompanying drawings. The exemplary embodiments and descriptions of the present invention are provided to explain the present invention, but not to limit the present invention.

FIG. 1 is a flowchart of a BCH code decoding method according to an embodiment of the present invention, in this embodiment, an error location polynomial is expressed as

The auxiliary polynomial representation of the error location polynomial isThe error value polynomial is expressed as

The auxiliary polynomial representation of the error value polynomial isWherein,

coefficients of zi in the error location polynomial (r, z) in the r-th iteration; r is the number of iterations; i is a power term corresponding to the variable z; delta_i(r) is z in the error value polynomial Δ (r, z) in the r-th iterationⁱThe coefficient of (a); b_i(r) z in the auxiliary polynomial B (r, z) of the error location polynomial at the r-th iterationⁱThe coefficient of (a); theta_i(r) z of the auxiliary polynomial theta (r, z) of the error value polynomial at the r-th iterationⁱThe coefficient of (a); gamma (r) is an iteration coefficient multiplied when the conversion is carried out in a non-inverse algorithm; k (r) is a constraint in the iteration to ensure that a unique solution is found. Referring to fig. 1, the method includes:

101: calculating a syndrome from the received code;

in this embodiment, the receiving code refers to received encoded data, and the data needs to be decoded by using the method of this embodiment. In this embodiment, for the sake of convenience, the received code is represented by r (z), the syndrome is represented by S (z), and the coefficient of the syndrome is represented by S_i。

102: calculating an error location polynomial according to the syndrome by using an iterative algorithm, referring to fig. 2, specifically includes:

201: setting an initial value of an error position polynomial under zero iteration and an initial value of an auxiliary polynomial of the error position polynomial under zero iteration to be zero; setting an initial value of an error value polynomial under zero iteration and an initial value of an auxiliary polynomial of the error value polynomial under zero iteration as coefficients of the syndrome; setting an initial value of an error position polynomial under zero iteration zero power and an initial value of an auxiliary polynomial of the error position polynomial under zero iteration zero power as 1; setting an initial value of an iteration coefficient to be 0 under zero iteration; setting an initial value of an iteration limiting condition to be 1 under zero iterations;

wherein an initial value of the error location polynomial at zero iterations and an initial value of the auxiliary polynomial of the error location polynomial at zero iterations being zero may be represented as λ_i(0)＝b_i(0) 0, where i is 1, 2.

Wherein the initial value of the error value polynomial at zero iteration and the initial value of the auxiliary polynomial of the error value polynomial at zero iteration are coefficients of the syndrome, and can be expressed as

Wherein S is_iThe coefficients of the above formula are represented by i ═ 0,1, …,2 t-1.

Wherein the initial value of the error position polynomial at zero iteration zero power and the initial value of the auxiliary polynomial of the error position polynomial at zero iteration zero power are 1, which can be expressed as λ₀(0)＝b₀(0)＝1。

Here, the initial value of the iteration coefficient at zero iterations is 0, and may be represented as k (0) ═ 0.

Here, the initial value of the iteration limit condition at zero iterations is 1, and may be expressed as γ (0) ═ 1.

202: calculating an auxiliary polynomial of the error value polynomial, an auxiliary polynomial of the error position polynomial, an iteration coefficient and an iteration limiting condition according to the set initial value;

wherein if is delta₀(r) ≠ 0 and k (r) ≧ 0, then:

$\left\{\begin{array}{c}{\tilde{b}}_i(r+1)={\widetilde{\mathrm{\λ}}}_i\left(r\right),(i=\mathrm{0,1},......,t)\\ {\widetilde{\mathrm{\θ}}}_i(r+1)=\widetilde{{\mathrm{\δ}}_{i+1}}\left(r\right),(i=\mathrm{0,1},......2t-1);\\ \mathrm{\γ}(r+1)={\widetilde{\mathrm{\δ}}}_0\left(r\right)\\ k(r+1)=-k\left(r\right)\end{array}\right.$ if not, then, $\left\{\begin{array}{c}{\tilde{b}}_i(r+1)=\widetilde{b_{i-1}}\left(r\right),(i=\mathrm{0,1},......,t)\\ {\widetilde{\mathrm{\θ}}}_i(r+1)={\widetilde{\mathrm{\θ}}}_i\left(r\right),(i=\mathrm{0,1},......2t-1)\\ \mathrm{\γ}(r+1)=\mathrm{\γ}\left(r\right)\\ k(r+1)=k\left(r\right)+1\end{array}\right.,$ wherein r is the iteration number, and i is a power term.

203: calculating an error value polynomial according to the set initial value and according to the auxiliary polynomial of the error value polynomial, the auxiliary polynomial of the error position polynomial, the iteration coefficient and the iteration limiting condition obtained by calculation;

wherein, ${\widetilde{\mathrm{\δ}}}_i(r+1)=\mathrm{\γ}\left(r\right)\·\widetilde{{\mathrm{\δ}}_{i+2}}\left(r\right)-\widetilde{{\mathrm{\δ}}_0\left(r\right)}\·\widetilde{{\mathrm{\θ}}_{i+1}}\left(r\right),(i=\mathrm{0,1,2},......,2t-1).$

204: and calculating the error position polynomial according to the set initial value and the error value polynomial, the auxiliary polynomial of the error position polynomial, the iteration coefficient and the iteration limiting condition obtained by the calculation to obtain the error position polynomial.

Wherein, ${\widetilde{\mathrm{\λ}}}_i(r+1)=\left\{\begin{array}{c}\mathrm{\γ}\left(r\right)\·{\widetilde{\mathrm{\λ}}}_i\left(r\right)-{\widetilde{\mathrm{\δ}}}_0\left(r\right)\·{\tilde{b}}_{i-1}\left(r\right),(i=\mathrm{0,1},......,t),r=0\\ \mathrm{\γ}\left(r\right)\·{\widetilde{\mathrm{\λ}}}_i\left(r\right)-{\widetilde{\mathrm{\δ}}}_0\left(r\right)\·{\tilde{b}}_{i-2}\left(r\right),(i=\mathrm{0,1},......,t),r=\mathrm{1,2},......,t-1\end{array}\right..$

wherein the obtained error location polynomial can be expressed asWherein, i is 0, 1.

103: determining an error location from the error location polynomial using a chien search algorithm;

after the error location polynomial is obtained by calculation according to the above steps, the error location can be determined according to the error location polynomial by means of the prior art and using a chien search algorithm, which is not described herein again.

104: and correcting the error value at the determined error position to obtain a recovery code.

After the error position is determined according to the above steps, the error value at the error position can be corrected by means of the prior art, and then the recovery code is obtained, which is not described herein again.

According to the BCH code decoding method provided by the embodiment of the invention, two-point optimization is carried out on the riBM decoding method according to the characteristics of a BCH binary code system, namely when the iteration r is an odd number of times, the difference value lambda (r) is constantly 0, so that 2t iterations of iteration can be reduced to t iterations; and error correction is required by the error value polynomial omega (r) in decoding the RS code, while for the binary BCH code, the correction value must be 1, so the error value polynomial omega (r) can be simplified.

Fig. 3 is a block diagram of a BCH code decoding device according to an embodiment of the present invention, please refer to fig. 3, which is based on the riBM algorithm and mainly includes: a first calculation unit 31, a second calculation unit 32, a determination unit 33, and an error correction unit 34, wherein:

the first calculation unit 31 is configured to calculate the syndrome from the received code. The details have already been described in step 101, and are not described herein again.

The second calculating unit 32 is configured to solve the error location polynomial from the syndrome by using an iterative algorithm, and in this embodiment, the second calculating unit 32 includes: a setting module 321, a control module 322, a first calculating module 323, and a second calculating module 324, wherein:

the setting module 321 is configured to set an initial value of the error location polynomial in zero iterations and an initial value of an auxiliary polynomial of the error location polynomial in zero iterations to be zero; setting an initial value of an error value polynomial under zero iteration and an initial value of an auxiliary polynomial of the error value polynomial under zero iteration as coefficients of the syndrome; setting an initial value of an error position polynomial under zero iteration zero power and an initial value of an auxiliary polynomial of the error position polynomial under zero iteration zero power as 1; setting an initial value of an iteration coefficient to be 0 under zero iteration; and setting an initial value of the iteration limiting condition to be 1 under zero iterations. The detailed description has been already made in step 201, and is not repeated herein.

The control module 322 is configured to calculate an auxiliary polynomial of the error value polynomial, an auxiliary polynomial of the error location polynomial, an iteration coefficient, and an iteration limiting condition according to the initial value set by the setting module 321. The details are described in step 202. In this embodiment, the control module 322 may include:

a receiving submodule, configured to receive an initial value of the iteration limitation condition set by the setting module 321 and a coefficient of the error value polynomial of the zeroth power;

and the judgment submodule is used for judging whether the coefficient of the error value polynomial of the zeroth power is zero or not and whether the initial value of the iteration limiting condition is larger than or equal to zero or not according to the coefficient of the error value polynomial of the zeroth power and the initial value of the iteration limiting condition, and generating a control instruction of the next iteration and an iteration coefficient gamma (r +1) of the next iteration according to the judgment result. Wherein, the control instruction of the next iteration comprises: coefficients of auxiliary polynomials of error location polynomials of the next iterationCoefficients of auxiliary polynomials of error value polynomials of the next iteration

And an iteration limit condition k (r +1) for the next iteration.Wherein if is delta₀(r) ≠ 0 and k (r) ≧ 0, then:

$\left\{\begin{array}{c}{\tilde{b}}_i(r+1)={\widetilde{\mathrm{\λ}}}_i\left(r\right),(i=\mathrm{0,1},......,t)\\ {\widetilde{\mathrm{\θ}}}_i(r+1)=\widetilde{{\mathrm{\δ}}_{i+1}}\left(r\right),(i=\mathrm{0,1},......2t-1)\\ \mathrm{\γ}(r+1)={\widetilde{\mathrm{\δ}}}_0\left(r\right)\\ k(r+1)=-k\left(r\right)\end{array}\right.;$ if not, then, $\left\{\begin{array}{c}{\tilde{b}}_i(r+1)=\widetilde{b_{i-1}}\left(r\right),(i=\mathrm{0,1},......,t)\\ {\widetilde{\mathrm{\θ}}}_i(r+1)={\widetilde{\mathrm{\θ}}}_i\left(r\right),(i=\mathrm{0,1},......2t-1)\\ \mathrm{\γ}(r+1)=\mathrm{\γ}\left(r\right)\\ k(r+1)=k\left(r\right)+1\end{array}\right.;$

wherein r is the iteration number, and i is a power term.

In this embodiment, the control module 322 can be implemented by the control circuit shown in fig. 4, but this embodiment is not limited thereto, and any control circuit for implementing the foregoing formula and method can be used to implement the control module 322 of the embodiment of the present invention.

The first calculating module 323 is configured to calculate an error value polynomial according to the initial value set by the setting module 321 and the calculation result of the control module 322. The details of step 203 are described in detail. In this embodiment, the first calculating module 323 may include 2t first calculating sub-modules, and each first calculating sub-module respectively calculates the following formula:

${\widetilde{\mathrm{\δ}}}_i(r+1)=\mathrm{\γ}\left(r\right)\·\widetilde{{\mathrm{\δ}}_{i+2}}\left(r\right)-\widetilde{{\mathrm{\δ}}_0\left(r\right)}\·\widetilde{{\mathrm{\θ}}_{i+1}}\left(r\right),(i=\mathrm{0,1,2},......,2t-1)$ performing iterative operation from 0 th power to 2t-1 th power, wherein each first calculation submodule comprises:

the first multiplier is used for carrying out multiplication operation on the coefficient of the error value polynomial of the previous power and the iteration coefficient of the current iteration;

a first data selector for selecting one of the coefficients of the error value polynomial of the previous power and the coefficients of the auxiliary polynomial of the error value polynomial according to a control instruction of a control module;

a first register for storing an output of the first data selector as an input to a coefficient of an auxiliary polynomial of an error value polynomial of the first data selector;

a second multiplier for multiplying the coefficient of the error value polynomial of the zeroth power and the coefficient of the auxiliary polynomial of the error value polynomial;

the first adder is used for adding the multiplication result of the first multiplier and the multiplication result of the second multiplier to obtain the coefficient of the error value polynomial;

and the second register is used for storing and outputting the coefficients of the error value polynomial.

In this embodiment, the first computation submodule may be implemented by the circuit composition shown in fig. 5, and may be implemented by PE1 shown in fig. 6_iAnd, the 2t first computation submodules of the present embodiment may be respectively represented by PE1 of the drawing shown in fig. 7₀~PE1_2t-1To indicate.

The second calculating module 324 is configured to calculate an error location polynomial according to the initial value set by the setting module and the calculation result of the control module and the first calculating module, so as to obtain the error location polynomial. Specifically, as explained in step 204, in the present embodiment, the second calculating module 324 includes t second calculating sub-modules, which respectively calculate, according to the formula:

${\widetilde{\mathrm{\λ}}}_i(r+1)=\left\{\begin{array}{c}\mathrm{\γ}\left(r\right)\·{\widetilde{\mathrm{\λ}}}_i\left(r\right)-{\widetilde{\mathrm{\δ}}}_0\left(r\right)\·{\tilde{b}}_{i-1}\left(r\right),(i=\mathrm{0,1},......,t),r=0\\ \mathrm{\γ}\left(r\right)\·{\widetilde{\mathrm{\λ}}}_i\left(r\right)-{\widetilde{\mathrm{\δ}}}_0\left(r\right)\·{\tilde{b}}_{i-2}\left(r\right),(i=\mathrm{0,1},......,t),r=\mathrm{1,2},......,t-1\end{array}\right.$ performing iterative operations from the 0 th power to the t th power, wherein each second computation submodule comprises:

the third multiplier is used for multiplying the iterative coefficient of the iteration and the coefficient of the error position polynomial;

a fourth multiplier for multiplying the coefficient of the error value polynomial of the zeroth power and the coefficient of the auxiliary polynomial of the error location polynomial of the next power;

a second data selector for selecting one of the coefficients of the error location polynomial and the coefficients of the auxiliary polynomial of the error location polynomial of the previous power in accordance with a control instruction of a control module;

a third register for storing an output of the second data selector as a coefficient output of an auxiliary polynomial of the error location polynomial to the power of the current power;

a second adder for adding the multiplication result of the third multiplier and the multiplication result of the fourth multiplier;

and a fourth register for storing the addition result of the second adder and outputting it as a coefficient of the error position polynomial.

In this embodiment, the first computation submodule may be implemented by the circuit composition shown in fig. 5, and may be implemented by PE1 shown in fig. 6_iAnd, the 2t first computation submodules of the present embodiment may be respectively represented by PE1 of the drawing shown in fig. 7₀~PE1_2t-1To indicate.

In this embodiment, the second computation submodule 123 may be implemented by the circuit composition shown in FIG. 8, which may be implemented by the PEO of the drawing shown in FIG. 9_iAnd, the t second computation submodules of the present embodiment may be respectively represented by PE0 of the drawing shown in fig. 10_t～PE0₀To indicate.

Referring to fig. 11, which is a schematic circuit implementation diagram of the second calculating unit 32 according to the embodiment of the present invention, as shown in fig. 11, the second calculating unit 32 includes a setting module (not shown), 2t first calculating sub-modules 111, a control module 112, and t second calculating modules 113, and specific functions have been described above and are not described herein again.

The determination unit 33 is configured to determine the error location according to the error location polynomial calculated and obtained by the second calculation unit 32 using the chien search algorithm.

The determination unit 33 can be implemented by means of the prior art, and is not described herein again.

The error correction unit 34 is configured to correct an error value at the error position determined by the determination unit 33 to obtain a recovery code.

The error correction unit 34 can also be implemented by means of the prior art, and will not be described herein.

The BCH code decoding device of the embodiment of the invention performs two-point optimization on the riBM decoding method according to the characteristics of the BCH binary code system, namely when the iteration r is odd, the difference value lambda (r) is constantly 0, so that 2t iterations of iteration can be reduced to t iterations; and error correction is required by the error value polynomial omega (r) in decoding the RS code, while for the binary BCH code, the correction value must be 1, so the error value polynomial omega (r) can be simplified. Therefore, the embodiment of the invention realizes the difficulty in the BCH decoding method under the conditions of occupying less FPGA resources and ensuring high-speed realization, namely solving the error position polynomial according to the syndrome, and optimizing the parallel BM iterative algorithm in terms of resources and speed by improving the ribM algorithm.

The above-mentioned embodiments are intended to illustrate the objects, technical solutions and advantages of the present invention in further detail, and it should be understood that the above-mentioned embodiments are only exemplary embodiments of the present invention, and are not intended to limit the scope of the present invention, and any modifications, equivalent substitutions, improvements and the like made within the spirit and principle of the present invention should be included in the scope of the present invention.

Claims (10)

1. A BCH code decoding method, characterized in that the method comprises:

calculating a syndrome from the received code;

calculating an error location polynomial from the syndrome using an iterative algorithm comprising:

setting an initial value of an error position polynomial under zero iteration and an initial value of an auxiliary polynomial of the error position polynomial under zero iteration to be zero; setting an initial value of an error value polynomial under zero iteration and an initial value of an auxiliary polynomial of the error value polynomial under zero iteration as coefficients of the syndrome; setting an initial value of an error position polynomial under zero iteration zero power and an initial value of an auxiliary polynomial of the error position polynomial under zero iteration zero power as 1; setting an initial value of an iteration coefficient to be 0 under zero iteration; setting an initial value of an iteration limiting condition to be 1 under zero iterations;

calculating an auxiliary polynomial of the error value polynomial, an auxiliary polynomial of the error position polynomial, an iteration coefficient and an iteration limiting condition according to the set initial value;

calculating an error value polynomial according to the set initial value and according to the auxiliary polynomial of the error value polynomial, the auxiliary polynomial of the error position polynomial, the iteration coefficient and the iteration limiting condition obtained by calculation;

calculating an error position polynomial according to the set initial value and according to the error value polynomial, the auxiliary polynomial of the error position polynomial, the iteration coefficient and the iteration limiting condition obtained by calculation, and obtaining an error position polynomial;

determining an error location from the error location polynomial using a chien search algorithm;

correcting the error value at the determined error position to obtain a recovery code;

when the iteration times are odd times, the difference is constantly 0; for a binary BCH code, the correction value is 1.

2. The method of claim 1, wherein:

the initial value of the error position polynomial at zero iteration and the initial value of the auxiliary polynomial of the error position polynomial at zero iteration being zero are represented as lambda_i(0)＝b_i(0) 0, wherein i is 1,2,.. t;

the initial value of the error value polynomial at zero iteration and the initial value of the auxiliary polynomial of the error value polynomial at zero iteration are the coefficients of the syndrome, and the formula is expressed as

Wherein S is_iIs the coefficient of the syndrome, i ═ 0,1, …,2 t-1;

the initial value of the error position polynomial at zero iteration zero power and the initial value of the auxiliary polynomial of the error position polynomial at zero iteration zero power are 1, and the mathematical expression is lambda₀(0)＝b₀(0)＝1；

The initial value of the iteration coefficient under zero iteration is 0, and the mathematical expression is that k (0) is 0;

the initial value of the iteration limiting condition under zero iteration is 1, and the mathematical expression is that gamma (0) is 1;

wherein i is a power term, and t is the iteration number.

3. The method of claim 2, wherein calculating the auxiliary polynomial of the error value polynomial, the auxiliary polynomial of the error location polynomial, the iteration coefficient, and the iteration limit condition based on the set initial values comprises:

calculating an auxiliary polynomial of the error value polynomial, an auxiliary polynomial of the error location polynomial, an iteration coefficient and an iteration limiting condition according to the set initial value and the following formula:

if delta₀(r) ≠ 0 and k (r) ≧ 0, then:

$\left\{\begin{array}{c}{\tilde{b}}_i(r+1)={\widetilde{\mathrm{\λ}}}_i\left(r\right),(i=\mathrm{0,1},......,t)\\ {\widetilde{\mathrm{\θ}}}_i(r+1)=\widetilde{{\mathrm{\δ}}_{i+1}}\left(r\right),(i=\mathrm{0,1},......2t-1);\\ \mathrm{\γ}(r+1)={\widetilde{\mathrm{\δ}}}_0\left(r\right)\\ k(r+1)=-k\left(r\right)\end{array}\right.$ if not, then, $\left\{\begin{array}{c}{\tilde{b}}_i(r+1)=\widetilde{b_{i-1}}\left(r\right),(i=\mathrm{0,1},......,t)\\ {\widetilde{\mathrm{\θ}}}_i(r+1)={\widetilde{\mathrm{\θ}}}_i\left(r\right),(i=\mathrm{0,1},......2t-1)\\ \mathrm{\γ}(r+1)=\mathrm{\γ}\left(r\right)\\ k(r+1)=k\left(r\right)+1\end{array}\right.,$ wherein r is the iteration number, and i is a power term.

4. The method according to claim 3, wherein calculating an error value polynomial from the set initial value and from the auxiliary polynomial of the error value polynomial, the auxiliary polynomial of the error location polynomial, the iteration coefficient, and the iteration limit condition obtained by the calculation comprises:

calculating an error value polynomial according to the set initial value, the auxiliary polynomial of the error value polynomial, the auxiliary polynomial of the error position polynomial, the iteration coefficient and the iteration limiting condition;

${\widetilde{\mathrm{\δ}}}_i(r+1)=\mathrm{\γ}\left(r\right)\·\widetilde{{\mathrm{\δ}}_{i+2}}\left(r\right)-\widetilde{{\mathrm{\δ}}_0\left(r\right)}\·\widetilde{{\mathrm{\θ}}_{i+1}}\left(r\right),(i=\mathrm{0,1,2},......,2t-1).$

5. the method according to claim 4, wherein calculating an error location polynomial from the set initial value and from the error value polynomial obtained by the calculation, an auxiliary polynomial of the error value polynomial, an auxiliary polynomial of the error location polynomial, an iteration coefficient, and an iteration limit condition, obtaining the error location polynomial comprises:

calculating an error location polynomial from the set initial value and the error value polynomial, the auxiliary polynomial of the error location polynomial, the iteration coefficient, and the iteration limit condition obtained through the calculation, using:

${\widetilde{\mathrm{\λ}}}_i(r+1)=\left\{\begin{array}{c}\mathrm{\γ}\left(r\right)\·{\widetilde{\mathrm{\λ}}}_i\left(r\right)-{\widetilde{\mathrm{\δ}}}_0\left(r\right)\·{\tilde{b}}_{i-1}\left(r\right),(i=\mathrm{0,1},......,t),r=0\\ \mathrm{\γ}\left(r\right)\·{\widetilde{\mathrm{\λ}}}_i\left(r\right)-{\widetilde{\mathrm{\δ}}}_0\left(r\right)\·{\tilde{b}}_{i-2}\left(r\right),(i=\mathrm{0,1},......,t),r=\mathrm{1,2},......,t-1\end{array}\right.,$ obtaining an error location polynomial expressed as

Wherein, i is 0, 1.

6. An apparatus for decoding BCH codes, the apparatus comprising:

a first calculation unit for calculating a syndrome from the received code;

a second calculation unit for calculating an error location polynomial from the syndrome using an iterative algorithm, the second calculation unit comprising:

the setting module is used for setting the initial value of the error position polynomial under zero iteration and the initial value of the auxiliary polynomial of the error position polynomial under zero iteration to be zero; setting an initial value of an error value polynomial under zero iteration and an initial value of an auxiliary polynomial of the error value polynomial under zero iteration as coefficients of the syndrome; setting an initial value of an error position polynomial under zero iteration zero power and an initial value of an auxiliary polynomial of the error position polynomial under zero iteration zero power as 1; setting an initial value of an iteration coefficient to be 0 under zero iteration; setting an initial value of an iteration limiting condition to be 1 under zero iterations;

the control module is used for calculating an auxiliary polynomial of the error value polynomial, an auxiliary polynomial of the error position polynomial, an iteration coefficient and an iteration limiting condition according to the initial value set by the setting module;

the first calculation module is used for calculating an error value polynomial according to the initial value set by the setting module and the calculation result of the control module;

the second calculation module is used for calculating an error position polynomial according to the initial value set by the setting module and the calculation results of the control module and the first calculation module to obtain the error position polynomial;

a determining unit for determining an error location according to the error location polynomial using a chien search algorithm;

the error correction unit is used for correcting the error value on the error position determined by the determination unit to obtain a recovery code;

when the iteration times are odd times, the difference is constantly 0; for a binary BCH code, the correction value is 1.

7. The apparatus according to claim 6, wherein the setting module sets the initial values specifically as:

the initial value of the error position polynomial at zero iteration and the initial value of the auxiliary polynomial of the error position polynomial at zero iteration being zero are represented as lambda_i(0)＝b_i(0) 0, wherein i is 1,2,. t;

the initial value of the error value polynomial at zero iteration and the initial value of the auxiliary polynomial of the error value polynomial at zero iteration are the coefficients of the syndrome, and the formula is expressed as

Wherein S is_iIs the coefficient of the syndrome, i ═ 0,1, …,2 t-1;

the initial value of the error position polynomial at zero iteration zero power and the initial value of the auxiliary polynomial of the error position polynomial at zero iteration zero power are 1, and the mathematical expression is lambda₀(0)＝b₀(0)＝1；

The initial value of the iteration coefficient under zero iteration is 0, and the mathematical expression is that k (0) is 0;

the initial value of the iteration limiting condition under zero iteration is 1, and the mathematical expression is that gamma (0) is 1;

wherein i is a power term, and t is the iteration number.

8. The apparatus of claim 7, wherein the control module comprises:

the receiving submodule is used for receiving the initial value of the iteration limiting condition set by the setting module and the coefficient of the error value polynomial of the zeroth power;

a judging submodule, configured to judge whether the coefficient of the error value polynomial of the zeroth power is zero or not and whether the initial value of the iteration limiting condition is greater than or equal to zero or not according to the coefficient of the error value polynomial of the zeroth power and the initial value of the iteration limiting condition, and accordingly generate a control instruction of a next iteration and an iteration coefficient γ (r +1) of the next iteration;

wherein, the control instruction of the next iteration comprises: coefficients of auxiliary polynomials of error location polynomials of the next iteration

Coefficients of auxiliary polynomials of error value polynomials of the next iteration

And an iteration limit condition k (r +1) for the next iteration;

wherein if is delta₀(r) ≠ 0 and k (r) ≧ 0, then:

$\left\{\begin{array}{c}{\tilde{b}}_i(r+1)={\widetilde{\mathrm{\λ}}}_i\left(r\right),(i=\mathrm{0,1},......,t)\\ {\widetilde{\mathrm{\θ}}}_i(r+1)=\widetilde{{\mathrm{\δ}}_{i+1}}\left(r\right),(i=\mathrm{0,1},......2t-1);\\ \mathrm{\γ}(r+1)={\widetilde{\mathrm{\δ}}}_0\left(r\right)\\ k(r+1)=-k\left(r\right)\end{array}\right.$ if not, then, $\left\{\begin{array}{c}{\tilde{b}}_i(r+1)=\widetilde{b_{i-1}}\left(r\right),(i=\mathrm{0,1},......,t)\\ {\widetilde{\mathrm{\θ}}}_i(r+1)={\widetilde{\mathrm{\θ}}}_i\left(r\right),(i=\mathrm{0,1},......2t-1)\\ \mathrm{\γ}(r+1)=\mathrm{\γ}\left(r\right)\\ k(r+1)=k\left(r\right)+1\end{array}\right.;$

wherein r is the iteration number, and i is a power term.

9. The apparatus of claim 8, wherein the first computation module comprises 2t first computation submodules, each according to the formula:

${\widetilde{\mathrm{\δ}}}_i(r+1)=\mathrm{\γ}\left(r\right)\·\widetilde{{\mathrm{\δ}}_{i+2}}\left(r\right)-\widetilde{{\mathrm{\δ}}_0\left(r\right)}\·\widetilde{{\mathrm{\θ}}_{i+1}}\left(r\right),(i=\mathrm{0,1,2},......,2t-1)$ performing iterative operation from 0 th power to 2t-1 th power, wherein each first calculation submodule comprises:

the first multiplier is used for carrying out multiplication operation on the coefficient of the error value polynomial of the previous power and the iteration coefficient of the current iteration;

a first data selector for selecting one of the coefficients of the error value polynomial of the previous power and the coefficients of the auxiliary polynomial of the error value polynomial according to a control instruction of a control module;

a first register for storing an output of the first data selector as an input to a coefficient of an auxiliary polynomial of an error value polynomial of the first data selector;

a second multiplier for multiplying the coefficient of the error value polynomial of the zeroth power and the coefficient of the auxiliary polynomial of the error value polynomial;

the first adder is used for adding the multiplication result of the first multiplier and the multiplication result of the second multiplier to obtain the coefficient of the error value polynomial;

and the second register is used for storing and outputting the coefficients of the error value polynomial.

10. The apparatus of claim 9, wherein the second computation module comprises t second computation submodules, each according to the formula:

${\widetilde{\mathrm{\λ}}}_i(r+1)=\left\{\begin{array}{c}\mathrm{\γ}\left(r\right)\·{\widetilde{\mathrm{\λ}}}_i\left(r\right)-{\widetilde{\mathrm{\δ}}}_0\left(r\right)\·{\tilde{b}}_{i-1}\left(r\right),(i=\mathrm{0,1},......,t),r=0\\ \mathrm{\γ}\left(r\right)\·{\widetilde{\mathrm{\λ}}}_i\left(r\right)-{\widetilde{\mathrm{\δ}}}_0\left(r\right)\·{\tilde{b}}_{i-2}\left(r\right),(i=\mathrm{0,1},......,t),r=\mathrm{1,2},......,t-1\end{array}\right.$ performing iterative operations from the 0 th power to the t th power, wherein each second computation submodule comprises:

the third multiplier is used for multiplying the iterative coefficient of the iteration and the coefficient of the error position polynomial;

a fourth multiplier for multiplying the coefficient of the error value polynomial of the zeroth power and the coefficient of the auxiliary polynomial of the error location polynomial of the next power;

a second data selector for selecting one of the coefficients of the error location polynomial and the coefficients of the auxiliary polynomial of the error location polynomial of the previous power in accordance with a control instruction of a control module;

a third register for storing an output of the second data selector as a coefficient output of an auxiliary polynomial of the error location polynomial to the power of the current power;

a second adder for adding the multiplication result of the third multiplier and the multiplication result of the fourth multiplier;

and a fourth register for storing the addition result of the second adder and outputting it as a coefficient of the error position polynomial.

Images