000204945 001__ 204945
000204945 005__ 20181117224356.0
000204945 037__ $$aCONF
000204945 245__ $$aAsynchronous Decoding of LDPC Codes over BEC
000204945 269__ $$a2015
000204945 260__ $$c2015
000204945 336__ $$aConference Papers
000204945 520__ $$aLDPC codes are typically decoded by running a synchronous message passing algorithm over the corresponding bipartite factor graph (made of variable and check nodes). More specifically, each synchronous round consists of 1) updating all variable nodes based on the information received from the check nodes in the previous round, and then 2) updating all the check nodes based on the information sent from variable nodes in the current round. However, in many applications, ranging from message passing in neural networks to hardware implementation of LDPC codes, assuming that all messages are sent and received at the same time is far from realistic. In this paper, we investigate the effect of asynchronous message passing on the decoding of LDPC codes over a BEC channel. We effectively assume that there is a random delay assigned to each edge of the factor graph that models the random propagation delay of a message along the edge. As a result, the output messages of a check/variable node are also asynchronously updated upon arrival of a new message in its input. We show, for the first time, that the asymptotic performance of the asynchronous message passing is fully characterized by a fixed point integral equation that takes into account both the temporal and the spatial feature of the factor graph. Our theoretical result is reminiscent of the fixed point equation in traditional BP decoding. Surprisingly, our simulation results show that asynchronous scheduling outperforms tremendously the traditional BP in the finite block length regime by avoiding standard trapping sets.
000204945 6531_ $$aLDPC Codes
000204945 6531_ $$aErasure Channel
000204945 6531_ $$aAsynchronous Belief Propagation
000204945 6531_ $$aGraphical Models
000204945 700__ $$0244475$$aHaghighatshoar, Saeid$$g200157
000204945 700__ $$0242509$$aKarbasi, Amin$$g161506
000204945 700__ $$0243425$$aSalavati, Amir Hesam$$g190838
000204945 7112_ $$aIEEE International Symposium on Information Theory (ISIT)$$cHong Kong$$dJune 14-19, 2015
000204945 8564_ $$uhttps://github.com/saloot/AsynchronousBP/tree/master/ErasureDecoder$$zURL
000204945 8564_ $$s397552$$uhttps://infoscience.epfl.ch/record/204945/files/Asynchronous%20Decoding%20of%20LDPC%20Codes%20over%20BEC.pdf$$yn/a$$zn/a
000204945 8564_ $$s172677$$uhttps://infoscience.epfl.ch/record/204945/files/Erasure%20Decoding.ipynb$$yiPython Notebook$$ziPython Notebook
000204945 8564_ $$s132624$$uhttps://infoscience.epfl.ch/record/204945/files/ErasureDecoder_Code_RR.zip$$ythe Code used in the paper$$zthe Code used in the paper
000204945 8564_ $$s264755$$uhttps://infoscience.epfl.ch/record/204945/files/Figures_Data.zip$$yThe data used in the figures$$zThe data used in the figures
000204945 909C0 $$0252435$$pISC$$xU10423
000204945 909CO $$ooai:infoscience.tind.io:204945$$pconf$$qGLOBAL_SET
000204945 917Z8 $$x190838
000204945 917Z8 $$x148230
000204945 917Z8 $$x190838
000204945 937__ $$aEPFL-CONF-204945
000204945 973__ $$aEPFL$$rREVIEWED$$sPUBLISHED
000204945 980__ $$aCONF