Asymptotic convergence of dual-tree entropy codes

Entropy coding introduces a probabilistic matching at the interface between the discrete-time, finite-alphabet, source model sequence and the discrete-time, finite-alphabet, channel information sequence. Source entropy codes, such as common-string parsers, alter the source statistics to match the given channel. Channel entropy codes, such as Huffman codes, alter the channel statistics to match the given source. These are given a joint, dual description using parse and code trees describing the source and channel word sets. Divergence and variational distance are defined between the source word distribution and the desired channel word distribution. Convergence of any scheme for extending the size of the source word set is demonstrated if the divergence divided by the expected source-word length becomes zero. Huffman channel coding implies an upper bound on divergence in terms of variational distance. This leads to an heuristic algorithm to extend the source word set while keeping the divergence low. Examples show a significant complexity reduction for performance equivalent to Tunstall source coding or Huffman channel coding alone