Maximum likelihood decoding of the Leech lattice
IEEE Transactions on Information TheoryPublished 1 July 1993
Alexander Vardy, Y. Be'ery
Citations63
SJR quartileQ1
SJR score1.46
SNIP1.76
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An algorithm for maximum likelihood decoding of the Leech lattice is presented and it is shown that this algorithm is about half the worst case and the average complexity of the best previously known algorithm.
Abstract
An algorithm for maximum likelihood decoding of the Leech lattice is presented. The algorithm involves projecting the points of the Leech lattice directly onto the codewords of the (6,3,4) quaternary code-the hexacode. Projection on the hexacode induces a partition of the Leech lattice into four cosets of a certain sublattice 24. Such a partition into cosets enables maximum likelihood decoding of the Leech lattice with 3595 real operations in the worst case and only 2955 operations on the average. This is about half the worst case and the average complexity of the best previously known algorithm.>
Keywords
Computer Science
IEEE Transactions on Information TheoryChannel coding with multilevel/phase signals
3,738 Citations1982G. Ungerboeck
A coding technique is described which improves error performance of synchronous data links without sacrificing data rate or requiring more bandwidth by channel coding with expanded sets of multilevel/phase signals in a manner which increases free Euclidean distance.
Grundlehren der mathematischen WissenschaftenSphere Packings, Lattices and Groups
1,507 Citations1988John H. Conway, N. J. A. Sloane
IEEE Journal on Selected Areas in CommunicationsEfficient Modulation for Band-Limited Channels
715 Citations1984G. David Forney, Robert G. Gallager +3 more
This paper attempts to present a comprehensive tutorial survey of the development of efficient modulation techniques for bandlimited channels, such as telephone channels, with principal emphasis on coded modulation techniques, in which there is an explosion of current interest.
IEEE Transactions on Information TheoryCoset codes. II. Binary lattices and related codes
654 Citations1988G. David Forney
The family of Barnes-Wall lattices and their principal sublattices, which are useful in constructing coset codes, are generated by iteration of a simple construction called the squaring construction, and are represented by trellis diagrams that display their structure and interrelationships and that lead to efficient maximum-likelihood decoding algorithms.
IEEE Transactions on Information TheoryCoset codes. I. Introduction and geometrical classification
614 Citations1988G. David Forney
The known types of coset codes, as well as a number of new classes that systematize and generalize known codes, are classified and compared in terms of these parameters.
IEEE Transactions on Information TheoryVoronoi regions of lattices, second moments of polytopes, and quantization
323 Citations1982J. Conway, N. J. A. Sloane
The answers to the squared distance questions and a description of the Voronoi (or nearest neighbor) regions of these lattices have applications to quantization and to the design of signals for the Gaussian channel.
IEEE Transactions on Information TheoryNew trellis codes based on lattices and cosets
236 Citations1987A.R. Calderbank, N. J. A. Sloane
A new technique is proposed for constructing trellis codes which provides an alternative to Ungerboeck's method of "set partitioning" and several of the new codes are better than those previously known.
IEEE Transactions on Information TheorySoft decoding techniques for codes and lattices, including the Golay code and the Leech lattice
165 Citations1986J. Conway, N. J. A. Sloane
Ami are used to obtain new and faster decoding algorithms for the Gosset lattice E_{8} , the Golay code the Leech lattice and some general methods are given for constructing such algorithms.
IEEE Transactions on Information TheoryTables of sphere packings and spherical codes
142 Citations1981N. J. A. Sloane
The theta functions of a number of important packings and tables of the first fifty or so of their coefficients are given in this paper.
Mathematical Proceedings of the Cambridge Philosophical SocietyA new combinatorial approach to <i>M</i><sub>24</sub>
122 Citations1976Robert T. Curtis
IEEE Transactions on Information TheoryMaximum likelihood soft decoding of binary block codes and decoders for the Golay codes
112 Citations1989J. Snyders, Y. Be'ery
A binary multiple-check generalization of the Wagner rule is presented, and two methods for its implementation, one of which resembles the suboptimal Forney-Chase algorithms, are described.
IEEE Journal on Selected Areas in CommunicationsSome optimal codes have structure
111 Citations1989R. de Buda
It is demonstrated that optimal codes need not be random, but rather that some of them have structure, e.g. the structure of a lattice code.
SIAM Journal on Algebraic and Discrete MethodsOn the Voronoi Regions of Certain Lattices
89 Citations1984John H. Conway, N. J. A. Sloane
IEEE Journal on Selected Areas in CommunicationsA Leech lattice modem
89 Citations1989G.R. Lang, F.M. Longstaff
A 24-dimensional block code based on the Leech lattice is described for use in a 19200-b/s modem and encoding plus decoding was successfully programmed for an ADSP2100 signal processor requiring altogether slightly less than one half the processing capability.
IEEE Transactions on Information TheoryDecoding the Golay codes
65 Citations1986Vera Pless
This work introduces exceptionally simple decoding algorithms for the two extended Golay codes based on recent methods of Conway and Curtis of finding the unique blocks containing five points in either the (5,8,24) Steiner system or the ( 5,6,12) Steiners system.
IEEE Transactions on Information TheoryA bounded-distance decoding algorithm for the Leech lattice, with generalizations
62 Citations1989G. David Forney
An algorithm is given that decodes the Leech lattice with not much more than twice the complexity of soft-decision decoding of the Golay code, and is readily generalized to lattices that can be expressed in terms of binary code formulas.
IEEE Transactions on Information TheoryMore efficient soft decoding of the Golay codes
60 Citations1991Alexander Vardy, Y. Be'ery
IEEE Journal on Selected Areas in CommunicationsFast decoding of the Leech lattice
39 Citations1989Y. Be'ery, B. Shahar +1 more
An efficient algorithm is presented for maximum-likelihood soft-decision decoding of the Leech lattice and seems to achieve a computational complexity comparable to that of the equivalent trellis codes.
IEEE Transactions on Information TheoryNearest neighbor algorithm for spherical codes from the Leech lattice
24 Citations1988J.-P. Adoul, Matthew Barth
A nearest-neighbor algorithm that works on this is developed to determine the point in the code closet to some arbitrary vector in R/sup 24/.