Linear block source coding for binary memoryless sources

Abstract

Traditional block source coding theory has primarily focused on binary memoryless sources (BMS) with equiprobable symbols, where cosets of the source-encoding standard array are equally likely. This thesis introduces a simple yet powerful model for general asymmetric BMS, enabling exact computation of coset probabilities. The model reveals that even for asymmetric sources, coset probabilities rapidly converge to a uniform distribution. This insight allows a reevaluation of the role of minimum distance in block source codes, leading to source-coding analogs of several well-known bounds. A novel and simplified proof of the linear block source coding theorem is presented, leveraging relationships between the Gilbert bound and the rate-distortion bound. Furthermore, a universal source coding theorem is established for linear block coding of arbitrary BMS. Extensions to binary Markov sources are briefly explored, including burst-correcting and run-length coding schemes.