Distinguishing codes from noise : fundamental limits and applications to sparse communication

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.Cataloged from student-submitted PDF version of thesis.Includes bibliographical references (p. 99-100).This thesis investigates the problem of distinguishing codes from noise. We develop a slotted channel model where in each time slot, the channel input is either a codeword or a noise sequence. In this model, successful communication requires both correctly detecting the presence of a codeword and decoding it to the correct message. While the decoding problem has been extensively studied, the problem of distinguishing codes from noise is relatively new, and we ask the following question regarding the "distinguishability" of a channel code: given a noisy channel and a code with a certain rate, what are the fundamental limits of distinguishing this code from noise at the output of the channel? The problem of distinguishing codes from noise involves both detection and decoding. In our analysis, we first extend the classical channel coding problem to incorporate the requirement of detection, which admits both miss and false alarm errors. Then we investigate the fundamental limits of code distinguishing in terms of the error exponents of miss and false alarm error probabilities. In a scenario that miss probability is required to vanish asymptotically but not necessarily exponentially, we characterize the maximum false alarm error exponent at each rate, and show that an i.i.d. codebook with typicality decoding is sufficient to achieve the maximum exponent. In another scenario that requires certain miss error exponent, we show that for DMC channels, the i.i.d. codebook is suboptimal and the constant composition codebook achieves the best known performance. For AWGN channels, we develop a clustered spherical codebook that achieves the best known performance in all operating regimes. This code distinguishability problem is strongly motivated by the synchronization problem in sparse communication, a new communication paradigm where transmissions take place intermittently and each transmission consists of a small amount of data. Our results show that, in sparse communication, the traditional approach of conducting synchronization and coding separately is suboptimal, and our approach of designing codes for joint synchronization and information transmission achieves better performance, especially at high rates. Therefore, for systems with sparse transmissions such as sensor networks, it is beneficial to adopt the joint sync-coding architecture instead of the traditional separate sync-coding architecture.by Da Wang.S.M