On a partial ordering relation derived from redundancy of Slepian-Wolf coding

Let (X, Y) denote a pair of finite-valued random variables. In this paper we use two examples to show an inherent partial ordering relation among the set {PY|X : H(X\Y) = α} where PY|X denotes the channel from X to Y, and 0 ≤ α ≤ H(X) is a constant. Specifically, we consider the following cases: the channel from X to Y is either a binary symmetric channel (BSC) or a binary erasure channel (BEC). In each case, we characterize the redundancy of Slepian-Wolf coding of X with decoder only side information Y. It is thus revealed that for any binary X and 0 < α < H(X), under the condition that H(X|Y) = α the redundancy of the BSC case is strictly larger than that of the BEC case for a range of decoding error probabilities. Interestingly, our results also reveal that the redundancy of variable-rate Slepian-Wolf coding is generally better than that of fixed-rate Slepian-Wolf coding. ©2007 IEEE.