String matching-based universal source codes for source networks with asymptotically zero feedback

Abstract

Consider a source network in which a finite alphabet source X = {X i}i=0∞ is to be encoded and transmitted, and another finite alphabet source Y = {Yi}i=0∞ available only to the decoder as the side information correlated with X. Traditionally the channel between the encoder and decoder in the source network is assumed to be one-way. This, together with that the encoder does not have access to Y, necessitates that the encoder knows 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. Assuming that the encoder and decoder share a random database that is independent of both X and Y, we propose a string matching-based (variable-rate) block coding algorithm with a simple progressive encoder for the feedback source network. This algorithm 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 which includes the class of all memoryless sources, the class of all aperiodic Markov sources, and a large class of finite-state sources as special subclasses, the average number of bits per letter transmitted from the encoder to the decoder (compression rate) goes arbitrarily close to the conditional entropy H(X|Y) of X given Y asymptotically, and the average number of bits per letter transmitted from the decoder to the encoder (feedback rate) goes to 0 asymptotically.