Linear block source coding for binary memoryless sources

Abstract

Despite the existence of well-defined rate-distortion functions for general binary memoryless sources (BMS), block source coding theory has traditionally been restricted to sources with equiprobable symbols, in which case the cosets of the source-encoding standard array are equally likely. In this thesis, we develop a simple yet powerful model for the general asymmetric BMS, which leads to an exact computation of the coset probabilities. The model shows that even for asymmetric BMS, the coset probabilities rapidly converge to a uniform distribution. In light of this model, the role played by the minimum distance of block source codes is reviewed. Source-coding analogs of several well-known minimum-distance bounds are obtained. Using some relationships between the Gilbert bound and the rate-distortion bound, a new and very simple proof is provided for the linear block source coding theorem. A universal source coding theorem is established for linear block coding of arbitrary BMS. Finally, some extensions to binary Markov sources are considered. A burst-correcting block coding scheme and a run-length coding scheme are briefly examined.