Perfect binary codes: classification and properties
Loading...
Journal Title
Journal ISSN
Volume Title
Doctoral thesis (article-based)
Checking the digitized thesis and permission for publishing
Instructions for the author
Instructions for the author
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Author
Date
2009
Major/Subject
Mcode
Degree programme
Language
en
Pages
Verkkokirja (254 KB, 19 s.)
Series
Report.
Helsinki University of Technology, Department of Communications and Networking,
3/2009
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.Description
Keywords
classification, exact cover problem, extended perfect code, isomorph rejection, minimum distance graph, perfect code, Steiner system
Other note
Parts
- [Publication 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.
- [Publication 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.
- [Publication 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.
- [Publication 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.
- [Publication 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.
- [Publication 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 file]: Errata of publication 5
