Analysis of the Second Moment of the LT Decoder

Abstract

In this paper, the second moment of the ripple size during the Luby transform (LT) decoding process is analyzed. Combined with a result by Karp et al. (2004) stating that the expectation of the ripple size is of the order of <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i> , our study gives bounds on the error probability of the LT decoder. Furthermore, an analytic expression for the variance of the ripple size up to terms of constant order is given, and the expression of Karp et al. for the expectation of the ripple size is refined up to terms of the order of 1/ <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</i> . This provides a first step toward an analytic finite-length analysis of LT decoding.