Book contents
- Frontmatter
- Contents
- Preface
- Acknowledgments
- Part I Introduction
- Part II Combinational logic
- Part III Arithmetic circuits
- 10 Arithmetic circuits
- 11 Fixed- and floating-point numbers
- 12 Fast arithmetic circuits
- 13 Arithmetic examples
- Part IV Synchronous sequential logic
- Part V Practical design
- Part VI System design
- Part VII Asynchronous logic
- Part VIII Appendix: VHDL coding style and syntax guide
- References
- Index of VHDL design entities
- Subject index
12 - Fast arithmetic circuits
from Part III - Arithmetic circuits
Published online by Cambridge University Press: 01 February 2019
Book contents
- Frontmatter
- Contents
- Preface
- Acknowledgments
- Part I Introduction
- Part II Combinational logic
- Part III Arithmetic circuits
- 10 Arithmetic circuits
- 11 Fixed- and floating-point numbers
- 12 Fast arithmetic circuits
- 13 Arithmetic examples
- Part IV Synchronous sequential logic
- Part V Practical design
- Part VI System design
- Part VII Asynchronous logic
- Part VIII Appendix: VHDL coding style and syntax guide
- References
- Index of VHDL design entities
- Subject index
Summary
In this chapter, we look at three methods for improving the speed of arithmetic circuits, and in particular multipliers. We start in Section 12.1 by revisiting binary adders and see how to reduce their delay from O(n) to O(log(n)) by using hierarchical carry-look-ahead circuits. This technique can be applied directly to build fast adders and is also used to accelerate the summation of partial products in multipliers. In Section 12.2 we see how the number of partial products that need to be summed in a multiplier can be greatly reduced by recoding one of the inputs as a sequence of higher-radix, signed digits. Finally, in Section 12.3 we see how the partial products can be accumulated with O(log(n)) delay by using a tree of full adders. The combination of these three techniques into a fast multiplier is left as Exercises 12.17 to 12.20.
CARRY LOOK-AHEAD
Recall that the adder developed in Section 10.2 is called a ripple-carry adder because a transition on the carry signal must ripple from bit to bit to affect the final value of the MSB of the sum. This ripple-carry results in an adder delay that increases linearly with the number of bits in the adder. For large adders, this linear delay becomes prohibitive.
We can build an adder with a delay that increases logarithmically, rather than linearly, with the width of the adder by using a dual-tree structure as shown in Figure 12.1. This circuit works by computing carry propagate and carry generate across groups of bits in the upper tree and then using these signals to generate the carry signal into each bit in the lower tree. The propagate signal pij is true if a carry into bit i will propagate from bit i to bit j and generate a carry out of bit j. The generate signal gij is true if a carry will be generated out of bit j regardless of the carry into bit i.
Information
- Type
- Chapter
- Information
- Digital Design Using VHDLA Systems Approach, pp. 269 - 289Publisher: Cambridge University PressPrint publication year: 2015
Accessibility standard: Unknown
Why this information is here
This section outlines the accessibility features of this content - including support for screen readers, full keyboard navigation and high-contrast display options. This may not be relevant for you.Accessibility Information
Accessibility compliance for the PDF of this chapter is currently unknown
and may be updated in the future.