Optimal source codes for geometrically distributed integer alphabets (Corresp.)

1975/03/01 by Robert G. Gallager, D. van Voorhis · 2 citations
Computer Science · Biochemistry, Genetics and Molecular Biology · #Algorithms and Data Compression #DNA and Biological Computing #Error Correcting Code Techniques

paper · doi:10.1109/tit.1975.1055357

openalex publication_date 1975/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

LetP(i)= (1 - θ)θⁱbe a probability assignment on the set of nonnegative integers where\thetais an arbitrary real number,0 < θ < 1. We show that an optimal binary source code for this probability assignment is constructed as follows. Letlbe the integer satisfyingθ^l + θ^l+1 ≤ 1 < θ^l + θ^l-1and represent each nonnegative integeriasi = lj + rwhenj = \lfloor i/l \rfloor, the integer part ofi/l, andr = [i] mod l. Encodejby a unary code (i.e.,jzeros followed by a single one), and encoderby a Huffman code, using codewords of length\lfloor log₂ l \rfloor, forr < 2^{\lfloor log l+1 \rfloor} - l, and length\lfloor log₂ l \rfloor + 1otherwise. An optimal code for the nonnegative integers is the concatenation of those two codes.

Citations

• A Mathematical Theory of Communication
• A Method for the Construction of Minimum-Redundancy Codes

Cited by

• Code and parse trees for lossless source encoding
• Huffman coding [wikipedia]