Maximum likelihood soft decoding of binary block codes and decoders for the Golay codes
IEEE Transactions on Information TheoryPublished 1 January 1989
J. Snyders, Y. Be'ery
Citations112
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
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.
Abstract
Maximum-likelihood soft-decision decoding of linear block codes is addressed. 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. Besides efficient soft decoding of small codes, the generalized rule enables utilization of subspaces of a wide variety, thereby yielding maximum-likelihood decoders with substantially reduced computational complexity for some larger binary codes. More sophisticated choice and exploitation of the structure of both a subspace and the coset representatives are demonstrated for the (24, 12) Golay code, yielding a computational gain factor of about 2 with respect to previous methods. A ternary single-check version of the Wagner rule is applied for efficient soft decoding of the (12, 6) ternary Golay code.>
Keywords
Computer ScienceEngineering
IEEE Transactions on Information TheoryMaximum-likelihood sequence estimation of digital sequences in the presence of intersymbol interference
2,455 Citations1972G. David Forney
A maximum-likelihood sequence estimator for a digital pulse-amplitude-modulated sequence in the presence of finite intersymbol interference and white Gaussian noise is developed and performance is shown to be effectively as good as could be attained by any receiver structure.
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 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 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 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 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.
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 TheoryOptimal soft decision block decoders based on fast Hadamard transform
91 Citations1986Y. Be'ery, J. Snyders
An approach for efficient utilization of fast Hadamard transform in decoding binary linear block codes is presented and the availability of these codewords in general, and particularly in some of the most frequently encountered codes, is discussed.
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.
Journal of Combinatorial Theory Series AOvals in projective designs
44 Citations1979E. F. Assmus, J. H. van Lint
The notion of “oval” arose in the study of finite projective planes and is extended to arbitrary projective designs — indeed to arbitrary designs.
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.
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 TheoryThe construction of fast, high-rate, soft decision block decoders
18 Citations1983Elwyn R. Berlekamp
A detailed description is given of a fast soft decision decoding procedure for high-rate block codes made possible by using the symmetries of the code to simplify the syndrome decoding by table look-up and by making the best use of the soft decision information.
Grundlehren der mathematischen WissenschaftenThe Golay Codes and The Mathieu Groups
3 Citations1988J. H. Conway
This chapter contains a detailed description of the binary Golay code of length 24, the Steiner system S (5, 8, 24), and the Mathieu group M 24.