Finite Block Length Rate-Distortion Theory for the Bernoulli Source with Hamming Distortion: A Tutorial
2026-02-27 • Information Theory
Information Theory
AI summaryⓘ
The authors explain how data compression works when you want to reduce file size but still keep it close to the original. They focus on a simple example where data is just a sequence of zeros and ones, measuring errors by how many bits are different. They start with the classic formula showing the best possible compression for very long files, then show how real, shorter files behave differently. They introduce a concept called rate-distortion dispersion to describe how much extra space is needed for shorter blocks. The paper includes clear examples and Python code to help understand the math.
Lossy data compressionRate-distortion theoryBernoulli sourceHamming distortionShannon limitBlahut-Arimoto algorithmFinite block lengthRate-distortion dispersionInformation theoryData compression
Authors
Bhaskar Krishnamachari
Abstract
Lossy data compression lies at the heart of modern communication and storage systems. Shannon's rate-distortion theory provides the fundamental limit on how much a source can be compressed at a given fidelity, but it assumes infinitely long block lengths that are never realized in practice. We present a self-contained tutorial on rate-distortion theory for the simplest non-trivial source: a Bernoulli$(p)$ sequence with Hamming distortion. We derive the classical rate-distortion function $RD = Hp - HD$ from first principles, illustrate its computation via the Blahut-Arimoto algorithm, and then develop the finite block length refinements that characterize how the minimum achievable rate approaches the Shannon limit as the block length $n$ grows. The central quantity in this refinement is the \emph{rate-distortion dispersion} $V(D)$, which governs the $O(1/\sqrt{n})$ penalty for operating at finite block lengths. We accompany all theoretical developments with numerical examples and figures generated by accompanying Python scripts.