Linear interactive encoding and decoding schemes for lossless source coding with decoder only side information

Near lossless source coding with side information only at the decoder, was first considered by Slepian and Wolf in 1970s, and rediscovered recently due to applications such as sensor network and distributed video coding. Suppose X is a source and Y is the side information. The coding scheme proposed by Slepian and Wolf, called SW coding, in which information only flows from the encoder to the decoder, was shown to achieve the rate H(X|Y) asymptotically for stationary ergodic source pairs. As H(X|Y) is the minimum achievable rate even if the encoder is informed of the side information Y, this implies the optimality of SW coding for any stationary ergodic source-side information pairs. However, it is shown by Yang and He that SW coding can not achieve this rate for most of non-ergodic source-side information pairs.;The results reviewed above show that IED schemes are much more appealing than SW coding schemes to applications where the interaction between the encoder and the decoder is possible. However, the IED schemes proposed by Yang and He do not have an intrinsic structure that is amenable to design and implement in practice. Towards practical design, we restrict the encoding method to linear block codes, resulting in linear IED schemes. It is then shown that this restriction will not undermine the asymptotic performance of IED, in the sense that a sequence of linear IED schemes can be always found for any stationary ergodic source-side information pair (X, Y) to achieve the rate of conditional entropy H(X| Y). Moreover, the result can also be extended to non-ergodic source-side information pairs.;Another step of practical design of IED schemes is to make the computational complexity incurred by encoding and decoding feasible. In the framework of linear IED, a scheme can be conveniently described by parity check matrices. It can be easily observed that density of these matrices (measured as the average number of non-zero entries) is directly related to the scheme's encoding and decoding complexity: the complexity increases as the density increases. Further, we get an interesting trade-off between the density of the associated parity check matrices and the resulting symbol error probability. Our analysis reveals that as long as enp*n = O(log n/n), where epsilonn and p*n are real numbers, one can always construct a sequence of universal linear IED schemes { In } such that the average density of the parity check matrices associated with In is concentrated around (| X | -- 1) p*n , and the resulting symbol error probability is upper bounded by epsilon n+o(epsilonn). In addition, if some modification applies to linear IED schemes, it can be shown that p*n can be as low as lognn while the symbol error probability goes to zero asymptotically.;To implement the idea of linear IED and follow the instinct provided by the result above, Low Density Parity Check (LDPC) codes and Belief Propagation (BP) decoding are utilized. Considering incremental encoding is needed in IED, a successive LDPC code based on syndrome splitting is proposed, and the splitting rule is optimized according to density evolution results. Moreover, as existing BP decoding algorithms can only apply to limited kinds of correlation between the source X and the side information Y, a new BP decoding algorithm is proposed, which applies to the case where the correlation between Y and X can be modelled as a finite state channel. It then can be shown that the existing BP algorithms, which apply to hidden Markov state channels, such as GE channels and Markov Modulated Channels, are the special cases of this new algorithm. Finally, simulation results show that linear IED schemes are indeed superior to SW coding schemes.;Recently, a new source coding paradigm called interactive encoding and decoding (IED) was proposed for near lossless coding with side information only at the decoder. In such paradigm, information flows in both ways, from the encoder to the decoder and vice verse, and the behaviour of the encoder also relies on the bits sent back from the decoder. The compression rate of an IED scheme is defined as average number of bits per symbol exchanged between the encoder and the decoder. In contrary to SW coding, IED can achieve the rate of H(X|Y) for any stationary source-side information pairs, ergodic or not. Also it was shown that for memoryless source-side information pairs, IED schemes achieve better redundancy performance than SW coding schemes. And universal IED can be built coupled with classical universal codes for any stationary ergodic source-side information pairs, while it is well known that there does not exist a universal SW coding scheme.