Designs from Linear Codes

The following sections are included:

• Preface
• Contents

It is impossible to introduce combinatorial designs and linear codes without basic tools in certain mathematical areas. In this chapter, we give a brief introduction to cyclotomy, finite geometry, group actions, group algebra, finite fields, special functions, and sequences, which are the foundations of other chapters.

This chapter introduces the basics of linear codes over finite fields. Fundamental results about linear codes will be summarized. Some of the results presented in this chapter will not be proved. The reader may find out a proof of such theorems and lemmas in Huffman and Pless (2003)[Chapters 1, 2] or work out a proof.

A linesr code C is called a cyclic code if c = (c₀, c₁, …, c_n−1) ∊ C implies (c_n−1, c₀, c₁, …, c_n−2) ∊ C. As a subclass of linear codes, cyclic codes have wide applications in consumer electronics, data storage systems, and communication systems as they have some efficient encoding and decoding algorithms. In this chapter, we introduce the basic theory of cyclic codes over finite fields without providing a proof in many cases. We refer the reader to Huffman and Pless (2003)[Chapter 4] for a proof of such result.

Designs and codes are companions. On one hand, a design may give many codes. On the other hand, a code may yield many designs. The objective of this chapter is to introduce basic connections between designs and codes, which will lay a foundation for subsequent chapters.

In this chapter, we first treat binary Reed-Muller codes in details and then study their designs. Binary Reed-Muller codes are named after Reed (1954) and Muller (1954). These codes are of special interest, as they hold exponentially many 3-designs.

Throughout this chapter, let n = q^m − 1, where m is a positive integer. A cyclic code of length n over GF(q) is said to be primitive. In this chapter, we treat a special type of primitive cyclic codes and their extended codes over GF(q), which are called affine-invariant codes. We will also deal with the designs held in some affine-invariant codes.

BCH codes are an important class of cyclic codes and were treated in Section 3.6. In this chapter, we introduce several families of BCH codes whose weight distributions are known. Some of these codes will be employed to construct t-designs in subsequent chapters.

In this chapter, we will present many infinite families of 2-designs and 3-designs, which are derived from three types of binary codes and a type of ternary codes whose weight distributions are of special forms. We do not need the description of the codes, but only their weight distributions. In this case, we have to make full use of the Assmus-Mattson Theorem (i.e., Theorem 4.14 and Corollary 4.2), as the automorphism groups of such codes could not be determined with only the knowledge of the weight distribution. The materials presented in this chapter are from Ding (2018d) and Ding and Li (2017).

In this chapter, we first introduce a general theorem about 2-designs from narrow-sense primitive BCH codes and then determine the parameters of 2-designs from some classes of binary primitive BCH codes. It should be noted that the Assmus-Mattson Theorem does not apply to most of the codes in this chapter. We have to use the automorphism group of these codes, in order to prove that they hold designs. The materials presented in this chapter are mainly from Ding and Zhou (2017).

In this chapter, we will introduce several types of codes with regularity and deal with their support designs. These codes include perfect codes, quasi-perfect codes, uniformly packed codes, and t-regular codes. The codes dealt with in this chapter may be linear or nonlinear. The materials in Sections 10.2, 10.3 and 10.6 come from Goethals and Van Tilborg (1975).

Self-dual codes are fascinating in both theory and application. The objective of this chapter is to present a summary of results about self-dual codes and extended quadratic residue codes as well as their designs. We restrict ourselves to only theories of these codes that are related to t-designs, as self-dual codes form a huge topic with hundreds of references.

MDS codes do hold support t-designs for large t. But these designs are complete and not interesting. Nevertheless, certain MDS codes over GF(2^m) yield hyperovals in PG(2,GF(2^m)), and such hyperovals give rise to two types of 2-designs and 3-designs, which are called hyperoval designs. This demonstrates that certain linear codes can be employed to construct designs in other ways. Maximal arcs are an interesting topic of study in finite geometries. They give interesting two-weight codes, which hold nice 2-designs. The objective of this chapter is to present these designs. Although all the designs treated in this chapter are from linear codes, some of them are support designs of linear codes, others are not support designs.

In the preceding chapter, we treated designs from some MDS codes and hyperovals, and observed a close connection between some MDS codes and hyperovals in PG(2,GF(2^e)). In this chapter we will deal with ovoids in PG(3,GF(q)), their codes and 3-designs held in these codes. We will see that ovoids in PG(3,GF(q)) are equivalent to [q²+1,4,q²−q] codes over GF(q).

Designs are often associated with optimal codes. Symmetric designs with the symmetric difference property are a special type of symmetric designs and related to Hadamard difference sets and a type of linear codes. Their derived and residual designs are quasi-symmetric and have a close connection with a family of linear codes meeting the Grey-Rankin bound. The objectives of this chapter is to give a coding-theoretic construction of all quasi-symmetric SDP designs. It will be seen that the linear codes holding quasi-symmetric designs are optimal with respect to the Grey-Rankin bound (see Theorem 2.29).

In some preceding chapters, we considered designs held in linear codes over finite fields. In this appendix, we consider support designs held in codes which may be linear or nonlinear. Most of the results presented in this appendix were developed in Delsarte (1973a), and results for binary codes were extended and strengthened in MacWilliams and Sloane (1977)[Chapter 6, Section 3]. We will summarize the major results without giving a proof. The reader is referred to Delsarte (1973a) and MacWilliams and Sloane (1977)[Chapter 6, Section 3] for a detailed proof. All the codes mentioned in this appendix are binary.

The following sections are included:

• Bibliography
• Index