| 1. |
- Agrell, Erik, 1965, et al.
(författare)
-
Closest point search in lattices
- 2002
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448 .- 1557-9654. ; 48:8, s. 2201-2214
-
Tidskriftsartikel (refereegranskat)abstract
- In this semitutorial paper, a comprehensive survey of closest point search methods for lattices without a regular structure is presented. The existing search strategies are described in a unified framework, and differences between them are elucidated. An efficient closest point search algorithm, based on the Schnorr-Euchner variation of the Pohst method, is implemented. Given an arbitrary point x is an element of R-m and a generator matrix for a lattice A, the algorithm computes the point of A that is closest to x. The algorithm is shown to be substantially faster than other known methods, by means of a theoretical comparison with the Kannan algorithm and an experimental comparison with the Pohst algorithm and its variants, such as the recent Viterbo-Boutros decoder. Modifications of the algorithm are developed to solve a number of related search problems for lattices, such as finding a shortest vector, determining the kissing number, computing the Voronoi-relevant vectors, and finding. a Korkine-Zolotareff reduced basis.
|
|
| 2. |
|
|
| 3. |
|
|
| 4. |
- Agrell, Erik, 1965, et al.
(författare)
-
Optimization of lattices for quantization
- 1998
-
Ingår i: IEEE Transactions on Information Theory. - : Institute of Electrical and Electronics Engineers (IEEE). - 0018-9448 .- 1557-9654. ; 44:5, s. 1814-1828
-
Tidskriftsartikel (refereegranskat)abstract
- A training algorithm for the design of lattices for vector quantization is presented. The algorithm uses a steepest descent method to adjust a generator matrix, in the search for a lattice whose Voronoi regions have minimal normalized second moment. The numerical elements of the found generator matrices are interpreted and translated into exact values. Experiments show that the algorithm is stable, in the sense that several independent runs reach equivalent lattices. The obtained lattices reach as low second moments as the best previously reported lattices, or even lower. Specifically, we report lattices in nine and ten dimensions with normalized second moments of 0.0716 and 0.0708, respectively, and nonlattice tessellations in seven and nine dimensions with 0.0727 and 0.0711, which improves on previously known values. The new nine- and ten-dimensional lattices suggest that Conway and Sloane's (1993) conjecture on the duality between the optimal lattices for packing and quantization might be false. A discussion of the application of lattices in vector quantizer design for various sources, uniform and nonuniform, is included.
|
|
| 5. |
|
|
