Improving the redundancy of slepian-Wolf coding by feedback

Abstract

For any memoryless source-side information pair (X; Y ) with finite alphabet, it is well known that the smallest compression rate in bits per letter achievable in Slepian-Wolf coding, i.e., coding X with Y being available only to the decoder, is the conditional entropy H(X|Y ). Though this rate is the same as the best rate achievable in traditional lossless source coding of X with Y being available to both the encoder and the decoder, it has been found recently that the redundancy R<inf>n</inf>(ε<inf>n</inf>) of Slepian-Wolf coding, which is defined as the minimum of the difference between the compression rate of any Slepian- Wolf code resulting from coding Xⁿ<inf>1</inf> with decoding error ε<inf>n</inf>, and H(X|Y ), is significantly worse than that of traditional source coding. In this paper, we investigate whether feedback from the decoder to the encoder can improve the compression efficiency of Slepian-Wolf coding. It turns out that the answer is affirmative. More specifically, it is shown that feedback reduces the redundancy of Slepian-Wolf coding significantly.