alexa A Multivariate Weight Enumerator for Tail-biting Trellis Pseudocodewords | OMICS International
ISSN: 1736-4337
Journal of Generalized Lie Theory and Applications
Make the best use of Scientific Research and information from our 700+ peer reviewed, Open Access Journals that operates with the help of 50,000+ Editorial Board Members and esteemed reviewers and 1000+ Scientific associations in Medical, Clinical, Pharmaceutical, Engineering, Technology and Management Fields.
Meet Inspiring Speakers and Experts at our 3000+ Global Conferenceseries Events with over 600+ Conferences, 1200+ Symposiums and 1200+ Workshops on
Medical, Pharma, Engineering, Science, Technology and Business

A Multivariate Weight Enumerator for Tail-biting Trellis Pseudocodewords

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

Abstract

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.

Keywords

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

Introduction

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.

Tail-biting Trellises

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 image 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 [6]. Their complexity depends on the state complexityimage 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 image) 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.

The Extended Binary Golay Code

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

image

Pseudocodewords

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 image of depth mn by letting image be a copy of Vj where j=i (mod n) and letting the edges from image to image be those from image The edge-labels on cycles in Tm starting at imageyield a code Cm such that C1 is the original code C represented by T.

Assume that C is binary. If (c0, ..., cmn−1) is in Cm, its associated pseudo code-word is defined to beimage 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 image [12].

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

image

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. [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 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.

Pseudocodewords Weight Enumerators

Let image be a pseudocodeword of period m. Attach to p the monomial image where ri is the number of occurrences of i in p. Note that image . For example, the two pseudocodewords referred to in the penultimate paragraph of section 3 yield monomials image and image 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,

image

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

image

image

image

image

image

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.

Invariant Theory

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

image

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

image

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 [3] 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 image 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 [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 Wm for the Golay case. This theory is new, not covered by the above book.

Symmetric Power Invariance

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

image

The above 3-by-3 matrix is then image . 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 image 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 image It is also a complex reflection group, which makes its invariant theory particularly nice, leading to the following pretty formula. Let

image

image

Then image

Golay Pseudocodewords Enumerators

We move first to computing W3. The above theory shows that W3 is invariant under image for A in G1. This yields 192 transformations. In addition, W3 is invariant under the transformation

image 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 image 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, image which gives:

image

image

image

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.

Conclusions and Further Work

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.

References

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

Share This Article

Relevant Topics

Recommended Conferences

  • 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

Article Usage

  • Total views: 12025
  • [From(publication date):
    specialissue-2015 - Aug 19, 2018]
  • Breakdown by view type
  • HTML page views : 8062
  • PDF downloads : 3963
 

Post your comment

captcha   Reload  Can't read the image? click here to refresh

Peer Reviewed Journals
 
Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals
International Conferences 2018-19
 
Meet Inspiring Speakers and Experts at our 3000+ Global Annual Meetings

Contact Us

Agri & Aquaculture Journals

Dr. Krish

kactakapaniyor.com

[email protected]

+1-702-714-7001Extn: 9040

Biochemistry Journals

Datta A

Taktube

[email protected]

1-702-714-7001Extn: 9037

Business & Management Journals

Ronald

porn sex

[email protected]

1-702-714-7001Extn: 9042

Chemistry Journals

Gabriel Shaw

Gaziantep Escort

[email protected]

1-702-714-7001Extn: 9040

Clinical Journals

Datta A

sikiş

[email protected]

1-702-714-7001Extn: 9037

instafollowers

James Franklin

[email protected]

1-702-714-7001Extn: 9042

Food & Nutrition Journals

Katie Wilson

[email protected]

1-702-714-7001Extn: 9042

General Science

Andrea Jason

mp3 indir

[email protected]

1-702-714-7001Extn: 9043

Genetics & Molecular Biology Journals

Anna Melissa

[email protected]

1-702-714-7001Extn: 9006

Immunology & Microbiology Journals

David Gorantl

[email protected]

1-702-714-7001Extn: 9014

Materials Science Journals

Rachle Green

[email protected]

1-702-714-7001Extn: 9039

Nursing & Health Care Journals

Stephanie Skinner

[email protected]

1-702-714-7001Extn: 9039

Medical Journals

putlockers

Nimmi Anna

[email protected]

1-702-714-7001Extn: 9038

Neuroscience & Psychology Journals

Nathan T

seks

[email protected]

1-702-714-7001Extn: 9041

Pharmaceutical Sciences Journals

Ann Jose

[email protected]

1-702-714-7001Extn: 9007

Social & Political Science Journals

Steve Harry

[email protected]

1-702-714-7001Extn: 9042

 
© 2008- 2018 OMICS International - Open Access Publisher. Best viewed in Mozilla Firefox | Google Chrome | Above IE 7.0 version