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

Reduction and optimal performance of acyclic adders of binary codes

Mykhailo Solomko, Petro Tadeyev, Yaroslav Zubyk, Olena Hladka

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

Keywords


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

References


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

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

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

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

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

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.

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

Class ECE6332 Fall 12 Group-Fault-Tolerant Reconfigurable PPA. Available at: http://venividiwiki.ee.virginia.edu/mediawiki/index.php/ClassECE6332Fall12Group-Fault-Tolerant_Reconfigurable_PPA

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/

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/

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

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

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

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

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

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

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

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.

Parhomenko, P. P. (1976). Osnovy tekhnicheskoy diagnostiki. Moscow: Energiya, 464.

Logic Friday 1.02. Available at: http://www.f1cd.ru/soft/base/logic_friday/logic_friday_102/

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

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

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

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

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.

Two-Operand Addition. Available at: https://pubweb.eng.utah.edu/~cs5830/Slides/addersx6.pdf

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

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


GOST Style Citations


Brent, Kung. A Regular Layout for Parallel Adders // IEEE Transactions on Computers. 1982. Vol. C-31, Issue 3. P. 260–264. doi: https://doi.org/10.1109/tc.1982.1675982 

Han T., Carlson D. A. Fast area-efficient VLSI adders // 1987 IEEE 8th Symposium on Computer Arithmetic (ARITH). 1987. doi: https://doi.org/10.1109/arith.1987.6158699 

Kogge P. M., Stone H. S. A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations // IEEE Transactions on Computers. 1973. Vol. C-22, Issue 8. P. 786–793. doi: https://doi.org/10.1109/tc.1973.5009159 

Ladner R. E., Fischer M. J. Parallel Prefix Computation // Journal of the ACM. 1980. Vol. 27, Issue 4. P. 831–838. doi: https://doi.org/10.1145/322217.322232 

Choi Y., Swartzlander E. E. Parallel Prefix Adder Design with Matrix Representation // 17th IEEE Symposium on Computer Arithmetic (ARITH'05). 2005. doi: https://doi.org/10.1109/arith.2005.35 

Solomko M., Olshansky P. The Parallel Acyclic Adder // 2017 14th International Conference The Experience of Designing and Application of CAD Systems in Microelectronics (CADSM). Lviv, 2017. P. 125–129.

Srinivasarao B. N., Prathyusha Ch. Power Efficient Parallel Prefix Adders // International Journal of Research. 2018. Vol. 5, Issue 4. P. 472–477. URL: https://pen2print.org/index.php/ijr/article/view/12158/11483

Class ECE6332 Fall 12 Group-Fault-Tolerant Reconfigurable PPA. URL: http://venividiwiki.ee.virginia.edu/mediawiki/index.php/ClassECE6332Fall12Group-Fault-Tolerant_Reconfigurable_PPA

Ganesh Senthil R., Kalaimathi R. Design and Analysis of Kogge-Stone and Han-Carlson Adders in 130nm CMOS Technology // International Journal of Research. 2018. Vol. 05, Issue 07. P. 1063–1068. URL: https://pen2print.org/index.php/ijr/article/view/13190/

Ananda Kumari M., Loknadh Ch. Design an Efficient Fault Tolerant Kogge Stone Adder // International Journal of Research. 2018. Vol. 05, Issue 16. P. 1446–1449. URL: https://pen2print.org/index.php/ijr/article/view/15599/

Karthik K., Rajeshwar B. A New Design for Variable Latency Speculative E.C&D Han-Carlson Adder // International Journal of Research. 2017. Vol. 04, Issue 13. P. 975–980. URL: https://pen2print.org/index.php/ijr/article/view/9332/8980

Hima B. C., Srujana G., Rao M. V. Design of a novel BCD adder using parallel prefix technique // International Journal of Research in Electronics and Computer Engineering. 2018. Vol. 6, Issue 2. P. 2213–2219. doi: http://doi.org/10.13140/RG.2.2.26923.49443

Suvarna P., Murali krishna M. FPGA implementation of the carry select adder without using multiplexer // Global Journal for Research Analysis. 2017. Vol. 6, Issue 3. P. 642–643. URL: https://wwjournals.com/index.php/gjra/article/view/15467

Mathematical Modeling of Timing Attributes of Self-Timed Carry Select Adders / Balasubramanian P., Jacob Prathap Raj C., Anandi S., Mastorakis N., Bhavanidevi U. // 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, 2013. P. 228–243. URL: https://www.researchgate.net/publication/265684833_Mathematical_Modeling_of_Timing_Attributes_of_Self-Timed_Carry_Select_Adders

Revanna N., Swartzlander E. E. Memristor Adder Design // 2018 IEEE 61st International Midwest Symposium on Circuits and Systems (MWSCAS). Windsor, 2018. doi: https://doi.org/10.1109/MWSCAS.2018.8623864

Design Methodology to Explore Hybrid Approximate Adders for Energy-Efficient Image and Video Processing Accelerators / Soares L. B., da Rosa M. M. A., Diniz C. M., da Costa E. A. C., Bampi S. // IEEE Transactions on Circuits and Systems I: Regular Papers. 2019. P. 1–14. doi: https://doi.org/10.1109/tcsi.2019.2892588 

Nagaraj S., Reddy G. M. S., Mastani S. A. Analysis of different Adders using CMOS, CPL and DPL logic // 2017 14th IEEE India Council International Conference (INDICON). 2017. doi: https://doi.org/10.1109/indicon.2017.8487636 

Odnorozriadnyi sumator: Pat. No. 109142 UA / Nykolaichuk Ya. M., Davletova A. Ya., Krulikovskyi B. B., Vozna N. Ya. No. u201602165; declareted: 04.03.2016; published: 10.08.2016, Bul. No. 15.

Parhomenko P. P. Osnovy tekhnicheskoy diagnostiki. Moscow: Energiya, 1976. 464 p.

Logic Friday 1.02. URL: http://www.f1cd.ru/soft/base/logic_friday/logic_friday_102/

Orlov S. P., Martem'yanov B. V. Arifmetika EVM i logicheskie osnovy pereklyuchatel'nyh funkciy. Moscow: Mashinostroenie -1, 2005. 256 p. URL: http://vt.samgtu.ru

Solomko M., Krulikovskyі B. Study of carry optimization while adding binary numbers in the rademacher number-theoretic basis // Eastern-European Journal of Enterprise Technologies. 2016. Vol. 3, Issue 4 (81). P. 56–63. doi: https://doi.org/10.15587/1729-4061.2016.70355 

Zeydel B. R., Baran D., Oklobdzija V. G. Energy-Efficient Design Methodologies: High-Performance VLSI Adders // IEEE Journal of Solid-State Circuits. 2010. Vol. 45, Issue 6. P. 1220–1233. URL: http://www.acsel-lab.com/Publications/Papers/energy_efficient_adders.pdf

Govindarajulu S., Vijaya Durga Royal T. Design of Energy-Efficient and High-Performance VLSI Adders // International Journal of Engineering Research. 2014. Vol. 3. P. 55–59. URL: https://pdfs.semanticscholar.org/a54c/5727cdc2be7830ea734f15eb1ba9ecfc2110.pdf

Pinto R., Shama K. Efficient shift-add multiplier design using parallel prefix adder // International Journal of Control Theory and Applications. 2016. Vol. 9, Issue 39. P. 45–53.

Two-Operand Addition. URL: https://pubweb.eng.utah.edu/~cs5830/Slides/addersx6.pdf

Knowles S. A family of adders // Proceedings 14th IEEE Symposium on Computer Arithmetic (Cat. No.99CB36336). 1999. doi: https://doi.org/10.1109/arith.1999.762825 

Sklansky J. Conditional-Sum Addition Logic // IEEE Transactions on Electronic Computers. 1960. Vol. EC-9, Issue 2. P. 226–231. doi: https://doi.org/10.1109/tec.1960.5219822 






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.

ISSN (print) 1729-3774, ISSN (on-line) 1729-4061