A pruning algorithm of P.A. Chou et al. (1989) for designing optimal tree structures identifies only those codebooks which lie on the convex hull of the original codebook's operational distortion rate function. The authors introduce a modified version of the original algorithm, which identifies a large number of codebooks having minimum average distortion, under the constraint that, in each step, only modes having no descendents are removed from the tree. All codebooks generated by the original algorithm are also generated by this algorithm. The new algorithm generates a much larger number of codebooks in the middle- and low-rate regions. The additional codebooks permit operation near the codebook's operational distortion rate function without time sharing by choosing from the increased number of available bit rates. Despite the statistical mismatch which occurs when coding data outside the training sequence, these pruned codebooks retain their performance advantage over full search vector quantizers (VQs) for a large range of rates.

The generalized BFOS (G-BFOS), a sequential pruning algorithm for designing optimal tree structures, was presented by Chou, Lookabaugh, and Gray (see IEEE Trans. Inf. Theory, vol.35, no.2, p.299, 1989), and it was applied to tree-structured vector quantizers (TSVQ). G-BFOS yields VQ codebooks that often outperform conventional generalized Lloyd full search codebooks having the same rate and block size. The authors have developed a modified version of G-BFOS, called the recursive optimal pruning algorithm (ROPA), which recursively searches for the nodes to be pruned next. The sequence of these pruned codebooks includes the original optimal G-BFOS codebooks and many additional ones. The optimality of these codebooks is described, and simulations evaluate their performance.>