Near lossless source coding with side information at the decoder: Beyond conditional entropy

Abstract

In near lossless source coding with decoder only side information, i.e., Slepian-Wolf coding (with one encoder), a source X with finite alphabet x is first encoded, and then later decoded subject to a small error probability with the help of side information Y with finite alphabet y available only to the decoder. The classical result by Slepian and Wolf shows that the minimum average compression rate achievable asymptotically subject to a small error probability constraint for a memoryless pair (X, Y) is given by the conditional entropy H(X|Y). In this paper, we look beyond conditional entropy and investigate the tradeoff between compression rate and decoding error spectrum in Slepian-Wolf coding when the decoding error probability goes to zero exponentially fast. It is shown that when the decoding error probability goes to zero at the speed of 2-δn, where δ is a positive constant and n denotes the source sequences' length, the minimum average compression rate achievable asymptotically is strictly greater than H(X\Y) regardless of how small 5 is. More specifically, the minimum average compression rate achievable asymptotically is lower bounded by a quantity called the intrinsic conditional entropy Hin(X\Y, δ), which is strictly greater than H(X\Y), and is also asymptotically achievable for small δ.