Encoding independent sample information sources.

Abstract

The theory of encoding memoryless information sources so that the output can be transmitted with minimum rate and still satisfy a fidelity criterion based on a single letter distortion measure is investigated. This report extends and amplifies the theory developed by Shannon. A general proof of the Source Coding theorem for memoryless sources and single letter distortion measures is presented using variable length codes. It is shown that this proof is more generally applicable than Shannon's previously derived block coding results; moreover, without some additional restrictions, the coding theorem is false if only block codes are permitted. It is also shown that the convergence of encoder rate to R(D) (the minimum rate necessary to achieve average distortion D) with increasing block length n, can be made at least as fast as (log n)/n. (Author)