Indexing algorithms for Zn, An, Dn, and Dn++ lattice vector quantizers

This paper describes vector indexing algorithms valid for a large class of lattices (Z_n, A_n, D_n, and D _n⁺⁺ including as special cases the Gosset (E₈ ) and Barnes-Wall (Λ₁₆ⁿ) lattices), widely used in audio-visual signal compression. The indexing mechanism relies on reverse lexicographic ordering of the vectors, in classes of equivalence defined as sets of vectors obtained by "signed" permutations of the components of initial vectors called leaders. The approach makes it possible to trade the size of the lookup tables-or codebooks-for arithmetic operations. The reduction of codebook sizes leads in turn to reduced encoder and decoder complexities. Pursuing the goal of best tradeoff between storage requirements and arithmetic complexity, two algorithms, based on the proposed indexing mechanisms, allowing "on-the-fly" generation of adaptive portions of codebooks are then described. These algorithms make it possible to overcome the problems of lattice truncating usually encountered in lattice vector quantization (LVQ). Combined with product codes, these indexing techniques lead to increased compression performances