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

Abstract

The invention belongs to the technical field of communication. The method includes: based on the cyclic characteristics of the RS code, by effectively utilizing the relationship before and after the cyclic shift of the RS code reception polynomial, and the error position correlation of the long burst, assuming the error position of the burst error In order to receive the lowest 2t bits of the polynomial, the coding method is simplified as a method of cyclically shifting the receiving polynomial, and then solving the error pattern by a set of linear equations. The present invention realizes error correction decoding suitable for long burst errors with relatively much smaller decoding delay and relatively much higher information transmission rate.

Description

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

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.

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个错误的位置。因此接收多项式可表示为：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}^{i_2}+...+e_{i_1}{x}^{i_v}---\left(1\right)$ In the formula, v is the number of errors actually occurred, 0≤v≤t;

Indicates the value of the rth error; i _r indicates the location of the rth error. So the reception polynomial can be expressed as:

R(x)=C(x)+E(x) (2) where C(x)=c _n-1 x ^n-1 +c _n-2 x ^n-2 +...+c ₁ x+c ₀ is (n, k) Code polynomial after RS code encoding. The adjoint obtained from the receiving polynomial is:

(r＝1，2，…，v)为错误值；(r＝1，2，…，v)为错误位置，则： $E\left({\mathrm{\α}}^j\right)=e_{i_1}{\left({\mathrm{\α}}^j\right)}^{i_1}+e_{i_2}{\left({\mathrm{\α}}^j\right)}^{j_2}+...+e_{i_v}{\left({\mathrm{\α}}^j\right)}^{j_v}$ $=e_{i_1}{\left({\mathrm{\α}}^{j_1}\right)}^j+e_{i_2}{\left({\mathrm{\α}}^{j_2}\right)}^j+...+e_{i_v}{\left({\mathrm{\α}}^{j_v}\right)}^j---\left(4\right)$ $=Y_1{X}_1^j+Y_2{X}_2^j+...+Y_v{X}_v^j$ 将(2)式代入(1)式并将所得的式子展开，得到2t个方程式：

S _j ＝R(α ^j )＝C(α ^j )+E(α ^j )＝Eα ^j )(1≤j≤2t) (3) For convenience, define

(r=1, 2, ..., v) is an error value; (r=1, 2, ..., v) is the wrong position, then: $\mathrm{E.}\left({\mathrm{\α}}^j\right)=e_{i_1}{\left({\mathrm{\α}}^j\right)}^{i_1}+e_{i_2}{\left({\mathrm{\α}}^j\right)}^{j_2}+...+e_{i_v}{\left({\mathrm{\α}}^j\right)}^{j_v}$ $=e_{i_1}{\left({\mathrm{\α}}^{j_1}\right)}^j+e_{i_2}{\left({\mathrm{\α}}^{j_2}\right)}^j+...+e_{i_v}{\left({\mathrm{\α}}^{j_v}\right)}^j---\left(4\right)$ $=Y_1{x}_1^j+Y_2{x}_2^j+...+Y_v{x}_v^j$ Substitute (2) into (1) and expand the obtained formula to get 2t equations:

There are 2t equations in the above equations, and there are less than 2t unknowns, and X ₁ , X ₂ ,..., X _v in the equations constitute a always invertible Vandermonde matrix, 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.

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 _lm of setting current maximum possible error pattern is 2t , the value of the burst pattern Y _m is 0, and 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 to receive the transmission information series R(x), and calculate its Corresponding syndrome S _j (1≤j≤2t); 3) Judging the syndrome obtained in the previous step: if the syndrome is not equal to zero, then the next step will be transferred to step 4, otherwise the next step will be skipped to step 9; 4 ) calculate the burst pattern Y _c , where S′ _j =S _j (1≤j≤2t) and calculate the corresponding burst length l _c ; 5) compare the size of l _c and l _m : if l _c <l _m , The next step is transferred to step 6, otherwise the next step is skipped to step 7; 6) Y _c , l _c , N _c are the parameters of the current maximum possible burst pattern, and their values are used to cover Y _m , l _m , The value of N _m ; 7) Judging whether the value of N _c is greater than the code length n: if yes, then the next step is transferred to step 9; otherwise, transferred to step 8; 8) The receiving polynomial is cyclically shifted to the right by 2t-v _max +1 code word length and calculate the corresponding adjoint formula, 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-v _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 by 2t-v _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 error position N _m , and output the corrected information at the same time series; after this step is completed, transfer to step 10 to 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}+...+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 v 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_{h-1}{x}^{\mathrm{no}-1}+...+(c_{i_1+v}+e_v)x^{i_1+v}+...+(c_{i_1}+e_1)x^{i_1}+...+c_0---\left(7\right)$

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)\&Center\; Dot;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 v to 2t, if the actual burst length v is less than 2t, the values of the remaining 2t-v burst units are 0. In this way, combined with formula (6), formula (9) can be written as:

式中的系数矩阵是一个非奇异范德蒙矩阵且α⁰，α¹，…，α^(2t-1)为互不相同的根，该系数矩阵可逆。因而，有： The lowest bit of the burst pattern is x ⁰ , that is, X ₁ =α ⁰ =1. So (10) can be rewritten as:

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:

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 v _max , when the adjoint formula is not equal to zero, cyclically move 2t-v _max +1 sign bits and then calculate the corresponding burst pattern, and so on $\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 (255, 223) RS code is shown in Table 1, where v _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.

Brief description of the 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.

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 l _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; simultaneously 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 l _c is calculated. Then the decoder transfers from step 1e to step 1f, and compares the size of l _c and l _m : if l _c <l _m , the next step transfers to step 1g, otherwise the next step jumps to step 1h. In step 1g, Y _c , l _c , and N _c are the parameters of the current maximum possible burst pattern, and their values are used to overwrite the values of Y _m , l _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\&le;j\&le;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, to calculate S′ _j =S _j ·(α ^j ) ⁵ (1≤j≤32 )) while increasing 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-correcting decoding method that adopts Reed-solomon code may further comprise the steps:

1) carries out initialization: the burst length l that the error pattern of current maximum possible is set _mValue be 2t, burst pattern Y _mValue be 0, minimum burst position N _mValue be 0; While shift count variable N _cValue be set to 0;

2) begin to receive transmission information series R (x), and calculate its corresponding syndrome S _j(1≤j≤2t);

3) syndrome of previous step gained is judged: if syndrome is not equal to zero, then next step transfers to step 4, otherwise next step jumps to step 9;

4) calculate burst pattern Y _c, S ＇ here _j=S _j(1≤j≤2t) also calculates corresponding burst length l _c

5) compare l _cWith l _mSize: if l _c＜l _m, next step transfers to step 6, otherwise next step jumps to step 7;

6) Y _c, l _c, N _cBe the parameter of the burst pattern of current maximum possible, the value with them overrides Y respectively _m, l _m, N _mValue;

7) judge N _cValue whether greater than code length n: if then next step transfers to step 9; Otherwise transfer to step 8;

8) receiverd polynomial ring shift right 2t-v _Max+ 1 code word size also calculates corresponding syndrome, promptly calculates $S_j^{\&prime;}=\frac{S_j}{{\left(a^j\right)}^{{2t-v}_{\max }+1}}$ , the value with the shift count variable increases 2t-v simultaneously _Max+ 1, next step turns back to step 4 then;

9) according to error pattern Y _mWith errors present N _mValue carry out error correction, export the information series after the error correction simultaneously; After this step is finished, transfer to step 10, judge whether decode procedure finishes: if finish decode procedure; Otherwise next step jumps back to step 1, restarts the decoding of next code vector.

Images