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

著者: Robert G. Gallager, David C. van Voorhis - IEEE Transactions on Information Theory, TIT 1975 被引用: 233

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