Problems in compression, transmission and storage of correlated sources

This dissertation studies certain problems in compression, transmission and storage of correlated sources. The first problem considered is lossy compression under a maximum distortion constraint when the decoder has access to side-information in the form of a random sequence correlated with the source data. Using a combinatorial framework, a non-single letter expression for the minimum asymptotic average rate as well as single letter bounds on this rate are derived. Combinatorial conditions for coincidence of these bounds are also studied.; In the second scenario, perfect reconstruction of the source is required, but the encoder and decoder only have partial knowledge of the joint distribution between the source and the side-information: although they know the set of joint distributions the pair of correlated sources could correspond to, neither knows the exact element of the set that characterizes the observations. For this scenario, the minimum asymptotic rate for both fixed length as well as variable length codes are characterized. Further, the capacity of the dual channel for the source coding scenario, the compound channel, is shown to the Sperner capacity of a set of directed graphs associated with the channel. The capacities when either the decoder or encoder has side-information regarding the channel are also characterized.; The next scenario is joint source-channel coding where the decoder has side-information about the source and both terminals are aware of the joint distribution of the source-side-information pair. If zero-error transmission is required, it is shown that separate source and channel coding is asymptotically suboptimal and further that the gains from joint-source channel coding can be arbitrarily large. Sufficient conditions for separate coding to be optimal are derived. Some results on the computational complexity of designing joint source-channel codes are also discussed.; Databases often contain data that is correlated. Therefore, one way to reduce the storage cost is to jointly compress all the data. However, this can result in a penalty in terms of the time taken to retrieve subsets of the data at some later point in time. In this dissertation, the problem of noiseless (in the Shannon sense) storage of correlated data is formulated and the tradeoff between storage and retrieval is studied. On analyzing this tradeoff, the storage problem is seen to be a special case of another problem, called the shared descriptions problem. By deriving achievable rate regions for the shared descriptions scenario, the storage vs. retrieval tradeoff is characterized.