Adders

n-bit adder can be built as a cascade of full adders
- While fully implementing the truth table as SOP would be faster with propagation delay, it would be to expensive to build because of the number of gates (because it would grow exponentially)

Full Adder

The 1-bit adder is called a full adder
Logic functions
- $s_{i} = x_{i} \oplus y_{i} \oplus c_{i - 1}$
- $c_{i} = x_{i} y_{i} + x_{i} c_{i - 1} + y_{i} c_{i - 1}$
Implementation

Single full adder is used
- Addition is done stepwise
- The carry is saved in a flip flop
- Parallel to serial converter is needed at the inputs
- Serial to parallel converter at the output
Cost
- Hardware: constant
- Delay: $n t_{c l k}$

Allows us to speed up the slow carry signal
Introduces two help functions
- $g_{i}$ : generate carry
  - if $g_{i} = 1$ then a a carry will be generated in position $i$ regardless of $c_{i - 1}$
  - $g_{i} = x_{i} \cdot y_{i}$
- $p_{i}$ : propagate carry
  - if $p_{i} = 1$ then $c_{i}$ will be propagated. otherwise, the carry will be absorbed
  - $p_{i} = x_{i} + y_{i}$
Equations
- $s_{i} = g_{i} \oplus p_{i} \oplus c_{i - 1}$
- $c_{i} = g_{i} + p_{i} c_{i - 1}$
Cost
- Hardware: $\frac{n ^{2}}{2} + \frac{9 n}{2}$
  - This grows polynomially which is acceptable (compared to the exponential brute force option)
- Delay: $4 t_{p d}$

	Ripple Carry	Carry Lookahead	2-Level Logic
Hardware (in num gates)	$5 n$	$\frac{n ^{2}}{2} + \frac{9 n}{2}$	$O (2^{n + 1})$
Delay (in $t_{p d}$ )	$2 n$	$4$	$2$

Adder for large bit width
- Carry lookahead adders are expensive for large $n$
- Instead you can connect multiple smaller carry lookahead adders together
- Ex: 12 bit adder as 3 4-bit carry lookahead adders

Built the same way as adders
1-bit full subtractor exists but often two’s complement addition is just used instead
- XOR allows for the second operand to be optionally negated (need to negate when subtracting)
- $c_{- 1}$ is set to 1 when subtracting to convert the 1’s complement calculated by the XOR into a 2’s complement