Previous article Next article Perfect Codes in the Lee Metric and the Packing of PolyominoesSolomon W. Golomb and Lloyd R. WelchSolomon W. Golomb and Lloyd R. Welchhttps://doi.org/10.1137/0118025PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout[1] S. W. Golomb and , E. C. Posner, Rook domains, Latin squares, affine planes, and error-distributing codes, IEEE Trans. Information Theory, IT-10 (1964), 196–208 10.1109/TIT.1964.1053680 MR0168394 (29:5657) 0124.11404 CrossrefISIGoogle Scholar[2] S. W. Golomb and , E. C. Posner, Hypercubes of nonnegative integers, Bull. Amer. Math. Soc., 71 (1965), 587– CrossrefISIGoogle Scholar[3] H. S. M. Coxeter, Regular polytopes, Second edition, The Macmillan Co., New York, 1963xx+321 pp. (8 plates) MR0151873 (27:1856) 0118.35902 Google Scholar[4] S. Chaude Shannon, A mathematical theory of communication, Bell System Tech. J., 27 (1948), 379–423, 623–656 MR0026286 (10,133e) CrossrefGoogle Scholar[5] Hermann Minkowski, Quelques nouveaux nouveaux thèoremes sur l'approximation des quantites a l'aide de nombres rationnels, Bulletin des sciences mathématique (2), 25 (), 72–76 Google Scholar Previous article Next article FiguresRelatedReferencesCited byDetails 1-Perfect Codes Over the Quad-CubeIEEE Transactions on Information Theory, Vol. 68, No. 10 Cross Ref Partitions into Perfect Codes in the Hamming and Lee Metrics4 October 2022 | Problems of Information Transmission, Vol. 58, No. 3 Cross Ref Lattice packings of cross‐polytopes from Reed–Solomon codes and Sidon sets29 June 2022 | Bulletin of the London Mathematical Society, Vol. 18 Cross Ref Perfect t-codes in Cayley graphs of groups19 April 2021 | Discrete Mathematics, Algorithms and Applications, Vol. 14, No. 02 Cross Ref Topological Quantum Codes11 May 2022 Cross Ref Perfect codes in Euclidean lattices12 February 2021 | Computational and Applied Mathematics, Vol. 40, No. 2 Cross Ref Obtaining Binary Perfect Codes Out of TilingsIEEE Transactions on Information Theory, Vol. 66, No. 10 Cross Ref No lattice tiling of Zn by Lee sphere of radius 2Journal of Combinatorial Theory, Series A, Vol. 171 Cross Ref On the non-existence of linear perfect Lee codes: The Zhang–Ge condition and a new polynomial criterionEuropean Journal of Combinatorics, Vol. 83 Cross Ref Steganographic schemes from perfect codes on Cayley graphs2 March 2019 | Designs, Codes and Cryptography, Vol. 87, No. 10 Cross Ref Runlength-Limited Sequences and Shift-Correcting Codes: Asymptotic AnalysisIEEE Transactions on Information Theory, Vol. 65, No. 8 Cross Ref On the nonexistence of lattice tilings of Zn by Lee spheresJournal of Combinatorial Theory, Series A, Vol. 165 Cross Ref Bounds on Codes for the Bit-Shift Channel with (d,k)-Constrained Inputs Cross Ref Metrics which turn tilings into binary perfect codes Cross Ref Perfect Codes in Euclidean Lattices: Bounds and Case Studies Cross Ref Fault-Tolerant Dot-Product EnginesIEEE Transactions on Information Theory, Vol. 65, No. 4 Cross Ref Codes in the Space of Multisets—Coding for Permutation Channels With ImpairmentsIEEE Transactions on Information Theory, Vol. 64, No. 7 Cross Ref Quasi-perfect codes in the $$\ell _p$$ ℓ p metric8 August 2016 | Computational and Applied Mathematics, Vol. 37, No. 2 Cross Ref Restriction conditions on PL(7, 2) codes (3 ≤ |𝓖 i | ≤ 7)2 April 2018 | Open Mathematics, Vol. 16, No. 1 Cross Ref 50 Years of the Golomb–Welch ConjectureIEEE Transactions on Information Theory, Vol. 64, No. 4 Cross Ref 2-Correcting Lee Codes: (Quasi)-Perfect Spectral Conditions and Some ConstructionsIEEE Transactions on Information Theory, Vol. 64, No. 4 Cross Ref Non-Existence of Linear Perfect Lee Codes With Radius 2 for Infinitely Many DimensionsIEEE Transactions on Information Theory, Vol. 64, No. 4 Cross Ref Lattice Codes for Deletion and Repetition ChannelsIEEE Transactions on Information Theory, Vol. 64, No. 3 Cross Ref Orthogonal Polynomials in Information Theory2 July 2017 Cross Ref Perfect and Quasi-Perfect Codes Under the $l_{p}$ MetricIEEE Transactions on Information Theory, Vol. 63, No. 7 Cross Ref Nonexistence of perfect 2 -error-correcting Lee codes in certain dimensionsEuropean Journal of Combinatorics, Vol. 63 Cross Ref Improved Bounds on Sidon Sets via Lattice Packings of SimplicesMladen Kovačević and Vincent Y. F. Tan28 September 2017 | SIAM Journal on Discrete Mathematics, Vol. 31, No. 3AbstractPDF (357 KB)Lattices from Codes9 December 2017 Cross Ref Distances Cross Ref The Cayley Graphs Associated With Some Quasi-Perfect Lee Codes Are Ramanujan GraphsIEEE Transactions on Information Theory, Vol. 62, No. 11 Cross Ref Systematic Error-Correcting Codes for Permutations and Multi-PermutationsIEEE Transactions on Information Theory, Vol. 62, No. 6 Cross Ref Accurate, Dynamic, and Distributed Localization of Phenomena for Mobile Sensor NetworksACM Transactions on Sensor Networks, Vol. 12, No. 2 Cross Ref Perfect codes in the lp metricEuropean Journal of Combinatorics, Vol. 53 Cross Ref Quasi-Perfect Lee Codes of Radius 2 and Arbitrarily Large DimensionIEEE Transactions on Information Theory, Vol. 62, No. 3 Cross Ref On perfect q-ary codes in the maximum metric Cross Ref Perfect codes in direct graph bundlesInformation Processing Letters, Vol. 115, No. 9 Cross Ref 1-Perfect Codes Over Dual-Cubes vis-à-vis Hamming Codes Over HypercubesIEEE Transactions on Information Theory, Vol. 61, No. 8 Cross Ref Bounds on the Size of Permutation Codes With the Kendall $\tau $ -MetricIEEE Transactions on Information Theory, Vol. 61, No. 6 Cross Ref Cross-packing lattices for the Rician fading channel Cross Ref Mellin transforms with only critical zeros: Legendre functionsJournal of Number Theory, Vol. 148 Cross Ref Systematic Error-Correcting Codes for Rank ModulationIEEE Transactions on Information Theory, Vol. 61, No. 1 Cross Ref Systematic codes for rank modulation Cross Ref Perfect permutation codes with the Kendall's τ-metric Cross Ref A new approach towards the Golomb–Welch conjectureEuropean Journal of Combinatorics, Vol. 38 Cross Ref On the non-existence of lattice tilings by quasi-crossesEuropean Journal of Combinatorics, Vol. 36 Cross Ref Codes and lattices in the lp metric Cross Ref Codes for Information Retrieval With Small UncertaintyIEEE Transactions on Information Theory, Vol. 60, No. 2 Cross Ref A generalization of Lee codes21 April 2012 | Designs, Codes and Cryptography, Vol. 70, No. 1-2 Cross Ref [1, 2]-sets in graphsDiscrete Applied Mathematics, Vol. 161, No. 18 Cross Ref Coding for the Lee and Manhattan Metrics With Weighing MatricesIEEE Transactions on Information Theory, Vol. 59, No. 10 Cross Ref Bounds on the size of Lee-codes Cross Ref Quasi-Perfect Codes From Cayley Graphs Over Integer RingsIEEE Transactions on Information Theory, Vol. 59, No. 9 Cross Ref Coding for the Lee and Manhattan metrics with weighing matrices Cross Ref Lattice based codes for insertion and deletion channels Cross Ref (a,b) -codes in Z/nZDiscrete Applied Mathematics, Vol. 161, No. 4-5 Cross Ref Codes over Hurwitz integersDiscrete Mathematics, Vol. 313, No. 5 Cross Ref Tilings by $(0.5,n)$-Crosses and Perfect CodesSarit Buzaglo and Tuvi Etzion10 June 2013 | SIAM Journal on Discrete Mathematics, Vol. 27, No. 2AbstractPDF (305 KB)The Structure of Cube Tilings Under Symmetry Conditions19 July 2012 | Discrete & Computational Geometry, Vol. 48, No. 3 Cross Ref Diameter Perfect Lee CodesIEEE Transactions on Information Theory, Vol. 58, No. 8 Cross Ref Systematic error-correcting codes for rank modulation Cross Ref On the use of Lee-codes for constructing multiple-valued error-correcting decision diagrams Cross Ref Quasi-Cross Lattice Tilings With Applications to Flash MemoryIEEE Transactions on Information Theory, Vol. 58, No. 4 Cross Ref Non-periodic Tilings of ℝ n by Crosses3 September 2011 | Discrete & Computational Geometry, Vol. 47, No. 1 Cross Ref The 2-distance coloring of the Cartesian product of cycles using optimal Lee codesDiscrete Applied Mathematics, Vol. 159, No. 18 Cross Ref Product Constructions for Perfect Lee CodesIEEE Transactions on Information Theory, Vol. 57, No. 11 Cross Ref Decoding q-ary lattices in the Lee metric Cross Ref Quasi-cross lattice tilings with applications to flash memory Cross Ref On perfect codes in Cartesian products of graphsEuropean Journal of Combinatorics, Vol. 32, No. 3 Cross Ref Basis arrays and successive packing for M-D interleaving4 September 2010 | Multidimensional Systems and Signal Processing, Vol. 22, No. 1-3 Cross Ref Dense error-correcting codes in the Lee metric Cross Ref Quotients of Gaussian graphs and their application to perfect codesJournal of Symbolic Computation, Vol. 45, No. 7 Cross Ref Codes in Permutations and Error Correction for Rank ModulationIEEE Transactions on Information Theory, Vol. 56, No. 7 Cross Ref High dimensional error-correcting codes Cross Ref Quasi-perfect geometrically uniform codes derived from graphs over Gaussian integer rings Cross Ref Perfect graph codes over two dimensional lattices Cross Ref Correcting Charge-Constrained Errors in the Rank-Modulation SchemeIEEE Transactions on Information Theory, Vol. 56, No. 5 Cross Ref Two-Dimensional Patterns With Distinct Differences—Constructions, Bounds, and Maximal AnticodesIEEE Transactions on Information Theory, Vol. 56, No. 3 Cross Ref Bounding the minimal Euclidean distance for any PSK block codes of alphabet size 8 Cross Ref Weighted codes in Lee metrics27 February 2009 | Designs, Codes and Cryptography, Vol. 52, No. 2 Cross Ref Weighted perfect codes in Lee metricElectronic Notes in Discrete Mathematics, Vol. 34 Cross Ref Perfect Codes From Cayley Graphs Over Lipschitz IntegersIEEE Transactions on Information Theory, Vol. 55, No. 8 Cross Ref Error-Correction of Multidimensional BurstsIEEE Transactions on Information Theory, Vol. 55, No. 3 Cross Ref Adaptive identification in graphsJournal of Combinatorial Theory, Series A, Vol. 115, No. 7 Cross Ref Two-Dimensional Array Coloring With Many ColorsIEEE Transactions on Information Theory, Vol. 54, No. 9 Cross Ref Error-correcting codes for rank modulation Cross Ref Graph-based metrics over QAM constellations Cross Ref Modeling hexagonal constellations with Eisenstein-Jacobi graphs4 May 2008 | Problems of Information Transmission, Vol. 44, No. 1 Cross Ref Perfect Codes for Metrics Induced by Circulant GraphsIEEE Transactions on Information Theory, Vol. 53, No. 9 Cross Ref Error-Correction of Multidimensional Bursts Cross Ref Optimal interleaving schemes for correcting two-dimensional cluster errorsDiscrete Applied Mathematics, Vol. 155, No. 10 Cross Ref A generalization of the pentomino exclusion problem: Dislocation of graphsDiscrete Mathematics, Vol. 307, No. 3-5 Cross Ref Optimal Lee-Type Local Structures in Cartesian Products of Cycles and PathsSimon Špacapan26 September 2007 | SIAM Journal on Discrete Mathematics, Vol. 21, No. 3AbstractPDF (220 KB)Nonexistence of face-to-face four-dimensional tilings in the Lee metricEuropean Journal of Combinatorics, Vol. 28, No. 1 Cross Ref Optimal Interleaving Schemes for Two-Dimensional ArraysIEEE Transactions on Information Theory, Vol. 52, No. 9 Cross Ref A Generalization of Perfect Lee Codes over Gaussian Integers Cross Ref Frequency Coded Waveforms for Adaptive Waveform Radar Cross Ref Optimal Interleaving on ToriAnxiao (Andrew) Jiang, Matthew Cook, and Jehoshua Bruck5 December 2006 | SIAM Journal on Discrete Mathematics, Vol. 20, No. 4AbstractPDF (542 KB)Perfect codes in Cartesian products of hypercube and multidimensional gridElectronic Notes in Discrete Mathematics, Vol. 22 Cross Ref Characterizing r-perfect codes in direct products of two and three cyclesInformation Processing Letters, Vol. 94, No. 1 Cross Ref Optimal 2-D Interleaving With Latin RectanglesIEEE Transactions on Information Theory, Vol. 51, No. 3 Cross Ref On the Optimality of Coloring with a LatticeYael Ben-Haim and Tuvi Etzion1 August 2006 | SIAM Journal on Discrete Mathematics, Vol. 18, No. 4AbstractPDF (431 KB)Interleaving for combating bursts of errorsIEEE Circuits and Systems Magazine, Vol. 4, No. 1 Cross Ref Frequency-coded waveforms for enhanced delay-doppler resolutionIEEE Transactions on Information Theory, Vol. 49, No. 11 Cross Ref Perfect r-domination in the Kronecker product of two cycles, with an application to diagonal/toroidal meshInformation Processing Letters, Vol. 87, No. 3 Cross Ref Tilings with Generalized Lee Spheres Cross Ref Optimal 2-D interleaving for robust multimedia transmission Cross Ref A new two-dimensional interleaving technique using successive packingIEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, Vol. 49, No. 6 Cross Ref Decoding a class of Lee metric codes over a Galois ringIEEE Transactions on Information Theory, Vol. 48, No. 4 Cross Ref Perfect r-domination in the Kronecker product of three cyclesIEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, Vol. 49, No. 1 Cross Ref On the Use of Duality and Geometry in Layouts for ATM Networks1 June 2001 Cross Ref Duality in ATM Layout Problems14 February 2000 Cross Ref Interleaving schemes for multidimensional cluster errorsIEEE Transactions on Information Theory, Vol. 44, No. 2 Cross Ref On domination numbers of Cartesian product of pathsDiscrete Applied Mathematics, Vol. 80, No. 2-3 Cross Ref On optimal graphs embedded into paths and rings, with analysis using l 1-spheres17 June 2005 Cross Ref Bibliography Cross Ref Complexity Cross Ref On the Nonexistence of Perfect Codes in the Johnson SchemeTuvi Etzion12 July 2006 | SIAM Journal on Discrete Mathematics, Vol. 9, No. 2AbstractPDF (1216 KB)Lee-metric BCH codes and their application to constrained and partial-response channelsIEEE Transactions on Information Theory, Vol. 40, No. 4 Cross Ref Variable Length Perfect CodesJournal of Information and Optimization Sciences, Vol. 13, No. 1 Cross Ref The file distribution problem for processor networks8 June 2005 Cross Ref The les association scheme27 May 2005 Cross Ref Bibliography Cross Ref Constructions and properties of Costas arraysProceedings of the IEEE, Vol. 72, No. 9 Cross Ref Bibliography Cross Ref Derived thingsJournal of Combinatorial Theory, Series A, Vol. 20, No. 1 Cross Ref Optimization and the Geometry of Numbers: Packing and CoveringThomas L. Saaty and Joyce M. Alexander18 July 2006 | SIAM Review, Vol. 17, No. 3AbstractPDF (3800 KB)Splittings of cyclic groups, tilings of Euclidean space, and perfect shift codes Cross Ref On the optimality of coloring with a lattice Cross Ref Optimal interleaving schemes for correcting 2-D cluster errors Cross Ref Optimal t-interleaving on tori Cross Ref User traffic multiplexing on OFDM downlink Cross Ref Frequency coded waveforms for enhanced delay-Doppler resolution Cross Ref Volume 18, Issue 2| 1970SIAM Journal on Applied Mathematics History Submitted:27 January 1968Published online:01 August 2006 InformationCopyright © 1970 © Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0118025Article page range:pp. 302-317ISSN (print):0036-1399ISSN (online):1095-712XPublisher:Society for Industrial and Applied Mathematics
