Corresponding Author: Vera Pless

University of Illinois at Chicago Department of Mathematics, Statistics, and Computer Science (M/C 249) 851 South Morgan Street Chicago, Illinois 60607-7045

pless@math.uic.edu

Abstract

There are known constraints on the number of doubly-even and singly-even vectors in a linear even binary code C. These constraints give information about C ∩C^{⊥}. We find new constraints on weights in a binary linear code C which also contains odd weight vectors. This leads to information about the dimension and weights of C ∩ C^{⊥}.

Key words: Weights, Constraints, Singly-Even, Doubly-Even

Running Head: Constraints on Weights in Binary Codes

Constraints on Weights in Binary Codes

Vera Pless

Dedicated to Aimo Tietäväinen on the occasion of his 60th birthday

1. Preliminaries

Notation and definitions can be found in [5].

All codes will be binary, linear codes. A binary code is called even if it only contains even weight vectors. It is shown in [1, 3, 6] that such a code is one of three types which we describe after giving some terminology. A doubly-even (d.e.) vector has weight ≡ 0(mod 4), while a singly-even (s.e.) vector has weight ≡ 2(mod 4).

A hyperbolic plane is a two dimensional space generated by two doublyeven vectors which are not orthogonal to each other. An anisotropic plane is generated by two singly-even non-orthogonal vectors. We write C_{1}⊥ C_{2} to mean the vector space direct sum of two codes C_{1} and C_{2} which are orthogonal to each other. If C is a code, let R(C) denote the largest doublyeven subcode of C ∩ C^{⊥} and let r = dim R(C). Let a denote the number of d.e. vectors in C and b denote the number of s.e. vectors in C. Then every even [n, k] code C is one of three types.

1. Hyperbolic Type.

Here C = R(C)⊥H_{2m} where H_{2m} is the orthogonal sum of m hyperbolic planes. Clearly k = r + 2m. In this case the following holds

a = 2^{r}(2^{2m−1} + 2^{m−1})

(1)

b = 2^{r}(2^{2m−1} − 2^{m−1})

2. Anisotropic Type.

Here C = R(C)⊥H_{2(m−1)}⊥A where H_{2(m−1)} is the orthogonal sum of (m − 1) hyperbolic planes and A is an anisotropic plane. Again k = r + 2m. Further,

a = 2^{r}(2^{2m−1} − 2^{m−1})

(2)

b = 2^{r}(2^{2m−1} + 2^{m−1})

3. Odd Anisotropic Type.

Here C = R(C)⊥H_{2m}⊥⟨x⟩ where x is a singly-even vector. Now k = r + 2m + 1 and a = b = 2^{k−1}.

See [7] for further discussion of this case.

These characterizations have many uses. They can show that a code with a certain weight distribution cannot be linear. For example, there is no linear code with the weight distribution of the Nordstrom Robinson code: A_{0} = A_{16} = 1, A_{6} = A_{10} = 112 and A_{8} = 30. Here a = 32 and b = 224. There are no numbers i and j so that b = 2^{i} + 2^{j} and a = 2^{i} − 2^{j}. These criteria can also be used to show that the Gray images of certain Z_{4} codes are not linear [2]. Other uses are to demonstrate non-existence in investigating the possible existence of codes with high minimum weight or in finding good covering codes.

It is clear that every self-orthogonal code which is not doubly-even is odd-anisotropic, however these are not the only codes of this type. Call an even code C formally self-dual (f.s.d.) if C and C^{⊥} have the same weight distributions [4]. There are f.s.d., not self-dual, odd anisotropic codes, for example the [6, 3, 2] code with the following generator matrix.

G = ( \begin{matrix}1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 \end{matrix} )

There are also f.s.d. hyperbolic and anisotropic codes whose weight distributions satisfy the MacWilliams identities as does the code above [4]. Clearly any self-dual code which is not doubly-even must be odd anisotropic.

2. The General Case

We start with the following theorem for even codes.

Theorem 1. Let C be an even binary code. If a = 2^{k−1}, then b = 2^{k−1} and C ∩ C^{⊥} is singly-even.

If not, then C ∩ C^{⊥} is doubly-even and a = 2^{k−1} ± 2^{s}, b = 2^{k−1} ∓ 2^{s} where dim C ∩ C^{⊥} = 2s − k + 2. Further, if a = 2^{k−2}, then r = 2^{k−2} which means that C ∩ C^{⊥} consists of all the d.e. vectors in C.

Proof: From the description of the types of even codes, it follows that R(C) is all of C ∩ C^{⊥} for both the hyperbolic and anisotropic codes. However in the odd anisotropic case C ∩ C^{⊥} = R(C)⊥⟨x⟩, a singly-even code.

In the cases that C ∩ C^{⊥} is doubly-even, its dimension follows from formulas (1) and (2) for a and b. □

Note that in the case that C ∩ C^{⊥} is singly-even, there is no information about its dimension and indeed this can vary. For example, the f.s.d. [6, 3, 2] code C with generator matrix G has dim ·C ∩ C^{⊥} = 1 whereas the unique self-dual [6, 3, 2] code (with the same weight distribution as C has dim C ∩ C^{⊥} = 3.

We now consider binary codes which contain odd-weight vectors. Again let a be the number of vectors whose weight is ≡ 0(mod 4) in such a code C and let b be the number of vectors in C of weight ≡ 2(mod 4). Note that a ≠ 0. Further let c be the number of vectors in C of weight ≡ 3(mod 4) and d the number whose weight is ≡ 1(mod 4).

If C is an [n, k] code let C_{e} denote the [n, k − 1] subcode which contains all the even weight vectors in C and \overline{C} be the [n + 1, k] extended code of C. Clearly \overline{C} is an even code and a + c is the number of its d.e. vectors while b + d is the number of its s.e. vectors.

The following theorem gives constraints on a, b, c and d and information about the dimension of C ∩ C^{⊥} whenever it is doubly-even. We also give information about the dimensions of C_{e} ∩ C_{e}^{⊥} and \overline{C} ∩ \overline{C}^{⊥} and tell when these codes are s.e. or d.e.

Theorem 2. Let C be a binary [n, k] code with odd weight vectors. If a = b = c = d = 2^{k−2} then C ∩ C^{⊥} is singly-even. In all other cases C ∩ C^{⊥} is doubly-even and we have the following pos-

sibilities.

Except where stated \frac{k − 2}{2} =^{<} s =^{<} k − 2 and 2 =^{<} k.

In the columns headed C_{e} ∩ C_{e}^{⊥}(\overline{C} ∩ \overline{C}^{⊥}) we tell whether these codes are s.e. or d.e. and give their dimensions (when known).

As C ∩ C^{⊥} is always d.e., we only give its dimension.

C_{e} ∩ C_{e}^{⊥}  C ∩ C^{⊥}  \overline{C} ∩ \overline{C}^{⊥}
1) a = b = 2^{k−2}  s.e.  d.e.
c = 2^{k−2} ± 2^{s}  2s − k + 3 2s − k + 2 2s − k + 2

d = 2^{k−2} ∓ 2^{s} If s = k − 2, C ∩ C^{⊥} consists of all the d.e. vectors in C.

2) a = 2^{k−2} ± 2^{s}  d.e.

In case of the minus sign, we take

s =^{<} k − 3.

b = 2^{k−2} ∓ 2^{s}  2s − k + 3

s.e.

(i) c = b, a = d  2s − k + 3 2s − k + 4

d.e.

(ii) c = a, b = d  2s − k + 3 2s − k + 4

d.e.

(iii) c = d = 2^{k−2}  2s − k + 2 2s − k + 2

Proof: If both C_{e} and \overline{C} are odd anisotropic, we have the first part of the theorem. This is the only case where we have no information about dim(C ∩ C^{⊥}). In fact, examples can be constructed where there are different values for this dimension.

If C_{e} is odd-anisotropic and \overline{C} is not, we have case 1) as a + c (b + d) is the number of d.e. (s.e.) vectors in \overline{C}. Noting that in this situation C ∩ C^{⊥} = R(C) = R(\overline{C}) gives its dimension from formulas ?? and ??.

Case 2) covers the situation in which C_{e} is either hyperbolic or anisotropic. Then C_{e} ∩ C_{e}^{⊥} is d.e. and its dimension follows from formulas ?? and ??.

Subcase i) is where \overline{C} is odd-anisotropic. Here C ∩ C^{⊥} = C_{e} ∩ C_{e}^{⊥}.

In subcases ii) and iii) \overline{C} is also either hyperbolic or anisotropic. This means that dim R(\overline{C}) is either dim(R(C_{e})) + 1 or dim(R(C_{e})) − 1. The former occurs in subcase ii) and the latter in subcase iii). In subcase ii)

C ∩ C^{⊥} = C_{e} ∩ C_{e}^{⊥} while in iii) C ∩ C^{⊥} = \overline{C} ∩ \overline{C}^{⊥}. □

This theorem can be used to obtain constraints on weights in cosets of codes.

Acknowledgement

I thank Richard Wilson for suggesting the questions treated here.

References

[1] Brouwer, A. E.: The Linear Programming Bound for Binary Linear Codes. IEEE Trans. Info. Th. 39, 677-688 (1993).

[2] Fields, J., Pless, V.: Methods for Classifying Z_{4} Codes. To appear in Proceedings of Thirty-Fourth Allerton Conference on Communication, Control and Computing, October, 1996.

[3] Kennedy, G. T.: Weight Distributions for Linear Codes and the Gleason-Pierce Theorem. J. Combin. Th. (A) 67, 72-88 (1994).

[4] Kennedy, G. T., Pless, V.: On Designs and Formally Self-Dual Codes, Designs, Codes and Cryptography 4, 43-55 (1994).

[5] Pless, V.: Introduction to the Theory of Error-Correcting Codes. Second edition, Wiley, New York, 1989.

[6] Pless, V.: Parents, Children, Neighbors and the Shadow. Contemporary Math. 168, 279-290 (1994).

[7] Simonis, J.: Restrictions on the Weight Distribution of Binary Linear Codes Imposed by the structure of Reed-Muller Codes. IEEE Trans. Inf. Th. 40, 194-196 (1994).