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 $\{(X_i, Y_i)\}_{i=1}^{\infty}$ with finite alphabet, the redundancy $R^n(\epsilon_n)$ of variable rate Slepian–Wolf coding of $X_1^n$ with decoder only side information $Y_1^n$ depends on both the block length $n$ and the decoding block error probability $\epsilon_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 $\epsilon_n$, and the conditional entropy $H(X\vert Y)$, where $H(X\vert Y)$ is the conditional entropy rate of the source given the side information. The redundancy of fixed rate Slepian–Wolf coding of $X_1^n$ with decoder only side information $Y_1^n$ is defined similarly and denoted by $R^n_F(\epsilon_n)$. It is proved that under mild assumptions about $\epsilon_n,$ $R^n(\epsilon_n) = d_v \sqrt{-\log\epsilon_n/n} + o(\sqrt{-\log \epsilon_n/n})$ and $R^n_{F}(\epsilon_n) = d_f \sqrt{- \log \epsilon_n / n} + o(\sqrt{-\log \epsilon_n/n})$, where $d_f$ and $d_v$ are two constants completely determined by the joint distribution of the source-side information pair. Since $d_v$ is generally smaller than $d_f$, our results show that variable rate Slepian–Wolf coding is indeed more efficient than fixed rate Slepian–Wolf coding.