A survey of methods for constructing nonlinear perfect binary codes

A. M. Romanov

Diskretnyj analiz i issledovanie operacij, Tome 13 (2006) no. 4, pp. 60-88.

Résumé

The theory of perfect codes is an area at the juncture of coding theory and design theory which is rather hard to explore. Linear perfect codes were constructed by M. Golay and R. Hamming in the end of the 1940s. Nonlinear perfect codes were discovered by Yu. L. Vasil'ev in 1961. At present, many different methods are known for constructing perfect codes. This article presents a survey of the methods for constructing nonlinear perfect binary codes alongside some open questions of the theory of perfect codes.

Bibliographie

[1] Avgustinovich S. V., Solovëva F. I., “O nesistematicheskikh sovershennykh dvoichnykh kodakh”, Problemy peredachi informatsii, 32:3 (1996), 47–50 | MR | Zbl

[2] Avgustinovich S. V., Solovëva F. I., “Postroenie sovershennykh dvoichnykh kodov posledovatelnymi sdvigami $\tilde{\alpha}$-komponent”, Problemy peredachi informatsii, 33:3 (1997), 15–21 | MR | Zbl

[3] Avgustinovich S. V., Solovëva F. I., Kheden U., “Sovershennye kody polnogo ranga s yadrami bolshikh razmernostei”, Diskret. analiz. i issled. operatsii. Ser. 1, 8:4 (2001), 3–8 | MR | Zbl

[4] Avgustinovich S. V., Solovëva F. I., Kheden U., “O probleme rangov i yader sovershennykh kodov”, Problemy peredachi informatsii, 39:4 (2003), 30–34 | MR | Zbl

[5] Vasilev Yu. L., “O negruppovykh plotno upakovannykh kodakh”, Problemy kibernetiki, no. 8, Fizmatgiz, M., 1962, 337–339 | MR

[6] Vasilev Yu. L., “O sravnenii slozhnosti tupikovykh i minimalnykh diz'yunktivnykh normalnykh form”, Problemy kibernetiki, no. 10, Fizmatgiz, M., 1963, 5–61 | MR

[7] Vasilev Yu. L., Solovëva F. I., “Kodoobrazuyuschie faktorizatsii $n$-mernogo edinichnogo kuba i sovershennykh dvoichnykh kodov”, Problemy peredachi informatsii, 33:1 (1997), 64–74 | MR

[8] Zinovev V. A., Kody dlya korrelyatsionnoi mnogoadresnoi selektsii, Dis. $\dots$ kand. tekhn. nauk, M., 1970

[9] Zinovev V. A., “Obobschënnye kaskadnye kody”, Problemy peredachi informatsii, 12:1 (1976), 5–15 | MR

[10] Zinovev V. A., Kombinatornye metody postroeniya i analiza nelineinykh korrektiruyuschikh kodov, Dis. $\dots$ d-ra fiz.-mat. nauk, M., 1988

[11] Zinovev V. A., Zinovev D. V., “Dvoichnye rasshirennye sovershennye kody dliny 16, postroennye obobschënnoi kaskadnoi konstruktsiei”, Problemy peredachi informatsii, 38:4 (2002), 56–84 | MR

[12] Zinovev V. A., Zinovev D. V., “Dvoichnye sovershennye kody dliny 15, postroennye obobschënnoi kaskadnoi konstruktsiei”, Problemy peredachi informatsii, 40:1 (2004), 27–39 | MR

[13] Zinovev V. A., Zinovev D. V., “Dvoichnye rasshirennye sovershennye kody dliny 16 ranga 14”, Problemy peredachi informatsii, 42:2 (2006), 63–80 | MR

[14] Zinovev V. A., Leontev V. K., “Nesuschestvovanie sovershennykh kodov nad polyami Galua”, Problemy upravleniya i teorii informatsii, 2:2 (1973), 123–132 | MR

[15] Zinovev V. A., Lobstein A. S., “Ob obobschënnykh kaskadnykh konstruktsiyakh sovershennykh dvoichnykh nelineinykh kodov”, Problemy peredachi informatsii, 36:4 (2000), 59–73 | MR

[16] Krotov D. S., “Nizhnie otsenki chisla $m$-kvazigrupp poryadka 4 i chisla sovershennykh dvoichnykh kodov”, Diskret. analiz. i issled. operatsii. Ser. 1, 7:2 (2000), 47–53 | MR | Zbl

[17] Krotov D. S., “Kombinirovannaya konstruktsiya sovershennykh dvoichnykh kodov”, Problemy peredachi informatsii, 36:4 (2000), 74–79 | MR | Zbl

[18] Los A. V., “Postroenie sovershennykh $q$-ichnykh kodov svitchingami prostykh komponent”, Problemy peredachi informatsii, 42:1 (2006), 34–42 | MR | Zbl

[19] Mak-Vilyams F. Dzh., Sloen N. Dzh. A., Teoriya kodov, ispravlyayuschikh oshibki, Svyaz, M., 1979

[20] Malyugin S. A., “Nesistematicheskie sovershennye dvoichnye kody”, Diskret. analiz. i issled. operatsii. Ser. 1, 8:1 (2001), 55–76 | MR | Zbl

[21] Malyugin S. A., O klassakh ekvivalentnosti sovershennykh dvoichnykh kodov dliny 15, Preprint RAN, Sib. otd-nie. Institut matematiki. No 138, Novosibirsk, 2004, 34 pp.

[22] Malyugin S. A., “O perechislenii neekvivalentnykh sovershennykh dvoichnykh kodov dliny 15 i ranga 15”, Diskret. analiz. i issled. operatsii. Ser. 1, 13:1 (2006), 77–98 | MR

[23] Malyugin S. A., Romanov A. M., “O razbieniyakh kodov Khemminga na neperesekayuschiesya komponenty”, Diskret. analiz. i issled. operatsii. Ser. 1, 9:1 (2002), 42–48 | MR | Zbl

[24] Romanov A. M., “O postroenii sovershennykh nelineinykh dvoichnykh kodov inversiei simvolov”, Diskret. analiz. i issled. operatsii. Ser. 1, 4:1 (1997), 46–52 | MR | Zbl

[25] Romanov A. M., “O nesistematicheskikh sovershennykh kodakh dliny 15”, Diskret. analiz. i issled. operatsii. Ser. 1, 4:4 (1997), 75–78 | MR | Zbl

[26] Romanov A. M., “Sovershennye dvoichnye kody s trivialnym yadrom”, Diskret. analiz. i issled. operatsii. Ser. 1, 7:2 (2000), 71–74 | MR | Zbl

[27] Romanov A. M., “O razbieniyakh $q$-ichnykh kodov Khemminga na neperesekayuschiesya komponenty”, Diskret. analiz. i issled. operatsii. Ser. 1, 11:3 (2004), 80–87 | MR | Zbl

[28] Solovëva F. I., “O dvoichnykh negruppovykh kodakh”, Metody diskretnogo analiza v izuchenii bulevykh funktsii i grafov, Sb. nauch. tr., no. 37, In-t matematiki, Novosibirsk, 1981, 65–76 | MR

[29] Solovëva F. I., Tochnye granitsy svyaznosti kodoobrazuyuschikh d.n.f., Preprint AN SSSR, Sib. otd-nie. Institut matematiki. No 10, Novosibirsk, 1990, 15 pp.

[30] Forni D., Kaskadnye kody, Mir, M., 1970

[31] Avgustinovich S. V., Heden O., Solov'eva F. I., “The classification of some perfect codes”, Designs, Codes and Cryptog., 31:3 (2004), 313–318 | DOI | MR | Zbl

[32] Avgustinovich S. V., Lobstein A., Solov'eva F. I., “Intersection matrices for partitions by binary perfect codes”, IEEE Trans. on Inform. Theory, 47:4 (2001), 1621–1624 | DOI | MR | Zbl

[33] Bauer H., Ganter B., Hergert F., “Algebraic techniques for nonlinear codes”, Combinatorica, 3:1 (1983), 21–33 | DOI | MR | Zbl

[34] Cohen G., Honkala I., Litsyn S., Lobstein A., Covering codes, Elsevier, North Holland, 1998 | MR

[35] Cohen G., Litsyn S., Vardy A., Zemor G., “Tilings of binary spaces”, SIAM J. Discrete Math., 9:3 (1996), 393–412 | DOI | MR | Zbl

[36] Delsarte P., Goethals J. M., “Unrestricted codes with the Golay parameters are unique”, Discrete Math., 12:3 (1975), 211–224 | DOI | MR | Zbl

[37] Gibbons P. B., Computing techniques for the construction and analysis of block designs, Ph. D. Thesis, Department of Computer Science, University of Toronto, 1976

[38] Hamming R. W., “Error detecting and error correcting codes”, Bell System Tech. J., 29:2 (1950), 147–160 | MR

[39] Heden O., “A new construction of group and nongroup perfect codes”, Inform. and Control, 34:4 (1977), 314–323 | DOI | MR | Zbl

[40] Heden O., “A binary perfect code of length 15 and codimension 0”, Designs, Codes and Cryptog, 4:3 (1994), 213–220 | DOI | MR | Zbl

[41] Heden O., “A full rank perfect code on length 31”, Designs, Codes and Cryptog, 38:1 (2006), 125–129 | DOI | MR | Zbl

[42] Hergert F., Combinatorial Theory, Lectures Notes in Math., 969, Springer, Berlin, 1982, 176–186 | MR

[43] Etzion T., Vardy A., “Perfect binary codes: constructions, properties, and enumeration”, IEEE Trans. on Inform. Theory, 40:3 (1994), 754–763 | DOI | MR | Zbl

[44] Etzion T., Vardy A., “On perfect codes and tilings: problems and solution”, SIAM J. Discrete Math., 11:2 (1998), 205–253 | DOI | MR

[45] Kaski P., Östergård P. R. J., Pottonen O., “The Steiner quadruple systems of order 16”, J. Combin. Theory. Ser. A., 113:8 (2006), 1764–1770 | DOI | MR | Zbl

[46] Limbos M., “Projective embeddings of small “Steiner triple systems””, Ann. Discrete Math., 7 (1980), 151–173 | DOI | MR | Zbl

[47] Lobstein A. S., Zinoviev V. A., “On new perfect binary nonlinear codes”, Applicable Algebra in Engineering, Communication and Computing, 8:5 (1997), 415–420 | DOI | MR | Zbl

[48] Mollard M., “A generalized parity function and its use in construction of perfect codes”, SIAM J. Algebraic Discrete Methods, 7:1 (1986), 113–115 | DOI | MR | Zbl

[49] Östergård P. R. J., Pottonen O., “The exist Steiner triple systems of order 15 that do not occur in a perfect binary one-error-correcting code”, J. of Combinatorial Designs (to appear)

[50] Östergård P. R. J., Vardy A., “Resolving the existence of full-rank tilings of binary Hamming spases”, SIAM J. Discrete Math., 18:2 (2004), 382–387 | DOI | MR | Zbl

[51] Phelps. K. T., “A combinatorial construction of perfect codes”, SIAM J. Algebraic Discrete Methods, 4:3 (1983), 398–403 | DOI | MR | Zbl

[52] Phelps K. T., “A general product construction for error correcting codes”, SIAM J. Algebraic Discrete Methods, 5:2 (1984), 224–228 | DOI | MR | Zbl

[53] Phelps K. T., “An enumeration of 1-perfect binary codes”, Australas. J. Combin., 21 (2000), 287–298 | MR | Zbl

[54] Phelps K. T., “Combinatorial designs and perfect codes”, Electronic Notes in Discrete Math., 10 (2001), 15 p | MR

[55] Phelps K. T., LeVan M., “Kernels of nonlinear Hamming codes”, Designs Codes and Cryptogr, 6:3 (1995), 247–257 | DOI | MR | Zbl

[56] Phelps K. T., LeVan M., “Non-systematic perfect codes”, SIAM J. Discrete Math., 12:1 (1999), 27–34 | DOI | MR | Zbl

[57] Phelps K. T., LeVan M., “Switching equivalence classes of perfect codes”, Designs Codes and Cryptogr., 16:2 (1999), 179–184 | DOI | MR | Zbl

[58] Phelps K. T., Rif`a J., Villanueva M., “Kernels and $p$-kernels of $p^r$-ary 1-perfect codes”, Designs Codes and Cryptogr., 37:2 (2005), 243–261 | DOI | MR

[59] Phelps K. T., Villanueva M., “Ranks of $q$-ary 1-perfect codes”, Designs Codes and Cryptogr., 27:1–2 (2002), 139–144 | DOI | MR | Zbl

[60] Phelps K. T., Villanueva M., “On perfect codes: rank and kernel”, Designs Codes and Cryptogr., 27:3 (2002), 183–194 | DOI | MR | Zbl

[61] Pless V., “On the uniqueness of the Golay codes”, J. Combin. Theory, 5:3 (1968), 215–228 | DOI | MR | Zbl

[62] Rif`a J., “Well-ordered Steiner triple systems and 1-perfect partitions of the $n$-cube”, SIAM J. Discrete Math., 12:1 (1999), 35–47 | DOI | MR | Zbl

[63] Rif`a J., Vardy A., “On partitions of space into perfect codes”, III French-IsraeliWorkshop on Coding Theory and Information Integrity (Ein Boqeq, Dead Sea, Israel, October 1997)

[64] Schönheim J., “On linear and nonlinear single-error-correcting $q$-nary perfect codes”, Inform. and Control., 12:1 (1968), 23–26 | DOI | MR | Zbl

[65] Solov'eva F. I., “Structure of $i$-components of perfect binary codes”, Discrete Applied Math., 111:1–2 (2001), 189–197 | DOI | MR

[66] Solov'eva F. I., On perfect codes and related topics, Lecture Note, 13, Combinatorial and Computational Mathematics Center. Pohang University of Science and Technology, Korea, Pohang, 2004, 80 pp.

[67] Tietäväinen A., “On the nonexistence of perfect codes over finite fields”, SIAM J. Applied Math., 24:1 (1973), 88–96 | DOI | MR | Zbl

[68] van Lint J. H., Introduction to coding theory, Springer-Verlag, New York-Berlin, 1982

[69] White H. S., Cole F. N. Cummings L. D., “Complete classification of triad systems on fifteen elements”, Memoirs Nat. Acad. Sci. USA, 14 (1919), 1–89