The structure of tail-biting trellises: minimality and basic principles

Basic structural properties of tail-biting trellises are investigated. We start with rigorous definitions of various types of minimality for tail-biting trellises. We then show that biproper and/or nonmergeable tail-biting trellises are not necessarily minimal, even though every minimal tail-biting trellis is biproper. Next, we introduce the notion of linear (or group) trellises and prove, by example, that a minimal tail-biting trellis for a binary linear code need not have any linearity properties whatsoever. We observe that a trellis - either tail-biting or conventional - is linear if and only if it factors into a product of elementary trellises. Using this result, we show how to construct, for any given linear code /spl Copf/, a tail-biting trellis that minimizes the product of state-space sizes among all possible linear tail-biting trellises. We also prove that every minimal linear tail-biting trellis for /spl Copf/ arises from a certain n/spl times/n characteristic matrix, and show how to compute this matrix in time O(n/sup 2/) from any basis for /spl Copf/. Furthermore, we devise a linear-programming algorithm that starts with the characteristic matrix and produces a linear tail-biting trellis for /spl Copf/; which minimizes the maximum state-space size. Finally, we consider a generalized product construction for tail-biting trellises, and use it to prove that a linear code /spl Copf/ and its dual /spl Copf//sup /spl perp///spl Copf//sup /spl perp///spl Copf//sup /spl perp///spl Copf//sup /spl perp// have the same state-complexity profiles.     

Lower bounds on the state complexity of linear tail-biting trellises

Lower bounds on the state complexity of linear tail-biting trellises are presented. One bound generalizes the total-span bound, while another bound can be regarded as a generalization of the cut-set bound. It is shown by examples that the new bounds may be tighter than any of the existing lower bounds.     

Linear tail-biting trellises, the square-root bound, andapplications for Reed-Muller codes

Linear tail-biting trellises for block codes are considered. By introducing the notions of subtrellis, merging interval, and sub-tail-biting trellis, some structural properties of linear tail-biting trellises are proved. It is shown that a linear tail-biting trellis always has a certain simple structure, the parallel-merged-cosets structure. A necessary condition required from a linear code in order to have a linear tail-biting trellis representation that achieves the square root bound is presented. Finally, the above condition is used to show that for r⩾2 and m⩾4r-1 or r⩾4 and r+3⩽m⩽[(4r+5)/3] the Reed-Muller code RM(r, m) under any bit order cannot be represented by a linear tail-biting trellis whose state complexity is half of that of the minimal (conventional) trellis for the code under the standard bit order     

Decoding of the Golay code

A decoding algorithm based on revised syndromes to decode the binary (23, 12, 7) Golay code is presented. The algorithm strongly depends on the algebraic properties of the code. For the algorithm, the worst complexity is ~576 mod 2 additions, which is less than that of the algorithms available for the code; the average complexity is approximately 224 mod 2 additions, which is also less than that of the known algorithms for the code     

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     

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     

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     

Minimal permutation sets for decoding the binary Golay codes (Corresp.)

For permutation decoding of aneerror-correcting linear code, a set of permutations which move all error vectors of weightleq eout of the information places is needed. A method of finding minimal decoding sets is given, along with minimal sets obtained with this method for the binary 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.     

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     

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     

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.     

Decoding algorithm based on revised syndrome for the binary (23,12,7) Golay code

A decoding algorithm based on revised syndromes to decode the binary (23,12,7) Golay code is presented. The algorithm strongly depends on the algebraic properties of the code. For the algorithm, the worst complexity is about 683 mod2 additions, which is less than that of the algorithms available for the code, the average complexity is approximately 319 mod2 additions, which is slightly more than that of Blaum’s algorithm for the code. Supported by the National Natural Science Foundation of China     

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     

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.     

A permutation decoding of the (24, 12, 8) Golay code (Corresp.)

We give a minimal set consisting of14permutations to decode the(24,12,8)Golay code using a permutation decoding method.     

On the uniqueness of a certain thin near octagon (or partial 2-geometry, or parallelism) derived from the binary Golay code

The question of the uniqueness of a certain combinatorial structure has arisen in three contexts: a) is the regular near octagon with parameters(s,t_{2},t_{3},t)=(1, 1,2,23)unique [5]? b) is the partial2-geometry with nexus three and blocksize24unique [2]? c) is there a unique graph such that it is the graph of a parallelism ofleft(^{24}_{4}right)with respect to any [1]? We observe that these questions are equivalent and give an affirmative answer. In fact, we prove a more general theorem, showing the truth of a conjecture by Cameron.     

Even more efficient bounded-distance decoding of the hexacode, theGolay code, and the Leech lattice

We present a new bounded-distance decoding algorithm for the hexacode, which requires at most 34 real operations in the worst case, as compared to 57 such operations in the best previously known decoder. The new algorithm is then employed for bounded-distance decoding of the Leech lattice and the Golay code. The error-correction radius of the resulting decoders is equal to that of a maximum-likelihood decoder. The resulting decoding complexity is at most 331 real operations for the Leech lattice and at most 121 operations for the Golay code. For all the three codes-the hexacode, the Golay code, and the Leech lattice-the proposed decoders are considerably more efficient than any decoder presently known     

DNA Golay码的设计与分析

 DNA编码是DNA计算初始数据库中寡核苷酸序列的设计问题.合理的DNA编码可以提高实验的稳定性和正确性,从而确保DNA计算的成功率.本文给出DNA码字重量和DNA码字间Watson-Crick Hamming距离的定义;提出DNA Golay码的设计方法;分析了DNA Golay码的性质和规模;与随机搜索优码方法相比,DNA Golay码求解优码更加简单可行.