Network Source Coding in Scenarios with Uncertainty at the Decoder

In this thesis, I investigate four network source coding problems in scenarios with uncertainty at the decoder. In network communications, uncertainty may arise from both extrinsic forces such as a noisy environment and intrinsic forces such as the choices of participating agents. For example, both imperfect coordination capabilities and deliberate removal of synchronization requirements lead to uncertainty about the relative timing of messages from different communicators. Similarly, errors in source code reconstructions can arise either due to channel code failure or because compression algorithms are designed to tolerate a certain amount of error for the sake of improving rate or latency. Since distributed source codes have the potential to benefit from source dependencies but these dependencies may be damaged or destroyed by prior source coding decisions, the existence of reconstruction errors is another potential source of uncertainty in network communications. My thesis investigates the performance of communication systems under uncertainties that include the examples described above. I first propose an asynchronous random access source code (ARASC) and present bounds on its performance. In traditional random access source codes (RASCs), the source blocks from different terminals are aligned, meaning that the codeword transmissions begin and end at the same time. ARASC removes the synchronization constraint, allowing each encoder to encode and start a codeword transmission any time it has available information to describe and the channel is idle. In this work, I show that ARASC can take advantage of source dependence without enforcing synchrony; I propose an ARASC algorithm, bound the second-order rate of the proposed strategy, and show simulation results that explore the performance tradeoffs between RASC and ARASC. I then introduce the problem of source coding with unreliable side information. This problem models the scenario where a decoder is tasked with reconstructing a source with the help of side information that is not necessarily reliable. I propose a code that uses a 2-stage decoding strategy that prevents the uncertainty in the side information from damaging the reliability of the source reconstruction while taking advantage of the side information. I next present bounds on the performance of an almost lossless point-to-point source code in scenarios where the description from the given code is later used to aid the description of another dependent source. I demonstrate that, even under strict efficiency and reliability constraints, point-to-point source codes are not equally powerful when the decoder outputs are used as side information to help a downstream user decode a dependent source, and the difference is big enough to affect the downstream user in a significant way. I show the full range of possible performances and prove that the designer of the point-to-point code can control where on the spectrum, from the least to the most helpful, the reconstruction is expected to be. Furthermore, I show that, if the designer wishes to provide more information rather than less about a dependent source to a downstream user through the source reconstruction, they can do so without observing the joint distribution with the later source. As a step towards practicality, I also show that it is possible to generate a linear point-to-point code that is helpful to later users if the designer accepts a small rate penalty. Finally, I present the performance of a random binning source code when the source reconstruction from that code is used as an input to a distributed hypothesis test. I show that random binning generates a source code whose codeword serves simultaneously as a source description and as an input to a distributed hypothesis test that seeks to determine whether the coded source is independent of or dependent on side information available to the decoder. The given random binning code can serve these dual roles without significantly worsening the source coding rate. When the joint distribution between sources is uncertain, such a code offers a way to distinguish between possible joint distributions and to decode only if the source description rate and hypothesis regarding dependency together render decoding appropriate. I also discuss the implications of such a hypothesis test on the statistics of the random binning code output, analyze the statistics through an alternative route that involves direct analysis of the random binning code, and compare the results.