Decoding the Golay code with Venn diagrams

A decoding algorithm, based on Venn diagrams, for decoding the [23, 12, 7] Golay code is presented. The decoding algorithm is based on the design properties of the parity sets of the code. As for other decoding algorithms for the Golay code, decoding can be easily done by hand     

Decoding the Golay codes

We introduce exceptionally simple decoding algorithms for the two extended Golay codes. The algorithms are 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)Steiner system. These decoding methods are simple enough to enable decoding extended Golay codes by hand. Both of the methods involve relations between the extended Golay codes and other self-dual codes. Proofs are given explaining these relationships and why the decoding methods work. The decoding algorithms are explained and illustrated with many examples.[3, chap.12]has facts about the Mathieu group and some details about decoding the Golay codes.     

Decoding the binary Golay code with miracle octad generators (Corresp.)

The recently introduced notion of a miracle octad generator can be viewed as a means of identifying a codeword of weight eight of the extended binary Golay code, given five of its nonzero positions. It is shown that this fact can be used as the basis of a new decoding algorithm for this code which decodes all the information positions simultaneously. The performance of this algorithm, as well as methods for its implementation, are considered.     

Golay码的快速译码

本文利用Ｇｏｌａｙ码的代数结构给出了二元（２３，１２，７）Ｇｏｌａｙ码及三元（１１，６，５）Ｇｏｌａｙ码新的译码算法。对于二元Ｇｏｌａｙ码，所提的算法的最坏时间复杂性为５３４次ｍｏｄ２加法，比已知的同类译码算法的时间复杂性都小；平均时间复杂性为２２４次ｍｏｄ２加法，比目前已知的最快的译码算法的平均时间复杂性２７９次ｍｏｄ２加法还要小。对于三元Ｇｏｌａｙ码，所提算法的最坏时间复杂性为１２３次ｍｏｄ３加法，平均时间复杂性为８５次ｍｏｄ３加法，比同类的算法都快。此外，这里给出的算法结构简单，易于实现。     

Golay码的一种新译码算法

本文提出(24,12)扩展Golay码的一种新的译码算法,并证明其实现了最大似然译码。与现有的译码算法比较,本文的译码法有许多优越之处。同时它还可以推广到其它具有良好代数构造的分组码的译码。     

一种Golay码的快速译码算法

本文提出了一种（２４，１２，８）扩展Ｇｏｌａｙ码的新的软判决译码算法，其译一组码字的运算量最多为５０７次二元运算，优于目前已发表的各种算法。我们证明了该算法，并实现了广义最小距离译码。计算机模拟表明在完备译码时其性能与最大似然译码几乎一样。     

On high-speed decoding of the (23,12,7) Golay code

An algebraic decoding method for triple-error-correcting binary BCH codes applicable to complete decoding of the (23,12,7) Golay code has been proved by M. Elia (see ibid., vol.IT-33, p.150-1, 1987). A modified step-by-step complete decoding algorithm of this Golay code is introduced which needs fewer shift operations than Kasami's error-trapping decoder. Based on the algorithm, a high-speed hardware decoder of this code is proposed     

Minimal tail-biting trellises: the Golay code and more

Tail-biting trellis representations of block codes are investigated. We develop some elementary theory, and present several intriguing examples, which we hope will stimulate further developments in this field. In particular, we construct a 16-state 12-section structurally invariant tail-biting trellis for the (24, 12, 8) binary Golay code. This tail-biting trellis representation is minimal: it simultaneously minimizes all conceivable measures of state complexity. Moreover, it compares favorably with the minimal conventional 12-section trellis for the Golay code, which has 256 states at its midpoint, or with the best quasi-cyclic representation of this code, which leads to a 64-state tail-biting trellis. Unwrapping this tail-biting trellis produces a periodically time-varying 16-state rate-1/2 “convolutional Golay code” with d=8, which has attractive performance/complexity properties. We furthermore show that the (6, 3, 4) quaternary hexacode has a minimal 8-state group tail-biting trellis, even though it has no such linear trellis over F₄. Minimal tail-biting trellises are also constructed for the (8, 4, 4) binary Hamming code, the (4, 2, 3) ternary tetracode, the (4, 2, 3) code over F₄, and the Z₄-linear (8. 4, 4) octacode     

On minimal decoding sets for the extended binary Golay code

Minimal decoding sets consisting of fourteen permutations have been found for the (24,12,8) extended binary Golay code. It is shown that by properly sequencing the permutations of one such set, the average number of permutations required to decode a random received word can be minimized     

Decoding by sequential code reduction

A general decoding method for cyclic codes is presented which gives promise of substantially reducing the complexity of decoders at the cost of a modest increase in decoding time (or delay). Significant reductions in decoder complexity for binary cyclic finite-geometry codes are demonstrated.     

基于神经网络的（23,12）Golay码译码新算法

对Ｈｏｐｆｉｅｌｄ神经网络（Ｈ．Ｎ．）在纠错编译码技术中的具体应用进行了研究，分析指出了该网络与循环码，尤其是Ｇｏｌａｙ码的关系，提出了一种采用高阶互连网络实现循环码最大似然译码的方法，并且实现了一套有效的算法，非常完满地解决了（２３，１２）Ｇｏｌａｙ码的完全译码。最后指明了硬件实现的思路。     

Decoding of the IS-95A uplink code

This letter considers the decoding of the IS-95(A) uplink code in an effort to assess its best achievable performance. Union bounds on the bit error probability for the IS-95(A) indicate that the interleaver affects significantly system performance. Computer simulation results for iterative decoding show that performance gains in the order of 0.6 dB can be obtained when the sequential interleaver is replaced by a pseudorandom interleaver of same size. Improving iterative decoding for this code while maintaining the original sequential interleaver, results only in minor performance gains over published results     

Algebraic decoding of the (23,12,7) Golay code (Corresp.)

It is shown that the algebraic method for decoding three-error-correcting BCH codes is also applicable to complete decoding of the(23,12,7)Golay code.     

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

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     

Decoding the Johnson code by 2-output comparator circuits

The problem of decoding the n-bit Johnson code to decimal numbers is discussed. For an odd number n, a systematic procedure is possible utilising n 2-input 2-output comparator circuits. A theorem is stated and proved for the nonexistence of such a procedure when n is even.     

Cover positions and decoding complexity of the Golay code, using anextended Kasami algorithm

This paper compares the complexity of an extended Kasami (1964) algorithm with three other algorithms for the Golay code. A nonmathematical method is described to determine the best cover positions. This leads to a result different from the Kasami algorithm and significantly reduces the decoding complexity     

An Efficient Algorithm for Soft-Decision Decoding of the (24, 12) Extended Golay Code

An efficient algorithm for soft-decision decoding of the (24, 12) extended Golay code is described. Results obtained for white Gaussian noise are presented which show that performance is only a few tenths of a decibel away from that of an ideal correlator.     

VLSI implementation of a maximum-likelihood decoder for the Golay(24, 12) code

J.H. Conway and N.J.A. Sloane (1986) have introduced an algorithm for the exact maximum-likelihood decoding of the Golay (24, 12) code in the additive white Gaussian noise channel that requires significantly fewer computations than previous algorithms. An efficient bit-serial VLSI implementation of this algorithm is described. The design consists of two chips developed using path-programmable logic (PPL) and an associated system of automated design tools for three-μm NMOS technology. It is estimated that this decoder will produce an information bit every 1.6-2.4 μs. Higher speeds can be achieved by using a faster technology or by replicating the chips to perform more operations in parallel     

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

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 latticeLambdainR^{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.     

基于FPGA的IRIG—B（DC）码解码

在分析了IRIG-B（DC）码码型特点的基础上,提出了一种IRIG-B（DC）时间码解码的设计方法。该方法由少量外围电路与一片现场可编程门阵列（FPGA）芯片组成,来实现对IRIG-B（DC）码的解码、1PPS信号输出、实时时间显示以及串行异步通信。与传统的方法相比,该设计方案具有体积小、成本低、工作稳定等优点,完全能够替代传统的B码机箱的功能。