Abstract
We present constructions of bases for a Hamming code having small width and height, i.e. number of 1s in each row and column in the corresponding matrix. Apart from being combinatorially interesting in their own right, these bases also lead to improved embeddings of a hypercube of cliques into a same-sized hypercube
This work was supported in part by an NSERC International Fellowship and ITRC.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
W. Aiello and T. Leighton, Coding theory, hypercube embeddings, and fault tolerance, Proc. of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 125–136, 1991. To appear in IEEE Trans. Computer.
E. Assmus, Jr and H. Mattson, On tactical configurations and error-correcting-codes, J. of Combin. Theory, vol. 2, pp. 243–257, 1967.
L. Babai, H. Oral and K. Phelps, Eulerian self-dual codes, SIAM J. Discrete Math., vol. 7, pp. 325–330, 1994.
R. H. Hamming, Error detecting and error correcting codes, Bell System Technical Journal, vol. 29, pp. 147–160, 1950.
T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays · Trees · Hypercubes, Morgan Kaufmann, San Mateo, California, 1992, Chapter 3, p. 430.
R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, California, 1983.
V. Pless, Introduction to the Theory of Error-Correcting-Codes, John Wiley and Sons, Inc., New York, 1989.
D. Pritikin, Graph embeddings from Hamming bases, DIMACS Workshops on Interconnection Networks and Mapping and Scheduling Parallel Computations, February 1994.
A. Reddy, Parallel input/output architectures for multiprocessors, Ph. D. dissertation. Dept. of Electronical and Computer Engineering, Univ. of Illinois, Urbana, 1990.
W. Stahnke, Primitive binary polynomials, Mathematics of Computation, vol. 124, pp. 977–980, 1973.
L. Zhang, A new bound for the width of Hamming codes, to appear in Proceedings of the 6th Inter. Conference on Computing and Information, 1994.
I. F. Blake, S.Gao and R. J. Lambert, Construction and distribution problem for irreducible trinomials over finite fields, To appear in Proceedings of the Holloway Conference on Finite Fields, Oxford University Press, 1995.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tromp, J., Zhang, L., Zhao, Y. (1995). Small weight bases for hamming codes. In: Du, DZ., Li, M. (eds) Computing and Combinatorics. COCOON 1995. Lecture Notes in Computer Science, vol 959. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0030838
Download citation
DOI: https://doi.org/10.1007/BFb0030838
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60216-3
Online ISBN: 978-3-540-44733-7
eBook Packages: Springer Book Archive