VARIABLE-RATE TREE-STRUCTURED VECTOR QUANTIZERS

In general, growth algorithms for optimal tree-structured vector quant izers do not exist. In this paper we show that if the source satisfies certain conditions; namely, that of diminishing marginal returns; opt imal growth algorithms do exist. We present such an algorithm and comp are its performance with that of other tree growth algorithms. Even fo r sources that do not meet the necessary conditions for the growth alg orithm to be optimal, such as for speech with unknown statistics, it i s seen by simulation that the algorithm outperforms other known growth algorithms. For sources that do not satisfy the required conditions, the algorithm presented here can also be used to grow the initial tree for the pruning process. The performance of Such pruned trees is supe rior to that of trees pruned from full trees of the same rate.