Designs From Linear Codes

Contents
Preface
Preface to the First Edition
1. Mathematical Foundations
	1.1 The Rings Zn
	1.2 Finite Fields
		1.2.1 Introduction to Finite Fields
		1.2.2 Traces, Norms, and Bases
		1.2.3 Field Automorphisms
		1.2.4 Additive and Multiplicative Characters
		1.2.5 Several Types of Character Sums
		1.2.6 Quadratic Forms over GF(q)
	1.3 Group Algebra
	1.4 Special Types of Polynomials
		1.4.1 Permutation Polynomials over Finite Fields
		1.4.2 Dickson Polynomials over Finite Fields
		1.4.3 Krawtchouk Polynomials
	1.5 Cyclotomy in GF(r)
		1.5.1 Cyclotomy
		1.5.2 Cyclotomy in GF(r)
	1.6 Finite Geometries
		1.6.1 Projective Spaces PG(m, GF(q))
		1.6.2 Affine Spaces AG(m, GF(q))
		1.6.3 Projective Planes
		1.6.4 Desarguesian Projective Planes PG(2, GF(q))
		1.6.5 Central Collineations and Homologies of Projective Planes
		1.6.6 Affine Planes
	1.7 Basics of Group Actions
	1.8 Permutation Groups and Their Actions
		1.8.1 Semilinear Mappings of GF(q)
		1.8.2 General Linear Groups GLm(GF(q))
		1.8.3 General Semilinear Groups ΓLm(GF(q))
		1.8.4 Special Linear Groups SLm(GF(q))
		1.8.5 General Affine Groups GAm(GF(q))
		1.8.6 Special Affine Groups SAm(GF(q))
		1.8.7 Semilinear Affine Groups ΓAm(GF(q))
		1.8.8 Projective General Linear Groups PGLm(GF(q))
		1.8.9 Projective Semilinear Groups PΓLm(GF(q))
		1.8.10 Projective Special Linear Groups PSLm(GF(q))
		1.8.11 A Summary of the Group Actions on GF(q)m and (GF(q)m)
	1.8.12 Permutation Group Actions on GF(qm) and GF(qm)
		1.8.13 Highly Transitive Permutation Groups
		1.8.14 Homogeneous Permutation Groups
	1.9 Planar Functions
		1.9.1 Definitions and Properties
		1.9.2 Some Known Planar Functions
		1.9.3 Planar Functions from Semifields
		1.9.4 Affine Planes from Planar Functions
	1.10 Almost Perfect Nonlinear and Almost Bent Functions
		1.10.1 APN Functions
		1.10.2 AB Functions
	1.11 Periodic Sequences
		1.11.1 The Linear Span
		1.11.2 Correlation Functions
	1.12 Difference Sets
		1.12.1 Fundamentals of Difference Sets
		1.12.2 Divisible and Relative Difference Sets
		1.12.3 Characteristic Sequence of Difference Sets in Zn
		1.12.4 Characteristic Functions of Difference Sets
2. Linear Codes over Finite Fields
	2.1 Linear Codes over GF(q)
	2.2 The MacWilliams Identity and Transform
	2.3 The Pless Power Moments
	2.4 Punctured Codes of a Linear Code
	2.5 Shortened Codes of a Linear Code
	2.6 Extended Code of a Linear Code
	2.7 Augmented Code of a Linear Code
	2.8 Automorphism Groups and Equivalences of Linear Codes
	2.9 Subfield Subcodes
	2.10 Bounds on the Size of Linear Codes
	2.11 Restrictions on Parameters of Linear Codes
	2.12 Bounds on the Size of ConstantWeight Codes
	2.13 Hamming and Simplex Codes, and One-Weight Codes
	2.14 A Trace Construction of Linear Codes
	2.15 Projective Linear Codes and Projective Geometry
	2.16 Generalised HammingWeights of Linear Codes
	2.17 Notes
3. Cyclic Codes over Finite Fields
	3.1 Factorization of xn – 1 over GF(q)
	3.2 Generator and Check Polynomials
	3.3 Idempotents of Cyclic Codes
	3.4 Zeros of Cyclic Codes
	3.5 A Trace Construction of Cyclic Codes over Finite Fields
	3.6 Lower Bounds on the Minimum Distance
	3.7 BCH Codes
		3.7.1 Definition and Basic Properties
		3.7.2 Recent Advances in BCH Codes
	3.8 Quadratic Residue Codes
		3.8.1 Quadratic Residue Codes
		3.8.2 Extended Quadratic Residue Codes
	3.9 Duadic Codes
	3.10 A Combinatorial Approach to Cyclic Codes
	3.11 Notes
4. Designs and Codes
	4.1 Fundamentals of t-Designs
		4.1.1 Incidence Structures
		4.1.2 Incidence Matrices
		4.1.3 Isomorphisms and Automorphisms
		4.1.4 Definition and Properties of t-Designs
		4.1.5 Intersection Numbers of t-Designs
		4.1.6 Related Designs of a t-Design
	4.2 The Classical Codes of t-Designs
		4.2.1 Linear Codes of Incidence Structures
		4.2.2 The Classical Codes of t-Designs
	4.3 The Support Designs of Linear Codes
		4.3.1 The Construction of t-Designs from Linear Codes
		4.3.2 MDS Codes and Complete Designs
		4.3.3 Constructing Designs from Related Binary Codes
	4.4 Designs of Codes with Special Automorphism Groups
	4.5 Designs from Finite Geometries
	4.6 The Codes of Geometric Designs
		4.6.1 The Codes of the Designs of the Affine Geometry
		4.6.2 The Codes of the Designs of the Projective Geometry
	4.7 Spherical Geometry Designs
	4.8 Notes
5. Designs of Binary Reed-Muller Codes
	5.1 Binary Reed-Muller Codes and Their Relatives
	5.2 Designs from the Binary Reed-Muller Codes
		5.2.1 Designs in R2(1,m) and R2(m – 2,m)
		5.2.2 Designs in R2(2,m) and R2(m–3,m)
		5.2.3 Designs in R2(r,m) for 3 ≤ r ≤ m – 4
		5.2.4 Designs from Binary Codes between R2(r,m) and R2(r+1,m)
	5.3 Designs from the Punctured Binary Reed-Muller Codes
	5.4 Notes
6. Affine Invariant Codes and Their Designs
	6.1 Affine-Invariant Extended Cyclic Codes and Their Designs
	6.2 Specific Families of Affine-Invariant Extended Cyclic Codes
		6.2.1 Extended Narrow-Sense Primitive BCH Codes
		6.2.2 Generalised Reed-Muller Codes and Their Designs
		6.2.3 Dilix Codes and Their Designs
		6.2.4 Extended Binary Cyclic Codes with Zeros of the Forms α and α1+2e and Their Designs
	6.3 Another Family of Affine-Invariant Codes and Their Designs
		6.3.1 The Special Case q = 2
		6.3.2 Several Special Cases of 3-Designs
	6.4 Notes
7. Weights in Some BCH Codes over GF(q)
	7.1 A Recall of BCH Codes
	7.2 The Parameters of the Codes C(q,qm–1,δ1,1) and C(q,qm–1,δ1+1,0), where δ1 = (q–1)qm–1 – 1
	7.3 The Parameters of the Codes C(q,qm–1,δ2,1) and C(q,qm–1,δ2+1,0), where δ2 = (q–1)qm–1 – 1 – q (m–1)/2
	7.4 The Parameters of the Codes C(q,qm–1,δ3,1) and C(q,qm–1,δ3+1,0), where δ3 = (q – 1)qm–1 – 1 – q (m+1)/2
	7.5 Weights in C(2,2m–1,δ,1) and Its Dual for δ ϵ {3,5,7}
	7.6 Notes
8. Designs from Four Types of Linear Codes
	8.1 Designs from a Type of Binary Codes with Three Weights
	8.2 An Extended Construction from Almost Bent Functions
	8.3 Designs from a Type of Binary Codes with Five Weights
		8.3.1 The Codes with Five Weights and Their Related Codes
		8.3.2 Infinite Families of 2-Designs from C┴m and Cm
		8.3.3 Infinite Families of 3-Designs from C┴m and C┴m?
		8.3.4 Two Families of Binary Cyclic Codes with the Weight Distribution of Table 8.2
	8.4 Infinite Families of Designs from a Type of Ternary Codes
	8.5 Infinite Families of Designs from Another Type of Ternary Codes
		8.5.1 Conjectured Infinite Families of 2-Designs
		8.5.2 A Class of Ternary Cyclic Codes of Length 3m–1/2
		8.5.3 Shortened Codes and Punctured Codes from C(E)
		8.5.4 Steiner Systems and 2-Designs from C(E)
	8.6 Notes
9. Designs from BCH Codes
	9.1 A General Theorem on Designs from Primitive BCH Codes
	9.2 Designs from the Primitive BCH Codes C(2,2m–1,δ2,1)
	9.3 Designs from the Primitive BCH Codes C(q,qm–1,δ2,1) for Odd Prime q
	9.4 Designs from the Primitive BCH Codes C(2,2m–1,δ3,1)
	9.5 Designs from the Primitive BCH Codes C(q,qm–1,δ3,1) for Odd q
	9.6 Designs from C(2,2m–1,5,1) and C(2,2m–1,5,1)┴ for Even m ≥ 4
	9.7 Designs from the Primitive BCH Codes C(q,qm–1,3,1) for q ≥ 3
	9.8 Designs from Nonprimitive BCH Codes
	9.9 Notes
10. Designs from Codes with Regularity
	10.1 Packing and Covering Radii
	10.2 The Characteristic Polynomial of a Code
	10.3 Regular Codes and Their Designs
	10.4 Perfect Codes
	10.5 Designs in Perfect Codes
		10.5.1 Theory of Designs in Perfect Codes
		10.5.2 Designs in the [23,12,7] Golay Binary Code
		10.5.3 Designs in the [11,6,5] Golay Ternary Code
		10.5.4 Designs in the Hamming and Simplex Codes
	10.6 Designs in Uniformly Packed Codes
		10.6.1 Definitions, Properties and General Results
		10.6.2 Designs in Uniformly Packed Binary Codes
11. Designs from QR and Self-Dual Codes
	11.1 Self-Dual Codes and Their Designs
		11.1.1 Definition and Existence
		11.1.2 Weight Enumerators of Self-Dual Codes
		11.1.3 Extremal Self-Dual Codes and Their Designs
	11.2 Designs from Extended Quadratic Residue Codes
		11.2.1 Infinite Families of 2-Designs and 3-Designs
		11.2.2 Sporadic 5-Designs from Self-Dual Codes
	11.3 Pless Symmetry Codes and Their Designs
	11.4 Other Self-Dual Codes Holding t-Designs
12. Designs from Arc and MDS Codes
	12.1 Arcs, Caps, Conics, Hyperovals and Ovals in PG(2,GF(q))
	12.2 Hyperovals in PG(2,GF(q)) and [q+2,3,q] MDS Codes
	12.3 Oval Polynomials on GF(2m)
		12.3.1 Basic Properties of Oval Polynomials
		12.3.2 Translation Oval Polynomials
		12.3.3 Segre and Glynn Oval Polynomials
		12.3.4 Cherowitzo Oval Polynomials
		12.3.5 Payne Oval Polynomials
		12.3.6 Subiaco Oval Polynomials
	12.4 A Family of Hyperovals from Extended Cyclic Codes
	12.5 Hyperoval Designs
	12.6 Hadamard Designs from Hyperovals
	12.7 Maximal Arc Codes and Their Designs
	12.8 A Family of Extended Cyclic Codes and Their Designs
13. Designs from Oviod Codes
	13.1 Ovoids in PG(3,GF(q)) and Their Properties
	13.2 Ovoids in PG(3,GF(q)) and [q2+1,4,q2–q] Codes
	13.3 A Family of Cyclic Codes with Parameters [q2+1,4,q2–q]
	13.4 Designs from Ovoid Codes over GF(q)
	13.5 Ovoids, Codes, Designs and Inversive Planes
	13.6 Designs Held in Punctured and Shortened Ovoid Codes
14. Quasi-Symmetric Designs from Bent Codes
	14.1 Derived and Residual Designs of Symmetric Designs
	14.2 Symmetric and Quasi-Symmetric SDP Designs
	14.3 The Roadmap of the Remaining Sections
	14.4 Bent Functions
	14.5 Symmetric 2-(2m,2m–1 ???? 2m–22 ,2m–2 – 2m–22 ) Designs and Their Codes
	14.6 Symmetric 2-(2m,2m–1 – 2m–22, 2m–2 – 2m–22) SDP Designs
	14.7 Derived and Residual Designs of Symmetric SDP Designs
	14.8 A General Construction of Linear Codes with Bent Functions
	14.9 Infinite Families of 2-Designs from Bent Codes
	14.10 Notes
15. Almost MDS Codes and Their Designs
	15.1 Almost MDS Codes
	15.2 Near MDS Codes
	15.3 Designs from Near MDS Codes
		15.3.1 A General Theorem about t-Designs from NMDS Codes
		15.3.2 Infinite Families of NMDS Codes Holding Infinite Families of t-Designs
		15.3.3 An Infinite Family of Near MDS Codes Holding 4-Designs
			15.3.3.1 Combinatorial t-Designs Constructed with Some Elementary Symmetric Polynomials
			15.3.3.2 Infinite Families of BCH Codes Holding t-Designs for t ϵ {3,4}
	15.4 Sporadic Designs from Near MDS Codes
	15.5 Designs from Almost MDS Codes
16. Beyond the Assmus-Mattson Theorem
	16.1 Introduction of Notation and Notions for This Chapter
	16.2 The Assmus-Mattson Theorem in the Languge of This Chapter
	16.3 New Notation of Intersection Numbers of Designs
	16.4 Shortened and Punctured Codes of Linear Codes Supporting t-Designs
		16.4.1 General Results for Shortened and Punctured Codes of Linear Codes Supporting t-Designs
		16.4.2 Punctured and Shortened Codes of a Family of Binary Codes
		16.4.3 Punctured and Shortened Codes of Another Family of Binary Codes
	16.5 Characterizations of Linear Codes Supporting t-Designs via Shortened and Punctured Codes
	16.6 A Generalization of the Assmus-Mattson Theorem
		16.6.1 The Generalization of the Assmus-Mattson Theorem
		16.6.2 The Generalized Assmus-Mattson Theorem versus the Original
	16.7 Some 2-Designs and Differentially δ-Uniform Functions
	16.8 Notes
Appendix A Sporadic Designs from Linear Codes
	A.1 Designs from Cyclic Codes of Length 17 over GF(4)
	A.2 Steiner Systems from Cyclic Codes of Length 17 over GF(16)
	A.3 Designs from Cyclic Codes of Length 23 over GF(3)
	A.4 Designs from Cyclic Codes of Length 29 over GF(4)
Appendix B Designs from Binary Codes with Regularities
	B.1 Four Fundamental Parameters of Codes
	B.2 Designs from Codes with Regularity
		B.2.1 Designs from Codes When s ≤ d′
		B.2.2 Designs from Nonlinear Codes When s′ ≤ d
Appendix C Exercises on Mathematical Foundations
	C.1 Modular Arithmetic
	C.2 Elementary Number Theory
	C.3 Groups, Rings and Fields
	C.4 Polynomials over a Field F
	C.5 A Constructive Introduction to Finite Fields
Bibliography
Notation and Symbols
Index