ABSTRACT

In order to solve the problem that the original decoding algorithm of multi-band LDPC codes is high and is not conducive to hardware implementation, two simplified decoding algorithms for multi-band LDPC codes are studied: the reliability propagation based on fast Fourier transform Code algorithm (FFT-BP) and log-BP decoding algorithm based on logarithmic operations. The simulation results show that the FFT-BP decoding algorithm is more convenient and efficient.

Keywords:

LDPC, FFT-BP, BP

1. Introduction

Multicomponent coding is the key technology of multivariate wireless transmission, and its core lies in multivariate codec. Most of the current multi-code modulation using multiple LDPC code, multi-LDPC code was first proposed by Gallager, 1998 Davey and MacKay studied the finite field of multiple LDPC code. Compared with the binary LDPC code, the main advantages of multiple LDPC codes are reflected in the following aspects: 1) better error correction performance: multiple LDPC code will be a number of bits into a multi-symbol, which has the potential of eliminating LDPC code small ring of binary map and getting better error correction performance; 2) Strong anti-burst error capability: Because of Multiple LDPC codes making multiple burst bit errors can be combined into fewer multi-symbol errors, the error correction performance is better than binary LDPC codes; 3) Suitable for high-speed transmission: Based on high-or- der finite-domain multivariate LDPC codes are designed and are well suited for combining high-order modulation schemes with multi-antenna systems to provide higher data rates and spectral efficiency. It can be seen that multi-LDPC coding and modulation technology is more suitable for wireless channel transmission [1].

2. Multivariate LDPC Coding Algorithm

2.1. Definition and Operation of Finite Field GF (q) Domain

Field F is a set of elements that define two operations, plus “+” and multiplication “ ”and both of which satisfy the law of union, distribution law, and exchange law, both of these operations are closed [2], that is, for any, there are:

If there is a domain F which has only a finite number of q elements, then the domain is called a finite field, or Galois Filed, denoted as GF (q). There is a finite field GF (q) only if q is a power of prime number, the extended domain GF () can be constructed according to the base domain GF (p) domain. The extension field GF () of the binary domain GF (2), where any of the nonzero elements can be expressed by the power of. In the infinite set of elements, the elements are generated according to element set

(2-1)

The last element in the field is obtained by multiplying the previous element. The domain F must be conditional so that the domain can contain only element to get the GF () field. The multiplicative closure of domain F can be represented by an irreducible polynomial (2-2), that is:

(2-2)

Then. According to the polynomial constraint, any element whose power is greater than or equal to is reduced to an element whose power is less than, that is:

(2-3)

So the elements of the finite field GF () are:

(2-4)

2.2. Construction of Multiple LDPC Codes

The multi-band LDPC code defined on the finite field GF (q), which evaluates the value of the nonzero element in the matrix H on the GF (q), Where q is a prime or prime power, which is constructed in a manner similar to that of a binary construct, requiring the following characteristics when constructing a rule sparse check matrix H:

1) Row weight p, column weight q, p and q are very small with respect to m and n.

2) In H, any two rows and two columns of the corresponding position on the same non-zero elements no more than one.

The irregular polygon LDPC codes p and q are not fixed. The second row constraint ensures that the constructed parity check matrix has no four rings on its Tanner graph [3], thereby further improving its coding performance. And for the multi-band LDPC codes, there is a fixed relationship between the symbol symbols and the bits relative to the binary code of the same length, so that it has not only good ability to correct random errors, but also has a good Correct the performance of sudden errors. In the literature [4], it is shown that the LDPC codes with better short and medium length have better potential performance. Similar to the construction of binary LDPC parity check matrix, the construction of LDPC parity check matrix is divided into two categories: One is the random construction method; the second is the algebraic construction method. The first class of construction methods, mainly divided into Gallger structure method, PEG construction method, Bit-filling, Mackey structure method [5] four kinds of algorithms. The Gallger construction method and the Mackey construction method are mainly applied to the construction of regular LDPC codes, while the other two can be used to construct irregular LDPC codes. In the design of the LDPC code, it is the premise of the random construction method to know the distribution of the check node and the variable node. The distribution is generally obtained by EXIT, density evolution or Gaussian approximation. Although the LDPC codes constructed by the random method have strong randomness and good progress, the parity check matrix has no regularity, and the coding and hardware implementation are high in complexity. Generally, this kind of construction is not adopted.

Compared with the random construction method, LDPC codes constructed by combinatorial and algebraic methods have little difference in performance loss and low hardware implementation. The algebraic construction method with the theoretical research value is composed of the LDPC code and the quasi-cyclic LDPC codes with quasi-cyclic algebra structure proposed by Tanner and Fossorier et al., however, the parameters of the algebraic structure of the regular LDPC code length, bit rate and other parameters of the selectivity is not strong, cannot be pre-set code length and bit rate, which can be based on these parity check matrix itself to determine the code length and bit rate and other parameters. On the basis of Tanne and Fossorier et al., Lin S. propose a method for constructing quasi-cyclic LDPC codes based on finite field GF (q) and affine mapping [6].

For multivariate QC-LDPC coding, since the generation matrix of multiple LDPC codes and binary LDPC is similar in construction, therefore, according to the construction of binary QC-LDPC, and each sub-matrix is independent, it is only necessary to obtain the generator in its generation matrix G, which can be encoded in serial or parallel way.

The information sequence is denoted as, where represents the symbols contained in the segment. After encoding it, we can get the encoded codeword sequence, then the code after the paragraph of the parity bit code is:

3. Multivariate LDPC Decoding Algorithm

At present, the practical implementation of multi-band LDPC code coding structure is no longer difficult, but the multi-band LDPC decoding of the highly complex problem has not been a very good solution. Davey and MacKay put forward the classic belief transmission (Belief Propagation, BP), the core idea is to pass the Tanner map to probability information [7], will be divided into check node and variable node update two processes. However, compared with the binary, multi-LDPC code encoding process is based on GF (q) domain, thus, the elements that are passed between every two nodes in the Tanner graph are no longer only “0” or “1”, but are , they cannot be expressed directly in a connected way, instead of adding to the replacement node. As shown in Figure 1.

3.1. Multiple BP Decoding Algorithm

Binary and multivariate LDPC codes can adopt BP decoding algorithm, but the two are slightly different in the process, in which the multiple BP decoding algorithm has message replacement and inverse permutation process. In the decoding process, we must first calculate the initial probability information, in practice, usually among the multi-band values are independent of each other, therefore, an element on the GF (q) () field can be repre- sented by a b-bit binary sequence, there is a relationship between the initial probability information of the binary and multivariate () LDPC codes [9]:

(3-1)

Among them, , is the probability of the q corresponding, , is the binary probability of taking. For, according to the channel conditions and modulation methods, the value is different.

The decoding process of multiple LDPC codes can be summarized as follows:

1) Initialization: The variable node initial channel probability probability:

(3-2)

2) Information replacement: Unlike binary LDPC code BP decoding, it is necessary to transpose the variable node information sequence. The rule is that the value of each variable in the information sequence is multiplied by (Non-zero elements in row and column of the parity check matrix), the multiplication of is in the GF (q) field, which is equivalent to a permutation of the transmitted information. Similarly, the way reversal is similar.

(3-3)

3) Check node update: Check the node information according to the full probability formula can be expanded to the following formula:

(3-4)

where represents the set of vectors satisfying the math parity equation.

4) Replacement: This process is the inverse of the check node transfer message and the parameter (the row and the column in the parity check matrix), and the reverse of the process (2):

(3-5)

5) Variable Node Update: After the transcoding of the check node information by the process (4), the new check sequence is obtained. According to the Bayesian formula,

(3-6)

In order for equation to be established, the introduction coeffi-

cient completes the normalization of the equation.

6) Posterior probability of the calculation, the decision:

(3-7)

The decision to use the information from the information and outside the information, rather than the variable node update, just update the external information.

Perform a hard decision expression:

(3-8)

Selecting the highest codeword as the decision codeword, and finally obtaining, If the equation is satisfied, the decoding can be ended, otherwise the operation (2) is continued until the equation is established or the iteration is reached.

3.2. FFT-BP Decoding Algorithm

In the traditional BP decode algorithm, the check node update process uses many addition and multiplication operations. In the hardware implementation, it will seriously consume the logic resources, which will affect the practical application to a large extent. (3)-(4) can be regarded as convolution in the BP decoding algorithm, and the algorithm is optimized for this performance. A decoding algorithm is proposed, in the process of decoding iterations, fast Fourier transform (Fast Fourier Transform) is introduced to transform the convolution of the time domain into the product of the frequency domain [10], thus simplifying the process (3), while the other process does not change, the complexity. Since the operation in the multivariate BP decoding algorithm process (3) is based on the GF (q) domain (), when the FFT operation is used, it becomes a b-dimensional 2-point FFT operation. In the GF (4) domain, that is, (b = 2) has a 2-dimensional 2-point FFT operation, the expression is:

(3-9)

When GF (4), the corresponding butterfly chart as shown in Figure 2.

The initialization process in the decoding algorithm is the same as the BP decoding algorithm. The iterative decoding steps are as follows:

1) FFT transforms the information variables to obtain intermediate values

(3-10)

2) Make accumulate operations according to the following formula:

(3-11)

3) Transform the results obtained by the above formula:

(3-12)

Due to the fast Fourier transform introduced in the decoding algorithm, the convolution of the time domain becomes the product of the frequency domain, which simplifies the updating process of the check node to a certain extent, Compared with the decoding algorithm, the complexity of the decoding algorithm is reduced, but it can be seen from Equation (3)-(12) whether a lot of multiplication is required, so it need to use a large number of multipliers, and high precision for data accuracy, in the hardware implementation, still need to take up more hardware resources.

4. Simulation Analysis

The FFT-BP decoding algorithm is based on the traditional BP decoding algorithm, and the fast Fourier transform algorithm is used to replace the convolution operation in the variable node updating process of the BP decoding algorithm, reducing the amount of computation and speeding up the decoding rate. At the same time, compared with the traditional BP decoding algorithm, because of the use of fewer multipliers, so the hardware is also more convenient to achieve, improve the hardware resource utilization. The simulation results are shown in Figure 3:

It can be seen from the simulation results that the multivariate BP decoding algorithm and the FFT-BP decoding algorithm are simplified by the fast Fourier transform performance and simplification of the operation due to the same information probabilistic initialization method. The performance of the decoding algorithm is the same, but the FFT-BP decoding algorithm is more convenient and efficient.

Acknowledgements

This paper is funded by the International Exchange Program of Harbin Engineering University for Innovation Oriented Talents Cultivation, International Science & Technology Cooperation Program of China (2014 DFR10240), National Nature Science Foundation of China (No. 61401115), National Natural

Science Foundation of China (No. 61301095), National Natural Science Foundation of China (No. 61671167), China Postdoctoral Science Foundation (2013- T60346), Harbin Science and Technology Research Projects (P083313026), Natural Science Foundation of Heilongjiang Province (P083014025).

Cite this paper

Wei, X., Li, Z.G. and Dou, Z. (2017) Simulation Analysis of Multiple BP Decoding Algorithm and FFT-BP Decoding Algorithm. Int. J. Communications, Network and System Sciences, 10, 255-262. https://doi.org/10.4236/ijcns.2017.108B027

References