 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): 30072018
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Low Complexity Design of Nonbinary LDPC Decoder Using Extended Minsum 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. Nonbinary LDPC is the class of binary LDPC, which works on the higher order Galois field. The decoding performance of nonbinary (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 NBLDPC. The extension of conventional sumproduct 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 NBLDPC decoder.
Index TermsNonbinary, 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 errorcorrecting capability, LDPC codes have been used in wireless communications, optical and magnetic recording and digital television broad casting. The standards such as DVBS2, WiMAX, WLAN, storage devices and so on. Binary low density paritycheck (LDPC) codes, revealed by Gallager in 1962[1,2] were rediscovered and shown to approach Shannon capacity in the late 1990s.Nonbinary LDPC (NBLDPC), viewed as an extension of the binary codes. It was first investigated by Davey and Mackay [3].NBLDPC codes have performance advantage over binary codes. A simplified decoding algorithm for lowdensity paritycheck (LDPC) codes over high order Galois field is proposed to reduce the complexity of tradition sumproduct algorithm (SPA) [4]. The minsum algorithm is extended to any finite field of order q, only additions are performed and no channel information is necessary [5]
Based on simplified minsum 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 Minsum 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 BitErrorRate (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 Nonbinary LDPC codes. In section III explanation of Minsum 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.

NONBINARY LDPC CODES REPRESENTATION

Matrix Representation
LDPC codes are represented by parity check matrix. Number of nonzero elements present in each row parity check matrix is wr and wc is the number of nonzero 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 NBLDPC, the computational burdon in the check node mainly depends on the number of nonzero 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 (cnodes) 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


MINSUM ALGORITHM
Minsum 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 nonzero 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 IIdentity 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 nonbinary 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
Minsum decoding for nonbinary 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
101
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 NBLDPC 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
101
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
100.8
BER
100.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
101
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 MINSUM 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 nonzero 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. IT8,pp.2128, 1962.

R.G Gallager,LowDensity ParityCheck codes, Cambridge,MA:MIT press,1963.

D.J.Mackay and R.Neal,Near ShannonLinit performance of low density paritycheck codes,vol. 32,pp. 16451646,1996

M.Davey and D. Mackay, Lowdensity paritycheck 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 NonBinary 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. ChungLi, HighThroughput Efficient Non Binary LDPC Decoder Based on the Simplified MinSum Algorithm,IEEE transactions on Circuits and Systems,vol.59,pp. 27842794,Nov 2012.

A. voicila, D. Declerq, F. verdier, M. Fossorier and P. Urard, Architecture of a lowcomplexity nonbinary 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.772776, Paris, France, June 2004.

V.S. Ganepola, R.A Carrasco, I.J. Wassell and S. Le Goff , Performance study of Nonbinary 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 MinSum Algorithms for Decoding of LDPC over GF(q),IEEE information theory workshop(ITW06),pp.9699, September 2006.

X. Zhang, F. Cai, Reducedcomplexity Extended Minsum Check Node Processing for Nonbinary 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, LowComplexity Decoding for NonBinary 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.