Reduction and optimal performance of acyclic adders of binary codes

Authors

DOI:

https://doi.org/10.15587/1729-4061.2019.157150

Keywords:

acyclic model of addition of binary codes, prefix model, Ling Adder, Kogge-Stone Adder, Han-Carlson Adder

Abstract

The conducted studies have established the prospect of increasing productivity of computing components, in particular, combinational adders, based on applying principles of computation of digital signals of the acyclic model.

Application of the acyclic model is designed for:

‒ the process of series (for low-order digits of the adder circuit) and parallel (for the rest of the digits) computation of sum and carry signals. Due to this approach, it is possible, in the end, to reduce complexity of the hardware part of the device and not increase the circuit depth;

‒ setting the optimal number of computational steps.

The assumption that the number of computational steps of the directed acyclic graph with two logical operations (AND and XOR) determines optimal number of carry operations in the circuit of the n-bit parallel adder of binary codes was experimentally proved. In particular, this is confirmed by presence of the 8-bit parallel acyclic adder with the circuit depth of 8 standard 2-input logic elements. Connection between the number of computational steps of the acyclic graph and the number of operations of a unit carry to the high-order digit causes the process of comparison of the adder structure with the corresponding acyclic graph. The purpose of this comparison is to set the minimum sufficient number of carry operations for adding binary codes in the circuit of a parallel adder using the parallel carry method.

Use of the acyclic model is more advantageous in comparison with counterparts due to the following factors:

‒ less development costs since the acyclic model requires a simpler adder structure;

‒ presence of an optimization criterion, i.e. the number of computational steps of the acyclic graph indicates the minimum sufficient number of operations of a unit carry to the high-order digit.

This provides the possibility of obtaining optimum indicators of the adder structure complexity and circuit depth. Compared to counterparts of known 8-bit prefix adder structures, this provides a 14–31% increase in the 8-bit acyclic adder operation quality, e.g. power consumption or chip area depending on the chosen structure,

There are grounds to assert possibility of increasing productivity of computing components, in particular, binary code adders applying the principles of computation of digital signals of the acyclic model

Author Biographies

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

PhD, Associate Professor

Department of Computer Engineering

Petro Tadeyev, National University of Water and Environmental Engineering Soborna str., 11, Rivne, Ukraine, 33028

PhD, Doctor of Pedagogical Sciences, Professor

Department of Higher Mathematics

Yaroslav Zubyk, National University of Water and Environmental Engineering Soborna str., 11, Rivne, Ukraine, 33028

Senior Lecturer

Department of Applied Mathematics

Olena Hladka, National University of Water and Environmental Engineering Soborna str., 11, Rivne, Ukraine, 33028

PhD, Associate Professor

Department of Computer Science

References

  1. Brent, Kung (1982). A Regular Layout for Parallel Adders. IEEE Transactions on Computers, C-31 (3), 260–264. doi: https://doi.org/10.1109/tc.1982.1675982
  2. Han, T., Carlson, D. A. (1987). Fast area-efficient VLSI adders. 1987 IEEE 8th Symposium on Computer Arithmetic (ARITH). doi: https://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, C-22 (8), 786–793. doi: https://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: https://doi.org/10.1145/322217.322232
  5. Choi, Y., Swartzlander, E. E. (2005). Parallel Prefix Adder Design with Matrix Representation. 17th IEEE Symposium on Computer Arithmetic (ARITH'05). doi: https://doi.org/10.1109/arith.2005.35
  6. 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.
  7. Srinivasarao, B. N., Prathyusha, Ch. (2018). Power Efficient Parallel Prefix Adders. International Journal of Research, 5 (4), 472–477. Available at: https://pen2print.org/index.php/ijr/article/view/12158/11483
  8. Class ECE6332 Fall 12 Group-Fault-Tolerant Reconfigurable PPA. Available at: http://venividiwiki.ee.virginia.edu/mediawiki/index.php/ClassECE6332Fall12Group-Fault-Tolerant_Reconfigurable_PPA
  9. Ganesh Senthil, R., Kalaimathi, R. (2018). Design and Analysis of Kogge-Stone and Han-Carlson Adders in 130nm CMOS Technology. International Journal of Research, 05 (07), 1063–1068. Available at: https://pen2print.org/index.php/ijr/article/view/13190/
  10. Ananda Kumari, M., Loknadh, Ch. (2018). Design an Efficient Fault Tolerant Kogge Stone Adder. International Journal of Research, 05 (16), 1446–1449. Available at: https://pen2print.org/index.php/ijr/article/view/15599/
  11. Karthik, K., Rajeshwar, B. (2017). A New Design for Variable Latency Speculative E.C&D Han-Carlson Adder. International Journal of Research, 04 (13), 975–980. Available at: https://pen2print.org/index.php/ijr/article/view/9332/8980
  12. Hima, B. C., Srujana, G., Rao, M. V. (2018). Design of a novel BCD adder using parallel prefix technique. International Journal of Research in Electronics and Computer Engineering, 6 (2), 2213–2219. doi: http://doi.org/10.13140/RG.2.2.26923.49443
  13. Suvarna, P., Murali krishna, M. (2017). FPGA implementation of the carry select adder without using multiplexer. Global Journal for Research Analysis, 6 (3), 642–643. Available at: https://wwjournals.com/index.php/gjra/article/view/15467
  14. Balasubramanian, P., Jacob Prathap Raj, C., Anandi, S., Mastorakis, N., Bhavanidevi, U. (2013). Mathematical Modeling of Timing Attributes of Self-Timed Carry Select Adders. Conference: 4th European Conference of Circuits Technology and Devices (in the Book, “Recent Advances in Circuits, Systems, Telecommunications and Control,” Included in ISI/SCI Web of Science and Web of Knowledge. Paris, 228–243. Available at: https://www.researchgate.net/publication/265684833_Mathematical_Modeling_of_Timing_Attributes_of_Self-Timed_Carry_Select_Adders
  15. Revanna, N., Swartzlander, E. E. (2018). Memristor Adder Design. 2018 IEEE 61st International Midwest Symposium on Circuits and Systems (MWSCAS). Windsor. doi: https://doi.org/10.1109/MWSCAS.2018.8623864
  16. Soares, L. B., da Rosa, M. M. A., Diniz, C. M., da Costa, E. A. C., Bampi, S. (2019). Design Methodology to Explore Hybrid Approximate Adders for Energy-Efficient Image and Video Processing Accelerators. IEEE Transactions on Circuits and Systems I: Regular Papers, 1–14. doi: https://doi.org/10.1109/tcsi.2019.2892588
  17. Nagaraj, S., Reddy, G. M. S., Mastani, S. A. (2017). Analysis of different Adders using CMOS, CPL and DPL logic. 2017 14th IEEE India Council International Conference (INDICON). doi: https://doi.org/10.1109/indicon.2017.8487636
  18. Nykolaichuk, Ya. M., Davletova, A. Ya., Krulikovskyi, B. B., Vozna, N. Ya. (2016). Pat. No. 109142 UA. Odnorozriadnyi sumator. No. u201602165; declareted: 04.03.2016; published: 10.08.2016, Bul. No. 15.
  19. Parhomenko, P. P. (1976). Osnovy tekhnicheskoy diagnostiki. Moscow: Energiya, 464.
  20. Logic Friday 1.02. Available at: http://www.f1cd.ru/soft/base/logic_friday/logic_friday_102/
  21. Orlov, S. P., Martem'yanov, B. V. (2005). Arifmetika EVM i logicheskie osnovy pereklyuchatel'nyh funkciy. Moscow: Mashinostroenie -1, 256. Available at: http://vt.samgtu.ru
  22. 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: https://doi.org/10.15587/1729-4061.2016.70355
  23. 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. Available at: http://www.acsel-lab.com/Publications/Papers/energy_efficient_adders.pdf
  24. Govindarajulu, S., Vijaya Durga Royal, T. (2014). Design of Energy-Efficient and High-Performance VLSI Adders. International Journal of Engineering Research, 3, 55–59. Available at: https://pdfs.semanticscholar.org/a54c/5727cdc2be7830ea734f15eb1ba9ecfc2110.pdf
  25. 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.
  26. Two-Operand Addition. Available at: https://pubweb.eng.utah.edu/~cs5830/Slides/addersx6.pdf
  27. Knowles, S. (1999). A family of adders. Proceedings 14th IEEE Symposium on Computer Arithmetic (Cat. No.99CB36336). doi: https://doi.org/10.1109/arith.1999.762825
  28. Sklansky, J. (1960). Conditional-Sum Addition Logic. IEEE Transactions on Electronic Computers, EC-9 (2), 226–231. doi: https://doi.org/10.1109/tec.1960.5219822

Downloads

Published

2019-02-20

How to Cite

Solomko, M., Tadeyev, P., Zubyk, Y., & Hladka, O. (2019). Reduction and optimal performance of acyclic adders of binary codes. Eastern-European Journal of Enterprise Technologies, 1(4), 40–53. https://doi.org/10.15587/1729-4061.2019.157150

Issue

Vol. 1 No. 4 (2019): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2019 Mykhailo Solomko, Petro Tadeyev, Yaroslav Zubyk, Olena Hladka

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.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.