 Open Access
 Total Downloads : 18
 Authors : Sai Supriya G K, Smt. Pushpalatha K N
 Paper ID : IJERTCONV6IS13128
 Volume & Issue : NCESC – 2018 (Volume 6 – Issue 13)
 Published (First Online): 24042018
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
DEMS Algorithm for LDPC Codes used in Error Detection and Correction
Sai Supriya G K
MTechstudent, Dept. of Electronics & communication Dayananda Sagar College for PGstudies,
BengaluruIndia
Smt. Pushpalatha K N
Associate Professor, Dept. of Electronics & communication Dayananda Sagar College for PGstudies,
BengaluruIndia
Abstract The proposed project investigates the behavior of the MinSum decoder running on noisy devices. The aim is to evaluate the robustness of the decoder to computation noise, caused by the faulty logic in the processing units. This type of noise represents a new source of errors that may occur during the decoding process. Hence here introduced a unique algorithmic approach called Density Evolved Min Sum (DEMS) algorithm, which checks for the individual iterative population of the respective information during decoding. There will be two updates involved in the approach evolved with its density function value.
KeywordsMS (Min Sum), DE (Density Evolution), LDPC (Low Density Parity Check) codes, ECC (Error Control Coding)

INTRODUCTION
Over the past years, the study of error correcting decoders, especially LowDensity ParityCheck (LDPC) decoders, running on noisy hardware attracted more and more interest in the coding community. The analytical methods have been proposed to evaluate the performance of one step majority logic LDPC decoders constructed from faulty gates. Then the concentration and convergence properties were proved for the asymptotic performance of noisy message passing decoders, and density evolution equations were derived for the noisy GallagerA and BeliefPropagation (BP) decoders. The authors of past research investigated the asymptotic behavior of the noisy GallagerB decoder defined over binary and nonbinary alphabets. Finite Alphabet Iterative Decoders (FAIDs) under processing errors have also been investigated. Recently, the MinSum decoding under unreliable message storage has also been investigated. In all those research the noisy implementation of the iterative message passing decoders was emulated by passing each of the exchanged messages through a noisy channel.
In the proposed project, we investigate the asymptotic and finitelength behavior of the noisy MS decoder. Aim is to refine the probabilistic error models for the noisy MS decoder which were used previously, and discussed for their symmetry properties. Then derivation of density evolution equations and to conduct a thorough asymptotic analysis of the noisy MS decoder.

OBJECTIVES AND TOOLS USED

Objectives

To achieve higher gain of about 0.2db compared to other classical NMS algorithms.

To achieve equivalent decoding performance compared with the Linear Minimum Mean Square Error (LMMSE) MS algorithm.

To improve decoding speed of about 7% compared to other classical NMS algorithms.

To improve the power consumption, which can be reduced 16% by skipping unnecessary steps in the unsuccessful iteration without any loss in error correction performance.


Tools Used
The software tool that is going to be used for the project work is,

Mat lab R2014a (version 7.1)

ModelSim for simulating the design

The project is about to provide an opportunity to use theoretical knowledge and write Mat lab algorithms using both source code and Simulink modeling. Within an acceptable tolerance, the simulations successfully in recreating results published in 2003 by MacKay. The required flow chart and proposed methodologies are stated in brief sentenced below.


PROPOSED METHADOLOGY AND OVERALL BLOCK SCHEMATIC
Figure 1: System Overview
The above shown is the complete block schematic of the proposed methodology. The block wise explanation of the above schematic is as follows:

Schematic Explaination

Message Source: The message source is the enduser transmitting the data. In terms of mobile communications, the message source would be the enduser transmitting his/her voice information. The simulation utilized a random message generator. This generator creates a message vector with equal a priori probability: Pr [= 1] = Pr [= 0] = 0.5

LDPC Encoder: The LDPC encoder is implemented at the enduser transmitting the data. In terms of simulation implementation, encoding is done via a generator matrix. This is covered in further detail in section 3.4.

BPSK Modulator: The BPSK (Binary Phase Shift Keying) modulator maps the input binary signals, to an analog signal for transmission. In simulation, the BPSK signal is represented by the mapping: {0, 1} {,} b b E E.

Channel: The channel is the medium of which information is transmitted from the transmitter to the receiver. In mobile communication, this is a wireless channel, and for other applications this could be copper or fiber optics. The addition of noise normally occurs in the channel. In the simulations, the channel is modeled as an AWGN (Additive White Gaussian Noise) channel. The resulting noise added to the system follows the zeromean normal distribution, with variance NO/2, and NO is the singlesided noise power spectral density.

LDPC Decoder: The decoder is implemented at the end user receiving the information. In terms of simulation implementation, decoding is a process that loops through passing messages back and forth along the tanner graph under certain conditions are satisfied, or a maximum number of passes have occurred. It is obvious that in mobile communications, the handset would require both the encoder and decoder as a pair to allow for bidirectional communication.

Retrieve Message From Codeword: This simple process retrieves the estimated message from the estimated codeword. In the simulation this is done via a simple function call following estimating the codeword.

Message Destination: The message destination is the end user receiving the data. In a mobile communications environment, this would be the user receiving the voice information of the other user. In the simulations, there is no message destination; rather the estimated message is compared to the transmitted message in order to detect whether a transmission error occurred.


Generation of H for Simulation
The method used for generating the H matrix in this paper was random generation with constraints. The algorithm used to generate this routine allows for 4 input parameters:

N – Block/Codeword Length

k – Message Bits

wC – Column Weight (# of 1s per column)

reltol – Tolerance Variable used to control regularity
The row weight (wR) is computed as wCN/(Nk). In order to guarantee that wR is a whole number, the value is
rounded up if it contains a decimal value, setting the maximum allowed number of 1s per row. In order to allow for sufficiently fast computation of the H matrix, only cycles of length 4 are avoided in the algorithm. The algorithm for generation of the matrix is shown in Figure 2 below.


Flowchart
Figure 2: Flow chart of the encoding part of proposed methodology
Interconnect representation of H matrix

Two sets of nodes: Check nodes and Variable nodes

Each row of the matrix is represented by a Check node

Each column of matrix is represented by a Variable node
A message passing method is used between nodes to correct rrors

Initialization with Received word

Messages passing until correct Example:
Where,
Figure 5: Flowchart of proposed decoding methodology
Figure 3: Flow chart to create the ParityCheck matrix H
: message from check to variable node
:message from variable to check node
: is the original received information from the channel

Based on the modulation scheme (here BPSK) estimate the transmitted bits
i

Compute syndrome H.V T=0(Binary multiplication) Ex:
Figure 4: Hmatrix check node and variable node representation
Then using above shown figure 4, proposed methodology alpha and beta updates are done to generated matrix along with PDF form density evolution.



Proposed Decoding Methadology
Now calculate alpha, beta, Zi using below formulas for the node updates of the proposed algorithm. The follow the next steps to terminate the process.

Z j ij ' j
j ',hij ' 1

ij Z j ij

If syndrome =0, terminate decoding

Else, continue another iteration


Hence, the process terminates when syndrome becomes zero or else the entire step repeats.


EXPERIMENTAL RESULTS
The simulation result is expected that, a gain of about
0.2 dB can be achieved in comparison with the classical NMS algorithm The simulation results the decoding speed which can be improved by 7%, and the power consumption can be reduced 16% by skipping unnecessary steps in the unsuccessful iteration without any loss in error correction performance.

BitError Rate Graph
Transmitter: For the given information source a respective parity check matrix (H) is created. The H matrix consists of kbit message with nsymbol block (code word). Then the code rate(R) is a ratio of k by n, which gives the information about the number of bits entering encoder per transmitted symbol. The condition is, R should be Â½ initially. Then the number of columns, number of rows, time interval, method to be used out of three Hmatrix creation methods are opted with evencolumn or evenboth options which spreads the particular number of ones fed. Then for the respective
signal to noise ratios fed in (in experiment taken as: Eb/N0= 0, 0.5, 1.0, 1.5), a minimum of five iterations takes place with a frame size of ten to create the respective Hmatrix. This is LDPC encoding. Then the encoded message is been modulated using Binary Phase Shift Keying (BPSK) to make it compatible to transfer over noisy channel.
Figure 6: The Bit Error Rate Graph of Computed methodology compared with the classical LDPC methodology.
Channel: Then modulated signal is passed over Additive White Gaussian Noise (AWGN) channel which introduces noise to the information.
Receiver: then the affected information is got from the noisy channel, which is demodulated and decoded in three techniques respectively for the comparison purpose. They are: LDPC decoding, MINSUM decoding, and the proposed DEMS decoding. They are been decoded using their respective formulas and algorithms discussed. Then the result is tabulated in terms of graph of Signal to Noise Ratio (SNR) v/s Bit Error Rate (BER).
The result shows that the proposed methodology improves the Error Control rate in wireless communication system efficiently than the previous classical algorithms.

Gain Performance
The simulation result is expected that, a gain of about 0.2 dB can be achieved in comparison with the classical NMS algorithm.

Advantages

LDPC: In information theory, a lowdensity parity check (LDPC) code is a linear error correcting code, a method of transmitting a message over a noisy transmission channel. An LDPC is constructed using a sparse bipartite graph. LDPC codes are capacity approaching codes which means that practical constructions exist that allow the noise threshold to be set very close.

Low Density Parity Check (LDPC) codes have superior error performance with 4 dB coding gain over convolution codes

Density evolution (DE): tracks the average probability density functions of the messages exchanged between the variable and check nodes at each decoding iteration in the limit of infinite block length.

MIN SUM (MS): satisfactory error correction performance and relatively low design complexity can be achieved.
The simulation results the decoding in which speed can be improved by 7% and the power consumption can be reduced 16% by skipping unnecessary steps in the unsuccessful iteration without any loss in error correction performance.


Applications
Mobile Broadcasting, Satellite and Wireless Communications, WideBand Wireless Multimedia Communications and Magnetic Storage Systems., Digital Video Broadcasting (DVBS2, DVBT2, DVBC2), Next Gen Wired Home Networking (G.hn), WiMAX (802.16e), WiFi (802.11n), Hard Disks, DeepSpace Satellite Missions etc.,


CONCLUSION AND FUTURE ENHANCEMMENTS
The simulation result is expected to have a gain of about 0.2 dB in comparison with the classical NMS algorithm. In addition, this algorithm can obtain the same decoding performance compared with the Linear Minimum Mean Square Error (LMMSE) MS algorithm whose decoding performance is very close to that of the BP algorithm. . In the simulation results, the decoding speed can be improved more and the power consumption can also be reduced by skipping unnecessary steps in the unsuccessful iteration without any loss in error correction performance. This can be more improved in terms of time elapsed to perform the whole action using still more effective time controllable algorithms for the purpose of high resolution Audios and videos.
ACKNOWLEDGMENT
Its an immense pleasure to thank Sri Manoj Kumar Singh, Sc E, ADE, Defense Research and Development Organization, Bangalore.
REFERENCES

Jorge Castineira Moreira and Patrick Guy Farell, Essentials o ErrorControl Coding, 2006 John Wiley & Sons, Ltd, Indian Edition, 2nd impression, ISBN 8962331034404, 2006.

Shu Lin and Daniel J. Costello, Jr., Error Control Coding the, 2011 Dorling Kindersley India Pvt. Ltd., Indian Edition, 2nd impression, ISBN 9788131734407, 2011.

Mohammad Rakibul Islam, Dewan Siam Shafiullah, Muhammad Mostafa Amir Faisal, Imran Rahman, Optimized MinSum Decoding Algorithm for Low Density Parity Check Codes,(IJACSA) International Journal of Advanced Computer Science and Applications, Vol. 2, No. 12,, Islamic University of Technology, Boardbazar, Gazipur1704, Dhaka, Bangladesh, 2015.

M. Martal`o, G. Ferrari, A. Abrardo, M. Franceschini, and R. Raheli, Density EvolutionBased Analysis and Design of LDPC Codes with A Priori Information, IBM T.J. Watson Research Centre, 1101 Kitchawan Road, Rte. 134, Yorktown Heights, NY 10598, USA, 2016.

Dan Dechene & Kevin Peets, SIMULATED PERFORMANCE OF LOWDENSITY PARITY CHECK CODES (a matlab implementation), lakehead university faculty of engineering, 2006.

Venkatesan Guruswami, Iterative Decoding of LowDensity Parity Check Codes (An Introductory Survey), Department of Computer Science and Engineering, University of Washington, Seattle, WA 98195, September 2006.

Farhad Zarkeshvari and Amir H. Banihashemi, On Implementation of MinSum Algorithm for Decoding LowDensity ParityCheck (LDPC) Codes, Broadband Communications and Wireless Systems (BCWS) Centre Dept. of Systems and Computer Engineering, Carleton University 1125 Colonel By Drive, Ottawa, Ontario, CanadaKlS 5B6, 0780376323/02/$17.00 02002 IEEE 2002.

Jinghu Chen, R. Michael Tanner, Christopher Jones and Yan Li, Improved MinSum Decoding Algorithms for Irregular LDPC Codes, Department of ECE, Unversity of Arizona, USA, June 2011.

Jun Xu, Lei Chen, Ivana Djurdjevic, Shu Lin and Khaled Abdel Ghaffar, Construction of Regular and Irregular LDPC Codes: Geometry Decomposition and Masking, IEEE transactions on information theory, vol. 53, no. 1, january 2007

Sachini Jayasooriya, Mahyar Shirvanimoghaddam and Lawrence Ong, A New Density Evolution Approximation for LDPC and MultiEdge Type LDPC Codes, arXiv:1605.04665v1 [cs.IT], 16 May 2016

Henry D. Pfister, Density Evolution for LDPC Codes on the BEC, Supplemental Material for Advanced Channel Coding, March 12th, 2014.

Eran Sharon, Simon Litsyn and Jacob Goldberger, AN EFFICIENT MESSAGEPASSING SCHEDULE FOR LDPC DECODING, TelAviv University, feransh,litsyng@eng.tau.ac.il, may 2005.

Yongmin Jung, Yunho Jung, Seongjoo Lee, and Jaeseok Kim, New Minsum LDPC Decoding Algorithm Using SNRConsidered Adaptive Scaling Factors, ETRI Journal, Volume 36, Number 4, August 2014.

Kapil Bhattad, LDPC Code Design for MinSum Based Decoding, Department of Electrical and Computer Engineering, Texas A&M University, College Station, Texas, USA, 2015.