Soft decoding techniques for codes and lattices, including the Golay code and the Leech lattice
IEEE Transactions on Information TheoryPublished 1 January 1986
J. Conway, N. J. A. Sloane
Citations165
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
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.
Abstract
Two kinds of algorithms are considered. 1) If *** is a binary code of length n , a "soft decision" decoding algorithm for *** changes an arbitrary point of R^{n} into a nearest codeword (nearest in Euclidean distance). 2) Similarly, a decoding algorithm for a lattice \Lambda in R^{n} changes an arbitrary point of R^{n} into a closest lattice point. Some general methods are given for constructing such algorithms, ami are used to obtain new and faster decoding algorithms for the Gosset lattice E_{8} , the Golay code the Leech lattice.
Keywords
Computer Science
North-Holland mathematical libraryThe Theory of Error-Correcting Codes
11,012 Citations1977
This book presents an introduction to BCH Codes and Finite Fields, and methods for Combining Codes, and discusses self-dual Codes and Invariant Theory, as well as nonlinear Codes, Hadamard Matrices, Designs and the Golay Code.
IEEE Transactions on Information TheoryError bounds for convolutional codes and an asymptotically optimum decoding algorithm
6,705 Citations1967Andrew J. Viterbi
The upper bound is obtained for a specific probabilistic nonsequential decoding algorithm which is shown to be asymptotically optimum for rates above R_{0} and whose performance bears certain similarities to that of sequential decoding algorithms.
Proceedings of the IEEEThe viterbi algorithm
5,595 Citations1973G. David Forney
This paper gives a tutorial exposition of the Viterbi algorithm and of how it is implemented and analyzed, and increasing use of the algorithm in a widening variety of areas is foreseen.
IEEE Transactions on Information TheoryClass of algorithms for decoding block codes with channel measurement information
1,073 Citations1972D. Chase
It is shown that as the signal-to-noise ratio (SNR) increases, the asymptotic behavior of these decoding algorithms cannot be improved, and computer simulations indicate that even for SNR the performance of a correlation decoder can be approached by relatively simple decoding procedures.
IEEE Transactions on Information TheoryAsymptotically optimal block quantization
869 Citations1979A. Gersho
A heuristic argument generalizing Bennett's formula to block quantization where a vector of random variables is quantized is given, leading to a rigorous method for obtaining upper bounds on the minimum distortion for block quantizers.
IEEE Transactions on Information TheoryEfficient maximum likelihood decoding of linear block codes using a trellis
568 Citations1978J.K. Wolf
It is shown that soft decision maximum likelihood decoding of any (n,k) linear block code over GF(q) can be accomplished using the Viterbi algorithm applied to a trellis with no more than q^{(n-k)} states.
IEEE Transactions on Information TheoryGeneralized minimum distance decoding
563 Citations1966G. David Forney
A new distance measure is introduced which permits likelihood information to be used in algebraic minimum distance decoding techniques and an efficient decoding algorithm is given, and exponential bounds on the probability of not decoding correctly are developed.
IEEE Transactions on Information TheoryFast quantizing and decoding and algorithms for lattice quantizers and codes
436 Citations1982J. Conway, N. J. A. Sloane
A very fast algorithm is given for finding the closest lattice point to an arbitrary point if these lattices are used for vector quantizing of uniformly distributed data.
Proceedings of the IEEEPermutation modulation
326 Citations1965D. Slepian
A class of codes and decoders is described for transmitting digital information by means of bandlimited signals in the presence of additive white Gaussiau noise, called permutation modulation, which has many desirable features.
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 TheoryOn the structure of vector quantizers
317 Citations1982A. Gersho
Vector quantization is intrinsically superior to predictive coding, transform coding, and other suboptimal and {\em ad hoc} procedures since it achieves optimal rate distortion performance subject only to a constraint on memory or block length of the observable signal segment being encoded.
IEEE Transactions on Information TheoryA fast encoding method for lattice codes and quantizers
251 Citations1983J. Conway, N. J. A. Sloane
A solution to the inverse problem for the same lattices, namely, given an integer k, to find the kth code vector, and to the closely related problem of finding the index k of a given code vector.
Proceedings of the IEEEThe technology of error-correcting codes
251 Citations1980Elwyn R. Berlekamp
This paper is a survey of error-correcting codes, with emphasis on the costs of encoders and decoders, and the relationship of these costs to various important system parameters such as speed and delay.
Bell System Technical JournalGray Codes and Paths on the n-Cube
247 Citations1958E. N. Gilbert
This paper finds all types of closed paths on cubes with n ≦ 4 and a process given here will produce large numbers of paths.
Journal of Number TheoryDefinite quadratische formen der dimension 24 und diskriminante 1
212 Citations1973Hans-Volker Niemeier
Canadian Journal of MathematicsSphere Packings and Error-Correcting Codes
201 Citations1971John Leech, N. J. A. Sloane
IEEE Transactions on Information TheoryAn optimum symbol-by-symbol decoding rule for linear codes
195 Citations1976C. Hartmann, L. Rudolph
A decoding rule is presented which minimizes the probability of symbol error over a time-discrete memory]ess channel for any linear error-correcting code when the codewords are equiprobable.
SIAM Journal on Applied MathematicsA Connection Between Block and Convolutional Codes
191 Citations1979G. Solomon, Henk C. A. van Tilborg
Using the soft decoding techniques for convolutional decoding the authors now have a new maximum likelihood decoding algorithm for many block codes that will yield an optimal quasi-cyclic code with optimal local properties and therefore with good infinite Convolutional coding properties.
Journal of Combinatorial Theory Series AOn the enumeration of self-dual codes
188 Citations1980John H. Conway, Vera Pless
The complete classification of all binary, self-dual, doubly-even (32, 16) codes is given and a set of generators is given for a code in each equivalence class together with its entire weight distribution and the order of its entire group with other information facilitating the computation of permutation generators.
Journal of Combinatorial Theory Series AOn the classification and enumeration of self-dual codes
187 Citations1975Vera Pless, N. J. A. Sloane
A complete classification is given of all [22, 11] and [24, 12] binary self-dual codes, giving the order of its group, the number of codes equivalent to it, and its weight distribution.
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.
IEEE Transactions on Information TheoryOptimum quantizers and permutation codes
140 Citations1972Thomas Berger
It is shown in this paper that these seemingly different approaches to efficient digitization of analog data actually are equivalent in the sense that their optimum rate versus distortion performances are identical, which permits us to deduce that permutation codes provide a readily implementable block-coding alternative to buffer-instrumented variable-length codes.
IEEE Transactions on Information TheoryPermutation codes for sources
118 Citations1972Thomas Berger, F. Jelinek +1 more
It is shown that optimum encoding of a source permutation code is easy to instrument even for very long block lengths, and that permutation codes are asymptotically ideal for small rates and perform as well as the best entropy-coded quantizers presently known for intermediate rates.
IEEE Transactions on Information TheoryA decoding algorithm for binary block codes andJ-ary output channels (Corresp.)
107 Citations1974B.G. Dorsch
A search algorithm is described to decode long binary block codes of any rate for the memoryless binary input J -ary output channel and can be used directly to perform maximum-likelihood decoding or in a constrained version that gives considerably fewer searches at a small sacrifice in performance.
IEEE Transactions on Information TheoryReplication decoding
104 Citations1979Gérard Battail, M. Decouvelaere +1 more
Two specific problems are discussed: the use of previous decisions, which leads to a weighted generalization of feedback decoding, and the extension of replication decoding to nonsystematic codes.
SIAM Journal on Algebraic and Discrete MethodsOn the Voronoi Regions of Certain Lattices
89 Citations1984John H. Conway, N. J. A. Sloane
IEEE Transactions on Information TheoryMinimal permutation sets for decoding the binary Golay codes (Corresp.)
77 Citations1982Dan Gordon
A method of finding minimal decoding sets is given, along with minimal sets obtained with this method for the binary Golay codes, for permutation decoding of an e error-correcting linear code.
Journal of Number TheoryOn the enumeration of lattices of determinant one
72 Citations1982John H. Conway, N. J. A. Sloane
IEEE Transactions on Information TheoryThe upper error bound of a new near-optimal code
71 Citations1975R. de Buda
The bound shows that fairly efficient codes can be obtained, particularly, at high signal-to-noise ratio (SNR) the bound approaches asymptotically the error bound of an optimal code.
Grundlehren der mathematischen WissenschaftenThe Covering Radius of the Leech Lattice
54 Citations1999J. H. Conway, Richard Parker +1 more
Proceedings of the Royal Society of London A Mathematical and Physical SciencesThe covering radius of the Leech lattice
50 Citations1982John H. Conway, Richard Parker +1 more
There are 23 types of ‘deepest hole’, one for each of the 23 even unimodular 24-dimensional lattices found by Niemeier, i.
IEEE Transactions on Information TheoryA permutation decoding of the (24, 12, 8) Golay code (Corresp.)
44 Citations1983J. Wolfmann
A minimal set consisting of 14 permutations to decode the (24,12,8) Golay code using a permutation decoding method is given.
IEEE Transactions on Information TheoryDecoding linear block codes for minimizing word error rate (Corresp.)
43 Citations1979Tai-Yang Hwang
Two modifications of the basic correlation decoding approach are presented, one of them yields a nonexhaustive optimum word decoding algorithm whose complexity depends upon the "projecting" structure of the code.
Proceedings of the Royal Society of London A Mathematical and Physical SciencesTwenty-three constructions for the Leech lattice
42 Citations1982John H. Conway, N. J. A. Sloane
Grundlehren der mathematischen WissenschaftenTwenty-Three Constructions for the Leech Lattice
35 Citations1988James Conway, N. J. A. Sloane
IEEE Transactions on Information TheoryGeneralization of chase algorithms for soft decision decoding of binary linear codes
30 Citations1984Nandakumar Nityananda Tendolkar, C. Hartmann
Simulation results for the (47, 23) quadratic residue code indicate that even for low SNR the performance level of a maximum likelihood decoder can be approached by a relatively simple decoding procedure.
IRE Transactions on Communications SystemsAn Efficient Algorithm for Soft-Decision Decoding of the (24, 12) Extended Golay Code
28 Citations1981C. M. Hackett
An efficient algorithm for soft-decision decoding of the (24, 12) extended Golay code is described and results obtained for white Gaussian noise show that performance is only a few tenths of a decibel away from that of an ideal correlator.
European Journal of CombinatoricsThe Unimodular Lattices of Dimension up to 23 and the Minkowski-Siegel Mass Constants
26 Citations1982John H. Conway, N. J. A. Sloane
This paper extends the enumeration to dimension 23, finding 40 lattices of dimension 21, 68 of dimension 22, and 117 of dimension 23 and gives explicit formulae for the Minkowski-Siegel mass constants for unimodular lattices and an exact table of the mass constants up to 32 dimensions.
IEEE Transactions on Information TheoryThe children of the (32, 16) doubly even codes
25 Citations1978Vera Pless
Generator matrices, weight distributions, and automorphism groups are given for all (26,13, 6), (28,14,6), and (30,15,6) binary self-dual codes.
IEEE Transactions on Information TheoryAlgebraic analog decoding of linear binary codes
21 Citations1979L. Rudolph, C. Hartmann +2 more
An iterative extension of the basic algebraic analog decoding scheme is discussed, and performance curves are given for the (17,9), (21,11), and (73,45) codes on the AWGN channel.
Transactions of the American Mathematical SocietyComplex and integral laminated lattices
19 Citations1983John H. Conway, N. J. A. Sloane
Grundlehren der mathematischen WissenschaftenLorentzian Forms for the Leech Lattice
19 Citations1993John H. Conway, N. J. A. Sloane
Bulletin of the American Mathematical SocietyLorentzian forms for the Leech lattice
18 Citations1982John H. Conway, N. J. A. Sloane
Information and ControlThe Leech lattice as a code for the Gaussian channel
14 Citations1971Ian F. Blake
A simple upper bound on the probability of error using the first n shells of the Leech lattice as a signalling system is derived and is shown to be lower than the upper bound given by Gallager (1965) .
NASA Technical Reports Server (NASA)Combinatorial structures in planetary reconnaissance.
12 Citations1968Edward C. Posner
IEEE Transactions on Information TheoryPartial-optimal piecewise decoding of linear codes
11 Citations1978P. Delsarte
The theory is applied to multidimensional orthogonal check set decoding of matrices over a finite field GF(q) and explicit expressions are obtained forDelta ; they allow computation of the critical probabilities of the channel.
UA Campus Repository (The University of Arizona)Soft decision decoding of block codes
10 Citations1978L. D. Baumert, Robert J. McEliece
Using a general decoding technique of Solomon, certain block codes on a Gaussian channel are evaluated and all four perform quite favorably with respect to the constraint-length 7 rate 1/2 convolutional code presently used on NASA's Mariner-class spacecraft.
Information and ControlA note on the leech lattice as a code for the gaussian channel
6 Citations1980N. J. A. Sloane
The Leech lattice A is a very dense packing of spheres in 24-dimensional Euclidean space, discovered by Leech (1967) and its automorphism group was determined by Conway (1969), and its usefulness as a source of codes for the Gaussian channel was studied by Blake (1971).
IEEE Transactions on Information TheoryEfficient optimal decoding of linear block codes (Corresp.)
6 Citations1980Tai-Yang Hwang
An optimal soft decision (maximum likelihood) decoding scheme for linear block codes is described which works in the code domain and is relatively simple and can be simplified further by considering more channel measurement information.
Decoding with multipliers
4 Citations1976L. D. Baumert, Robert J. McEliece +1 more
A general technique, called decoding with multipliers, is presented that can be used to decode any linear code and is applied to the (48,24) quadratic residue code and yields the first known practical decoding algorithm for this powerful code.
UA Campus Repository (The University of Arizona)Performance of some block codes on a Gaussian channel
2 Citations1975L. D. Baumert, Robert J. McEliece
A technique proposed by Chase (1972) is used to evaluate the performance of several fairly long binary block codes on a wideband additive Gaussian channel and it is concluded that there are many block codes of length not exceeding 100 with extremely attractive maximum likelihood decoding performance on aGaussian channel.