Source Coding for Erasure Channels

Abstract: The main goal of this thesis is to bound the rate-distortion performance of the aforementioned sparse-graph codes for lossy compression of a BES. As our main contributions, we first derive lower bounds on the rate-distortion performance of LDGM codes for the BES, which are valid for any LDGM code of a given rate and generator node degree distribution and any encoding function. Our approach follows that of Kudekar and Urbanke, where lower bounds were derived for the BSS case. They introduced two methods for deriving lower bounds, namely the counting method and the test channel method. Based on numerical results they observed that the two methods lead to the same bound. We generalize these two methods for the BES and prove that indeed both methods lead to identical rate-distortion bounds for the BES and hence, also for the BSS. Secondly, based on the technique introduced by Martinian and Wainwright, we upper bound the rate-distortion performance of the check regular Poisson LDGM (CRP LDGM) ensemble and the compound LDGM-LDPC ensemble for the BES.We also show that there exist compound LDGM-LDPC codes, with degrees independent of the blocklength, which can achieve any given point on the Shannon rate-distortion curve of the BES.