Transcript Carry Select Adders

Multi-operand Addition
• Consider the Following Addition:
SUM = a[0];
for (i=1; i<N; i++)
{ SUM = SUM + a[i]; }
a[7]
a[6]
a[5]
a[7]+a[6]
a[4]
a[3]
a[2]
a[5]+a[4]
a[7]+a[6]+a[5]+a[4]
a[1]
a[3]+a[2]
a[0]
a[1]+a[0]
a[3]+a[2]+a[1]+a[0]
a[7]+a[6]+a[5]+a[4]+a[3]+a[2]+a[1]+a[0]
Multi-operand Addition
a[7]
a[6]
a[5]
a[7]+a[6]
a[4]
a[3]
a[2]
a[5]+a[4]
a[7]+a[6]+a[5]+a[4]
a[1]
a[3]+a[2]
a[0]
a[1]+a[0]
a[3]+a[2]+a[1]+a[0]
a[7]+a[6]+a[5]+a[4]+a[3]+a[2]+a[1]+a[0]
• O(lg2N) – Lower Bound – Theoretical Lower Limit
• This is “Binary Reduction” Operation
• Theoretical Time to Add Two Values
– O(n) – Carry Ripple Operation
– O(lg2n) – CLG/CLA tree/Prefix/Carry Skip/Carry Select
– O(1) – Avizienis/Takagi Signed Digit Arithmetic
Multiplication
• Multiplication Requires Multi-operand Addition
• Dot Product Requires Multi-operand Addition
• Defer Carry Assimilation
• Represent Intermediate Sums Redundantly
Implementation Serially
Implementation with Pipelining
Parallel Implementation
Parallel Implementation – bit
level
Carry Save Adders
• FA Used in This Configuration is Also Known as a 3:2 Compressor
Dot Notation
3:2 Compressor
2:2 Compressor
Example Tree
Example Tree (cont)
Tabular Form Representation
Adder Tree Bus Sizes
Serial Carry Save Adder
Wallace Tree
• Previous Example is 7 Input Wallace Tree
• n-input Wallace Tree Reduces k-bit Inputs to Two
(k + log2n - 1)-bit Outputs
• CSA Reduces Number of Operands by Factor of 1.5
• Smallest Height h(n) For an n-input Tree Can be
Given by a Recurrence Relation
Wallace Tree
• h(n) = 1 + h(2n/3)
• Ignoring Ceiling Operator Write as: h(n) = 1 + h(2n/3)
• Can Get Lower Bound on Tree Height: h(n)  log1.5(n/2)
• Equality for n = 2, 3 only
Wallace Tree Height
• Can Also Consider n(h)
– Number of Inputs for a Tree of Height h
• Recurrence is: n(h) = 3n(h-1)/2
• Ignoring Floor Operator Can get Bounds
• Lower Bound: n(h) > 2(3/2)h-1
• Upper Bound: n(h) < 2(3/2)h
• Exact Values for 0  h  20 in Table
Tree Levels
Wallace Versus Dadda Trees
• Reduce the Number of Operands at Earliest Opportunity
• m Dots Per Column – Apply m/3 Full Adders to Column
• Tends to Minimize Overall Delay by Making CPA
CPA as Short as Possible
• Delay of Fast CPA is Generally Not Smoothly Increasing
Function of Word Width
• EXAMPLE: CLA Has Essentially Same Delay for Widths
of 17-32 Bits
• Dadda Tree Reduces Number of Operands to Next Lower
Number Using the Fewest FAs and HAs as Possible
• Justification is No Need to Reduce Number of Operands to
Next Lower n(h) in Tree Since A Faster Tree Would
Not Result
Wallace Tree
Dadda Tree
Parallel Counters
• Single-bit Full Adder Referred to as (3:2) Counter (or Compressor)
• Meaning is it “Counts” the Ones in 3 Input Bits
• Can be Generalized to (n : log2(n+1) Counter
• Has n Inputs
• Produces a log2(n+1)-bit Binary Output Representing the
Number of 1’s Among the n Inputs
• Next Example Shows a (10:4) Counter
(10:4) Parallel Counter
Generalized Parallel Counters
• Parallel Counter Reduces Number of Dots in a Column
(same Radix Position)
• Output Dots are Placed into Different Positions (one each)
• Can Generalize This Notion
• Generalized Parallel Counter Receives “Dot Patterns” as Input
(not Necessarily in Same Bit Position)
• Converts Them to Other Dot Patterns
(not Necessarily one in Each Column)
• If Output Dot Pattern Has Fewer Dots Than Input, the
Counter is a Compressor and Can be Used for a Tree
Generalized Parallel Counters
• Characterized by Number of Dots in Each Input Column
and Output Column
• Book Limits to Class of Counters that Output a Single Dot
in Each Column
• Limitation Allows Output to be Characterized by Single Integer
Representing Number of Columns Spanned by Output
• Input Side is Characterized by Integer Sequence Corresponding
to Number of Inputs in Various Columns
(5,5 : 4) Parallel Counter
• Dot Notation for (5,5 : 4) Counter
• (5,5 : 4) Counters to Compress 5 Numbers to 2 Numbers
• Can Have Other Forms, eg. ( 4,6 : 4) Counter
• Receives 6 bits of weight 1 and 4 bits of weight 2
• Delivers the Weighted Sum in the Form of a 4-bit
Binary Number
• This Type Requires Sum of Output Weights to Equal or
Exceed Sum of Input Weights
Generalized Parallel Counters
• Powerful Concept – 4-bit Binary Full Adder Can be Viewed as
(2,2,2,3 : 5)-counter
• Goal is to Reduce n Numbers to 2 Numbers in Carry-Save Adder
• Sometimes Notation of (n : 2)-counter is Used Although it Strictly
Doesn’t Make Sense for n > 3
• (n : 2)-counter is Shorthand Notation for a Slice of a Circuit
• When Slice is Replicated, n Values are Reduced to 2 Values
• Slice i Receives n Input Bits in Position i Plus Transfer (or Carry)
Bits From One or More Positions to Right (i - 1, i - 2, etc.)
• Slice i Produces Output Bits in Positions i and i + 1 Plus Transfer
Digits Into Higher Positions (i + 1, i + 2, etc.)
• yj Denotes Number of Transfer bits From Slice i to i + j
(n : 2) Parallel Counters
• Must Satisfy This Inequality for Scheme to Work
• 3 Represents Maximum of 2 Output Bits
• eg. (7 : 2)-counter can be Built Allowing y1 = 1
- Transfer bit From Position i to i + 1
and y2=2
- Transfer bit into Position i + 2
Adding Multiple Signed Numbers
• Must Sign Extend 2’s Complement Numbers to Final Result Width
• Appears Sign Extension Could Dramatically Increase Complexity
of CSA Tree for Large n
• Trick is to Take Advantage of Fact that all Sign Extension bits are
Identical
• Use a Single Full Adder to do Job of Several Full Adders
• Allows CSA Internal Widths to be Marginally Increased
Hardware Sharing Method
Single Full Adder Used Here With Result Fanned Out
Negative Weight Interpretation
• Recall That 2’s Complement Values May be Interpreted as:
n 2
| X |  xn 1  2n 1   xi 2i
i 0
• Replace Negative Sign Bit by it’s Complement and Put a -1 in
Sign Column
• Multiple –1’s Can be Combined Each Pair Placed in –1 in Next
Higher Column
• A Solitary –1 in a Column is Replaced by a +1 in That
Column and a –1 in the Next Higher Column
Negative Weight Interpretation
• Complement Three Sign Bits and Place –1’s in Sign Column
• Replace Three –1’s by a +1 in Sign Position and Two –1’s in
Next Higher Position
• These Two –1’s are Removed and Single –1 is Inserted in
Position k + 1
• Latter –1 is in Turn Replaced by a + 1 in Position k + 1 and a – 1 in
Position k + 2
• Finally a –1 Moves Out of the Resultant Sum Width and the
Procedure Stops