Authors E.S. Balaka, D.A.Gorodecky, V.S. Rukhlov, A.N. Schelokov
Month, Year 06, 2016 @en
Index UDC 004.272.2
Abstract The growth of the complexity of computing systems, data processing of large dimension pose the problem of finding solutions to improve the structure of calculators both at algorithmic the hardware level. For multi-bit data processing the combinational high-speed Parallel Prefix Adders are used. Thus, with increase of input data bit width, carry chain length is increased respectively. The RNS is an arithmetic system which decomposes a number into parts (residues) and performs arithmetic operations in parallel for each residue without the need of carry propagation among them. It makes it possible to reduce the number of the carry chain logic levels relative to positional implementation. In this paper special modulo adders are implemented using parallel prefix structures like modified Kogge-Stone, Knowles, Ladner-Fischer. A comparative analysis has been made between various parallel prefix modulo architectures in terms of VLSI entities such as area and delay. The special moduli (2n ± 1), which are as close as possible to the power of two, allow the use of the most advanced architecture PPA with minimal introduction of redundancy. Simulation results of constructed schemes of modular adders have shown that modified Kogge-Stone PPA is the optimal architecture for modulo (2n-1) adders at low bit width (64 bit), for widths more than 64 bits - architecture based on the modified Knowles PPA. For modulo (2n + 1) adders the best architecture is based on the modified Knowles PPA, for more than 32 bits – Ladner-Fischer PPA. For both types of adders, from hardware cost point of view, the most effective implementation is based on Ladner-Fischer PPA.

Download PDF

Keywords Residue Number System; Parallel Prefix Modulo Adder; Carry Save Adders; Kogge-Stone Adder; Knowles Adder; Ladner-Fischer Adder
References 1. «50 let modulyarnoy arifmetike». Yubileynaya Mezhdunarodnaya nauchno-tekhnicheskaya konferentsiya (V ramkakh V Mezhdunarodnoy nauchno-tekhnicheskoy konferentsii «Elektronika i informatika – 2005»): Sbornik nauchnykh trudov [Collection of scientific works Anniversary International Scientific Conference "50 years of Residue Number System"]. Mos-cow: OAO «Angstrem», MIET, 2006, 775 p.
2. Shalini R.V., Sampath, P. Designing of Area and Power Efficient Modulo 2N Multiplier, Eco-friendly Computing and Communication Systems (ICECCS), 2014. 3rd International Conference on,On page(s), pp. 246-249.
3. Azadeh Alsadat Emrani Zarandi, Amir Sabbagh Molahosseini, Mehdi Hosseinzadeh, Saeid Sorouri, Samuel Antão, and Leonel Sousa. Reverse Converter Design via Parallel-Prefix Adders: Novel Components, Methodology, and Implementations‖, in IEEE Trans. on VLSI SYSTEMS, January 16, 2014.
4. Chen J. and Hu J. Energy-efficient digital signal processing via voltageover scaling-based residue number system, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., Jul. 2013, Vol. 21, No. 7, pp. 1322-1332.
5. Kravchenko V., Radchenko D. Sovremennye tekhnologii RTL-sinteza v produktakh kompanii Synopsys [Modern technology RTL-synthesis products from Synopsys], Elektronika: nauka, tekhnologiya, biznes [Electronics: Science, Technology, Business], 2005, No. 2, pp. 66-69.
6. Sudheer Kumar Yezerla, B RajendraNaik. Design and Estimation of delay, power and area for Parallel prefix adders, Recent Advances in Engineering and Computational Sciences, 2014, Vol. 2, pp. 1-6.
7. Sunitha P. A Novel Approach For Designing A Low Power Parallel Prefix Adders, October 2012, Vol. 1, Issue 8.
8. Padmajarani S.V., and Muralidhar M. A New Approach to implement Parallel Prefix Adders in an FPGA. A Novel Approach For Designing A Low Power Parallel Prefix Adders, 2012, pp. 1524-1528.
9. Naganathan Vignesh. A Comparative Analysis of Parallel Prefix Adders in 32 nm and 45 nm static CMOS Technology. Dissertations. The University of Texas at Austin, 2015.
10. Kogge P. and Stone H. A parallel algorithm for the efficient solution of a general class of recurrence relations, IEEE Transactions on Computers, 1973, Vol. C-22, pp. 786-793.
11. Knowles S. A family of adders, Proceedings of the 15th IEEE Symposium on Computer Arithmetic, June 2001, pp. 277-281.
12. Ladner R. and Fischer M. Parallel prefix Computation, Journal of the ACM, 1980, Vol. 27, pp. 831-838.
13. CH. Pavan Kumar and K. Sivani. Implementation of Efficient Parallel Prefix Adders for Residue Number System, Int. J. Com. Dig. Sys. 4, o.4 (Oct-2015), pp. 295-300.
14. Brent R.P. and Kung H.T. A regular layout for parallel adders, IEEE Transactions on Computers, 1982, Vol. C-31, pp. 260-264.
15. Sklansky J. Conditional-sum addition logic, IRE Transactions on Electronic Computers, 1960, Vol. EC-9, pp. 226-231.
16. Omondi Amos, Premkumar Benjamin, Eds., Residue Number Systems: Theory and Implementation (Advances in Computer Science and Engineering Texts) London, UK: Imperial College Press, September 10, 2007).
17. Jaberipur and S. Nejati. Balanced minimal latency RNS addition for moduli set {2n-1,2n,2n+1}, in Proc. 18th Int. Conf. Systems, Signals and Image Processing (IWSSIP), 2011, pp. 1-7.
18. Jaberipur G. and Parhami B. &ldquo,Unified Approach to the Design of Modulo-( 2n+1 ) Adders Based on Signed-LSB Representation of Residues,&rdquo, Proc. 19th IEEE Symp. Computer Arithmetic, 2009, pp. 57-64.
19. NanGate 45nm Open Cell Library. Available at: (accessed 28 April 2016).
20. Balaka E.S. Tel'pukhov D.V., Osinin I.P., Gorodetskiy D.A. Sravnitel'noe issledovanie i analiz metodov apparatnoy realizatsii summatorov po modulyu [Comparative study and analysis meth-ods hardware implementation RNS-based Adders], Universum: Tekhnicheskie nauki: elektron. nauchn. zhurn. [Universum: Technical Sciences: electronic scientific journal], 2016, No. 1 (23). Available at: (accessed 28 April 2016).

Comments are closed.