Home » Software Implementation of Break-Up Algorithm for Logic Minimization

Software Implementation of Break-Up Algorithm for Logic Minimization



Sahadev Roy

Dept. of ECE, NIT Arunachal Pradesh, India

Koustuvmoni Bharadwaj

Dept. of ECE, NIT Arunachachal Pradesh, Yupia, India
email: koustuv_red@yahoo.in



In this paper, we propose a robust technique to minimize multiple input digital circuits. This technique is simple and efficient to determine the minimum number of gates required to realize a multiple input digital circuit. Rather than using sizeable truth table for multiple input combinational circuits having at least one operation per minterms, proposed technique produced a minimal solution by breaking the minterms and arranging them in adjacent groups. This technique also overcomes the problems related to simplification using Karnaugh Map for more than four inputs system. Also we have proposed an algorithm to implement this technique in Java programming language and out provide results.


Breakup Algorithm;
Logic Minimization;
Prime Implicants;
Prime Implicant Table

Cited as

Sahadev Roy and, Koustuvmoni Bharadwaj “Software Implementation of Break-Up Algorithm for Logic Minimization,” International Journal of Advanced Engineering and Management, vol. 2, no. 6, pp. 141-145,  2017. DOI: https://doi.org/10.24999/IJOAEM/02060034
download pdf


  1. Roy, S., & Bhunia, C. T. (2015). On synthesis of combinational logic circuits. International J of Computer Applications127(1), 21-6. DOI: 10.5120/ijca2015906311.
  2. Veitch, E. W. (1952, May). A chart method for simplifying truth functions. In Proceedings of the 1952 ACM national meeting (Pittsburgh)(pp. 127-133). ACM..
  3. Karnaugh, M. (1953). The map method for synthesis of combinational logic circuits. Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics72(5), 593-599.
  4. Roy, S., & Bhunia, C. T. (2014, August). Constraints analysis for minimization of multiple inputs logic programming. In Proceedings of International Conference on Signal and Speech Processing ICSSP-14, India(pp. 61-64).
  5. Quine, W. V. (1952). The problem of simplifying truth functions. The American Mathematical Monthly59(8), 521-531.
  6. McCluskey, E. J. (1956). Minimization of Boolean functions. Bell Labs Technical Journal35(6), 1417-1444.
  7. McCluskey, E. J. (1956). Detection of group invariance or total symmetry of a Boolean function. Bell Labs Technical Journal35(6), 1445-1453.
  8. McCluskey, E. J. (1961, October). Minimal sums for Boolean functions having many unspecified fundamental products. In Switching Circuit Theory and Logical Design, 1961. SWCT 1961. Proceedings of the Second Annual Symposium on(pp. 10-17). IEEE.
  9. Green, D. H., & Khuwaja, G. A. (1993). Tabular simplification method for switching functions expressed in Reed-Muller algebraic form. International Journal of Electronics Theoretical and Experimental75(2), 297-314.
  10. Roy, S. (2016). Breakup Algorithm for Switching Circuit Simplifications. International Journal of Advanced Engineering and Management1(1), 1-11.
  11. Bose, S., & Saha, A. R. (1997). Some Algorithmic Improvements in Multi-Level Logic Minimisation. IETE Journal of Research43(5), 371-381.
  12. Das, S. R., & Jone, W. B. (1992). On random testing for combinational circuits with a high measure of confidence. IEEE transactions on systems, man, and cybernetics22(4), 748-754.
  13. Mohyuddin, N., Pakbaznia, E., & Pedram, M. (2011). Probabilistic error propagation in a logic circuit using the boolean difference calculus. In Advanced Techniques in Logic Synthesis, Optimizations and Applications(pp. 359-381). Springer New York.
  14. Dartu, F., Menezes, N., Qian, J., & Pillage, L. T. (1994, June). A gate-delay model for high-speed CMOS circuits. In Proceedings of the 31st annual Design Automation Conference(pp. 576-580). ACM.
  15. Roy, S. (2017). An Efficient Technique For Switching Functions Simplification. International Journal of Advanced Engineering and Management2(1), 21-28.
  16. Roy, S., & Bhunia, C. T. (2013). Minterms generations algorithm using weighted sum method. International Journal on Current Science & Technology1(2), 34-38.
  17. Roy, S., & Bhunia, C. T. (2014, January). Minimization algorithm for multiple input to two input variables. In Control, Instrumentation, Energy and Communication (CIEC), 2014 International Conference on(pp. 555-557). IEEE.
  18. Roy, S., & Bhunia, C. T. (2015). Simplification of Switching Functions Using Hex-Minterms. International Journal of Applied Engineering Research10(24), 45619-45624.
  19. Roy, S., Saha, R., & Bhunia, C. T. (2016). Multiple Inputs Combinational Logic Minimization by Minterms Set. In Proceedings of the International Conference on Recent Cognizance in Wireless Communication & Image Processing(pp. 133-140). Springer, New Delhi.
  20. Rudell, R., & Sangiovanni-Vincentelli, A. (1985, May). ESPRESSO-MV: Algorithms for multiple-valued logic minimization. In  IEEE Custom Integrated Circuits Conf(pp. 230-234).
  21. Wayne Current, K. (1979). Quaternary logic techniques for simplified integrated digital signal processing circuitry. International Journal of Electronics Theoretical and Experimental46(6), 611-620.
  22. Rao, P. S., & Jacob, J. (1998, January). A fast two-level logic minimizer. In VLSI Design, 1998. Proceedings., 1998 Eleventh International Conference on(pp. 528-533). IEEE.
  23. Poikonen, J. H., Lehtonen, E., & Laiho, M. (2012). On synthesis of Boolean expressions for memristive devices using sequential implication logic. IEEE Transactions on computer-aided design of Integrated Circuits and Systems31(7), 1129-1134.
  24. Taherifard, M., & Fathy, M. (2015). Improving logic function synthesis, through wire crossing reduction in quantum-dot cellular automata layout. IET Circuits, Devices & Systems9(4), 265-274.
  25. Rathore, T. S. (2014). Minimal Realizations of Logic Functions Using Truth Table Method with Distributed Simplification. IETE Journal of Education55(1), 26-32.
  26. Choudhuky, A., Basu, M. S., & Das, S. R. (1964). On a Method of Simplification of Multiple-output Switching Functions. International Journal of Electronics16(2), 223-237.
  27. Teodorovic, P., Dautovic, S., & Malbasa, V. (2013). Recursive Boolean formula minimization algorithms for implication logic. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems32(11), 1829-1833.