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  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 , but the method, dating back to Gleason , 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 Vi+1 for some i with 0 ≤ i ≤ n − 2 or begins at a vertex of Vn−1 and ends at a vertex of V0.
The set of edge labels along a cycle in T starting at a vertex in V0 is an n-tuple in An. 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 |V0 | = 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 . 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 . 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  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  showed that the state complexity of its minimal conventional trellis is at least 256 and Forney  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 .
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 . 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.
Assume that C is binary. If (c0, ..., cmn−1) is in Cm, 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 .
In the case where C is the extended Golay code, a trellis-oriented generator matrix for Cm 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 Mm to be the 12m-by-24m block matrix
Then Cmis the [24m, 12 m, 8] binary linear code with generator matrix Mm. Note that in the limit as m → ∞ , Mm 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.  and Forney et al. . 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 122/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 162/32=8.
This question motivated the current work. It is feasible to find all 224 code-words of C2 and hence all corresponding pseudocodewords but to do the same with C3 is already computationally intense. Resolving the question by brute force would require doing the same for all Cm for 1 ≤ m ≤ 16 since cycles can go around up to 16 times before necessarily returning to the same vertex of V0.
Let be a pseudocodeword of period m. Attach to p the monomial where ri 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 Wm associated to pseudocodewords of period m to be the sum of all these monomials as we run through the code words of Cm. Note that Wm is a polynomial in m + 1 variables x0, ..., xm with non-negative integer coefficients. So, for example, W1 is the usual weight enumerator. For the extended Golay code,
As noted above, a brute force calculation of W2 for the extended Golay code is feasible. We thereby obtain:
Knowing W2 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 Wm for all m by using the fact that Wm has some very nice transformation properties.
In her 1962 Harvard PhD thesis , 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 G1.
In 1970, Gleason  observed that this imposes a strong restriction on the structure of W , since every homogeneous polynomial in x0, x1 invariant under G1 is a polynomial in the weight enumerators of the extended [8,4,4] Hamming code and WG(= W1 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  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 .
We are guided by a similar philosophy below, in seeking to compute the multi-variate weight enumerators Wm 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 x0, x1 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 G1 above yields 96 3-by-3 matrices (we say that the ho-momorphism Sym2 has a kernel of order 2). Each such matrix defines a linear transformation in x0, x1, x2. 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 G2 of 384 3-by-3 matrices, all leaving W2 invariant.
If we had known a priori that W2 is invariant under G2, then we could have used Magma to compute all homogeneous degree 24 polynomials invariant under G2 (it turns out that they are spanned by 6 such polynomials I1, ..., I6). The correct linear combination of those 6 polynomials (in fact I1 + 294I6) could then be found by exploiting a computation of low weight codewords of C2. 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, Wm is invariant under every matrix Symm(A) where A is in G1 and under certain diagonal matrices. This produces a typically large group Gm of (m + 1)-by-(m + 1) matrices leaving Wm invariant.
The group G2 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
We move first to computing W3. The above theory shows that W3 is invariant under for A in G1. This yields 192 transformations. In addition, W3 is invariant under the transformation
All possible compositions of the above transformations yield a group G3 of 1152 4-by-4 matrices leaving W3 invariant.
Next, using Magma, we compute all homogeneous degree 24 polynomials in invariant under G3. Magma produces 26 polynomials I1, ..., I26 that span this space. Using low weight code words in C3 yields a simple linear combination of them that must equal W3. Namely, which gives:
There are 212 terms in W3, too many to list here, but note that each monomial that appears corresponds to pseudocodewords that have pseudo weight at least 8.
As for W4, we similarly obtain a group G4 of 384 5-by-5 matrices that leave W4 invariant. The space of homogeneous degree 24 polynomials in x0, ..., x4 invariant under G4 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 C4 of weight at most 24. By analyzing low weight codewords of C4, 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 Wm invariant. Unfortunately, both the computation of homogeneous degree 24 polynomials invariant under Gm and the analysis of low weight code words of Cm become computationally too expensive. It is clear that there are 147m code words of Cm of weight 8, but beyond that patterns are hard to spot. For example, the code words of Cm 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 Wm are defined for any tail-biting trellis. It is not true, however, that they are invariant under the same group Gm as for the Golay code above. For example, for tailbiting trellises attached to the extended [8,4,4] Hamming code, the polynomials Wm 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.