Codes and Projective Multisets

Stefan Dodunekov Institute of Mathematics and Informatics Bulgarian Academy of Sciences 8 G. Bontchev Str. 1113 Sofia, Bulgaria e-mail: stedo@moi2.math.acad.bg

Juriaan Simonis Delft University of Technology Faculty of Information Technology and Systems Department of Technical Mathematics and Informatics P.O. Box 5031 2600 GA Delft, the Netherlands e-mail: J.Simonis@twi.tudelft.nl

Submitted: December 25, 1997; Accepted: July 27, 1998.

Abstract The paper gives a matrix-free presentation of the correspondence between full-length linear codes and projective multisets. It generalizes the Brouwer-Van Eupen construction that transforms projective codes into two-weight codes. Short proofs of known theorems are obtained. A new notion of self-duality in coding theory is explored. 94B05, 94B27, 51E22.

1 Introduction

We start by describing the main idea in an informal way. Let G be a generator matrix of a q-ary linear [n, k, d]-code C, and let g_{1}, g_{2}, …, g_{n} ∈ 𝔽_{q}^{k} be the columns of G. Suppose that none of the g_{i}’s is the zero vector. (We say that the code C is of full length.) Then each g_{i} determines a point [g_{i}] in the projective space Π := ℙ(𝔽_{q}^{k}). If the g_{i} happen to be pair-wise independent, then X := {[g_{1}], [g_{2}], …, [g_{n}]} is a set of n points in Π. When dependence occurs, we interpret X as a multiset and count each point with the appropriate multiplicity. Different generator matrices yield projectively equivalent codes. In fact, we have a bijective correspondence between the equivalence classes of full-length q-ary linear codes and the projective equivalence classes of multisets in finite Desarguesian projective spaces. It is easy to recover minimum distance d of C from X. A nonzero codeword c := (c_{1}, c_{2}, …, c_{n}) ∈ C corresponds to the hyperplane H_{c} in Π with equation c_{1}ξ_{1} + c_{2}ξ_{2} + ⋯ + c_{n}ξ_{n} = 0 and the weight of c equals the size of X ∩ (Π \ H_{c}). So d = n − min |X ∩ H|, where H runs through the hyperplanes of Π.

The first one to use this relationship between linear codes and projective multisets was Slepian [27], who used the term modular representation. See also [25]. Delsarte, Hill and others studied the relation between projective two-weight codes and projective (n, k, h_{1}, h_{2}) sets. These are subsets of size n of ℙ(𝔽_{q}^{k}) with the property that every hyperplane is met in h_{1} points or h_{2} points. Two-weight codes are surveyed in Calderbank and Cantor’s paper [6].

Subsets of a finite projective space that have a small intersection with all subspaces of a given dimension have been extensively studied by finite geometers. In [17], Hirschfeld and Storme survey the known results with respect to so-called (n; r, s; N, q)- sets. These are spanning subsets K ⊂ ℙ(𝔽_{q}^{N+1}) of size n and such that all sdimensional projective subspaces of ℙ(𝔽_{q}^{N+1}) intersect K in at most s points. So (n; k − 2, n − d; k − 1, q)-sets correspond to q-ary linear [n, k, d]-codes for which the columns of any generator matrix are pair-wise independent. Other good references are the survey papers by Hill [16] and Landgev [22].

Yet another terminology has been introduced by Hamada and Tamari in [13]. They defined a minihyper (maxhyper) {f, m; t, q} to be a multiset w in ℙ(𝔽_{q}^{t+1}) of size f and such that all hyperplanes intersect w in at most (at least) m points. Hence there is a bijective correspondence between the {n, n − d; k − 1, q} maxhypers that span ℙ(𝔽_{q}^{k}) and the (equivalence classes) of q-ary linear [n, k, d]-codes. A recent survey of results on minihypers and their relation to codes meeting the Griesmer bound can be found in [14].

Goppa’s work [12] initiated a constant flow of contributions to coding theory by algebraic geometers. Of course, the natural setting here is the correspondence between linear codes and projective multisets. A good example is the book [32]. where the term ”projective system” is used. As a matter of fact, in Problem 1.1.9 of [32] the reader is invited to ”Rewrite existing books on coding theory in terms of projective systems”. The present paper can be regarded as a first step towards this goal.

Quite recently, Brouwer and Van Eupen published a gem of a paper, [5], in which they used a correspondence between projective codes and two-weight codes to construct optimal codes and to prove the uniqueness of certain codes. Their construction, a generalization of an old result on projective two-weight codes (cf. [15], Th. 8.7, or [6], Th. 5.2), transforms subsets of a finite projective space Π into multisets of the dual space Π^{∗}. Although mainly dual transforms of ”degree” one are considered, the final section of their paper gives a more general construction in which the degree of the dual transform is arbitrary. Our paper describes the dual transform in its full generality.

Outline of the paper

Section 2 contains a concise introduction to algebraic coding theory and fixes notation. In particular, we introduce the reduced distribution matrix of a code, a convenient notion in our treatment of the dual transform. In Section 3, we list some basic properties of projective multisets. The notion of lifting is introduced. We need this notion in Proposition 2 to repair a minor flaw in [5]. The section also contains a matrix-free presentation of the correspondence between full-length linear codes and projective multisets. Section 4 is devoted to the dual transform of multisets. We give simple expresssions of the basic parameters of the dual transform in terms of the reduced distribution matrix of the dual of the original code. Section 5 treats dual transforms of degree one. To demonstrate the effectiveness of this concept, we give short proofs of a theorem of Ward, a theorem of Bonisoli and the uniqueness of the generalized MacDonald codes. Finally, Section 6 explores a new kind of duality in coding theory. A code C is said to be σ-self-dual if its dual transform C^{σ} is equivalent to C. We give a list of examples and derive strong conditions in the case of transforms of degree one.

2 Codes

2.1 Basic definitions

Let 𝔽_{q} be the finite field of q elements and let S be a finite set of size n.

Definition 1 The standard vector space 𝔽_{q}^{S} over 𝔽_{q} is the 𝔽_{q}-vector space of the mappings

x : S → 𝔽_{q}.

(If S := {1, 2, …, n}, we usually write 𝔽_{q}^{n} for 𝔽_{q}^{S}.) The value of x ∈ 𝔽_{q}^{S} in s ∈ S is denoted by x_{s}.

The natural basis {e_{s} | s ∈ S} of 𝔽_{q}^{S} is defined by

(e_{s})_{t} := \{ \begin{matrix}1 & if & s = t, \\ 0 & if & s ≠ t. \end{matrix}

So the dimension of 𝔽_{q}^{S} is equal to n.

Definition 2 Let S, S′ be two sets of size n, and let {e_{s} | s ∈ S}, {e′_{s′} | s′ ∈ S′} be the natural bases of 𝔽_{q}^{S}, 𝔽_{q}^{S′} respectively. A linear isomorphism μ : 𝔽_{q}^{S} → 𝔽_{q}^{S′} is said to be monoidal if nonzero elements a_{s} ∈ 𝔽_{q} and a bijection σ : S → S′ exist such that μ(e_{s}) = a_{s}e′_{σ(s)} for all s ∈ S.

Definition 3 A q-ary (linear) code C of length n and dimension k is a k-dimensional linear subspace of the n-dimensional standard vector space 𝔽_{q}^{S}. Two codes C ⊆ 𝔽_{q}^{S}, C′ ⊆ 𝔽_{q}^{S′} are said to be equivalent if a monoidal isomorphism μ : 𝔽_{q}^{S} → 𝔽_{q}^{S′}exists such that μ(C) = C′.

2.2 Weight and distance

The Hamming weight |x| of a vector x ∈ 𝔽_{q}^{S} is the size of its support:

|x| := |{s | s ∈ S ∧ x_{s} ≠ 0}|.

The Hamming weight is a norm on the vector space 𝔽_{q}^{S}. The induced metric, with distance function

d(x, y) := |x − y|, x, y ∈ 𝔽_{q}^{S},

is called the Hamming metric. Note that the monoidal isomorphisms are precisely the linear isomorphisms that leave the Hamming weight invariant. Hence equivalent codes are isometric.

Definition 4 The weight distribution of a code C ⊆ 𝔽_{q}^{S} is the sequence

A_{0}(C), A_{1}(C), …, A_{n}(C)

defined by

A_{i}(C) := |{c | c ∈ C ∧ |c| = i}|, i = 0, 1, …, n.

The weight set of C is the set

W_{C} := {i | i ∈ {1, 2, …, n} ∧ A_{i}(C) ≠ 0}

and the minimum weight of C is the integer

d_{C} := min W_{C}.

Let

D_{i}(C, x) := |{c | c ∈ C ∧ d(x, c) = i}|

be the number of codewords at distance i from x ∈ 𝔽_{q}^{S}.

Definition 5 (Cf. [8]) The distribution matrix of C is the q^{n} × (n + 1) matrix D parametrized by 𝔽_{q}^{S} × {0, 1, …, n} having D_{i}(C, x) as its (x, i) entry.

The linearity of C immediately implies that D_{i}(C, x) = D_{i}(C, x + c) for all c ∈ C. In other words, the rows of D are constant on the cosets of C. Moreover, D_{i}(C, ax) = D_{i}(C, x) for all a ∈ 𝔽_{q} \ {0}. Hence the following definition makes sense.

Definition 6 The reduced distribution matrix of C is the \frac{q^{n−k}−1}{q−1} × (n + 1) matrix D̄ parametrized by ℙ(𝔽_{q}^{S}/C) × {0, 1, …, n} and having D_{i}(C, x) − D_{i}(C, o) as its ([x̄], i) entry. (Here x̄ denotes the vector in 𝔽_{q}^{S}/C corresponding to the coset x + C and [x̄] denotes the projective point determined by x̄ in the projective space ℙ(𝔽_{q}^{S}/C) over 𝔽_{q}^{S}/C.) The (i + 1)-st column of D̄ will be denoted by D̄_{i}.

2.3 Dual codes

The standard inner product on 𝔽_{q}^{S} is defined by

⟨x, y⟩ := ∑_{s∈S} x_{s}y_{s}, x, y ∈ 𝔽_{q}^{S}.

Definition 7 The dual of a code C ⊆ 𝔽_{q}^{S} is the code

C^{⊥} := {x | x ∈ 𝔽_{q}^{S} ∧ ⟨x, c⟩ = 0 for all c ∈ C}.

The external distance t_{C} of C is the size of the weight set of C^{⊥} and the dual distance of C is the minimum distance of C^{⊥}. A code C is said to be of full length if d_{C^{⊥}} ≥ 2 and projective if d_{C^{⊥}} ≥ 3.

The external distance of a code C gives information about its distribution matrix. In fact, Delsarte proved the

Theorem 1 ([8]) The rank of the distribution matrix D of C is equal to t_{C} + 1. In fact, the first t_{C} + 1 columns of D are independent and the i-th column of D can be expressed in these columns by a linear relation that only depends on k, n, q, i and the weight set W_{C^{⊥}} of C^{⊥}.

In 1963, MacWilliams found a remarkable relation between the weight spectra of C and C^{⊥}.

Theorem 2 ([23]) For i = 0, 1, …, n, we have the identities

∑_{j=0}^{n} \binom{n − j}{i}A_{j}(C) = q^{k−i} ∑_{j=0}^{n} \binom{n − j}{n − i}A_{j}(C^{⊥}).

If we solve this system of equations for the A_{j}(C), we find

A_{i}(C) = q^{k−n} ∑_{j=0}^{n} K_{i}(j)A_{j}(C^{⊥}),  (1)

with

K_{i}(j) := ∑_{m=0}^{i}(−1)^{m}(q − 1)^{i−m}\binom{j}{m}\binom{n − j}{i − m}.

The K_{i}(j) are polynomials of degree i in j, the so-called Krawtchouk polynomials, cf. [21]. A comprehensive description can be found in [24], pp. 129 ff., 150 ff.. We shall need the fact that the K_{i}(j) satisfy the orthogonality relations

∑_{j=0}^{n} K_{l}(j)K_{j}(i) = q^{n}δ_{l,i}, l, i = 0, 1, …, n.  (2)

3 Projective multisets

3.1 Basic definitions

Let Π := ℙ(V) be the projective space over a finite-dimensional 𝔽_{q}-vector space V, and let ℕ denote the set of the nonnegative integers.

Definition 8 A projective multiset in Π is a mapping γ : Π → ℕ of Π into ℕ. The multiplicity of a point p ∈ Π in γ is the integer γ(p). The multiplicity set of γ is the set

M_{γ} := Im γ.

If M_{γ} ⊆ {0, 1}, we identify γ with its support and call it a set.

Definition 9 The spanning space of γ is the projective span

Σ_{γ} := ⟨supp(γ)⟩

of the support

supp(γ) := {p | p ∈ Π ∧ γ(p) ≠ 0}.

of γ in Π. The dimension of γ is the integer

k_{γ} := dim Σ_{γ} + 1.

Definition 10 Two projective multisets γ, γ′ are said to be equivalent if a projective isomorphism φ : Σ_{γ} → Σ_{γ′} exists such that γ = γ′ ∘ φ.

For example, any projective multiset γ : Π → ℕ is equivalent to the restriction γ|_{Σ_{γ}} of γ to its spanning space.

We can extend the mapping γ to the power set of Π as follows.

Definition 11 If W ⊆ Π is any subset, then

γ(W) := ∑_{p∈W} γ(p).

In particular, the integer

n_{γ} := γ(Π)

is called the length of the multiset γ.

3.2 Projective multisets and full-length codes

In Definition 7, we defined a full-length code to be a code with dual distance ≥ 2. This can be rephrased as follows: a code C ⊆ 𝔽_{q}^{S} is of full length if and only if the natural basis {e_{s} | s ∈ S} does not intersect the dual code C^{⊥}.

Definition 12 Let C ⊆ 𝔽_{q}^{S} be a full-length code, and let \overline{e_{s}} denote the image of the standard basis vector e_{s} under the quotient mapping 𝔽_{q}^{S} → 𝔽_{q}^{S}/C^{⊥}. Then the multiset

γ_{C} : ℙ(𝔽_{q}^{S}/C^{⊥}) → ℕ, p ↦ |\{s | p = [\overline{e_{s}}]\}|

is called the projective multiset induced by C.

Remark 1 The multiset induced by C can be identified with the (second) column D̄_{1} of the reduced distribution matrix D̄ of C^{⊥}.

The length and dimension of a full-length code C are equal to the length and dimension of the induced multiset γ_{C}. A full-length code C is projective if and only if the induced multiset γ_{C} is a set.

Proposition 1 Any projective multiset is equivalent to a projective multiset induced by a code. Two induced multisets γ_{C}, γ_{C′} are equivalent if and only if the codes C, C′ are equivalent.

Proof. Let γ : Π := ℙ(V) → ℕ be a projective multiset of dimension k and length n. Choose a list (v_{1}, v_{2}, …, v_{n}) of vectors v_{i} ∈ V such that

{[v_{1}], [v_{2}], …, [v_{n}]} = supp(γ)

and such that each point p ∈ Π occurs in the list ([v_{1}], [v_{2}], …, [v_{n}]) with multiplicity γ(p). Consider the linear mapping φ : 𝔽_{q}^{n} → V fixed by φ(e_{i}) = v_{i}, i = 1, 2, …, n. If we put C := ker(φ)^{⊥}, then γ = γ_{C}. Secondly, if two full-length codes C, C′ are equivalent under a monoidal isomorphism μ : 𝔽_{q}^{S} → 𝔽_{q}^{S′}, then μ(C^{⊥}) = C′^{⊥}. So the induced projective isomorphism μ̃ : ℙ(𝔽_{q}^{S}/C^{⊥}) → ℙ(𝔽_{q}^{S′}/C^{′⊥}) is well-defined. It obviously defines an equivalence between the projective multisets γ_{C} and γ_{C′}.

Conversely, let C ⊆ 𝔽_{q}^{S}, C′ ⊆ 𝔽_{q}^{S′} be two full-length codes such that γ_{C} and γ_{C′} are equivalent. Let φ : 𝔽_{q}^{S}/C^{⊥} → 𝔽_{q}^{S′}/C^{′⊥} be a linear isomorphism such that the induced projective isomorphism φ̃ : ℙ(𝔽_{q}^{S}/C^{⊥}) → ℙ(𝔽_{q}^{S′}/C^{′⊥}) is an equivalence between γ_{C} and γ_{C′}. Then a bijection σ : S → S′ exists such that φ̃([\overline{e_{s}}]) = [\overline{e′_{σ(s)}}], s ∈ S. So nonzero elements a_{s} ∈ 𝔽_{q} exist such that φ(\overline{e_{s}}) = a_{s}\overline{e′_{σ(s)}}, s ∈ S. Now the monoidal isomorphism μ : 𝔽_{q}^{S} → 𝔽_{q}^{S′} fixed by μ(e_{s}) := a_{s}e′_{σ(s)}, s ∈ S, determines an equivalence between C and C′.

Notation If γ is a projective multiset, then C_{γ} denotes any code such that the multiset induced by C_{γ} is equivalent to γ. The preceding proposition shows that the code C_{γ} exists and that it is determined by γ up to equivalence.

3.3 Quotient multisets

An interesting way to obtain new projective multisets from old ones is by considering quotient spaces. Let U be an (m + 1)-dimensional linear subspace of the vector space V,and let L := ℙ(U) be the corresponding m-dimensional projective subspace of the projective space Π := ℙ(V). Then the points of the projective space

Π/L := ℙ(V/U)

can be identified with the (m + 1)-dimensional projective subspaces M of Π such that M ⊃ L. More generally, the i-dimensional subspaces of Π/L correspond to the (i + m + 1)-dimensional subspaces of Π that contain L. In particular, the dual space (Π/L)^{∗} will be identified with the subspace of Π^{∗} consisting of all hyperplanes in Π that contain L.

Definition 13 The quotient multiset of γ by L is the mapping γ^{L} : Π/L → ℕ defined by

(γ^{L})(M) := γ(M \ L), M ∈ Π/L.

Note that the dimension of γ^{L} is equal to k_{γ} − dim(L ∩ Σ_{γ}) − 1.

Remark 2 Let γ := γ_{C} be the projective multiset induced by the code C ⊆ 𝔽_{q}^{S}. An m-dimensional subspace L ⊆ ℙ(𝔽_{q}^{S}/C^{⊥}) is of the form ℙ(U), where U is a subspace of the vector space 𝔽_{q}^{S}/C^{⊥}. If W is the inverse image of U under the quotient mapping 𝔽_{q}^{S} → 𝔽_{q}^{S}/C^{⊥}, then D := W^{⊥} is a subcode of codimension m+1 in C and γ^{L} = γ_{D}. So the quotient multisets of γ correspond to the subcodes of C of the same codimension.

3.4 Weights

Now we turn to the dual space Π^{∗} of the projective space Π. (The points of Π^{∗} are the hyperplanes H ⊂ Π.)

Definition 14 The weight function of γ is the mapping

μ : Π^{∗} → ℕ, H ⟼ γ(Π \ H).

The weight set of γ is the set

W_{γ} := Im μ \ {0}.

The minimum weight of γ is the integer

d_{γ} := min W_{γ}.

The frequency of a weight w ∈ W_{γ} is the integer

f_{w}(γ) := q^{dim Σ_{γ}−dim Π}|μ^{−1}(w)|.

Note that μ^{−1}(0) = (Π/Σ_{γ})^{∗}. Hence μ takes the value 0 if and only if dim γ < dim Π + 1.

Remark 3 The weight distribution of C_{γ} and the frequencies f_{w}(γ) of γ are related as follows:

A_{i}(C_{γ}) = \{ \begin{matrix}1 & for & i = 0, \\ 0 & for & i ∉ W_{γ} ∪ \{0\}, \\ (q − 1)f_{w}(γ) & for & i ∈ W_{γ}. \end{matrix}

Hence the weight set of C_{γ} is equal to W_{γ}. In particular, the minimum weight of C_{γ} is the minimum weight of γ.

Example 1 Let the projective multiset γ be (the characteristic function of) the complement of a (u − 1)-dimensional subspace L of a (k − 1)-dimensional projective space Π. Denote by \left[{k \atop j}\right] the q-ary Gaussian binomial coefficient. If u = 0, then C_{γ} is called a simplex code, with parameters

[\left[{k \atop 1}\right], k, q^{k−1}].

It has only one weight: q^{k−1}. If k > u > 0,then C_{γ} is called a Macdonald code, with parameters

[\left[{k \atop 1}\right] − \left[{u \atop 1}\right], k, q^{k−1} − q^{u−1}].

This code is a two-weight code, with weights q^{k−1} − q^{u−1} and q^{k−1}. Both the simplex codes and the MacDonald codes attain the Griesmer bound. Hence they are lengthoptimal.

3.5 Simple constructions

In this section, we describe two methods of constructing a new projective multiset γ′ from a projective multiset γ. In both cases the parameters of γ′ only depend on those of γ and on the construction parameters.

3.5.1 Linear transforms

Let γ be a projective multiset on the projective space Π, and let a ∈ ℚ^{∗}, b ∈ ℚ be such that

γ′ : Π → ℚ, γ′(p) := aγ(p) + b,

is a projective multiset, i.e. such that Im γ′ ⊂ ℕ . Putting l := dim Π + 1, we find that

n_{γ′} = an + b\left[{l \atop 1}\right]

and

μ_{γ′}(H) = aμ_{γ}(H) + bq^{l−1}.

If b ≠ 0, the dimensions k, k′ of γ and γ′ may differ. In fact, if k′ ≠ k then either k = l or k′ = l.

If k′ ≤ k, then

W_{γ′} = {aw + bq^{l−1} | w ∈ W_{γ}} \ {0}

and

f_{w′}(γ′) = q^{k′−k}f_{w}(γ), w′ = aw + bq^{l−1}.

Three special cases are particularly important:

• γ′(p) := aγ(p), with a ∈ ℕ. Then the code C_{γ′} is said to be the a-fold replication of C_{γ}.

• γ′(p) := m − γ(p), with m := max M_{γ}. In this case C_{γ′} is called an anticode of C_{γ}. The Macdonald codes, for instance, are the anticodes of the simplex codes.

• γ′(p) := γ(p) + b, b ∈ ℕ. Then C_{γ′} is said to be obtained from C_{γ} by adding b simplex codes of dimension l.

Example 2 If we add t−1 simplex codes of dimension k to the [\left[{k \atop 1}\right]−\left[{u \atop 1}\right], k, q^{k−1}−q^{u−1}] MacDonald code, we obtain a generalized MacDonald code, with parameters

[t\left[{k \atop 1}\right] − \left[{u \atop 1}\right], k, tq^{k−1} − q^{u−1}].

3.5.2 Lifting

Let N be an (s − 1)-dimensional subspace of Π and let γ : Π/N → ℕ be a k-dimensional projective multiset of length n. Choose a nonnegative integer c and define a projective multiset γ′ on Π as follows:

γ′(p) := \{ \begin{matrix}c & if & p ∈ N, \\ γ(Np) & if & p ∉ N. \end{matrix}

We say that γ′ is obtained from γ by an (s, c)-lifting of γ to Π. If s > 0, the lifting is said to be proper. So a properly lifted projective multiset γ′ : Π → ℕ is characterized by the property that a nonempty projective subspace N ⊂ Π exists such that γ′ is constant on N and on all sets M \ N, M ∈ Π/N.

The dimension of γ′ is k + s and its length is q^{s}n + c\left[{s \atop 1}\right]. The weight function of γ′ is given by

μ_{γ′}(H) = \{ \begin{matrix}(q − 1)q^{s−1}n + q^{s−1}c & if & H ⊉ N, \\ q^{s}μ_{γ}(H) & if & H ⊇ N. \end{matrix}

Hence the minimum weight of γ′ is equal to

d_{γ′} = min{q^{s}d_{γ}, (q − 1)q^{s−1}n + q^{s−1}c}.

Note that the quotient multiset (γ′)^{N} is equivalent to q^{s}γ.

Remark 4 If γ, δ : Π/N → ℕ are equivalent, the (s, c)-lifted multisets γ′, δ′ : Π → ℕ are equivalent.

4 Dual transforms of multisets

4.1 Definition and basis properties

Now consider any function

σ : W → ℕ

on the weight set W := W_{γ} of a projective multiset γ : Π → ℕ. Let us extend this function to a polynomial function

σ(i) := ∑_{y∈W} σ(y)\frac{∏_{w∈W \y}(i − w)}{∏_{w∈W \y}(y − w)}

on ℚ by Lagrange interpolation. Note that the degree g := g_{σ} of the polynomial σ does not exceed |W | − 1 = t − 1, where t is the external distance of the dual of C_{γ}.

For each σ, we shall construct from γ a new multiset on the dual of the spanning space Σ := Σ_{γ}.

Definition 15 The dual transform of the projective multiset γ with respect to σ is the multiset

γ^{σ} : Σ^{∗} → ℕ, H ⟼ σ(μ(H)).

Obviously, the multiplicity set of Γ := γ^{σ} is the σ-image of the weight set of γ :

M_{Γ} = {σ(w) | w ∈ W_{γ}}.  (3)

The length of Γ is equal to

n_{Γ} = ∑_{w∈W} σ(w)f_{w}(γ)

and its weight function is given by

μ_{Γ}(p) = n_{Γ} − ∑_{H∋p} Γ(H) = ∑_{w∈W} σ(w){f_{w}(γ) − f_{w}(γ^{p})}, p ∈ Σ.  (4)

From (4), we see that the weight function μ_{Γ} is known if we can calculate the frequencies of all 1-codimensional quotient multisets γ^{p} of γ.

Now we turn to the dimension of Γ. The dual of the spanning space Σ_{Γ} of Γ is equal to N := μ_{Γ}^{−1}(0) ⊆ Σ_{γ}. Hence N is a projective subspace of Σ_{γ} and Σ_{Γ} = (Σ/N)^{∗}. This implies that the dimension k_{Γ} of Γ is equal to

k_{γ} − dim N − 1.

In particular,

k_{Γ} < k_{γ} ⟺ μ_{Γ}^{−1}(0) ≠ ∅.  (5)

4.2 Dual transforms of codes

Let C ⊆ 𝔽_{q}^{S} be a k-dimensional full-length code, and let σ be a function that takes integer values on the weight set of C.

Definition 16 The dual transform of C ⊆ 𝔽_{q}^{S} with respect to σ is the code C^{σ} := C_{Γ}, where Γ := γ^{σ}, the dual transform of γ := γ_{C} with respect to σ.

There is a bijective correspondence between the 1-codimensional subcodes D ⊂ C and the points p = [D^{⊥}/C^{⊥}] ∈ ℙ(𝔽_{q}^{S}/C^{⊥}). Since f_{w}(γ) = \frac{1}{q−1}A_{w}(C) and f_{w}(γ^{p}) = \frac{1}{q−1}A_{w}(D), we can use the MacWilliams identities (1) to express μ_{Γ} in terms of σ and the reduced distribution matrix D̄ of C^{⊥}. From equation (1), we get

μ_{Γ}(p) = ∑_{w∈W} σ(w){f_{w}(γ) − f_{w}(γ^{p})}

= \frac{1}{q − 1} ∑_{w∈W} σ(w)\{A_{w}(C) − A_{w}(D)\}

= \frac{1}{q − 1} ∑_{j=0}^{n} σ(j)\{A_{j}(C) − A_{j}(D)\}

= \frac{q^{k−n−1}}{q − 1} ∑_{j=0}^{n} σ(j) ∑_{i=0}^{n} K_{j}(i)\{qA_{i}(C^{⊥}) − A_{i}(D^{⊥})\}

= −q^{k−n−1} ∑_{i=0}^{n} ∑_{j=0}^{n} σ(j)K_{j}(i)D̄_{p,i}.

To simplify this further, let us express the polynomial σ in the Krawtchouk polynomials. There are – uniquely determined – rational numbers a_{0}, a_{1}, …, a_{g} such that

σ(j) = ∑_{l=0}^{g} a_{l}K_{l}(j).

The orthogonality relations (2) imply that

∑_{j=0}^{n} σ(j)K_{j}(i) = ∑_{l=0}^{g} a_{l} ∑_{j=0}^{n} K_{l}(j)K_{j}(i) = q^{n}a_{i}.

Hence

μ_{Γ}(p) = −q^{k−1} ∑_{i=0}^{g} a_{i}D̄_{p,i}.  (6)

We infer that the weight function μ_{Γ} of Γ is a linear combination of the first g + 1 ≤ t columns of the reduced distribution matrix D̄ of C^{⊥}.

We can express the length n_{C^{σ}} = n_{Γ} of C^{σ} in terms of the weight distribution of C^{⊥} :

n_{C^{σ}} = ∑_{w∈W_{γ}} σ(w)f_{w}(γ) =

= \frac{1}{q − 1} ∑_{j=0}^{n} σ(j)A_{j}(C) − \frac{σ(0)}{q − 1} =

= \frac{q^{k−n}}{q − 1} ∑_{i=0}^{n} ∑_{j=0}^{n} σ(j)K_{j}(i)A_{i}(C^{⊥}) − \frac{σ(0)}{q − 1} =

= \frac{q^{k}}{q − 1} ∑_{i=0}^{g} ∑_{j=0}^{n} a_{i}A_{i}(C^{⊥}) − \frac{1}{q − 1} ∑_{i=0}^{g} a_{i}(q − 1)^{i}\binom{n}{i} =

= ∑_{i=0}^{g} a_{i}\{\frac{q^{k}}{q − 1}A_{i}(C^{⊥}) − (q − 1)^{i−1}\binom{n}{i}\}.  (7)

An even simpler formula, in terms of the reduced distribution matrix D̄ of C^{⊥}, is

n_{C^{σ}} = − ∑_{i=0}^{g} a_{i} ∑_{p∈Π_{γ}} D̄_{p,i}.  (8)

Example 3 Let C be the unique binary [48, 8, 22]-code. (Cf. [9] for a construction and [18] for a computerized uniqueness proof.) The weight set of C is {22,24,30,32}. If we choose for σ the function with σ(22) = σ(30) = 1 and σ(24) = σ(32) = 0, then the dual transform C^{σ} turns out to be a [192, 8, 96]-code which in fact is optimal. Another, record breaking, example is the [245, 9, 120] code described in [19]. D. Jaffe found this example (and several others that happen to improve the table [4]) by means of an extensive computer search. The basic problem here is to develop a theory that predicts which input codes C and which transform functions σ produce record-breaking output codes C^{σ}.

4.3 The dual distance

If the dual distance of C is at least 2e + 1, i.e. if

A_{1}(C^{⊥}) = A_{2}(C^{⊥}) = ⋯ = A_{2e+1}(C^{⊥}) = 0,

the columns D̄_{1}, D̄_{2}, …, D̄_{e} of the reduced distribution matrix D̄ of C^{⊥} are {0, 1}- functions on Π whose supports are the projective images of the Hamming spheres of radius i, i = 1, …, e, in 𝔽_{q}^{S}. So

| supp(D̄_{i})| = (q − 1)^{i−1}\binom{n}{i}, i = 1, …, e.

Let us suppose that the degree g of the polynomial σ does not exceed e. Then we can calculate the parameters of the dual transform C^{σ} of C explicitly. Let Γ be the dual transform of γ := γ_{C} with respect to σ. Using (7) or (8), we find that the length of Γ (and C^{σ}) is equal to

n_{C^{σ}} = a_{0}\left[{k \atop 1}\right] − ∑_{i=1}^{g} a_{i}(q − 1)^{i−1}\binom{n}{i}.

The weight function μ_{Γ} is given by

μ_{Γ}(p) = \{ \begin{matrix}q^{k−1}(a_{0} − a_{i}) & if & p ∈ supp(D̄_{i}), \\ q^{k−1}a_{0} & if & p ∉ ⋃_{i=1}^{g} supp(D̄_{i}). \end{matrix}

The sets supp(D̄_{i}), i = 1, 2, …, g, fill the space ℙ(𝔽_{q}^{S}/C^{⊥}) if and only if n = k = g. Let us exclude that trivial case. Then the weight set of C^{σ} is equal to

{q^{k−1}(a_{0} − a_{i}) | i = 1 … e} ∪ {q^{k−1}a_{0}}

As to the dimension of C^{σ}, we observe that k_{Γ} = k unless a_{0} = 0 or a_{0} = a_{i} for some i between 1 and g.

Finally we calculate the frequencies of Γ. Suppose that k_{C^{σ}} = k. Then

f_{w}(Γ) = \{ \begin{matrix}\left[{k \atop 1}\right] − ∑_{\{j|j>0,a_{j}≠0\}}(q − 1)^{j−1}\binom{n}{j} & if & w = q^{k−1}a_{0,} \\ ∑_{\{j|j>0,a_{j}=a_{i}\}}(q − 1)^{j−1}\binom{n}{j} & if & w = q^{k−1}(a_{0} − a_{i}) ≠ q^{k−1}a_{0}. \end{matrix}

5 Dual transforms of degree one

Let C ⊆ 𝔽_{q}^{S} be a k-dimensional full-length code of length n, and let γ := γ_{C} be the corresponding projective multiset on Π := ℙ(𝔽_{q}^{S}/C^{⊥}). In this section, we study dual transforms C^{σ} under the assumption that the transform function σ is has degree one: σ(j) := aj + b. Two choices for σ are particularly useful: If Δ := gcd W, d := min W and D := max W, then the functions σ_{+} and σ_{−} defined by

σ_{+}(j) := \frac{j − d}{Δ}, σ_{−}(i) := \frac{−j + D}{Δ}  (9)

indeed take nonnegative integer values on W_{C}.

5.1 Length, weights, dimension, frequencies

Expressing the polynomial σ in the Krawtchouk polynomials K_{0}(j) := 1 and K_{1}(j) := (q − 1)n − qj, we get

σ(j) = a_{0}K_{0}(j) + a_{1}K_{1}(j) =

= (b + \frac{(q − 1)an}{q})K_{0}(j) + (−\frac{a}{q})K_{1}(j).

Let D := C^{σ} be the dual transform of C with respect to σ. Since the code C is of full length, i.e. A_{1}(C^{⊥}) = 0, Formula (7) for the length of D reduces to

n_{D} = a_{0}(\frac{q^{k}}{q − 1} − \frac{1}{q − 1}) + a_{1}n =  (10)

= nq^{k−1}a + \left[{k \atop 1}\right]b.

Now we consider the weight function of Γ := γ^{σ}. Formula (6) gives us

μ_{Γ}(p) = −q^{k−1}\{(b + \frac{(q − 1)an}{q})D̄_{p,0} + (−\frac{a}{q})D̄_{p,1}\} =
= q^{k−2}{qb + (q − 1)an + aγ(p)} =  (11)
= αγ(p) + β,

with

α := q^{k−2}a

and

β := q^{k−1}b + q^{k−2}(q − 1)an = \frac{(q − 1)n_{D} + b}{q}.

Remark 5 Note that the weight set W_{D} of D is equal to

{αm + β | m ∈ M_{γ}} \ {0}.

If, in particular, C is projective, then D is a (≤ 2)-weight code. This case is the main subject matter of Brouwer and Van Eupen’s paper [5].

Next we discuss the possibility of a dimension drop. Put

N := {p ∈ Π | αγ(p) + β = 0}.

This is a projective subspace of Π on which γ has the constant value −\frac{β}{α} = −q \frac{b}{a} − (q − 1)n. From (5) we see that the dimension k_{D} of D is equal to k unless

−q \frac{b}{a} − (q − 1)n ∈ M_{γ}.

If p ∈ Π \ N, then w := μ_{Γ}(p) ∈ W_{D}. Moreover γ takes the constant value \frac{w−β}{α} on Np \ N. Hence if k_{D} < k, then γ has to be a properly lifted projective multiset, cf. subsubsection 3.5.2.

Formula (11) immediately gives the minimum distance of D. If k_{D} = k, then

d_{D} = \{ \begin{matrix}(an + b)q^{k−1} + a(min M_{γ} − n)q^{k−2} & if & a > 0, \\ (an + b)q^{k−1} + a(max M_{γ} − n)q^{k−2} & if & a < 0. \end{matrix}

If k_{D} < k, then min M_{γ} and max M_{γ} have to be replaced by min(M_{γ} \ {min M_{γ}}) and max(M_{γ} \ {max M_{γ}}) respectively.

Finally, we see from (11) that the frequency of a weight w := αm + β of Γ is equal to

f_{w}(Γ) = q^{k−k_{D}}|γ^{−1}(m)|.

Example 4 An alternative construction of the [162, 8, 80]-codes (cf. [2]). There exist binary [21, 8, 8]-codes C_{1} and C_{2} with the same weight set {8, 12, 16}, but with A_{2}(C_{1}^{⊥}) = 0 and A_{2}(C_{2}^{⊥}) = 1 (cf. [18]). Hence we can calculate the values of |γ^{−1}(m)|:

|γ^{−1}(0)| |γ^{−1}(1)| |γ^{−1}(2)|
C_{1} 234  21  0
C_{2} 235  19  1

Consequently, as one of the referees of [2] pointed out, the codes C_{i}^{σ_{+}}, i = 1, 2, have parameters [162, 8, 80] and weight distributions

\begin{aligned}& A_{80} & A_{96} & A_{112} \\ C_{1}^{σ_{+}} & 234 & 21 & 0 \\ C_{2}^{σ_{+}} & 235 & 19 & 1 \end{aligned} .

5.2 The inverse of the dual transform

If γ, δ are equivalent k-dimensional projective multisets, then their dual transforms Γ, Δ with respect to any function σ obviously are equivalent as well. For dual transforms of degree one the converse is also true. This follows from the following proposition and Remark 4. We use the notation of the preceding subsection.

Proposition 2 Let Γ be the dual transform of γ with respect to a function σ of degree one. Then a function τ of degree one exists such that γ is an (s, c)-lifting of the dual transform γ′ of Γ with respect to τ. The parameters s and c depend only Γ, k_{γ} and σ.

Proof. From (11), we see that the function τ : j ↦ a′j + b′ defined by

a′ := \frac{1}{q^{k−2}a}, b′ := −q \frac{b}{a} − (q − 1)n = −\frac{(q − 1)n_{Γ} + b}{aq^{k−1}},

takes nonnegative integer values on W_{Γ}. The spanning space Σ_{Γ} of Γ is equal to (Σ/N)^{∗} and γ′ : Σ/N → ℕ takes the value γ(p) on Np, p ∉ N. So γ is an (s, c)-lifting of γ′, with s := k − k_{Γ} and c := b′.

Remark 6 This result is an extension of Section 4: ”Going Back and Forth” in [5], where only projective sets are considered and the absence of a dimension drop is tacitly assumed.

5.3 Short proofs of known results

As an amusing sideline, we give short proofs of a theorem of Ward, a theorem of Bonisoli and the uniqueness of the generalized MacDonald codes.

Proposition 3 ([33], Th. 1) Let C be a q-ary full-length code, and let Δ be the greatest common divisor of the codeword weights. If y is the maximal factor of Δ that is relatively prime to q, then C is a y-fold replicated code.

Proof. We use the notation of Subsection 5.1 and consider the σ_{+}-dual transform D of C. From the fact that

n_{Γ} = \frac{nq^{k−1}}{Δ} − \frac{q^{k} − 1}{q − 1} \frac{d}{Δ} ∈ ℕ

and Δ | d, we see that y | n. Since

μ_{Γ}(p) = −\frac{q^{k−1}d}{Δ} + \frac{q^{k−2}(q − 1)n}{Δ} + \frac{q^{k−2}γ(p)}{Δ} ∈ ℕ for all p ∈ Π,

we infer that y | γ(p) for all p ∈ Π.

Example 5 In [7], Cherdieu et al. described a code Γ_{0} with length q^{2n}, dimension n^{2} log_{r} q and weight distribution

w_{ρ} = q^{2n} − r^{−1}q^{2n} − r^{−1}(−1)^{ρ}q^{2n−ρ}(r − 1), ρ = 0, 1, ..., n

where n and r are integers > 1 , r | q. Since all weights w_{ρ}, ρ = 1, ..., n are divisible by q + 1, the code Γ_{0} is a (q + 1)-fold replicated code extended by an appropriate number of zero columns.

Proposition 4 ([1]) Let C be a q-ary k-dimensional full-length code with exactly one non-zero weight d. Then C is a \frac{d}{q^{k−1}} times replicated simplex code.

Proof. By counting the non-zero entries in the list of all codewords, we see that

n = \frac{(q^{k} − 1)d}{q^{k−1}(q − 1)}.

Consider the σ_{+}-dual transform Γ of γ_{C}. Note that Δ = d. Hence

n_{Γ} = \frac{nq^{k−1}}{d} − \frac{q^{k} − 1}{q − 1} \frac{d}{d} = 0,

which implies that

μ_{Γ}(p) = −\frac{q^{k−1}d}{d} + \frac{q^{k−2}(q − 1)n}{d} + \frac{q^{k−2}γ(p)}{d} =

= −\frac{1}{q} + \frac{q^{k−2}γ(p)}{d} = 0 for all p ∈ Π.

So γ is the constant function \frac{d}{q^{k−1}} .

Proposition 5 (Tamari [28]) The generalized MacDonald codes are unique.

Proof. Let C be a q-ary code with parameters

[t\left[{k \atop 1}\right] − \left[{u \atop 1}\right], k, tq^{k−1} − q^{u−1}],

and let γ := γ_{C} be the corresponding multiset in Π := ℙ(𝔽_{q}^{n}/C^{⊥}). Consider the dual transform Γ of γ with respect to σ : j ↦ j − tq^{k−1} + q^{u−1}. Substitution of the parameters in (11) yields

μ_{Γ}(p) = q^{k−2}(−t + 1 + γ(p)).

Since μ_{Γ} is nonnegative, the minimum multiplicity of γ must be at least t − 1. In fact this minimum is equal to t − 1, and |γ^{−1}(t − 1)| ≥ \left[{u \atop 1}\right], because t|Π| − n_{γ} = \left[{u \atop 1}\right]. Consequently, the dimension v − 1 of the projective subspace μ_{Γ}^{−1}(0) = γ^{−1}(t − 1) of Π is not smaller than u − 1. From Proposition 2, we see that γ is a (v, t − 1)-lifting of a multiset γ′. By Subsection 3.5.2, the length of γ′ is equal to

q^{−v}(n_{γ} − (t − 1)\left[{v \atop 1}\right]) = t\left[{k − v \atop 1}\right] + \frac{q^{u−v} − 1}{q − 1}.

This is an integer if and only if v ≤ u. Hence u = v. So γ(p) ≥ t outside a (u − 1)- dimensional subspace L := γ^{−1}(t − 1) ⊂ Π. But the existence of any point p with γ(p) > t would imply that

n_{γ} > t\left[{k \atop 1}\right] − \left[{u \atop 1}\right].

Hence

γ(p) = \{ \begin{matrix}t − 1 & if & p ∈ L, \\ t & if & p ∈ Π \ L. \end{matrix}

6 σ–self-dual codes

Let C ⊆ 𝔽_{q}^{S} be a k-dimensional full-length code, and let σ be a function that takes integer values on the weight set of C.

Definition 17 The code C is said to be self-dual with respect to σ if it is equivalent to its dual transform C^{σ}.

Example 6 Let C be the [48, 8, 22]-code C discussed in Example 3. If we take σ to be the function with σ(30) := 1 and σ(w) := 0 for w ∈ W_{C} \ {30}, then C^{σ} turns out to have the same parameters as C. Hence the uniqueness of C implies that it is self-dual with respect to σ.

Example 7 It is known [10] that there are exactly two nonequivalent binary [18, 6, 8]- codes C_{1}, C_{2}. Their weight distributions are

A_{8} A_{12} A_{16} A_{2}(C_{i}^{⊥})
C_{1} 46 16 1  1
C_{2} 45 18 0  0

Both codes are easily seen to be self-dual with respect to σ_{+}.

Example 8 The unique binary [51, 8, 24]-code has weight distribution A_{24} = 204 and A_{32} = 51 (cf. [18]). This code is self-dual with respect to σ_{+}.

Example 9 Let G be an incidence matrix of the finite projective plane 𝔓 := ℙ(𝔽_{p}^{3}), p prime, and let C be the q-ary code with generator matrix G. It is well known [26] that C is a [p^{2} +p+1, \frac{1}{2}(p^{2} +p+2), p+1]-code for which the words of minimum weight are the nonzero multiples of the rows of G. Let σ be the function with σ(p + 1) := 1 and σ(w) := 0 for w ∈ W_{C} \ {p + 1}. The existence of correlations in 𝔓 implies that the transpose G^{t} is a permutation of G. Hence C is self-dual with respect to σ.

If the transform function σ has degree one, it is easy to derive strong conditions on the parameters of self-dual codes with respect to σ :

Proposition 6 Let C be q-ary [n, k, d]-code which is self-dual with respect to the function σ : j ↦ aj + b. If C is not a replicated simplex code, then

a = ±q^{1− \frac{k}{2}} , b = −\frac{q − 1}{1 + q^{k−1}a}n.  (12)

Proof. Let (w_{1}, w_{2}, …, w_{r}) be the ordered weight set of C (and C^{σ}), and let (m_{1}, m_{2}, …, m_{r}) be the ordered multiplicity set of γ_{C} (and γ_{C^{σ}}). Since C is selfdual with respect to σ,the sizes of these sets are equal: r = s. Moreover (3) and (11) imply that either

w_{i} = q^{k−2}am_{i} + q^{−1}((q − 1)n + b),
m_{i} = aw_{i} + b

or

w_{i} = q^{k−2}am_{r−i} + q^{−1}((q − 1)n + b),
m_{i} = aw_{r−i} + b,

for i = 1, 2, …, r. Eliminating m_{i}, we find that

w_{i} = q^{k−2}a^{2}w_{i} + q^{k−2}ab + q^{−1}((q − 1)n + b).

If r > 1, then

q^{k−2}a^{2} = 1 and q^{k−2}ab + q^{−1}((q − 1)n + b) = 0,

which immediately gives (12). If r = 1, then C is an m_{1}-fold replicated simplex code. This code is self-dual with respect to the constant function σ = m_{1}.

Example 10 A. Brouwer [3] constructed a family of q-ary two-weight projective codes with parameters

n = (q^{e−1} − 1)(q^{de−e} + q^{\frac{de}{2} −e})/(q − 1), k = de,

where d and e are arbitrary integers, d even and e > 1. The weights are

w_{1} = (q^{e−1} − 1)q^{de−e−1}, w_{2} = w_{1} + q^{\frac{de}{2} −1}.

These codes satisfy the conditions (12) with respect to σ_{−}. It is not known if they are self-dual with respect to σ_{−}.

Remark 7 Choose q = 2, d = 2 in the above construction. Then the resulting code C_{1}(e) has parameters

n = 2^{2e−1} − 2^{e−1}, k = 2e

and

w_{1} = 2^{2e−2} − 2^{e−1}, w_{2} = 2^{2e−2}.

The code C(e) := ⟨C_{1}(e), 1⟩ , spanned by C_{1}(e) and the all-one vector 1, is a projective self-complementary [n, k + 1, w_{1}]-code with weight set {w_{1}, w_{2}, n}. It meets the Grey-Rankin bound. Since it is projective, the code

D(e) := RM(1, 2e)\C(e)

(the column set of the first order Reed-Muller code with the columns of C(e) deleted) has parameters

[2^{2e−1} + 2^{e−1}, 2e + 1],

and the weight set

{2^{2e−2}, 2^{2e−2} + 2^{e−1}, 2^{2e−1} + 2^{e−1}}.

It also meets the Grey-Rankin bound. For an alternative construction of codes with the above parameters see [20]. The partition

RM(1, 2e) = (C(e) | D(e))

shows that the number of nonequivalent projective self-complementary codes with parameters

[2^{2e−1} − 2^{e−1}, 2e + 1, 2^{2e−2} − 2^{e−1}]

coincides with the number of nonequivalent projective self-complementary codes with parameters

[2^{2e−1} + 2^{e−1}, 2e + 1, 2^{2e−2}].

In particular, since there are exactly 4 non-equivalent projective self-comple-mentary [28, 7, 12]-codes (cf.[11], [29]), it follows that there are exactly 4 nonequivalent projective self-complementary [36, 6, 16]-codes (cf.[29]).

Remark 8 Tonchev showed in [30] and [31] that there are exactly 5 nonequivalent [27, 6, 12] two-weight codes, with weight A_{12} = 36 and A_{16} = 27. All these codes satisfy the conditions (12) with respect to σ_{+}. As a matter of fact, Boukliev and Kapralov managed to show that they are self-dual with respect to σ_{+}. In general, however, it is not clear whether the conditions (12) imply self-duality in the case of transforms σ of degree 1.

Acknowledgments

This work was completed during the visit of S. Dodunekov to the Faculty of Technical Mathematics and Informatics, Delft University of Technology. He would like to thank Dr. Juriaan Simonis and Dr. Jan van Zanten for their support and hospitality and Mrs. C.A. van Baar for her assistance.

The paper was partially supported by the Bulgarian NSF grant MM502/95.

References

[1] Bonisoli, A. Every equidistant linear code is a sequence of dual Hamming codes. Ars Combin. 18 (1984), 181–186.

[2] Boukliev, I.; Dodunekov, S. M.; Helleseth, T.; Ytrehus, Ø. On the [162, 8, 80; 2] codes. IEEE Trans. Inform. Theory 43 (1997), no. 6, 2055–2057.

[3] Brouwer, A. E. Some new two-weight codes and strongly regular graphs. Discrete Appl. Math. 10 (1985), no. 4, 455–461.

[4] Brouwer, A. E.; Verhoeff, T. An updated table of minimum-distance bounds for binary linear codes. IEEE Trans. Inform. Theory 39 (1993), no. 2, 662–676. Online version: http://www.win.tue.nl/math/dw/voorlincod.html.

[5] Brouwer, A. E.; van Eupen, M. The correspondence between projective codes and 2-weight codes. Des. Codes Cryptogr. 11 (1997), no. 3, 262–266.

[6] Calderbank, A. R.; Kantor, W. M. The geometry of two-weight codes. Bull. London Math. Soc. 18 (1986), 97–122.

[7] Cherdieu, J. P.; Delcroix, A.; Mado, J. C.; Mercier, D. J. Weight distribution of the Hermition forms codes. Appl. Alg. Engrg. Comm. Comput. 8 (1997), no. 4, 307–314.

[8] Delsarte, P. An algebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl. No. 10 (1973), vi+97 pp.

[9] Dodunekov, S. M.; Manev, N. L. An improvement of the Griesmer bound for some small minimum distances. Discrete Appl. Math. 12 (1985), no. 2, 103–114.

[10] Dodunekov, S. M.; Encheva, S. B. Uniqueness of some linear subcodes of the binary extended Golay code. Problems Inform. Transmission 29 (1993), no. 1, 38–43; translated from Problemy Peredachi Informatsii 29 (1993), no. 1, 45–51 (Russian).

[11] Dodunekov, S. M.; Encheva, S. B.; Kapralov, S. N. On the [28, 7, 12] binary selfcomplementary codes and their residuals. Des. Codes Cryptogr. 4 (1994), no. 1, 57–67.

[12] Goppa, V. D. Codes on algebraic curves. Soviet Math. Doklady 24, 170–172; translated from Dokl. Akad. Nauk SSSR 259 (1981), no. 6, 1289–1290 (Russian).

[13] Hamada, N.; Tamari, F. On a geometrical method of construction of maximal t-linearly independent sets. J. Combin. Theory Ser. A 25 (1978), no. 1, 14–28.

[14] Hamada, N. A characterization of some [n, k, d; q]-codes meeting the Griesmer bound using a minihyper in a finite projective geometry. Discrete Math. 116 (1993), no. 1-3, 229–268.

[15] Hill, R. Caps and codes. Discrete Math. 22 (1978), no. 2, 111–137.

[16] Hill, R. Optimal linear codes. Cryptography and coding, II (Cirencester, 1989), 75-104, Inst. Math. Appl. Conf. Ser. New Ser., 33, Oxford Univ. Press, New York, 1992.

[17] Hirschfeld, J. W. P.; Storme, L. The packing problem in statistics, coding theory and finite projective spaces. To appear in J. Statist. Plann. Inference .(Proceedings of the Bose Memorial conference, Colorado, June 1995).

[18] Jaffe, D. B. Binary linear codes: new results on nonexistence. Draft version accessible through the author’s web page: http://www.math.unl.edu/^{∼}djaffe/, November 10,1997 (Version 0.5). Dept. of Math. and Statistics, University of Nebraska, Lincoln.

[19] Jaffe, D. B.; Simonis, J. New binary linear codes which are dual transforms of good codes. submitted to IEEE Trans. Inform. Theory. Online preprint available at http://www.math.unl.edu/^{∼}djaffe/.

[20] Jungnickel, D.; Tonchev, V. D. Exponential number of quasi-symmetric SDP designs and codes meeting the Grey-Rankin bound. Des. Codes Cryptogr. 1 (1991), no. 3, 247–253.

[21] Krawtchouk, M. Sur une généralisation des polynomes d’Hermite. Comptes Rendus 189 (1929), 620-622.

[22] Landgev, I. N. Linear codes over finite fields and finite projective geometries. To appear in Discrete Math..

[23] MacWilliams, F. J. A theorem on the distribution of weights in a systematic code. Bell System Tech. J. 42 (1963), 79-94.

[24] MacWilliams, F. J.; Sloane, N. J. A. The theory of error-correcting codes. 2nd reprint. North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam - New York - Oxford, 1983, xx+762 pp. ISBN: 0-444-85009-0 and 0-444-85010-4.

[25] Peterson, W. W.; Weldon, E. J., Jr. Error-correcting codes. Second edition. The M.I.T. Press, Cambridge, Mass. - London, 1972. xi+560 pp.

[26] Sachar, H. The 𝔽_{p} span of the incidence matrix of a finite projective plane. Geom. Dedicata 8 (1979), 407–415.

[27] Slepian, D. A class of binary signaling alphabets. Bell System Tech. J. 35 (1956), 203–234.

[28] Tamari, F. On linear codes which attain the Solomon-Stiffler bound. Discrete Math. 49 (1984), no. 2, 179–191.

[29] Tonchev, V. D. Quasi-symmetric designs, codes, quadrics, and hyperplane sections. Geom. Dedicata 48 (1993), no. 3, 295–308.

[30] Tonchev, V. D. The uniformly packed binary [27, 21, 3] and [35, 29, 3] codes. Proc. Int. Workshop on Optimal Codes and Related Topics, Sozopol, Bulgaria, May 26 - June 1, 1995, 130-136.

[31] Tonchev, V. D. The uniformly packed binary [27, 21, 3] and [35, 29, 3] codes. Discrete Math. 149 (1996), 283-288.

[32] Tsfasman, M. A.; Vladut, S. G. Algebraic-geometric codes. Translated from the Russian by the authors. Mathematics and its Applications (Soviet Series),

58. Kluwer Academic Publishers Group, Dordrecht, 1991 xxiv+667 pp. ISBN: 0-7923-0727-5.

[33] Ward, H. N. Divisible codes. Arch. Math. (Basel) 36 (1981), no. 6, 485–494.