Abstract
This work is a survey on completely regular codes. Known properties, relations with other combinatorial structures, and construction methods are considered. The existence problem is also discussed, and known results for some particular cases are established. In addition, we present several new results on completely regular codes with covering radius ρ = 2 and on extended completely regular codes.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Change history
16 October 2019
Abstract���We correct mistakes in the formulations of Theorem 19 and Proposition 17 of the original article, published in vol. 55, no. 1, 1���45.
References
Shapiro, G.S. and Slotnik, D.L., On the Mathematical Theory of Error-Correcting Codes, IBM J. Res. Develop., 1959, vol. 3, no. 1, pp. 25–34.
Semakov, N.V., Zinoviev, V.A., and Zaitsev, G.V., Uniformly Packed Codes, Probl. Peredachi Inf., 1971, vol. 7, no. 1, pp. 38–50 [Probl. Inf. Transm. (Engl. Transl.), 1971, vol. 7, no. 1, pp. 30–39].
Delsarte, P., An Algebraic Approach to the Association Schemes of Coding Theory, Philips Res. Rep. Suppl., 1973, no. 10.
Goethals, J.-M. and van Tilborg, H.C.A., Uniformly Packed Codes, Philips Res. Rep., 1975, vol. 30, pp. 9–36.
van Tilborg, H.C.A., Uniformly Packed Codes, PhD Thesis, Tech. Univ. Eindhoven, The Netherlands, 1976.
Solé, P., Completely Regular Codes and Completely Transitive Codes, Discrete Math., 1990, vol. 81, no. 2, pp. 193–201.
Giudici, M., Completely Transitive Codes in Hamming Graphs, PhD Thesis, Univ. of Western Australia, Perth, Australia, 1998.
Giudici, M. and Praeger, C.E., Completely Transitive Codes in Hamming Graphs, European J. Combin., 1999, vol. 20, no. 7, pp. 647–662.
Gillespie, N.I. and Praeger, C.E., New Characterisations of the Nordstrom–Robinson Codes, Bull. London Math. Soc., 2017, vol. 49, no. 2, pp. 320–330.
Brouwer, A.E., Cohen, A.M., and Neumaier, A., Distance-Regular Graphs, Berlin: Springer, 1989.
van Dam, E.R., Koolen, J.H., and Tanaka, H., Distance-Regular Graphs, Electron. J. Combin., 2016, Dynamic Survey DS22 (156 pp.).
Koolen, J., Krotov, D., and Martin, B., Completely Regular Codes, 2016. Available at https://sites.google.com/site/completelyregularcodes.
Koolen, J.H., Lee, W.S., Martin, W.J., and Tanaka, H., Arithmetic Completely Regular Codes, Discrete Math. Theor. Comput. Sci., 2016, vol. 17, no. 3, pp. 59–76.
Tietäväinen, A., On the Nonexistence of Perfect Codes over Finite Fields, SIAM J. Appl. Math., 1973, vol. 24, no. 1, pp. 88–96.
Zinoviev, V.A. and Leont’ev, V.K., On Non-existence of Perfect Codes over Galois Fields, Probl. Upravlen. Teor. Inform., 1973, vol. 2, no. 2, pp. 123–132 [Probl. Control Inf. Theory (Engl. Transl.), 1973, vol. 2, no. 2, pp. 16–24].
Borges, J. and Rifà, J., On the Nonexistence of Completely Transitive Codes, IEEE Trans. Inform. Theory, 2000, vol. 46, no. 1, pp. 279–280.
Borges, J., Rifà, J., and Zinoviev, V., Nonexistence of Completely Transitive Codes with Error-Correcting Capability e < 3, IEEE Trans. Inform. Theory, 2001, vol. 47, no. 4, pp. 1619–1621.
Neumaier, A., Completely Regular Codes, Discrete Math., 1992, vol. 106/107, pp. 353–360.
Borges, J., Rifà, J., and Zinoviev, V.A., On Non-antipodal Binary Completely Regular Codes, Discrete Math. 2008, vol. 308, no. 16, pp. 3508–3525.
Avgustinovich, S.V., Krotov, D.S., and Vasil’eva, A.Yu., Completely Regular Codes in the Infinite Hexagonal Grid, Sib. Electron. Mat. Izv., 2016, vol. 13, pp. 987–1016. Available at http://semr.math.nsc.ru/v13/p987-1016.pdf.
MacWilliams, F.J. and Sloane, N.J.A., The Theory of Error-Correcting Codes, Amsterdam: North-Holland, 1977. Translated under the title Teoriya kodov, ispravlyayushchikh oshibki, Moscow: Svyaz’, 1979.
Brouwer, A.E., A Note on Completely Regular Codes, Discrete Math., 1990, vol. 83, no. 1, pp. 115–117.
Lindström, K., All Nearly Perfect Codes Are Known, Inform. Control, 1977, vol. 35, no. 1, pp. 40–47.
Bassalygo, L.A., Zaitsev, G.V., and Zinoviev, V.A., Uniformly Packed Codes, Probl. Peredachi Inf., 1974, vol. 10, no. 1, pp. 9–14 [Probl. Inf. Transm. (Engl. Transl.), 1974, vol. 10, no. 1, pp. 6–9].
Beth, T., Jungnickel, D., and Lenz, H., Design Theory, 2 vols., Cambridge: Cambridge Univ. Press, 1999, 2nd ed.
Blake, I.F. and Mullin, R.C., The Mathematical Theory of Coding, New York: Academic, 1975.
Hughes, D.R. and Piper, F.C., Design Theory, Cabmridge: Cambridge Univ. Press, 1985.
Handbook of Combinatorial Designs, Colbourn, C.J. and Dinitz, J.H., Eds., Boca Raton: Chapman & Hall, 2007, 2nd ed.
Magliveras, S.S. and Leavitt, D.W., Simple Six Designs Exist, Congr. Numer. 1983, vol. 40, pp. 195–205.
Teirlinck, L., Non-trivial t-Designs without Repeated Blocks Exist for All t, Discrete Math., 1987, vol. 65, no. 3, pp. 301–311.
Assmus, E.F., Jr., Goethals, J.-M., and Mattson, H.F., Jr., Generalized t-Designs and Majority Decoding of Linear Codes, Inform. Control, 1976, vol. 32, no. 1, pp. 43–60.
Zinoviev, V.A. and Rifàa, J., On New Completely Regular q-ary Codes, Probl. Peredachi Inf., 2007, vol. 43, no. 2, pp. 34–51 [Probl. Inf. Transm. (Engl. Transl.), 2007, vol. 43, no. 2, pp. 97–112].
Bassalygo, L.A. and Zinoviev, V.A., Remark on Uniformly Packed Codes, Probl. Peredachi Inf., 1977, vol. 13, no. 3, pp. 22–25 [Probl. Inf. Transm. (Engl. Transl.), 1977, vol. 13, no. 3, pp. 178–180].
Rifà, J. and Zinoviev, V.A., New Completely Regular q-ary Codes Based on Kronecker Products, IEEE Trans. Inform. Theory, 2011, vol. 56, no. 1, pp. 266–272.
Rifà, J. and Zinoviev, V.A., On Lifting Perfect Codes, IEEE Trans. Inform. Theory, 2011, vol. 57, no. 9, pp. 5918–5925.
Rifà, J. and Zinoviev, V.A., On a Family of Binary Completely Transitive Codes with Growing Covering Radius, Discrete Math., 2014, vol. 318, pp. 48–52.
Gillespie, N.I. and Praeger, C.E., Uniqueness of Certain Completely Regular Hadamard Codes, J. Com-bin. Theory Ser. A, 2013, vol. 120, no. 7, pp. 1394–1400.
Borges, J., Rifà, J., and Zinoviev, V.A., New Families of Completely Regular Codes and Their Corresponding Distance Regular Coset Graphs, Des. Codes Cryptogr., 2014, vol. 70, no. 1–2, pp. 139–148.
Borges, J., Rifà, J., and Zinoviev, V.A., Families of Nested Completely Regular Codes and Distance-Regular Graphs, Adv. Math. Commun., 2015, vol. 9, no. 2, pp. 233–246.
Calderbank, A.R. and Goethals, J.-M., Three-Weight Codes and Association Schemes, Philips J. Res., 1984, vol. 39, no. 4–5, pp. 143–152.
Calderbank, A.R. and Goethals, J.-M., On a Pair of Dual Subschemes of the Hamming Scheme H n (q), European J. Combin., 1985, vol. 6, no. 2, pp. 133–147.
Baker, R.D., van Lint, J.H., and Wilson, R.M., On the Preparata and Goethals Codes, IEEE Trans. Inform. Theory, 1983, vol. 29, no. 3, pp. 342–345.
Zaitsev, G.V., Zinoviev, V.A., and Semakov, N.V., On the Duality of Preparata and Kerdock Codes, in Proc. 5th All-Union Conf. on Coding Theory, Moscow-Gorky, 1972, Part 2, pp. 55–58.
Camion, P., Courteau, B., Delsarte, P., On r-Partition Designs in Hamming Spaces, Appl. Algebra Engrg. Commun. Comput., 1992, vol. 2, no. 3, pp. 147–162.
Brouwer, A.E., On Complete Regularity of Extended Codes, Discrete Math., 1993, vol. 117, no. 1–3, pp. 271–273.
Rifà, J. and Pujol, J., Completely Transitive Codes and Distance Transitive Graphs, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (Proc. 9th Int. Sympos. AAECC-9, New Orleans, USA, Oct. 7–11, 1991), Mattson, H.F., Mora, T., and Rao, T.R.N., Eds., Lect. Notes Comp. Sci, vol. 539, Berlin: Springer, 1991, pp. 360–367.
Livingstone, D. and Wagner, A., Transitivity of Finite Permutation Groups on Unordered Sets, Math. Z., 1965, vol. 90, no. 5, pp. 393–403.
Berger, T.P., The Automorphism Group of Double-Error-Correcting BCH Codes, IEEE Trans. Inform. Theory, 1994, vol. 40, no. 2, pp. 538–542.
Godsil, C.D. and Praeger, C.E., Completely Transitive Designs, arXiv:1405.2176 [math.CO], 2014.
Bannai, E., Codes in Bipartite Distance-Regular Graphs, J. London Math. Soc. (2), 1977, vol. 16, no. 2, pp. 197–202.
Hammond, P., On the Non-existence of Perfect and Nearly Perfect Codes, Discrete Math., 1982, vol. 39, no. 1, pp. 105–109.
Etzion, T., On the Nonexistence of Perfect Codes in the Johnson Scheme, SIAM J. Discrete Math., 1996, vol. 9, no. 2, pp. 201–209.
Etzion, T. and Schwarz, M., Perfect Constant-Weight Codes, IEEE Trans. Inform. Theory, 2004, vol. 50, no. 9, pp. 2156–2165.
Etzion, T., Configuration Distribution and Designs of Codes in the Johnson Scheme, J. Combin. Des., 2007, vol. 15, no. 1, pp. 15–34.
Shimabukuro, O., On the Nonexistence of Perfect Codes in J (2w + p 2, w), Ars Combin., 2005, vol. 75, pp. 129–134.
Gordon, D.M., Perfect Single Error-Correcting Codes in the Johnson Scheme, IEEE Trans. Inform. Theory, 2006, vol. 52, no. 10, pp. 4670–4672.
Kummer, E.E., Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen, J. Reine Angew. Math., 1852, vol. 44, pp. 93–146.
Loxton, J.H., Some Problems Involving Powers of Integers, Acta Arith., 1986, vol. 46, no. 2, pp. 113–123.
Bernstein, D.J., Detecting Perfect Powers in Essentially Linear Time, Math. Comp., 1998, vol. 67, no. 223, pp. 1253–1283.
Roos, C., A Note on the Existence of Perfect Constant Weight Codes, Discrete Math., 1983, vol. 47, no. 1, pp. 121–123.
Movsisyan, G.L., Perfect Codes in Johnson Schemes, Vestn. Mosk. Gos. Univ. Ser. 15: Vychisl. Matem. Kibern., 1982, no. 1, pp. 64–69.
Movsisyan, G.L., Perfect Constant-Weight Codes and Steiner Systems, Probl. Peredachi Inf., 1983, vol. 19, no. 2, pp. 109–112.
Movsisian, G.L. and Margarian, Zh.G., D-Representing Code Problem Solution, Fundamentals of Computation Theory (Proc. Int. Conf. FCT’87, Kazan, USSR, June 22–26, 1987), Budach, L., Bukharajev, R.G., and Lupanov, O.B., Eds., Lect. Notes Comp. Sci., vol. 278, Berlin: Springer, 1987, pp. 328–331.
Leont’ev, V.K., Movsisyan, G.L., and Margaryan, Zh.G., Constant Weight Perfect and D-Representable Codes, Proc. Yerevan State Univ. Phys. Math. Sci., 2012, no. 1, pp. 16–19.
Mogil’nykh, I.Yu., On the Regularity of Perfect 2-Colorings of the Johnson Graph, Probl. Peredachi Inf., 2007, vol. 43, no. 4, pp. 37–44 [Probl. Inf. Transm. (Engl. Transl.), 2007, vol. 43, no. 4, pp. 303–309].
Mogil’nykh, I.Yu., On Nonexistence of Some Perfect 2-Colorings of Johnson Graphs, Diskretn. Anal. Issled. Oper., 2009, vol. 16, no. 5, pp. 52–68.
Avgustinovich, S.V., and Mogil’nykh, I.Yu., Perfect 2-Colorings of the Johnson Graphs J (8, 3) and J (8, 4), Diskretn. Anal. Issled. Oper., 2010, vol. 17, no. 2, pp. 3–19.
Martin, W.J., Completely Regular Designs of Strength One, J. Algebraic Combin., 1994, vol. 3, no. 2, pp. 177–185.
Martin, W.J., Completely Regular Designs, J. Combin. Des., 1998, vol. 6, no. 4, pp. 261–273.
Meyerowitz, A.D., Cycle-Balance Conditions for Distance-Regular Graphs, Discrete Math., 2003, vol. 264, no. 1–3, pp. 149–165.
Godsil, C., Personal communication to W. Martin [69].
Avgustinovich, S.V., and Mogilnykh, I.Yu., Induced Perfect Colorings, Sib. Electron. Mat. Izv., 2011, vol. 8, pp. 310–316. Available at http://semr.math.nsc.ru/v8/p310-316.pdf.
Delorme, C., Régularité métrique forte, Rapport de Recherche, Univ. Paris Sud, Orsay, France, 1983, no. 156.
Godsil, C., Association Schemes, Univ. of Waterloo, Canada, 2005. Available at https://www.math.uwaterloo.ca/∼cgodsil/pdfs/assoc2.pdf.
Godsil, C.D., Equitable Partitions, Combinatorics, Paul Erdős is Eighty, Miklós, D., Sós, V.T., and Szónyi, T., Eds., Budapest: János Bolyai Math. Soc., 1993, vol. 1. pp. 173–192.
Rifà, J. and Zinoviev, V.A., On Completely Regular Codes from Perfect Codes, in Proc. 10th Int. Workshop on Algebraic and Combinatorial Coding Theory (ACCT-10), Zvenigorod, Russia, Sept. 3–9, 2006, pp. 225–229.
Ivanov, A.A., Liebler, R.A., Penttila, T., and Praeger, C.E., Antipodal Distance-Transitive Covers of Complete Bipartite Graphs, European J. Combin., 1997, vol. 18, no. 1, pp. 11–33.
Rifà, J. and Zinoviev, V.A., Completely Regular Codes with Different Parameters Giving the Same Distance-Regular Coset Graphs, Discrete Math., 2017, vol. 340, no. 7, pp. 1649–1656.
Rifà, J. and Zinoviev, V.A., On a Class of Binary Linear Completely Transitive Codes with Arbitrary Covering Radius, Discrete Math., 2009, vol. 309, no. 16, pp. 5011–5016.
Borges, J., Rifà, J., and Zinoviev, V., Completely Regular Codes by Concatenating Hamming Codes, Adv. Math. Commun., 2018, vol. 12, no. 2, pp. 337–349.
Borges, J., Rifà, J., and Zinoviev, V., On New Infinite Families of Completely Regular and Completely Transitive Binary Codes, in Proc. 16th Int. Workshop on Algebraic and Combinatorial Coding Theory (ACCT-16), Svetlogorsk, Russia, Sept. 2–9, 2018, pp. 7–8.
Borges, J., Rifà, J., and Zinoviev, V.A., On q-ary Linear Completely Regular Codes with p =2 and Antipodal Dual, Adv. Math. Commun., 2010, vol. 4, no. 4, pp. 567–578.
Fon-Der-Flaass, D.G., A Bound on Correlation Immunity, Sib. Electron. Mat. Izv., 2007, vol. 4, pp. 133–135. Available at http://semr.math.nsc.ru/v4/p133-135.pdf.
Fon-Der-Flaass, D.G., Perfect 2-Colorings of a Hypercube, Sibirsk. Mat. Zh., 2007, vol. 48, no. 4, pp. 923–930 [Siberian Math. J. (Engl. Transl.), 2007, vol. 48, no. 4, pp. 740–745].
Fon-Der-Flaass, D.G., Perfect 2-Colorings of the 12-Cube That Attain the Bounds on Correlation Immunity, Sib. Electron. Mat. Izv., 2007, vol. 4, pp. 292–295. Available at http://semr.math.nsc.ru/v4/p292-295.pdf.
Tarannikov, Y.V., On Resilient Boolean Functions with Maximal Possible Nonlinearity, Progress in Cryptology — INDOCRYPT 2000 (Proc. 1st Int. Conf. in Cryptology in India, Calcutta, India, Dec. 10–13, 2000), Roy, B.K. and Okamoto, E., Eds., Lect. Notes Comp. Sci., vol. 1977, Berlin: Springer, 2000, pp. 19–30.
Calderbank, R. and Kantor, W.M., The Geometry of Two-Weight Codes, Bull. London Math. Soc., 1986, vol. 18, no. 2, pp. 97–122.
Bush, K.A., Orthogonal Arrays of Index Unity, Ann. Math. Statist., 1952, vol. 23, no. 3, pp. 426–434.
Delsarte, P., Two-Weight Linear Codes and Strongly Regular Graphs, MBLE Research Lab. Report, Brussels, Belgium, 1971, no. R160.
Semakov, N.V., Zinoviev, V.A., and Zaitsev, G.V., A Class of Maximum Equidistant Codes, Probl. Peredachi Inf., 1969, vol. 5, no. 2, pp. 84–87 [Probl. Inf. Transm. (Engl. Transl.), 1969, vol. 5, no. 2, pp. 65–68].
Carlet, C., Charpin, P., and Zinoviev, V., Codes, Bent Functions and Permutations Suitable for DES-like Cryptosystems, Des. Codes Cryptogr., 1998, vol. 15, no. 2, pp. 125–156.
Gold, R., Maximal Recursive Sequences with 3-Valued Recursive Cross-Correlation Functions, IEEE Trans. Inform. Theory, 1968, vol. 14, no. 1, pp. 154–156.
Kasami, T., The Weight Enumerators for Several Classes of Subcodes of the 2nd Order Binary Reed-Muller Codes, Inform. Control, 1971, vol. 18, no. 4, pp. 369–394.
Welch, L.R., Trace Mappings in Finite Fields and Shift Register Cross-Correlation Properties, Dept. Electrical Engineering Report, Univ. of Southern California, Los Angeles, 1969.
Canteaut, A., Charpin, P., and Dobbertin, H., Binary m-Sequences with Three-Valued Crosscorrelation: A Proof of Welch’s Conjecture, IEEE Trans. Inform. Theory, 2000, vol. 46, no. 1, pp. 4–8.
Hollmann, H.D.L. and Xiang, Q., A Proof of the Welch and Niho Conjectures on Cross-Correlations of Binary m-Sequences, Finite Fields Appl., 2001, vol. 7, no. 2, pp. 253–286.
Dobbertin, H., Almost Perfect Nonlinear Power Functions over GF(2n): The Niho Case, Inform. and Comput., 1999, vol. 151, no. 1–2, pp. 57–72.
Beth, T. and Ding, C., On Almost Perfect Nonlinear Permutations, Advances in Cryptology–EURO-CRYPT’93 (Proc. Workshop on the Theory and Application of Cryptographic Techniques, Lofthus, Norway, May 23–27, 1993), Helleseth, T., Ed., Lect. Notes Comp. Sci., vol. 765, Berlin: Springer, 1994, pp. 65–76.
Dobbertin, H., Almost Perfect Nonlinear Power Functions on GF(2n): A New Case for n Divisible by 5, Finite Fields and Applications, Jungnickel, D. and Niederreiter, H., Eds., Berlin: Springer, 2001, pp. 113–121.
Budaghyan, L., Carlet, C., and Pott, A., New Classes of Almost Bent and Almost Perfect Nonlinear Polynomials, IEEE Trans. Inform. Theory, 2006, vol. 52, no. 3, pp. 1141–1152.
Berger, T.P., Canteaut, A., Charpin, P., and Laigle-Chapuy, Y., On Almost Perfect Nonlinear Functions over \(F_2^n\), IEEE Trans. Inform. Theory, 2006, vol. 52, no. 9, pp. 4160–4170.
Carlet, C., Boolean Functions for Cryptography and Error-Correcting Codes, ch. 8 of Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Crama, Y. and Hammer, P.L., Eds., Cambridge: Cambridge Univ. Press, 2010, pp. 257–397.
Dumer, I.I. and Zinoviev, V.A., Some New Maximal Codes over Galois Field GF(4), Probl. Peredachi Inf., 1978, vol. 14, no. 3, pp. 24–34 [Probl. Inf. Transm. (Engl. Transl.), 1978, vol. 14, no. 3, pp. 174–181].
Shi, M., Krotov, D.S., and Solé, P., A New Distance-Regular Graph of Diameter 3 on 1024 Vertices, arXiv:1806.07069v3 [math.CO], 2018.
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Borges, J., Rifà, J. & Zinoviev, V.A. On Completely Regular Codes. Probl Inf Transm 55, 1–45 (2019). https://doi.org/10.1134/S0032946019010010
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0032946019010010