CN111900998B - LDPC code dynamic turning decoding method based on packet parallel processing - Google Patents

Abstract

The invention discloses a dynamic overturn decoding method of an LDPC code by grouping parallel processing, which is characterized in that whether the decoding is in a state cycle or not is detected by detecting an overturn sequence of two adjacent iterations in the process of the iteration overturn decoding, and after the state cycle is detected, a grouping bit overturn threshold and an overturn bit number are dynamically changed, so that the invalid iteration of bit overturn decoding is effectively eliminated, and the system performance is improved. The invention judges whether the state cycle condition exists in the grouped bit reversal decoding through simple check formula calculation, namely when the two adjacent check formula sequences are the same, the iterative decoding is determined to fall into the error cycle, and the bit can not be effectively reversed. After the circulation state is judged, the method of dynamically changing the packet bit turning threshold and the turning bit number is adopted to effectively break the state circulation and obtain the performance improvement. The improved method is established on the basis of hard decision flip decoding, and has the advantages of rapid iterative convergence, high decoding throughput rate and low implementation complexity.

Description

A Dynamic Flipping Decoding Method for LDPC Codes Based on Packet Parallel Processing

technical field

The invention relates to an iterative decoding method of LDPC codes, in particular to an improved algorithm based on a packet hard-decision bit flip decoding algorithm, and belongs to the technical field of decoding.

Background technique

Low Density Parity Check (LDPC, Low Density Parity Check) code is a linear block code, which can be represented by Tanner diagram and parity check matrix H. The number of non-zero elements in the parity check matrix is far less than zero elements the number of . Because of its superior performance close to the Shannon limit, it has attracted great attention in the field of channel coding. At present, LDPC codes have been widely used in mobile and deep space communications and other fields, and have very important application prospects. For regular LDPC codes, each row and each column contain the same number of non-zero elements, where the number of non-zero elements in each column (row) is called the column (row) weight. After the LDPC code word is transmitted through the channel, the receiving end needs to perform channel decoding on it. The LDPC decoding algorithm is mainly divided into three categories: hard decision decoding algorithm, soft decision decoding algorithm and mixed decision decoding algorithm. The soft-decision decoding algorithm increases the complexity of the decoding algorithm due to the introduction of soft information, while the hard-decision decoding algorithm has simple ideas, low complexity, and is easy to implement in hardware.

Bit Flipping (BF, Bit Flipping) decoding is a hard-decision decoding method proposed by Gallager, which only flips one bit with the maximum flipping weight in each iteration, but in a limited number of iterations Under the condition, the number of bits that can be corrected is very limited, and the algorithm converges slowly, resulting in poor decoding performance; in order to speed up the convergence speed, it is proposed to flip all the bits with the maximum flip weight in each iteration, although the algorithm only involves real operations, The implementation is simple, but finding the maximum flip weight value increases the complexity of the algorithm. Some scholars propose to add a new parameter in the decoding algorithm: the threshold threshold, and flip all the bits that reach the threshold. Therefore, in each iterative decoding process, multiple bits may be flipped, which increases the convergence speed of decoding, and does not need to find the maximum flip weight, reducing the complexity of the algorithm.

In the iterative decoding process, if all the bits that reach the threshold value are flipped, the original correct bits may be flipped, that is, there is an overcorrection problem. Based on this, a new decoding algorithm is proposed—— MBF algorithm (see literature: Jaehwan Jung, In-Cheol Park.Multi-Bit Flipping Decoding of LDPC Codes forNAND Storage Systems.IEEE Communication Letters.VOL.21,NO.5,MAY 2017.), the algorithm proposed, in the determined Under the flipping threshold T _h , there is an optimal number of flipping bits F _x , and the bits whose flipping weight reaches the threshold are regarded as candidates. If the number of candidates exceeds F _x , the candidates are selected according to the flipping weight by From large to small, select the first F _x to flip, otherwise flip all the candidates. However, to compare and sort the flipping weights and find the first F _x bits globally is very complicated, and requires a large number of comparison units and storage units on the hardware. Based on this, the author proposes an AMBF algorithm to divide the codewords into Q groups. , select a bit with the largest flipping weight value from each group to form a candidate flipping bit set of size Q, and select F _x local maxima with the largest flipping weights for flipping.

SUMMARY OF THE INVENTION

Purpose of the invention: In order to overcome the deficiencies in the prior art, the present invention provides a dynamic inversion decoding method for LDPC codes processed in parallel by grouping. In the iterative inversion decoding process, the inversion sequences of two adjacent iterations are detected to determine whether the decoding results in The code is in a state loop, and after the state loop is detected, the packet bit flip threshold and the number of flip bits are dynamically changed, effectively eliminating the invalid iteration of bit flip decoding and improving system performance. The present invention judges whether there is a state cycle in packet bit flip decoding through simple check formula calculation, that is, when two adjacent check formula sequences are the same, it is determined that iterative decoding falls into an error cycle and cannot effectively flip bits. After the cycle state is judged, the method of dynamically changing the packet bit flipping threshold and the number of flipping bits is used to effectively break the state cycle and improve performance. This method improves the decoding reliability, and no soft information is introduced in the whole decoding process, the hardware implementation is simple, the iterative convergence is fast, the decoding throughput rate is high, and the algorithm complexity is low.

Technical scheme: in order to achieve the above object, the technical scheme adopted in the present invention is:

A dynamic flipping decoding method for LDPC codes that is grouped and processed in parallel. For an LDPC code with a code length of N, the parity check matrix H _M×N has a dimension of M rows and N columns, and h _m,n is recorded as the mth row of the matrix The elements of n columns. The set of column coordinates of non-zero elements in each row is B(m), h _{m, n} = 1, n∈B(m), m = 1,..., M, and the set of row coordinates of non-zero elements in each column is A(n ), h _{m, n} ＝1, m∈A(n), n＝1,…, N, including the following steps:

q＝1,…,Q-1,最后一个分组g_Q的比特长度为L_Q＝N-(Q-1)L₁，其中，L₁表示第一个分组的比特长度，对信道输出的加噪码字r＝(r₁,r₂,...,r_N)进行硬判决，得到初始长度为N的硬判决比特序列z¹＝(z₁,z₂,...,z_N)，即如果r_n>0，则z_n＝1，否则z_n＝0,n＝1,2,...,N，迭代次数k＝1，进入迭代译码。Step 1. Initialization: Initialize all M row check formulas of the check matrix H=[h _m,n ] _M×N of LDPC code size M×N to an all-zero row vector s ⁰ =[ s ₁ , s ₂ ,…,s _M ] ⁰ ＝0 _M , h _{m, n} are the elements of row m and column n of the parity check matrix, the flipping threshold is T _h ＝t ₀ , and the maximum bit that is allowed to flip in each iteration The number is F _x =f ₀ , the maximum number of iterations is k _max , and the coded bits of length N are sequentially divided into Q groups g ₁ , g ₂ ,...,g _Q , where the bit length of the first Q-1 groups is

q=1,...,Q-1, the bit length of the last packet g _Q is L _Q =N-(Q-1)L ₁ , where L ₁ represents the bit length of the first packet, and the addition of the channel output Random code word r=(r ₁ , r ₂ ,...,r _N ) performs hard decision, and obtains a hard decision bit sequence z ¹ =(z ₁ ,z ₂ ,...,z _N ) with an initial length of N , that is, if r _n >0, then z _n =1, otherwise z _n =0, n=1, 2,...,N, the number of iterations k=1, and enter iterative decoding.

Step 2. Calculation of check formulas: calculate the M check formulas of the current iteration by s ^k =z ^k *H ^T (mod 2), s ^k and z ^k respectively represent the check formulas and decoding sequences of the kth iteration ^HT represents the transposition of H, and mod represents the remainder function. If all zeros s ^k =0 _M , it means that all codewords satisfy the checksum and the decoding is successful. Output the current codeword sequence z ^k and decode success. Otherwise, if k≤k _max , perform the iterative decoding step 3, if k>k _max , the decoding fails, output the initial hard decision code word z ¹ , and end the iterative decoding, where k represents the current iteration number.

Step 3. Calculation of flipping weights: For Q groups g ₁ , g ₂ ,...,g _Q , calculate the flipping weights of all bits in parallel according to the formula E _n =∑ _m∈A(n) (2s _m -1) E _n ,n=1,...,N, where A(n) is a set of check formulas involving the nth bit, h _m,n =1,m∈A(n).

Step 4. Determine the flip bit set: for Q groups g ₁ , g ₂ ,...,g _Q , find a bit in parallel with the maximum flip weight in each group n _q =arg max{E _n' ,n' ∈g _q }, q=1,...,Q, get a candidate flip bit set κ={n ₁ ,n ₂ ,...,n _Q } whose size is Q.

Step 5, state loop detection: compare the check formula sequence sk in the current iteration process with the check formula sequence ^{sk -1} in the previous iteration, and adjust the threshold value.

Step 6. Flip bits: In the candidate flip bit set κ, further screen the bits whose flip weight reaches or exceeds the threshold T _h to obtain a set κ*={n”∈κ,E _n ”≥T _h }, the size of the set is recorded is N _κ , then arrange the bits of the set κ*, and obtain a new codeword sequence z ^k+1 according to the arranged set κ*.

Step 7. Update the number of iterations: add one to the number of iterations, k=k+1, and execute decoding step 2.

Preferably: the method of adjusting the threshold value in step 5: if s ^k =s ^k-1 is the same, adjust the threshold value T _h =t ₁ , flip the number of bits to F _x =f ₁ , otherwise T _h =t ₀ ,F _x =f ₀ .

Preferably: the method of obtaining a new codeword sequence z ^k+1 according to the arranged set κ* in step 6: if the number of bits N _κ ≥ F _x in the set κ*, select the first F _x in the set κ* Bits {n _i , i=1,...,F _x ,n _i ∈κ*}, perform bit flipping on the bit elements at the corresponding positions in the sequence z ^k , if the number of bits N _κ <F _x in the set κ*, then According to all the bits in the set κ*, the bit elements at the corresponding positions in the sequence z ^k are flipped to obtain a new codeword sequence z ^k+1 .

Preferably: in step 6, the bits of the set κ* are arranged according to the flip weight.

Preferably: in step 6, the bits of the set κ* are arranged in descending order according to the flipping weight.

Compared with the prior art, the present invention has the following beneficial effects:

The decoding method proposed by the present invention dynamically adjusts the flipping threshold T _h and the maximum flipping bit number F _x allowed for each iteration by automatically detecting the values of two adjacent check formulas, thereby changing the bits in the candidate bit set, and correspondingly Ground, cause the change of the bit flip situation, achieve the effect of breaking the state cycle, and obtain the improvement of the decoding performance. For different codewords, the cycle situation is different, which will be related to the improvement of performance by breaking the cycle. Because the cycle leads to codewords whose final decoding errors account for a relatively large codeword, it can bring obvious improvements. In addition, the calculation of the bit flipping weight in each group and the search for the bit with the maximum flipping weight value are processed in parallel between groups, which shortens the decoding delay and is beneficial to the application of low-latency hardware.

The decoding algorithms proposed by the present invention are all based on hard-judgment flip decoding, and have rapid iterative convergence, small delay, high decoding throughput, good error correction performance, and low implementation complexity.

Description of drawings

Fig. 1 is a processing flowchart of the decoding method proposed by the present invention.

Fig. 2 is a simulation verification diagram of the present invention: a frame error rate curve diagram of (607,60,6) QC-LDPC code.

Fig. 3 is a simulation verification diagram of the present invention: a curve diagram of the average number of iterations of (607,60,6) QC-LDPC codes.

Detailed ways

Below in conjunction with accompanying drawing and specific embodiment, further illustrate the present invention, should be understood that these examples are only for illustrating the present invention and are not intended to limit the scope of the present invention, after having read the present invention, those skilled in the art will understand various aspects of the present invention All modifications of the valence form fall within the scope defined by the appended claims of the present application.

进行硬判决，得到硬判决序列z¹＝(z₁,z₂,...,z_N)，其中z_i∈{0,1}，然后对硬判序列z¹进行译码。Suppose c is a binary LDPC codeword whose check matrix is H _M×N , and the set of non-zero element column coordinates of each row is B(m), h _{m, n} = 1, n∈B(m), m = 1,...,M, the set of row coordinates of non-zero elements in each column is A(n),h _m,n =1,m∈A(n),n=1,...,N, the coding sequence c=(c ₁ ,c ₂ ,...,c _N ), through binary phase shift keying (BPSK) modulation to obtain x=(x ₁ ,x ₂ ,...,x _N ), where x _i =2c _i -1, a The mutually uncorrelated and independent sequence representing additive white Gaussian noise (AWGN) is defined as v=(v ₁ ,v ₂ ,...,v _N ), then the output real-valued signal sequence through the AWGN channel is expressed as r =(r ₁ ,r ₂ ,...,r _N ), where r _i = _xi +v _i . The received sequence r follows the rule

Perform a hard decision to obtain a hard decision sequence z ¹ =(z ₁ ,z ₂ ,...,z _N ), where z _i ∈{0,1}, and then decode the hard decision sequence z ¹ .

In this embodiment, the (607,60,6) QC-LDPC code with a column weight of 6 and a row weight of 60 is selected for testing, and its dimension size is (6×607)×(60×607), and the length of the coding sequence is N=36420, check formula number is M=3642, in conjunction with the algorithm flowchart of the present invention (as shown in Figure 1), the whole decoding process of algorithm is described in detail:

q＝1,…,31，最后一个分组g₃₂的比特长度为L₃₂＝36420-31×1138＝1142，对初始硬判决比特序列z¹进行迭代译码：S1: Set the maximum number of iterations k _max to 50, the current number of iterations to 1, set the threshold T _h to t ₀ =4, set the maximum number of flipped bits F _x to f ₀ =8, and initialize the array vector s ⁰ = with a dimension of 3642 [s ₁ , s ₂ ,…,s ₃₆₄₂ ] ⁰ ＝0 ₃₆₄₂ , divide the codeword into Q=32 groups according to the length, g ₁ , g ₂ ,…,g ₃₂ , wherein the bit length of the first 31 groups is

q=1,...,31, the bit length of the last packet g ₃₂ is L ₃₂ =36420-31×1138=1142, iteratively decoding the initial hard-decision bit sequence z ¹ :

S2: Calculate the value of the current iterative check formula by s ^k =z ^k *H ^T (mod 2), if s ^k =0 ₃₆₄₂ , the decoding is successful, and output the current codeword sequence z ^k . Otherwise, if k≤50, go to S3; if k>50, the decoding fails, the iterative decoding ends, and z ¹ is output.

S3: For the groups g ₁ , g ₂ ,...,g ₃₂ , according to the formula E _n =∑ _m∈A(n) (2s _m -1), calculate the flip weights E _n of all bits in parallel, n=1, 2,...,36420.

S4: For groups g ₁ , g ₂ ,…,g ₃₂ , find a bit in parallel with the maximum flip weight in each group n _q =arg max{E _n' ,n'∈g _q },q=1 ,2,...,32, to obtain a candidate flip bit set κ={n ₁ ,n ₂ ,...,n ₃₂ } whose size is 32.

S5: Compare the check formula sequence s ^k in the current iteration process with the check formula sequence ^sk-1 in the previous iteration, if s ^k =s ^{k -1} , adjust the T _h value to t ₁ =0, F _x value f ₁ =16, otherwise _Th =4, F _x =8.

S6: In the candidate flip bit set κ, select the bits whose flip weight reaches or exceeds the threshold T _h to obtain a set κ*={n”∈κ,E _n'' ≥T _h }, and the set size is denoted as N _κ , Then arrange the bits of the set κ* in descending order according to the flipping weight. If the number of elements N _κ ≥ F _x in the set κ*, select the first F _x bits {n _i ,i=1,… ,F _x ,n _i ∈κ*} flips the bit elements at the corresponding positions in the sequence z ^k , if the number of bits in the set κ* N _κ < F _x , then flip all the bits in the set κ* to the sequence z The bit elements at corresponding positions in ^k are flipped to obtain a new codeword sequence z ^k+1 .

S7: the number of iterations k=k+1, return to S2.

This decoding method aims at detecting whether a state cycle occurs during the decoding process by comparing two adjacent check formulas, and dynamically adjusts the flip threshold and the number of flip bits. For example, in S5, when two adjacent check formulas At the same time, it shows that the decoding is stuck in a state loop, lowering the flipping threshold to 0, increasing the number of flipping bits to 16, changing the elements in the flipping bit set, causing the flipping bits to change, thereby destroying the flipping state of the codeword that is caught in a cycle, making it impossible to Decoding the correct codeword has a chance of successful decoding, which improves the decoding performance.

It can be seen from Figure 2 that breaking the cycle algorithm has a significant improvement on the performance of (607,60,6)QC-LDPC. According to the test statistics, as shown in Table 1, the codeword (607,60,6)QC- LDPC has a large proportion of bit errors due to looping. When the signal-to-noise ratio is 5.4dB and 5.5dB, frame errors are caused by falling into a state loop. Therefore, when the mechanism of breaking the state loop is introduced, the original loop cannot be decoded correctly. The codeword can also get the correct decoding result, which improves the decoding performance. At the same time, in the decoding algorithm proposed by the present invention, the calculation of the flipping weight and the search for the maximum flipping weight value are all processed in parallel between groups, which reduces the decoding delay.

Table 1 (607, 60, 6) QC-LDPC codes under different SNRs, statistics on the proportion of state cycles in errored frames

Fig. 2 and Fig. 3 respectively represent under AMBF algorithm and the algorithm (break_loop AMBF, BAMBF) that the present invention proposes, (607,60,6) the frame error rate of QC-LDPC code, and the average number of iterations under the initial error bit rate of the graph. It can be seen from Fig. 2 that when the initial error bit number is 0.00375, under the AMBF algorithm, the frame error rate is 2×10 ^-4 , while the frame error rate of the decoding algorithm proposed by the present invention is 4×10 ^-5 , which is given by It can be seen that the LDPC code dynamic flip decoding algorithm suitable for packet parallel processing proposed by the present invention has better decoding performance. As can be seen from Figure 3, when the initial error bit number is higher than 0.00425, the average number of iterations of the decoding algorithm proposed by the present invention is higher than that of the AMBF decoding algorithm, but with the reduction of the initial error bit number, the average iteration number of the two algorithms The times are almost the same, indicating that the decoding algorithm proposed by the present invention will not greatly reduce the convergence speed of decoding.

To sum up, the decoding method proposed by the present invention eliminates the state cycle that exists in packet bit flip decoding, that is, when two adjacent check formulas are the same, iterative decoding falls into an error cycle and cannot effectively flip bits. Break out of state loops and get performance improvements. An LDPC code dynamic flip decoding method suitable for packet parallel processing proposed by the present invention, compared with the existing packet flip decoding algorithm, not only can obtain better decoding performance, but also can reduce delay, increase Decoding throughput, suitable for use on hardware systems with high latency requirements.

The above is only a preferred embodiment of the present invention, it should be pointed out that for those of ordinary skill in the art, without departing from the principle of the present invention, some improvements and modifications can also be made, and these improvements and modifications are also possible. It should be regarded as the protection scope of the present invention.

Claims (5)

1. A dynamic reverse decoding method of LDPC code by grouping parallel processing is characterized by comprising the following steps:

step 1, a check matrix H = [ H ] with LDPC code size of M multiplied by N _m,n ] _M×N Is initialized to a full zero row vector s with dimension M ⁰ ＝[s ₁ ,s ₂ ,…,s _M ] ⁰ ＝0 _M ，h _m，n Is the element of the mth row and the nth column of the check matrix, and the turning threshold is T _h ＝t ₀ The maximum number of bits allowed to flip per iteration is F _x ＝f ₀ Maximum number of iterations k _max Sequentially dividing the coded bits of length N into Q groups g ₁ ,g ₂ ,…,g _Q Wherein the first Q-1 packets have a bit length of

Last packet g _Q Has a bit length of L _Q ＝N-(Q-1)L ₁ Wherein L is ₁ Representing the bit length of the first packet, and performing hard decision on the received signal passing through the channel to obtain a hard decision bit sequence z with an initial length of N ¹ Entering iterative decoding when the iteration times k = 1;

step 2, obtaining ^k ＝z ^k *H ^T (mod 2) computing M syndromes, s, for the current iteration ^k ,z ^k Values, H, representing the check equation and the decoded sequence, respectively, for the kth iteration ^T Denotes the transpose of H, mod denotes the remainder function, if all are zero s ^k ＝0 _M Output the current codeword sequence z ^k Decoding is successful; otherwise, if k is less than or equal to k _max Performing iterative decoding step 3, if k>k _max If the decoding fails, ending the iterative decoding, wherein k represents the current iteration times;

step 3, grouping Q groups g ₁ ,g ₂ ,…,g _Q According to formula E respectively _n =∑ _m∈A(n) (2s _m -1) computing in parallel the flipping weights E of all bits _n N =1, \8230, N, where A (N) is the check formula set participated by the nth bit, h _m,n ＝1,m∈A(n)；

Step 4, grouping Q groups g ₁ ,g ₂ ,…,g _Q Finding in parallel a bit n with the largest flipping weight within each group _q ＝arg max{E _n’ ,n’∈g _q Q =1, \ 8230;, Q, resulting in a set of candidate flip bits k = { n } of size Q ₁ ,n ₂ ,…,n _Q }；

Step 5, checking a check formula sequence s in the current iteration process ^k Check-up sequence s with previous iteration ^k-1 Comparing and adjusting the threshold value;

step 6, in the candidate flip bit set kappa, further screening the flip weight reaching or exceeding the threshold T _h The bit of (d) yields the set k = { n "∈ k, E _n” ≥T _h }, set size N _κ Then, arranging the bits of the set k, and obtaining a new code word sequence z according to the arranged set k ^k+1 ；

And 7, adding one to the iteration times, wherein k = k +1, and executing a decoding step 2.

2. The dynamic reverse decoding method of LDPC code according to claim 1, wherein: the method for adjusting the threshold value in the step 5 comprises the following steps: if s ^k ＝s ^k-1 The threshold value is adjusted to be T _h ＝t ₁ The number of flip bits is F _x ＝f ₁ Otherwise T _h ＝t ₀ ,F _x ＝f ₀ 。

3. The dynamic reverse decoding method for LDPC codes according to claim 2, wherein: in step 6, a new codeword sequence z is obtained from the arranged set k ^k+1 The method comprises the following steps: number of bits N in the set k _κ ≥F _x Selecting the front F in the set k _x One bit n _i ,i＝1,…,F _x ,n _i E.g.. Kappa. }, for sequence z ^k Bit elements in corresponding positions are inverted, if the bit number N in the set k _κ <F _x Then sequence z is aligned according to all bits in set κ ^k Bit elements at corresponding positions in the code word sequence z are subjected to bit reversal to obtain a new code word sequence z ^k+1 。

4. The dynamic reverse decoding method of LDPC code according to claim 3 wherein: in step 6, the bits of the set κ are arranged according to the flipping weight.

5. The dynamic reverse decoding method of LDPC code according to claim 4 wherein: in step 6, the bits in the set κ are sorted in descending order according to the inversion weight.

Images