%0 Journal Article
%T Hash Property and Coding Theorems for Sparse Matrices and Maximum-Likelihood Coding
%A Jun Muramatsu
%A Shigeki Miyake
%J Mathematics
%D 2008
%I arXiv
%X The aim of this paper is to prove the achievability of several coding problems by using sparse matrices (the maximum column weight grows logarithmically in the block length) and maximal-likelihood (ML) coding. These problems are the Slepian-Wolf problem, the Gel'fand-Pinsker problem, the Wyner-Ziv problem, and the One-helps-one problem (source coding with partial side information at the decoder). To this end, the notion of a hash property for an ensemble of functions is introduced and it is proved that an ensemble of $q$-ary sparse matrices satisfies the hash property. Based on this property, it is proved that the rate of codes using sparse matrices and maximal-likelihood (ML) coding can achieve the optimal rate.
%U http://arxiv.org/abs/0801.3878v2