Research on encoding and decoding algorithms of non-binary LDPC code and FPGA implementation

Abstract

Low density parity check (LDPC) code is a kind of linear block code with excellent performance which is proposed by Dr. Gallager. It overcomes the shortcomings of other error correcting codes and it is the nearest channel code from Shannon limit at the present discover. The decoding algorithms of LDPC code can reduce the decoding delay by the parallel decoding structure, so this has caused great concern in many fields. In recent years more and more scholars begin to study LDPC code, this makes the coding and decoding algorithms of LDPC code improved continuously. LDPC code has been widely used in many fields such as optical fiber communication, digital watermarking, underwater communication and deep space communication because of its excellent performance. Non-binary LDPC code has better performance compared with binary LDPC code. In this paper, FFT-BP decoding algorithm of non-binary LDPC code is studied, and on this basis, we proposed an improved FFT-BP algorithm. The improved decoding algorithm can effectively reduce the average iteration number. Finally, we achieved encode and decode algorithm of non-binary LDPC code with FPGA.

Keywords

LDPC code decoding algorithms modelsim FPGA

1. Introduction

Low density parity check (LDPC) code [1] is a class of linear block code with good performance, and it is widely used in various fields. Studies on binary LDPC code has been quite common [2, 3, 4], but research shows that non-binary LDPC code has better performance. So, more and more scholars begin to study non-binary LDPC code. Non-binary LDPC code defined over GF (q), was investigated in 1998 by Davey and Mackay [5]. Non-binary LDPC code decoding algorithms are complex, which are not conducive to hardware implementation [6]. Nowadays, the research of non-binary LDPC code mainly focus on the simplification of decoding algorithms. In document [7], a method of constructing multivariate domain LDPC codes with large girth is introduced. This method is simple and can realize the unification of decoding performance and coding complexity. Document [8] uses Euclidean method to construct multivariate LDPC codes and is successfully used in MIMO systems. In document [9], a method based on external information transfer graph (EXIT) for designing multivariate domain LDPC codes is proposed and successfully applied to the Gauss channel. Document [10] introduces an efficient decoding algorithm, which combines the characteristics of the serial and parallel decoder, not only ensures the decoding speed, but also reduces the consumption of hardware resources. In document [11], a simplified SPA decoding algorithm for multivariate LDPC codes is given. The iterative form of the algorithm is similar to that of the two element domain. Compared with the regular SPA decoding algorithm, the decoding complexity of the algorithm is decreased. In document [12], a multivariate LDPC code Min-max adaptive decoding algorithm is proposed to reduce the complexity of Min-max decoding algorithm. Document [13] proposes a bubble detection (BC) algorithm to further reduce the complexity of the update of the check nodes in the EMS algorithm. In document [14], we analyze the likelihood ratio message oscillation characteristics in the multivariate LDPC code EMS algorithm, and propose a method to suppress the oscillation. The improved EMS algorithm can effectively improve the message convergence characteristics and reduce the iterative number of decoding. The [15] presents an improved multiple LDPC code FFT-BP decoding algorithm, the algorithm is used in the iterative process of stability and reliability of message transfer to adjust the variable nodes to check nodes outside the check node message, message received is more accurate so as to improve the performance of decoding algorithm. Document [16] introduces a hardware implementation structure of LDPC decoder on a domain. A multivariate LDPC decoder is designed in the literature [17], and the decoding throughput can reach 44.4 Mb/s at the clock frequency of 150 MHz. Declercq and Fossoier proposed an extended min-sum (EMS) decoding algorithm in 2007 [18]. Compared with the BP decoding algorithm, EMS has low complexity, but its performance has declined [19].

FFT-BP [20] decoding algorithm can reduce the complexity of algorithm by introducing Fast Fourier Transform (FFT), which uses multiplication operations to replace complex convolution operations. In order to improve the performance of FFT-BP algorithm further, we proposed an improved decoding algorithm. From perivous works, we know that the initial information before starting decoding is very important. We know that the noise in channel is the crucial factor on the initial information. Before being transmitted to the channel, by adding the decision bits at the intervals of the codeword after modulation, the accuracy of the initial information of the FFT-BP decoding algorithm is improved. Simulation results show that the improved decoding algorithm can effectively reduce the number of average iteration.

2. Improved FFT-BP decoding algorithm

Non-binary LDPC code uses the idea of belief propagation algorithm to perform iterative decoding [21, 22]. FFT-BP decoding algorithm of non-binary LDPC code improved check node update process on the basis of BP decoding algorithm. The complex convolution operations are transformed into multiplication operations by introducing FFT. The operations in GF (q) is the same except some opertations realted to check matrix which should follow rules in GF (q). In this section, we will introduce the FFT-BP decoding algorithm and its improved algorithm in detail. First, we define the meaning of some symbols. $q_{n}^{a,i}$ represents the probability of the nth symbol is $a$ . $R_{mn}^{a,i}$ represents the message of the check node $m$ passing to the variable node $n$ at the time of the $i$ iteration. $N(m)$ represents the collection of all variable nodes that participating in the mth check equation. Similarly, $M(n)$ represents the collection of all check nodes that the variable node $n$ participates in the check equations. The detailed steps of FFT-BP decoding algorithm for non-binary LDPC code are shown below.

(1)
Initialization process. Using Eq. (1) calculate initialization probability $q_{mn}^{a,0}$ .

$\displaystyle q_{mn}^{a,0}=f_{n}^{a}=\prod_{j=1}^{p}g_{n_{j}}^{s_{j}}$ (1)
(2)
Check nodes update process. Firstly, we can obtain $Q_{mn}^{a,i}$ by FFT operation from Eq. (2). Secondly, we can obtain $R_{mn}^{a,i}$ by IFFT operation in Eq. (3). It is important to note that the FFT operation in FFT-BP decoding algorithm is P-dimensional two-point operation [26].

$\displaystyle Q_{mn}^{a,i}=\textit{FFT}\left[q_{mn}^{0,(i-1)},q_{mn}^{1,(i-1)}% \ldots,q_{mn}^{(q-1),(i-1)}\right]$ (2) $\displaystyle R_{mn}^{a,i}=\textit{IFFT}\left[\prod\limits_{n^{\prime}\in N(m)% \backslash n}{Q_{mn^{\prime}}^{0,i}},\prod\limits_{n^{\prime}\in N(m)% \backslash n}{Q_{mn^{\prime}}^{1,i}}\ldots,\prod\limits_{n^{\prime}\in N(m)% \backslash n}{Q_{mn^{\prime}}^{(q-1),i}}\right]$ (3)
(3)
Variable nodes update process. We can calculate the information that the variable node passes to the check node by using Eq. (4). In the formula, $\alpha_{mn}$ is a normalization factor and it satisfies the equation $q_{mn}^{0,i}+q_{mn}^{1,i}+\ldots+q_{mn}^{(q-1),i}=1$ .

$\displaystyle q_{mn}^{a,i}=\alpha_{mn}f_{n}^{a}\prod\limits_{m^{\prime}\in M(n% )\backslash m}{R_{m^{\prime}n}^{a,i}}$ (4)
(4)
Codeword decision. Using the Eq. (5) to calculate $q_{n}^{a,i}$ and find the maximum of $q_{n}^{a,i}$ .

$\displaystyle q_{n}^{\alpha,i}=\alpha_{n}f_{n}^{a}\prod\limits_{m^{\prime}\in M% (n)}{R_{m^{\prime}n}^{a,i}}$ (5)

In the formula, $\alpha_{n}$ is a normalization factor and it satisfies the equation $q_{n}^{0,i}+q_{n}^{1,i}+\ldots+q_{n}^{(q-1),i}=1$ . The element corresponding to the maximum of $q_{n}^{a,i}$ is the value of the current symbol.
(5)
Decoding stop. When the decoding decision is complete, we can obtain the corresponding codeword. If the codeword satisfies $Hc^{T}=0$ or reaches the maximum number of iterations, that the decoding process is finished and output the current codeword. Otherwise, it should go back to step (2) and continue the iteration process.

The FFT-BP decoding algorithm of non-binary LDPC code has good performance and the complexity is lower than the BP decoding algorithm. In order to improve the decoding efficiency further, an improved FFT-BP decoding algorithm is proposed in this paper. From the previous chapter, we can see that the initial information obtained by the variable node from the channel has great influence on the decoding performance at the beginning of the decoding process. The first step of FFT-BP decoding algorithm is initialization, and initialization is to use the received codeword and channel characteristics to determine the prior probability of each symbol, and to use it as the initial value of the subsequent iterative decoding. The initialization of FFT-BP decoding algorithm for non-binary LDPC code shows that the channel noise variance $\sigma^{2}$ is an important factor in determining the accuracy of initialization information. Therefore, if we can estimate the noise variance $\sigma^{2}$ accurately, we can get more accurate initial information, so as to improve the decoding speed [25].

The method we employ is to insert an element in the GF (q) domain at the middle of the coded codeword as the decision bits. The sequence of codeword after adding the decision bits is transmitted in the channel after modulation, and the information transmitted may be wrong due to noise interference. After the receiver is demodulated, we can extract the decision bits and compare them with the decision bits sent by the sending end. At the receiving, after demodulation we can extract the decision bits and then compare with the decision bits sent by the sending. If the current decision bit is the same as the decision bit added at the sending, it is shown that the channel noise at this bit is smaller. Otherwise, the channel noise superimposed on this bit is larger. The channel noise is estimated by the change of these bit positions, and a more accurate channel noise variance model is built to initialize the FFT-BP decoding algorithm. We modeled the channel noise variance as follows:

$\displaystyle\sigma^{2}(n)=\frac{E_{b}}{2R\cdot E_{b}/N_{0}}\left[{1+\sum% \limits_{a=1}^{k}{x(a)e^{-\alpha(n-a\cdot\tau)^{2}}}}\right]^{2}$ (6)

In the formula, $k=\lfloor{N/\tau}\rfloor$ and $N$ is the code length. $R$ is bit rate and $\tau$ is the decision bit interval. By using Eq. (6) we can dynamic channel noise variance estimation. Plug this into the Eq. (1), we can calculate the posterior probability $f_{n}^{a}$ of each symbol, so as to improve the accuracy of the FFT-BP decoding algorithm of initial information. In order to verify the performance of the improved decoding algorithm, we perform simulation analysis on the FFT-BP decoding algorithm for non-binary LDPC code and an improved algorithm for adding decision bits. We select the LDPC code on the GF (4) field with code length 100 and code rate 0.5, and the modulation mode adopts QPSK modulation. The simulation results are shown in Fig. 1. As can be seen from the graph, when the SNR is 6.5 dB, to achieve convergence, the needed iteration times of improved FFT-BP decoding algorithm is 14.5, which is less than that of FFT-BP decoding algorithm 18. And we know that that the comlexity of decoding algorithm is the product of the complexity per iteration and the the number of iterations, so the complexity of the imroved FFT-BP decoding algorithm can be effectively reduced and the decoding efficiency is greatly improved. The proposed algorithm need less itertaion times than FFT-BP decoding algorithm at the same SNR, which means the former reaches convergence first than the latter,so the proposed algorithm owns better performance.

Figure 1.
The iteration diagram of FFT-BP decoding algorithm and its improved decoding algorithm.

3. FPGA implementation of encoder

Before designing multivariate LDPC code encoders, we first introduce the FPGA implementation of addition and multiplication in finite fields. Through the analysis of the upper section, we already know that if the data is expressed in exponential form, the finite field multiplication is relatively simple, but the addition operation is more complex. If it is expressed in vector form, it is simpler to add operations, but multiplication is more complicated. Considering the relatively large number of multiplications in the encoding process, we convert the data into exponential storage. In storage, we only need to store the exponential $l$ of the exponential form $\alpha^{l}$ . But considering the two elements of “0” and “1” in the exponential form, in order to avoid the confusion in the storage process, we stored “0” as “ $-$ 1”, and stored “1” as “0”. When we implement multiplication, we first judge whether the operands are “0” or “1”, because any number multiplied by zero is zero, and any number multiplied by 1 is the original number. The simulation waveforms of multiplication module in GF (8) domain are shown in Fig. 2.

Figure 2.

The simulation waveform of multiplication module in finite field.

Figure 3.

The simulation waveform of addition operation module in finite field.

Figure 4.

Simulation waveform of non-binary LDPC encoder.

First, we convert the two operands Gout and Iout into exponential form Gexout and Iexout to store them. Add the exponential sum to GFout, and then judge: If $\textit{GFout}<7$ gets the final exponent, GFindex is the value of GFout. If $\textit{GFout}\geqslant 7$ , the final exponent GFindex is the value of GFout to carry out the remainder operation of 7. Because it is more complex to use FPGA to implement remainder calculation and more hardware resources are consumed, so we use the look-up table method to achieve the remainder of this step. After getting the final index, we can get the result of the multiplier output by looking up the table Binout.

When designing addition modules, we need to note that any number plus 0 is invariant. The simulation waveform of addition operation module in GF (8) domain is shown in Fig. 3.

It can be seen from the simulation diagram that the exponential form is transformed into vector form in addition operation, and then bitwise XOR operation is performed. Finally, the result (vector form) obtained by bitwise XOR operation is transformed into the result of final adder output (decimal form). For example, the yellow line identifier in Fig. 3 calculates the sum of two elements “6” and “7” in a finite field. First, their corresponding index form of “5” and “6” into the corresponding vector form of “111” and “101” and then the bitwise XOR operation to extract the results for “010”, finally turned into the final decimal results for “2”.

Suppose the codeword after encoding is $c$ , then the $c$ can be computed by the Eq. (7).

$\displaystyle c=u\cdot G=[u_{1},u_{2},\ldots u_{k}]\left[{{\begin{array}[]{*{2% 0}c}{g_{11}}&{g_{12}}&{\ldots}&{g_{1n}}\\ {g_{21}}&{g_{22}}&{\ldots}&{g_{2n}}\\ \vdots&\vdots&\ddots&\vdots\\ {g_{k1}}&{g_{k2}}&\cdots&{g_{kn}}\\ \end{array}}}\right]=[v_{1},v_{2}\ldots v_{n}]$ (7)

In the formula, $u=[u_{1},u_{2},\ldots u_{k}]$ is the information vector and $G$ is the generating matrix. Next, we will introduce the FPGA implementation of the non-binary LDPC encoder in GF (8) domain. We transform all the elements in the generating matrix into exponential form and store the index in ROM.

(1)

Taking out the index of each element in the first row of the generating matrix and adding with the index of the first multivariate codeword. Then we translate the result into vector form and store it in FIFO.

(2)

Taking out the index of each element in the second row of the generating matrix and adding with the index of the second multivariate codeword. Translating the result into vector form and at the same time XOR operation is performed with the result of FIFO in step (1). Finally, we still store the result in FIFO.

(3)

Repeat the above operation until the k-1 times XOR operation is completed. Then the final encoding result is obtained by look-up table operation. In order to observe the output of coded codeword clearly, the length of the codeword we selected is shorter in the simulation process. The non-binary LDPC encoder simulation waveform is shown in Fig. 4.

The information vector is $u=[3,6,4,2,7]$ , and the generating matrix is:

$\displaystyle G=\left[{{\begin{array}[]{*{20}c}1&0&0&0&0&3&5&2&4&7\\ 0&1&0&0&0&2&4&1&3&6\\ 0&0&1&0&0&1&6&7&2&5\\ 0&0&0&1&0&2&7&5&3&2\\ 0&0&0&0&1&6&2&2&4&7\\ \end{array}}}\right]$ (8)

As can be seen from the simulation diagram, the result of the encoding of the information sequence is $c=[3,6,4,2,7,2,7,5,6,4]$ . Compared with the operation results, we can found that the output of this encoder is completely correct.

4. FPGA implementation of FFT-BP decoding algorithm

The design of non-binary LDPC decoder requires not only the speed of decoding but also the consumption of hardware resources. The fast decoding means the consumption of hardware resources is more, and the slower decoding speed means less consumption of hardware resources. Therefore, we should choose the appropriate method to achieve the non-binary LDPC decoder according to the specific requirements of the design. The LDPC decoder is mainly divided into three types: full serial decoder, full parallel decoder and partial parallel decoder. Compared with full parallel decoder, partial parallel decoder reduces the consumption of hardware resources, and improves the decoding speed compared with the full serial decoder. Therefore, some parallel decoders have solved the problem of decoding speed and hardware resource balance, and have been widely used in many fields. Considering the advantages of some parallel decoders, this paper adopts partial parallel architecture to design nonbinary LDPC codes.

The design of non-binary LDPC decoder requires not only the speed of decoding but also the consumption of hardware resources. The partial parallel decoder can solve the problem of the balance between decoding speed and hardware resources. So in this paper, we design the decoder with partial parallel architecture. The main control module is an important module of the non-binary LDPC decoder, which controls each module to do the corresponding operation according to the correct timing. The updating process of check nodes is the difficulties of design. Therefore, this paper describes the design of these two modules in detail.

(1)
Design of main control module:

The design of the main control module can be accomplished by a finite state machine (FSM). Its state transition diagram is shown in Fig. 5.

Figure 5.
The state transition diagram of main control module.

As you can see from the diagram, the design of the main control module contains 6 states and is idle at the beginning. The simulation waveform of main control module is shown in Fig. 6.

Figure 6.
The simulation waveform of main control module.

(2)
Design of updating module of check node:

The function of the check node update module is to update using the messages passed by the variable nodes, and store the updated data for updating the variable nodes. Below we detail the check node update module implementation steps.

1)
Read the address of the required variable node information during the update of the check node, and then read all the variable node information required by the current check node update according to the address. Since the non-binary LDPC codes we choose are (100, 3, 6) regular codes, each check node is connected to the 6 variable nodes. For example, the check node $m_{1}$ is connected to the variable node $n_{1},n_{7},n_{16},n_{37},n_{58},n_{62}$ . So it calculates the information that the check node $m_{1}$ passes to the variable node $n_{1}$ , and needs to read the information of the variable node $n_{7},n_{16},n_{37},n_{58},n_{62}$ (quantization to 8 bit).
2)
The information of each variable node after reading is transformed into ET (equivalent) transformation [23] and three-dimensional two-point FFT transform. That is the 8 probabilities of taking 0 $\sim$ 7 for each variable node are three-dimensional two-point FFT transform. Then, the transformed data is multiplied by point by step in frequency domain.
3)
The results after the multiplication perform the IFFT transform first, and then the IET transform is performed. The transformed results are normalized so that the probability of each variable node taking 0 $\sim$ 7 is added to $2^{8}-1$ . Finally, the results are stored in the check nodes information store RAM for updating the next variable nodes.

5. Conclusions

In this paper, we studied the encoding and decoding algorithm of non-binary LDPC code mainly. And on this basis, we proposed an improved FFT-BP decoding algorithm. By the simulation of MATLAB we can know that the improved decoding algorithm could effectively reduce the average iteration number. We also implemented non-binary LDPC encoder and decoder by using FPGA in the GF (8) domain by QuartusII software. The compliation and synthesis result shows that the generated circuit consumes logical resource by 76% and memory resource by 56%. The simulation of modelsim indicates that the improved FFT-BP decoding algorithm can effectively improve the decoding performance.

References

Gallager

R.G.

, Low density parity check codes, IRE Transactions on Information Theory 8(1) (1962), 21–28.

Wang

Qian

and Wu

, A development overview of the concatenation system based on LDPC codes and Polar codes, Journal of China University of Metrology 29(2) (2018), 169–173.

, The applied overview and the theory of LDPC codes, New Technology 2012(9), 25–33.

Liu

, The technology overview of LDPC codes in communication system, Electronics World 2016(19), 34–35.

Davey

and MacKay

, Low-density parity check codes over GF (q), IEEE Communications Letters 2(6) (1998), 165–167.

Lin

and Yan

, An efficient fully parallel decoder architecture for nonbinary LDPC codes, IEEE Transactions on Very Large Scale Integration Systems 22(12) (2014), 2649–2660.

Huang

and Zhao

, A construction method of nonbinary LDPC codes with large girth, Computer and Digital Engineering 55(1) (2011), 28–30.

Huang

Zhou

and Willett

, Nonbinary LDPC Coding for Multicarrier Underwater Acoustic Communications, in: IEEE International Conf. on OCEANS, April. 2008, pp. 1–6.

Byers

G.J.

and Takawira

, EXIT Charts for Non-binary LDPC Codes, in: IEEE International Conf. on ICC, Vol. 1, May. 2005, pp. 652–657.

10.

Zhang

and Cai

, Efficient partial-parallel decoder architecture for quasi-cyclic nonbinary LDPC codes, IEEE Transactions on Circuits and System 58(2) (2011), 402–414.

11.

Liu

and Bu

, A Simplified Decoding Algorithm for Nonbinary LDPC Codes, in: IEEE Fourth International Conf. on ChinaCOM, Aug. 2009, pp. 1–5.

12.

Chen

and Xie

, Min-max adaptive decoding algorithm for multivariate LDPC codes, TV Technology 40(4) (2016), 85–89.

13.

Boutillon

and Conde-Canencia

, Simplified Check Node Processing in Nonbinary LDPC decoder, in: Proc. IEEE Int. Symp. Turbo Codes Iterative Information Processing, Sep. 2010, pp. 201–205.

14.

Wen

and Zhang

, Research on simplified decoding algorithm of LDPC codes in multivariate domain, Journal of Southwestern Normal University (NATURAL SCIENCE EDITION) 38(10) (2013), 147–154.

15.

Zhang

and Xu

, An improved decoding algorithm for nonbinary LDPC codes, Wireless Communication Technology 42(6) (2016), 56–58.

16.

Spagnol

Marnane

and Popovici

, FPGA Implementations of LDPC over GF (q) Decoders, in: IEEE Workshop on Signal Proc. Sys. (Institute of Electrical and Electronics Engineers, Shanghai, China, 2007), April. 2007, pp. 273–278.

17.

Voicila

Declercq

Verdier

et al., Architecture of a low-complexity non-binary LDPC Decoder, in: IEEE International Conf. on ICCE, Jan. 2008, pp. 1–2.

18.

Declercq

and Fossorier

, Decoding algorithms for nonbinary LDPC codes over GF (q), IEEE Trans Commun 55(4) (2007), 633–643.

19.

Lin

and Yan

Z.Y.

, Efficient shuffled decoder architecture for nonbinary quasi-cyclic LDPC codes, IEEE Transactions on Very Large Scale Integration (VLSI) Systems 21(9) (2013), 1756–1761.

20.

Barnault

and Declercq

, Fast decoding algorithm for LDPC over GF (q), in: IEEE Inform. Theory Workshop’2003, Paris, France, March 2003.

21.

McEliece

MacKay

and Cheng

, Turbo decoding as an instance of Pearl’s “belief propagation” algorithm, Selected Areas in Communications IEEE Journal on 16(2) (1998), 140–152.

22.

Kschischang

and Frey

, Iterative decoding of compound codes by probability propagation in graphical models, IEEE Journal on Selected Areas in Communications 16(2) (1998), 219–230.

23.

MacKay

, Good error-correcting codes based on very sparse matrices, IEEE Transactions on Information Theory 45(2) (1999), 399–431.

24.

Lan

and Zeng

L.Q.

, Constructions of Quasi-cyclic LDPC codes for the AWANG and binary erasure channels based on finite fields and affine mappings, in: International Symposium on Information Theory, 2005, pp. 2285–2289.

25.

Zhang

et al., Performance analysis of LDPC code based on watermark scheme in high-speed optical communication system, Chinese Optics Letters 13(S1) (2015), S10601.

26.

and Soleymani

M.R.

, A proof of the Hadamard transform decoding of the belief propagation algorithm for LDPC over GF (q), in: IEEE 60𝑡ℎ Vehicular Technology Conference, Los Angeles, USA, 2004(9), pp. 2518–2519.