A Parametric based Technique for Detection of Total and Multiform Symmetric Switching Functions in Logic Synthesis

Print
IJCA Proceedings on International Conference on Microelectronic Circuit and System
© 2015 by IJCA Journal
MICRO 2015 - Number 1
Year of Publication: 2015
Authors:
Subhajit Guha
Kritanta Saha
Nilkantha Sen

Subhajit Guha, Kritanta Saha and Nilkantha Sen. Article: A Parametric based Technique for Detection of Total and Multiform Symmetric Switching Functions in Logic Synthesis. IJCA Proceedings on International Conference on Microelectronic Circuit and System MICRO 2015(1):1-10, December 2015. Full text available. BibTeX

@article{key:article,
	author = {Subhajit Guha and Kritanta Saha and and Nilkantha Sen},
	title = {Article: A Parametric based Technique for Detection of Total and Multiform Symmetric Switching Functions in Logic Synthesis},
	journal = {IJCA Proceedings on International Conference on Microelectronic Circuit and System},
	year = {2015},
	volume = {MICRO 2015},
	number = {1},
	pages = {1-10},
	month = {December},
	note = {Full text available}
}

Abstract

An innovative as well as illuminating approach for detection of total and multiform symmetric switching functions is proposed. This method is based on modulo-2 sum between existent parameters rather than using maps, charts or large tables. The invariant properties are being revealed by the set of true minterms in accordance with the logical construction of existent parameters resulting in the reduction of complexity in time-space domain.

References

  • C. E. Shannon, "A symbolic analysis of relay and switching circuits,"AIEE Trans. , vol. 57, pp. 713-723, 1938.
  • G. Birkhoff and S. MacLane, "A Survey of Modern Algebra", New York: Macmillan, 1953.
  • S. H. Caldwell, "The recognition and identification of symmetric switching functions," Trans. AIEE (Communication and Electronics), vol. 73, pt. 1,pp. 142-146, May 1954
  • A. A. Mullin and W. G. Kellner, "A residue test for Boolean functions," unpublished teaching memorandum, Dept. of Elec. Engrg. , M. I. T. , Cambridge, Mass. , 1955.
  • E. J. McCluskey, "Detection of group invariance or total symmetry of a Boolean function," Bell Sys. Tech. J. , vol. 35, pp. 1445-1453, November 1956.
  • M. P. Marcus, "The detection and identification of symmetric switching functions with the use of tables of combinations," IRE Trans. on Electronic Computers(Correspondence), vol. EC-5, pp. 237-239, December 1956.
  • T. Singer, "Some uses of truth tables", Proc. Int. Symp. on the Theory of Switching (Part I), pp. 125-133, April 1959.
  • A. K. Choudhury and M. S. Basu, "On detection of group invariance or total symmetry of a Boolean function", Indian J. Phys. , vol. 36, pp. 31-42, January 1962.
  • S. R. Das, "Detection of invariance, total symmetry and partial symmetry of switching functions", Indian J. Phys. , vol. 37, pp. 219-232,April 1963.
  • R. F. Arnold and M. A. Harrison, "Algebraic properties of symmetric and partially symmetric Boolean functions," IEEE Trans. Electronic Computers, vol. EC-12, pp. 244-251, June 1963.
  • A. Mukhopadhyay, "Detection of total or partial symmetry of a switching function with the use of decomposition charts," IEEE Trans. on Electronic Computers(Correspondence), vol. EC-12, pp. 553-557, October 1963.
  • C. L. Sheng, "Detection of totally symmetric Boolean functions," IEEE Trans. Electronic Computers (Short Notes), vol. EC-14, pp. 924-926, December 1965.
  • S. Das and C. Sheng, "On detecting total or partial symmetry of switching functions", IEEE Trans, on Computers, 352-355, 1971. DOI: 10. 1109/PROC. 1970. 7777
  • Z. Kohavi, Switching and Finite Automata Theory, Tata McGraw-Hill publishers, Second Edition, pp. 126-127,1978
  • C. C. Tsai and M. MarekSadowska, "Generalized Reed Muller forms as a tool to detect symmetries," IEEE Trans. Comput. , vol. 45, pp. 33-40, Jan. 1996. DOI: 10. 1109/ISCAS. 1994. 408811
  • V. N. Kravets, K. A. Sakallah, "Generalized Symmetries in Boolean Functions," International Conference on ComputerAided Design (ICCAD'00), 526, 2000. DOI: 10. 1109/ICCAD. 2000. 896526
  • T. Sasao, "A new expansion of symmetric functions and their application to non-disjoint functional decompositions for LUT type FPGAs," IEEE International Workshop on Logic Synthesis, pp. 105-110, 2000.
  • Peter M Maurer, "Using Conjugate Symmetries to Enhance Gate-Level Simulations", Dept. of Computer Science, Baylor University #97356 WACO, TX-76798-7356, 2006
  • J. S. Zhang, A. Mishchenko, R. Brayton and M. Chrzanowska-Jeske, "Symmetry detection for large Boolean functions using circuit representation, simulation, and Satisfiability". 43rd ACM/IEEE Design Automation Conference, USA, CA,ISBN:1-59593-381-6, pp. 510-515, 2006. DOI: 10. 1109/DAC. 2006. 229269
  • N. Kettle, A. King, "An Anytime Algorithm for Generalized Symmetry Detection in ROBDDs", Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, pp. 764 – 777, Volume: 27 Issue: 4, April 2008.
  • SubhajitGuha, SatrajitGhosh, ParthaPratimDas, "A Novel Approach for Identification of Symmetric Switching Function", Recent Advances in Information Technology (RAIT),1st International Conference, RAIT, India, IEEE,ISBN: 978-1-4577-0694-3,pp. 731-736,March2012. DOI:10. 1109/RAIT. 2012. 6194545
  • Peter M Maurer, "Using Conjugate Symmetries to Enhance Gate-Level Simulations", Dept. of Computer Science, Baylor University #97356 WACO, TX-76798-7356, 2006