<style>
* {
letter-spacing: 0.02em;
text-align:justify
}
p.part {
line-height: 2em;
}
.keyword {
color: #03A9F4;
}

.variable {
color: red;
border-radius: 10%;
margin: 1px;
padding: 1px 5px;
background: #f5f5f5;
font-weight: 480;
}

.not-indent{
text-indent: 0;
line-height: 0;
}
p .small {
text-indent: 0em;
line-height: 0em;
}
</style>

# Faster Adder

## Half Adder
---
Adds 2 bits, generates sum and carry

#### Step 1: Capture the function

<table>
<tr>
<th colspan="2">Inputs</th>
<th colspan="2">Outputs</th>
</tr>
<tr>
<td>a</td>
<td>b</td>
<td>carry out (co)</td>
<td>sum (s)</td>
</tr>
<tr>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
</tr>
<tr>
<td>0</td>
<td>1</td>
<td>0</td>
<td>1</td>
</tr>
<tr>
<td>1</td>
<td>0</td>
<td>0</td>
<td>1</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>1</td>
<td>0</td>
</tr>
</table>

#### Step 2: Convert to Equations

co = ab
s = a'b + ab' = a xor b

#### Step 3: Create the circuit


## Full-Adder
---
Adds 3 bits, generates sum and carry

#### Step 1: Capture the function

<table>
<tr>
<th colspan="3">Inputs</th>
<th colspan="2">Outputs</th>
</tr>
<tr>
<td>a</td>
<td>b</td>
<td>ci</td>
<td>carry out (co)</td>
<td>sum (s)</td>
</tr>
<tr>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
</tr>
<tr>
<td>0</td>
<td>0</td>
<td>1</td>
<td>0</td>
<td>1</td>
</tr>
<tr>
<td>0</td>
<td>1</td>
<td>0</td>
<td>0</td>
<td>1</td>
</tr>
<tr>
<td>0</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>0</td>
</tr>
<tr>
<td>1</td>
<td>0</td>
<td>0</td>
<td>0</td>
<td>1</td>
</tr>
<tr>
<td>1</td>
<td>0</td>
<td>1</td>
<td>1</td>
<td>0</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>0</td>
<td>1</td>
<td>0</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
</tr>
</table>

#### Step 2: Convert to Equations

co = a'bc + ab'c + abc' + abc
co = a'bc + abc + ab'c + abc + abc' + abc
co = (a' + a)bc + (b' + b)ac + (c' + c)ab
**co = bc + ac + ab**

s = a'b'c + a'bc' + ab'c' + abc
s = a'(b'c + bc') + a(b'c' + bc)
s = a' (b xor c) + a (b xor c)'
**s = a xor b xor c**

#### Step 3: Create the circuit


### Carry-Ripple Adder
---
Using half-adder and full-adders, we can build adder that adds like we would by hand

#### 4 bit Carry-Ripple Adder (using FA and HA)


#### 4 bit Carry-Ripple Adder (All using FA)


#### Problem (Long Latency)

Full Adder 2 must wait for Adder 1, due to Adder 2 needing **carry-in** (Adder 1's carry out), and so on.


Con: Slow
> Output is not correct until the carries have rippled to the left

> 4-bit carry-ripple adder has 4*2 = **8 gate delays** (1 Adder has 2 level delay)

Pro: Small
> 4-bit carry-ripple adder has just 4*5 = **20 gates**
### Faster Adder (Trade Off) (參考)
---
Faster adder - Use two-level combinational logic design process

### Faster Adder (Bad)

* Idea
Using the **"lookahead"** technique directly compute from inputs


* No waiting for ripple

* Problem
* Equations get too big
* Not efficient
* Need a better form of lookahead

#### Pro: Fast

#### Con: Large
* Truth table would have $2^{4+4}=256$ rows
* 4-bit adder would use about **500 gates**

### Better Form of Lookahead

* Idea
Compute two terms instead using external inputs
* **Propagate: P = a xor b**
* **Generate: G = ab**

* meaning
* G： if two bits **a and b are 1**, then carry-out must be 1. (exclude carry-in)

* P： if only one of **a or b is 1**, then carry-out will **equal carry-in** (like propagation)

* Revisited Half-Adder

By using Half-Adder, we can conclude that the carry-out is G and the sum is P.

Then, modify the half-adder, and you can also get the S0.

We call that structure the **SPG block** ( Sum / Propagate / Generate).


* With P and G, the carry lookahead equations are much simpler
* c1 = G0 + P0c0
* c2 = G1 + P1c1
* c3 = G2 + P2c2
* cout = G3 + P3c3

* After pluggin in
* c1 = **G0 + P0c0**
* c2 = G1 + P1 (G0 + P0c0) = **G1 + P1G0 + P1P0c0**
* c3 = G2 + P2 (G1 + P1G0 + P1P0c0) = **G2 + P2G1 + P2P1G0 + P2P1P0c0**
* cout = G3 + P3c3 = **P3P2G1 + P3P2P1G0 + P3P2P1P0c0**

* 4-bits Better Form of Lookahead (Using SPG block)



* overall
* Fast
**only 4 gate delays**
* Each stage has SPG block with 2 gate levels
* Carry-lookahead logic quickly computes the carry from the propagate and generate bits using 2 gate levels inside
* Reasonable number of gates 4 bit adder has only **26 gates**

## Comparison
---

4-bit adder comparision (gate delays, gates)

| Carry Ripple | Two level | CLA |
| -------- | -------- | -------- |
| (8, 20) | (2, 500) | (4, 26) |

## Reference
---
[1] Slides to accompany the textbook Digital Design, First Edition, by Frank Vahid, John Wiley and Sons Publishers, 2007

###### tags: `Logic Design`