On the Nonexistence of Perfect Codes over Finite Fields 论文

摘要

Previous article Next article On the Nonexistence of Perfect Codes over Finite FieldsAimo TietäväinenAimo Tietäväinenhttps://doi.org/10.1137/0124010PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstractIt is proved that there are no unknown perfect (Hamming-)error-correcting codes over finite fields.[1] Ronald Alter, On the nonexistence of close-packed double Hamming-error-correcting codes on $q=7$ symbols, J. Comput. System Sci., 2 (1968), 169–176 MR0239870 0162.22801 CrossrefGoogle Scholar[2] Ronald Alter, On the non-existence of perfect double Hamming-error-correcting codes on $q=8$ and $q=9$ symbols, Information and Control, 13 (1968), 619–627 10.1016/S0019-9958(68)91038-3 MR0239869 0165.22101 CrossrefGoogle Scholar[3] E. F. Assmus, Jr., , H. F. Mattson, Jr. and , R. Turyn, Cyclic codes, Rep., AFCRL-66-348, Applied Research Laboratory, Sylvania Electronic Systems, 1966 Google Scholar[4] Elwyn R. Berlekamp, Algebraic coding theory, McGraw-Hill Book Co., New York, 1968xiv+466 MR0238597 0988.94521 Google Scholar[5] Edward L. Cohen, A note on perfect double error-correcting codes on q symbols, Information and Control, 7 (1964), 381–384 10.1016/S0019-9958(64)90454-1 MR0168393 0134.15302 CrossrefGoogle Scholar[6] M. J. E. Golay, Notes on digital coding, Proc. IRE, 37 (1949), 657– ISIGoogle Scholar[7] Solomon W. Golomb and , Lloyd R. Welch, Algebraic coding and the Lee metric, Error Correcting Codes (Proc. Sympos. Math. Res. Center, Madison, Wis., 1968), John Wiley, New York, 1968, 175–194, Mann, H. B. MR0234758 0169.51001 Google Scholar[8] R. W. Hamming, Error detecting and error correcting codes, Bell System Tech. J., 29 (1950), 147–160 MR0035935 CrossrefISIGoogle Scholar[9] Bernt Lindström, On group and nongroup perfect codes in q symbols, Math. Scand., 25 (1970), 149–158 (1970) MR0270823 ISIGoogle Scholar[10] J. H. van Lint, On the nonexistence of certain perfect codes, Computers in Number Theory, Proc. Science Research Council Atlas Symposium (Oxford, 1969), 1971 0226.94006 Google Scholar[11] J. H. van Lint, 1967-1969 report of the discrete mathematics group, Rep., 69-WSK-04, Technological University, Eindhoven, 1969 Google Scholar[12] J. H. van Lint, On the nonexistence of perfect 2- and 3-Hamming-error-correcting codes over ${\rm GF}(q)$, Information and Control, 16 (1970), 396–401 10.1016/S0019-9958(70)90213-5 MR0270824 0205.47102 CrossrefGoogle Scholar[13] J. H. van Lint, Nonexistence theorems for perfect error-correcting codes, Computers in Algebra and Number Theory, SIAM-AMS, vol. 3 Google Scholar[14] J. H. van Lint, On the nonexistence of perfect 5-, 6- and 7-Hamming-error-correcting codes over GF(q), Rep., 70-WSK-06, Technological University, Eindhoven, 1970 Google Scholar[15] J. H. van Lint, Coding theory, Lecture Notes in Mathematics, Vol. 201, Springer-Verlag, Berlin, 1971vii+136 MR0286555 0224.94002 CrossrefGoogle Scholar[16] S. P. Lloyd, Binary block coding, Bell System Tech. J., 36 (1957), 517–535 MR0088077 CrossrefISIGoogle Scholar[17] F. J. MacWilliams, H. B. Mann, Error-correcting codes—a historical surveyError-Correcting Codes, John Wiley, New York, 1968, 3–13 Google Scholar[18] Vera Pless, On the uniqueness of the Golay codes, J. Combinatorial Theory, 5 (1968), 215–228 MR0242561 0172.43105 CrossrefGoogle Scholar[19] J. Schönheim, On linear and nonlinear single-error-correcting q-nary perfect codes., Information and Control, 12 (1968), 23–26 MR0237227 CrossrefGoogle Scholar[20] H. S. Shapiro and , D. L. Slotnick, On the mathematical theory of error-correcting codes, IBM J. Res. Develop., 3 (1959), 25–34 MR0098636 0109.10706 CrossrefISIGoogle Scholar[21] Aimo Tietäväinen, On the nonexistence of perfect 4-Hamming-error-correcting codes, Ann. Acad. Sci. Fenn. Ser. A I No., 485 (1970), 6– MR0280267 Google Scholar[22] Aimo Tietäväinen and , Aarni Perko, There are no unknown perfect binary codes, Ann. Univ. Turku. Ser. A I No., 148 (1971), 6– MR0282735 Google Scholar[23] Ju. L. Vasil'ev, On ungrouped, close-packed codes, Problemy Kibernet. No., 8 (1962), 337–339, (in Russian); Probleme der Kybernetik, 8 (1965), pp. 375–378. (In German.) MR0168398 Google Scholar Previous article Next article FiguresRelatedReferencesCited ByDetails On the classification of binary completely transitive codes with almost-simple top-groupEuropean Journal of Combinatorics, Vol. 107 | 1 Jan 2023 Cross Ref Two-State Alien Tiles: A Coding-Theoretical PerspectiveMathematics, Vol. 10, No. 16 | 19 August 2022 Cross Ref Linear Block CodesFundamentals of Classical and Modern Error-Correcting Codes | 9 Dec 2021 Cross Ref On existence of perfect bitrades in Hamming graphsDiscrete Mathematics, Vol. 343, No. 12 | 1 Dec 2020 Cross Ref Minimal binary 2-neighbour-transitive codesJournal of Combinatorial Theory, Series A, Vol. 171 | 1 Apr 2020 Cross Ref The Existence of Perfect Codes in Doob GraphsIEEE Transactions on Information Theory, Vol. 66, No. 3 | 1 Mar 2020 Cross Ref How Many Weights Can a Cyclic Code Have?IEEE Transactions on Information Theory, Vol. 66, No. 3 | 1 Mar 2020 Cross Ref Subgroup Perfect Codes in Cayley GraphsXuanlong Ma, Gary L. Walls, Kaishun Wang, and Sanming ZhouSIAM Journal on Discrete Mathematics, Vol. 34, No. 3 | 1 September 2020AbstractPDF (425 KB)Steganographic schemes from perfect codes on Cayley graphsDesigns, Codes and Cryptography, Vol. 87, No. 10 | 2 March 2019 Cross Ref Match fitness landscapes for macromolecular interaction networks: Selection for translational accuracy and rate can displace tRNA-binding interfaces of non-cognate aminoacyl-tRNA synthetasesTheoretical Population Biology, Vol. 129 | 1 Oct 2019 Cross Ref Additive perfect codes in Doob graphsDesigns, Codes and Cryptography, Vol. 87, No. 8 | 29 November 2018 Cross Ref On Perfect Codes and Related ConceptsProbabilistic Methods and Distributed Information | 31 December 2018 Cross Ref Perfect, Hamming and Simplex Linear Error-Block Codes with Minimum $$\pi $$ -distance 3Codes, Cryptology and Information Security | 28 March 2019 Cross Ref On Completely Regular CodesProblems of Information Transmission, Vol. 55, No. 1 | 24 April 2019 Cross Ref Hierarchical PosetsPoset Codes: Partial Orders, Metrics and Coding Theory | 2 November 2018 Cross Ref Applications of graph containers in the Boolean latticeRandom Structures & Algorithms, Vol. 49, No. 4 | 22 July 2016 Cross Ref Quasi-perfect linear codes from planar and APN functionsCryptography and Communications, Vol. 8, No. 2 | 16 April 2015 Cross Ref On the Existence of Perfect Linear Codes Over $${{\mathbb{Z}}_{{2^{l}}}}$$ with Respect to Homogenous MetricArabian Journal for Science and Engineering, Vol. 38, No. 8 | 16 February 2013 Cross Ref BibliographyHandbook of Finite Fields | 18 June 2013 Cross Ref On Perfect 2-Colorings of Johnson Graphs J ( v , 3)Journal of Combinatorial Designs, Vol. 21, No. 6 | 30 July 2012 Cross Ref Prologue: What This Book Is AboutFault-Tolerant Search Algorithms | 12 September 2013 Cross Ref Fault-Tolerant Search à la Ulam-RényiFault-Tolerant Search Algorithms | 12 September 2013 Cross Ref Adaptive vs. Non-adaptive SearchFault-Tolerant Search Algorithms | 12 September 2013 Cross Ref Variations on a Theme of Ulam and Rényi: More Types of Questions and LiesFault-Tolerant Search Algorithms | 12 September 2013 Cross Ref Delays and Time OutsFault-Tolerant Search Algorithms | 12 September 2013 Cross Ref Group TestingFault-Tolerant Search Algorithms | 12 September 2013 Cross Ref Resilient SearchFault-Tolerant Search Algorithms | 12 September 2013 Cross Ref A Model for LearningFault-Tolerant Search Algorithms | 12 September 2013 Cross Ref A note on the symmetry group of full rank perfect binary codesDiscrete Mathematics, Vol. 312, No. 19 | 1 Oct 2012 Cross Ref Fuzzy Joins Using MapReduce2012 IEEE 28th International Conference on Data Engineering | 1 Apr 2012 Cross Ref BibliographyAlgebraic and Stochastic Coding Theory | 10 May 2012 Cross Ref ReferencesIntroduction to the Theory of Error-Correcting Codes | 28 October 2011 Cross Ref The non-existence of some perfect codes over non-prime power alphabetsDiscrete Mathematics, Vol. 311, No. 14 | 1 Jul 2011 Cross Ref A family of constacyclic ternary quasi-perfect codes with covering radius 3Designs, Codes and Cryptography, Vol. 59, No. 1-3 | 30 December 2010 Cross Ref Irredundant families of subcubesMathematical Proceedings of the Cambridge Philosophical Society, Vol. 150, No. 2 | 12 January 2011 Cross Ref Golay Code Clustering for Mobility Behavior Similarity Classification in Pocket Switched NetworksWireless Algorithms, Systems, and Applications | 1 Jan 2011 Cross Ref Recent Developments of Feedback Coding and Its Relations with Many-Valued LogicProof, Computation and Agency | 10 March 2011 Cross Ref On $q$-ary linear completely regular codes with $\rho=2$ and antipodal dualAdvances in Mathematics of Communications, Vol. 4, No. 4 | 1 Nov 2010 Cross Ref A Lower Bound on the Optimum Distance Profiles of the Second-Order Reed–Muller CodesIEEE Transactions on Information Theory, Vol. 56, No. 9 | 1 Sep 2010 Cross Ref Constructions of partitions of F q N into perfect q-ary codesJournal of Applied and Industrial Mathematics, Vol. 4, No. 1 | 25 March 2010 Cross Ref Privacy Weaknesses in Biometric Sketches2009 30th IEEE Symposium on Security and Privacy | 1 May 2009 Cross Ref A family of ternary quasi-perfect BCH codesDesigns, Codes and Cryptography, Vol. 49, No. 1-3 | 21 March 2008 Cross Ref Perfect codes from the dual point of view IDiscrete Mathematics, Vol. 308, No. 24 | 1 Dec 2008 Cross Ref On perfect codes for an additive channelProblems of Information Transmission, Vol. 44, No. 4 | 24 January 2009 Cross Ref The Algebraic Degree of Perfect Binary CodesIEEE Transactions on Information Theory, Vol. 54, No. 11 | 1 Nov 2008 Cross Ref Binary and Ternary Linear Quasi-Perfect Codes With Small DimensionsIEEE Transactions on Information Theory, Vol. 54, No. 9 | 1 Sep 2008 Cross Ref On non-antipodal binary completely regular codesDiscrete Mathematics, Vol. 308, No. 16 | 1 Aug 2008 Cross Ref The algebraic degree of 1-perfect binary codes and a relation with the code characters2008 IEEE International Symposium on Information Theory | 1 Jul 2008 Cross Ref Survey of the methods for constructing nonlinear perfect binary codesJournal of Applied and Industrial Mathematics, Vol. 2, No. 2 | 3 June 2008 Cross Ref On perfect binary codesDiscrete Applied Mathematics, Vol. 156, No. 9 | 1 May 2008 Cross Ref Intersections of q-ary perfect codesSiberian Mathematical Journal, Vol. 49, No. 2 | 1 Mar 2008 Cross Ref On perfect codes in rank distanceJournal of Discrete Mathematical Sciences and Cryptography, Vol. 11, No. 1 | 1 Feb 2008 Cross Ref Perfect Codes of Length n with Kernels of Dimension $n-\log(n+1)-3$Olof HedenSIAM Journal on Discrete Mathematics, Vol. 22, No. 4 | 4 September 2008AbstractPDF (176 KB)On perfect p-ary codes of length p + 1Designs, Codes and Cryptography, Vol. 46, No. 1 | 13 November 2007 Cross Ref A coding problem in steganographyDesigns, Codes and Cryptography, Vol. 46, No. 1 | 28 November 2007 Cross Ref On new completely regular q-ary codesProblems of Information Transmission, Vol. 43, No. 2 | 1 Jun 2007 Cross Ref Perfect minimally adaptive -ary search with unreliable testsJournal of Statistical Planning and Inference, Vol. 137, No. 1 | 1 Jan 2007 Cross Ref Perfect codes in additive channelsDoklady Mathematics, Vol. 74, No. 3 | 1 Dec 2006 Cross Ref Jack van Lint (1932–2004): A survey of his scientific workJournal of Combinatorial Theory, Series A, Vol. 113, No. 8 | 1 Nov 2006 Cross Ref On the classification of perfect codes: side class structuresDesigns, Codes and Cryptography, Vol. 40, No. 3 | 1 Sep 2006 Cross Ref (1, 2) Optimal codes over GF(5)Journal of Interdisciplinary Mathematics, Vol. 9, No. 2 | 1 Jun 2006 Cross Ref On partitions of theq-ary Hamming space into few spheresJournal of Combinatorial Designs, Vol. 14, No. 3 | 1 January 2006 Cross Ref On some perfect codes with respect to Lee metricLinear Algebra and its Applications, Vol. 405 | 1 Aug 2005 Cross Ref Perfect Constant-Weight CodesIEEE Transactions on Information Theory, Vol. 50, No. 9 | 1 Sep 2004 Cross Ref Ternary (1, 2) optimal linear codesJournal of Interdisciplinary Mathematics, Vol. 7, No. 1 | 1 Jan 2004 Cross Ref Quasi-Perfect Minimally Adaptive q-ary Search with Unreliable TestsAlgorithms and Computation | 1 Jan 2003 Cross Ref Learning and the Art of Fault-Tolerant GuessworkAdaptivity and Learning | 1 Jan 2003 Cross Ref The Statistical Physics of Learning: Phase Transitions and Dynamical Symmetry BreakingAdaptivity and Learning | 1 Jan 2003 Cross Ref Designs and Error-Correcting CodesEncyclopedia of Physical Science and Technology | 1 Jan 2003 Cross Ref Least adaptive optimal search with unreliable testsTheoretical Computer Science, Vol. 270, No. 1-2 | 1 Jan 2002 Cross Ref On completely regular binary codes and t-designs∗Electronic Notes in Discrete Mathematics, Vol. 10 | 1 Nov 2001 Cross Ref Structure of i-components of perfect binary codesDiscrete Applied Mathematics, Vol. 111, No. 1-2 | 1 Jul 2001 Cross Ref Nonexistence of completely transitive codes with error-correcting capability e<3IEEE Transactions on Information Theory, Vol. 47, No. 4 | 1 May 2001 Cross Ref Rota-Metropolis cubic logic and Ulam-Rényi gamesAlgebraic Combinatorics and Computer Science | 1 Jan 2001 Cross Ref Perfect Two-Fault Tolerant Search with Minimum AdaptivenessAdvances in Applied Mathematics, Vol. 25, No. 1 | 1 Jul 2000 Cross Ref Least Adaptive Optimal Search with Unreliable TestsAlgorithm Theory - SWAT 2000 | 15 March 2002 Cross Ref Switchings and Perfect CodesNumbers, Information and Complexity | 1 Jan 2000 Cross Ref On the nonexistence of completely transitive codesIEEE Transactions on Information Theory, Vol. 46, No. 1 | 1 Jan 2000 Cross Ref A characterization of 1-perfect additive codesIEEE Transactions on Information Theory, Vol. 45, No. 5 | 1 Jul 1999 Cross Ref The art of signaling: fifty years of coding theoryIEEE Transactions on Information Theory, Vol. 44, No. 6 | 1 Oct 1998 Cross Ref On Perfect Codes and Tilings: Problems and SolutionsTuvi Etzion and Alexander VardySIAM Journal on Discrete Mathematics, Vol. 11, No. 2 | 1 August 2006AbstractPDF (412 KB)Translation-invariant propelinear codesIEEE Transactions on Information Theory, Vol. 43, No. 2 | 1 Mar 1997 Cross Ref BibliographyCovering Codes | 1 Jan 1997 Cross Ref Chapter 20 ComplexityCovering Codes | 1 Jan 1997 Cross Ref On the Non - Existence of Perfect Codes with Rank DistanceMathematische Nachrichten, Vol. 182, No. 1 | 1 Jan 1996 Cross Ref A decoding algorithm for the (23, 12, 7) golay code with error and erasure correctionAnnales Des Télécommunications, Vol. 50, No. 9-10 | 1 Sep 1995 Cross Ref Football Pools—A Game for MathematiciansThe American Mathematical Monthly, Vol. 102, No. 7 | 18 April 2018 Cross Ref The Unity of CombinatoricsCombinatorics Advances | 1 Jan 1995 Cross Ref GEncyclopaedia of Mathematics | 1 Jan 1995 Cross Ref Perfect binary codes: constructions, properties, and enumerationIEEE Transactions on Information Theory, Vol. 40, No. 3 | 1 May 1994 Cross Ref Error Correction I: Distance Concepts and BoundsBasic Concepts in Information Theory and Coding | 1 Jan 1994 Cross Ref A characterization of some [n,k,d;q]-codes meeting the Griesmer bound using a minihyper in a finite projective geometryDiscrete Mathematics, Vol. 116, No. 1-3 | 1 Jun 1993 Cross Ref Classification of a class of distance-regular graphs via completely regular codesDiscrete Applied Mathematics, Vol. 26, No. 2-3 | 1 Mar 1990 Cross Ref Perfect Multiple Coverings in Metric SchemesCoding Theory and Design Theory | 1 Jan 1990 Cross Ref GEncyclopaedia of Mathematics | 1 Jan 1989 Cross Ref EEncyclopaedia of Mathematics | 16 November 2011 Cross Ref On the nonexistence of nontrivial perfecte-codes and tight 2e-designs in hamming schemesH(n, q) withe ≥ 3 andq ≥ 3Graphs and Combinatorics, Vol. 2, No. 1 | 1 Dec 1986 Cross Ref Maximal partial spreads and two-weight codesDiscrete Mathematics, Vol. 62, No. 3 | 1 Dec 1986 Cross Ref Upper Bounds for the Cardinality of s-Distances CodesEuropean Journal of Combinatorics, Vol. 7, No. 1 | 1 Jan 1986 Cross Ref Some aspects of coding theory between probability, algebra, combinatorics and complexity theoryCombinatorial Theory | 25 August 2006 Cross Ref Caps Related to Incidence Structures and to Linear CodesCombinatorial and Geometric Structures and their Applications | 1 Jan 1982 Cross Ref An Elias-type bound for Lee codes over large alphabets and its application to perfect codes (Corresp.)IEEE Transactions on Information Theory, Vol. 28, No. 1 | 1 Jan 1982 Cross Ref Weight distribution of translates, covering radius, and perfect codes correcting errors of given weightsIEEE Transactions on Information Theory, Vol. 27, No. 4 | 1 Jul 1981 Cross Ref A modification of the elias-bound and nonexistence theorems for perfect codes in the Lee-metricInformation and Control, Vol. 49, No. 2 | 1 May 1981 Cross Ref On the Weight Distributions of Cosets of a Linear CodeThe American Mathematical Monthly, Vol. 87, No. 7 | 11 April 2018 Cross Ref Codes and DesignsMathematics Magazine, Vol. 52, No. 2 | 13 February 2018 Cross Ref On some properties of the undetected error probability of linear codes (Corresp.)IEEE Transactions on Information Theory, Vol. 25, No. 1 | 1 Jan 1979 Cross Ref Lloyd's theorem for perfect codesDiscrete Mathematics, Vol. 21, No. 2 | 1 Jan 1978 Cross Ref Codes projectifs à deux poids, "caps" complets et ensembles de différencesJournal of Combinatorial Theory, Series A, Vol. 23, No. 2 | 1 Sep 1977 Cross Ref All nearly perfect codes are knownInformation and Control, Vol. 35, No. 1 | 1 Sep 1977 Cross Ref On perfect codes in the hamming schemes H(n, q) with q arbitraryJournal of Combinatorial Theory, Series A, Vol. 23, No. 1 | 1 Jul 1977 Cross Ref PHASED ERROR CORRECTING PERFECT CODESJournal of Cybernetics, Vol. 7, No. 3-4 | 1 Jul 1977 Cross Ref Algebraic theory of block codes detecting independent errorsJournal of Soviet Mathematics, Vol. 7, No. 2 | 1 Feb 1977 Cross Ref Permutation Groups on Unordered SetsHigher Combinatorics | 1 Jan 1977 Cross Ref Nonexistence of nontrivial perfect codes in case q = pr1p12,e ⩾ 3Discrete Mathematics, Vol. 17, No. 2 | 1 Jan 1977 Cross Ref CombinatoricsUse of Mathematical Literature | 1 Jan 1977 Cross Ref BibliographyThe Theory of Error-Correcting Codes | 1 Jan 1977 Cross Ref ADJACENT-ERROR CORRECTING BINARY PERFECT CODESJournal of Cybernetics, Vol. 7, No. 1-2 | 3 April 2007 Cross Ref Generalized t-designs and majority decoding of linear codesInformation and Control, Vol. 32, No. 1 | 1 Sep 1976 Cross Ref ReferencesAn Introduction to Algebraic and Combinatorial Coding Theory | 1 Jan 1976 Cross Ref Perfect codes in the graphs OkJournal of Combinatorial Theory, Series B, Vol. 19, No. 3 | 1 Dec 1975 Cross Ref A class of binoid single-error-correcting codes (Corresp.)IEEE Transactions on Information Theory, Vol. 21, No. 4 | 1 Jul 1975 Cross Ref Recent Results on Perfect Codes and Related TopicsCombinatorics | 1 Jan 1975 Cross Ref Unrestricted codes with the golay parameters are uniqueDiscrete Mathematics, Vol. 12, No. 3 | 1 Jan 1975 Cross Ref ReferencesThe Mathematical Theory of Coding | 1 Jan 1975 Cross Ref Coding and CombinatoricsE. F. Assmus, Jr. and H. F. Mattson, Jr.SIAM Review, Vol. 16, No. 3 | 18 July 2006AbstractPDF (4660 KB)Characterisations of some Steiner systems, parallelisms, and biplanesMathematische Zeitschrift, Vol. 136, No. 1 | 1 Mar 1974 Cross Ref Perfect codes in graphsJournal of Combinatorial Theory, Series B, Vol. 15, No. 3 | 1 Dec 1973 Cross Ref Four fundamental parameters of a code and their combinatorial significanceInformation and Control, Vol. 23, No. 5 | 1 Dec 1973 Cross Ref A survey of constructive coding theory, and a table of binary codes of highest known rateDiscrete Mathematics, Vol. 3, No. 1-3 | 1 Jan 1972 Cross Ref Some new double-error correcting quasi-perfect codesICC 91 International Conference on Communications Conference Record Cross Ref Perfect, minimally adaptive, error-correcting searching strategies2000 IEEE International Symposium on Information Theory (Cat. No.00CH37060) Cross Ref New bounds on a hypercube coloring problem and linear codesProceedings International Conference on Information Technology: Coding and Computing Cross Ref Perfect Codes in the Johnson Schemes2006 IEEE Information Theory Workshop Cross Ref Volume 24, Issue 1| 1973SIAM Journal on Applied Mathematics1-143 History Submitted:28 April 1971Accepted:18 April 1972Published online:17 February 2012 InformationCopyright © 1973 Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0124010Article page range:pp. 88-96ISSN (print):0036-1399ISSN (online):1095-712XPublisher:Society for Industrial and Applied Mathematics