Medical, Pharma, Engineering, Science, Technology and Business

**Nigel Boston ^{*}**

Departments of Mathematics, Electrical and Computer Engineering, University of Wisconsin, Madison, WI 53706, USA

- Corresponding Author:
- Nigel Boston

Departments of Mathematics

and Electrical and Computer Engineering

University of Wisconsin, Madison

WI 53706, USA

**Tel:**608263-2400

**E-mail:**[email protected]

**Received date:** July 21, 2015 **Accepted date:** August 03, 2015 **Published date:** August 31, 2015

**Citation:** Boston N (2015) A Multivariate Weight Enumerator for Tail-biting Trellis Pseudocodewords. J Generalized Lie Theory Appl S1:004. doi:10.4172/1736-4337.S1-004

**Copyright:** © 2015 Boston N. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

**Visit for more related articles at** Journal of Generalized Lie Theory and Applications

Tail-biting-trellis representations of codes allow for iterative decoding algorithms, which are limited in effectiveness by the presence of pseudocodewords. We introduce a multivariate weight enumerator that keeps track of these pseudocodewords. This enumerator is invariant under many linear transformations, often enabling us to compute it exactly. The extended binary Golay code has a particularly nice tail-biting-trellis and a famous unsolved question is to determine its minimal AWGN pseudodistance. The new enumerator provides an inroad to this problem.

Tail-biting trellis; Binary golay code; Pseudocodewords; Weight enumerators; Invariant theory

This paper makes headway into a longstanding problem, namely that of whether the Golay tail-biting trellis found by Calderbank, Forney, and Vardy [1] has any pseudocodewords of AWGN pseudoweight less than 8. This problem was addressed by many experts in the field before being abandoned as being computationally too hard. We circumvent this issue by introducing a new kind of multivariate weight enumerator that is invariant under the action of a large group of matrices. This enumerator is not covered by the encyclopedic work of Nebe, Rains, and Sloane [2], but the method, dating back to Gleason [3], of using **invariant theory **so as to constrain drastically the form of the enumerator polynomial, works well. In particular, we show that there are no Golay **pseudocodewords **of period less than 5 and AWGN pseudo weight less than 8. Deeper explorations of these techniques should permit us to extend this result to periods of 5 and higher.

**Definition: **A tail-biting trellis T = (V, E, A) of depth n is a directed graph with vertex set V and edge set E such that each edge has a label taken from alphabet A and with the following property: the set V can be partitioned into n subsets such that every edge in T either begins at a vertex of Vi and ends at a vertex of V_{i+1} for some i with 0 ≤ i ≤ n − 2 or begins at a vertex of V_{n−1} and ends at a vertex of V_{0}.

The set of edge labels along a cycle in T starting at a vertex in V_{0} is an n-tuple in A^{n}. We say that T represents a linear block code C over A if C is precisely the set of all edge-label sequences in T.

Conventional trellises, corresponding to the case where |V_{0} | = 1, have an older history dating back to the 60’s. Trellis representations of linear block codes provide efficient decoding algorithms such as the two-way, or BCJR, algorithm [4,5] and the Viterbi algorithm [6]. Their complexity depends on the state complexity and associated to each code is a minimal conventional trellis, unique up to isomorphism.

Tail-biting trellises date back to 1979 [7]. Their advantage is that they can have much lower state complexity (in fact ) than that, σ, of the minimal conventional trellis associated to the code. Also, they are the simplest kind of factor graph with cycles. On the other hand, there are different notions of minimality [8] and so no uniqueness for minimal tail-biting trellises associated to a given code. Additionally, their construction can be hard, as in one famous case given next.

One of the most extraordinary binary linear codes is the [24 m, 12 m, 8] extended binary Golay code. Muder [9] showed that the state complexity of its minimal conventional trellis is at least 256 and Forney [10] that this bound is met. It follows that any associated **tail-biting trellis **has state complexity at least 16 and in 1996 Forney issued the challenge of finding a tail-biting trellis meeting this bound. In 1999, Calder bank, Forney, and Vardy successfully answered this challenge [1].

The corresponding trellis-oriented generator matrix is

Because of the local nature of iterative decoding algorithms they can decode to vectors that are not code words of the original code but come from some ‘covering’ code instead. This is most commonly studied in the case of belief propagation algorithms on Tanner graphs of low density parity check codes, where since finite covers of Tanner graphs are locally identical to the original graph, the algorithm can be misled by code words associated to the cover. This leads to a theory of pseudocodewords for which advanced algebraic tools have already been developed by, for instance, Koetter, Li, Vontobel, and Walker [11]. Much work has also been carried out to define suitable pseudo weights for various channels and the minimum pseudo weight of a nonzero pseudocodeword becomes a better performance measure for the code than its minimum distance.

Tail-biting trellises also yield pseudocodewords. Namely, given T = (V, E, A) and any positive integer m, define tail-biting trellis of depth mn by letting be a copy of V_{j} where j=i (mod n) and letting the edges from to be those from The edge-labels on cycles in T^{m} starting at yield a code C_{m} such that C_{1} is the original code C represented by T.

Assume that C is binary. If (c_{0}, ..., c_{mn−1}) is in C_{m}, its associated pseudo code-word is defined to be where pj counts the number of nonzero ci for i (mod n) = j (note that sometimes this is normalized by dividing each entry by m). We say that p is of period m. There are different kinds of pseudo weight - for example, the AWGN pseudo weight of p is defined to be [12].

In the case where C is the extended Golay code, a trellis-oriented generator matrix for C_{m} is given as follows. Let M be the generator matrix given in section 2. Let A be the matrix obtained by zeroing out the ones in the bottom left hand corner of M and B = M − A, i.e. the matrix obtained by zeroing out everything but the bottom left hand corner. Let Z be the zero matrix of the same dimensions as M. Define M_{m} to be the 12m-by-24m block matrix

Then C_{m}is the [24m, 12 m, 8] binary linear code with generator matrix M_{m}. Note that in the limit as m → ∞ , M_{m} yields the infinite recurring generator matrix for the Golay convolutional code.

Much work has been done on pseudo weights of pseudocodewords in this case, notably in Aji et al. [13] and Forney et al. [14]. The question of whether there exist nonzero pseudo code-words of AWGN pseudo weight less than 8 apparently became a major challenge but remains open to this day. There are many nontrivial near-misses - for example, there are pseudocodewords of period 2 with 2 in 2 positions, 1 in 8 positions, and 0 elsewhere, which therefore have AWGN pseudo weight 12^{2}/16=9, and pseudo code-words of period 3 with 3 in 2 positions, 2 in 2 positions, 1 in 6 positions, and 0 elsewhere, which therefore have AWGN pseudo weight 16^{2}/32=8.

This question motivated the current work. It is feasible to find all 224 code-words of C_{2} and hence all corresponding pseudocodewords but to do the same with C_{3} is already computationally intense. Resolving the question by brute force would require doing the same for all C_{m} for 1 ≤ m ≤ 16 since cycles can go around up to 16 times before necessarily returning to the same vertex of V_{0}.

Let be a pseudocodeword of period m. Attach to p the monomial where r_{i} is the number of occurrences of i in p. Note that . For example, the two pseudocodewords referred to in the penultimate paragraph of section 3 yield monomials and respectively. Note that the AWGN pseudo weight can be calculated from the corresponding monomial.

Next, define the *pseudocodeword weight enumerator* W_{m} associated to pseudocodewords of period m to be the sum of all these monomials as we run through the code words of C_{m}. Note that W_{m} is a polynomial in m + 1 variables x0, ..., xm with non-negative integer coefficients. So, for example, W_{1} is the usual weight enumerator. For the extended Golay code,

As noted above, a brute force calculation of W_{2} for the extended Golay code is feasible. We thereby obtain:

Knowing W_{2} is enough to establish that there are no nonzero pseudocodewords of period 2 with pseudo weight less than 8. Our strategy then will be to try to compute W_{m} for all m by using the fact that W_{m} has some very nice transformation properties.

In her 1962 Harvard PhD thesis [15], MacWilliams showed that the weight enumerator W of the dual of a binary linear code C is closely related to that of the code. In particular, W is invariant under the transformation

If the weights of all code words are divisible by 4 (C is then called doubly even), then W is also invariant under the transformation

Thus, W is invariant under all possible compositions of these two transformations, of which there are 192, forming what is called the Clifford-Weil group G_{1}.

In 1970, Gleason [3] observed that this imposes a strong restriction on the structure of W , since every homogeneous polynomial in x0, x_{1} invariant under G_{1} is a polynomial in the **weight enumerators ** of the extended [8,4,4] Hamming code and W_{G}(= W_{1} given in the previous section) of the extended Golay code. This permits quick computation of weight enumerators of large selfdual doubly even codes.

In the last four decades, hundreds of papers have appeared generalizing and applying Gleason’s results, culminating in the book [2] by Nebe, Rains, and Sloane unifying these theories. They define the Type of a self-dual code such that the weight enumerator of any code of that Type lies in the invariant ring of a certain Clifford-Weil group associated with that Type, and furthermore such that this invariant ring is spanned by weight enumerators of that Type. There are also fascinating algebra isomorphisms due to Broue and Enguehard between various rings of modular forms and rings of weight enumerators [16].

We are guided by a similar philosophy below, in seeking to compute the multi-variate weight enumerators W_{m} for the Golay case. This theory is new, not covered by the above book.

Let A be a 2-by-2 matrix. Then A acts on x_{0}, x_{1} by linear transformations. Substituting these into , yields a linear transformation of those m + 1 terms and hence produces an m + 1-by-m + 1 matrix, denoted For example, if then and so Similarly one computes that and It follows that A sends

The above 3-by-3 matrix is then . Applying this to all 192 matrices in the Clifford-Weil group G_{1} above yields 96 3-by-3 matrices (we say that the ho-momorphism Sym^{2} has a kernel of order 2). Each such matrix defines a linear transformation in x_{0}, x_{1}, x_{2}. One can check using a computer algebra system such as Magma that W2 is invariant under all 96 of these transformations.

In fact W2 is also invariant under the transformation Compositions formed from this and the 96 transformations above yield a group G_{2} of 384 3-by-3 matrices, all leaving W_{2} invariant.

If we had known a priori that W_{2} is invariant under G_{2}, then we could have used Magma to compute all homogeneous degree 24 polynomials invariant under G_{2} (it turns out that they are spanned by 6 such polynomials I_{1}, ..., I_{6}). The correct linear combination of those 6 polynomials (in fact I_{1} + 294I_{6}) could then be found by exploiting a computation of low weight codewords of C_{2}. This is the strategy we employ in section 7 below to calculate W3 and W4, which would otherwise have been out of reach. The main (nontrivial) point, proven in David Conti’s upcoming University College Dublin PhD thesis, is that, for every m, W_{m} is invariant under every matrix Sym^{m}(A) where A is in G_{1} and under certain diagonal matrices. This produces a typically large group G_{m} of (m + 1)-by-(m + 1) matrices leaving Wm invariant.

The group G_{2} is the group of 3-by-3 quasipermutation matrices which have exactly one nonzero entry, a 4th root of unity, in every row and every column. This makes it isomorphic to the wreath product It is also a complex reflection group, which makes its invariant theory particularly nice, leading to the following pretty formula. Let

Then

We move first to computing W_{3}. The above theory shows that W_{3} is invariant under for A in G_{1}. This yields 192 transformations. In addition, W_{3} is invariant under the transformation

All possible compositions of the above transformations yield a group G_{3} of 1152 4-by-4 matrices leaving W_{3} invariant.

Next, using Magma, we compute all homogeneous degree 24 polynomials in invariant under G_{3}. Magma produces 26 polynomials I_{1}, ..., I_{26} that span this space. Using low weight code words in C_{3} yields a simple linear combination of them that must equal W_{3}. Namely, which gives:

There are 212 terms in W_{3}, too many to list here, but note that each monomial that appears corresponds to pseudocodewords that have pseudo weight at least 8.

As for W_{4}, we similarly obtain a group G_{4} of 384 5-by-5 matrices that leave W_{4} invariant. The space of homogeneous degree 24 polynomials in x_{0}, ..., x_{4} invariant under G_{4} is spanned by 153 very lengthy polynomials which Magma gives explicitly. Of these 153 polynomials, 87 have the property that every monomial occurring in them corresponds to pseudocodewords of pseudoweight at least 8. We show that W4 is a span of these 87 polynomials by excluding the other 66 polynomials as follows. Every such polynomial contains a monomial that occurs in it and none of the remaining 152 polynomials. Examining these special monomials, we see that, for those 66 polynomials, if the special monomial were present, it would come from a codeword of C_{4} of weight at most 24. By analyzing low weight codewords of C_{4}, we can show that this does not happen. Thus, there are no nonzero pseudocodewords of period ≤ 4 of pseudoweight less than 8.

Likewise, for m ≥ 5, there is an explicitly given group Gm of m + 1-by-m + 1 matrices leaving W_{m} invariant. Unfortunately, both the computation of homogeneous degree 24 polynomials invariant under G_{m} and the analysis of low weight code words of Cm become computationally too expensive. It is clear that there are 147m code words of C_{m} of weight 8, but beyond that patterns are hard to spot. For example, the code words of C_{m} of weight 12 correspond to pseudocodewords either consisting of 12 ones and 12 zeros or 2 twos, 8 ones, and 14 zeros, but there is no clear, even conjectural, formula for the number of either kind.

We have introduced new and useful multivariate polynomials attached to a tail-biting trellis. These keep track of what kinds of pseudocodewords exist and indeed how many there are of each kind. This can in turn be used to measure how good the code is as regards iterative decoding, with various formulae for pseudo weight being used, depending on the channel. It has been a longstanding question to determine whether the AWGN pseudo weight of a nonzero pseudocodeword for the tail-biting trellis of the extended **binary Golay code **is ever less than 8. Our new invariant theory methods allow us to answer this question in the negative for all pseudocodewords of period ≤ 4.

Pseudocodeword weight enumerators W_{m} are defined for any tail-biting trellis. It is not true, however, that they are invariant under the same group G_{m} as for the Golay code above. For example, for tailbiting trellises attached to the extended [8,4,4] Hamming code, the polynomials W_{m} are invariant under slightly smaller groups than Gm. The author’s PhD student, David Conti, is developing a theory that should hopefully clarify the notion of Type for a tail-biting trellis and allow one to define an analogue of the Clifford-Weil group for each Type.

- Calderbank AR, Forney GD, Vardy A (1999) Minimal tail-biting trellises: The Golay code and more. IEEE Transactions on Information Theory 45: 1435-1455.
- Nebe G, Rains EM, Sloane NJA (2006) Self-Dual Codes and Invariant Theory. Springer-Verlag.
- Gleason AM (1971) Weight polynomials of self-dual codes and the MacWilliams identities.Gauthiers-Villars, Paris 3: 211-215.
- Bahl LR, Cocke J, Jelinek F, Raviv J (1974) Optimal decoding of linear codes for minimizing symbol error rate. IEEE Transactions on Information Theory 20: 284-287.
- Gallager RG (1963) Low-density parity-check codes. MA, MIT Press, Cambridge.
- Viterbi AJ (1967) Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory 13: 260-269.
- Solomon G, van Tilborg HCA (1979) A connection between block and convolutional codes. SIAM Journal of Applied Mathematics 37: 358-369.
- Koetter R, Vardy A (2003) The structure of tail-biting trellises: minim ality and basic principles. IEEE Transactions on Information Theory 49: 1877-1901.
- Muder DJ (1988) Minimal trellises for block codes. IEEE Transactons on Information Theory 34: 1049-1053.
- Forney GD (1994) Dimension/length profiles and trellis complexity of linear block codes. IEEE Transactions on Information Theory 40: 1741-1752.
- Koetter R, Li WCW, Vontobel PO, Walker JL (2007) Characterizations of pseudo-code words of (low-density) parity-check codes. Advances in Mathematics 213: 205-229.
- Wiberg N (1996) Codes depending on general graphs, Doctor of Philosophy Dissertation. Department of Electrical Engineering, University of Linkoping, Sweden.
- Aji S, Horn G, McEliece R, Xu M (1998) Iterative min-sum decoding of tail-biting codes. Proc ITW workshop, Killarney.
- Forney GD, Koetter R, Kschischang FR, Reznik A (1999) On the effective weights of pseudocodewords for codes defined on graphs with cycles, in Codes. The IMA Volumes in Mathematics and its Applications 123: 101-112.
- MacWilliams FJ (1963) A theorem on the distribution of weights in a systematic code. Bell Syst Tech J 42: 79-94.
- Sole P (2008) Codes, invariants, and modular forms, talk at Bonn MPIM.

Select your language of interest to view the total content in your interested language

- Adomian Decomposition Method
- Algebra
- Algebraic Geometry
- Analytical Geometry
- Applied Mathematics
- Axioms
- Balance Law
- Behaviometrics
- Big Data Analytics
- Binary and Non-normal Continuous Data
- Binomial Regression
- Biometrics
- Biostatistics methods
- Clinical Trail
- Combinatorics
- Complex Analysis
- Computational Model
- Convection Diffusion Equations
- Cross-Covariance and Cross-Correlation
- Deformations Theory
- Differential Equations
- Differential Transform Method
- Fourier Analysis
- Fuzzy Boundary Value
- Fuzzy Environments
- Fuzzy Quasi-Metric Space
- Genetic Linkage
- Geometry
- Hamilton Mechanics
- Harmonic Analysis
- Homological Algebra
- Homotopical Algebra
- Hypothesis Testing
- Integrated Analysis
- Integration
- Large-scale Survey Data
- Latin Squares
- Lie Algebra
- Lie Superalgebra
- Lie Theory
- Lie Triple Systems
- Loop Algebra
- Matrix
- Microarray Studies
- Mixed Initial-boundary Value
- Molecular Modelling
- Multivariate-Normal Model
- Noether's theorem
- Non rigid Image Registration
- Nonlinear Differential Equations
- Number Theory
- Numerical Solutions
- Operad Theory
- Physical Mathematics
- Quantum Group
- Quantum Mechanics
- Quantum electrodynamics
- Quasi-Group
- Quasilinear Hyperbolic Systems
- Regressions
- Relativity
- Representation theory
- Riemannian Geometry
- Robust Method
- Semi Analytical-Solution
- Sensitivity Analysis
- Smooth Complexities
- Soft biometrics
- Spatial Gaussian Markov Random Fields
- Statistical Methods
- Super Algebras
- Symmetric Spaces
- Theoretical Physics
- Theory of Mathematical Modeling
- Three Dimensional Steady State
- Topologies
- Topology
- mirror symmetry
- vector bundle

- 7th International Conference on Biostatistics and Bioinformatics

September 26-27, 2018 Chicago, USA - Conference on Biostatistics and Informatics

December 05-06-2018 Dubai, UAE - Mathematics Congress - From Applied to Derivatives

December 5-6, 2018 Dubai, UAE

- Total views:
**12002** - [From(publication date):

specialissue-2015 - Jun 18, 2018] - Breakdown by view type
- HTML page views :
**8044** - PDF downloads :
**3958**

Peer Reviewed Journals

International Conferences 2018-19