The doctoral dissertations of the former Helsinki University of Technology (TKK) and Aalto University Schools of Technology (CHEM, ELEC, ENG, SCI) published in electronic format are available in the electronic publications archive of Aalto University - Aaltodoc.
Aalto

Perfect Binary Codes: Classification and Properties

Olli Pottonen

Dissertation for the degree of Doctor of Science in Technology to be presented with due permission of the Faculty of Electronics, Communications and Automation for public examination and debate in Auditorium S4 at Helsinki University of Technology (Espoo, Finland) on the 21st of August, 2009, at 12 noon.

Overview in PDF format (ISBN 978-952-248-011-8)   [254 KB]
Dissertation is also available in print (ISBN 978-952-248-010-1)

Abstract

An r-perfect binary code is a subset of ℤ2n such that for any word, there is a unique codeword at Hamming distance at most r. Such a code is r-error-correcting. Two codes are equivalent if one can be obtained from the other by permuting the coordinates and adding a constant vector. The main result of this thesis is a computer-aided classification, up to equivalence, of the 1-perfect binary codes of length 15.

In an extended 1-perfect code, the neighborhood of a codeword corresponds to a Steiner quadruple system. To utilize this connection, we start with a computational classification of Steiner quadruple systems of order 16. This classification is also used to establish the nonexistence of Steiner quintuple systems S(4, 5, 17).

The classification of the codes is used for computational examination of their properties. These properties include occurrences of Steiner triple and quadruple systems, automorphisms, ranks, structure of i-components and connections to orthogonal arrays and mixed perfect codes.

It is also proved that extended 1-perfect binary codes are equivalent if and only if their minimum distance graphs are isomorphic.

This thesis consists of an overview and of the following 6 publications:

  1. Petteri Kaski, Patric R. J. Östergård, and Olli Pottonen. 2006. The Steiner quadruple systems of order 16. Journal of Combinatorial Theory, Series A, volume 113, number 8, pages 1764-1770.
  2. Patric R. J. Östergård and Olli Pottonen. 2007. There exist Steiner triple systems of order 15 that do not occur in a perfect binary one-error-correcting code. Journal of Combinatorial Designs, volume 15, number 6, pages 465-468.
  3. Patric R. J. Östergård and Olli Pottonen. 2008. There exists no Steiner system S(4, 5, 17). Journal of Combinatorial Theory, Series A, volume 115, number 8, pages 1570-1573.
  4. Patric R. J. Östergård and Olli Pottonen. The perfect binary one-error-correcting codes of length 15: Part I—Classification. IEEE Transactions on Information Theory, to appear. © 2009 IEEE. By permission.
  5. Patric R. J. Östergård, Olli Pottonen, and Kevin T. Phelps. 2009. The perfect binary one-error-correcting codes of length 15: Part II—Properties. Espoo, Finland. Helsinki University of Technology, Department of Communications and Networking, Report 2/2009. © 2009 by authors.
  6. Ivan Yu. Mogilnykh, Patric R. J. Östergård, Olli Pottonen, and Faina I. Solov'eva. 2009. Reconstructing extended perfect binary one-error-correcting codes from their minimum distance graphs. IEEE Transactions on Information Theory, volume 55, number 6, pages 2622-2625. © 2009 IEEE. By permission.

Errata of publication 5

Keywords: classification, exact cover problem, extended perfect code, isomorph rejection, minimum distance graph, perfect code, Steiner system

This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

© 2009 Helsinki University of Technology

Last update 2011-05-26