Fast Generation of Tunstall Codes

Let a binary memoryless source assign positive probabilities p, q to the binary letters 0,1 (respectively), where p ges q, and let t = log₂ q/ log₂ p. There is a well-known incremental algorithm due to B. Tunstall which, for each positive integer n, constructs the coding tree of the n codeword Tunstall code for the source. We present a faster incremental algorithm which constructs the n codeword Tunstall coding tree from the first k_nmiddot terms of the rotation sequence {lflooriTrfloor}^infin _i=1, where k_n rarr infin very slowly as n rarr infin.