Download Full-Text PDF Cite this Publication

**Open Access**-
**Total Downloads**: 5 -
**Authors :**C.S.Elamaran, M.Anbuselvi -
**Paper ID :**IJERTCONV1IS06147 -
**Volume & Issue :**ICSEM – 2013 (Volume 1 – Issue 06) -
**Published (First Online):**30-07-2018 -
**ISSN (Online) :**2278-0181 -
**Publisher Name :**IJERT -
**License:**This work is licensed under a Creative Commons Attribution 4.0 International License

#### 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

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

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.

NON-BINARY LDPC CODES REPRESENTATION

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.

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

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.

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.

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.

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.

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.

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

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

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

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

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.

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

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

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

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

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

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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.