ISIT2000, Sorrento, Italy, June 25–30, 2000

Projective Systems and Higher Weights

Hans Georg Schaathun

Department of Informatics University of Bergen Høyteknologisenteret N-5020 Bergen, Norway

                                          e-mail: georg@ii.uib.no

Abstract — We use projective multisets (projective systems) to find upper bounds on the weight hierarchies for a special class of codes, namely the extremal non-chain codes. Several code constructions exist meeting the bounds with equality.

I. Introduction

Let C be a linear q-ary code of dimension k and length n. The weight w(S) of a subcode S ⊆ C, is the number of positions where at least one word in S differs from zero. The rth generalised Hamming weight d_{r} of C is the least weight of an r-dimensional subcode of C. The sequence (d_{1}, d_{2}, …, d_{k}) is called the weight hierarchy of C [6].

II. Extremal Non-Chain Codes

The chain condition was introduced in [7], and states that there is a chain D_{0} ⊂ … ⊂ D_{k} of subcodes, where D_{i} has dimension i and weight d_{i}.

The opposite extreme are the extremal non-chain codes, defined as follows. For each pair (i, j) where 1 ≤ i < j < k, there are no subcodes D_{i} ⊆ D_{j} of dimensions i and j respectively such that w(D_{i}) = d_{i} and w(D_{j}) = d_{j}. The extremal non-chain codes were introduced by Chen and Kløve [1], and this study continues their work.

III. Projective Multisets

Let G be a k × n generator matrix of C. By permuting columns of G or by multiplying certain columns by non-zero scalars, we get an equivalent code. Equivalent codes have the same weight hierarchy.

Let PG(k−1, q) be the projective (k−1)-space over the finite field with q elements. The code C is determined up to equivalence by giving the map γ : PG(k − 1, q) → {0, 1, …}, saying how many times each projective point occurs as a column in G. Such a map is called a projective multiset [2], a projective system [5], or a value assignment [1, 4]. The definition of γ is extended by γ(S) = ∑_{x∈S} γ(x) for all S ⊆ PG(k − 1, q). The number γ(S) is called the value of S.

We know [3, 5] that a subcode D_{r} of dimension r and weight w, corresponds to a subspace S_{r} ⊆ PG(k − 1, q) of dimension k − r − 1 and value γ(S_{r}) = n − w. Hence a subcode D_{r} of minimum value corresponds to a projective subspace S_{r} of maximum value. Also if D_{r} ⊆ D_{r′}, then S_{r} ⊇ S_{r′}.

The difference sequence (δ_{0}, δ_{1}, …, δ_{k−1}) is defined by δ_{i} = d_{k−1} − d_{k−1−i}. The difference sequence is easily computed from the weight hierarchy and vice versa. If S is an i-space of maximum value, then γ(S) = δ_{0} + δ_{1} + … + δ_{i}. A difference sequence corresponding to an extremal non-chain code is called an ENDS (Extremal Nonchain Difference Sequence).

IV. Results

Theorem 1 (General Bound) If (δ_{0}, δ_{1}, …, δ_{k−1}) is an

ENDS, 1 ≤ m ≤ k − 2, then

δ_{m} ≤ q^{m}δ_{0} − \frac{q^{m+1} − 1}{q − 1} .

If equality holds for m = m̄, then equality holds for all m < m̄.

Theorem 2 (Binary Codes) If (δ_{0}, δ_{1}, …, δ_{k−1}), k ≥ 4 is a binary ENDS, then

δ_{k−2} ≤ 2^{k−3}δ_{1} − 2 − 2^{k−3}.

Theorem 3 (Total Value) If (δ_{0}, δ_{1}, …, δ_{k−1}), k ≥ 3 is an ENDS, then

γ(PG(k − 1, q)) ≤ ∑_{i=0}^{m−1} δ_{i} + (δ_{m} − 1) \frac{q^{k−m} − 1}{q − 1} ,

for all m such that 1 ≤ m ≤ k − 2.

Explicit constructions meeting the bounds with equality exist in dimension 5 and less, provided δ_{0} is sufficiently large; δ_{0} ≥ 5 is sufficient in all cases.

Acknowledgments

Most of this work is part of my graduate thesis. I am grateful to prof. Torleiv Kløve for all his help as a superviser in all stages of the work.

References

[1] Wende Chen and Torleiv Kløve. Bounds on the weight hierarchies of extremal non-chain codes of dimension 4. Applicable Algebra in Engineering, Communication and Computing, 8:379–386, 1997.

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

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

[4] Hans Georg Schaathun. Upper bounds on weight hierarchies of extremal non-chain codes. Technical Report 171, Department of Informatics, University of Bergen, 1999. Also available at http://www.ii.uib.no/∼georg/sci/inf/coding/public/.

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

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

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