Analysis of the Second Moment of the LT Decoder

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 k , our study gives bounds on the error probability of the LT decoder. Furt...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2012-05, Vol.58 (5), p.2558-2569
Main Authors: Maatouk, G., Shokrollahi, A.
Format: Article
Language:English
Subjects:
Applied sciences
Approximation methods
Closed-form solutions
Codes
Coding, codes
Decoders
Decoding
Difference equations
Differential equations
Error analysis
Error probability
Exact sciences and technology
Exact solutions
Finite-length analysis
Information theory
Information, signal and communications theory
Luby transform (LT) decoder
Mathematical analysis
Probability distribution
Receivers
ripple
Ripples
second moment
Signal and communications theory
Telecommunications and information theory
Transforms
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 k , 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/ k . This provides a first step toward an analytic finite-length analysis of LT decoding.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2012.2184690