JACODESMATH / ISSN 2148-838X

J. Algebra Comb. Discrete Appl.
1(1) • 29-39

Received: 9 July 2014; Accepted: 19 August 2014
DOI 10.13069/jacodesmath.79879

Journal of Algebra Combinatorics Discrete Structures and Applications

New extremal binary self-dual codes of length 68

Research Article

Abidin Kaya1∗, Bahattin Yildiz1∗∗

1. Department of Mathematics, Fatih University, 34500, İstanbul, Turkey

Abstract: In this correspondence, we consider quadratic double and bordered double circulant construction
methods over the ring R := F2 + uF2 + u2F2, where u3 = 1. Among other examples, extremal
binary self-dual codes of length 66 are obtained by these constructions. These are extended by using
extension theorems for self-dual codes and as a result 8 new extremal binary self-dual codes of length
68 are obtained. More precisely, codes with β=117, 120, 133 in W68,1 and with γ = 1, β=49, 57,
59 and codes with γ=2, β=69, 81 in W68,2 are constructed for the first time in the literature. The
binary generators of these codes are available online at [7]. In addition to these, some known codes
are reconstructed via this extension. The results are tabulated.

2010 MSC: 94B05, 94B60, 94B65

Keywords: Extremal codes, Codes over rings, Gray maps, Quadratic double-circulant codes

1. Introduction

The theory of self-dual codes, especially the so called extremal ones, has attracted a lot of research in
the coding theory community. The connection of self-dual codes with many different fields of study such
as designs, lattices and cryptography has made them of interest to many researchers. The theoretical
background for extremal binary self-dual codes has been established in [1, 2, 9] and the references therein.
In the aforementioned works, among other things, it was established that extremal binary self-dual codes
can only have certain weight enumerators. Much of the research in the study of self-dual codes has been
towards finding extremal self-dual codes with new weight enumerators.

Starting with [3], the use of quadratic residues has been part of the armory for constructing binary
self-dual codes. The method, which combines quadratic residues with the well-known methods of double
circulant and bordered double circulant constructions has successfully been used to obtain many new
extremal binary self-dual codes in [6] and [8]. In doing so, rings other than the binary field, which are
endowed with duality and distance preserving Gray maps were used.

In this work we consider the construction method described above for the ring R := F2 +uF2 +u2F2,
where u3 = 1. This is a non-chain extension of the binary field. We describe a Lee weight and a related

∗ E-mail: akaya@fatih.edu.tr
∗∗ E-mail: byildiz@fatih.edu.tr

29



New extremal binary self-dual codes of length 68

distance-preserving Gray map for the ring. Unlike many of the rings studied before, the Gray map is
not duality-preserving. However we establish the conditions for the Gray image to be self-dual. Using
quadratic double and bordered double circulant constructions over the ring R, we find extremal binary
self-dual codes of length 66. Applying extensions to these codes we find eight new binary extremal self-
dual codes of length 68. More precisely, codes with β=117, 120, 133 in W68,1 and with γ = 1, β=49, 57,
59 and codes with γ=2, β=69, 81 in W68,2 are constructed for the first time in the literature.

The rest of the work is organized as follows. Section 2 includes a general overview on the ring R
and self-dual codes. In Section 3, we consider projections, lifts and duality conditions. Section 4 contains
the quadratic double and bordered double circulant constructions over the ring R and some extremal
self-dual examples including codes of length 66. In Section 5, codes of length 66 are extended, using
extension theorems, to obtain new extremal binary self-dual codes of length 68. The paper ends with
some concluding remarks and comments.

2. Preliminaries

2.1. The structure of the ring F2 + uF2 + u2F2 with u3 = 1

The ring F2 +uF2 +u2F2 defined by the relation u3 = 1 is isomorphic to F2 [x] /
〈
x3 − 1

〉
. Throughout

the text the ring F2 + uF2 + u2F2 is denoted by R and it is easily observed that R ∼= F2 × F4. The ring
R is not a local ring because its ideal structure is given by I0 ⊂ Iu+u2,I1+u+u2 ⊂ R where;

I1+u+u2 =
(
1 + u + u2

)
=
{

0, 1 + u + u2
}
,

Iu+u2 = (1 + u) =
{

0,u + u2, 1 + u, 1 + u2
}
.

However, it is a Frobenius ring as can easily be seen by the isomorphism R ∼= F2 × F4. The units in the
ring R are given by

{
1,u,u2

}
and the non-units are{

u + u2, 1 + u, 1 + u2, 1 + u + u2
}
.

The ring R has two primitive idempotent elements
{
u + u2, 1 + u + u2

}
. Every element of the ring R

can be written in a unique way as a + bu + cu2 =
(
1 + u + u2

)
(a + b + c) +

(
u + u2

)
(a + c + (b + c) u).

A linear code C of length n over the ring R is an R-submodule of Rn and has a generating matrix
that is permutation equivalent to

G =


 Ik1 A B C0 (u + u2)Ik2 0 (u + u2)D

0 0
(
1 + u + u2

)
Ik3

(
1 + u + u2

)
E


 .

We define a Gray map as follows;

ϕ : Rn → F3n2
a + bu + cu2 7→

(
a,b,c

)
.

Definition 2.1. The Lee weight of an element x = a + bu + cu2 ∈ R is the Hamming weight of its Gray
image, i.e. wtL

(
a + bu + cu2

)
= wtH (a) + wtH (b) + wtH (c). An element is called even if its Lee weight

is even and odd otherwise.

So, the elements in ideal Iu+u2 are even and 1,u,u2, 1 +u+u2 are the odd elements. The Lee weight
of a codeword is defined to be the sum of the Lee weights of its components. The minimum Lee weight
of a code C is denoted by wtL (C) and defined as wtL (C) = min{wtL (c) |c ∈C}.

Definition 2.2. A code C over R is called an even code if all the codewords have even Lee weight.

30



A. Kaya, B. Yildiz

The duality is understood in terms of the Euclidean inner product; a◦ b =
∑
aibi. The dual of C is

defined as C⊥ = {y ∈ Rn | y ◦x = 0 for all x ∈C}. A code C is said to be self-orthogonal if C ⊆ C⊥ and
self-dual if C = C⊥. A self-dual binary code is said to be Type II if all codewords have weight divisible
by 4 and Type I otherwise.

The minimum distance d of a binary self-dual code of length n is bounded above as d ≤ 4 [n/24] + 6
if n ≡ 22 (mod 24) and d ≤ 4 [n/24] + 4, otherwise ([1, 9]). A self-dual code is called extremal if it meets
the bound.

2.2. Quadratic double circulant codes

Quadratic double circulant (QDC) codes are a generalization of quadratic residue codes and have
been introduced in [3]. Let p be an odd prime and Qp (a,b,c) be the circulant matrix with first row r
based on quadratic residues modulo p defined as r [1] = a, r [i + 1] = b if i is a quadratic residue and
r [i + 1] = c if i is a quadratic non-residue modulo p. We state the special case of the main theorem from
[3] where p is an odd prime;

Theorem 2.3. ([3]) Let p be an odd prime and let Qp (a,b,c) be the circulant matrix with a,b and c as
the elements of the ring R. If p = 4k + 1 then

Qp (a,b,c) Qp (a,b,c)
T

= Qp

(
a2 + 2k

(
b2 + c2

)
, 2ab− b2 + k (b + c)2 , 2ac− c2 + k (b + c)2

)
If p = 4k + 3 then

Qp (a,b,c) Qp (a,b,c)
T

= Qp(a
2 + (2k + 1)

(
b2 + c2

)
,ab + ac + k

(
b2 + c2

)
+ (2k + 1) bc,

ab + ac + k
(
b2 + c2

)
+ (2k + 1) bc).

Definition 2.4. ([3]) The code generated by Pp (a,b,c) =
(
Ip Qp (a,b,c)

)
over the ring R is called a

quadratic pure double circulant code and is denoted by Pp (a,b,c). In a similar way, the code generated
by

Bp (a,b,c | λ,β,γ) =
(
Ip+1

λ β ×1
γ ×1T Qp (a,b,c)

)
,

where 1 is the all 1 vector of length p, is called a bordered quadratic double circulant code and is denoted
by Bp (a,b,c | λ,β,γ).

3. Projections, lifts and duality conditions

Since the Gray map introduced in Section 2 does not preserve orthogonality, we start with de-
termining the conditions when the binary image of a code over the ring R is self-orthogonal. Then, a
projection and related lift will be defined. The extended quadratic residue codes of parameters [24, 12, 8]2
and [48, 24, 12]2 which are unique up to equivalence are constructed as lifts of self-dual double circulant
binary codes.

The following example indicates that the Gray image of a self-orthogonal code over the ring R is not
necessarily a self-orthogonal binary code.

Example 3.1. Let us consider the code C over the ring R of length 3 generated by(
1 + u, 1 + u2,u + u2

)
.

31



New extremal binary self-dual codes of length 68

We may easily observe that the code is self-orthogonal since

(1 + u)
2

+
(
1 + u2

)2
+
(
u + u2

)2
= 1 + u2 + 1 + u + u + u2 = 0.

On the other hand, its binary image is the code generated by

G =


 1 1 0 1 0 1 0 1 10 1 1 1 1 0 1 0 1

1 0 1 0 1 1 1 1 0




and it is not self-orthogonal since distinct rows of G are not orthogonal to each other.

Definition 3.2. A vector x = a + bu + cu2 over the ring R can be expressed as

x =
(
1 + u + u2

)(
a + b + c

)
+
(
u + u2

)(
a + c +

(
b + c

)
u
)
.

a + b + c and a + c +
(
b + c

)
u are called F2 and F4-components of x, respectively.

Definition 3.3. A matrix over the ring R is said to be free of u if all its entries are of the form a + bu2
with a, b ∈ F2.

Lemma 3.4. The Gray images of two vectors x = a+bu+cu2 and y = d+eu+fu2 in Rn are orthogonal
to each other if their F2-components are orthogonal and the product of their F4-components is free of u.

Proof. If the F2-components of the vectors x and y are orthogonal we have(
a + b + c

)
◦
(
d + e + f

)
= a◦d + a◦e + a◦f + b◦d + b◦e + b◦f + c◦d + c◦e + c◦f = 0 (1)

and if the inner product of their F4-components
(
a + c +

(
b + c

)
u
)
◦
(
d + f +

(
e + f

)
u
)
is free of u we

have a◦e + a◦f + b◦d + b◦f + c◦d + c◦e = 0, which implies a◦d + b◦e + c◦f = 0 by (1). Hence
ϕ (x) ◦ϕ (y) = 0.

We would like to determine when the Gray image of a code is self-dual. Much like ring elements and
vectors, a matrix G over R can also be expressed as

G = G1 + uG2 + u
2G3

=
(
1 + u + u2

)
(G1 + G2 + G3) +

(
u + u2

)
(G1 + G3 + (G2 + G3) u)

where G1, G2 and G3 are binary matrices. G1 + G2 + G3 is called F2-component of G and denoted by
GF2 and G1 + G3 + (G2 + G3) u is called F4-component of G and denoted by GF4.

The following theorem characterizes codes over the ring R with self-orthogonal binary images:

Theorem 3.5. Let C be the code generated by G over the ring R. Then ϕ (C) is a self-orthogonal binary
code if GF2G

T
F2 = 0 and GF4G

T
F4 and GF4 (uG)

T
F4 are matrices over the ring R which are free of u.

Proof. Let G = G1 + uG2 + u2G3 then GF2G
T
F2 = 0 implies

(G1 + G2 + G3)
(
GT1 + G

T
2 + G

T
3

)
= 0. (2)

The matrix GF4G
T
F4 = (G1 + G3 + (G2 + G3) u)

(
GT1 + G

T
3 +

(
GT2 + G

T
3

)
u
)
is free of u implies

G1G
T
2 + G1G

T
3 + G3G

T
2 + G2G

T
1 + G2G

T
3 + G3G

T
1 = 0

then this together with equation (2) implies

G1G
T
1 + G2G

T
2 + G3G

T
3 = 0. (3)

32



A. Kaya, B. Yildiz

Similarly, if GF4 (uG)
T
F4 = (G1 + G3 + (G2 + G3) u)

(
GT3 + G

T
2 +

(
GT1 + G

T
2

)
u
)
is free of u then we have

G1G
T
1 + G1G

T
2 + G3G

T
1 + G2G

T
3 + G2G

T
2 + G3G

T
3 = 0 then this together with equation (3) gives

G1G
T
2 + G3G

T
1 + G2G

T
3 = 0. (4)

Now consider the Gray image ϕ (C) of C which is generated by

G∗ =


 ϕ (G)ϕ (uG)
ϕ
(
u2G

)

 =


 G1 G2 G3G3 G1 G2
G2 G3 G1


 .

By equations (3) and (4) we have G∗ (G∗)T = 0 which implies ϕ (C) is a self-orthogonal binary code.

Example 3.6. The code generated by the matrix

G =

(
1 0 1 + u u
0 1 u 1 + u

)
is a free self-dual code over the ring R but its Gray image is not self-dual. We may easily observe

that GF2 =
(

1 0 0 1
0 1 1 0

)
and it generates a binary self-dual code. On the other hand, GF4 = G and

(uG)F4 =

(
u 0 1 1 + u
0 u 1 + u 1

)
. The matrix GF4 (uG)

T
F4 =

(
1 + u + u2 1 + u + u2

1 + u + u2 1 + u + u2

)
is not free of u.

If C is self-orthogonal over the ring R then some of the conditions of Theorem 3.5 may be relaxed.

Lemma 3.7. Let C be a self-orthogonal code over the ring R and G be a generator matrix of C. Then
ϕ (C) is a binary self-orthogonal code if GF4GTF4 and GF4 (uG)

T
F4 are free of u.

Proof. Let G =
(
1 + u + u2

)
GF2 +

(
u + u2

)
GF4 be a generator matrix for a self-orthogonal code over

R. Then GGT = 0 which implies GF2G
T
F2 = 0. The result follows by Theorem 3.5.

An immediate consequence of Lemma 3.7 is;

Lemma 3.8. Let G be a generator matrix of a self-dual code C over the ring R. Then ϕ (C) is a binary
self-dual code if GF4G

T
F4 and GF4 (uG)

T
F4 are free of u.

Lemma 3.9. A self-orthogonal code C over the ring R is an even code.

Proof. Let C be a self-orthogonal code of length n over the ring R and x be an arbitrary codeword
in C. Let x = a + bu + cu2 where a,b and c ∈ Fn2 then x◦x = a◦a + (c◦ c) u +

(
b◦ b

)
u2 = 0 implies

a ◦ a = 0 = b ◦ b = c ◦ c. Then, wtH (a), wtH
(
b
)
and wtH (c) are even since a self-orthogonal binary

vector has even weight. Hence, wtL (x) = wtH (a) + wtH
(
b
)

+ wtH (c) is even.

We define a projection π : R → F2 as;

π (r) =

{
1
0

if r is odd
if r is even.

The projection π is extended componentwise and denoted by Π. For a matrix G over the ring R the
projection of the matrix is its F2-component; Π (G) = GF2.

Moreover, π is a ring homomorphism. So, the following result follows;

Lemma 3.10. Let C be a linear code over the ring R generated by matrix G then C is an even code if
the rows of G are even.

33



New extremal binary self-dual codes of length 68

Definition 3.11. Let C be a code of length n over the ring R. The code C is said to be a lift of the binary
code D if Π (C) = D. The code D is called the projection of C.

Note that the projection of a self-dual code is a binary self-orthogonal code. On the other hand a
lift of a self-dual code may not be self-dual. In the following example we construct the extended binary
Golay code as a lift of the [8, 4, 4]2 extended Hamming code.

Example 3.12. Take the following generator matrix of the [8, 4, 4]2 extended Hamming code

G =


 I4

0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0


 .

We lift G to a matrix G∗ over the ring R by keeping I4 as it is and lifting 0 to an even element and 1 to
an odd element. Let C∗ be the code generated by

G∗ =


 I4

u + u2 1 + u + u2 1 1
1 u + u2 1 + u + u2 1
1 1 u + u2 1 + u + u2

1 + u + u2 1 1 u + u2


 .

G∗F2 = G and

G∗F4 =


 I4

1 0 1 1
1 1 0 1
1 1 1 0
0 1 1 1


 , (uG)∗F4 =


 uI4

1 + u 0 u u
u 1 + u 0 u
u u 1 + u 0
0 u u 1 + u




GGT = 0 and G∗F4
(
uG∗F4

)T
is 4×4 circulant matrix with first row (1, 0, 1, 1) and hence is free of u. Thus

by Theorem 3.5 ϕ (C∗) is self-dual, which turns out to be the [24, 12, 8]2 extended binary Golay code.

Example 3.13. The binary code generated by G = (I8 | A) where A is the circulant matrix with first
row rA = (0, 1, 0, 0, 0, 1, 0, 1) is a self-dual [16, 8, 4]2-code. Consider a lift

rA′ =
(
1 + u,u2,u + u2, 1 + u, 0, 1 + u + u2,u + u2, 1 + u + u2

)
of rA. Then the code generated by G′ = (I8 | A′) where A′ is the circulant matrix with first row rA′ has
a self-dual binary image that is the unique self-dual [48, 24, 12]2-code.

Example 3.14. The double circulant binary code generated by G = (I11 | A) where A is the 11 × 11
circulant matrix with first row rA = (1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0) is a self-dual [22, 11, 6]2-code. Let

rA′ =
(
1, 1, 1, 1 + u2, 1 + u2, 1 + u2, 1, 1 + u2,u + u2, 1, 1 + u2

)
be a lift of rA and C be the code over the ring R generated by G′ = (I11 | A′) where A′ is the circulant
matrix with first row rA′. The binary image ϕ (C) of C which we denote by C66,0 is an extremal self-dual
binary code of lengh 66.

4. Quadratic Double Circulant codes over R

In this section, we consider QDC codes over the ring R and obtain families of codes which satisfy
duality conditions given in Theorem 3.5. Therefore we obtain self-dual binary codes as Gray images of
codes over the ring R. In particular, some extremal self-dual [66, 33, 12]2-codes are reconstructed.

34



A. Kaya, B. Yildiz

Theorem 4.1. Let p ≡ 3 (mod 8) be an odd prime. Then Pp
(
0, 1 + u2, 1 + u + u2

)
and

Pp
(
1 + u2,u, 1 + u

)
are codes over the ring R with self-dual binary images.

Proof. A generator matrix of Pp
(
0, 1 + u2, 1 + u + u2

)
is given by

G =
(
Ip Qp

(
0, 1 + u2, 1 + u + u2

) )
.

Then GF2 =
(
Ip Qp (0, 0, 1)

)
and by Theorem 2.3 we have

Qp (0, 0, 1) Qp (0, 0, 1)
T

= Qp (1, 0, 0) = Ip.

So GF2 (GF2 )
T

= 0. Analogously, GF4 =
(
Ip Qp (0,u, 0)

)
by Theorem 2.3 we have

Qp (0,u, 0) Qp (0,u, 0)
T

= Qp
(
u2, 0, 0

)
= u2Ip.

Therefore, GF4 (GF4 )
T

=
(
1 + u2

)
Ip which is free of u. Now, we need to show that GF4 (uG)

T
F4 is also

free of u where (uG)F4 =
(
uIp Qp (0, 1 + u, 0)

)
. We have

Qp (0,u, 0) Qp (0, 1 + u, 0)
T

= uQp (0, 1, 0) (1 + u) Qp (0, 1, 0)

=
(
u + u2

)
Ip by Theorem 2.3,

which implies GF4 (uG)
T
F4 = uIp +

(
u + u2

)
Ip = u

2Ip which is free of u. Hence, by Theorem 3.5 the
binary image of Pp

(
0, 1 + u2, 1 + u + u2

)
is self-orthogonal. Since

∣∣Pp (0, 1 + u2, 1 + u + u2)∣∣ = 8p it has
a self-dual binary image. The same can be done for Pp

(
1 + u2,u, 1 + u

)
.

Theorem 4.2. Let p be a prime with p ≡ 3 (mod 8). Then the code

Bp
(
1,u + u2, 1 + u + u2 | 0, 1, 1

)
is a self-dual code over the ring R and its Gray image is a binary self-dual Type II code.

Proof. Let bi denote the i-th row of the matrix

G = Bp
(
1,u + u2, 1 + u + u2 | 0, 1, 1

)
=

(
Ip+1

0 1
1T Qp

(
1,u + u2, 1 + u + u2

) ) .
Then b1 ◦ b1 = 0 since p is odd. If p = 8k + 3 then for 2 ≤ i ≤ p + 1 we have

b1 ◦ bi = 1 +
p− 1

2

(
u + u2

)
+
p− 1

2

(
1 + u + u2

)
= 1 + (4k + 1) = 0.

So by Theorem 2.3 we have

Qp
(
1,u + u2, 1 + u + u2

)
Qp
(
1,u + u2, 1 + u + u2

)T
= Qp

(
1 + u + u2 + 1 + u + u2,u + u2 + 1 + u + u2 + 0,u + u2 + 1 + u + u2 + 0

)
= Qp (0, 1, 1) ,

which implies bi ◦ bj = 0 for 2 ≤ i ≤ j ≤ q + 1. Hence the code is self-dual. On the other hand,
the binary code generated by GF2 = Π (G) = Bp (1, 0, 1 | 0, 1, 1) generates a self-dual binary code since
Qp (1, 0, 1) Qp (1, 0, 1)

T
= Qp (0, 1, 1). So, GF2 (GF2 )

T
= 0. GF4 = Bp (1, 1, 0 | 0, 1, 1) is a binary matrix

and moreover GF4 (GF4 )
T

= 0 since Qp (1, 1, 0) Qp (1, 1, 0)
T

= Qp (0, 1, 1).

(uG)F4 =

(
uIp+1

0 u1
u1T Qp (u,u, 0)

)
= u (GF4 )

and GF4 (uG)
T
F4 = uGF4 (GF4 )

T
= u0 = 0. Hence by Theorem 3.5 the binary image of the code is self-

dual. In addition, wt (b1) = 8k + 4 and wt (bi) = 3 + (4k + 1) 2 + (4k + 1) 3 = 20k + 8 for 2 ≤ i ≤ q + 1
which implies that the Gray image is Type II.

35



New extremal binary self-dual codes of length 68

An extremal self-dual binary code of length 66 has a weight enumerator in one of the following forms
([2]):

W66,1 = 1 + (858 + 8β) y
12 + (18678 − 24β) y14 + · · · , 0 ≤ β ≤ 778,

W66,2 = 1 + 1690y
12 + 7990y14 + · · ·

and W66,3 = 1 + (858 + 8β) y12 + (18166 − 24β) y14 + · · · , 14 ≤ β ≤ 756.

Recently, 24 new codes in W66,3 are constructed in [6]. For a list of known codes we refer to [6] and
references therein. The code C66,0 in Example 3.14 has weight enumerator β = 0 in W66,1. We complete
this section by giving some examples of QDC codes over the ring R in Table 1. The binary images of two
of the codes are extremal self-dual binary codes with weight enumerators β = 0 and 66 in W66,1.

Table 1. Examples of quadratic double circulant codes over the ring R

p Code over R Gray image remark
3 P3

(
1 + u2,u,1 + u

)
[18,9,4]

2

3 P3
(
0,1 + u2,1 + u + u2

)
[18,9,4]

2

3 B3
(
0,u,1 + u2 | 1 + u + u2,1 + u,1 + u

)
[24,12,6]

2

11 P11
(
1 + u2,u,1 + u

)
[66,33,12]

2
β = 0 in W66,1

11 P11
(
0,1 + u2,1 + u + u2

)
[66,33,12]

2
β = 66 in W66,1

11 B11
(
1,u + u2,1 + u + u2 | 0,1,1

)
[72,36,12]

2
Type II

19 P19
(
1 + u2,u,1 + u

)
[114,57,16]2

19 P19
(
0,1 + u2,1 + u + u2

)
[114,57,16]2

19 B19
(
1,u + u2,1 + u + u2 | 0,1,1

)
[120,60,16]2 Type II

5. New extremal binary self-dual codes of length 68

An efficient method to construct self-dual binary codes of length n+ 2 is to extend a self-dual binary
code of length n. Such an extension method for an arbitrary generator matrix of the code is used in [5].
Such extension methods for binary rings are introduced in [8] and a substantial number of new extremal
binary self-dual codes of length 68 are obtained. In this section, extension is used for extremal self-dual
binary codes of length 66 which were constructed in sections 3 and 4. As a result, we were able to obtain
eight extremal self-dual binary codes of length 68 with new weight enumerators.

The weight enumerator of an extremal binary self-dual code of length 68 is characterized in [2] as
follows:

W68,1 = 1 + (442 + 4β) y
12 + (10864 − 8β) y14 + · · · , 104 ≤ β ≤ 1358,

W68,2 = 1 + (442 + 4β) y
12 + (14960 − 8β − 256γ) y14 + · · ·

where 0 ≤ γ ≤ 11 and 14γ ≤ β ≤ 1870−32γ. Tsai et al. constructed new extremal self-dual binary codes
of lengths 66 and 68 in [10]. Together with the codes obtained in [10] the existence of codes in W68,1 are
known for β =104, 122, 125,. . . ,132, 134,. . . ,168, 170,. . . ,232, 234, 235, 236, 241, 255, 257,. . . ,269, 302,
328,. . . , 336, 338, 339, 345, 347, 355, 401. We construct codes with weight enumerators β =117, 120 and
133 in W68,1 which are listed in Table 2. Recently, new codes in W68,2 are obtained in [6, 8] together

36



A. Kaya, B. Yildiz

with these, codes exists for W68,2 when

γ = 0, β = 44, . . . , 154 or β ∈{2m|m = 17, 20, 88, 102, 119, 136 or 78 ≤ m ≤ 86} ;
γ = 1, β = 60, . . . , 160 or β ∈{2m|m = 27, 28, 29, 95, 96 or 81 ≤ m ≤ 89} ;
γ = 2, β = 65, 68, 71, 77, 159 or β ∈{2m|37 ≤ m ≤ 68, 70 ≤ m ≤ 81} or
β ∈ {2m + 1|42 ≤ m ≤ 69, 71 ≤ m ≤ 77} ;
γ = 3, β = 101, 117, 123, 127, 133, 137, 141, 145, 147, 149, 153, 159, 193 or
β ∈ {2m|m = 44,45,48,50,51,52,54, . . . ,58,61,63, . . . ,66,68, . . . ,72,74,77, . . . ,81,88,94,98} ;
γ = 4, β ∈{2m|m = 51, 55, 58, 60, 61, 62, 64, 65, 67, . . . ,71, 75, . . . , 78, 80} and
γ = 6 with β ∈{2m|m = 69, 77, 78, 79, 81, 88} .

We construct codes with weight enumerators γ = 1 and β =49, 57, 59, 67, 69, 71 and codes with
weight enumerators γ = 2 and β =69, 81 in W68,2 that are given in Table 3 and Example 5.2.

The following is an extension theorem that is true for all commutative rings A of characteristic 2.

Theorem 5.1. ([8]) Let C be a self-dual code over A of length n and G = (ri) be a k × n generator
matrix for C, where ri is the i-th row of G, 1 ≤ i ≤ k. Let c be a unit in A such that c2 = 1 and X be a
vector in An with X ◦X = 1. Let yi = ri ◦X for 1 ≤ i ≤ k. Then the following matrix

G∗ =




1 0 X

y1 cy1 r1
...

...
...

yk cyk rk


 ,

generates a self-dual code C∗ over A of length n + 2.

Example 5.2. When we apply the extension in Theorem 5.1 to C66,0 in Example 3.14 with

X = (000101000011111010001111011100110101001110001101101011001111111111)

in other words, when we consider the code generated by


1 0 X

y1 y1
...

... ϕ (G′)
y33 y33




we obtain an extremal binary self-dual code of length 68 with an automorphism group of order 10 and
weight enumerator γ = 1, β = 49 in W68,2. Note that this is the first extremal binary self-dual code with
this weight enumerator.

In a similar way, the extension is applied to the Gray image of P11
(
1 + u2,u, 1 + u

)
in Table 1 and

seven new extremal self-dual binary codes of length 68 are obtained. These are listed in tables 2 and 3.

Remark 5.3. Recently, in [6] by using a different method codes with weight enumerators γ = 1 and
β = 67, 69, 71 in W68,2 are constructed for the first time in literature. Since the method used here is
different we list them in Table 3.

6. Conclusion

In this work, we applied the quadratic double and bordered double circulant constructions over the
ring R := F2[u]/

(
u3 − 1

)
to obtain extremal binary self-dual codes. Applying extension theorems to the

37



New extremal binary self-dual codes of length 68

Table 2. Extremal binary self-dual codes in W68,1 as extensions of ϕ
(
P11

(
1 + u2,u,1 + u

))
X β

011011011011011001001110100111000100000110010000010000000011100111 117

011011001001011000010101111011101111010101011011010110100011111011 120

011100000001010000000001111011101111001011111010100001100101110100 133

Table 3. Extremal binary self-dual codes in W68,2 as extensions of ϕ
(
P11

(
1 + u2,u,1 + u

))
X γ β

100010010101000101110011011111100101100000000001011010000100111111 1 57

000010001001100101011111101000110001100010010111111111011011110001 1 59

001010111001001111111010010100100010101000001010110101010101001010 1 67

001100101010011110110111001000000111101110100111100101110101001111 1 69

111000000010100001010000101001101110101011100110110011101110001100 1 71

100010101100011000011001101100100101110110101111001011111001101001 2 69

000111000010101101101111110010001000100011010010110101101100110101 2 81

extremal self-dual binary codes of length 66 obtained from the ring R we were able to find eight new
extremal self-dual binary codes of length 68 updating the list of all known such codes. The methods we
have used have proven to be useful in many works in the literature of self-dual codes. We believe they
could be applied to other rings and structures such as Z4.

Acknowledgements

The authors would like to thank Prof. İrfan Şiap for his suggestions and the anonymous referees for
their remarks which improved the manuscript considerably.

References

[1] J. H. Conway, N. J. A. Sloane, A new upper bound on the minimal distance of self-dual codes, IEEE
Trans. Inform. Theory, 36(6), 1319-1333, 1990.

[2] S. T. Dougherty, T. A. Gulliver, M., Harada, Extremal binary self dual codes, IEEE Trans. Inform.
Theory, 43(6), 2036-2047, 1997.

[3] P. Gaborit, Quadratic double circulant codes over fields, Journal of Combinatorial Theory Series A,
97(1), 85-107, 2002.

[4] W.C. Huffman, V. Pless, Fundamentals of error correcting codes, Cambridge University press, 2003.
[5] J.-L. Kim, New extremal self-dual codes of lengths 36, 38 and 58, IEEE Trans. Inf. Theory, 47(1),

386-393, 2001.
[6] A. Kaya, B. Yildiz, İ. Şiap, New extremal binary self-dual codes from F4 + uF4-lifts of quadratic

38



A. Kaya, B. Yildiz

double circulant codes over F4, available online at http://arxiv.org/abs/1405.7147
[7] A. Kaya, B. Yildiz, Binary generator matrices of new extremal self-dual binary codes of length 68,

available online at http://www.fatih.edu.tr/~akaya/binary/68u31.txt
[8] A. Kaya, B. Yildiz, Extension theorems for self-dual codes over rings and new binary self-dual codes,

available online at http://arxiv.org/abs/1404.0195.
[9] E. M. Rains, Shadow Bounds for Self Dual Codes, IEEE Trans. Inf. Theory, 44(1), 134-139, 1998.
[10] H.-P. Tsai, P.-Y. Shih, R.-Y. Wuh, W.-K. Su, C.-H. Chen, Construction of self-dual codes, IEEE

Trans. Inform. Theory, 54(8), 3826-3831, 2008.

39


	Introduction
	Preliminaries
	Projections, lifts and duality conditions
	Quadratic Double Circulant codes over R
	New extremal binary self-dual codes of length 68
	Conclusion
	Acknowledgements
	References