Optimization of the acyclic adders of binary codes

Authors

• Mykhailo Solomko National University of Water and Environmental Engineering, 11, Soborna str., Rivne, Ukraine, 33028, Ukraine

Abstract

The object of research is a prefix model for calculating adding and transport signals in a parallel adder circuit with a parallel transfer method. One of the most problematic places in the prefix model is the process of generating adding and carry signals, in which the beginning of the prefix calculation is provided from the first bit of the circuit. This leads, in the end, to excessive accumulation and complications of the hardware part of the device.

In the course of the research, a mathematical model is used to calculate the adding and carry signals in a parallel adder circuit based on the properties of a directed acyclic graph with two typical operations.

The complexity of the logical structure of the adder of binary codes is reduced, the depth of the circuit is reduced and the total length of the connecting wires is reduced. This is due to the fact that the proposed method for calculating adding and transport signals has a number of features of the device circuit synthesis, in particular, the application of a mathematical model based on the properties of an acyclic graph is calculated for:

• process of sequential (for lower order devices) and parallel calculation of adding and carry signals, which, in the end, reduces the complexity of the hardware of the device and does not increase the depth of the circuit;
• comparison of the number of computational steps of an oriented acyclic graph with the number of transfers of one to the high-order bit in the adder circuit, which allows to determine the optimal number of computational steps for the structure of the device.

Due to this, it is possible to obtain optimal values for the complexity of the structure and the depth of the adder circuit. The connection between the number of computational steps of an oriented acyclic graph and the number of transfers in the parallel adder circuit with a parallel transport method indicates the expediency of comparing the structure of the adder with the corresponding oriented acyclic graph.

In comparison with similar known structures of 8-bit prefix adders, this provides an increase in the quality index of 8-bit acyclic adders, for example, by power consumption, the chip area, depending on the chosen structure, by 10–40 %.

Author Biography

Mykhailo Solomko, National University of Water and Environmental Engineering, 11, Soborna str., Rivne, Ukraine, 33028

PhD, Associate Professor

Department of Computer Engineering

References

1. Brent, R. P., Kung, H. T. (1982). A regular layout for parallel adders. IEEE Transactions on Computers, 31 (3), 260–264. doi: http://doi.org/10.1109/tc.1982.1675982
2. Han, T., Carlson, D. A. (1987). Fast area-efficient VLSI adders. IEEE 8th Symposium on Computer Arithmetic (ARITH). doi: http://doi.org/10.1109/arith.1987.6158699
3. Kogge, P. M., Stone, H. S. (1973). A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations. IEEE Transactions on Computers, 22 (8), 786–793. doi: http://doi.org/10.1109/tc.1973.5009159
4. Ladner, R. E., Fischer, M. J. (1980). Parallel Prefix Computation. Journal of the ACM, 27 (4), 831–838. doi: http://doi.org/10.1145/322217.322232
5. Solomko, M., Olshansky, P. (2017). The Parallel Acyclic Adder. 2017 14th International Conference The Experience of Designing and Application of CAD Systems in Microelectronics (CADSM). Lviv, 125–129.
6. Balasubramanian, P., Jacob Prathap Raj, C., Anandi, S., Bhavanidevi, U., Mastorakis, N. E. (2013). Mathematical Modeling of Timing Attributes of Self-Timed Carry Select Adders. Recent Advances in Circuits, Systems, Telecommunications and Control, 228–243. Available at: http://www.wseas.us/e-library/conferences/2013/Paris/CCTC/CCTC-34.pdf
7. Venkatanaga Kumar, G., Pushpalatha, C. H. (2016). Implementation of Carry Tree Adders and Compare with RCA and CSLA. International Journal of Emerging Engineering Research and Technology, 4 (1), 1–11. Available at: http://www.ijeert.org/pdf/v4-i1/1.pdf
8. Gedam, K. S., Zode, P. P. (2014). Parallel prefix han-carlson adder. International Journal of Research in Engineering and Applied Sciences, 2 (2), 81–84. Available at: http://mgijournal.com/pdf_new/electronics/swapna%20gedam-1.pdf
9. Krishna Kumari, V., Sri Chakrapani, Y., Kamaraju, M. (2013). Design and Characterization of Kogge-Stone, Sparse Kogge-Stone, Spanning tree and Brent-Kung Adders. International Journal of Scientific & Engineering Research, 4 (10), 1502–1506. Available at: https://www.ijser.org/researchpaper/Design-and-Characterization-of-Koggestone-Sparse-Koggestone-Spanning-tree-and-Brentkung-Adders.pdf
10. Ramanathan, P., Vanathi, P. T. (2009). Hybrid Prefix Adder Architecture for Minimizing the Power Delay Product. World Academy of Science, Engineering and Technology International Journal of Electrical, Computer, Energetic, Electronic and Communication Engineering, 3 (4), 869–873. Available at: https://waset.org/publications/5272/hybrid-prefix-adder-architecture-for-minimizing-the-power-delay-product
11. Kaarthik, K., Vivek, C. (2016). Hybrid Han Carlson Adder Architecture for Reducing Power and Delay Middle-East. Journal of Scientific Research, 24, 308–313. Available at: https://www.idosi.org/mejsr/mejsr24(IIECS)16/48.pdf
12. Yagain, D., Vijaya, K. A., Baliga, A. (2012). Design of High-Speed Adders for Efficient Digital Design Blocks. ISRN Electronics, 2012, 1–9. doi: http://doi.org/10.5402/2012/253742
13. Krishna, B., Siva Durga Rao, P., Prasad, N. V. G. (2012). High Speed and Low Power Design of Parallel Prefix Adder. International Journal of Electronics & Communication Technology, 3 (4), 472–475. Available at: http://www.iject.org/vol34/3/a572
14. Aktan, M., Baran, D., Oklobdzija, V. G. (2015). Minimizing Energy by Achieving Optimal Sparseness in Parallel Adders. 2015 IEEE 22nd Symposium on Computer Arithmetic, 10–17. doi: http://doi.org/10.1109/arith.2015.13
15. Anitha, R., Bagyaveereswaran, V. (2012). High performance parallel prefix adders with fast carry chain logic. International Journal of Advanced Research in Engineering and Technology (IJARET), 3 (2). Available at: https://www.slideshare.net/iaemedu/high-performance-parallel-prefix-adders-with-fast-carry-chain-logic
16. Vozna, N. Ya., Krulikovskyi, B. B., Hryha, V. M., Davletova, A. Ya., Nykolaichuk, Ya. M. (11.12.2017). Kombinatsiinyi sumator. Patent 115751 UA, MPK G 06 F 7/501 (2006.01). Filed: 13.02.2017. Bul. No. 23. Available at: http://uapatents.com/6-115751-kombinacijjnijj-sumator.html
17. Gurkayna, F. K., Leblebicit, Y., Chaouati, L., McGuinness, P. J. (2000). Higher radix Kogge-Stone parallel prefix adder architectures. 2000 IEEE International Symposium on Circuits and Systems. Emerging Technologies for the 21st Century. Proceedings (IEEE Cat No. 00CH36353). Presses Polytech. Univ. Romandes. doi: http://doi.org/10.1109/iscas.2000.857516
18. Knowles, S. (1999). A family of adders. Proceedings 14th IEEE Symposium on Computer Arithmetic (Cat. No. 99CB36336). IEEE Comput. Soc. doi: http://doi.org/10.1109/arith.1999.762825
19. Beaumont-Smith, A., Lim, C.-C. (2001). Parallel prefix adder design. Proceedings 15th IEEE Symposium on Computer Arithmetic. ARITH-15 2001. IEEE Comput. Soc. doi: http://doi.org/10.1109/arith.2001.930122
20. Zimmermann, R. (1999). Efficient VLSI implementation of modulo (2/sup n/±1) addition and multiplication. Proceedings 14th IEEE Symposium on Computer Arithmetic (Cat. No. 99CB36336). IEEE Comput. Soc. doi: http://doi.org/10.1109/arith.1999.762841
21. Zeydel, B. R., Baran, D., Oklobdzija, V. G. (2010). Energy-Efficient Design Methodologies: High-Performance VLSI Adders. IEEE Journal of Solid-State Circuits, 45 (6), 1220–1233. doi: http://doi.org/10.1109/jssc.2010.2048730
22. Govindarajulu, S., Vijaya Durga Royal, T. (2014). Design of Energy-Efficient and High-Performance VLSI Adders. International Journal of Engineering Research, 3 (2), 55–59. Available at: http://ijer.irponline.in/ijer/publication/v3si2/IJER_2014_NCSC%2013.pdf
23. Pinto, R., Shama, K. (2016). Efficient shift-add multiplier design using parallel prefix adder. International Journal of Control Theory and Applications, 9 (39), 45–53. Available at: http://serialsjournals.com/serialjournalmanager/pdf/1500377875.pdf
24. Solomko, M., Krulikovskyі, B. (2016). Study of carry optimization while adding binary numbers in the rademacher number-theoretic basis. Eastern-European Journal of Enterprise Technologies, 3 (4 (81)), 56–63. doi: http://doi.org/10.15587/1729-4061.2016.70355

2018-01-23

How to Cite

Solomko, M. (2018). Optimization of the acyclic adders of binary codes. Technology Audit and Production Reserves, 3(2(41), 55–65. https://doi.org/10.15587/2312-8372.2018.133694

Section

Mathematical Modeling: Original Research