Low-density linear IED schemes for lossless source coding with decoder only side information
Jin Meng, En‐hui Yang, Dake He · 2008
In this paper we investigate the performance of linear interactive encoding and decoding (IED) for lossless source coding with decoder only side information. Assume that the source alphabet chi is a finite field and that the side information alphabet is finite. It is shown that there exist universal linear IED schemes which are asymptotically optimal for any stationary, ergodic source-side information pair. Our analysis of low-density IED schemes further reveals that as long as isinnpn*= Omega(log n/n), where isinnand pn*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 Inis concentrated around (|chi|-1)pn*, and the resulting symbol error probability is upper bounded by isinn+ o(isinn).