Switching Systems Synthesis Method Using Permuted Gray Code Tables (PGC Method)

  • Cesar Troya-Sherdek International University of Ecuador
  • Valentin Salgado-Fuentes Technical University of Denmark
  • Jaime Molina Kachariy Higher Technical Institute
  • Gustavo Moreno Kachariy Higher Technical Institute
Keywords: Boolean functions, discrete problems, Gray Code, Hamiltonian Paths, hypercube, switching systems

Abstract

Finding the shortest function on switching systems is a necessity for the development of efficient automatic systems. Currently, several methodologies aim to solve this need with different techniques. This article proposes a new methodology to find a propositional formula that describes a switching system problem using several truth tables which are based on an original one; these tables are generated using Gray Code principles and permutations. As it will be shown, the used code has a direct relation to the Hamiltonian paths, where each permutation is a different connection in a hypervolume, and each node is represented as a bit combination. An algorithm was developed using MATLAB and compared with the solutions from the software Boole-Deusto to verify and validate the applicability and implementation of the method. Finally, examples of execution, computational cost comparison and future work proposals are presented.

DOI

Downloads

Download data is not yet available.

References

J. P. Roth, "Algebraic topological methods for the synthesis of switching systems. I.," Transactions of the American Mathematical Society 88.2, pp. 301-326, 1958.

W.V. Quine "A way to simplify truth functions." The American mathematical monthly 62.9, pp. 627-631, 1955.

M. Karnaugh, "The map method for synthesis of combinational logic circuits," Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics 72.5, pp. 593-599, 1963.

R.B Hurley, "Probability maps," IEEE Transactions on Reliability 12.3 pp. 39-44, 1963.

Astola, Jaakko, and R. Stankovic. “Fundamentals of Switching Theory and Logic Design A Hands-on Approach,” Springer, 2006.

E.W. Veitch, "A chart method for simplifying truth functions," Proceedings of the ACM national meeting (Pittsburgh), 1952.

Bitner, R James., Gideon Ehrlich, and E.M. Reingold. "Efficient generation of the binary reflected Gray code and its applications," Communications of the ACM 19.9, pp. 517-521, 1976.

W. Press, et al. Numerical recipes in Fortran 77: volume 1, volume 1 of Fortran numerical recipes: the art of scientific computing. Cambridge university press. 1992.

J. Zubia, J. García, Sanz Martínez, and S. Borja, "BOOLE-DEUSTO, la aplicación para sistemas digitales," 2001.

J. Dybizbanski, and A. Szepietowski, "Hamiltonian paths in hypercubes with local traps," Information Sciences 375, pp. 258-270, 2007.

K. Sankar, V. Jaya, M. Pandharipande, and P. S. Moharir. "Generalized gray codes," Proceedings of 2004 International Symposium on Intelligent Signal Processing and Communication Systems, ISPACS IEEE. 2004.

D. Benavides, “Diseño, implementación y evaluación de unidades didácticas de matemáticas en MAD 2,” pp. 265. 2019.

L. Egghe and I. Ravichandra Rao, "Classification of growth models based on growth rates and its applications," Scientometrics 25.1, pp. 5-46, 1992.

Published
2021-01-01
How to Cite
[1]
C. Troya-Sherdek, V. Salgado-Fuentes, J. Molina, and G. Moreno, “Switching Systems Synthesis Method Using Permuted Gray Code Tables (PGC Method)”, LAJC, vol. 8, no. 1, pp. 118-129, Jan. 2021.
Section
Research Articles for the Regular Issue