CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Closest point search in lattices

Erik Agrell (Institutionen för signaler och system, Kommunikationssystem) ; Thomas Eriksson (Institutionen för signaler och system, Kommunikationssystem) ; Alexander Vardy ; Kenneth Zeger
IEEE Transactions on Information Theory (0018-9448 ). Vol. 48 (2002), 8, p. 2201-2214.
[Artikel, refereegranskad vetenskaplig]

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.

Nyckelord: source-coding, error-control



Denna post skapades 2006-09-12. Senast ändrad 2016-08-18.
CPL Pubid: 14990

 

Läs direkt!

Lokal fulltext (fritt tillgänglig)

Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för signaler och system, Kommunikationssystem

Ämnesområden

Information Technology

Chalmers infrastruktur