Analysis of the Second Moment of the LT Decoder

DOI10.1109/TIT.2012.2184690MaRDI QIDQ5271930zbMATH OpenFDO

Authors Ghid Maatouk, M. Amin Shokrollahi

Publication date 12 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0902.3114

Mathematics Subject Classification ID

Decoding (94B35) Other types of codes (94B60)

Abstract: We analyze the second moment of the ripple size during the LT decoding process and prove that the standard deviation of the ripple size for an LT-code with length $k$ is of the order of $sqrtk.$ Together with a result by Karp et. al stating that the expectation of the ripple size is of the order of $k$ [3], this gives bounds on the error probability of the LT decoder. We also give an analytic expression for the variance of the ripple size up to terms of constant order, and refine the expression in [3] for the expectation of the ripple size up to terms of the order of $1/k$, thus providing a first step towards an analytic finite-length analysis of LT decoding.

Cited in

(1)

• Theory and applications of Raptor codes

This page was built for publication: Analysis of the Second Moment of the LT Decoder

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5271930)