- This paper presents a study on the VHDL implementation of a class of binary irregular structured LDPC codes (IS-LDPC) applied to 100 Gbps optical networks. A comparison between two iterative decoding algorithms for irregular structured LDPC codes, sum-product based on loglikelihood ratio and min-sum, is used to define the best choice for implementation. The performances of IS-LDPC codes are evaluated on an AWGN channel. The aim of this paper is to select out of a class IS-LDPC codes those ones with the best performance using the MS algorithm for VHDL implementation.
I. INTRODUCTION
The increasing traffic in optical telecommunication networks
has demanded links with even higher transmission rates.
However, higher rates mean more noise and interference
introduced by optical and electronic devices [
LDPC codes can achieve near optimum Shannon limit performance over the additive white Gaussian noise (AWGN) channel [8]. The sparseness of 1's in the binary parity check matrix H makes the iterative decoding particularly attractive. The iterative decoding of LDPC codes allows a high degree of parallelism, which makes it suitable for high data rate communications.
Iterative decoding algorithms for LDPC codes are bounded by a trade-off between decoding performance, in terms of bit error rate (BER), and implementation complexity. Moreover, the performance varies with the length and the structure of the parity check matrix of the LDPC codes.
Among of the iterative decoding algorithms, the sumproduct (SP) algorithm achieves the best performance however it demands a high hardware complexity. An alternative is the min-sum (MS) algorithm that significantly reduces the implementation complexity at a cost of acceptable performance degradation. The complex computations at the check nodes are approximated to simple comparison and summation operations in the MS algorithm [7].
In general, LDPC codes can be categorized into regular and irregular codes. An LDPC code is regular if the weights of rows and columns in its parity check matrix are equal, otherwise it is irregular. Irregular LDPC codes have better performance than regular ones.
The aim of this paper is to select out of a class of irregular structured (IS) LDPC codes those ones with the best performance using the MS algorithm. The log-SP decoding algorithm is used as reference for the sake of performance comparison. The MS algorithm presents lower complexity for VHDL implementation than the log-SP decoding algorithm [7]. The IS-LDPC codes were designed to match with the specifications of the 100 Gbps optical networks.
The binary irregular structured (n, k) LDPC codes are built
using a parity check matrix H generated by grouping circulant
sub-matrices [
Let Np be the set of the natural prime numbers. This set can
be used to generate circulant sub-matrices that compose the
parity check matrix H. For instance, fig. 2 shows a matrix H
for a (32, 16) irregular structured code. Notice that H is in the
systematic form = !!! ] where P is a parity sub-matrix
built by grouping four circulant sub-matrixes defined by the
Copyright © 2015 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and
copyrighted by its editors. Latin American Workshop On Communications' 2015 Arequipa, Peru Published on CEUR-WS: http://ceur-ws.org/Vol-1538/
first four elements of Np. This matrix H provides a fast
encoding process [
Notice that Im is used to generate the circulant sub-matrixes Cm,j of P, whereas In-k is related to the systematic part of H.
III. ITERATIVE DECODING PROCESS Tanner graph is a graphic representation of the parity check matrix H of a LDPC code. This graph is composite of two sets of nodes: variable nodes vi and check nodes cj. There is a connection between vi and cj when the entry hij of the matrix H is equal to 1.
The log-SP algorithm is a well-known decoding algorithm for LDPC codes. It operates on the Tanner graph representation of the parity check matrix of a code. The most straightforward variant of the log-SP algorithm is the a posteriori probability (APP) decoding. A simplified version of the log-SP algorithm is the MS or maximum-likelihood sequence detection (MLSD). The iterative decoding process is illustrated in fig. 3. However, before describing the steps of the decoding algorithm, it is convenient to set some definitions: (!): intrinsic information received by the decoder. (!"): message evaluated by the check node ! and sent to
the variable node !. (!"):message evaluated by the variable node ! and sent to
the check node !. !: !\!: ! : variable nodes connected to the check node !. variable nodes connected to the check node ! with exception of the variable node !.
check nodes connected to the variable node ! !\!: check nodes connected to the variable node ! with exception of the check node !.
The log-SP decoding algorithm is divided into the following steps [8]: a) Initialization: the intrinsic message ! = 2!/! is evaluated where ! is the received signal and ! is the variance of the AWGN (additive white Gaussian noise) channel. b) Horizontal step: each check node then sends to the variable nodes its new probabilities of 0 and 1, which are evaluated from the probabilities received from the variable nodes, excluding the check node that is going to receive that probabilities. The probabilities are evaluated by (1) (2) (3) where !" = !!∈!!\! !!!. ( !!!!!\! ( !!!)), = − log ℎ 2
!!!! = log (!!!!). c) Vertical step: each variable node sends to its connected check nodes the probabilities of 0 and 1. New probabilities are evaluated by summing the received probabilities from the check nodes, excluding the probabilities of the check node that is going to receive them. The new probabilities are evaluated by !" = ! + !!∈!!\! (!!!). d) Syndrome: after horizontal and vertical steps, each entry of the codeword c is updated using ! = ! + !∈!! (!") and ! = 1 if ! < 0 0 otherwise.
The syndrome is then evaluated and if it is a null vector the decoding process stops and the information is recovered.
Otherwise the process continues until the number of iterations set by the algorithm is reached.
When the log-SP decoding algorithm is implemented in VHDL, the vertical step consumes the greatest amount of logical elements. This happens because it is necessary to perform logarithmic operations to evaluate Φ(x). The function Φ(x) can be implemented in VHDL by lookup tables.
However, if the H matrix has a greater number of 1’s the number of lookup tables can be prohibitive. Notice that it is necessary a lookup table for each hij = 1 of the parity check matrix H of a LDPC code.
An alternative to the log-SP algorithm to reduce the number of logical elements is the MS decoding process. The vertical step of the MS algorithm is simplified by evaluating the minimum values of probabilities from the check nodes. Let !" = sgn((!")) and !" = abs((!")), then Φ(x) can be evaluated by the following approximation [4] (4) (5) !! !!! ≈ min!! !!!
= min!!!!!\! !!!.
This simplifies the evaluation of !" to !" =
!!!!!\! !!!. min!!!!!\! !!!.
Therefore there is no need of lookup tables for the MS decoding algorithm. Notice also that there is no need of knowing the channel characteristics [7], i.e., the initialization of the algorithm can be made by !" = ! .
IV. RESULTS The IS-LDPC codes are designed to operate at 100 Gbs optical networks. Therefore, the encoding and decoding algorithms of the (2000, 1000) and (4000, 2000) IS-LDPC codes should operate at the frequencies of 50 MHz and 25 MHz, respectively, for the VHDL implementation. The performances of the codes are analyzed on an additive white Gaussian noise (AWGN) channel, which is considered a good statistical model for the impairments found in an optical network. Then the goal of this work is to adjust the dimension of the parent identity matrix Im that generates the IS-LDPC code to narrow the performance gap between log-SP and MS decoding algorithms.
For instance, four (2000, 1000) IS-LDPC codes are built using circulant sub-matrixes generated by different-size parent identity matrixes (I50, I100, I200 and I500) to find that with the best MS decoding performance.
A. (2000, 1000) IS-LDPC codes Figures 4 to 7 show the performance, in terms of bit error rate (BER) versus energy per bit/unilateral noise power spectral density (Eb/N0), of the (2000, 1000) IS-LDPC using log-SP and MS decoding schemes. Each code is decoded using five iterations. Four codes were implemented using parent identity matrixes with dimension values: 50, 100, 200 and 500.
Finally, fig. 7 presents an IS-LDPC code built with an identity matrix of dimension equal to 500. The decoding performances for both algorithms are almost coincident. The difference in performance is smaller than 0.1 dB between log
SP and MS algorithms, for a BER = 10-4.
Notice that by increasing the dimension of the parent identity matrix the performances of the log-SP and MS decoding algorithm become closer and closer. Further the increase in dimension reduces the number of 1's in H, which reduces the VHDL implementation complexity. Notice also that the (2000, 1000) IS-LDPC code generated by I50 presents the best performance for MS decoding algorithm. However, this code has more branches between variable and check nodes than the others.
B. (4000, 2000) IS-LDPC codes Figures 8 to 12 show the performance, in terms of BER versus Eb/N0, for the (4000, 2000) IS-LDPC codes using log-SP and MS decoding algorithms. Again each code is decoded using five iterations. Five codes were implemented using parent identity matrixes with dimension values: 50, 100, 200, 500 and 1000.
Fig. 8 shows the performance of a (4000, 2000) IS-LDPC code with identity matrix with dimension 50. The log-SP algorithm presents around 1 dB gain over the MS algorithm for BER = 10-3.
Fig. 9 presents the performance curves for the IS-LDPC code using an identity matrix of dimension 100. The algorithm log-SP performs 1.3 dB, in terms of Eb/N0, better than the MS algorithm, for BER = 10-4.
Finally, fig. 12 presents an IS-LDPC code built with an identity matrix of dimension equal to 1000. The decoding performances for both algorithms are coincident.
Again, the performance gap between the log-SP and MS decoding algorithm narrows when the dimension of the parent identity matrix increases. Therefore, the (4000, 2000) IS LDPC codes using parent identity matrixes with dimension 500 and 1000 present the lowest VHDL implementation complexity.
V. CONCLUSION The class of IS-LDPC codes can be generated in an easy and direct way. Moreover, its parity check matrix structure reduces the iterative decoding complexity and as consequence it reduces also the VHDL implementation complexity.
As expected the sum-product decoding algorithm performs always better than the min-sum algorithm. However, a decrease in performance around 0.2 dB by using the MS decoding algorithm instead of log-SP algorithm is very reasonable, because the MS algorithm provides a significant reduction in the number of logical elements in FPGA and VHDL implementations.
For the (2000, 1000) IS-LDPC codes, the code built with the parent identity matrix of dimension 500 is under the 0.2 dB log-SP/MS performance threshold. On the other hand, for the (4000, 2000) IS-LDPC codes, the codes built with parent identity matrix of dimension 500 and 1000 have very close performance for both decoding algorithms and they are also under the 0.2 dB threshold. Therefore, those codes present lower complexity for VHDL implementation. Notice that the decoding performances between log-SP and MS algorithms are very close for codes with the parent identity matrix with high dimension.
ACKNOWLEDGEMENTS This work was partially supported by FAPESP under contract nº. 2012/01789-4.