Low Complexity Design of Non-binary LDPC Decoder Using Extended Min-sum Algorithm

Low Complexity Design of Non-binary LDPC Decoder Using Extended Min-sum Algorithm

C.S.ELAMARAN

Dept.of ECE

SSN College of engineering Kalavakkam, Chennai. elamaran27@gmail.com

1. NBUSELVI

   Assistant Professor, Dept.of ECE SSN College of engineering Kalavakkam, Chennai. anbuselvim@ssn.edu.in

   Abstract Low Density Parity Check (LDPC) codes, is a linear block code having the decoding performance closer to Shannons limit. Non-binary LDPC is the class of binary LDPC, which works on the higher order Galois field. The decoding performance of non-binary (NB) LDPC is better than binary LDPC for moderate code lengths. The increased computation with the increased order of field is the major challenge in hardware realization of NB-LDPC. The extension of conventional sum-product algorithm, known as extended Min- Sum (EMS) algorithm, with reduced computational complexity is used in this paper. However, a tradeoff exists between computational complexity and decoding performance.

   This paper aims at reducing the computational complexity by focusing on the Parity Check Matrix (PCM) modifications. The bottleneck of the design is large memory requirement and more computation intensive. The modification in the EMS algorithm can be incorporated to design low complexity hardware architecture of NB-LDPC decoder.

   Index TermsNon-binary, LDPC, EMS algorithm, PCM

   1. INTRODUCTION

      LDPC codes have attracted much attention because of their excellent error correcting performance and near to Shannon limit. Due to the powerful error-correcting capability, LDPC codes have been used in wireless communications, optical and magnetic recording and digital television broad casting. The standards such as DVB-S2, WiMAX, WLAN, storage devices and so on. Binary low- density parity-check (LDPC) codes, revealed by Gallager in 1962[1,2] were rediscovered and shown to approach Shannon capacity in the late 1990s.Non-binary LDPC (NB-LDPC), viewed as an extension of the binary codes. It was first investigated by Davey and Mackay [3].NB-LDPC codes have performance advantage over binary codes. A simplified decoding algorithm for low-density parity-check (LDPC) codes over high order Galois field is proposed to reduce the complexity of tradition sum-product algorithm (SPA) [4]. The min-sum algorithm is extended to any finite field of order q, only additions are performed and no channel information is necessary [5]

      Based on simplified min-sum algorithm decoder architecture is built, in which the design technique employed

      increases the parallelism and throughput by three or four times [6]. The decoding complexity is reduced by Extended Min-sum algorithm. It also works on Log likely hood ratios (LLR); log domain is advantageous because it requires only sum operation. It also reduces the computational burden in the check node update. Our paper aims to reduce the hardware complexity and also reducing the memory requirement through parity check matrix modification. The Bit-Error-Rate (BER) performance for NB parity check matrix used in IEEE 802.1ln with code length of 648 is used in this paper .Section I review the basics of LDPC codes and section II provides the representation of Non-binary LDPC codes. In section III explanation of Min-sum algorithm is presented. Section IV presents the Parity Check Matrix modification and section V gives the performance analysis of modified parity check matrices in terms of BER for the code length of IEEE 802.11n standard and 504.In section VI, it describes the computational analysis of modified parity check matrices.

   2. NON-BINARY LDPC CODES REPRESENTATION

      1. Matrix Representation

         LDPC codes are represented by parity check matrix. Number of non-zero elements present in each row parity check matrix is wr and wc is the number of non-zero elements present in each column. For a matrix to be called low density it should satisfy the conditions like wc << n and wr << m. (m, n) are the number of rows and columns present in the parity check matrix (PCM). Fig.1, shows the matrix representation of NB-LDPC, the computational burdon in the check node mainly depends on the number of non-zero elements present in the parity check matrix.

         Fig. 1. Example of parity check matrix.

      2. Graphical Representation

      Tanner graph is an effective graphical representation for LDPC codes. Tanner graphs are bipartite graphs. The nodes of the graph are separated into two distinctive sets and edges are only connecting nodes of two different types. The types of nodes in a Tanner graph are called variable nodes (v- nodes) and check nodes (c-nodes) as shown in fig. 2. Check node and variable node represents the number of rows and columns in a parity check matrix respectively. Whenever, a nonzero element is present in a PCM, it indicates an edge formation between a check node and a variable node. The Computational complexity of the tanner graph depends on the check node.

      Fig. 2.Tanner graph representation

   3. MIN-SUM ALGORITHM

      Min-sum algorithm with proper modifications has given negligible performance degradation. It works on log likelihood ratio. It requires only sum and comparison operation, it also reduces the computational burden in the check node update.

      1. Step1: Initialization

         All messages passing from a variable node to a check node are initialized to Ln (a), the log likelihood ratio concerning symbol a. This value depends on the type of channel under investigation.

         (1)

         where Sn denotes the most likely symbol for a.

      2. Step2: Variable node update.

         All messages from the check nodes are updated using,

         (3)

         (4)

         set of neighboring variable nodes connected to a check node

         m.

      3. Step3:Check node update

         All messages from the variable nodes are updated using equation

         (5)

         (6)

         (7)

         M(n) denotes the set of neighboring check nodes connected to a variable node n.

      4. Step4:Tentative Decoding

         An estimation of the variable node is made using equation

         (8)

         (9)

         (10)

         The minfunctions return the minimum and the maximum values among their inputs,respectively . If C is verified to be a valid codeword or maximum iteratiion number L is reached ,then the decoding process will be terminated. Otherwise another decoding iteration will be initiated. But if valid codeword is not obtained until maximum iteration then decoding failure is declared.

   4. PARITY CHECK MATRIX MODIFICATION

      The strength of the LDPC are defined by number of non zero elements present in the parity check matrix. Computational complexity increases with number of non-zero elements. Increasing the sparcity of parity check matrix in turn reduces the computational complexity. The PCM has the following structural properties.

      • Each row has weight, wr

      • Each column has weight, wc

      • No two rows (or two columns) have more than one place where they both have non zero elements.

        Modifications

        With the randomly generated parity check matrix, we propose two modifications to reduce the computational complexity, retaining the structural properties of PCM.Two modifications are namely,

      • Lower Diagonal Parity Check Matrix

      Where

      Am,n (a)

      is the set of vectors that consists of

      • Doubly Diagonal Parity Check Matrix

      Galois field symbols. Each vector consists of N(m)-1 Galois feld symbols that satisfy the check equation.N(m) denote the

      1. Lower Diagonal Parity Check Matrix (LDM)

         This focuses on the diagonal elements of the matrix. Here in first kind, we propose the modified PCM structure where the diagonal elements of lower part of the PCM matrix are modified. Lower diagonal parity check matrix in the size of (12, 24) is shown in fig. 3.

         The matrix structure is in the form of

         H= [H QC |I] (11)

         H QC -Quasy cyclic matrix I-Identity matrix

         The mathematical model for the first proposal can be

         given as follows:

         The formation of the matrix is defined with the model of identifying the position of identity matrix (IM) and random matrix (RM). Let be the element in the parity check matrix defined. Mentioning the placement of the IM as

         = IM for {r/2 to r, s/2 to s} (12)

         = RM for {1 to r/2} (13)

         Fig. 3.Lower diagonal parity check matrix

      2. Doubly Diagonal Based Parity Check Matrix (DDM)

      In the second proposal, the PCM is framed using the double diagonal identity matrix. In this frame work also, the properties of the matrix for non-binary code over GF (q) are retained. The formation of the matrix is defined with the model of identifying the identity matrix (IM) and redundant identity matrix (RIM).The DDM matrix structure in the size (12, 24) is shown in fig. 4.

      = IM for {r, s/2 to s} (14)

      =RIM for{r, 1 to s/2} (15)

      Fig. 4.Doubly Diagonal Parity Check Matrix

   5. PERFORMANCE ANALYSIS

      							Standard Parity Check Matrix Lower Diagonal Parity Check Matrix Doubly Diagonal Parity Check Matrix

      Min-sum decoding for non-binary LDPC codes are coded using MATLAB and the decoding performance of two different parity check matrices are obtained for the specification of IEEE 802.11n under AWGN channel. Performance curves like Bit Error Rate (BER) for a range of Signal to Noise Ratio are plotted. The Code length of 648 with code rate of ½ is taken for analysis. The code length of 504 is also selected to investigate for under water communication.

      BER

      10-1

      0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

      SNR(dB)

      Fig. 5.BER performance comparison of Code length 504 for GF (4)

      By increasing the order of Galois field decoding performance also increases.BER performance is plotted for both GF (4) and GF (8) under the code length of 648 and 504. BER performance of code length 504 for GF(4) and GF(8) are shown in fig. 4 & fig. 5.From these figures it is inferred that the BER rate of DDM is very less compared to Standard and LDM. The decoding performance of the NB-LDPC codes improves with the increase in the code length. It is proven that with the modified parity check matrices, improved performance is attained at higher code length. The decoding performance of DDM is less compared with other matrices .It gives a better decoding performance.

      BER

      						Standard Parity Check Matrix
      						Lower Diagonal Parity Check Matrix Doubly Diagonal Parity Cehck Matrix

      10-1

      0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

      SNR(dB)

      Fig. 6.BER performance comparison of code length 504 for GF (8)

      Standard Parity Check Matrix Lower Diagonal Parity Check Matrix

      Doubly Diagonal Parity Check Matrix

      10-0.8

      BER

      10-0.9

      0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

      SNR(dB)

      							Standard Parity Check Matrix Lower Diagonal Parity Check Matrix Doubly Diagonal Parity Check Matrix

      Fig . 7.BER performance comparison of code length 648 for GF (4)

      BER

      10-1

      0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

      SNR(dB)

      Fig. 8.BER performance comparison of code length 648 for GF (8).

      BER Performance of code length 648 for GF (4) and GF

      1. is shown in fig. 7 & fig. 8. LDM based PCM structures are suitable for the moderate decoding performance with lesser computational complexity.DDM based PCM structures are applicable for the best decoding performance with the compromise on the computational complexity.

   6. COMPUTATIONAL ANALYSIS

      The significance of the proposed matrix structures are analyzed with the computation complexity involved in it. The analysis of the strength of each proposed modified PCM structures are done for the matrix size of (12×24).

      TABLE I. COMPUTATIONAL COMPLEXITY OF MIN-SUM DECODING WITH MODIFIED PARITY CHECK

      MATRICES

      Computations	Standard Parity Check Matrix	Lower Diagonal Parity Check Matrix	Doubly Diagonal Parity Check Matrix
      Number of Addition operation in CNU
      Number of Comparison operation in VNU

      Where, q- Order of Galois field

      m – Number of rows in PCM.

      n – Number of columns in PCM.

      – Row weight in PCM.

      -Column weight in PCM. -Row weight in LDM

      -Column weight in LDM

      • Row weight in DDM

      • Column weight in DDM

      Table. I shows that the computational complexity for Parity Check Matrix (PCM), Doubly Diagonal based PCM (DDM) and Lower Diagonal based PCM (LDM). This shows that the number of addition and comparison operation in Check Node Unit (CNU) and Variable Node Unit (VNU) for LDM is lesser since number of non-zero elements in it is less when compared with Standard PCM and DDM.

      Table. II shows that the number of addition and the number of comparison in CNU and VNU for standard PCM, DDM and LDM for the matrix size of 12X24. When compared to standard PCM the number of addition and comparison operations is less for lower diagonal PCM, for Doubly diagonal PCM the number computations are high when compared to standard PCM.But the performance of DDM is better than other matrices.

      TABLE II.

      NUMBER OF COMPUTATIONS IN MODIFIED PARITY CHECK MATRICES

      Comput ation	Standard Parity Check Matrix		Lower Diagonal Parity Check Matrix		Dobly Diagonal Parity Check Matrix
      	Addit ion	Compar ison	Addit ion	Compar ison	Addit ion	Compar ison

      In CNU	276	276	180	180	304	304
      In VNU	264	264	168	168	292	292

   7. CONCLUSION

This paper proposes two modifications to the PCM structure there by the decoding performance will be improved with reduced computational complexity. The performance analysis of the proposed LDM and DDM based PCM structures are analyzed with the BER graphs and computational complexities are also evaluated. It is inferred that LDM based PCM structures are suitable for the moderate decoding performance with lesser computational complexity and DDM based PCM structures are applicable for the best decoding performance with the compromise on the computational complexity.

REFERENCES

1. Gallager, R.G.; Low density parity check codes,IRE Trans.Info.Theory, Vol. IT-8,pp.21-28, 1962.

2. R.G Gallager,Low-Density Parity-Check codes, Cambridge,MA:MIT press,1963.

3. D.J.Mackay and R.Neal,Near Shannon-Linit performance of low density parity-check codes,vol. 32,pp. 1645-1646,1996

4. M.Davey and D. Mackay, Low-density parity-check codes over GF(q),IEEE communication letter., vol.2, no.1, pp. 165- 167,January 1998.

5. El Hassani, S. Hamon, M. and H. Penard, P."Comparison Study Of Binary and Non-Binary LDPC codes Decoding," Proc in IEEE international conference ,software ,telecommunications and computer networks (softCOM),pp.355 359A Sep.2010.

6. D. Declercq and M. Fossorier, Decoding algorithms for non- binary LDPC codes GF(q), IEEE Trans. Commun., vol. 55, no. 4, pp.633, 2007.

7. X.Chen, W. Chung-Li, High-Throughput Efficient Non- Binary LDPC Decoder Based on the Simplified Min-Sum Algorithm,IEEE transactions on Circuits and Systems,vol.59,pp. 2784-2794,Nov 2012.

8. A. voicila, D. Declerq, F. verdier, M. Fossorier and P. Urard, Architecture of a low-complexity non-binary LDPC decoder for high order fields,IEEE Transactions on communication, vol.55, no.4, Oct.2007.

9. H. Wymeersch, H. Steendam and M. Moeneclaey, Lod- domain decoding of LDPC codes over GF(q),The proc. IEEE Intern. Conf. on Commun., pp.772-776, Paris, France, June 2004.

10. V.S. Ganepola, R.A Carrasco, I.J. Wassell and S. Le Goff , Performance study of Non-binary LDPC codes over GF(q),IEEE intern. Conf. on communication systems

    ,Networks and digital signal processing,pp.585 589, July 2008.

11. X. Huang, S. Ding, Z. Yang and Y.Wu,Fast Min-Sum Algorithms for Decoding of LDPC over GF(q),IEEE information theory workshop(ITW06),pp.96-99, September 2006.

12. X. Zhang, F. Cai, Reduced-complexity Extended Min-sum Check Node Processing for Non-binary LDPC Decoding, IEEE intern. Conf. on circuits and systems (MWSCAS),pp. 737- 740, August 2010.

13. A. Voicila, D. Declercq, F.Verdier, M. Fossorier and P. Urard, Low-Complexity Decoding for Non-Binary LDPC codes in High Order Fields,IEEE Transactions on communication, Vol. 58, No.5 , May 2010.

14. J. Huang, S. Zhou and P.Willett Nonbinary LDPC Coding for Multi carrier Underwater Acoustic CommunicationIEEE journals and magazines on communication, Vol.26, pp. 1684 1696, Dec 2008.