Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-26T01:06:20.225Z Has data issue: false hasContentIssue false
  • English
  • Français

Sphere Packings and Error-Correcting Codes

Published online by Cambridge University Press:  20 November 2018

John Leech  and
N. J. A. Sloane
John Leech
Affiliation:
University of Stirling, Stirling, Scotland
N. J. A. Sloane
Affiliation:
Bell Telephone Laboratories, Murray Hill, New Jersey
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Error-correcting codes are used in several constructions for packings of equal spheres in n-dimensional Euclidean spaces En. These include a systematic derivation of many of the best sphere packings known, and construction of new packings in dimensions 9-15, 36, 40, 48, 60, and 2m for m ≧ 6. Most of the new packings are nonlattice packings. These new packings increase the previously greatest known numbers of spheres which one sphere may touch, and, except in dimensions 9, 12, 14, 15, they include denser packings than any previously known. The density Δ of the packings in En for n = 2m satisfies

In this paper we make systematic use of error-correcting codes to obtain sphere packings in En, including several of the densest packings known and several new packings.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 23 , Issue 4 , August 1971 , pp. 718 - 745
Copyright
Copyright © Canadian Mathematical Society 1971

References

1. Assmus, E. F., Jr. and Mattson, H. F., Jr., New 5-designs, J. Combinatorial Theory 6 (1969), 122–151.Google Scholar
2. Assmus, E. F., Jr. and Mattson, H. F., Jr., Algebraic theory of codes. II, Applied Research Laboratory, Sylvania Electronic Systems, Waltham, Mass., Report AFCRL-69-0461, 15 October, 1969.Google Scholar
3. Barnes, E. S. and Wall, G. E., Some extreme forms defined in terms of Abelian groups, J. Australian Math. Soc. 1 (1959), 47–63.Google Scholar
4. Berlekamp, E. R., Algebraic Coding Theory (McGraw-Hill, New York, 1968).Google Scholar
5. Berlekamp, E. R., Coding theory and the Mathieu groups, Information and Control 18 (1971), 40–64.Google Scholar
6. Chen, C. L., Computer results on the minimum distance of some binary cyclic codes, IEEE Trans. Information Theory 16 (1970), 359–360.Google Scholar
7. Conway, J. H., A characterization of Leech's lattice, Invent, math. 7 (1969), 137–142.Google Scholar
8. Conway, J. H., A group of order 8,315,553,613,086,720,000, Bull. London Math. Soc. 1 (1969), 79–88.Google Scholar
9. Conway, J. H., (private communication).Google Scholar
10. Coxeter, H. S. M., Extreme forms, Can. J. Math. 8 (1951), 391–441.Google Scholar
11. Coxeter, H. S. M., An upper bound for the number of equal nonoverlapping spheres that can touch another of the same size, Proc. Symp. Pure Math, Vol VII (Providence, 1963), 53–71.Google Scholar
12. Coxeter, H. S. M. and Todd, J. A., An extreme duodenary form, Can. J. Math. 5 (1953), 384–392.Google Scholar
13. Golay, M. J. E., Notes on digital coding, Proc. I.R.E. 37 (1949), 637.Google Scholar
14. Golay, M. J. E., Binary coding, IRE Trans. Information Theory 4 (1954), 23–28.Google Scholar
15. Hanani, H., On quadruple systems, Can. J. Math. 12 (1960), 145–157.Google Scholar
16. Julin, D., Two improved block codes, IEEE Trans. Information Theory 11 (1965), 459.Google Scholar
17. Kasami, T. and Tokura, N., Some remarks on BCH bounds and minimum weights of binary primitive BCH codes, IEEE Trans. Information Theory 15 (1969), 408–413.Google Scholar
18. Leech, J., Some sphere packings in higher space, Can. J. Math. 16 (1964), 657–682.Google Scholar
19. Leech, J., Notes on sphere packings, Can. J. Math. 19 (1967), 251–267.Google Scholar
20. Leech, J., Five-dimensional nonlattice sphere packings, Can. Math. Bull. 10 (1967), 387–393.Google Scholar
21. Leech, J., Six and seven dimensional nonlattice sphere packings, Can. Math. Bull. 12 (1969), 151–155.Google Scholar
22. Leech, J. and Sloane, N. J. A., New sphere packings in dimensions 9-15, Bull. Amer. Math. Soc. 76 (1970), 1006–1010.Google Scholar
23. Leech, J. and Sloane, N. J. A., New sphere packings in more than 32 dimensions, Proceedings of Second Chapel Hill Conference on Combinatorial Mathematics and its Applications, University of North Carolina at Chapel Hill, 1970, pp. 345–355.Google Scholar
24. Mann, H. B., On the number of information symbols in Bose-Chaudhuri codes, Information and Control 5 (1962), 153–162.Google Scholar
25. Peterson, W. W., Err or-correcting Codes (The M.I.T. Press, Cambridge, Mass., 1961).Google Scholar
26. Pierce, J. N. (private communication).Google Scholar
27. Pless, V., On a new family of symmetry codes and related new five-designs, Bull. Amer. Math. Soc. 75 (1969), 1339–1342.Google Scholar
28. Pless, V., Symmetry codes over GF﹛3) and new five-designs (to appear in J. Combinatorial Theory).Google Scholar
29. Pless, V., (private communication).Google Scholar
30. Rogers, C. A., The packing of equal spheres, Proc. London Math. Soc. 8 (1958), 609–620.Google Scholar
31. Rogers, C. A., Packing and Covering (Cambridge University Press, Cambridge, 1964).Google Scholar
32. Sloane, N. J. A. and Seidel, J. J., A new family of nonlinear codes obtained from conference matrices, Ann. New York Acad. Sci. 175 (1970), 363–365.Google Scholar
33. Sloane, N. J. A. and Whitehead, D. S., A new family of single-error correcting codes, IEEE Trans. Information Theory 16 (1970), 717–719.Google Scholar
34. Thompson, J. G. (private communication).Google Scholar
35. Todd, J. A., A representation of the Mathieu group Mu as a collineation group, Ann. Mat. Pura Appl. 71 (1966), 199–238.Google Scholar
36. Watson, G. L., The number of minimum points of a positive quadratic form (to appear).Google Scholar
37. Witt, E., Über Steinersche Système, Abh. Math. Sem. Hansischen Univ. 12 (1938), 256–264 Google Scholar