Record Details

A Modified Sum-Product Algorithm over Graphs with Short Cycles

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title A Modified Sum-Product Algorithm over Graphs with Short Cycles
 
Creator Raveendran, Nithin
 
Subject Computer Mathematics
Decoding Algorithms
Sum-Product Algorithms
Low Density Parity Check Codes (LDPC)
Error Control Codes
Graphical Codes
Modified Message Passing Algorithm
Tanner Grpahs
Graph Algorithms
Cycle (Graph Theory)
Short Cycle Graphs
Graphs
Iterative Decoding Algorithm
Electronic System Engineerin
 
Description We investigate into the limitations of the sum-product algorithm for binary low density parity check (LDPC) codes having isolated short cycles. Independence assumption among messages passed, assumed reasonable in all configurations of graphs, fails the most
in graphical structures with short cycles. This research work is a step forward towards
understanding the effect of short cycles on error floors of the sum-product algorithm.
We propose a modified sum-product algorithm by considering the statistical dependency
of the messages passed in a cycle of length 4. We also formulate a modified algorithm in
the log domain which eliminates the numerical instability and precision issues associated
with the probability domain. Simulation results show a signal to noise ratio (SNR) improvement for the modified sum-product algorithm compared to the original algorithm.
This suggests that dependency among messages improves the decisions and successfully
mitigates the effects of length-4 cycles in the Tanner graph. The improvement is significant at high SNR region, suggesting a possible cause to the error floor effects on such graphs. Using density evolution techniques, we analysed the modified decoding algorithm. The threshold computed for the modified algorithm is higher than the threshold computed for the sum-product algorithm, validating the observed simulation results. We also prove that the conditional entropy of a codeword given the estimate obtained using the modified algorithm is lower compared to using the original sum-product algorithm.
 
Contributor Srinivasa, Shayan G
 
Date 2018-07-18T14:12:22Z
2018-07-18T14:12:22Z
2018-07-18
2015
 
Type Thesis
 
Identifier http://etd.iisc.ernet.in/2005/3847
http://etd.iisc.ernet.in/abstracts/4719/G27110-Abs.pdf
 
Language en_US
 
Relation G27110