Near-optimum low-complexity lattice quantization

Computationally efficient vector quantization for discrete time sources can be performed by using lattices over linear block codes. For high rates (low distortions) the performance of a multidimensional lattice depends mainly on the normalized second moment (NSM) of the lattice. Well-known optimum or best-known lattices for a given dimension such as the Leech lattice, have rather high encoding complexity which makes them impractical for many applications. We present lattices over tailbiting (TB) convolutional codes and show that in this class of lattices near-optimum NSM values can be achieved using codes over small alphabets and relatively small memories of parent convolutional codes. First, an upper bound on the NSM is obtained by using random coding arguments. This bound is a function of the alphabet size q and the code memory v. It follows from the bound that near-optimum NSM values can be achieved when the code length (lattice dimension) grows while the values q and v are kept constant. Since the encoding complexity depends mainly on v, it means that the encoding complexity for such trellises is a linear function of the lattice dimension. Second, low-complexity high-dimensional lattices with NSM substantially smaller than that of the Leech lattice are constructed. The newly constructed lattices are less than 0.2 dB away from the Zador sphere-packing bound and only 0.3 dB away from ultimate gain equal to 101g(πe/6) = 1.53 dB.