Applications of Low Density Graph Codes in Two Source Coding Problems

Abstract

<p>In this thesis, we present the applications of low density graph codes in two different types of source coding problems. First, we consider asynchronous Slepian-Wolf coding where the two encoders may not have completely accurate timing information to synchronize their individual block code boundaries, and propose LDPC design in this scenario. A new information-theoretic coding scheme based on source splitting is provided, which can achieve the entire asynchronous Slepian-Wolf rate region. Unlike existing methods based on source splitting, the proposed scheme does not require common randomness at the encoder and the decoder, or the construction of superletter from several individual symbols. We then design LDPC codes based on this new scheme, by applying the recently discovered source-channel code correspondence. Second, we consider the lossy source coding problem. In contrast with most prior work that has focused exclusively on the binary uniformly distributed source, we address the problem of lossy coding for sources with arbitrary alphabets and distributions. Built upon the idea of approximating the optimal output distribution indicated by the rate-distortion theory with a uniform distribution over a larger alphabet, we propose a multilevel coding scheme using LDGM codes that can approach the rate-distortion limit for a general source. Experimental results validate the effectiveness of both proposed methods.</p>