IEEE Transactions on Information Theory

Soft decoding techniques for codes and lattices, including the Golay code and the Leech lattice

J. Conway, Neil J.A. Sloane

Published Jan 1, 1986• 162 citations

Abstract

Two kinds of algorithms are considered.1)If *** is a binary code of lengthn, a "soft decision" decoding algorithm for *** changes an arbitrary point ofR^{n}into a nearest codeword (nearest in Euclidean distance).2)Similarly, a decoding algorithm for a lattice\LambdainR^{n}changes an arbitrary point ofR^{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 latticeE_{8}, the Golay code the Leech lattice.

DOI: 10.1109/tit.1986.1057135

Related papers

A bounded-distance decoding algorithm for the Leech lattice, with generalizations

G. 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. The algorithm has the same effective minimum distance as maximum-likelihood decoding and increases the effective error coefficient by less than a factor or two. The algorithm can be recognized as a member of the class of multistage algorithms that are applicable to hierarchical constructions. It is readily generalized to lattices that can be expressed in terms of binary code formulas, and in particular to construction B lattices.>

IEEE Transactions on Information TheoryJul 1, 198963 citations

More efficient soft decoding of the Golay codes

Alexander Vardy, Yair Be'ery

An algorithm for maximum-likelihood soft-decision decoding of the binary (24,12,8) Golay code is presented. The algorithm involves projecting the codewords of the binary Golay code onto the codewords of the (6,3,4) code over GF(4)-the hexacode. The complexity of the proposed algorithm is at most 651 real operations. Along similar lines, the tetracode may be employed for decoding the ternary (12,6,6) Golay code with only 530 real operations. The proposed algorithm also implies a reduction in the number of computations required for decoding the Leech lattice.>

IEEE Transactions on Information TheoryMay 1, 199159 citations

Efficient bounded-distance decoding of the hexacode and associated decoders for the Leech lattice and the Golay code

Ofer Amrani, Yair Be'ery

Two soft-decision decoding algorithms for the (6, 3, 4) quaternary code hexacode are presented. Both algorithms realize half the minimum Euclidean distance of the code. The proposed algorithms are most practical. In using them, bounded-distance decoding of the Golay code and the Leech lattice are performed with at most 187 and 519 real-number operations respectively. Compare this to 651, respectively 3595, operations required by the best known maximum likelihood decoders (Vardy and Be'ery, 1991, 1993), and 431, respectively 1007, operations required by the bounded-distance decoders (Amrani et al., 1994). We present some simulation results for the proposed Leech lattice decoders revealing near-optimal performance. A comparison to known trellis codes is also provided.

IEEE Transactions on CommunicationsMay 1, 199614 citations

Efficient bounded-distance decoding of the hexacode and associated decoders for the Leech lattice and the Golay code

Ofer Amrani, Yair Be'ery

Two soft-decision algorithms for decoding the (6,3,4) quaternary code, the hexacode, are presented. Both algorithms have the same guaranteed error correction radius as that of maximum-likelihood decoding. In using them, bounded-distance decoding of the Golay code and the Leech lattice are performed in at most 187 and 519 real operations respectively. We present some simulation results for the Leech lattice decoder revealing near-optimal performance. A comparison to known trellis codes is also provided.>

IEEE International Symposium on Information Theory (ISIT)Dec 17, 20026 citations

Bounded-distance soft decision decoding of binary product codes

Ofer Amrani, Yair Be'ery

A two-step sub-optimal algorithm for decoding binary product codes is discussed. This algorithm realizes at least half the minimum Euclidean distance of the code. The fundamental geometric properties associated with the algorithm are investigated, and bounds on the number of nearest neighbors are derived. This investigation also results with an improved algorithm which achieves the minimum effective error coefficient, the number of minimum-weight codewords in the product code.

IEEE International Symposium on Information Theory (ISIT)Nov 7, 20026 citations

Hard- and soft-decision decoding beyond the half minimum distance---An algorithm for linear codes (Corresp.)

Martin Bossert, F. Hergert

A decoding algorithm for linear codes that uses the minimum weight words of the dual code as parity checks is defined. This algorithm is able to correct beyond the half minimum distance and has the capability of including soft-decision decoding. Results on applying this algorithm to quadratic residue (QR) codes, BCH codes, and the Golay codes (with and without soft-decision decoding) are presented.

IEEE Transactions on Information TheorySep 1, 198638 citations