DEMS Algorithm for LDPC Codes used in Error Detection and Correction

DEMS Algorithm for LDPC Codes used in Error Detection and Correction

Sai Supriya G K

MTech-student, Dept. of Electronics & communication Dayananda Sagar College for PG-studies,

Bengaluru-India

Smt. Pushpalatha K N

Associate Professor, Dept. of Electronics & communication Dayananda Sagar College for PG-studies,

Bengaluru-India

Abstract The proposed project investigates the behavior of the Min-Sum 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)

1. INTRODUCTION

   Over the past years, the study of error correcting decoders, especially Low-Density Parity-Check (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 Gallager-A and Belief-Propagation (BP) decoders. The authors of past research investigated the asymptotic behavior of the noisy Gallager-B decoder defined over binary and non-binary alphabets. Finite Alphabet Iterative Decoders (FAIDs) under processing errors have also been investigated. Recently, the Min-Sum 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 finite-length 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.

2. OBJECTIVES AND TOOLS USED

   1. 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.

   2. Tools Used

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

      • Mat lab R2014a (version 7.1)

      • Model-Sim 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.

3. 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:

   1. Schematic Explaination

      • Message Source: The message source is the end-user transmitting the data. In terms of mobile communications, the message source would be the end-user 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 end-user 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 zero-mean normal distribution, with variance NO/2, and NO is the single-sided 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 bi-directional 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.

   2. 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/(N-k). 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.

   3. 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

        1. Initialization with Received word

        2. Messages passing until correct Example:

        Where,

        Figure 5: Flowchart of proposed decoding methodology

        Figure 3: Flow chart to create the Parity-Check 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: H-matrix 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.

   4. 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.

4. 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.

   1. BitError Rate Graph

      Transmitter: For the given information source a respective parity check matrix (H) is created. The H matrix consists of k-bit message with n-symbol 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 H-matrix creation methods are opted with even-column or even-both 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 H-matrix. 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.

   2. 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.

   3. Advantages

      • LDPC: In information theory, a low-density 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.

   4. Applications

      Mobile Broadcasting, Satellite and Wireless Communications, Wide-Band Wireless Multimedia Communications and Magnetic Storage Systems., Digital Video Broadcasting (DVB-S2, DVB-T2, DVB-C2), Next- Gen Wired Home Networking (G.hn), Wi-MAX (802.16e), Wi-Fi (802.11n), Hard Disks, Deep-Space Satellite Missions etc.,

5. 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

1. Jorge Castineira Moreira and Patrick Guy Farell, Essentials o Error-Control Coding, 2006 John Wiley & Sons, Ltd, Indian Edition, 2nd impression, ISBN 896-23-310-3440-4, 2006.

2. Shu Lin and Daniel J. Costello, Jr., Error Control Coding the, 2011 Dorling Kindersley India Pvt. Ltd., Indian Edition, 2nd impression, ISBN 978-81-317-3440-7, 2011.

3. Mohammad Rakibul Islam, Dewan Siam Shafiullah, Muhammad Mostafa Amir Faisal, Imran Rahman, Optimized Min-Sum 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, Gazipur-1704, Dhaka, Bangladesh, 2015.

4. M. Martal`o, G. Ferrari, A. Abrardo, M. Franceschini, and R. Raheli, Density Evolution-Based 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.

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

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

7. Farhad Zarkeshvari and Amir H. Banihashemi, On Implementation of Min-Sum Algorithm for Decoding Low-Density Parity-Check (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, 0-7803-7632-3/02/$17.00 02002 IEEE 2002.

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

9. 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

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

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

12. Eran Sharon, Simon Litsyn and Jacob Goldberger, AN EFFICIENT MESSAGE-PASSING SCHEDULE FOR LDPC DECODING, Tel-Aviv University, feransh,litsyng@eng.tau.ac.il, may 2005.

13. Yongmin Jung, Yunho Jung, Seongjoo Lee, and Jaeseok Kim, New Min-sum LDPC Decoding Algorithm Using SNR-Considered Adaptive Scaling Factors, ETRI Journal, Volume 36, Number 4, August 2014.

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