On the redundancy of Slepian-Wolf coding

In this paper, the redundancy of both variable and fixed rate Slepian-Wolf coding is considered. Given any jointly memoryless source-side information pair { (Xi, Yi)}∞ i=1 with finite alphabet, the redundancy Rn ( εn ) of variable rate Slepian-Wolf coding of X1n with decoder only side information Y1n depends on both the block length n and the decoding block error probability εn, and is defined as the difference between the minimum average compression rate of order n variable rate Slepian-Wolf codes having the decoding block error probability less than or equal to εn, and the conditional entropy H (X|Y), where H (X|Y) is the conditional entropy rate of the source given the side information. The redundancy of fixed rate Slepian-Wolf coding of X1n with decoder only side information Y1n is defined similarly and denoted by RFn( εn ). It is proved that under mild assumptions about εn, Rn( εn ) = dv √ - log εn/n + o(√ -log εn/n and RFn( εn ) = df √ -log εn/n + o( √ -log εn/n, where df and dv are two constants completely determined by the joint distribution of the source-side information pair. Since dv is generally smaller than df, our results show that variable rate Slepian-Wolf coding is indeed more efficient than fixed rate Slepian-Wolf coding. © 2009 IEEE.