TY - JOUR

T1 - Enumeration of lattice points in l1 norm

AU - Serra-Sagristà, Joan

PY - 2000/11/20

Y1 - 2000/11/20

N2 - The enumeration of lattice points is receiving much attention because the use of lattices as vector quantizers in several applications, as for instance still image and video compression, has grown increasingly in the last few years. In image coding applications there is a trade-off between minimum distortion and bit rate, therefore, lattices have to be truncated so that the chosen lattice points, the codebook size, lie within a finite boundary. The determination of this boundary is source dependent. The geometric properties of a memoryless Laplacian source fit properly to model transform coded image statistics. In this case, the l1 norm is more suitable than the l2 norm for enumerating lattice points. In this paper we define the contour points, which count how many lattice points are at l1 distance m from a given lattice point; i.e., they help to establish the lattice boundary or equivalently the codebook size. Explicit combinatorial expressions for the contour points determining the codebook size are given for some of the most used lattices. These expressions are easily implementable in any standard general-purpose programming language. In addition, they pave the way for developing algorithms for labeling lattice points that achieve full efficiency without any memory requirement at all.

AB - The enumeration of lattice points is receiving much attention because the use of lattices as vector quantizers in several applications, as for instance still image and video compression, has grown increasingly in the last few years. In image coding applications there is a trade-off between minimum distortion and bit rate, therefore, lattices have to be truncated so that the chosen lattice points, the codebook size, lie within a finite boundary. The determination of this boundary is source dependent. The geometric properties of a memoryless Laplacian source fit properly to model transform coded image statistics. In this case, the l1 norm is more suitable than the l2 norm for enumerating lattice points. In this paper we define the contour points, which count how many lattice points are at l1 distance m from a given lattice point; i.e., they help to establish the lattice boundary or equivalently the codebook size. Explicit combinatorial expressions for the contour points determining the codebook size are given for some of the most used lattices. These expressions are easily implementable in any standard general-purpose programming language. In addition, they pave the way for developing algorithms for labeling lattice points that achieve full efficiency without any memory requirement at all.

U2 - https://doi.org/10.1016/S0020-0190(00)00119-8

DO - https://doi.org/10.1016/S0020-0190(00)00119-8

M3 - Article

VL - 76

SP - 39

EP - 44

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

ER -