A Lower Bound on the Weight Hierarchies of Product Codes

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, and this conjecture has recently been proved in two different ways. In this self-contained paper we give a further generalisation, with a new proof which also covers the old 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 [10] in 1991. An early project by Victor Wei and Kyeongcheol Yang [11] started determining 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.

Two different proofs of the conjecture have appeared recently [9,7]. Each of the proofs give interesting generalisations of the Wei-Yang conjecture. In this

Preprint submitted to Discrete Applied Mathematics (WCC 2001)6 February 2001

paper we give a further generalisation of these results. In the appendix, we suggest some open problems for future study.

1.1 Basic Notation

Let C be a linear [n, k] code over a finite field 𝔽_{q}. If S is a subset of 𝔽_{q}^{n}, let χ(S) denote the set χ(C) = ⋃_{s∈S} χ(s), where χ(s) = {i | s_{i} ≠ 0} for s = (s_{1}, s_{2}, …, s_{n}). The weight hierarchy of C is the sequence (d_{1}(C), …, d_{k}(C)), where

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

The weight hierarchy is an increasing sequence with d_{1}(C) the minimum Hamming distance. We call C a chained code if there exists a chain

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

such that D_{i} has dimension i and weight d_{i}(C).

We consider now the tensor product C = C_{1} ⊗ … ⊗ C_{t} of [n_{i}, k_{i}] codes C_{i}. Clearly, C is an [n, k] code, where n = n_{1}n_{2} … n_{t} and k = k_{1}k_{2} … k_{t}. What can we tell about the weight hierarchy of C from the knowledge of the weight hierarchies of the C_{i}?

2 The Main Result

To state the main result, we need some definitions. First let

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

Definition 1 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, and

(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}.

Let P(k_{1}, k_{2}, …, k_{t}; r) denote the set of all (k_{1}, k_{2}, …, k_{t})-partitions of r. For π ∈ P(k_{1}, k_{2}, …, k_{t}; r), we define

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

Note that ∇(π) depends on the weight hierarchies of all the codes C_{i}. Now let

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

for r = 1, 2, …, k. This number was first defined in [11] for t = 2. It was generalised to arbitrary t in [7].

Theorem 2 Let C = C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t} be the product of linear codes C_{i}. Then d_{r}(C) ≥ d_{r}^{∗}(C) for all r = 1, 2, …, k. Moreover, equality holds if all the components C_{i} are chained.

The Wei-Yang Conjecture [11] said that d_{r}^{∗}(C_{1} ⊗ C_{2}) = d_{r}(C_{1} ⊗ C_{2}) if C_{1} and C_{2} are chained. Several researchers worked with this conjecture throughout the nineties, and partial results appeared in [1,8]. The number d_{r}^{∗}(C) was computed for certain classes of codes in [4,8].

The case t = 2 of Theorem 2, and hence the Wei-Yang Conjecture, was proved in [9]. The generalisation for products of chained codes was performed in [7]. Thus only the upper bound remains to be proved.

We will give a complete proof of the entire theorem, using the techniques from [9]. This technique is very different from the one applied in [7].

3 Proof of the Theorem

3.1 Projective Multisets

We shall prove the theorem in the language of projective multisets, which naturally arise in coding theory by considering the columns of some generator matrix as representatives of points in the projective space ℙ^{k−1}. It is customary to assume that the code has no zero-positions. We make this assumption as well, but all the results are valid for codes with zero-positions.

For a projective multiset γ and a point x ∈ ℙ^{k−1}, we let γ(x) denote the multiplicity (or value) of x in γ. This definition is extended to S ⊂ ℙ^{k−1} by setting

γ(S) := ∑_{s∈S} γ(s).

Instead of using the weights, it is more convenient to deal with the dual weights Δ_{i}(C) which we define by

Δ_{i}(C) := n − d_{k−i−1}(C) = ∑_{j=0}^{i} δ_{j}(C),

where

δ_{i}(C) := d_{k−i}(C) − d_{k−i−1}(C).

Analogously, we write

Δ_{i}^{∗}(C) := n − d_{k−i−1}^{∗}(C).

Thus, in order to prove the theorem, we will prove that Δ_{r}(C) ≤ Δ_{r}^{∗}(C) for r = 0, 1, …, k − 1.

In [6], it was shown that there is a one-to-one correspondence between subcodes D ≦ C and subspaces Π ≦ ℙ^{k−1}, such that dim Π = k − 1 − dim D and γ(Π) = n − w(D). In particular, Δ_{r} = n − d_{r}(C) is the maximum value of any r-space Π ≦ ℙ^{k−1}. This is the fundamental lemma for studying higher weights in the language of projective multisets.

The following lemma should be fairly easy to verify by investigating the generator matrices, but a complete proof may be found in [9].

Lemma 3 If γ_{1} and γ_{2} are projective multisets corresponding to C_{1} and C_{2}, then the projective multiset corresponding to C_{1} ⊗ C_{2} is formed by the image of γ_{1} × γ_{2} under the Segre embedding.

The Segre embedding of ℙ^{k_{1}−1} × ℙ^{k_{2}−1} in ℙ^{k_{1}k_{2}−1} is given by

((x_{1}, x_{2}, …, x_{k_{1}}), (y_{1}, y_{2}, …, y_{k_{2}})) ↦ (x_{i}y_{j} | 1 ≤ i ≤ k_{1}, 1 ≤ j ≤ k_{2}).

This map is well-known in algebraic geometry [3]. It is an injective morphism, and its image is a subvariety of ℙ^{k_{1}k_{2}−1}, called the Segre variety.

Definition 4 For every π ∈ P(k_{1}, k_{2}, …, k_{t}; r), the dual partition is defined as

π^{∗}(i) := k_{t} − π((k_{1}, k_{2}, …, k_{t}) − i).

Note that π^{∗} ∈ P(k_{1}, k_{2}, …, k_{t}; k − r) and (π^{∗})^{∗} = π. Furthermore, we define

Δ(π) := n − ∇(π^{∗}).

With this notation, we get

Δ_{r}^{∗}(C) = n − d_{k−1−r}^{∗}(C)
= n − min{∇(π) | π ∈ P(k_{1}, k_{2}, …, k_{t}; k − 1 − r)}
= max{Δ(π^{∗}) | π ∈ P(k_{1}, k_{2}, …, k_{t}; k − 1 − r)}.

Hence

Δ_{r}^{∗}(C) = max{Δ(π) | π ∈ P(k_{1}, k_{2}, …, k_{t}; r + 1)}.

The next step is to derive a more accessible expression for Δ(π).

Definition 5 Let π ∈ P(k_{1}, k_{2}, …, k_{t}; r), and take s ∈ {1, 2, …, k_{1}}. The s-th subpartition π|_{s} of π is given by

π|_{s}(i_{2}, i_{3}, …, i_{t−1}) = π(s, i_{2}, i_{3}, …, i_{t−1}).

Clearly π|_{s} ∈ π ∈ P(k_{2}, k_{3}, …, k_{t}; r_{s}) for some integer r_{s}, and r_{1} + r_{2} + … + r_{k_{1}} = r.

Define also

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

Lemma 6 The dual (π|_{s})^{∗} of π|_{s} is the (k_{1} − s + 1)-th subpartition π^{∗}|_{k_{1}−s+1} of π^{∗}.

PROOF. We have

\begin{aligned}(π|_{s})^{∗}(i) & = k_{t} − π|_{s}(k_{2} + 1 − i_{2}, k_{3} + 1 − i_{3}, …, k_{t−1} + 1 − i_{t−1}) \\ & = k_{t} − π(s, k_{2} + 1 − i_{2}, k_{3} + 1 − i_{3}, …, k_{t−1} + 1 − i_{t−1}). \end{aligned}

Then we have

\begin{aligned}π^{∗}|_{k_{1}−s+1}(i) & = π^{∗}(k_{1} − s + 1, i_{2}, i_{3}, …, i_{t−1}) \\ & = k_{t} − π(s, k_{2} + 1 − i_{2}, k_{3} + 1 − i_{3}, …, k_{t−1} + 1 − i_{t−1}). \end{aligned}

□

Lemma 7 We have

Δ(π) = ∑_{i∈M_{t}} Δ_{t_{i}−1}(C_{t}) ∏_{j=1}^{t−1} δ_{i_{j}−1}(C_{j}),

for all π ∈ P(k_{1}, k_{2}, …, k_{t}; r) and 0 ≤ r ≤ k.

PROOF. The proof runs by induction on t. The lemma was proved for t = 2 in [9], so assume it holds for t − 1.

Observe that Δ(π) = n − ∇(π^{∗}). The definition of ∇(π^{∗}) from (1) is

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

Thus we get

∇(π^{∗}) = ∑_{i_{1}=1}^{k_{1}} [ ∑_{i∈M_{t}^{1}} d_{π^{∗}|_{i_{1}}(i)}(C_{t}) ∏_{j=2}^{t−1} δ_{k_{j}−i_{j}}(C_{j})]δ_{k_{1}−i_{1}}(C_{1})

= ∑_{i_{1}=1}^{k_{1}} [ ∑_{i∈M_{t}^{1}} d_{(π|_{k_{1}+1−i_{1}})^{∗}(i)}(C_{t}) ∏_{j=2}^{t−1} δ_{k_{j}−i_{j}}(C_{j})]δ_{k_{1}−i_{1}}(C_{1})

= ∑_{i_{1}=1}^{k_{1}} [n_{2} · n_{3} · . . . · n_{t} − Δ(π|_{k_{1}+1−i_{1}})]δ_{k_{1}−i_{1}}(C_{1})

= n − ∑_{i_{1}=1}^{k_{1}} Δ(π|_{k_{1}+1−i_{1}})δ_{k_{1}−i_{1}}(C_{1}).

Hence

Δ(π) = ∑_{i_{1}=1}^{k_{1}} Δ(π|_{k_{1}+1−i_{1}})δ_{k_{1}−i_{1}}(C_{1}) = ∑_{i_{1}=1}^{k_{1}} Δ(π|_{i_{1}})δ_{i_{1}−1}(C_{1}).  (2)

By the induction hypothesis, we get

\begin{aligned}Δ(π) & = ∑_{i_{1}=1}^{k_{1}} [ ∑_{i∈M_{t}^{1}} Δ_{t_{i}−1}(C_{t}) ∏_{j=2}^{t−1} δ_{i_{j}−1}(C_{j})]δ_{i_{1}−1}(C_{1}). \\ & = ∑_{i∈M_{t}} Δ_{t_{i}−1}(C_{t}) ∏_{j=1}^{t−1} δ_{i_{j}−1}(C_{j}), \end{aligned}

as required. □

Define

P̂(k_{1}, k_{2}, …, k_{t}; r) := ⋃_{r′≤r} P(k_{1}, k_{2}, …, k_{t}; r′).

We have a partial ordering on P̂(k_{1}, k_{2}, …, k_{t}; r) by setting π′ ≤ π if π′(i) ≤ π(i) for all i ∈ M_{t}. If π ∈ P(k_{1}, k_{2}, …, k_{t}; r) is a partition, write Σπ = r for its sum.

Note that if we have a sequence of (k_{2}, k_{3}, …, k_{t})-partitions π_{1} ≥ π_{2} ≥ … ≥ π_{m}, then the π_{i} define the subpartitions π|_{i} of some partition π ∈ P(k_{1}, k_{2}, …, k_{t}; r), where r = Σπ_{1} + Σπ_{2} + … + Σπ_{m}.

3.2 The simple case

In this section we study the product codes of two components. We will continue by induction on t in the next section. The proof here is slightly different from the proof given for t = 2 in [9].

Let C = C_{1}⊗C_{2}, where dim C = k. Let γ_{1}, γ_{2}, and γ be the projective multiset corresponding to C_{1}, C_{2}, and C respectively.

Let Π ≦ ℙ^{k−1}. We will define the associated partition π(Π) of Π. For 0 ≤ i ≤ k_{1} − 1, let Θ_{i} be the set of points b ∈ ℙ^{k_{2}−1} such that there is an i-space Φ_{i} ≦ ℙ^{k_{1}−1} with Φ_{i} ⊗ b ⊆ Π. Let π(Π)(i) = dim⟨Θ_{i−1}⟩ + 1 for i = 1, 2, …, k_{1}. Obviously Θ_{i} ⊆ Θ_{i−1}. Hence π(Π) is in deed a partition. Finally put t_{i} := dim⟨Θ_{i}⟩.

For x ∈ ℙ^{k_{2}−1} define

R(x) := {p ⊗ x ∈ Π | p ∈ ℙ^{k_{1}−1}}.

By the bilinearity of the Segre embedding we have R(x) ≦ ℙ^{k−1}.

Lemma 8 If Π ≦ ℙ^{k−1} is an r-space, then π(Π) ∈ P̂(k_{1}, k_{2}; r + 1).

PROOF. Let b_{0}, b_{1}, …, b_{k_{2}−1} be a basis for ℙ^{k_{2}−1} such that b_{0}, b_{1}, …, b_{t_{i}} ∈ Θ_{i}. For each i where 0 ≤ i < k_{2}, let b_{i}^{0}, b_{i}^{1}, …, b_{i}^{r_{i}} be a basis for R(b_{i}) where r_{i} = max{j | i ≤ t_{j}}. Clearly b_{i}^{j} = a_{i}^{j} ⊗ b_{i} for some a_{i}^{j} ∈ ℙ^{k_{1}−1}.

Consider the set

B := {b_{i}^{j} | 0 ≤ j ≤ k_{1} − 1, 0 ≤ i ≤ t_{j}}.

Clearly

#B = ∑_{i=0}^{k_{1}−1}(t_{i} + 1).

The set B is a set of projectively independent points, and B ⊆ Π. Since dim Π = r, we get

Σπ(Π) = ∑_{i=0}^{k_{1}−1}(t_{i} + 1) = #B ≤ r + 1,

proving the lemma. □

Lemma 9 If Π ≦ ℙ^{k−1}, then γ(Π) ≤ Δ(π(Π)).

PROOF. For convenience, we write Θ_{k_{1}} := ∅. If b ∈ Θ_{i}\Θ_{i+1}, then R(b) = Φ_{i}(b) ⊗ b, where Φ_{i}(b) is an i-space in ℙ^{k_{1}−1}.

Now

Π̄ = R(Θ_{0}) = ⋃_{b∈Θ_{0}} R(b) = ⋃_{i=0}^{k_{1}−1} ⋃_{b∈Θ_{i}\Θ_{i+1}}(Φ_{i}(b) ⊗ b).

Note that the union is disjoint. Hence

γ(Π̄) = γ( ⋃_{b∈Θ_{0}} R(b)) = ∑_{i=0}^{k_{1}−1} ∑_{b∈Θ_{i}\Θ_{i+1}} γ_{1}(Φ_{i}(b)) · γ_{2}(b)

≤ ∑_{i=0}^{k_{1}−1} ∑_{b∈Θ_{i}\Θ_{i+1}} Δ_{i}(C_{1}) · γ_{2}(b) = ∑_{i=0}^{k_{1}−1} δ_{i}(C_{1}) ∑_{b∈Θ_{i}} γ_{2}(b)

≤ ∑_{i=0}^{k_{1}−1} δ_{i}(C_{1})Δ_{t_{i}}(C_{2}) = ∑_{i=0}^{k_{1}−1} δ_{i}(C_{1})Δ_{π(i+1)−1}(C_{2})

= ∑_{i=1}^{k_{1}} δ_{i−1}(C_{1})Δ_{π(i)−1}(C_{2}) = Δ(π(Π)).

(3)

Thus the lemma is proved. □

Lemma 10 If Π′ ≦ Π ≦ ℙ^{k−1}, then π(Π′) ≤ π(Π).

PROOF. Let Θ_{i} and t_{i} be as in the definition of π(Π), and let Θ′_{i} and t′_{i} be the corresponding objects for Π′. We only have to prove that t′_{i} ≤ t_{i} for all i. We obtain Π′ from Π by removing points. Hence Θ′_{i} ⊆ Θ_{i} for all i, and t′_{i} ≤ t_{i} as required. □

3.3 The general case

The t component codes C_{i} correspond to t projective multisets γ_{i} on ℙ^{k_{i}−1} for i = 1, 2, …, t. Let γ be the multiset corresponding to C = C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}, and let k := dim C.

Lemma 11 For every subspace Π ≦ ℙ^{k−1} of dimension r there is a welldefined associated partition π(Π) ∈ P̂(k_{1}, k_{2}, …, k_{t}; r + 1) such that

(a) γ(Π) ≤ Δ(π(Π)); and

(b) if Π′ ≦ Π ≦ ℙ^{k−1}, then π(Π′) ≤ π(Π).

PROOF. We argue by induction on t. The base case, t = 2, is proved in Lemmata 8, 9, and 10. Write k′ := k_{2} · k_{3} · . . . · k_{t}. Let γ′ be the projective multiset corresponding to C_{2} ⊗ C_{3} ⊗ … ⊗ C_{t}.

Let Θ_{i} ⊆ ℙ^{k′−1} be the set of points p such that there exists an i-space Φ_{i} ≦ ℙ^{k_{1}−1} where Φ_{i} ⊗ p ⊆ Π. Obviously Θ_{i} ⊆ Θ_{i−1}. Let t_{i} := dim⟨Θ_{i}⟩.

By the inductive hypothesis (a) there is an (unique) associated partition π_{i} ∈ P̂(k_{2}, k_{3}, …, k_{t}; t_{i} + 1) to ⟨Θ_{i}⟩ such that

γ′(Θ_{i}) ≤ γ′(⟨Θ_{i}⟩) ≤ Δ(π_{i})  (4)

for each i. Furthermore π_{i} ≤ π_{i−1} by the inductive hypothesis (2) since Θ_{i} ⊆ Θ_{i−1}. Hence the π_{i} can be viewed as the k_{1} subpartitions of some partition π ∈ P̂(k_{1}, k_{2}, …, k_{t}; r′ + 1) where

r′ := ∑_{i=0}^{k_{1}−1}(t_{i} + 1) − 1.

More precisely, π(i_{1}, i_{2}, …, i_{t−1}) = π_{i_{1}−1}(i_{2}, i_{3}, …, i_{t−1}). By an argument similar to that in the proof of Lemma 8, we get that r′ ≤ r. Hence

π ∈ P̂(k_{1}, k_{2}, …, k_{t}; r + 1).

For x ∈ ℙ^{k′−1} define

R(x) := {p ⊗ x ∈ Π | p ∈ ℙ^{k_{1}−1}}.

By the bilinearity of the Segre embedding, R(x) ≦ ℙ^{k−1}. If b ∈ Θ_{i}\Θ_{i+1}, then R(b) = Φ_{i}(b) ⊗ b for some i-space Φ_{i}(b) ∈ ℙ^{k_{1}−1}.

Now we can write (as in the proof of Lemma 9),

Π̄ = R(Θ_{0}) = ⋃_{i=0}^{k_{1}−1} ⋃_{b∈Θ_{i}\Θ_{i+1}} R(b).

Hence we get

γ(Π̄) = ∑_{i=0}^{k_{1}−1} ∑_{b∈Θ_{i}\Θ_{i+1}} γ_{1}(Φ_{i}(b))γ′(b)

≤ ∑_{i=0}^{k_{1}−1} Δ_{i}(C_{1}) ∑_{b∈Θ_{i}\Θ_{i+1}} γ′(b) ≤ ∑_{i=0}^{k_{1}−1} δ_{i}(C_{1}) ∑_{b∈Θ_{i}} γ′(b)

= ∑_{i=0}^{k_{1}−1} δ_{i}(C_{1})γ′(Θ_{i}) ≤ ∑_{i=0}^{k_{1}−1} δ_{i}(C_{1})Δ(π_{i}) = Δ(π).

(5)

The bound in the last line follows from (4), and the very last equality follows from (2). This proves (a) assuming that (a) and (b) holds for t − 1. It remains to prove that (b) holds.

Let π′ be the partition associated with Π′, and let π′_{i} := π′|_{i} be the associated subpartitions. To prove the second statement of the lemma, it is sufficient to show that π′_{i} ≤ π_{i} for all i.

Let Θ′_{i} be the Θ_{i} related to Π′. Recall that π′_{i} is the partition associated with ⟨Θ′_{i}⟩. We obtain Π′ by removing points from Π. Hence ⟨Θ′_{i}⟩ ≦ ⟨Θ_{i}⟩, and by the inductive hypothesis π′_{i} ≤ π_{i} as required. □

3.4 When the Chain Condition holds

Lemma 12 If C_{1}, C_{2}, …, C_{t} satisfy the chain condition, then for every π ∈ P(k_{1}, k_{2}, …, k_{t}; r + 1) there is an r-space Π ≦ ℙ^{k−1} such that π(Π) = π and Δ(π) = γ(Π).

Moreover, if π′ ∈ P(k_{1}, k_{2}, …, k_{t}; r′ + 1) and π′ ≤ π, then there is an r′-space Π′ ≦ Π such that π(Π′) = π′ and Δ(π′) = γ(Π′).

PROOF. First consider the case where t = 2. Let p_{0}, p_{1}, …, p_{k_{1}−1} be a basis for ℙ^{k_{1}−1} such that ⟨p_{0}, p_{1}, …, p_{i}⟩ is an i-space of maximum value. Let

∅ = Φ_{−1} ⊂ Φ_{0} ⊂ … ⊂ Φ_{k_{2}−1} = ℙ^{k_{2}−1}

be a chain of subspaces of maximum value. Write t_{i} = π(i + 1) − 1 for i = 0, 1, …, k_{1} − 1, and let Π = ⟨p_{i} ⊗ Φ_{t_{i}} | i = 0, 1, …, k_{1} − 1⟩. Clearly dim Π = r. As for the value, it is not hard to verify equality in (3). This proves the first statement of the lemma for t = 2.

Let t′_{i} = π′(i + 1) − 1 for i = 0, 1, …, k_{1} − 1, and let Π′ = ⟨p_{i} ⊗ Φ_{t′_{i}} | i = 0, 1, …, k_{1} − 1⟩. Clearly Π′ ⊂ Π, and the remaining properties of Π′ follows by the argument above. Hence the lemma is proved for t = 2.

Assuming that the lemma holds for t − 1, the inductive step is similar. Let p_{0}, p_{1}, …, p_{k_{1}−1} be a basis for ℙ^{k_{1}−1} such that ⟨p_{0}, p_{1}, …, p_{i}⟩ is an i-space of maximum value. Let π_{i} = π|_{i} be the subpartitions of π. By the inductive hypothesis, there is a chain of subspaces

Φ(π_{k′}) ⊆ Φ(π_{k′−1}) ⊆ … ⊆ Φ(π_{1}) ⊆ ℙ^{k′−1},

where all the Φ-s have maximum value and γ(Φ(π_{i})) = Δ(π_{i}). We define

Π = ⟨p_{i} ⊗ Φ(π_{i}) | i = 0, 1, …, k_{1} − 1⟩.

Clearly dim Π = ∑_{i=1}^{k_{1}} Σπ_{i} − 1 = r. The value is given by (5), and it may be verified that equality holds.

Consider at last a partition π′ ≤ π. We construct as above a chain of subspaces

Φ(π′_{k′}) ⊆ Φ(π′_{k′−1}) ⊆ … ⊆ Φ(π′_{1}) ⊆ ℙ^{k′−1}.

This can, by the induction hypothesis, be done such that Φ(π′_{i}) ⊆ Φ(π_{i}). We define

Π′ = ⟨p_{i} ⊗ Φ(π′_{i}) | i = 0, 1, …, k_{1} − 1⟩.

Clearly Π′ ⊆ Π, and the remaining properties are proved as in the previous paragraph. □

A Some Future Work

The support weight distribution was introduced in [5]. 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 [2] 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] G. David Forney, Jr. Dimension/length profiles and trellis complexity of linear block codes. IEEE Trans. Inform. Theory, 40(6):1741–1752, 1994.

[3] Joe Harris. Algebraic Geometry. Springer Verlag, 1992.

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

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

[6] Tor Helleseth, Torleiv Kløve, and Øyvind Ytrehus. Generalized Hamming weights of linear codes. IEEE Trans. Inform. Theory, 38(3):1133–1140, 1992.

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

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

[9] Hans Georg Schaathun. The weight hierarchy of product codes. IEEE Trans. Inform. Theory, 46(7):2648–2651, November 2000.

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

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