Transcript adder_cavallar

Application of Addition Algorithms
Joe Cavallaro
Overview

Addition algorithms – core operation

Fixed-point core algorithms easy to implement
Basic adder design from full adder cell
Ripple carry addition – O(n)
Carry propagation bottleneck
“Fast” algorithms control carry transport




Wireless Communications Applications





Key to all matrix algorithms.
GPP and DSP processors use a given algorithm
Flexible choice in ASIC and FPGA designs
Multiuser Detection – Addition bottleneck since
multiplications can be eliminated via hard decisions
Area-time complexity in choice of Adders
Redundant Arithmetic and On-Line
Addition





Traditional number systems have “0” and “1” and
work from LSB to MSB.
Redundant arithmetic allows “-1”, “0” and “1” bits per
digit – implies multiple representations and “error
correction”
On-Line arithmetic is bit serial from MSB to LSB
Allows for efficient pipelines and allows quick sign
detection
Challenge is to quantify speedup
Adder Equations

Full Adder Cell

S_I = x_I XOR y_I XOR c_I

C_I+1 = x_I AND y_I OR c_I AND (x_I OR y_I)
Ripple Carry Adder
Carry look-ahead Adder
(f,r) Gate Tree
Tree Structure Adder – T > log 2n
Manchester Carry Chain
Carry Skip Adder – comparable to CLA
Counter Cell – Multi-operand ->
Multiplication
Carry-Save Adders

Basic cell generate c and s output

S = (x + y + z) mod 2

C = ((x + y + z) – s) / 2

Final carry-propagate adder at bottom of tree
Carry Save Adder – 4 Operands
Carry Save Adder Tree for 6 Operands
Levels in the CSA Tree
Pipelined Design
Timing Diagram for Pipeline
Summary

Overview of addition algorithms

Block structures for RCA, CLA, CSA

Introduction to Redundant arithmetic and On-line
arithmetic

Application to ASICs for Multiuser Detection

Reference: Israel Koren