Linear Interactive Encoding and Decoding for Lossless Source Coding With Decoder Only Side Information
Jin Meng, En‐hui Yang, Dake He · IEEE Transactions on Information Theory · 2011
Linear interactive encoding and decoding (IED) for near lossless source coding with decoder only side information is considered, where the interactive encoder uses linear codes (described by parity-check matrices over a finite fieldX) for encoding. It is first demonstrated how to convert any classical universal lossless codeCn(with block lengthnand with side information available to both the encoder and decoder) into a universal random linear IED scheme based on Gallager's parity check ensemble. It is then shown that there is no performance loss by restricting IED to linear IED, and that the universal random linear IED scheme based on Gallager's parity check ensemble achieves essentially the same rate performance as doesCnfor each and every individual sequence pair (xn,yn) while the word decoding error probability goes to 0 asn→ ∞ . Define the density of a linear IED scheme as the percentage of nonzero entries in its parity-check matrix. To reduce the encoding complexity of linear IED, low density linear IED is further investigated in terms of the trade-off among its rate, decoding error probability, and density.