Optimization of the acyclic adders of binary codes

Authors

DOI:

https://doi.org/10.15587/2312-8372.2018.133694

Keywords:

acyclic model, prefix model, directed acyclic graph, Ling Adder, Kogge-Stone Adder, Brent-Kung Adder

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

Downloads

Published

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

Issue

Vol. 3 No. 2(41) (2018): Information and Control Systems

Section

Mathematical Modeling: Original Research

License

Copyright (c) 2018 Mykhailo Solomko

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.