On the Redundancy of Slepian–Wolf Coding

Dake He, L. A. Lastras-Montaño, En‐hui Yang, Ashish Jagmohan, Jun Chen

IEEE Transactions on Information Theory · 2009 · 59 citations · 16 references

Concepts

Abstract

<para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> In this paper, the redundancy of both variable and fixed rate Slepian–Wolf coding is considered. Given any jointly memoryless source-side information pair <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$\{(X_i, Y_i)\}_{i=1}^{\infty}$</tex></formula></emphasis> with finite alphabet, the redundancy <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">$R^n(\epsilon_n)$</tex></formula></emphasis> of variable rate Slepian–Wolf coding of <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$X_1^n$</tex></formula></emphasis> with decoder only side information <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">$Y_1^n$</tex></formula></emphasis> depends on both the block length <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">$n$</tex></formula></emphasis> and the decoding block error probability <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">$\epsilon_n$</tex></formula></emphasis>, and is defined as the difference between the minimum average compression rate of order <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$n$</tex> </formula></emphasis> variable rate Slepian–Wolf codes having the decoding block error probability less than or equal to <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$\epsilon_n$</tex></formula></emphasis>, and the conditional entropy <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">$H(X\vert Y)$</tex></formula></emphasis>, where <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$H(X\vert Y)$</tex></formula></emphasis> is the conditional entropy rate of the source given the side information. The redundancy of fixed rate Slepian–Wolf coding of <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$X_1^n$</tex></formula></emphasis> with decoder only side information <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$Y_1^n$</tex> </formula></emphasis> is defined similarly and denoted by <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$R^n_F(\epsilon_n)$</tex></formula></emphasis>. It is proved that under mild assumptions about <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$\epsilon_n,$</tex></formula></emphasis> <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$R^n(\epsilon_n) = d_v \sqrt{-\log\epsilon_n/n} + o(\sqrt{-\log \epsilon_n/n})$</tex></formula></emphasis> and <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$R^n_{F}(\epsilon_n) = d_f \sqrt{- \log \epsilon_n / n} + o(\sqrt{-\log \epsilon_n/n})$</tex></formula></emphasis>, where <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$d_f$</tex> </formula></emphasis> and <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">$d_v$</tex></formula></emphasis> are two constants completely determined by the joint distribution of the source-side information pair. Since <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$d_v$</tex> </formula></emphasis> is generally smaller than <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$d_f$</tex></formula></emphasis>, our results show that variable rate Slepian–Wolf coding is indeed more efficient than fixed rate Slepian–Wolf coding. </para>

References

16