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

Let P (i) = (1 -) ⁱ be a probability assignment on the set of nonnegative integers where is an arbitrary real number, 0. We show that an optimal binary source code for this probability assignment is constructed as follows. Let l be the integer satisfying ˡ + ^l+1 1 and represent each nonnegative integer i as i = lj + r when j = i/l, the integer part of i/l, and r = i mod l. Encode j by a unary code (i. e. , j zeros followed by a single one), and encode r by a Huffman code, using codewords of length ₂ l, for r, and length ₂ l + 1 otherwise. An optimal code for the nonnegative integers is the concatenation of those two codes.