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

LetP(i)= (1 - \theta)\theta^ibe a probability assignment on the set of nonnegative integers where\thetais an arbitrary real number,0 < \theta < 1. We show that an optimal binary source code for this probability assignment is constructed as follows. Letlbe the integer satisfying\theta^l + \theta^{l+1} \leq 1 < \theta^l + \theta^{l-1}and 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_2 l \rfloor, forr < 2^{\lfloor \log l+1 \rfloor} - l, and length\lfloor \log_2 l \rfloor + 1otherwise. An optimal code for the nonnegative integers is the concatenation of those two codes.