On Weight Hierarchies of Product Codes The Wei-Yang Conjecture and more

Conchita Martínez-Pérez

Departamento de Matemáticas, Universidad de Zaragoza, 50009 Zaragoza, Spain. Email: ⟨conmar@posta.unizar.es⟩.

Hans Georg Schaathun

Institutt for Informatikk, Universitas Bergensis, Høyteknologisenteret, N-5020 Bergen, Norway. Email: ⟨georg@ii.uib.no⟩.

Wolfgang Willems

Fakultät für Mathematik, Otto-von-Guericke-Universität, D 39106 Magdeburg, Germany. Email: ⟨wolfgang.willems@mathematik.uni-magdeburg.de⟩.

Abstract

The weight of a code is the number of coordinate positions where no codeword is zero. The rth minimum weight d_{r} is the least weight of an r-dimensional subcode. Wei and Yang conjectured a formula for the minimum weights of some product codes. The conjecture is proved in two different ways, each with interesting side-results.

Key words: product code, projective multiset, weight hierarchy, Segre embedding, chain condition

1 Introduction

Generalised Hamming weights have received a lot of attention after Victor Wei’s paper [14] in 1991. An early project by Victor Wei and Kyeongcheol Yang [15] attempted to determine the weight hierarchy of product codes, given the weight hierarchies for the component codes.

In the special case where both the component codes satisfy the chain condition they found an upper bound on the weight hierarchy. They conjectured that this bound is always satisfied with equality.

Preprint submitted to WCC 2001 15 November 2000

Two different proofs of the conjecture have appeared recently [11,9]. Each of the proofs give interesting generalisations of the Wei-Yang conjecture. In the sequel we will survey the results from both papers, as well as related results from the last decade. A new result appears in Theorem 8. Finally we suggest some open problems for further study.

2 Product Codes

An [n, k] code is a k-dimensional subspace C ≦ 𝕍 of some n-dimensional vector space 𝕍. The support of a vector c = (c_{1}, c_{2}, …, c_{n}) ∈ 𝕍 is the set

χ(c) := {i | c_{i} ≠ 0},

and the support of a subset S ⊆ 𝕍 is the set

χ(S) := ⋃_{c∈S} χ(c).

The weight hierarchy of the code C ≦ 𝕍 is the sequence

(d_{1}(C), d_{2}(C), …, d_{k}(C)),

where

d_{r}(C) := min{#χ(D) | D ≦ C, dim D = r}.

Clearly d_{1}(C) is the minimum distance, and for convenience we put d_{0}(C) = 0.

The chain condition says that there exists a sequence of subcodes

{0} = D_{0} < D_{1} < … < D_{k} = C,

such that D_{i} has dimension i and weight d_{i}(C). Codes satisfying the chain condition are called chained codes.

Remark 1 Almost all codes violate the chain condition [4]. However, a lot of interesting codes do satisfy the chain condition, such as the Hamming, Reed-Muller, MDS and extended Golay codes. In particular, codes with high generalised Hamming weights tend to satisfy the chain condition.

Let C_{1} be an [n_{1}, k_{1}] code and C_{2} an [n_{2}, k_{2}] code over the same field 𝔽. The product code C_{1} ⊗ C_{2} is the tensor product of C_{1} and C_{2} as vector spaces over 𝔽. In other words

C_{1} ⊗ C_{2} = ⟨a ⊗ b | a ∈ C_{1}, b ∈ C_{2}⟩,

where

a ⊗ b = (a_{i}b_{j} | 1 ≤ i ≤ n_{1}, 1 ≤ j ≤ n_{2}),
a = (a_{1}, a_{2}, …, a_{n_{1}}),
b = (b_{1}, b_{2}, …, b_{n_{2}}).

The product code is an [n_{1}n_{2}, k_{1}k_{2}] code.

A (k_{1}, k_{2})-partition of r is a non-increasing sequence π = (t_{1}, t_{2}, …, t_{k_{1}}) such that t_{1} + t_{2} + … + t_{k_{1}} = r and t_{i} ≤ k_{2}. Let P(k_{1}, k_{2}; r) denote the set of all (k_{1}, k_{2})-partitions of r.

We define

∇(π) := ∑_{i=1}^{k_{1}}(d_{i}(C_{1}) − d_{i−1}(C_{1}))d_{t_{i}}(C_{2}), π ∈ P(k_{1}, k_{2}; r),
d_{r}^{∗}(C_{1} ⊗ C_{2}) := min{∇(π) | π ∈ P(k_{1}, k_{2}; r)}.

The number d_{r}^{∗} was first defined in [15], and the following theorem was proved.

Theorem 2 (Wei–Yang 1993) If C_{1} and C_{2} are chained codes, then

d_{r}(C_{1} ⊗ C_{2}) ≤ d_{r}^{∗}(C_{1} ⊗ C_{2}) for all r.

The Wei-Yang conjecture says that d_{r}(C_{1}⊗C_{2}) = d_{r}^{∗}(C_{1}⊗C_{2}) for chained codes C_{1} and C_{2}. This has been proved for r ≤ 4 by Barbero and Teña [1]. Following the conjecture, d_{r}^{∗} has been determined for some linear codes by Helleseth and Kløve in [7]. It has also been proved that d_{r}^{∗}(C_{1} ⊗ C_{2}) = d_{r}^{∗}(C_{2} ⊗ C_{1}). Jeng Yune Park [10] has computed d_{r}^{∗} for products of certain classes of codes and shown that the conjecture holds for these classes.

Theorem 3 (Schaathun 2000) If C_{1} and C_{2} are arbitrary linear codes, then

d_{r}(C_{1} ⊗ C_{2}) ≥ d_{r}^{∗}(C_{1} ⊗ C_{2}) for all r.

The theorem has been proved in the language of projective multiset. Obviously Theorem 2 and 3 together prove the Wei-Yang conjecture.

A projective multiset is a collection of projective points which are not necessarily distinct. It is often presented as a map

γ : PG(k − 1, q) → {0, 1, 2, … }

where the value γ(x) of a point x is the number of times x occurs in the collection. We also define the value of a subset S ⊆ PG(k − 1, q) to be γ(S) = ∑_{x∈S} γ(x).

There is a well-known one-to-one correspondence between equivalence classes of projective multisets on PG(k − 1, q) and equivalence classes of linear qary codes of dimension k. See for instance [13,5,11]. The projective multiset γ corresponding to some [n, k] code C is obtained by taking the columns of some generator matrix for C as projective points.

The largest value of any subspace of codimension r in PG(k−1, q) is n−d_{r}(C). Hence the weight hierarchy can be computed in the language of projective multisets.

When a and b are projective points, the map a, b ↦ a ⊗ b is known as the Segre embedding. The image under the Segre embedding is called the Segre variety. The proof of Theorem 3 is based on the following key fact.

Proposition 4 Let γ_{A}, γ_{B}, and γ_{C} be the projective multisets corresponding to linear codes A, B, and C = A ⊗ B, respectively. We have:

γ_{C}(a ⊗ b) = γ_{A}(a) · γ_{B}(b), ∀a ∈ ℙ^{k_{A}−1}, ∀b ∈ ℙ^{k_{B}−1},
γ_{C}(c) = 0,  ∀c ∉ Y,

where Y is the Segre variety.

Theorem 5 For any two linear codes C_{1} and C_{2}, we have

d_{r}^{∗}(C_{1} ⊗ C_{2}) = d_{r}(C_{1} ⊗ C_{2}), r ∈ {0, 1, 2, k − 2, k − 1, k}.

This is well known for r = 0, 1, k. Wei and Yang proved it for r = 2. The proof for r = k − 2, k − 1 appears in [11], based on the language of projective multisets. For a six-dimensional product code C_{1} ⊗ C_{2}, we may or may not have d_{3}^{∗}(C_{1} ⊗ C_{2}) = d_{3}(C_{1} ⊗ C_{2}), see [11].

3 General Product Codes

Generalising the results from Section 2 we are lead to the following question: Given a family C_{1}, C_{2}, …, C_{t} of linear codes, what can we say about the weight hierarchy of C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}?

It is worth noting that the affirmative answer to the Wei-Yang conjecture has no implications for general product codes. Even if C_{1} and C_{2} are chained, C_{1} ⊗ C_{2} may be non-chained.

To answer the question, we generalise the definition of (k_{1}, k_{2})-partitions to (k_{1}, k_{2}, …, k_{t})-partitions.

Define

M_{t} := {i = (i_{1}, i_{2}, …, i_{t−1}) | 1 ≤ i_{j} ≤ k_{j}, 1 ≤ j < t}.

Note that M_{2} is just the set of integers from 1 through k_{1}. Hence an element π ∈ P(k_{1}, k_{2}; r) is a map π : M_{2} → {0, 1, …, k_{2}} where π(i) = t_{i}.

Definition 6 Let π be a map M_{t} → {0, 1, …, k_{t}} given by i ↦ t_{i}. We call π a (k_{1}, k_{2}, …, k_{t})-partition of r if

(1) ∑_{i∈M_{t}} t_{i} = r.

(2) π is a decreasing function in each coordinate, i.e.

t_{i_{1},...,i_{j},...,i_{t−1}} ≤ t_{i_{1},...,i_{j}−1,...,i_{t−1}}

for j = 1, …, t − 1 and 1 < i_{j}.

We define the general expression for d_{r}^{∗} as follows:

d_{r}^{∗}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}) := min {∇(π) | π ∈ P(k_{1}, k_{2}, …, k_{t}; r)},

where

∇(π) = ∑_{i∈M_{t}} ∏_{j=1}^{t−1}(d_{i_{j}}(C_{j}) − d_{i_{j}−1}(C_{j}))d_{π(i)}(C_{t}).

Theorem 7 (Martínez-Pérez–Willems 2000) If C_{1}, C_{2}, …, C_{t} are chained codes, then

d_{r}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}) = d_{r}^{∗}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}).

The Wei-Yang conjecture is just the special case of the theorem with t = 2.

The original proof of Theorem 7 above uses only elementary facts from linear algebra. For each subspace D ≦ C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t} there is a so-called normal subspace D̄ such that dim D = dim D̄ and #χ(D̄) ≤ #χ(D). Such a normal subspace D̄ is naturally associated to a (k_{1}, …, k_{t})-partition π and has support size ∇(π).

The following theorem is a new result. The proof is based on projective multisets, and it can also be extended to prove Theorem 7. We hope to publish the proof elsewhere.

Theorem 8 If C_{1}, C_{2}, …, C_{t} are arbitrary linear codes, then

d_{r}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}) ≥ d_{r}^{∗}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}).

By Theorem 3, we can obtain a lower bound for general product codes by recursion, but the theorem above is stronger than that. There is an analogue of Theorem 8 [12] for the greedy weights, which was introduced in [2,3].

A Some Future Work

The support weight distribution was introduced in [8]. It was proved that if the support weight distribution for C is known, then one can also find the weight distribution of C ⊗ S, where S is a simplex code. The support weight distribution is only known for a very few classes of codes. Is it possible to find the support weight distribution of some classes of product codes, such as the product of two simplex codes?

David Forney [6] proved that the generalised Hamming weights give a lower bound on the state complexity of a minimal trellis. It was proved that this bound is met with equality with some optimal bit ordering if and only if the code meets the so-called two-way chain condition. Is it possible to determine completely the state complexity of a product code, given the state complexities of the component codes?

References

[1] Angela I. Barbero and Juan G. Tena. Weight hierarchy of a product code. IEEE Trans. Inform. Theory, 41(5):1475–1479, September 1995.

[2] Wende Chen and Torleiv Kløve. On the second greedy weight for linear codes of dimension 3. To appear in Discrete Mathematics.

[3] Wende Chen and Torleiv Kløve. On the second greedy weight for binary linear codes. In M. Fossorier et al., editor, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, volume 1719 of Springer Lecture Notes in Computer Science, pages 131–141, 1999.

[4] Gérard D. Cohen, Sylvia B. Encheva, and Gilles Zémor. Antichain codes. Des. Codes Cryptogr., 18(1-3):71–80, 1999.

[5] S. Dodunekov and J. Simonis. Codes and projective multisets. Electron. J. Combin., 5(1), 1998. Research Paper 37.

[6] G. David Forney, Jr. Dimension/length profiles and trellis complexity of linear block codes. IEEE Trans. Inform. Theory, 40(6):1741–1752, 1994.

[7] Tor Helleseth and Torleiv Kløve. The weight hierarchies of some product codes. IEEE Trans. Inform. Theory, 42(3):1029–1034, 1996.

[8] Tor Helleseth, Torleiv Kløve, and Johannes Mykkeltveit. The weight distribution of irreducible cyclic codes with block lengths n_{1}((q^{l} − 1)/n). Discrete Math., 18:179–211, 1977.

[9] Conchita Martínez-Pérez and Wolfgang Willems. On the weight hierarchy of product codes. Preprint submitted to IEEE Trans. Inf. Theory, 2000.

[10] Jeng Yune Park. The weight hierarchies of some product codes. IEEE Trans. Inform. Theory, 46(6):2228–2235, November 2000.

[11] Hans Georg Schaathun. The weight hierarchy of product codes. IEEE Trans. Inform. Theory, 2000. To appear.

[12] Hans Georg Schaathun. A lower bound on the greedy weights of product codes. Submitted to ISIT, 2001.

[13] Michael A. Tsfasman and Serge G. Vlăduţ. Geometric approach to higher weights. IEEE Trans. Inform. Theory, 41(6, part 1):1564–1588, 1995. Special issue on algebraic geometry codes.

[14] Victor K. Wei. Generalized Hamming weights for linear codes. IEEE Trans. Inform. Theory, 37(5):1412–1418, 1991.

[15] Victor K. Wei and Kyeongcheol Yang. On the generalized Hamming weights of product codes. IEEE Trans. Inform. Theory, 39(5):1709–1713, 1993.