Hash Property and Fixed-Rate Universal Coding Theorems
Jun Muramatsu, Shigeki Miyake · IEEE Transactions on Information Theory · 2010
The aim of this paper is to prove the fixed-rate universal coding theorems by using the notion of the hash property. These theorems are the fixed-rate lossless universal source coding theorem and the fixed-rate universal channel coding theorem. Since an ensemble of sparse matrices (with logarithmic column degree) satisfies the hash property requirement, it is proved that we can construct universal codes by using sparse matrices.