Recursive optimal pruning of tree-structured vector quantizers

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