Fast Generation of Tunstall Codes
John C. Kieffer · 2007
Let a binary memoryless source assign positive probabilities p, q to the binary letters 0,1 (respectively), where p ges q, and let t = log2q/ log2p. 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 knmiddot terms of the rotation sequence {lflooriTrfloor}infini=1, where knrarr infin very slowly as n rarr infin.