Universal multiterminal source coding algorithms with asymptotically zero feedback: Fixed database case

Abstract

Consider a source network in which a finite alphabet source X = {Xi}i=0∞ is to be encoded and transmitted, and another finite alphabet source Y = {Yi}i=0∞ correlated with X is available only to the decoder as side information. Traditionally, the channel between the encoder and decoder in the source network is assumed to be one-way. This, together with the fact that the encoder does not have access to Y, implies that the encoder has to know the achievable rates before encoding. In this paper, we consider universal source coding for a feedback source network in which the channel between the encoder and decoder is two-way and asymmetric. Assume that the encoder and decoder share a random database that is independent of both X and Y. A string matching-based (variable-rate) block coding algorithm with simple progressive encoding and joint typicality decoding is first proposed for the feedback source network. The simple progressive encoder does not need to know the achievable rates at the beginning of encoding. It is proven that for any (X, Y) in a large class of sources satisfying some mixing conditions, the average number of bits per letter transmitted from the encoder to the decoder (compression rate) goes to the conditional entropy H(X Y) of X given Y asymptotically, and at the same time the average number of bits per letter transmitted from the decoder to the encoder (feedback rate) goes to 0 asymptotically. The algorithm and the corresponding analysis results are then extended to the case where both X and Y are to be encoded separately, but decoded jointly. Finally, a universal decoding algorithm is proposed to replace the joint typicality decoding, and the resulting universal compression algorithm consisting of the simple progressive encoder and the universal decoding algorithm is further shown to be asymptotically optimal for the class of all jointly memoryless source-side information pairs (X, Y). © 2008 IEEE.