Abstract
In this paper we propose a semi-distributed self-diagnostic algorithm for Hypercube networks which is based on the use of a combinatorial structure known as the Hadamard matrix. We propose a model for providing fault- tolerance to the diagnostic scheme and to analyze the performance of the proposed diagnostic scheme. This analysis provides a tradeoff between the complexity of the algorithm and its level of fault-tolerance. However, the optimal solution to the diagnostic problem with desired level of fault- tolerance is shown to be related to the problem of finding the covering radius of a binary code which is a NP-hard problem for the Hypercube networks. We discuss various cases for n=8, 16, 32. However, for achieving a level of about 50% fault-tolerance for the proposed diagnostic scheme, we provide an optimal solution valid for all Hypercube networks.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
H. Sullivan, and T.R. Bashkow, ”A large scale, homogeneous, fully distributed parallel machine, I”, in Proc. IEEE 1977 Comp. Arch., 1977, pp. 105–117.
N.J.A. Sloane, and R.J. Dick, “On the Enumeration of Cosets of First Order Reed Muller Codes”, Proc. IEEE Inter. Conf. on Communication, Vol. 7, Montreal, Canada, June 1971, pp. 36.2–36.6.
E.R. Berlekemp, and L.R. Welch, “Weight Distributions of the Cosets of the (32,6) Reed-Muller Code”, IEEE Trans. on Inf. Theory, vol. IT-18, no. 1, Jan. 1972, pp. 203–207.
L. Huguet, “Coding Scheme for a Wire-tap Channel Using Regular Codes”, Discrete Math., 1985.
A.M. McLoughlin, “The Complexity of Computing the Covering Radius of a Code”, IEEE Trans. on Inf. Theory, vol. IT-30, no. 6, November 1984, pp. 800–804.
L.D. Baumert, “Cyclic Difference Sets”, Lect. Notes in Mathematics, vol. 182. London Mathematical Society, Springer-Verlag Pub. New York. 1971.
J. Maeng and M. Malek, “A comparison connection assignment for self-diagnosis of multiprocessor systems”, in Proc. FTFC-11, June 1981, pp. 173–175.
J.R. Armstrong and F.G. Gray, “Fault diagnosis in a Boolean n-cube array of microprocessors”, IEEE Trans. on Comp. vol. c-30, pp. 581–590, Aug. 1981.
P. Delsarte, “An Algebraic Approach to the Association Schemes of Coding Theory”, Phillips Res. Report Suppls. no. 10, 1973.
P. Solé, “Completely Regular and Completely Transitive Codes”, To appear in Disc rete Math.
J.G. Kuhl and S.M. Reddy, “Distributed fault-tolerance for large multiprocessor system”, Proc. 1980 Comp. Arch. Conf. France. May 1980.
M. Hall Jr., Combinatorial Theory, Blaisdell Publishing New York, 1967.
F.P. Preparata, G. Metze and R.T. Chien, ”On the connection assignment problem of diagnosable system”, IEEE Trans. on Computer, Dec. 1967, pp:848–854.
J.G. Kuhl and S.M. Reddy, ”Distributed fault-tolerance for large multiprocessor system”, Proc. 1980 Comp. Arch. Conf. France. May 1980.
F.J. MacWilliams and N.J.A. Sloane, The theory of error-correcting codes, vols. I and II, New York, North-Holland Publishing Co., 1977.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ghafoor, A., Solé, P. (1989). Covering in hypercubes. In: Cohen, G., Wolfmann, J. (eds) Coding Theory and Applications. Coding Theory 1988. Lecture Notes in Computer Science, vol 388. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0019860
Download citation
DOI: https://doi.org/10.1007/BFb0019860
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-51643-9
Online ISBN: 978-3-540-46726-7
eBook Packages: Springer Book Archive