Study of carry optimization while adding binary numbers in the rademacher number-theoretic basis

Authors

DOI:

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

Keywords:

adder, cascade circuit, directed acyclic graph, Rademacher NTB

Abstract

The operation of addition of binary numbers in the multi-bit parallel carry adder circuit of the Rademacher NTB, the process of which uses the logarithmic summation algorithm is considered. It is found that computing of the sum and carry signals in circuits of such adders can be justified by the mathematical model in the form of the directed acyclic graph, which is a binary tree. It is revealed that the performance indicator of the directed acyclic graph in the form of a number of computing steps determines the optimum number of carries in the multi-bit parallel carry adder circuit in the Rademacher NTB.

It is found that the number of computing steps for the considered models of parallel carry adders is equal to the number of bits of binary numbers n. Thus, the complexity of the algorithm for computing the sum and carry signals of the parallel carry adder in the Rademacher NTB is O (n) and is linear – the time of the algorithm increases linearly with the number of bits of binary numbers n.

The research can be used for the design technology of electronic adder circuits, since it makes clear what is the structure of the adder, teach to operate the adder circuit at the design stage.

Author Biographies

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

PhD, Associate Professor

Department of Computer Engineering

Boris Krulikovskyі, National University of Water and Environmental Engineering 11 Soborna str., Rivne, Ukraine, 33028

PhD, Associate Professor

Department of Computer Engineering

References

  1. Borisenko, А. А. (2011). Remark about Fibonacci of microprocessors. Academy Trinitarizm. Available at: http://www.trinitas.ru/rus/doc/0232/009a/02321223.htm
  2. Sajesh, K., Mohamed, S. (2012). Efficient Carry Select Adder Design for FPGA Implementation. Procedia Engineering, 30, 449–456. doi: 10.1016/j.proeng.2012.01.884
  3. Hiremath, Y. (2014). A Novel 8-bit Carry Select Adder using 180nm CMOS Process Technology. International Journal of Emerging Engineering Research and Technology, 2 (6), 187–194. Available at: http://www.ijeert.org/pdf/v2-i6/25.pdf
  4. 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
  5. Chithra, M., Omkareswari, G. (2013) 128-bit Carry Select Adder Having Less Area And Delay. International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering, 2 (7), 3112–3118. Available at: http://www.ijareeie.com/upload/2013/july/35E_128-BIT.pdf
  6. Кunitskay, S. Y. (2015) Synthesis combiners in binary, ternary excess notation. Herald ChDТU, 1, 86–90.
  7. Tang, Y., Liu, L., Tatemura, J., Hacigumus, H. (2015). KTV-Tree: Interactive Top-K Aggregation on Dynamic Large Dataset in the Cloud. 2015 IEEE 35th International Conference on Distributed Computing Systems Workshops. Available at: https://pdfs.semanticscholar.org/cb3e/ae43d0e3465cd52acf73de974bcc374e6665.pdfdoi: 10.1109/icdcsw.2015.32
  8. Martyniuk, T. B., Коzhem’yko, А. В., Denysiuk, N. О. Pozdniakova Т. Y. (2015). Analіz operatsіynogo basis for neyromerezhevih іntelektualnih systems. Іnformatsіynі tehnologіi that Komp'yuterniy іnzhenerіya, 2, 83–87.
  9. Tsmots, І., Skorokhoda, О., Balych, B. (2012). The modified method and structure of the VLSI-device group for summing neyroelementa. Bulletin of the National University "Lviv Polytechnic": Computer Science and Information Technology, 732, 51–57. Available at: http://ena.lp.edu.ua:8080/bitstream/ntb/14865/1/9_Tsmots_51_57_732.pdf
  10. Wu, C., Wan, S., Hou, W., Zhang, L., Xu, J., Cui, C. et. al. (2015). A survey of advancements in nucleic acid-based logic gates and computing for applications in biotechnology and biomedicine. Chem. Commun., 51 (18), 3723–3734. doi: 10.1039/c4cc10047f
  11. Seelig, G., Soloveichik, D. (2009). Time-Complexity of Multilayered DNA Strand Displacement Circuits. DNA Computing and Molecular Programming, 144–153. Available at: http://www.dna.caltech.edu/Papers/CRN_circuit_complexity.pdf doi: 10.1007/978-3-642-10604-0_15
  12. Hamaiun, V. P. (1990) On the development of computational structures mnogooperandnyh. Control systems and machines, 4, 31–33.
  13. Gamajun, V. P. (1999). Teoretychni osnovy, algorytmy ta struktury bagatooperandnoi' obrobky. NAN Ukrai'ny. In-t kibernetyky im. V. M. Glushkova, 33.
  14. Martyniuk, T. B., Homyuk, V. V. (2005). Methods and means of parallel transformation vector data sets. Vinnitsa : "UNIVERCUM- Vinnitsa", 202.
  15. Martyniuk, T. B. (2000). Rekursyvni algorytmy bagatooperandnoi obrobky informacii. Vinnitsa: "UNIVERCUM- Vinnitsa", 216.
  16. Class ECE6332 Fall 12 Group-Fault-Tolerant Reconfigurable PPA. Available at: http://venividiwiki.ee.virginia.edu/mediawiki/index.php/ClassECE6332Fall12Group-Fault-Tolerant_Reconfigurable_PPA

Downloads

Published

2016-06-21

How to Cite

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. https://doi.org/10.15587/1729-4061.2016.70355

Issue

Vol. 3 No. 4(81) (2016): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2016 Mykhailo Solomko, Boris Krulikovskyі

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.