|
بسم الله الرحمن الرحيم |
|
|
|
|
||||||
|
|
|
|
|
|
||||
|
|
||||||||
|
|
|
|
 |
 |
 |
|
Carry-Save Adders (CSA): It is clear that carry-propagation is time-consuming and must be repeated several times i.e. k operands requires k-1 propagations. There exist techniques for lowering this penalty and the one that is most commonly used is the carry-save addition. Carry propagates only in last step, while, other steps generate partial sum and sequence of carries. Basic CSA accepts 3 n-bit operands and generates 2 n-bit results, which are: n-bit partial sum and n-bit carry. While the second CSA accepts the 2 sequences and another input operand, then it generates new partial sum and carry. Therefore, Cary Save Adder is used to add three (3) or more operands simultaneously. CSA reduces number of operands to be added from 3 to 2 without carry propagation. Implementing Carry Save Adders: The simplest implementation is the full adder (FA) with 3 inputs x,y,z. Where x+y+z = 2c+s ; (s =sum and c=carry outputs):
FA is called a (3,2) counter. The n-bit CSA consists of n (3,2) counters in parallel with no carry links as shown bellow:
Carry-Save Adder for four 4-bit Operands:
The upper 2 levels are 4-bit CSAs, while, the 3rd level is a 4-bit carry-propagating adder (CPA) Partial sum bits and carry bits interconnected to guarantee that only bits having same weight are added by any (3,2) counter
Adding k Operands: This requires (k-2) CSAs + one CPA If the CSAs are arranged in cascade, the time to add k operands is (k-2)TCSA + TCPA , where TCPA and TCSA are the operation time of CPA and CSA respectively. TCSA = DFA. The sum of k operands of size n bits each can be as large as k(2 -1) and the final addition result may reach a length of n+élog 2 kù bits.
Six-operand Wallace Tree: Wallace tree shows a better organization and faster operation time for CSAs as seen in the below diagram.
Number of Levels in Wallace Tree: The number of operands reduced by a factor of 2/3 at each level: Consequently, l = Only an estimate of l - number of operands at each level must be an integer Ni is the number of operands at level i. Thus, Ni+1 is at most ë3/2 Niû, where, ëxû means the largest integer smaller than or equal to x. The maximum at level 1 is 3 operands while the maximum at level 2 is ë9/2û =4 operands. Therefore, the resulting sequence: 2,3,4,6,9,13,19,28,…
Number of Levels in a CSA Tree for k operands
Example (1): If the number of operands is k=12: We have 5 levels and a delay of 5TCSA instead of 10TCSA in a linear cascade of 10 CSAs.
Most Economical Implementation (Fewer CSAs): This is achieved when the number of operands is element of 3,4,6,9,13,19,28,… If given number of operands, k, is not in the above sequence, we shall use only enough CSAs to reduce k to closest (smaller than k) element. Example (2): If k=27, use 8 CSAs (24 inputs) rather than 9 in top level. The number of operands in next level is 8´2+3=19 |
- Unconventional Number System - Additive & Non-additive Multiplier - Counters |
|
|
|
|
|
,
where l is the number of levels
