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.
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.
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.
Initialization process. Using Eq. (1) calculate initialization probability
Check nodes update process. Firstly, we can obtain
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,
Codeword decision. Using the Eq. (5) to calculate
In the formula, Decoding stop. When the decoding decision is complete, we can obtain the corresponding codeword. If the codeword satisfies
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
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:
In the formula,
The iteration diagram of FFT-BP decoding algorithm and its improved decoding algorithm.
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
The simulation waveform of multiplication module in finite field.
The simulation waveform of addition operation module in finite field.
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
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
In the formula,
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. 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. 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
As can be seen from the simulation diagram, the result of the encoding of the information sequence is
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.
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.
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.
The simulation waveform of main control module. 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.
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 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 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


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.
