A lower bound for variable rate slepian-wolf coding

Abstract

In this paper we analyze the redundancy of variable rate Slepian-Wolf coding. For any memoryless source-side information pair (X, Y) = {(X i, Yi)}i=1∞ with finite alphabet, the redundancy Rn(∈n) of variable rate Sepian-Wolf coding is defined as the minimum of the difference between the compression rate of any variable-rate Slepian-Wolf code resulting from coding X1n with decoding error probability ∈n, and the conditional entropy H(XΙY). It is proved that under mild assumptions, for sufficiently large n, Rn (∈n) is lower bounded by d√/logn/n, where d > 0 is a constant. © 2006 IEEE.