Two Results on Interactive Lossless Source Encoding and Decoding with Side Information at the Decoder

A new paradigm called interactive lossless source encoding and decoding is proposed for a source network in which a finite alphabet source $X = {Xi}{i=1}^{infty}$ is to be encoded and transmitted to the decoder, i.e., to be learnt by the decoder without any essential loss, and another finite alphabet source $Y={Yi}{i=1}^{infty}$ correlated with $X$ is available only to the decoder as a helper. In this paradigm, the encoder and decoder are allowed to interact with each other throughout the coding process. The optimal performance achievable asymptotically by interactive lossless source encoding and decoding is then investigated. Here the performance is measured as the average number of bits per symbol exchanged by the encoder and decoder until the decoder learns $X$, which in turn is the sum of the forward rate in bits per symbol from the encoder to the decoder and the feedback rate in bits per symbol from the decoder to the encoder. Two results on interactive lossless encoding and decoding are established. It is first shown that for any stationary source pair $(X, Y)$, whether it is ergodic or not, the optimal performance achievable asymptotically by interactive encoding and decoding is given by the conditional entropy rate $H(X|Y)$ of $X$ given $Y$. This is in contrast with non-interactive lossless source encoding and decoding, i.e., Slepian-Wolf coding, where the optimal performance achievable asymptotically by Slepian-Wolf coding is shown in general to be strictly greater than $H(X|Y)$ when $(X, Y)$ is stationary, but not ergodic. Thus interactive encoding and decoding achieves a first order performance gain over Slepian-Wolf coding when $(X, Y) $ is not ergodic. It is further demonstrated that one can easily convert any classical universal data compression algorithm (with side information available to both the encoder and decoder) to a universal interactive encoding and decoding scheme for the class of all stationary ergodic source pairs (X, Y). Contrasting this result with the well known fact that universal Slepian-Wolf coding algorithms in the sense of achieving asymptotically H(X|Y) for each and every stationary ergodic source pair (X, Y) do not exist, we see that interactive encoding and decoding achieves a universality gain over Slepian-Wolf coding.