Interval algorithm for homophonic coding

It is shown that the idea of the successive refinement of interval partitio ns, which plays the key role in the interval algorithm for random number ge neration by Han and Hoshi, is also applicable to the homophonic coding. An interval algorithm for homophonic coding is introduced which produces an in dependent and identically distributed (i.i.d.) sequence with probability p, Lower and upper bounds for the expected codeword length are given. Based o n this, an interval algorithm for fixed-to-variable homophonic coding is es tablished, The expected codeword length per source letter converges to H(X) / H(p) in probability as the block length tends to infinity, where H(X) is the entropy rate of the source X. The algorithm is asymptotically optimal. An algorithm for fixed-to-fixed homophonic coding is also established. The decoding error probability tends to zero as the block length tends to infi nity. Homophonic coding with cost is generally considered. The expected cos t of the codeword per source letter converges to (c) over bar (X) / H (p) i n probability as the block length tends to infinity, where (c) over bar den otes the verage cost of a source letter. The main contribution of this pape r can be regarded as a novel application of Elias' coding technique to homo phonic coding. Intrinsic relations among these algorithms, the interval alg orithm for random number generation and the arithmetic code are also discus sed.