7th Latin American Workshop On Communications - 2015 A Study on VHDL Implementation of a Class of Irregular Structured LDPC Codes applied to 100 Gbps Optical Networks AntΓ΄nio Unias de Lucena Renato Baldini Filho DECOM-FEEC-UNICAMP Av. Albert Einstein, 400 13083-852 Campinas – SP -Brazil antoniounias@gmail.com Abstract - This paper presents a study on the VHDL In general, LDPC codes can be categorized into regular and implementation of a class of binary irregular structured LDPC irregular codes. An LDPC code is regular if the weights of codes (IS-LDPC) applied to 100 Gbps optical networks. A rows and columns in its parity check matrix are equal, comparison between two iterative decoding algorithms for irregular structured LDPC codes, sum-product based on log- otherwise it is irregular. Irregular LDPC codes have better likelihood ratio and min-sum, is used to define the best choice for performance than regular ones. implementation. The performances of IS-LDPC codes are The aim of this paper is to select out of a class of irregular 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 structured (IS) LDPC codes those ones with the best performance using the MS algorithm for VHDL implementation. performance using the MS algorithm. The log-SP decoding algorithm is used as reference for the sake of performance Index Terms - LDPC codes; optical networks; VHDL. comparison. The MS algorithm presents lower complexity for I. INTRODUCTION VHDL implementation than the log-SP decoding algorithm [7]. The IS-LDPC codes were designed to match with the The increasing traffic in optical telecommunication networks specifications of the 100 Gbps optical networks. has demanded links with even higher transmission rates. However, higher rates mean more noise and interference II. IRREGULAR STRUCTURED LDPC CODES introduced by optical and electronic devices [1]. Efficient The binary irregular structured (n, k) LDPC codes are built channel coding schemes, such as, low-density parity-check using a parity check matrix H generated by grouping circulant (LDPC) and turbo codes, have been devised to overcome sub-matrices [2],[3]. Both code and the information lengths those sources of errors [1],[2],[3],[4],[5],[6]. are denoted by n and k, respectively. A circulant matrix is LDPC codes can achieve near optimum Shannon limit generated by successive shifts of the first row (column) of a performance over the additive white Gaussian noise (AWGN) parent identity matrix Im to obtain the following rows channel [8]. The sparseness of 1's in the binary parity check (columns). Fig. 1 shows two examples of circulant matrices matrix H makes the iterative decoding particularly attractive. C8,j obtained from the parent identity matrix I8. The index j The iterative decoding of LDPC codes allows a high degree of indicates the initial shift to the right of the first row of the parallelism, which makes it suitable for high data rate identity matrix. 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 sum- Fig.1 Circulant matrices obtained from I8. product (SP) algorithm achieves the best performance Let Np be the set of the natural prime numbers. This set can however it demands a high hardware complexity. An be used to generate circulant sub-matrices that compose the alternative is the min-sum (MS) algorithm that significantly parity check matrix H. For instance, fig. 2 shows a matrix H reduces the implementation complexity at a cost of acceptable for a (32, 16) irregular structured code. Notice that H is in the performance degradation. The complex computations at the systematic form 𝐇 = 𝐈!!!  𝐏] where P is a parity sub-matrix check nodes are approximated to simple comparison and built by grouping four circulant sub-matrixes defined by the summation operations in the MS algorithm [7]. 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 [2]. The square null sub-matrix 𝐎! has dimension 8. Fig. 2 Parity check matrix H for the (32,16) irregular structured code. 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 Fig. 3 Decoding fluxogram for a LDPC code. connection between vi Β and cj when the entry hij of the matrix H The log-SP decoding algorithm is divided into the is equal to 1. following steps [8]: The log-SP algorithm is a well-known decoding algorithm a) Initialization: the intrinsic message 𝐿 𝑐! = Β 2𝑦! /𝜎 ! Β  is for LDPC codes. It operates on the Tanner graph evaluated where 𝑦! is the received signal and 𝜎 ! Β  is the representation of the parity check matrix of a code. The most variance of the AWGN (additive white Gaussian noise) straightforward variant of the log-SP algorithm is the a channel. posteriori probability (APP) decoding. A simplified version of the log-SP algorithm is the MS or maximum-likelihood b) Horizontal step: each check node then sends to the variable sequence detection (MLSD). The iterative decoding process is nodes its new probabilities of 0 and 1, which are evaluated illustrated in fig. 3. However, before describing the steps of from the probabilities received from the variable nodes, the decoding algorithm, it is convenient to set some excluding the check node that is going to receive that definitions: probabilities. The probabilities are evaluated by 𝐿(𝑐! ): intrinsic information received by the decoder. 𝐿 π‘Ÿ!" = Β  !!∈!!\! 𝛼! ! ! . 𝛷( ! ! !!!\! 𝛷( 𝛽! ! ! )), (1) 𝐿(π‘Ÿ!" ): message evaluated by the check node 𝑐! and sent to where the variable node 𝑣! . ! ! !! 𝛷 π‘₯ = Β  βˆ’ log π‘‘π‘Žπ‘›β„Ž π‘₯ 2 = log Β ( ! ) 𝐿(π‘ž!" ):message evaluated by the variable node 𝑣! and sent to ! !! . (2) the check node 𝑐! . c) Vertical step: each variable node sends to its connected 𝑉! : variable nodes connected to the check node 𝑐! . check nodes the probabilities of 0 and 1. New probabilities are evaluated by summing the received probabilities from the 𝑉!\! : variable nodes connected to the check node 𝑐! with check nodes, excluding the probabilities of the check node that exception of the variable node 𝑣! . is going to receive them. The new probabilities are evaluated by 𝐿 π‘ž!" = 𝐿 𝑐! + Β  ! !∈!!\! 𝐿(π‘Ÿ!!! ). 𝐢! : check nodes connected to the variable node 𝑣! 𝐢!\! : check nodes connected to the variable node 𝑣! with d) Syndrome: after horizontal and vertical steps, each entry of exception of the check node 𝑐! . the codeword c is updated using 𝐿 𝑄! = 𝐿 𝑐! + Β  !∈!! 𝐿(π‘Ÿ!" ) and 1 Β  Β if Β   𝐿 𝑄! < 0 Β  𝑐! = 0 Β  Β  Β  Β  Β  Β  Β otherwise. (3) 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. Fig. 4 (2000, 1000) IS-LDPC codes with parent identity An alternative to the log-SP algorithm to reduce the number matrix I50. of logical elements is the MS decoding process. The vertical Fig. 5 presents the performance curves for (2000, 1000) IS- step of the MS algorithm is simplified by evaluating the LDPC code using an identity matrix of dimension 100. The minimum values of probabilities from the check nodes. Let algorithm log-SP performs 0.4 dB, in terms of Eb/N0, better 𝛼!" = sgn(𝐿(π‘ž!" )) and 𝛽!" = abs(𝐿(π‘ž!" )), then Ξ¦(x) can be than the MS algorithm for a BER = 10-4. evaluated by the following approximation [4] 𝛷 !! 𝛷 𝛽! !! β‰ˆ 𝛷 𝛷 min! ! 𝛽! !! = min! !!!!\! 𝛽! !! . (4) This simplifies the evaluation of 𝐿 π‘Ÿ!" to 𝐿 π‘Ÿ!" = !!!!!\! 𝛼!!! . min!!!!!\! 𝛽!!! . (5) 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 Fig. 5 (2000, 1000) IS-LDPC codes with I100. The IS-LDPC codes are designed to operate at 100 Gbs optical Fig. 6 shows the performance of an IS-LDPC code built networks. Therefore, the encoding and decoding algorithms of using an identity matrix with dimension 200. The log-SP the (2000, 1000) and (4000, 2000) IS-LDPC codes should algorithm presents 0.15 dB gain over the MS algorithm, for a operate at the frequencies of 50 MHz and 25 MHz, BER = 10-4. 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. Fig. 6 (2000, 1000) IS-LDPC codes with I200. A. (2000, 1000) IS-LDPC codes Finally, fig. 7 presents an IS-LDPC code built with an identity matrix of dimension equal to 500. The decoding Figures 4 to 7 show the performance, in terms of bit error rate performances for both algorithms are almost coincident. The (BER) versus energy per bit/unilateral noise power spectral difference in performance is smaller than 0.1 dB between log- density (Eb/N0), of the (2000, 1000) IS-LDPC using log-SP SP and MS algorithms, for a BER = 10-4. 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. Fig. 4 shows the performance of an IS-LDPC code built from an identity matrix with dimension 50. The log-SP algorithm presents 1.3 dB gain over the MS algorithm at BER = 10-4. Fig. 7 (2000, 1000) IS-LDPC codes with I500. Fig. 9 (4000, 2000) IS-LDPC codes with I100. Notice that by increasing the dimension of the parent Fig. 9 presents the performance curves for the IS-LDPC identity matrix the performances of the log-SP and MS code using an identity matrix of dimension 100. The algorithm decoding algorithm become closer and closer. Further the log-SP performs 1.3 dB, in terms of Eb/N0, better than the MS increase in dimension reduces the number of 1's in H, which algorithm, for BER = 10-4. 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 Fig. 10 (4000, 2000) IS-LDPC codes with I200. and 1000. Fig. 10 shows the performance of a IS-LDPC code built using an identity matrix with dimension 200. The log-SP algorithm presents 0.3 dB gain over the MS algorithm, for BER = 10-4. Fig. 8 (4000, 2000) IS-LDPC codes with I50. 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 Fig. 11 (4000, 2000) IS-LDPC codes with I500. for BER = 10-3. Fig. 11 presents an IS-LDPC code built with an identity matrix of dimension 500. The difference in performance was 0.1 dB between log-SP and MS algorithms, for BER = 10-4. [3] M. Karkooti, Semi-Parallel Architectures for Real-Time LDPC Coding, MSc thesis, Rice University, 2004. [4] M. M. Mansour, N. Shanbhag, Low Power VLSI Decoder Architectures for LDPC Codes, Proceedings of the 2002 International Symposium on Low Power Electronics and Design, pp. 284 – 289, 2002. [5] S. Myung, K. Yang, Quasi-Cyclic LDPC Codes for Fast Encoding, IEEE Transactions on Information Theory, Vol. 51, issue: 8, pp. 2894 - 2901, 2005. [6] I. B. Djordjevic, M. Arabaci, and L. L. Minkov, Next Fig. 12 (4000, 2000) IS-LDPC codes with I1000. Generation FEC for High-Capacity Communication in Finally, fig. 12 presents an IS-LDPC code built with an Optical Transport Networks, Journal of Lightwave identity matrix of dimension equal to 1000. The decoding Technology, Vol. 27, Issue 16, pp. 3518-3530, Aug. 2009. performances for both algorithms are coincident. [7] M. R. Islam, D. S. Shafiullah, M. M. A. Faisal, I. Rahman Again, the performance gap between the log-SP and MS Optimized Min-Sum Decoding Algorithm for Low decoding algorithm narrows when the dimension of the parent Density Parity Check Codes, International Journal of identity matrix increases. Therefore, the (4000, 2000) IS Advanced Computer Science and Applications, Vol. 2, LDPC codes using parent identity matrixes with dimension No. 12, 2011. 500 and 1000 present the lowest VHDL implementation [8] W. E. Ryan, An Introduction to LDPC Codes, complexity. http://tuk88.free.fr/LDPC/ldpcchap.pdf V. CONCLUSION [9] B. S. Nugroho, LDPC code using MATLAB and C MEX, The class of IS-LDPC codes can be generated in an easy and http://sites.google.com/site/bsnugroho/ldpc. 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. REFERENCES [1] Bo Yuan, Li Li and Zhongfeng Wang, Efficient Forward Error Correction Decoder Design for High-Speed Optical Networking, Instech, chapter 11, pp. 267 – 288. [2] M. Jobes, A VLSI Architecture and the FPGA Implementation for multi-rate LDPC Decoding, MSc thesis, McMaster University, 2009.