Jon-Lark Kim's Thesis Abstract

Coding theory has been a fascinating topic since the 1940's. It was started by Claude Shannon's paper ``A Mathematical Theory of Communication.'' Coding theory deals with source encoding and error-correcting coding. Source encoding is concerned with how to encode messages with high efficiency, on the other hand, error-correcting coding is about codes which are used to correct or detect errors over a noisy channel. In the latter case fast decoding algorithms are required.

My paper deals with error-correcting codes. In particular I am interested in classical self-dual codes over finite fields and additive quantum error-correcting codes over GF(4) as the latter codes can be constructed using techniques from classical coding theory. Self-dual codes are block codes which can be shown to satisfy the Gilbert-Vashamov bound. The reason that I am interested in self-dual codes is back to my master student years. When I started reading the famous book ``The Theory of Error-Correcting Codes'' by MacWilliams and Sloane and ``Sphere packing, Lattices, and Groups'' by Conway and Sloane, I noted that the theory of self-dual codes had many applications to other mathematical areas such as lattice packings, modular forms, and group theory. Let me give a few examples relating self-dual codes to other areas in mathematics. The famous extremal even unimodular Leech lattice can be constructed from the binary Golay code of length 24. The automorphism group of the binary (ternary) Golay code of length 24 (12) is the Mathieu group M_{24} (M_{12}) which is one of the 26 sporadic finite simple groups. The weight enumerators of self-dual codes are closely related to the theta series of unimodular lattices. So I studied self-dual codes with my thesis advisor Vera Pless when I came to the University of Illinois-Chicago in Fall, 1998.

In this thesis, we construct several new binary or quaternary extremal self-dual codes using a new construction method which I call the building-up method. We also construct new quantum error-correcting codes by generalizing the building-up construction. Besides the costruction of good codes, we demonstrate a hand decoding of the binary Reed-Muller code of length 32 and dimension 16 by projecting it onto the binary Hamming code of length 8 and dimension 4 over GF(4). We study combinatorial designs such as classical t-designs and generalized t-designs in self-dual quantum error-correcting codes. We remark that Chapters 2, 3, 4, and 7 were published, Chapter 6 was accepted and Chapter 5 was submitted.

This thesis consists of the following eight chapters.

Chapter [1]

Chapter [2]
New Binary Extremal Self-Dual Codes

Chapter [3]
New Quaternary Extremal Self-Dual Codes

Chapter [4]
Extremal Additive Self-Dual Quantum Codes

Chapter [5]
New Quantum Error-Correcting Codes from Hermitian Self-Orthogonal Codes

Chapter [6]
Decoding Binary R(2,5) by Hand

Chapter [7]
t-Designs in Additive Codes over GF(4)

Chapter [8]
Conculsion and Future Work

In Chapter 1 we introduce basic definitions and facts in coding theory.

In Chapter 2 we construct new extremal binary self-dual codes of length 36,38, and 58. For lengths 36 and 38, we construct more codes than were previously known and for length 58 we construct several new codes which have previously unknown weight enumerators. I give a construction method which I call the building-up method, which produces many binary self-dual codes from a given smaller length self-dual code. I also show that any nontrivial binary self-dual code can be obtained in this way.

Chapter 3 deals with Hermitian self-dual codes over GF(4). I construct several extremal self-dual codes of length 22 which do not have any non-trivial odd order automorphism. The existence of such codes was left open by W. C. Huffman in 1991. I also give a building-up construction method similar to that given in Chapter 2.

Chapter 4 classifies all extremal self-dual additive quantum error-correcting codes of lengths up to 12, except 10. Quantum error-correcting codes over GF(4) became an interesting topic after Calderbank-Rains-Sloane-Shor's paper (IEEE-IT, 1998) appeared. Additive self-dual quantum codes give a lower bound for the minimum weight of additive quantum codes. Therefore their classification is of great interest.

In Chapter 5 we construct record-breaking pure quantum-error-correcting codes of length 24 with 2 encoded qubits and minimum weight 7 from Hermitian self-orthogonal codes of length 24 with dimension 11 over GF(4). This shows that length n=24 is the smallest length for any known [[n,k,d]] quantum-error-correcting code with k > 1  and d=7.

In Chapter 6 we demonstrate the decoding of the second order Reed-Muller code R(2,5) by hand using the projection onto the Hamming code of length 8 over GF(4) which has a binary representation. After V. Pless showed that the binary Golay code of length 24 can be decoding by using the length 6 Hexacode over GF(4), it has been an open problem whether this idea can be extended to other self-dual codes. We show that this is possible for three binary extremal self-dual [32,16,8] codes, including R(2,5).

In Chapter 7 we study combinatorial t-designs in additive (quantum) codes over GF(4). It is well known that simple t-designs are often obtained from linear codes by the Assmus-Mattson Theorem. However few things were known about t-designs in additive codes over GF(4). There are two kinds of t-designs in the additive codes. One is a classical design with possibly repeated blocks and the other is a generalized t-design introduced by Delsarte in 1972. We show that there exists a simple 3-(11,5,4) design in the shortened dodecacode. This design is inequivalent to the 3-design ``held'' by weight five vectors in the ternary Golay code of length 11. So to the best of our knowledge, our design is new.

In Chapter 8 we summarize what we have done in this thesis and mention some interesting problems.