Open Access Open Access  Restricted Access Subscription or Fee Access

Design and Implementation of Carry Tree Adders using FPGAs

S. Haricharan, S. Sandhya Rani

Abstract


Carry-Tree Adders (also known as Parallel prefix adders) are known to have the best performance in VLSI designs. However, this performance advantage does not translate directly into FPGA implementations due to constraints on logic block configurations and routing overhead. This paper investigates three types of carry-tree adders (the Kogge-Stone, sparse Kogge-Stone, and spanning tree adder) and compares them to the simple Ripple Carry Adder (RCA) and Carry Skip Adder (CSA). These designs of varied bit-widths were implemented on a Xilinx Spartan 3E FPGA and delay measurements were made with a high-performance logic analyzer. Due to the presence of a fast carry-chain, the RCA designs exhibit better delay performance up to 128 bits. The carry-tree adders are expected to have a speed advantage over the RCA, CSA and carry lookahead adder as bit widths approach 256.

Keywords


Carry-Look Ahead Adder, Carry Skip Adder, Ripple-Carry Adder, Sparse KOGGE Stone And Spanning Tree Adder

Full Text:

PDF

References


N. H. E. Weste and D. Harris, CMOS VLSI Design, 4th edition, Pearson–Addison-Wesley, 2011.

R. P. Brent and H. T. Kung, “A regular layout for parallel adders,” IEEE Trans. Comput., vol. C-31, pp. 260-264, 1982.

D. Harris, “A Taxonomy of Parallel Prefix Networks,” in Proc. 37th Asilomar Conf. Signals Systems and Computers, pp. 2213–7, 2003.

P. M. Kogge and H. S. Stone, “A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations,” IEEE Trans. on Computers, Vol. C-22, No 8, August 1973.

P. Ndai, S. Lu, D. Somesekhar, and K. Roy, “Fine-Grained Redundancy in Adders,” Int. Symp. on Quality Electronic Design, pp. 317-321, March 2007.

T. Lynch and E. E. Swartzlander, “A Spanning Tree Carry Lookahead Adder,” IEEE Trans. on Computers, vol. 41, no. 8, pp. 931-939, Aug. 1992.

D. Gizopoulos, M. Psarakis, A. Paschalis, and Y. Zorian, “Easily Testable Cellular Carry Lookahead Adders,” Journal of Electronic Testing: Theory and Applications 19, 285-298, 2003.

S. Xing and W. W. H. Yu, “FPGA Adders: Performance Evaluation and Optimal Design,” IEEE Design & Test of Computers, vol. 15, no. 1, pp. 24-29, Jan. 1998.

M. Bečvář and P. Štukjunger, “Fixed-Point Arithmetic in FPGA,” Acta Polytechnica, vol. 45, no. 2, pp. 67- 72, 2005.

K. Vitoroulis and A. J. Al-Khalili, “Performance of Carry tree adders Implemented with FPGA technology,” IEEE Northeast Workshop on Circuits and Systems, pp. 498-501, Aug. 2007.

J. Rabaey, "Digital Integrated Circuits: A Design Perspective", Prentice Hall, 1996.

Majerski, S: "On Determination of Optimal Distributions of Carry Skips in Adders", IEEE Trans. EC-16 No.1, Feb. 1967

Bedrij, O.J.: "Carry-Select Adders", IRE Trans. EC-11 No. 3, June 1962

T. Han, D. A. Carlson. Fast area-efficient VLSI adders. In 8th Symp. on Comp. Arithmetic, May 1987.

S. Ghosh, P. Ndai, and K. Roy, “A novel low overhead fault tolerant kogge-stone adder using adaptive clocking,” Design, Automation and Test in Europe, 2008. DATE ’08, pp. 366–371, March 2008

R. E. Ladner,M. J. Fischer. Parallel prefix computation. Journal of the ACM, 27(4):831–838, Oct. 1980.

A. Beaumont-Smith, C.-C. Lim. Parallel prefix adder design. In Symp. on Comp. Arithmetic, Jun. 2001.

H. Ling. High speed binary adder. IBM Journal of R&D, 25(3):156–166, May 1981.

M. Ziegler and M. Stan, “A unified design space for regular parallel prefix adders,” Design, Automation and Test in Europe Conference and Exhibition, 2004. Proceedings, vol. 2, pp. 1386–1387 Vol.2, Feb. 2004.

D. Harris and I. Sutherland. Logical effort of carry propagate adders. Proc. 37th Asilomar Conf. Signals, Systems, andComputers, pages 873–878, 2003

I. E. Sutherland and R. F. Sproull. Designing for Speed on the Back of an Envelope in Advanced Research in VLSI. Univ. of Calif., CA, 1991.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.