CN1119869C - Long burst error-correcting decoding method adopting Reed-solomon code - Google Patents

Abstract

The present invention belongs to the technical field of communication. The method comprises the steps that the erroneous position of burst errors is hypothesized to be the minimum 2t bit of a receiving polynomial by effectively utilizing the relation of the receiving polynomial of RS codes before and after cyclic shift and the correlativity of the erroneous position of long burst errors based on the cycle characteristics of the RS codes, and thereby, the encoding method is simplified into a method for cyclically shifting the receiving polynomial and solving erroneous patterns by a group of linear equations. The present invention is suitable for error correction encoding of the long burst errors by correspondingly small encoding delay time and correspondingly high information transmission speed.

Description

A Long Burst Error Correction Decoding Method Using Reed-Solomon Code

technical field

The invention belongs to the technical field of communication, in particular to an effective method for correcting long burst errors using Reed-Solomon code (hereinafter referred to as RS code) in a data transmission and storage system using forward error control (FEC) technology. And fast decoding method.

Background technique

Burst errors often occur during data storage and transmission. Causes of this error include linear noise, loss of synchronization during demodulation, multipath fading in wireless transmission, and track defects in magnetic storage. Such burst errors generally appear periodically and last for a long time. Due to the existence of such long burst errors, the information transmission rate under a certain bandwidth and the storage capacity of a memory under a certain area are greatly limited. Especially in wireless transmission systems, due to the influence of multipath fading, this problem becomes more prominent.

Reed-Solomon code (RS code) has a strong ability to correct burst errors, and is widely used in data transmission and storage systems.

The principle of decoding method using RS code to correct long burst errors is as follows:

Definition and parameters of RS code: RS code is a multi-ary BCH code, which is defined as: Let f(x) be Galois field GF(q) (q is any power of any prime number) less than n polynomial of degree , and α is the original element of GF(q), then if and only if α, α ² ,..., α ^d-1 (d is an integer not less than 2) are all roots of f(x), The set {f(x)} is an RS code, or the RS code is based on g(x)=(x-α)(x-α ² )…(x-α ^d-1 ) as the generator polynomial and the code polynomial The multivariate BCH code whose root domain and symbol domain are consistent (both on GF(q)). The parameters of the RS code for correcting t symbol errors include: code length n=q-1, number of information symbols k, number of check symbols nk=2t, and minimum code distance d=2t+1.

Conventional error correction decoding method:

表示第r个错误的值；i_r表示第r个错误的位置。在发送端(n，k)RS码多项式为C(x)＝c_n-1x^n-1+c_h-2x^n-2+…+c₁x+c₀，该多项式经过调制后在噪声信道中传输。在接收端，经过解调后得到接收多项式。因此接收多项式可表示为：Assuming that an error occurs in the process of transmission or storage of the code symbol, the error polynomial can be expressed as: $\mathrm{E.}\left(x\right)=e_{i_1}{x}^{i_1}+e_{i_2}{x}^{{\mathrm{<figure-callout\; id="2"\; label="i"\; filenames="C0111013400121.png"\; state="\{\{state\}\}">i</figure-callout>}}_2}+\&Center\; Dot;\&CenterDot;\&Center\; Dot;+e_{i_v}{x}^{i_v}---\left(1\right)$ In the formula, ν is the actual number of errors, 0≤ν≤t;

Indicates the value of the rth error; i _r indicates the position of the rth error. At the transmitting end (n, k) the RS code polynomial is C(x)=c _n-1 x ^n-1 +c _h-2 x ^n-2 +…+c ₁ x+c ₀ , the polynomial is modulated in transmission in noisy channels. At the receiving end, the receiving polynomial is obtained after demodulation. So the reception polynomial can be expressed as:

R(x)=C(x)+E(x) (2) Obtain the adjoint formula according to the receiving polynomial: S _j =R(α ^j )(1≤j≤2t). According to the definition of the RS code, α ^j (1≤j≤2t) is the root of the generator polynomial g(x), and the code polynomial C(x) is a multiple of g(x), so C(α ^j )=0, (1≤j≤2t). Thus, the relationship between the adjoint and the error polynomial can be obtained as:

S _j =R(α ^j )=C(α ^j )+E(α ^j )=E(α ^j )(1≤j≤2t) (3)

For convenience, define $Y_r=e_{i_r}$ (r=1, 2, ..., ν) is an error value; $x_r={\mathrm{\&alpha;}}^{i_r}$ (r=1, 2, ..., ν) is the wrong position, then: $\mathrm{E.}\left({\mathrm{\&alpha;}}^j\right)=e_{i_1}{\left({\mathrm{\&alpha;}}^j\right)}^{i_1}+e_{i_2}{\left({\mathrm{\&alpha;}}^j\right)}^{i_2}+\&Center\; Dot;\&Center\; Dot;\&Center\; Dot;+e_{i_v}{\left({\mathrm{\&alpha;}}^j\right)}^{i_v}$ $=e_{i_1}{\left({\mathrm{\&alpha;}}^{i_1}\right)}^j+e_{i_2}{\left({\mathrm{\&alpha;}}^{i_2}\right)}^j+\&CenterDot;\&CenterDot;\&CenterDot;+e_{i_v}{\left({\mathrm{\&alpha;}}^{i_v}\right)}^j---\left(4\right)$ $=Y_1{x}_1^j+Y_2{x}_2^j+\&CenterDot;\&CenterDot;\&CenterDot;+Y_v{x}_v^j$ Substitute equation (4) into equation (3) and expand the resulting equation to obtain 2t equations:

There are 2t equations in the above equations, and there are less than 2t unknowns, and X ₁ , X ₂ ,..., X _ν constitute a always invertible Vandermonde matrix in the equations, so the equations have solutions. Conventional decoding methods, such as Berlekamp iterative method, are used to solve this system of equations to first obtain the error position, then substitute it into (5) to obtain the error pattern value, and finally perform error correction. Such methods are very effective for correcting random errors and a mixture of random and short bursts of errors. But it can only correct bursts with a maximum length of t, and the equation group (5) is still a nonlinear equation, and the decoding method is very complicated, so it is not suitable for correcting long burst errors.

There are mainly two existing methods for correcting long burst errors using RS codes: The first method is to use code interleaving technology, which mainly combines multiple short codes into one long code through interleaving. For example, (jn, jk) codes can be obtained by performing j-level interleaving on (n, k) linear codes. If the ability of the original (n, k) code to correct burst errors is t, then the ability of the interleaved (jn, jk) code to correct burst errors is jt. This approach actually breaks up burst errors into random errors and distributes them evenly to each short code. Its advantage is that it improves the ability of RS codes to correct long burst errors while keeping the information rate constant. However, since interleaving and deinterleaving are respectively performed after code vector encoding and before decoding, relatively large transmission delay will be brought, and the complexity of system implementation will be increased. The second method is to improve the error correction capability of the code vector by reducing the information rate. For example, the length of the supervisory bit is increased by reducing the length of the information bit under the premise of keeping the code length constant, or the length of the supervisory bit is increased by increasing the code length while keeping the length of the information bit constant. This method increases the minimum distance of the code vector space by sacrificing the information transmission rate without increasing the transmission delay, thereby improving the error correction capability.

Contents of the invention

The purpose of the present invention is to overcome the weak point of prior art, propose a kind of long burst error correction decoding method that adopts Reed-Solomon code, by utilizing the characteristic of burst error, with respect to above-mentioned method a little Compared with the above-mentioned method two, the error correction decoding suitable for long burst errors is realized with a much higher decoding delay and a much higher information transmission rate than the above-mentioned method two.

A kind of long burst error correction decoding method that adopts Reed-Solomon code that the present invention proposes, comprises the following steps: 1) carry out initialization: the value of the burst length ν _m of setting current maximum possible error pattern is 2t , the value of the burst pattern Y _m is 0, the value of the lowest burst position N _m is 0; at the same time, the value of the shift count variable N _c is set to 0; 2) Start receiving the transmission information series, and get the receiving polynomial R(x) for: $R\left(x\right)=C\left(x\right)+\mathrm{E.}\left(x\right)=c_{\mathrm{no}-1}{x}^{\mathrm{no}-1}+\&CenterDot;\&CenterDot;\&CenterDot;+{(c}_{i_1+v}+e_v)x^{i_1+v}+\&Center\; Dot;\&Center\; Dot;\&Center\; Dot;+(c_{i_1}+e_1)x^{i_1}+\&CenterDot;\&CenterDot;\&CenterDot;+c_0,$ In the formula, C(x) is the (n, k) RS code polynomial: C(x)=c _n-1 x ^n-1 +c _n-2 x ^n-2 +…+c ₁ x+c ₀ , E (x) is the error polynomial: $\mathrm{E.}\left(x\right)=e_{i_1}{x}^{i_1}+e_{i_2}{x}^{i_1+1}+\&CenterDot;\&CenterDot;\&CenterDot;+e_{i_v}{x}^{i_1+v-1},$ Where i ₁ is the lowest position of the long burst error in the code vector, ν is the burst length; and calculate its corresponding adjoint formula S _j =R(α ^j )(1≤j≤2t), α is Galois The original elements of the field GF(q); 3) Judging the syndrome obtained in the previous step: if the syndrome is not equal to zero, then the next step is transferred to step 4, otherwise the next step is skipped to step 9; 4) Calculate the burst Pattern Y _c : $\left[\begin{array}{c}{Y}_1\\ {\mathrm{<figure-callout\; id="2"\; label="Y"\; filenames="C0111013400121.png"\; state="\{\{state\}\}">Y</figure-callout>}}_2\\ \underset{.}{\overset{.}{.}}\\ Y_{2t}\end{array}\right]={\left[\begin{array}{cccc}{\mathrm{\&alpha;}}^0& \mathrm{\&alpha;}& ...& {\mathrm{\&alpha;}}^{(2t-1)}\\ {\mathrm{\&alpha;}}^0& {\mathrm{\&alpha;}}^2& ...& {\mathrm{\&alpha;}}^{2(2t-1)}\\ \underset{.}{\overset{.}{.}}& \underset{.}{\overset{.}{.}}& & \underset{.}{\overset{.}{.}}\\ {\mathrm{\&alpha;}}^0& {\mathrm{\&alpha;}}^{2t}& ...& {\mathrm{\&alpha;}}^{2t(2t-1)}\end{array}\right]}^{-1}\left[\begin{array}{c}{S}_1^{\&prime;}\\ {\mathrm{<figure-callout\; id="2"\; label="S"\; filenames="C0111013400121.png"\; state="\{\{state\}\}">S</figure-callout>}}_2^{\&prime;}\\ \underset{.}{\overset{.}{.}}\\ S_{2t}^{\&prime;}\end{array}\right],$ Here S ^′ _j =S _j (1≤j≤2t) and calculate the corresponding burst length ν _c , where ν _c is the maximum non-zero element distance in the burst pattern Y _c ; 5) compare ν _c with ν _m Size: if ν _c < ν _m , the next step is transferred to step 6, otherwise the next step is skipped to step 7; 6) Y _c , ν _c , N _c are the parameters of the current maximum possible burst pattern, and their 7) judge whether the value of N _c is greater than the code length _n : if yes, then move to step 9 in the next step _; otherwise, move to step ₈ ; 8) receive the polynomial loop right Shift 2t-ν _max +1 codeword length and calculate the corresponding syndrome, that is, calculate $S_j^{\&prime;}=\frac{S_j}{{\left({\mathrm{\&alpha;}}^j\right)}^{{2t-v}_{\max }+1}}$ (The method of cyclic left shift can also be used in the decoding process, each time the receiving polynomial is cyclically shifted to the left by 2t-ν _max +1 codeword length, that is, the calculation $S_j^{\&prime;}=S_j\&CenterDot;{\left({\mathrm{\&alpha;}}^j\right)}^{{2t-v}_{\max }+1}),$ At the same time, increase the value of the shift count variable N _c by 2t-ν _max +1, and then return to step 4 in the next step; 9) perform error correction according to the value of the error pattern Y _m and the error position N _m , and output the corrected value at the same time Information series; after this step is completed, transfer to step 10; 10) judge whether the decoding process ends: if yes, end the decoding process; otherwise the next step jumps back to step 1, and restarts the decoding of the next code vector.

The principle of the method of the present invention and the algorithm adopted are described as follows:

First consider the long burst error, whose polynomial can be expressed as: $\mathrm{E.}\left(x\right)=e_{i_1}{x}^{i_1}+e_{i_2}{x}^{i_1+1}+\&Center\; Dot;\&Center\; Dot;\&Center\; Dot;+e_{i_v}{x}^{i_1+v-1}---\left(6\right)$

Among them, i ₁ is the lowest position of the long burst error in the code vector, and ν is the burst length. Since the RS code has the property of a cyclic code, that is, the code vector obtained after encoding is cyclically shifted, and the obtained new vector is still a code vector. So the receiving vector $R\left(x\right)=C\left(x\right)+\mathrm{E.}\left(x\right)=c_{\mathrm{no}-1}{x}^{\mathrm{no}-1}+\&Center\; Dot;\&Center\; Dot;\&Center\; Dot;+{(c}_{i_1+v}+e_v)x^{i_1+v}+\&CenterDot;\&CenterDot;\&CenterDot;+(c_{i_1}+e_1)x^{i_1}+\&Center\; Dot;\&Center\; Dot;\&Center\; Dot;+c_0---(7)$

After shifting to the left by ni ₁ symbol length (or cyclically shifting to the right by i ₁ symbol length), the receiving polynomial with the lowest bit of the burst being x ⁰ =1 can be obtained: $R^{\&prime;}\left(x\right)=R\left(x\right)\&CenterDot;x^{\mathrm{no}-i_1}=C\left(x\right)\&CenterDot;x^{\mathrm{no}-i_1}+\mathrm{E.}\left(x\right)\&Center\; Dot;x^{\mathrm{no}-i_1}=C^{\&prime;}\left(x\right)+{\mathrm{E.}}^{\&prime;}\left(x\right)---\left(8\right)$ Since C'(x) is still a code vector, formulas (3) and (8) can be used to calculate the adjoint formula of R'(x). The adjoint formula corresponding to R'(x) is obtained by calculation:

S ^′ _j =S _j ·(α ^j ) ⁿⁱ (1≤j≤2t) (9).

Extend the above ν to 2t, if the actual burst length ν is less than 2t, the values of the remaining 2t-ν burst units are 0. In this way, combined with formula (6), formula (9) can be written as: The lowest bit of the burst pattern is x ⁰ , that is, X ₁ =α ⁰ =1. So (10) can be rewritten as: $\left[\begin{array}{c}{S}_1^{\&prime;}\\ {\mathrm{<figure-callout\; id="2"\; label="S"\; filenames="C0111013400121.png"\; state="\{\{state\}\}">S</figure-callout>}}_2^{\&prime;}\\ \underset{.}{\overset{.}{.}}\\ S_{2t}^{\&prime;}\end{array}\right]=\left[\begin{array}{cccc}{\mathrm{\&alpha;}}^0& \mathrm{\&alpha;}& ...& {\mathrm{\&alpha;}}^{(2t-1)}\\ {\mathrm{\&alpha;}}^0& {\mathrm{\&alpha;}}^2& ...& {\mathrm{\&alpha;}}^{2(2t-1)}\\ \underset{.}{\overset{.}{.}}& \underset{.}{\overset{.}{.}}& & \underset{.}{\overset{.}{.}}\\ {\mathrm{\&alpha;}}^0& {\mathrm{\&alpha;}}^{2t}& ...& {\mathrm{\&alpha;}}^{2t(2t-1)}\end{array}\right]\left[\begin{array}{c}{Y}_1\\ {\mathrm{<figure-callout\; id="2"\; label="Y"\; filenames="C0111013400121.png"\; state="\{\{state\}\}">Y</figure-callout>}}_2\\ \underset{.}{\overset{.}{.}}\\ Y_{2t}\end{array}\right]---\left(11\right)$ The coefficient matrix in the formula is a non-singular Vandermonde matrix and α ⁰ , α ¹ ,…, α ^(2t-1) are mutually different roots, and the coefficient matrix is invertible. Thus, there are: $\left[\begin{array}{c}{Y}_1\\ {\mathrm{<figure-callout\; id="2"\; label="Y"\; filenames="C0111013400121.png"\; state="\{\{state\}\}">Y</figure-callout>}}_2\\ \underset{.}{\overset{.}{.}}\\ Y_{2t}\end{array}\right]={\left[\begin{array}{cccc}{\mathrm{\&alpha;}}^0& \mathrm{\&alpha;}& ...& {\mathrm{\&alpha;}}^{(2t-1)}\\ {\mathrm{\&alpha;}}^0& {\mathrm{\&alpha;}}^2& ...& {\mathrm{\&alpha;}}^{2(2t-1)}\\ \underset{.}{\overset{.}{.}}& \underset{.}{\overset{.}{.}}& & \underset{.}{\overset{.}{.}}\\ {\mathrm{\&alpha;}}^0& {\mathrm{\&alpha;}}^{2t}& ...& {\mathrm{\&alpha;}}^{2t(2t-1)}\end{array}\right]}^{-1}\left[\begin{array}{c}{S}_1^{\&prime;}\\ {\mathrm{<figure-callout\; id="2"\; label="S"\; filenames="C0111013400121.png"\; state="\{\{state\}\}">S</figure-callout>}}_2^{\&prime;}\\ \underset{.}{\overset{.}{.}}\\ S_{2t}^{\&prime;}\end{array}\right]---\left(12\right)$

Note that the length of the burst pattern in the above equation is increased from t in the conventional decoding equation to 2t; the solution equation is changed from nonlinear equation (5) to linear equation (12) and the coefficient matrix is a full-rank matrix, with There is a one-to-one correspondence between formulas and burst patterns. This means that if the receiving polynomial contains a burst error, the lowest bit of the burst error must be shifted to x ⁰ after a proper cyclic shift, and the burst pattern can be calculated by formula (12).

Assuming that the maximum burst length that appears in practical applications is ν _max , when the adjoint formula is not equal to zero, move 2t-ν _max + 1 symbol bits in a cycle and then calculate the corresponding burst pattern, and repeat $\left[\frac{\mathrm{no}+2t-v_{\max }}{2t-v_{\max }+1}\right]$ times, the actual burst pattern must be included in the obtained $\left[\frac{\mathrm{no}+2t-v_{\max }}{2t-v_{\max }+1}\right]$ in a burst pattern. According to the maximum likelihood decoding criterion, the burst pattern with the shortest burst length among these burst patterns can be selected as the burst pattern obtained by decoding, and used to correct the information series.

Since the minimum distance between codes of (n, k) RS codes is d=n-k+1=2t+1, there is no decoding error in this decoding method when the burst length is less than or equal to t. When the length is greater than t but less than or equal to 2t, it is possible to find a burst shorter than the actual burst length in the decoding process, and a decoding error will occur at this time. However, the error probability of the decoding method of the present invention is still very low. As an example, the error decoding probability under a specific burst of the (255, 223) RS code is shown in Table 1, where ν _max =2t=32. What needs to be explained here is that when the actual burst length is equal to 2t, since none of the burst patterns calculated in the decoding process is greater than 2t, it cannot be decoded correctly, and the error decoding probability is 1. It can be seen from Table 1 that when the burst length is 28 symbols (equal to 224 bits), the error probability of this decoding method can be as low as 10 ⁻⁸ .

Table 1 Error decoding probabilities of (255, 223) RS codes under different burst lengths. Burst length (symbols) misdecoding probability Burst length (symbols) misdecoding probability 17 8.4× ^10-35 25 1.4× ^10-15 18 2.1× ^10-32 26 3.4×10 ^-13 19 5.3× ^10-30 27 8.6× ^10-11 20 1.3×10 ^-27 28 2.2×10 ^-8 twenty one 3.4× ^10-25 29 5.4×10 ^-6 twenty two 8.5×10 ^-23 30 1.4×10 ^-3 twenty three 2.1× ^10-20 31 0.34 twenty four 5.4× ^10-18 32 1.0

It can be seen that using this method can correct long burst errors with a length close to 2t with high accuracy, thus greatly improving the ability of RS codes to correct long burst errors.

The effect of the present invention is that by utilizing the characteristics of burst errors, the length of long burst errors that can be corrected by the RS code is increased from t in the traditional decoding method to nearly 2t, and its error correction capability is nearly doubled. At the same time, compared with the existing method 1, it reduces the delay caused by interleaving and deinterleaving, and compared with the existing method 2, it does not lose the information transmission rate; The complex method of solving nonlinear equations is simplified to the decoding method of linear equations, which not only reduces the complexity of the decoding method, makes it easy for hardware implementation, but also helps to further reduce the decoding delay by increasing the operating frequency of the circuit. hour. Therefore, when the RS code is applied to correct long burst errors, the performance of this decoding method is obviously better than other methods.

Description of drawings

Fig. 1 is a flow chart of the software implementation of the present invention.

Fig. 2 is a block diagram of a decoder designed according to the method of the present invention.

Fig. 3 is a diagram of a communication system for correcting long burst errors using the method of the present invention.

FIG. 4 is a block diagram of a communication system in which a concatenated code composed of RS codes using the decoding method as the outer code and convolutional codes as the inner code is applied to a composite channel.

Detailed ways

Below, explain the present invention in more detail according to accompanying drawing and two embodiments:

Embodiment 1: This embodiment uses software to implement the error correction decoding method proposed by the present invention, as shown in FIG. 1 . This embodiment adopts (255, 223) RS code, the maximum correctable burst length is the decoding algorithm of 28 codewords, and the decoding process includes the following steps: after the decoding starts, the decoder transfers from step 1a to step 1b , to initialize: set the value of the burst length ν _m of the current maximum possible error pattern to 32, the value of the burst pattern Y _m to 0, and the value of the lowest burst position N _m to 0; at the same time, shift the count variable N _c The value of is set to 0; then the decoder shifts to step 1c, starts to receive the transmission information series R(x), and uses (3) to calculate its corresponding adjoint formula S _j (1≤j≤32); complete this step Afterwards, the decoder goes to step 1d to judge the syndrome obtained in the previous step: if the syndrome is not equal to zero, then the next step is transferred to step 1e, otherwise the next step is skipped to step 1j. In step 1e, the burst pattern Y _c (here S' _j =S _j (1≤j≤32)) is calculated by formula (12) and the corresponding burst length ν _c is calculated. Then the decoder transfers from step 1e to step 1f, and compares ν _c and ν _m : if ν _c < ν _m , the next step transfers to step 1g, otherwise the next step jumps to step 1h. In step 1g, Y _c , ν _c , and N _c are the parameters of the current maximum possible burst pattern, and their values are used to cover the values of Y _m , ν _m , and N _m respectively. Subsequently, the decoder moves to step 1h to judge whether the value of N _c is greater than 255: if yes, then move to step 1j; otherwise, move to step 1i. In step 1i, the decoder cyclically shifts the received polynomial to the right by 5 codeword lengths and calculates the corresponding syndrome, that is, calculates $S_j^{\&prime;}=\frac{S_j}{{\left({\mathrm{\&alpha;}}^j\right)}^5}$ (1≤j≤32) (The method of cyclic left shift can also be used in the decoding process, each time the receiving polynomial is cyclically shifted to the left by 5 codeword lengths, that is, calculate S′ _j =S _j ·(α ^j ) ⁵ (1≤j≤32)), and increase the value of the shift count variable by 5, and then return to step 1e in the next step. In step 1j, the decoder performs error correction according to the values of the error pattern Y _m and the error position N _m , and at the same time outputs the corrected information series. After completing the operation of step 1j, the decoder transfers to step 1k to judge whether the decoding process ends: if yes, then the next step transfers to step 11 to end the decoding process; otherwise, the next step jumps back to step 1b and restarts the next step. Decoding of a code vector.

Embodiment 2: This embodiment implements the decoding method of the present invention by using hardware. Present embodiment still adopts (255,223) RS code, the decoding algorithm that the maximum correctable burst length is 28 codewords, the composition of this hardware circuit and decoding work process: as shown in Figure 2, in code stream 21 During the input process, the 32 syndrome calculation and shift register circuits 22-24 are in the calculation syndrome state, and the information part of the input code stream is temporarily stored in the memory 25 with a capacity of 223 codewords. During this period, the decoding circuit on the right side completes the initialization: the burst pattern register 29 is set to 0, the burst length calculation and register in the comparison circuit 2a is set to an initial value of 32, and the value of the burst lowest bit memory 2b is set to 0 , the shift counter 2c is reset to 0 state. When a code polynomial has been received, the decoder switches to the state of calculating burst patterns. Now 32 adjoint calculations and shift circuits 22-24 work in the shift state, and every clock pulse adjoint circuit completes a shift operation, and the shift counter adds 5 at the same time, and the value of the new adjoint formula is passed by the combination The matrix multiplication circuit 26 composed of logic circuits completes the operation of formula (12) to obtain corresponding burst patterns 27 and 28 . The burst pattern 28 is output to the burst length calculation and comparison circuit 2a for burst length calculation, and compared with the register value in this part of the circuit. If the calculated burst length is less than the register value, replace the burst length value with the register value and at the same time make the comparison result output a high level, so that the burst pattern register overwrites the original pattern value with burst pattern 27, and the burst minimum The position memory is loaded with the current value of the shift counter 2c as the corresponding burst lowest position. Work like this until the value of the shift counter 2c is greater than the code length 255, then the left part 21-25 of the decoding circuit turns into the receiving state; simultaneously the right side circuit 25-2d turns into the error correction output state: the information queue is transferred from the memory 25 according to the clock beat Output, the burst lowest position memory 2b enables the burst pattern register 29 and the one-of-two selector 2d at the burst position, so that the burst pattern output is added to the information series to complete error correction.

It can be seen from the above embodiments that, compared with the conventional error correction decoding method adopted by the two methods introduced above, this decoding method not only has stronger error correction capability, less time delay, but also is simple to implement. The application of the present invention in a communication system will be described below through two examples.

Example one, with reference to Fig. 3, the communication system that corrects long burst error includes a source 31 that produces digital information flow, RS coder 33, burst channel 35, and correct burst error decoder as shown in Fig. 2 37. In this example, the data symbol stream 32 carrying information generated by the information source 31 is sent to the RS code encoder 33, and the RS code encoder 33 performs channel encoding on the information. The coded RS code stream 34 is interfered in the transmission process of the long burst channel 35 to generate a long burst error, and the code stream 36 containing the long burst error is received by the RS code decoder 37 which corrects the long burst error. After error correction and decoding by the RS code decoder 37 for correcting long burst errors, the output code stream 38 is a correct digital information stream.

This decoding method is not only suitable for pure burst channels, but also can be combined with other codes to form concatenated codes to correct the mixed errors of both random errors and long burst errors in composite channels. An example is given below.

Example 2: As shown in Figure 4, the data stream generated by the digital source 41 is sent to the RS code encoder 43 and the convolutional code encoder 45 in turn to encode the outer code and the inner code, and then the output concatenated code stream 46 Transmission via composite channel 47. Due to the influence of various factors in the transmission process, the received concatenated code stream 48 will contain random errors and composite errors of burst errors, and these information streams containing composite errors are first sent to the convolutional code decoder for further processing. It is mainly aimed at error correction decoding of random errors. When a piece of code stream only contains random errors within the error correction capability of the convolutional code, these random errors can be corrected by decoding the convolutional code, and its output 4a is a correct information series; when this piece If the code stream contains long bursts or the number of random errors is greater than the error correction range of the convolutional code, the convolutional code fails to decode, and its output 4a can be considered as a long burst error. After the error correction decoding is performed by the burst error correction decoder 4b of the RS code, the long burst error is corrected. Obviously, by properly selecting the length of the inner and outer codes and the error correction ability according to the channel characteristics and using this method as the decoding method of the outer code, a concatenated code with stronger error correction ability can be obtained, so that at the same information transmission rate, Data with a lower error rate, or a higher data rate can be used for transmission under the same error rate.

Since the RS code is a subclass of the BCH code, the method of the invention is fully applicable to the BCH code, and can also be extended to all cyclic codes.

Claims (1)

1, a kind of long burst error correction decoding method that adopts Reed-Solomon code, comprises the following steps: 1) carry out initialization: the value of the burst length ν _m of setting current maximum possible error pattern is 2t, burst The value of the transmission pattern Y _m is 0, the value of the lowest burst position N _m is 0; at the same time, the value of the shift count variable N _c is set to 0; 2) start receiving the transmission information series, and the receiving polynomial R(x) is obtained as: $R\left(x\right)=C\left(x\right)+\mathrm{E.}\left(x\right)=c_{\mathrm{no}-1}{x}^{\mathrm{no}-1}+\&Center\; Dot;\&Center\; Dot;\&Center\; Dot;+{(c}_{i_1+v}+e_v)x^{i_1+v}+\&Center\; Dot;\&Center\; Dot;\&Center\; Dot;+(c_{i_1}+e_i)x^{i_1}+\&Center\; Dot;\&Center\; Dot;\&CenterDot;+c_0,$ In the formula, C(x) is the (n, k) RS code polynomial: C(x)=c _n-1 x ^n-1 +c _n-2 x ^n-2 +…+c ₁ x+c ₀ , E (x) is the error polynomial: $\mathrm{E.}\left(x\right)=e_{i_1}{x}^{i_1}+e_{i_2}{x}^{i_1+1}+\&CenterDot;\&CenterDot;\&CenterDot;+e_{i_v}{x}^{i_1+v-1},$ Where i ₁ is the lowest position of the long burst error in the code vector, ν is the burst length; and calculate its corresponding adjoint formula S _j =R(α ^j )(1≤j≤2t), α is Galois The original elements of the field DF(q); 3) Judging the syndrome obtained in the previous step: if the syndrome is not equal to zero, then the next step is transferred to step 4, otherwise the next step is skipped to step 9; 4) Calculate the burst Pattern Y _c : $\left[\begin{array}{c}{Y}_1\\ Y_2\\ \underset{.}{\overset{.}{.}}\\ Y_{2t}\end{array}\right]={\left[\begin{array}{cccc}{\mathrm{\&alpha;}}^0& \mathrm{\&alpha;}& ...& {\mathrm{\&alpha;}}^{(2t-1)}\\ {\mathrm{\&alpha;}}^0& {\mathrm{\&alpha;}}^2& ...& {\mathrm{\&alpha;}}^{2(2t-1)}\\ \underset{.}{\overset{.}{.}}& \underset{.}{\overset{.}{.}}& & \underset{.}{\overset{.}{.}}\\ {\mathrm{\&alpha;}}^0& {\mathrm{\&alpha;}}^{2t}& ...& {\mathrm{\&alpha;}}^{2t(2t-1)}\end{array}\right]}^{-1}\left[\begin{array}{c}{S}_1^{\&prime;}\\ S_2^{\&prime;}\\ \underset{.}{\overset{.}{.}}\\ S_{2t}^{\&prime;}\end{array}\right],$ Here S ^′ _j =S _j (1≤j≤2t) and calculate the corresponding burst length ν _c , where ν _c is the maximum non-zero element distance in the burst pattern Y _c ; 5) compare ν _c with ν _m Size: if ν _c < ν _m , the next step is transferred to step 6, otherwise the next step is skipped to step 7; 6) Y _c , ν _c , N _c are the parameters of the current maximum possible burst pattern, and their 7) judge whether the value of N _c is greater than the code length _n : if yes, then move to step 9 in the next step _; otherwise, move to step ₈ ; 8) receive the polynomial loop right Shift 2t-ν _max +1 codeword length and calculate the corresponding syndrome, that is, calculate $S_j^{\&prime;}=\frac{S_j}{{\left(a^j\right)}^{{2t-v}_{\max }+1}}$ Or use the method of cyclic left shift in the decoding process, each time the receiving polynomial is cyclically shifted to the left by 2t-ν _max +1 codeword length, that is, calculate $S_j^{\&prime;}=S_j\&Center\; Dot;{\left(a^j\right)}^{{2t-v}_{\max }+1},$ At the same time, increase the value of the shift count variable N _c by 2t-ν _max +1, and then return to step 4 in the next step; 9) perform error correction according to the value of the error pattern Y _m and the error position N _m , and output the corrected value at the same time Information series; after this step is completed, transfer to step 10; 10) judge whether the decoding process ends: if yes, end the decoding process; otherwise the next step jumps back to step 1, and restarts the decoding of the next code vector.

Images