International Research Journal of Innovations in Engineering and Technology - IRJIET International Open Access, Monthly, Peer Reviewed, Reputed Journal ISSN (online): 2581-3048

Impact Factor (2025): 6.9

DOI Prefix: 10.47001/IRJIET

AC’s Method of One-line Boolean Symmetry Detection

Abstract

The detection of symmetries in a switching function is an NP-complete problem. In this paper a single line solution for detecting total symmetry been proposed. The proposed method exploits the linearity among Boolean terms to obtain the unique transformation matrix associated with every linear function. A theorem has been proved which relates the equality of coefficients in the transformation matrix, of the variables with symmetry detection.  By using the proposed methodology, the simplicity for detecting total symmetries been improved in terms of cost in time-space domain.

Country : India

1 Anirban Chakraborty

  1. Assistant Professor, Barrackpore Rastraguru Surendranath College, Department of Computer Science, Barrackpore, Kolkata -120, West Bengal, India

IRJIET, Volume 7, Issue 9, September 2023 pp. 63-68

doi.org/10.47001/IRJIET/2023.709006

Full Paper
Download

References

  1. Stephen Boyd, Persi Diaconis, Pablo Parrilo and Lin Xiao, “Fastest Mixing Markov Chain on Graphs with Symmetries”. SIAM Journal on Optimization, vol. 20, issue 2, pp. 792–819, DOI: https://doi.org/10.1137/070689413.
  2. Kuo-Hua Wang and Jia-Hung Chen, “Symmetry Detection for Incompletely Specified Functions”. Proceedings of the 41st annual Design Automation Conference, pp 434-437, San Diego, California, USA, June 2004.
  3. J. E. Rice and J. C. Muzio, “Anti symmetries in the Realization of Boolean Functions”, Proceedings IEEE International Symposium on Circuits and Systems, vol. 4 pp. 69-72, 2002, DOI:10.1109/ISCAS.2002.1010390.
  4. Stjepan Picek, R. I. (Bob) McKay, Roberto Santana, San Sebastian, “Fighting the Symmetries: The Structure of Cryptographic Boolean Function Spaces”. Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp 457–464 Madrid, Spain, July 2015.
  5. Mitchell A. Thornton, Member, IEEE, and V. S. S. Nair, “Efficient Calculation of Spectral Coefficients and Their Applications”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume: 14, Issue: 11, pp 1328-1341, Nov 1995.
  6. Shao Jie Zhang, Jun Sun, Chengnian Sun, Yang Liu, Junwei Ma and Jin Song Dong, "Constraint-Based Automatic Symmetry Detection, Proceedings 28th IEEE/ACM International Conference on Automated Software Engineering (ASE), Silicon Valley, CA, USA, 2013
  7. A.KP.T. Darga, K. A. Sakallah, and I. L. Markov. Faster Symmetry Discovery using Sparsity of Symmetries, In Proceedings of the 45th Annual Design Automation Conference, DAC 7808, pp 149-154, New York, NY, USA.
  8. 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.
  9. S. Das and C. Sheng, “On detecting total or partial symmetry of switching functions”, IEEE Transaction on Computers, pp352-355,1971.DOI:10.1109/PROC.1970.7777.
  10. Z. Kohavi, Switching and Finite Automata Theory, Tata McGraw-Hill publishers, Second Edition, pp.126- 127, 1978.
  11. S. Guha, K. Saha and N. Sen “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, vol. 1, issue 10, December 2015.
  12. C. Mearsand, M. Garciade la Banda and M. Wallace." On implementing symmetry detection". Proceedings Sixth International Workshop Cite des Congres, Nantes, France, September 2006.
  13. C. E. Shannon, “A symbolic analysis of relay and switching circuits,” AIEE Transaction, vol. 57, pp. 713-723, 1938.
  14. G. Birkhoff and S. MacLane, “A Survey of Modern Algebra”, New York: Macmillan, 1953.
  15. S. H. Caldwell, “The recognition and identification of symmetric switching functions”, Trans. AIEE (Communication and Electronics), vol. 73, issue 1, pp. 142-146, May 1954.
  16. E. J. McCluskey, “Detection of group invariance or total symmetry of a Boolean function,” Bell Sys. Technical Journal, vol. 35, pp. 1445-1453, November 1956.
  17. 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.
  18. T. Singer, “Some uses of truth tables”, Proceedings International Symposium on the Theory of Switching (Part I), pp. 125-133, April 1959.
  19. A.K. Choudhury and M. S. Basu, “On detection of group invariance or total symmetry of a Boolean function”, Indian Journal of Physics, vol. 36, pp.31-42, January 1962.
  20. S. R. Das, “Detection of invariance, total symmetry and partial symmetry of switching functions”, Indian Journal of Physics, vol. 37, pp. 219-232, April 1963.
  21. C. L. Sheng, “Detection of totally symmetric Boolean functions,” IEEE Trans. Electronic Computers (Short Notes), vol. EC-14, pp. 924-926, December 1965.
  22. V. N. Kravets, K. A. Sakallah, “Generalized Symmetries in Boolean Functions,” In Digest of IEEE International Conference on Computer-Aided Design (ICCAD), pages 526-532, San Jose, California, November 2000DOI: 10.1109/ICCAD.2000.896526.
  23. 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.
  24. 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.
  25. Subhajit Guha, Satrajit Ghosh, Partha Pratim Das, “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-694-3, pp.731-736, March 2012.  DOI:10.1109/RAIT.2012.6194545.
  26. Saeyang Yang, Logic Synthesis and Optimization Benchmarks User Guide Version 3.0, Report issued at MCNC International Workshop on Logic Synthesis, https://ddd.fit.cvut.cz/prj/Benchmarks/LGSynth91.pdf, 1991.
  27. D. Margalit and J. Rabinoff, “Interactive Linear Algebra”, Georgia Institute of Technology, 2017©, pp. 114-153, Jun 2019, https://textbooks.math.gatech.edu/ila/ila.pdf

Copyright @ 2026-2017 IRJIET. All Right Reserved.

Developed by Byzero Technologies