Coding Constructions

Vera Pless

There are very many interesting constructions of codes. We cannot cover all or even most of them. Some are contained in other chapters. We begin with codes which are constructed from other codes.

1 Related codes

We recall some standard constructions which are described in Chapter 1. If C_{i}, i = 1, 2, are [n_{ij}, k_{ij}, d_{i}] codes with generator matrices G_{i}, then their direct sum C_{1} ⊕ C_{2} is an [n_{1} + n_{2}, k_{1} + k_{2}, min(d_{1}, d_{2})] code with generator matrix

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

Direct sums are used in many contexts. As can be seen from the minimum weight, this construction is not used to build codes with high minimum weight. However, the extended binary Golay code can be constructed from “glueing” a direct sum of an [8,1,8] code and a [16,5,8] code.

If C is an [n, k, d] code with d > 1, then a punctured code C^{∗} is the [n − 1, k] code resulting from omitting some coordinate from all codewords. If G is a generator matrix of C, then a generator matrix of C^{∗} is obtained from G by removing the special column. If C has a transitive group, then all of its punctured codes will be equivalent. Otherwise, they may not be. We can extend C to an [n + 1, k] code Ĉ by adding a new coordinate so that the sum of all coordinates is 0. If C is a binary code, the extended code has only even weight codewords. We will give natural constructions of the Golay codes and constructions of the extended Golay codes will follow from that. There are also natural constructions of the extended Golay codes, and the Golay codes are obtained from these as punctured codes. If H is a parity check matrix for C and the new coordinate for Ĉ is the last one, then a parity check matrix for Ĉ is the matrix

Ĥ = [ \begin{matrix}1 ⋯ 1 & 1 \\ & 0 \\ H & 0 \end{matrix} ] .

If T is a set of coordinate positions, the code obtained from puncturing on T is denoted by C^{T}. If T consists of one point, this is the punctured code C^{∗}. If we let C^{0} be the subcode of C consisting of the codewords in C which are zero on all the coordinates in T, then the shortened code of C, with respect to T, is the length n − |T | linear code (C^{0})^{T} denoted by C_{T}. From the matrix above we see that the shortened code of (Ĉ)^{⊥} with respect to the extended position is C^{⊥}. The general form of this is Lemma 10.1 of Chapter 1 which we repeat.

Lemma 1. Let C be an [n, k, d] code and let T be a set of coordinate positions. Then

(i) (C^{T})^{⊥} = (C^{⊥})_{T} and (C^{⊥})^{T} = (C_{T})^{⊥} and

(ii) if |T | < d, then dim C^{T} = k so that dim(C^{⊥})_{T} = n − |T | − k.

Shortening the binary [24,12,8] Golay code on the positions of a weight 8 vector in the code gives a [16,5,8] code which must be equivalent to the Reed-Muller code R(1, 4). If we consider all codewords in a code C which have a given set of components (not necessarily all zero) on certain fixed positions, then deleting those positions also gives a code which is usually non-linear. This is one way to construct the Nordstrom-Robinson (16, 2^{8}, 6) code [Chapter 1, Section 14]. So very good codes can be obtained from shortening very good codes.

In the case that the positions in T are those of a codeword c in C of weight |T | = t, C^{T} is the residual code of C with respect to c, Res(C, c). The first part of the next lemma is in Chapter 1 [Lemma 3.9].

Lemma 2. Let C be an [n, k, d] code over F_{q} and let c be a codeword of weight t where t < \frac{q}{q−1}d.

Then Res (C, c) is an [n − t, k − 1, d′] code where

d − ⌊\frac{t}{q} ⌋ =^{<} d′.

If, further, q = 2 and t = d^{∗} is the weight of a maximal weight vector in C and w is the weight of a vector in Res (C, c), then

d − ⌊\frac{d^{∗}}{2} ⌋ =^{<} w =^{<} ⌊\frac{d^{∗}}{2} ⌋.

The last part of the lemma is in [4].

In Chapter 1, the residual code was used to demonstrate the non-existence of a code with certain parameters. It has also been used to find good codes [Chapter on tables, this handbook].

We close this section with some facts about the weights in binary linear codes which can be used to show that codes with certain weight distributions cannot exist or even, at certain times, construct codes with specified weight distributions. If C is a self-orthogonal binary code, then it is clear that either half the weights in C are divisible by 4 or all of them are. This is not always true for even codes as we see in the next theorem portions of which are in [3,20].

Theorem 1. Let C be a binary [n,k] code with all weights even. Let a be the number of weights in C which are ≡ 0(mod4). Let b be the number of weights in C which are ≡ 2(mod4).

If a = 2^{k−1}, then b = 2^{k−1} and C ∩ C^{⊥} is singly-even.

If a ≠ 2^{k−1}, then either a = 2^{k−1} ± 2^{k+(r−2)/2} and b = 2^{k−1} ∓ 2^{k+(r−2)/2} where

r = dim(C ∩ C^{⊥})

and (C ∩ C^{⊥}) is singly-even.

From the weight distribution of the Nordstrom Robinson code (Chapter 1) we see that a = 32 and b = 224. If this were the weight distribution of a linear code, then we would have b − a = 2^{j+1}, but 224 − 32 is not a power of 2. This shows that the Nordstrom- Robinson code cannot be linear.

There is a [16,7,6] B.C.H. code C with A_{0} = A_{16} = 1, A_{6} = A_{10} = 48 and A_{8} = 30. The previous theorem tells us that C ∩ C^{⊥} is a doubly -even [16,5,8] code. A code with this weight distribution is uniquely determined and is R(1, 4). Hence in order to construct C we need to find two vectors of weight 6 (coset leaders of weight 6 cosets of R(1, 4) ) which are not orthogonal to each other or to R(1, 4) and whose sum is again in a coset of weight 6.

This theorem is used to show that binary linear codes with certain parameters cannot exist. There is a similar theorem for linear ternary codes which is also used to demonstrate non-existence[21] and [16].

2 Building Codes

Another construction that has yielded good codes from known codes C_{1} and C_{2} is the (u|u+v) construction where u is in C_{1} and v is in C_{2}. Clearly C_{1} and C_{2} must be of the same length n and over the same field GF (q). If C_{i}, i = 1, 2, are [n, k_{i}, d_{i}] codes, then this construction gives a [2n, k_{1} + k_{2}, min(2d_{1}, d_{2})] code C over GF (q). The length and dimension of C are immediate. To see the statement about the minimum weight of C we note that if v = 0, then C contains vectors of weight 2d_{1}, and if u = 0, vectors of weight d_{2}. The fact about the minimum weight follows as wt(x + y) =^{>} wt(x) − wt(y), for any vectors x and y, so that wt(u|u + v) = wt(u) + wt(u + v) =^{>} wt(u) + wt(v) − wt(u) = wt(v). Hence if wt(v) ≠ 0, wt(u|u + v) =^{>} d_{2} and if wt(v) = 0, wt(u|u + v) =^{>} 2d_{1}. If C_{i}, i = 1, 2, have generator matrices G_{i} and parity check matrices H_{i}, then the following are generator and parity check matrices for C.

G = ( \begin{matrix}G_{1} & G_{1} \\ 0 & G_{2} \end{matrix} ) , H = ( \begin{matrix}H_{2} & H_{2} \\ H_{1} & 0 \end{matrix} )

This construction is one way to obtain the binary Reed-Muller code R(r, m) from R(r − 1, m − 1) and R(r, m − 1). If the C_{i}, i = 1, 2, are nonlinear (n, M_{i}, d_{i}) codes over the same field, then the (u|u + v) construction gives a non-linear (2n, M_{1}M_{2}, min(2d_{1}, d_{2})) code.

If C_{1} and C_{2} are the binary extended [8,4,4] Q.R. codes which intersect in the all-one vector [Chapter 1, Section 9], then the extended [24,12,8] Golay code can be built from them via the (a+x|b+x|a+b+x) construction for a and b in C_{1} and x in C_{2}. If the C_{i}, i = 1, 2, have generator matrices G_{i}, i = 1, 2, then a generator matrix for the code C given by the (a + x|b + x|a + b + x) construction is as follows.

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

Clearly the length of C is 24. It is easy to show that C has dimension 12 from the form of G above. Note that C is doubly-even and self-dual so in order to show that C is equivalent to the Golay code, we need only show that C cannot contain any vectors of weight 4. As C_{1} and C_{2} consist solely of even weight vectors, all of the vectors a + x, b + x and a + b + x have even weight.

Hence the only way C could contain a vector of weight 4 is for one or two of these vectors to be the zero vector. If one, we can suppose that a + x = 0. As C_{1} ∩ C_{2} = ⟨1⟩, either a = x = 0 or a = x = 1. If a = x = 0, then b ≠ 0 and wt(0|b|b) =^{>} 8. If a = x = 1, then b ≠ 1 and wt(0, b + x, b) = 8. If two are zero, say a + x = b + x = 0, then a = b, so we have (0, 0, x). As x = a, x is in C_{1} ∩ C_{2} and so must be the all-one vector. Hence wt(0, 0, x) = 8. As C is a [24,12,8] code, it must be the extended Golay code [32],[Chapter 1].

This construction has been used to find codes with certain characteristics. A [48,15,16] code was found from an R[1, 4] and its reverse on the coordinates excluding the over-all parity check [47]. It is still an open problem whether this construction will yield further very good codes. If we build a [72,36] doubly-even code C from the two extended Golay codes (represented as extended Q.R. codes), then C has minimum weight 12 not 16 as one might have wanted.

We note that the representation above of the extended Golay code C determines a subgroup H of the group of C. The group of C is well-known to be the Mathieu group M_{24} of order 24.23.22.21.20.48. If we denote the three parts of the 24 coordinates as blocks I, II and III, then we can see S_{3} acting on these three blocks. Let Q and N denote the [7,4,3] Q.R. codes. Let G_{1} and G_{2} be the circulant generator matrices of Q̂ and N̂ whose first rows are the idempotent generators of these codes with a one in the extended position. Then the group of Q and N, of order 168, acts in the same fashion on G_{1} and G_{2} (leaving the extended position fixed). So the subgroup H has order 168.6 = 2^{4}.3^{2}.7. Clearly there are many permutations in M_{24} which do not preserve or permute these blocks.

There are five inequivalent [32,16,8] Type II codes [10]. Generator matrices of two of these have been given in [23] and [48] in terms of G_{1} and G_{2} above. These are different than the generators in [10]. One of these, 2g_{16} has the following generator matrix.

I II III IV
G_{1} 0 G_{1} 0
0 G_{1} G_{1} G_{1}
G_{2} G_{2} G_{2} 0
0 G_{2} 0 G_{2}

It is easy to see that this matrix generates a [32,16] doubly-even code.

Hence the minimum weight must be either 4 or 8. As the sum of a vector in Q̂ with one in N̂ has even weight, a vector of weight 4 must be zero on either 2 or 3 blocks. It is easy to rule out a vector of weight 4 by considering these possibilities. The group of 2g_{16} has order 2^{25}.3^{2}.5.7 [10]. Again the group, of order 168, of Q and N acting on Q̂ and N̂ sends this generator matrix onto itself. We also have a group of order 8 permuting the 4 blocks generated by the following two permutations σ and ρ.

σ : (I, II, III, IV)[G_{1}, G_{2}]

The above means that when we cycle the blocks we interchange (by μ_{−1})Q̂ and N̂. This permutation acts in the same fashion interchanging G_{1} and G_{2}.

ρ : (I, II)(III, IV)[G_{1}, G_{2}]

Again we interchange G_{1} and G_{2} when we interchange the two sets of blocks.

We have described a subgroup, of order 2^{6}.3.7, of the group of 2g_{16} preserving these four blocks. Again this construction with G_{1} and G_{2} being generator matrices of the two extended Q.R. [24,12,8] codes does not give a [96,48,20] code as vectors of weight 16 are evident.

Another construction of this nature in [23] and [48] is for 8f_{4} [10]. This has the following generator matrix with G_{1} and G_{2} as in the previous case. Let τG_{1} be obtained from G_{1} by cycling once on the last 7 coordinates and τ^{−1}G_{2} be obtained from G_{2} by cycling once in the reverse direction.

I  II III IV
G_{1} 0 G_{1} G_{1}
0  G_{1} G_{1} τG_{1}
G_{2} G_{2} G_{2} 0
G_{2} τ^{−1}G_{2} 0 G_{2}

Again it is not difficult to show that this matrix generates a [32,16,8] Type II code. The group of 8f_{4} has order 2^{12}.3.7 [10]. Noting that the permutation μ_{−1} which interchanges G_{1} and G_{2} also interchanges τG_{1} and τ^{−1}G_{2}, we obtain a subgroup of this group of order (2^{3}.3.7).2 = 2^{4}.3.7 preserving this partition. The new element of order 2 is as follows.

(I, III)(II, IV)[G_{1}, G_{2}]

There are three remaining inequivalent [32,16,8] Type II codes. One is an extended Q.R. code whose idempotent generator matrix is similar to G_{1} or G_{2} and which is described in Section 4. Another is R(2, 5). We give a generator matrix G of the last one, 16f_{2}. Let I_{16} denote the identity matrix of order 16, I_{4} the identity matrix of order 4 and J_{4} the all one matrix of order 4.

G = (I_{16} \begin{matrix}J_{4} & I_{4} & I_{4} & I_{4} \\ I_{4} & J_{4} & I_{4} & I_{4} \\ I_{4} & I_{4} & J_{4} & I_{4} \\ I_{4} & I_{4} & I_{4} & J_{4} \end{matrix} )

As 16f_{2} is self-dual, it also has G′ as a generator matrix.

G′ = ( \begin{matrix}J_{4} & I_{4} & I_{4} & I_{4} \\ I_{4} & J_{4} & I_{4} & I_{4} \\ I_{4} & I_{4} & J_{4} & I_{4} \\ I_{4} & I_{4} & I_{4} & J_{4} \end{matrix} I_{16})

It is easy to see that 16f_{2} is doubly-even, hence its minimum weight is either 4 or 8. If c is a vector in 16f_{2}, we let ℓwt(c) denote its weight on the first 16 coordinates and rwt(c) be its weight on the last 16 coordinates. Then, it can be seen that if ℓwt(c) = 1, rwt(c) = 7. If ℓwt(c) = 2, rwt(c) = 6 or 10 and by the form of G′, if ℓwt(c) = 3, rwt(c) ≠ 1. If ℓwt(c) = 4, rwt(c) ≠ 0, demonstrating that the minimum weight of 16f_{2} is 8. We will see more of this method in Section 5 on double circulants.

The group of 16f_{2} has order 2^{9}.3^{2}.5 [10]. From G and G′ we see that S_{4} acting on the blocks simultaneously on both sides is in the group of 16f_{2}. Also in this group is S_{4} acting simultaneously within the 8 blocks and the element of order 2 flipping the two sides. All told the subgroup described above has order 2(4!)^{2} = 2^{7}.3^{2}. We will see more about constructions involving self-dual codes in the next section.

3 Special relations for self-dual codes

A useful tool for analyzing self-dual codes is given by the following theorem called the balance principle by Koch [23], see also [36] Theorem 103.

Theorem 2. Let C be a self-dual [n, n/2] code and let C_{a} be the subcode of C consisting of all vectors in C with support in a fixed set of size a. Let C_{b} be the subcode of C whose support is in the complementary set of size b. Then

dim C_{a} − \frac{|a|}{2} = dim C_{b} − \frac{|b|}{2}.

Proof: We can suppose that the a positions are the first a positions. Then C has a generator matrix of the form

( \begin{matrix}A & 0 \\ 0 & B \\ D & E \end{matrix} )

where (A 0) is a generator matrix of C_{a} and (0 B) is a generator matrix of C_{b}. By the construction of C_{a} and C_{b}, the codes with generator matrices D and E have the same dimension, call it k. As C is self-dual, the dual code , C_{a}^{⊥}, has dimension equal to k + dim C_{a}. Hence 2 dim C_{a} + k = a. Similarly 2 dim C_{b} + k = b.

As many interesting codes such as the extended Golay codes can be represented as self-dual codes and since these codes satisfy the Varshamov-Gilbert bound [Chapter 1], this is a promising class of codes in which to search for new, good codes. One tool for such a search is the method of classification. Binary, ternary and quaternary self-dual codes have been classified for all lengths until a certain length n, where n is different for the different types of codes. The largest n is 32 for doubly-even codes. These classifications start with the shortest length where a self-dual code of the given type exists and then utilizes this information to classify the next length possible, and so on. The direct sum of self-dual codes is also self-dual so the real challenge is constructing codes which are not direct sums, the indecomposable ones. A key technique in building indecomposable self-dual codes is to start with the direct sum of self-orthogonal codes of smaller length, called components, and “glue” them together [see Chapter on self-dual codes]. The “glue” is found from stringing together appropriately chosen vectors in the duals to the component codes. In the binary case this technique is used to construct self- dual codes of minimum weight 4 so one has to be careful that the glue vectors, which must be of even weight and orthogonal to each other, do not generate further vectors of weight 4. In the ternary case similar methods produce self- dual codes of minimum weight 3. For example, we can “glue” the [7,3,4] binary self-orthogonal code C_{1} to itself to produce a self-dual [14,7,4] code C. If G_{1} is a generator matrix of C_{1}, then the following is a generator matrix of C.

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

Here a is an odd weight vector in the [7,4,3] Hamming code C^{⊥}. Usually a is taken to be of minimal weight in the dual of component code (modulo the component code). In this example a would be taken of weight 3.

The concept of a child of a self-dual code is only for binary codes. As the number of self-dual (Type I) codes is very large, it is easier to classify the less numerous doubly-even, self-dual (Type II) codes. Then a theorem [10] states that every self-dual code of length n ≢ 0(mod 8) is a child of some Type II code of the next larger length which is divisible by 8. We will demonstrate this theorem further in this section by showing how to construct the parent from the child, but first we define the children of a doubly-even, self-dual code which only exist at lengths n ≡ 0(mod 8). There are separate definitions of children of lengths n − 2, n − 4 and n − 6 (see [42]).

Any Type II code has children of length n − 2. Pick any two coordinate positions and let T be the set of these positions. As C = C^{⊥}, by Lemma 1, (C)_{T} has dimension n/2 − 2. Consider the subcode D of C consisting of all vectors in C which are either 11 or 00 on T. Then (D)^{T} is an [n − 2, n/2 − 1] self-dual code called the child of C. The minimum weight of (D)^{T} is at least d−2 where d is the minimum weight of C. The code C may have inequivalent children if its group is not doubly transitive. Any self-dual [6,3,2] code is a child of an extended Hamming [8,4,4] code. The unique self-dual [22,11,6] code is a child of an extended [24,12,8] Golay code.

Only Type II [n, n/2, 4] codes have self-dual children of length n − 4. Let T be the positions in a weight 4 vector t, called a tetrad, in C. Pick two positions out of these four, say the first two. Let D be the subcode of C consisting of all vectors in C which are zero on all positions in T or which are 1100 or 0011 on those positions. The linearity of D follows from the fact that t is in C. Then (D)^{T} is an [n − 4, n/2 − 2] self-dual child of C. This child can have minimum weight greater than 4. Inequivalent children arise from inequivalent pairs of positions chosen. The eight inequivalent [20,10,4] Type I codes are all children of [24,12,4] Type II codes. There are no length 20 Type I codes of minimum weight greater than 4.

A widely used component for Type II codes of minimum weight 4 is d_{2m}, of length 2m, which is constructed by dividing the 2m coordinate positions into pairs (called duads) and which has the following generator matrix.

G_{2m} = ( \begin{matrix}1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & ⋯ & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & ⋯ & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & ⋯ & 0 & 0 \\ & ⋮ & & & & & ⋮ & & & & ⋮ \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & ⋯ & 1 & 1 \end{matrix} )

We see that d_{2m} has dimension m − 1 [10]. If the pair of coordinates (as described above) is chosen in d_{4}, a tetrad, of a Type II code, then the resulting [n − 4, n/2 − 2] self-dual child has minimum weight 4 or more. One of the [20,10,4] codes, called 5d_{4}, is constructed in this fashion from a [24,12,4] code with 6 disjoint weight 4 vectors, called 6d_{4}. Some of the other [20,10,4] self-dual codes arise from choosing a pair in 6d_{4} which is not a duad.

If a duad in a d_{2m}, m > 2, is chosen as the distinguished pair of coordinates, then the resulting length n − 4 child has minimum weight 2. It is then possible to split off the weight 2 summand and obtain a self-dual code of length n − 2m. So from the [24,12,4] Type II code with description 4d_{6} (a direct sum of four d_{6}’s) we obtain an [18,9,4] code labelled 3d_{6} (a direct sum of three d_{6}’s), after deleting the weight 2 summand. This leads us to the next type of child.

Only Type II codes of length n which contain a d_{6} can have Type I children of length n − 6. For such a Type II code C consider its subcode D consisting of all vectors in C which are either zero or a duad on the 6 positions of d_{6}. Puncturing on D gives a Type I [n − 6, n/2 − 3] child. There are two [18,9,4] inequivalent Type I codes. Their weight 4 vectors reside in a 3d_{6} code and a d_{10} + e_{7} code where e_{7} refers to the [7,3,4] code. They are children of the length 24 Type II codes described by the labels 4d_{6} and d_{10} + 2e_{7} respectively.

Before locating the parents of self-dual codes, it is useful to introduce the concept of neighbors. Some good self-dual codes have been found as neighbors of known self-dual codes and this concept has been used to show that self-dual codes with certain parameters cannot exist. Two self-dual codes C and D of length n are called neighbors if C ∩ D has dimension (n/2 − 1). Note that this intersection must contain the all-one vector. The neighbors of a self-dual code C are closely associated to even-weight cosets of C and this relation is worth investigating. Let C_{0} be a subcode of C of codimension 1 which contains the all-one vector. Then C_{0}^{⊥} contains only even weight vectors, has dimension (n/2 + 1), and contains C. Hence we write C_{0}^{⊥} as a union of four cosets of C_{0} one of which, say C_{2}, is such that C = C_{0} ∪ C_{2}.

Theorem 3. If C is a binary self-dual code and C_{0} is a subcode of codimension 1 which contains the all-one vector, then

C_{0}^{⊥} = C_{0} ∪ C_{2} ∪ C_{1} ∪ C_{3}

where C_{0} ∪ C_{2} = C and C_{1} ∪ C_{3} is an even weight coset of C.

Further there exist c_{i} in C_{i}, i = 1, 2, 3, such that c_{i} + c_{j} = c_{k} for i, j, k = 1, 2, 3 in any order.

Also, C, C_{0} ∪ C_{1} and C_{0} ∪ C_{3} are all self-dual neighbors of each other. If C and C′ are self-dual neighbors, let C_{0} = C ∩ C′. If C_{0}^{⊥} is expressed

as above, then C′ is either C_{0} ∪ C_{1} or C_{0} ∪ C_{3}.

We express the orthogonality relations between C_{0} and these cosets in the next table.

Table 1

Orthogonality relations for an even coset C_{1} ∪ C_{3} of a self-dual binary code C = C_{0} ∪ C_{2}, where C_{0}^{⊥} = C_{0} ∪ C_{2} ∪ C_{1} ∪ C_{3}. (Note that every even coset can be expressed in this fashion where the C_{i} are cosets of C_{0} in C_{0}^{⊥}.)

( \begin{matrix}& C_{0} & C_{2} & C_{1} & C_{3} \\ C_{0} & ⊥ & ⊥ & ⊥ & ⊥ \\ C_{2} & ⊥ & ⊥ & / & / \\ C_{1} & ⊥ & / & ⊥ & / \\ C_{3} & ⊥ & / & / & ⊥ \end{matrix} )

The ⊥ sign in row 2, column 1 means that every element in C_{2} is orthogonal to every element in C_{0}. Similarly with every other ⊥ sign. The / sign indicates no pair of vectors are orthogonal. The ⊥ signs in row 1 or column 1 follow from the fact that all C_{i} are in C_{0}^{⊥}. The signs in either row 2 or column 2 are equally easy to show as C^{⊥} = C. As C_{3} = c_{3} + C_{0} with wt(c_{3}) even, C_{3}⊥C_{3}. Similarly C_{1}⊥C_{1}. As C_{0} ∪ C_{1} is self-dual, C_{1}/C_{3}. We can say more.

If C is doubly-even, C_{1} and C_{3} can be chosen so that all weights in C_{1} are ≡ 0(mod 4), and in C_{3} they are ≡ 2(mod 4).

If C and C_{0} are singly-even, then half of the vectors in C_{i}, i = 1, 3 are singly-even and half are doubly-even.

If C is singly-even and C_{0} is doubly-even, then all weights in C_{1} are equivalent to all weights in C_{3}(mod 4). Further, these weights are equivalent to n/2(mod 4) where n is the length of C.

All of these statements, except the last, follow easily from the orthogonality relations. Consider the first statement, for example. If c_{1} is in C_{1} and c_{3} is in C_{3}, then c_{1} +c_{3} is in C_{2}. Hence wt(c_{1} +c_{3}) ≡ wt(c_{1})+wt(c_{3})−2(c_{1} ∩c_{3}) ≡ 0(mod 4) as C is Type II. As C_{1}/C_{3}, wt(c_{1}) ≢ wt(c_{3})(mod 4).

For the last statement, note that the assumption that the all one vector is in C_{0} implies that either n ≡ 0(mod 8) or n ≡ 4(mod 8). If n ≡ 4(mod 8), the weights in C_{1} (or C_{3}) must be ≡ 2(mod 4) or else C_{0} ∪C_{1} would be a Type II code. But such codes only exist of length n ≡ 0(mod 8). If n ≡ 0(mod 8), by the formulas in [45], a doubly-even code of length n, and dimension (n/2−1) is contained in two Type II codes (which must be C_{0} ∪ C_{1} and C_{0} ∪ C_{3}) and one singly-even, self-dual code (C_{0} ∪ C_{2}). For more on this see [42].

In [13], Conway and Sloane computed the weight enumerators of all selfdual binary codes of highest possible minimum weight and of length =^{<} 64 in an attempt to determine whether or not codes with those enumerators exist. When the code C is singly-even and C_{0} is its unique doubly-even subcode of codimension 1, then the weight distribution of C_{0} is obvious from the weight distribution of C. Hence so is the weight distribution of C_{0}^{⊥} = C_{0}∪C_{2}∪C_{1}∪C_{3} with C_{0} ∪C_{2} = C. So the weight distribution of C_{1} ∪C_{3}, called the shadow, is also obvious. Sometimes it is possible to determine the weight distributions of C_{1} and C_{3} separately. This information may lead to the discovery of self-dual codes whose existence was not previously known. We illustrate this with the weights =^{<} 12 in a putative singly-even, self-dual [32,16,8] code C below. As noted above, the weight distribution of C’s shadow can be computed from the weight distribution of C. Note that all the vectors of weight 4 in the shadow must be in either C_{1} or C_{3} as the sum of a vector in C_{1} with one in C_{3} is in C_{2}. As C_{1}/C_{3} (see Table 1), such a sum would have weight less than 8. This information is enough to determine the weight distribution of C_{1} and C_{3}.

weights  4  8  10  12
C_{0}  364  6,720
C_{2}  2,048
C_{1}  8  336  6,776
C_{3}  256  7,168

The weight distribution of a Type II [32,16,8] is uniquely determined and can be seen to be that of C’s neighbor C_{0} ∪ C_{3}. From the five inequivalent Type II [32,16,8] codes, three inequivalent C’s were found by computer [13] from three of the Type II codes which have a diagram that can be obtained from the diagram above by interchanging rows C_{2} and C_{3} (see also [9]).

Also in [13] the weight distribution of a putative [48,24,10] self-dual code C was given as well as the weight distribution of its shadow. The weight distributions of C_{1} and C_{3} were not determined. The shadow had 1 vector of weight 4 and 44 vectors of weight 8. If all of these vectors were in C_{1}, say, then C would have to be a neighbor of a Type II [48,24,12] code. Looking at the complete coset weight distribution of the extended Q.R. [48,24,12] code [15] revealed that it indeed had a coset containing 1 vector of weight 4, 44 vectors of weight 8 and no vectors of weight 6. Hence C was constructed (with the help of a computer) from its extended Q.R. neighbor [6].

We can use the information in Table 1 to locate the Type II parent of a Type I code C of length n where n ≡ 4(mod 8). The parent is obtained by adding four new coordinate positions to the codewords of C_{0}, C_{2}, C_{1}, C_{3}, where C_{0} is d.e. as follows. To words in C_{0} add (0,0,0,0), to C_{2} add (1,1,0,0), to C_{1} add (1,0,1,0) and to C_{3} add (1,0,0,1). Then the parent consists of the [n + 4, n/2 + 1] self-orthogonal code generated by all these vectors plus the vector (0, …, 0,1,1,1,1). By Table 1 this parent is doubly-even.

We demonstrate this for the unique [12,6,4] Type I code. The diagram below gives the weight distributions of C_{0}, C_{2}, C_{1} and C_{3} and indicates the 4 new coordinates to be adjoined to these vectors.

Weight  0 2 4 6 8 10 12 The 4 New Positions
C_{0}  1  15  15  1  0 0 0 0
C_{2}  32  1 1 0 0
C_{1}  6  20  6  1 0 1 0
C_{3}  32  1 0 0 1
Additional Vector 0 · · · · · · · · · · · · 0  1 1 1 1

From this diagram it is easy to see that the weight distribution of the Type II [16,8,4] parent is

A_{0} = A_{16} = 1, A_{4} = A_{12} = 28, A_{8} = 198.

This is the unique weight distribution of a Type II [16,8,4] code. There are two inequivalent codes with this weight distribution [34].

Fact 1. If C is a Type I code of length n ≡ 4(mod 8) and the C_{i} are as above where each C_{i} has weight enumerator W_{i}(x, y), then the weight distribution of the length n + 4 parent of C is

(x^{4} + y^{4})W_{0}(x, y) + 2x^{2}y^{2}(W_{1}(x, y) + W_{2}(x, y) + W_{3}(x, y)).

To find the Type II parent of a Type I code of length n ≡ 2(mod 4) requires a table for odd weight cosets similar to Table 1.

Table 2

Orthogonality relations for an odd-weight coset C_{1} ∪ C_{3} of a self-dual code C = C_{0} ∪ C_{2} where C_{0}^{⊥} = C_{0} ∪ C_{2} ∪ C_{1} ∪ C_{3}.

( \begin{matrix}& C_{0} & C_{2} & C_{1} & C_{3} \\ C_{0} & ⊥ & ⊥ & ⊥ & ⊥ \\ C_{2} & ⊥ & ⊥ & / & / \\ C_{1} & ⊥ & / & / & ⊥ \\ C_{3} & ⊥ & / & ⊥ & / \end{matrix} )

The ⊥ and / signs have the same meaning as in Table 1. The only fact that might need some explanation is that C_{1}⊥C_{3}. Let c_{i} ∈ C_{i}, i = 1, 3. As c_{1} + c_{3} is in C_{2}, c_{1} + c_{3} is not orthogonal to c_{1}. As c_{1} is not orthogonal to itself, c_{1}⊥c_{3}.

The following statements (except the last) follow from these orthogonality relations.

If C is of Type II, C_{1} and C_{3} can be chosen so that all weights in C_{1} are ≡ 1(mod 4), and in C_{3} they are ≡ 3(mod 4).

If C_{0} is singly-even, half the weights in C_{1}(C_{3}) are ≡ 1(mod 4), half are ≡ 3(mod 4).

If C is singly-even and C_{0} is doubly-even, all weights in C_{1} are equivalent (mod 4) to all weights in C_{3}.

In the last case these weights are ≡ n/2(mod 4) where n is the length of C.

If C is a Type I code of length n ≡ 2(mod 8), and C_{0} is d.e., then the weights in C_{1}(C_{3}) are equivalent (mod 4) and odd. If they were ≡ 3(mod 4), we could construct a Type II [n + 2, n/2 + 1] parent consisting of the vectors (C_{0}, 0, 0), (C_{2}, 1, 1), (C_{1}, 1, 0) and (C_{3}, 0, 1). As Type II codes of this length cannot exist, the weights in C_{1}(C_{3}) must be ≡ 1(mod 4).

Fact 2 . If C is a Type I code of length n ≡ 2(mod 8) and the C_{i} are as above where each C_{i} has weight enumerator W_{i}(x, y), then the weight distribution of the length n + 2 parent of C is

x^{2}W_{0}(x, y) + y^{2}W_{2}(x, y) + xy(W_{1}(x, y) + W_{3}(x, y)).

If C is a Type 1 code of length n ≡ 6(mod 8) and C_{0} is d.e., we again know that the weights in C_{1}(C_{3}) are odd and equivalent (mod 4). Assume the weights are ≡ 1 (mod 4). Let D be the d.e. [n + 2, n/2] code consisting of the vectors (C_{0}, 0, 0) and (C_{2}, 1, 1). Then D is contained in the two Type I codes, D ∪(C_{1}, 1, 0)∪(C_{3}, 0, 1) and the code generated by D and the vector (0, …, 0,1,1). This contradicts the fact that D is contained in two Type II codes and one Type I code by the counting formulas in [45]. Hence the weights in C_{1}(C_{3}) must be ≡ 3(mod 4).

For example, if n = 6, the Type I (6,3,2) code is a child of the extended Hamming (8,4,4) code as can be seen from the following diagram.

Weight 0 1 2 3 4 5 6 Added Coordinate
C_{0}  1  3  0 0
C_{2}  3  1  1 1
C_{1}  4  1 0
C_{3}  4  0 1

It is easy to see from this diagram that the parent has the weight distribution A_{0} = A_{8} = 1 and A_{4} = 14.

If n ≡ 2(mod 8), we must adjoin 6 coodinates to obtain an [n+6, n/2+3] Type II parent code C. Two dimensions of C are provided by adjoining d_{6} preceded by zeros. Then C is generated by this two dimensional code and the following vectors: (C_{0}, 0, 0, 0, 0, 0, 0), (C_{2}, 1, 1, 0, 0, 0, 0), (C_{1}, 1, 0, 1, 0, 1, 0) and (C_{3}, 0, 1, 1, 0, 1, 0). Again the weight distribution of the parent can be computed from the weight distributions of the child and its shadow.

Fact 3 If C is a Type I code of length n ≡ 6(mod 8) and the C_{i} are as above where each C_{i} has weight enumerator W_{i}(x, y), then the weight distribution of the length n + 6 parent of C is

(x^{6} + 3x^{2}y^{4})W_{0}(x, y) + (3x^{4}y^{2} + y^{6})W_{2}(x, y) + 4x^{3}y^{3}(W_{1}(x, y) + W_{3}(x, y)).

There are still several weight enumerators in [13] where the existence of a self -dual code with that enumerator is unknown. Two long-standing extremal weight enumerators are those of Type II [72,36,16] and [96,48,20] codes. These enumerators have been computed and from the numbers, so far, no one has shown that these codes cannot exist. Nor has anyone constructed either of these codes.

There are other constructions for certain self-dual codes which can be represented as extended cyclic codes both in the binary and non-binary cases as we will see in the next section.

4 Circulant Constructions

Many explicit circulant constructions can be given for good or at least interesting codes. Such a construction gives a generator matrix M for the code where every row of M (after the first) is a shift of the preceding row. The generator polynomial of a cyclic code provides such a generator matrix ([36], Chapter 1). So does the idempotent generator of a cyclic code ([36], Chapter 1). This type of circulant construction can be determined for many cyclic codes without factoring x^{n} − 1. One of our objectives is to provide these constructions. A generator matrix for many extended cyclic codes has the form

( \begin{matrix}1 \\ ⋮ & M \\ 1 \end{matrix} )

where M is a circulant matrix. Such a matrix is also called circulant as is a matrix with the first column replaced by some other non-zero vector.

Another type of circulant is

( \begin{matrix}1 & ⋯ & 1 \\ ⋮ & M \\ 1 \end{matrix} )

where M is a circulant matrix. Again either the first column or first row can be replaced by some other vector.

We show how to easily construct circulant generator matrices for quadratic residue (Q.R.) codes over various finite fields. It is interesting that we can do this without recourse to Perron’s Theorem, a tool which has been used in prior constructions ([26]). We first recall some facts about these cyclic codes. They exist of prime length p over fields GF (q) where g.c.d. (p, q) = 1 and q is a square mod p. When they exist of length p there are two equivalent codes Q_{1} and N_{1} of dimension \frac{p+1}{2} and two equivalent codes Q_{2} and N_{2} of dimension \frac{p−1}{2}. We can say more about their idempotent generators. The idempotent generator of the whole space is 1 and the idempotent generator of the one-dimensional cyclic code consisting of the all-one vector and its multiples is the vector \frac{1}{p}(1, …, 1) which we call h. Then 1 − h is the idempotent generator of the cyclic code consisting of all even-like vectors. Recall [Chapter 1] that a vector is called even-like if the sum of its components is zero, and is called odd-like otherwise. We say that Q_{1} = ⟨e_{1}⟩ and N_{1} = ⟨e′_{1}⟩ meaning that e_{1} is the idempotent generator of Q_{1} and similarly for e′_{1} and N_{1}. We know that e_{1} and e′_{1} must be odd-like vectors. As shown in Chapter 1, Q_{1} + N_{1} is the whole space and Q_{1} ∩ N_{1} = ⟨h⟩, hence we have

e_{1} + e′_{1} − h = 1.  (1)

It is known that the other two Q.R. codes, Q_{2} = ⟨e_{2}⟩ and N_{2} = ⟨e′_{2}⟩ have even-like idempotents and as Q_{2} + N_{2} = ⟨1 − h⟩ and Q_{2} ∩ N_{2} = {0},

e_{2} + e′_{2} = 1 − h.  (2)

Further Q_{2} ⊂ Q_{1}, N_{2} ⊂ N_{1} so that Q_{1} must equal Q_{2}⊥⟨h⟩ and N_{1} must equal N_{2}⊥⟨h⟩. Hence

e_{1} = e_{2} + h and e′_{1} = e′_{2} + h.  (3)

Because e_{1} and e′_{1} are odd-like, e_{1}h = e′_{1}h = h. Because e_{2} and e′_{2} are even-like, e_{2}h = e′_{2}h = 0.

The multiplier μ_{a}, for a any non-residue, interchanges Q_{i} and N_{i} for i = 1, 2. If a is a residue, it leaves the code invariant.

As the extended (odd-like) Q.R. codes have a transitive automorphism group, the odd-like Q.R. codes have odd-like vectors of minimum weight. In the binary case this means that the minimum weight of the odd-like codes is odd. If d is the minimum weight of the odd-like Q.R. codes of length p then it is known [Chapter 1] that

d^{2} =^{>} p  (4)

and under certain conditions we have the stronger bound

d^{2} − d + 1 =^{>} p.  (5)

If equality holds in (5) the vectors of minimum weight d in the odd-like code hold a projective plane of order d − 1.

We let Q = Σx^{i} where i ranges over the quadratic residues (mod p) and N = Σx^{i} where i ranges over the non-residues (mod p). As μ_{a} ,for a a residue leaves any Q.R. code invariant, the idempotent of any Q.R. code (either oddlike or even-like) must have the form a_{0} + a_{1}Q + a_{2}N where the a_{i} are in GF (q). In addition, this polynomial being an idempotent implies that a_{0} is either 0 or 1. As any non-residue interchanges a pair of Q.R. codes these idempotents have the form (Corollary 5.20, Chapter 1)

a_{0} + a_{1}Q + a_{2}N and a_{0} + a_{2}Q + a_{1}N.  (6)

We will show how to find a_{0}, a_{1} and a_{2}. This is simplest to do in the binary case.

We denote the vector space direct sum of two codes C_{1} and C_{2} which are orthogonal to each other by C_{1}⊥C_{2}.

4.1 The Binary Case.

As 2 is a quadratic residue for primes p ≡ ±1(mod 8), these are the lengths at which binary Q.R. codes exist. The situation is different for lengths p ≡ −1(mod 8) and for lengths p ≡ 1(mod 8).

Suppose p ≡ −1(mod 8). Then Q_{1} = ⟨Q⟩, N_{1} = ⟨N⟩. Q_{2} = ⟨1 + N⟩, and N_{2} = ⟨1 + Q⟩. As Q_{1} = Q_{2}⊥⟨h⟩, we have two generator matrices for Q_{1}. Similarly for N_{1}.

Thus one of the [7,4,3] Q.R. codes has the following two circulant generator matrices.

( \begin{matrix}0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 0 \end{matrix} ) and ( \begin{matrix}0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \end{matrix} )

The first matrix is the idempotent generator matrix for Q_{1}. The second is the all-one vector and the idempotent generator matrix for Q_{2}.

In this case both Q_{2} and N_{2} are doubly-even codes. Hence the [p+1, \frac{p+1}{2}] extended Q.R. codes are Type II codes, i.e. doubly-even and self-dual.

Continuing with our example, the extended [8,4,4] code has the following two generator matrices.

( \begin{matrix}∞ & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 \end{matrix} ) and ( \begin{matrix}∞ & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 \end{matrix} )

So the extended odd-like [p + 1, \frac{p+1}{2}] Type II codes each have the following two generator matrices. For one code these matrices are

( \begin{matrix}1 \\ ⋮ & Q \\ 1 \end{matrix} ) and ( \begin{matrix}1 & ⋯ & 1 \\ 0 \\ ⋮ & 1 + N \\ 0 \end{matrix} )

where Q denotes the (\frac{p+1}{2}) × p circulant whose first row is Q. Similarly for 1 + N.

For the other code, the matrices are

( \begin{matrix}1 \\ ⋮ & N \\ 1 \end{matrix} ) and ( \begin{matrix}1 & ⋯ & 1 \\ 0 \\ ⋮ & 1 + Q \\ 0 \end{matrix} )

The minimum weight of the odd-like codes satisfy the stronger bound (5). We note that Q^{2} = Q, N^{2} = N and NQ = h. When p = 23, we get the binary Golay codes.

When p ≡ 1 (mod 8), Q_{1} = ⟨1 + Q⟩, N_{1} = ⟨1 + N⟩, Q_{2} = ⟨N⟩ and N_{2} = ⟨Q⟩. As above, Q_{1} has two generator matrices as follows

(1 + Q) and \binom{1 ⋯ 1}{N}.

In this situation Q_{1}^{⊥} = N_{2} and N_{1}^{⊥} = Q_{2}. The extended codes are duals of each other. Q̂_{1} has the following generator matrices

( \begin{matrix}1 \\ ⋮ & 1 + Q \\ 1 \end{matrix} ) and ( \begin{matrix}1 & ⋯ & 1 \\ 0 \\ ⋮ & N \\ 0 \end{matrix} ) .

Its dual code N̂_{1} has the following generator matrices.

( \begin{matrix}1 \\ ⋮ & 1 + N \\ 1 \end{matrix} ) and ( \begin{matrix}1 & ⋯ & 1 \\ 0 \\ ⋮ & Q \\ 0 \end{matrix} ) .

We note that Q^{2} = Q, N^{2} = N and NQ = 0.

4.2 The Ternary Case

We can also specify the idempotents for ternary Q.R. codes. These codes exist at prime lengths p ≡ ±1 (mod 12) as this is the condition that 3 is a quadratic residue (mod p). As before the notation Q^{2}, QN, etc. will mean the products of these polynomials reduced (mod x^{p} − 1), i.e. the product of vectors in their cyclic codes.

We first let p ≡ −1 (mod 12). Then h = −(1, …, 1). We can represent schematically the conditions for even-like idempotents of the even- like Q.R. codes as follows .

Even-like Q.R. idempotents

0 Q  N
a_{0} a_{1}  a_{2}
a_{0} a_{2}  a_{1}
−1 1  1

This scheme gives the information that if one even-like idempotent is a_{0} + a_{1}Q + a_{2}N, then the other is a_{0} + a_{2}Q + a_{1}N by (6) and their sum is 1 − h by (2). By the scheme 2a_{0} ≡ 2 (mod 3) so that a_{0} = 1 and our equation becomes

1 = a_{1} + a_{2} (mod 3).  (7)

Since the two idempotents are distinct, a_{1} ≠ a_{2} so that the two solutions are a_{1} = 1, a_{2} = 0 or a_{1} = 0, a_{2} = 1. Hence the scheme for the even-like Q.R. idempotents is as follows.

\begin{matrix}0 & Q & N \\ 1 & 1 & 0 \\ 1 & 0 & 1 \\ −1 & 1 & 1 \end{matrix}

Once we have determined the even-like idempotents, the odd-like idempotents can be computed as e_{1} = e′_{1} + h and e_{2} = e′_{2} + h by (3). Hence we have the following scheme.

Odd-like Q.R. idempotents

0 Q  N
0 0  −1
0 −1  0
0 −1  −1

Note that this implies that Q^{2} = −Q, N^{2} = −N and NQ = −1−N −Q = h.

For example when p = 11, there are two equivalent [11,6,5] Q.R. codes, the ternary Golay codes. The following are two generator matrices for one of these (the other is obtained by interchanging the roles of Q and N).

( \begin{matrix}& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & & 2 & & 2 & 2 & 2 & & & & 2 \\ 2 & & & 2 & & 2 & 2 & 2 & & & & 2 \\ 3 & 2 & & & 2 & & 2 & 2 & 2 \\ 4 & & 2 & & & 2 & & 2 & 2 & 2 \\ 5 & & & 2 & & & 2 & & 2 & 2 & 2 \\ 6 & & & & 2 & & & 2 & & 2 & 2 & 2 \end{matrix} )  ( \begin{matrix}& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 2 & 1 & & 1 & & & & 1 & 1 & 1 & & 1 \\ 3 & 1 & 1 & & 1 & & & & 1 & 1 & 1 \\ 4 & & 1 & 1 & & 1 & & & & 1 & 1 & 1 \\ 5 & 1 & & 1 & 1 & & 1 & & & & 1 & 1 \\ 6 & 1 & 1 & & 1 & 1 & & 1 & & & & 1 \end{matrix} )

In general, the two odd-like (p, \frac{p+1}{2}) Q.R. codes have two generator matrices each of which are as follows.

(−Q) and \binom{−1 ⋯ −1}{1 + N}

or

(−N) and \binom{−1 ⋯ −1}{1 + Q} .

It is known that the even-like codes Q_{2} and N_{2} are self-orthogonal. Hence Q_{2}^{⊥} = Q_{1} and N_{2}^{⊥} = N_{1}. This implies that the extended odd-like codes are self-dual. So all the weights in the even-like and extended odd-like Q.R. codes are divisible by three. Hence all weights in the odd-like code are ≡ 0, 2 (mod 3). The minimum weight of the odd-like codes satisfy the stronger bound (5) and are ≡ 2 (mod 3).

The extended odd-like Q.R. codes have the following generator matrices.

( \begin{matrix}−1 \\ ⋮ & −Q \\ −1 \end{matrix} ) and ( \begin{matrix}−1 & ⋯ & −1 \\ 0 \\ ⋮ & 1 + N \\ 0 \end{matrix} )

or

( \begin{matrix}−1 \\ ⋮ & −N \\ −1 \end{matrix} ) and ( \begin{matrix}−1 & ⋯ & −1 \\ 0 \\ ⋮ & 1 + Q \\ 0 \end{matrix} )

From the two generating matrices for the first code we see that it contains the following p + 1 maximal weight (p + 1) vectors and their negatives

( \begin{matrix}1 & ⋯ & 1 \\ ⋮ & −1 + Q − N \\ 1 \end{matrix} ) .

Here this matrix represents p+1 vectors as we take all p shifts of −1+Q−N. As p ≡ 3 (mod 4) this matrix is known to be a Hadamard matrix [1], indeed (−1 + Q − N) is a Jacobsthal matrix. The 2(p + 1) vectors of weight p + 1 in the other code are the rows of the following matrix and its negatives.

( \begin{matrix}1 & ⋯ & 1 \\ ⋮ & −1 + N − Q \\ 1 \end{matrix} ) .

The weight distributions of the extended odd-like Q.R. codes are known for p = 11,23,47 and 59 [28]. From this it can be seen that for p = 11,23,47 these vectors are all the maximal weight vectors (A_{p+1} = 2(p + 1)). When p = 59, there are more.

When p ≡ 1 (mod 12), we begin again with the even-like idempotents which can be represented ( (2) and (6)) by the following scheme after noting that h is the all-one vector.

Even-like Q.R. idempotents

0 Q  N
a_{0} a_{1}  a_{2}
a_{0} a_{2}  a_{1}
0 −1  −1

The solutions are easily seen to be a_{0} = 0, a_{1} = −1 and a_{2} = 0 or a_{1} = 0 and a_{2} = −1. This gives the following representations of the idempotents for the Q.R. codes.

Even-like Q.R. idempotents

0 Q  N
0 0  −1
0 −1  0
0 −1  −1

Odd-like Q.R. idempotents

0 Q  N
1 1  0
1 0  1
−1 1  1

We see in these situations also that Q^{2} = −Q and N^{2} = −N. However QN = 0.

Hence the [p, \frac{p+1}{2}] odd-like Q.R. codes have the following generator matrices

(1 + Q) or \binom{1 ⋯ 1}{−N} for one code,
(1 + N) or \binom{1 ⋯ 1}{−Q} for the other.

We know that Q_{2}^{⊥} = N_{1} and N_{2}^{⊥} = Q_{1}. The minimum weight of these codes satisfies the bound (4). The extended odd-like Q.R. codes are not duals of each other. However, if we extend one with a one instead of a −1 as we should to get an even-like code, we can get dual codes. The following [p + 1, \frac{p+1}{2}] codes are duals of each other.

( \begin{matrix}1 & 1 & ⋯ & 1 \\ 0 \\ ⋮ & & −N \\ 0 \end{matrix} ) and ( \begin{matrix}−1 & 1 & ⋯ & 1 \\ 0 \\ ⋮ & & −Q \\ 0 \end{matrix} ) .

4.3 Q.R. Codes of Prime lengths over Fields of Odd Order.

It is tempting to try to apply these techniques to Q.R. codes of prime length p over GF (q), q odd, g.c.d.(p, q) = 1 and q a square (mod p). However, there are many more choices for a_{1} and a_{2} and they cannot be solved in general. We can say something if we add further assumptions. So suppose also that

1) p ≡ 3 (mod 4) and

2) q|(p + 1).

Assumption 1) says that −1 is not a quadratic residue (mod p), which in turn implies that the two even-like Q.R. codes are self-orthogonal. By assumption 2), the two odd-like Q.R. codes can be extended to self-dual codes.

By 1) the following (p+1)×(p+1) matrices are Paley-Hadamard matrices [1].

H_{1} = ( \begin{matrix}1 & ⋯ & 1 \\ ⋮ & −1 + Q − N \\ 1 \end{matrix} ) and H_{2} = ( \begin{matrix}1 & ⋯ & 1 \\ ⋮ & −1 + N − Q \\ 1 \end{matrix} ) .

By the definition of a Hadamard matrix, H_{i}H_{i}^{T} = (p + 1)I, i = 1, 2 so that the rows of these matrices are orthogonal to each other over any field, hence over GF (q). By 2) they are orthogonal to themselves over GF (q). Hence H_{1} and H_{2} generate self-orthogonal codes Ĉ_{1} and Ĉ_{2} over GF (q). All the vectors in these codes are even-like as H_{1} and H_{2} contain the all-one vector. As q is a square (mod p) by assumption, Q.R. codes of length p over GF (q) exist. Puncturing Ĉ_{1} and Ĉ_{2} on their first positions, we obtain cyclic codes C_{1} and C_{2} generated by the odd-like vectors −1 + Q − N (and its shifts) and −1 + N − Q (and its shifts) respectively. As the only odd-like codes left invariant by all multipliers μ_{q}, for q a quadratic residue, are the whole space, the all one vector, and the odd-like Q.R. codes, these codes are equal to the distinct odd-like Q.R. codes. As 1 + N is an even-like vector in C_{1} and 1 + Q is an even-like vector in C_{2}, (1 + N)(1 + Q) = 1 + N + Q + NQ = 0. Hence NQ = −1 − N − Q. By 2), h = −(1, …, 1) so that the following scheme holds for the odd-like Q.R. codes.

\begin{matrix}0 & Q & N \\ 0 & a & b \\ 0 & b & a \\ 0 & −1 & −1 \end{matrix}

By the idempotent property (aQ + bN)^{2} = a^{2}Q^{2} + 2abQN + b^{2}N^{2} = a^{2}Q^{2} − 2ab−2abQ−2abN+b^{2}N^{2} = aQ+bN. As −1 is not a quadratic residue, neither Q^{2} nor N^{2} can contain any constant terms so that ab must be 0. Hence either a or b is 0 giving the following scheme for the odd-like idempotents.

\begin{matrix}0 & Q & N \\ 0 & 0 & −1 \\ 0 & −1 & 0 \\ 0 & −1 & −1 \end{matrix}

We sum this up in the following theorem.

Theorem 4. Let p be an odd prime and q an odd prime power. Assume q is a square (mod p), p ≡ 3 (mod 4) and q divides (p + 1).

Then the odd-like Q.R. [p, \frac{p+1}{2}] over GF (q) codes have −Q and −N as idempotent generators. Say Q_{1} = ⟨−Q⟩ and N_{1} = ⟨−N⟩.

The even-like Q.R. [p, \frac{p−1}{2}] codes are Q_{2} = ⟨1 + N⟩ and N_{2} = ⟨1 + Q⟩.

The minimum weight d of the odd-like codes satisfies d^{2} − d + 1 =^{>} p. The even-like codes are self-orthogonal and the extended odd-like codes

are self-dual.

The extended odd-like code Q̂_{1} contains 2(p + 1) vectors of weight p + 1 which are the rows of the Paley-Hadamard matrix

( \begin{matrix}1 & ⋯ & 1 \\ ⋮ & −1 + Q − N \\ 1 \end{matrix} )

and its negative.

The same statement holds for Q̂_{2} and the Paley-Hadamard matrix

( \begin{matrix}1 & ⋯ & 1 \\ ⋮ & −1 + N − Q \\ 1 \end{matrix} ) .□

This theorem includes the ternary case when p ≡ −1 (mod 12). In this fashion it is possible to write down generator matrices for all length 19 Q.R. codes over GF (5) and also to find maximal weight vectors in the odd- like codes.

If q is a square (mod p) and p ≡ 3 (mod 4), then there are Q.R. codes of length p, the even-like codes are self-orthogonal and there exist Paley-Hadamard (p + 1) × (p + 1) matrices of the form given above. However, without the assumption that q divides (p + 1), it is not necessarily the case that the code generated by such a matrix, punctured on its first position, is a Q.R. code. An example of this occurs for p = 11, q = 5. Here h is the all one vector. It is possible to determine that Q_{1} = ⟨1 + 2Q − N⟩, N_{1} = ⟨1−Q+2N⟩, Q_{2} = ⟨Q+3N⟩, N_{2} = ⟨3Q+N⟩. Further Q^{2} = 2Q+3N, N^{2} = 3Q + 2N and QN = 2(Q + N). Since Q is not in either even-like Q.R. code and it is invariant under all μ_{q}, for q a quadratic residue, Q (and its shifts) generate the (p − 1) dimensional space of even- like vectors as does N (and its shifts). Hence the punctured Hadamard matrices each generate the entire p-dimensional space.

4.4 Q.R. Codes over Fields of Characteristic 2.

As for the binary case it is possible to describe the generating idempotents for all Q.R. codes over fields of characteristic 2, although it is more complicated. As we will see it is necessary to construct these idempotents only for GF (2) (which is already done) and GF (4), so we start with GF (4).

Over GF (4) Q.R. codes exist for all prime lengths p as 4 is a square. Much about this case is in [40]. When p is a prime ≡ ±1 (mod 8), there are binary Q.R. codes and so their idempotents must be the idempotents of the Q.R. codes over any GF (2^{r}). Further the minimum weight of the binary Q.R. codes is the minimum weight of the Q.R. codes over any GF (2^{r}) [Chapter 1, Handbook].

Hence the interesting cases of quaternary Q.R. codes are of length p for p ≡ ±3 (mod 8). We again consider schemes for the even-like and odd-like idempotents using (2) and (6).

Even-like idempotents

0 Q N
a_{0} a_{1} a_{2}
a_{0} a_{2} a_{1}
0 1  1

Odd-like idempotents

0 Q N
1 + a_{0} 1 + a_{1} 1 + a_{2}
1 + a_{0} 1 + a_{2} 1 + a_{1}
0  1  1

As before a_{0} is either 0 or 1. We regard GF (4) as consisting of 0, 1, w, and \overline{w} = w^{2} where \overline{w} + w = 1, w^{3} = 1. Since there are no binary Q.R. codes of these lengths, neither a_{1} nor a_{2} can be binary so we can let a_{1} = w and a_{2} = \overline{w}. The schemes above look the same for the even-like and the odd-like idempotents. The difference between them is the property of being even-like or odd-like. This determines a_{0} depending on whether p ≡ 3 (mod 8) or p ≡ 5 (mod 8).

Let p ≡ 3 (mod 8). Then we have the following scheme.

Even-like Q.R. idempotents

0 Q  N
1 w \overline{w}
1 \overline{w}  w
0 1  1

Odd-like Q.R. idempotents

0 Q  N
0 \overline{w}  w
0 w \overline{w}
0 1  1

Hence the two [p, \frac{p+1}{2}] Q.R. codes have the following circulant generator matrices.

(\overline{w}Q + wN) and (wQ + \overline{w}N).

The two extended [p + 1, \frac{p+1}{2}] codes are self-dual with respect to the usual inner product and have circulant generator matrices as follows :

( \begin{matrix}1 \\ ⋮ & \overline{w}Q + wN \\ 1 \end{matrix} ) and ( \begin{matrix}1 \\ ⋮ & wQ + \overline{w}N \\ 1 \end{matrix} ) .

We note that Q^{2} = N, N^{2} = Q and NQ = 1.

The minimum weight of the odd-like codes satisfy the stronger bound (5 ). As 2 is not a quadratic residue in this case, μ_{2} interchanges Q_{1} and N_{1}. But μ_{2} sends a binary vector to a binary vector and vμ_{2} = v^{2} for any vector v. Hence the subfield subcode of binary vectors equals Q_{1} ∩ N_{1}, the one-dimensional space generated by the all-one vector [40].

When p ≡ 5 (mod 8), the situation is reversed.

Even-like Q.R. idempotents

0 Q  N
0 w \overline{w}
0 \overline{w}  w
0 1  1

Odd-like Q.R. idempotents

0 Q  N
1 \overline{w}  w
1 w \overline{w}
0 1  1

Hence the two [p, \frac{p+1}{2}] Q.R. codes have the following circulant generator matrices

(1 + \overline{w}Q + wN) and (1 + wQ + \overline{w}N).

As above the subcode of binary vectors is ⟨h⟩.

The even-like [p, \frac{p−1}{2}] Q.R. codes and the extended [p + 1, \frac{p+1}{2}] codes are self-orthogonal with respect to the Hermitian inner product and hence all weights of vectors in these codes are even. The extended codes have the following circulant generator matrices

( \begin{matrix}1 \\ ⋮ & 1 + \overline{w}Q + wN \\ 1 \end{matrix} ) and ( \begin{matrix}1 \\ ⋮ & 1 + wQ + \overline{w}N \\ 1 \end{matrix} ) .

We note that Q^{2} = N, N^{2} = Q and NQ = Q + N.

The minimum weight of the odd-like codes satisfy the stronger bound (5) and is odd.

These results give the following theorem.

Theorem 5. There exist Q.R. codes of any odd prime length p over GF (2^{r}) for r even. When p ≡ ±1 (mod 8), they have the same generating idempotents as the binary Q.R. codes of that length. They also have the same minimum weights as their binary subcodes. When p ≡ ±3 (mod 8), they have the same idempotents as the quaternary Q.R. codes of that length. They also have the same minimum weights as their quaternary subcodes.

When r is odd, Q.R. codes over GF (2^{r}) exist only at prime lengths p ≡ ±1 (mod 8). They have the same generating idempotents as the binary Q.R. codes of that length and the same minimum weights as their binary subcodes.

Proof: If r is odd, 2^{r} is a square (mod p) exactly when 2 is. If a Q.R. code over GF (2^{r}) contains either a binary or quaternary Q.R. subcode, their generating idempotents must be those of the subcode. The facts about the minimum weights being that of the subcode is in [Chapter 1, Handbook].

Hence the minimum weights for Q.R. codes over fields of characteristic 2 are the same as the minimum weights of either binary or quaternary Q.R. codes. Of course, the binary Golay code can be represented as a Q.R. code. The minimum weights of binary Q.R. codes of length =^{<} 241 are given in [Chapter 1, Handbook]. Either of the bounds (4) or (5) is seen to be quite weak as the length increases. When known, the minimum weights of the binary Q.R. codes are quite good. What happens asymptotically as their length increases is not known.

Similarly quaternary Q.R. codes have high minimum weights when these are known [40]. The hexacode can be presented as an extended Q.R. code and we give this example now.

Example: p = 5. The two odd-like quaternary Q.R. codes are [5,3,3] codes, hence M.D.S. codes. One of these, C, has the following generator matrix given by its idempotent generator.

( \begin{matrix}0 & 1 & 2 & 3 & 4 \\ 1 & w & \overline{w} & \overline{w} & w \\ w & 1 & w & \overline{w} & \overline{w} \\ \overline{w} & w & 1 & w & \overline{w} \end{matrix} )

This is also a Hamming single error-correcting code. Its even-like subcode, C^{⊥}, is a [5, 2, 4] code, also an M.D.S. code. The even-like subcode as well as the extended code are self-orthogonal with respect to the Hermitian inner product. Hence all vectors in these codes have even weight.

The extended code is the unique [6,3,4] quaternary code called the hexacode. It is also an M.D.S. code. Its weight distribution is A_{0} = 1, A_{4} = 45, A_{6} = 18. The hexacode can be used to decode the [24,12,8] Golay code [39].

Vectors of each weight in the extended quaternary Q.R. codes of length 30 hold 5-designs [40]. Again these quaternary codes seem to be quite good as far as their minimum weights are known. Nothing is known asymptotically about them.

4.5 Q.R. Codes over Fields of Characteristic 3.

We can similarly describe all Q.R. codes over fields of characteristic 3 once we know the generating idempotents for Q.R. codes over GF (9). For this purpose we describe GF (9) in terms of a primitive element ρ which satisfies the equation ρ^{2} = ρ + 1. Then ρ^{3} = −ρ + 1, ρ^{4} = −1 and ρ^{8} = 1. The two new lengths we have are prime lengths p ≡ ±5 (mod 12). Ternary Q.R. codes exist at prime lengths p ≡ ±1 (mod 12). The analysis is similar to the previous cases (but more complicated) so we just present the results.

Theorem 6. If p is a prime ≡ 5 (mod 12), then the two odd-like [p, \frac{p+1}{2}] Q.R. codes Q_{1} and Q_{2} over GF (9) have the following form.

Q_{1} = ⟨−ρQ − ρ^{3}N⟩, N_{1} = ⟨−ρ^{3}Q − ρN⟩

For the even-like [p, \frac{p−1}{2}] Q.R. codes over GF (9),

Q_{2} = ⟨1 + ρ^{3}Q + ρN⟩ and N_{2} = ⟨1 + ρQ + ρ^{3}N⟩.

The even-like and extended odd-like codes are self-orthogonal with respect to the Hermitian inner product.

The minimum weight of the odd-like codes satisfies the stronger bound (5). The ternary subcode of the odd-like codes is ⟨h⟩.

From this theorem it can be shown that Q^{2} = −1 + N, N^{2} = −1 + Q and QN = N + Q.

Example: When p = 5, the two [5,3,3] Q.R. codes over GF (9) are M.D.S. codes as are the two extended [6,3,4] codes. The latter follows from the square root bound.

The minimum weights of the larger codes are as yet unknown.

Theorem 7. If p is a prime ≡ 7 (mod 12), then the two odd-like [p, \frac{p+1}{2}] Q.R. codes over GF (9) have the following idempotent generators.

Q_{1} = ⟨1 + ρ^{3}Q + ρN⟩, N_{1} = ⟨1 + ρQ + ρ^{3}N⟩.

The even-like [p, \frac{p−1}{2}] Q.R. codes over GF (9) are as follows

Q_{2} = ⟨−ρQ − ρ^{3}N⟩, N_{2} = ⟨−ρ^{3}Q − ρN⟩.

The even-like codes are self-orthogonal with respect to the ordinary inner product.

The minimum weight of the odd-like codes satisfies the stronger bound (5 ).

The ternary subcode of the odd-like codes is ⟨h⟩.

From this theorem it can be shown that Q^{2} = Q − N, N^{2} = N − Q and NQ = Q + N.

These Q.R. codes have not been studied yet.

Theorem 8. There exist Q.R. codes over GF (3^{r}) with r even of any odd prime length p ≠ 3. If r is odd, they exist of prime length p ≡ ±1 (mod 12).

At lengths p ≡ ±1 (mod 12), Q.R. codes over GF (3^{r}) have the ternary idempotents described above for the ternary Q.R. codes of these lengths. Also the minimum weight of these codes equals the minimum weight of its ternary subcode.

There are Q.R. codes over GF (3^{r}) for r even of prime length p ≡ ±5(mod 12). They have the idempotents described above for the Q.R. codes over GF (9). The minimum weight of the GF (3^{r}) Q.R. code equals the minimum weight of its GF (9) subcode. □

Again the best Q.R. codes over fields of characteristic 3 are either ternary, of lengths p ≡ ±1 (mod 12), or Q.R. codes over GF (9) of lengths p ≡ ±5 (mod 12).

Similar to the reasoning about Q.R. codes, it is often possible to compute generating idempotents of other cyclic codes such as duadic, triadic and polyadic codes [5],[24],[40],[41],[43],[44]. More material on quadratic residue codes are in the chapters on Groups [W.C. Huffman] and Representations [H. Ward].

5 Double-Circulant Constructions

We call a matrix A whose rows are cycled in the reverse fashion a back circulant. Let A be either a circulant or a back circulant. Then a matrix of the form (IA) is called a double-circulant. If A is bordered like

( \begin{matrix}a_{1} & a_{2} & ⋯ & a_{k} \\ b_{2} \\ ⋯ & & A \\ b_{k} \end{matrix} ) = A′,

then (IA′) is called a bordered double-circulant. Much of the usefulness of this construction arises from the fact that (−A^{t}I) = H generates the dual code of (IA) = G. Hence, when C is known to be self-dual, both G and H are generator matrices of C and this can be enough to determine its minimum weight. It is even helpful in the formally self-dual case when G and H generate equivalent (not necessarily equal) codes. Many very good codes have been constructed via double-circulant bases. Note that if A is a back-circulant, then A = A^{t}.

We start with the double-circulants used to construct ternary self-dual codes, the symmetry codes [33]. A [2(q + 1), q + 1] symmetry code exists for each prime power q ≡ −1(mod 3) and the columns of the A part of its bordered circulant generator matrix are labelled with 0, …, q − 1. The first row of A starts with 0 and then has 1 under the quadratic residues and −1 under the non-residues. For the border, the top row is (0, 1, …, 1) and the rest of the first column is 1 if q ≡ 1(mod 4) and it is −1 if q ≡ 3(mod 4). This generator matrix is called (IS_{q}) and the code it generates is called C(q). For example the [12,6] code C(5) has the following generator matrix.

∞ 0 1 2 3 4

(I | \begin{matrix}0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & -1 & -1 & 1 \\ 1 & 1 & 0 & 1 & -1 & -1 \\ 1 & -1 & 1 & 0 & 1 & -1 \\ 1 & -1 & -1 & 1 & 0 & 1 \\ 1 & 1 & -1 & -1 & 1 & 0 \end{matrix} )

It can be shown [33] that each row of (IS_{q}) has weight divisible by 3 and that the rows are orthogonal to each other (over any field). Hence C(q) is a self-dual ternary code. From this it can be shown that when q ≡ 1(mod 4), [−S_{q}|I] is also a generator matrix of C(q) and when q ≡ 3(mod 4), [S_{q}|I] generates C(q). A lemma in [33] says that any row of either of these generator matrices or the sum of two or three rows has weight =^{>} \frac{(q+7)}{2}. We let the left weight of a vector in C(q) be its weight on the first (q + 1) coordinates and its right weight be its weight on the last (q + 1) coordinates. We can easily determine that C(5) has minimum weight 6 by the following table.

Left Weight Right Weight
1  5
2  4
3  3 or more
4  2 or more by divisibility by 3
5  1 or more for some reason.

It is not much more difficult to show by hand that C(11) has minimum weight 9, although in this case and from now on, the other basis will also have to be used.

Left Weight Right Weight
1  8 or 11
2  7
3  6 or more
4  Cannot be 2 by the other basis

and line 2 above. Hence 5 or more.

5  Cannot be 1 for similar reason.
6  Cannot be 0 by the second basis. Hence 3 or more.

The determination of the minimum weights of the next three symmetry codes utilized the same method only in these cases the needed right weights of vectors with certain (low) left weights were determined by computer. The first five symmetry codes are extremal, self-dual [12,6,6], [24,12,9], [36,18,12], [48,24,15] and [60,30,18] codes. The first code is the Golay code. The second, fourth and fifth codes have the same parameters as the extended quadratic residue codes, but are not equivalent to them. This was shown by using the fact that the entire group of the extended ternary quadratic residue codes of length r + 1 > 12 modulo their centers is P SL_{2}(r). The double circulant construction can be used to show that the group of C(p) contains P SL_{2}(r) acting simultaneously on both sides. The conclusion for the second code follows as P SL_{2}(11) is not contained in P SL_{2}(23). A similar argument holds for the fourth and fifth codes. C(17) was the first extremal ternary [36,18,12] code constructed. The Assmus-Mattson Theorem gives many 5-designs in these five codes [33]. So in this situation, the double-circulant construction found excellent new codes. Using the two bases it can be shown that certain maximal weight vectors form a Hadamard matrix and its negative. The minimum weight of the next code C(41) is unknown.

Open Problem: Determine the minimum weight of any other symmetry code or provide any information about how the minimum weight changes as the length increases.

It is natural to try this over GF (2). Binary [2(p + 1), p + 1] double - circulant codes were studied by Karlin [20].

Theorem 9. Let p be a prime ≡ 3(mod 8) and label the columns of A with 0, …, (p − 1). Let A be a back-circulant whose first row has ones at

Q ∪ \{0\}. Let A′ be \begin{matrix}0 & 1 ⋯ 1 \\ 1 \\ ⋮ & A \\ 1 \end{matrix} . Then G = (IA′) generates a doubly-even,

binary self-dual [2(p + 1), p + 1] code C. Another generator matrix for C is (A′I).

Proof: Let p = 3+8r. Then the weight of the first row of G is p+1 = 4+8r which is divisible by 4. So is the weight of any other row, 2 + \frac{(p+1)}{2} = 4 + 4r. Clearly the top row of G is orthogonal to any other row of G. By Perron’s Theorem [31] every two rows of A have 2r + 1 ones in common, so that the corresponding rows of G have 2r + 2 ones in common. Hence C is self- dual and doubly-even. The statement about the other generator matrix follows as A = A^{T}.

Corollary: The sum of any two rows of G has weight \frac{p+5}{2}.

The above theorem was generalized by Bhargava and Tavares [2] to include p’s which are either prime powers ≡ 3(mod 4) or twin primes ≡ 3(mod 4). A number p is a twin prime if it can be written as r(r + 2) where both r and (r + 2) are primes. In this setting the matrix A is related to the incidence matrix of a difference set of Hadamard type. For p = 15, a twin prime, they obtain a construction of a s.e. [32,16,8] self-dual code.

If we let p = 3, it is easy to see that the extended Hamming [8,4,4] code has a double circulant representation of the above form.

Let p = 11 and construct a generator matrix of a doubly-even [24,12] code, C. The following left weight-right weight analysis show that G has minimum weight 8 and so must be the unique [24,12,8] Golay code.

Left Weight Right Weight
1  7 or 11
2  6 by the corollary
3  5 or more as it cannot be 1

by the other generator matrix.

4  4 or more as it cannot be 0

by the other generator matrix.

By the doubly-even property we do not need to go further.

A similar argument for p = 19 gives a generator matrix for a doubly-even [40,20,8] code. The next case, p = 43, cannot be done by hand but with the aid of a computer it can be shown that there is an [88,44,16] doubly-even code with a double-circulant generator matrix [2].

Another use of double circulants in the binary case is to construct even formally self-dual (f.s.d.) codes. These are [n, n/2] codes which are equivalent (not necessarily equal) to their dual codes. If C has a generator matrix of the form (IA) where A = A^{T}, then C is obviously equivalent to C^{⊥} with generator matrix (AI) and so C is f.s.d. If the all-one vector is in C (hence in C^{⊥}), then both C and C^{⊥} are even codes. If we let A be a back circulant, then A will be symmetric, and we can easily construct generator matrices for f.s.d. codes. If further all rows of A have odd weight, then the all-one vector is in the code and so it must be even. To construct an even [10,5,4] f.s.d. code we let the first row of A have ones on Q ∪ {0}. Such a code is unique [22]. To construct an even f.s.d. [14,7,4] code we put ones on Q for the first row of A. Even though there is no s.d. [30,15,8] code, there is such a f.s.d. code. One double circulant basis which works here has the form

(I \begin{matrix}1 & ⋯ & 1 \\ ⋮ & A & B \\ 1 & B & A \end{matrix} )

where A(B) is the 7 × 7 back circulant whose first rows has ones on Q(N). For others see [22].

Richard Jenson [19] tried to determine whether binary extended Q.R. codes have a double circulant generator matrix. It is known that P SL_{2}(p) is always contained in the group of the extended Q.R. code of length p (and is the entire group for p > 23) and that P SL_{2}(p) contains an element with two cycles of length \frac{p+1}{2}. The question then is whether the elements in one of these cycles label an information set in the extended code. Jenson found many such codes, possibly an infinite family, and two cases, p = 89 and p = 167 which do not have such a presentation. As shown above, both the [8,4,4] Hamming and [24,12,8] Golay codes do.

6 Contracted Codes

Both circulant and double circulant codes can be viewed as codes with certain permutations in their groups. Contracted codes are constructed from a code C with a certain permutation in its group. Often the contracted code can be determined precisely from the permutation and certain properties of C. One can then, on occasion, construct C or show that such a C with such a permutation cannot exist. If the code C is known and elements in the group of C are known, the contracted code can be used to find vectors of low weight in C.

Suppose that a code C over GF(q) of length n has a permutation σ of prime order r in its group. Let σ have c cycles and f fixed points so that n = cr + f. Let D be the subcode of C, called the invariant subcode, consisting of all codewords x fixed by σ, i.e. xσ = x. If g.c.d.(r, q) = 1, then D consists of all vectors of the form x + xσ + ⋯ + xσ^{r−1} for x in C. Clearly such a vector is in D. On the other hand, if x is in D, then rx = x + xσ + ⋯ + xσ^{r−1}. It is easy to see that any vector in D has constant components on any cycle of σ. The contracted code C(σ) is the length (c+f) code over GF (q) whose codewords are obtained from the codewords in D by omitting all but one component of each cycle of σ. A fixed point is considered to be a cycle of length one. For example, if C is the [24,12] binary Golay code and σ is an element of order 11 in its group, then c = f = 2 and C(σ) is the [4,2,2] self-dual code with the following generator matrix.

1 2 3 4
1 0 1 0
0 1 0 1

This is related to the double-circulant representation of C. If σ has order 23, C(σ) is the [2,1,2] code.

Much of the usefulness of contracted codes is due to the following theorem [38].

Theorem 10. If C is a self-dual code over F and has a permutation σ of order r in its group where r is relatively prime to the characteristic of F, then C(σ) is also self-dual in the following cases.

1) F is GF (2).

2) F is GF (3) and each cycle of σ has length ≡ i(mod 3) where i is 1 or 2 and r ≡ 1(mod 3) if σ has fixed points .

3) F is GF (4).

Further, if F is GF (2) and C is doubly-even, then C(σ) is also doubly -even when all cycles of σ have length ≡ 1(mod 4).

As self-dual codes of modest lengths have been classified, this theorem allows us to use information about contracted codes to obtain information about the longer codes that the contracted codes came from.

In [11], contracted codes were used to show that if a [72,36,16] doublyeven code C exists, then its group can contain no element of order greater than 11 except for 17 and 23. Take an element σ of order 41 for example. Such a permutation must have 1 cycle and 31 fixed points. Hence C(σ) is a [32,16] doubly-even code. If the first coordinate of this code represents the 41- cycle and we shorten C(σ) on that coordinate, we get a [31,15,16] code. As there is no such code, σ cannot exist. Other useful conditions for the contracted code to exist are given in [8] and [11].

If there is an element σ of order 23 in the group of a putative [72,36,16] doubly-even code C, then it must have 3 cycles and 3 fixed points [11]. This element was eliminated by constructing all 348 possibilities by analyzing the length 23 cyclic codes which could occupy the cycles, and computing that all these codes must have minimum weight 12 or less [37]. An element σ of order 17 in the group of C must have 4 cycles and 4 fixed points [11] so that C(σ) is the [8,4,4] doubly-even code. Again a detailed analysis of how cyclic codes of length 17 could occupy these cycles led to the 16.17^{3} codes whose minimum weights were computed to be 12 or less [46]. The prime 11 was eliminated in [18]. At present the only odd primes which can be in the group order of a [72,36,16] code, if it exists, are 7, 5 and 3.

In response to the listing [13] of weight enumerators of extremal codes, Buyuklieva and Yorgov [8] describe all singly-even [40,20,8] codes whose groups contain an element of order 5. These were constructed by working up from its contracted [8,4,2] self-dual code. Some of these codes have new extremal weight enumerators. A similar feat was performed for all singly-even [40,20,8] codes whose group contains an element of order 7.

A particularly interesting weight enumerator of a self-dual [50,25,10] code was given in [13]. Its existence was related to that of a certain quasisymmetric design. Huffman and Tonchev [17] constructed such a code whose group they assumed contained an element of order 7, with 7 cycles and 1 fixed point, by working up from its contracted [8,4,4] doubly-even code. A systematic way of determining which codes can lead to a certain contracted code was developed by both Huffman and Yorgov and is described in the section on decompositions of codes in the chapter on Groups and Codes of this handbook.

In the case of the ternary symmetry codes of length greater than 60 more is known about the group of the code than about its minimum weight. The group of the [84,42] symmetry code C contains P SL_{2}(41) which has an element σ of order 7 with 12 cycles and no fixed points. Hence C(σ) is a [12,6] self-dual ternary code. It was found that C(σ) is a [12,6,3] code so that the minimum weight of C is =^{<} 21.

Quadratic residue codes are interchanged by any μ_{n} where n is a nonresidue. A similar situation holds for duadic codes although the multiplier need not be a non-residue. This is generalized to triadic codes [44] where a multiplier cycles three codes. Polyadic codes [5], are generalizations of duadic and triadic codes.

7 Greedy Codes

Let all binary n-tuples, V_{n}, be ordered lexicographically and choose a distance d. We construct a set S consisting of the zero vector, then we proceed through V_{n} in its given order choosing vectors at distance d or more from all the previously chosen vectors. It is surprising that S is actually a linear code [6,13,22]. When d = 3, and n = 2^{r} − 1, the Hamming [n, n − r, 3] codes are obtained. When d = 4, the extended Hamming code occurs and when d = 7(8) we obtain the Golay (extended Golay) code. In fact many excellent codes occur this way (see [7] and [14]). The same phenomenon occurs for other orders, called B-orders [7].

Choose an ordered basis {y_{i}, i = 1, …, n} for V_{n} and order the vectors as follows: zero vector, y_{1}, y_{2}, y_{2} ⊕ y_{1}, y_{3}, y_{3} ⊕ y_{1}, y_{3} ⊕ y_{2}, y_{3} ⊕ y_{2} ⊕ y_{1}, y_{4}, . . .. This ordering is a B-ordering and codes generated by the above greedy algorithm with respect to a B-ordering are called greedy codes. Even though this method produces seemingly very good codes, it takes too long to generate even codes of modest length.

An improvement is possible when the ordering is triangular [7], that is when y_{i} = (0, … 0, 1, …) with the 1 in the n−ith position. In this situation, a parity check matrix, called the g-parity check matrix H can be constructed as follows. The columns of H are constructed one by one. The right most

column is ( 0 ⋮ 0 1 ). We denote the columns of H by their binary representations,

so that this column is 1. Suppose H_{i} = [h_{i}, …, h_{1}] has been determined and

y_{i+1} = (0 ⋯ 0, 1^{i+1}, ∈_{i}, …, ∈_{1}). Then h_{i+1} = a ⊕ (∈_{i} h_{i} ⊕ ⋯ ⊕ ∈_{1} h_{1}) where

a is the smallest integer such h_{i+1} is not a sum of fewer than d − 1 columns of H_{i}. We let H_{i+1} = [h_{i+1}, h_{i}, …, h_{1}]. H is called the g-parity check matrix since certain numbers, called g-values, can be assigned to all the vectors in V_{n} by a greedy process similar to the one which finds code vectors, all of which have g-value 0 [7]. Further, it was shown that the syndrome of any vector with respect to H is its g-value.

It is also known [7] that the triangular greedy codes for d = 4 are either extended Hamming codes or shortened extended Hamming codes. Hence the above algorithm gives a parity check matrix for extended Hamming or shortened, extended Hamming codes. Any triangular greedy code for d = 3 is a punctured triangular greedy code for d = 4. Thus a parity check matrix of any Hamming code can be obtained by the above algorithm.

The greedy construction yields linear codes over any field of characteristic 2^{2^{a}} [14],[49]. However g values and the corresponding g-parity check matrix are known only for GF (2). However, the algorithm for such an H ( analogous to the g-parity check matrix algorithm) with ∈_{i} determined in advance, independent of any ordering, can be used over any field. This algorithm has been used to find codes over GF (4) better than any known codes [29].

Open Problems:

1) Does the g-parity check algorithm give the greedy-codes over GF (2^{2^{a}})?

2) Does the g-parity check algorithm correspond to some greedy choice of vectors for other fields?

Other constructive techniques can be found in many other chapters, in particular the ones on tables, self-dual codes, codes and groups, codes and finite geometries, designs, concatenated codes, convolutional codes, and covering radius.

References

[1] E.F. Assmus, Jr., J. Key – Designs and Their Codes, Cambridge University Press, 1992.

[2] V.K. Bhargava, S.E. Tavares – Difference sets of the Hadamard type and quasi-cyclic codes, Information and Control 26 (1974), 341-350.

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

[4] R.A. Brualdi, V. Pless, R.M. Wilson – Short codes with a given covering radius, IEEE Trans. Info. Th. 35 (1989), 99-109.

[5] R.A. Brualdi, V. Pless – Polyadic codes, Discrete Applied Math 25 (1989), 3-17.

[6] R.A. Brualdi, V. Pless – Weight enumerators of self-dual codes, IEEE Trans. Info. Th. 36 (1991), pp. 1222-1225.

[7] R.A. Brualdi, V. Pless – Greedy codes, JCT (A) 64 (1993), 10-30.

[8] Buyuklieva, V. Yorgov – Singly-even self-dual codes of length 40 – preprint.

[9] P. Camion, B. Corteau, A. Montpetit – Coset weight enumerators of the extremal self-dual binary codes of length 32, preprint.

[10] J.H. Conway, V. Pless – On the enumeration of self-dual codes, JCT (A) 28 (1980), 26-53.

[11] J.H. Conway, V. Pless – On primes dividing the group order of a doublyeven (72,36,16) code and the group order of a quaternary (24,12,10) code, Discrete Math 38 (1982), 143-156.

[12] J.H. Conway, N.J.A. Sloane – Sphere-Packings, Lattices and Groups, New York: Springer-Verlag 1988.

[13] J.H. Conway, N.J.A. Sloane – A new upper bound on the minimal distance of self-dual codes, IEEE Trans. Info. Th. 36 (1990), 1319-1333.

[14] J.H. Conway, N.J.A. Sloane – Lexicographic codes: error-correcting codes from game theory, IEEE Trans. Info. Th. 32 (1986), 337-348.

[15] P. Delsarte – Four fundamental parameters of a code and their combinatorial significance, Info. and Control 23 (1973), 407-438.

[16] M. van Eupen, R. Hill–An optimal ternary [69,5,45] code and related codes, Designs, Codes and Cryptography, 4 (1994), 271-282.

[17] W.C. Huffman, V.D. Tonchev – the existence of extremal self-dual [50,25,10] codes and quasi-symmetric 2 − (49, 9, 6) designs, Designs, Codes,and Cryptography 6 (1995),97-106.

[18] W.C. Huffman, V.Y. Yorgov – A [72,36,16] doubly even code does not have an automorphism of order II, IEEE Trans. Info. Th. 33 (1987), 749-752.

[19] R. Jenson – A double circulant presentation for Quadratic Residue codes, IEEE Trans. Info. Th. 26 (1980).

[20] M. Karlin – New binary coding results by circulants, IEEE Trans. Info. Th. 15 (1969), 81-92.

[21] G.T. Kennedy– Weight distributions of linear codes and the Gleason-Pierce Theorem. J. Combin. Th. (A) 67 (1994), 72-88.

[22] G.T. Kennedy, V. Pless – On designs and formally self-dual codes. Designs, Codes and Cryptography 4 (1994), 43-55.

[23] H.V. Koch – On self-dual, doubly-even codes of length 32, JCT (A), 51 (1989), 63-76.

[24] J.S. Leon, J.M. Masley, V. Pless – Duadic Codes, IEEE Trans. Info. Th. 30 (1984), 709-714.

[25] V.I. Levenshtein – A class of systematic codes, Soviet Math. Dokl. 1, No. 1 (1960), 368-371.

[26] F.J.MacWilliams and N.J.A. Sloane–The Theory of Error-Correcting Codes, North Holland, Amsterdam, 1977.

[27] F.J. MacWillians, N.J.A. Sloane and J.G. Thompson – Good self-dual codes exist, Discrete Math. 3 (1972), 153-162.

[28] C.L. Mallows, V. Pless, N.J.A. Sloane – Self-dual codes over GF (3), SIAM J. Applied Math 31 (1976), 649-666.

[29] L. Monroe – On Greedy Codes, Ph.D. thesis, Univ. of Illinois at Chicago, Chicago, IL, 1995.

[30] D.W. Newhardt – On minimum weight codewords in Q.R. codes, J. Combin. Th. (A) 48 (1988), 104-119.

[31] O. Perron – Bemerkungen über die Verteilung der quadratischen Reste, Math. Zeit. 56 (1952), 122-130.

[32] V. Pless – On the uniqueness of the Golay codes, JCT (A) 5 ( 1968), 215-228.

[33] V. Pless – Symmetry codes over GF (3) and new five designs, JCT (A) 12 (1972), 119-142.

[34] V. Pless – A classification of self-orthogonal codes over GF (2), Discrete Math. 3 (1972), 209-246.

[35] V. Pless – Symmetry codes and their invariant subcodes JCT (A) 18 (1975), 116-125.

[36] V. Pless – Introduction to the Theory of Error-Correcting Codes, second edition, Wiley, New York, 1989.

[37] V. Pless – 23 does not divide the order of the group of a (72,36,16) doubly-even code, IEEE Trans. Info. Th. 28 (1982), 112-117.

[38] V. Pless – On the uses of contracted codes, Proc. of Ninth Australian Combinatorics Conf., Univ. of Queensland, Combinatorial Mathematics IX, Lecture Notes in Math., Springer-Verlag, Berlin (1982), 115-122.

[39] V. Pless – Decoding the Golay codes, IEEE Trans. Info. Th. 32 (1986), 561-567.

[40] V. Pless – Q-Codes, JCT (A) 43 (1986), 258-276.

[41] V. Pless – Duadic Codes and generalizations, Proceedings of Eurocode 1992, Udine, Italy, CISM Courses and Lectures, No. 339, Springer-Verlag, N.Y., 3-16.

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

[43] V. Pless, J.M. Masley, J. Leon – On weights in duadic codes, JCT (A) 44 (1987), 6-21.

[44] V. Pless, J.J. Rushanan – Triadic codes, LAA 98 (1988), 415-433.

[45] V. Pless, N.J.A. Sloane – On the classification and enumeration of selfdual codes, JCT (A) 18 (1975), 313-335.

[46] V. Pless, J. Thompson – 17 does not divide the order of the group of a (72,36,16) doubly-even code, IEEE Trans. Info. Th. 28 (1982), 537-544 .

[47] NJ.A. Sloane, S.M. Reddy, C.L. Chen – New binary codes, IEEE Trans. Info. Th. 18 (1972), 503-510.

[48] V.Y. Yorgov – On the extremal doubly-even codes of length 32, Proc. Fourth Joint Swedish-Soviet Int. Workshop on Inform. Th. Gotland, Sweden (1989), 275-279.

[49] A.J. van Zanten – Lexicographic order and linearity, preprint .