11. Half & Full Adder

Memory was created using flip-flops, which are a form of sequential logic
Earlier, combinational logic was used to perform logical operations
Now, combinational logic will be used to perform addition
- However, it will become clear soon that binary addition is effectively a logical operation

11.1. Binary Addition as a Logical Operation

If one wants to add two bits together, how many output bits are needed?
To answer this, consider the possibilities
- \(0_{2} + 0_{2} = 0_{2}\)
- \(0_{2} + 1_{2} = 1_{2}\)
- \(1_{2} + 0_{2} = 1_{2}\)
- \(1_{2} + 1_{2} = 10_{2}\)
As one can see, when adding two 1s together, a carry bit is needed
Thus, when adding two bits together, two output bits are required
In general, when adding two \(n\) bit numbers together, \(n+1\) bits is sufficient to output the correct sum
- Remember, adding a bit doubles the number of representable values
Consider the below table showing the result of adding two one bit numbers together
- \(A\) and \(B\) are the two one bit numbers
- \(S\) is the sum bit
- \(C\) is the carry bit

Two Bit Addition as a Logical Operation
\(A\)	\(B\)	\(C\)	\(S\)
`0`	`0`	`0`	`0`
`0`	`1`	`0`	`1`
`1`	`0`	`0`	`1`
`1`	`1`	`1`	`0`

Referring to the above table, notice how this is effectively a logical operation
- When both inputs are 0, output 00
- When one input is 1, output 01
- When both inputs are 1, output 10
As previously discussed, programmable logic arrays can be configured to create any boolean logical function

A circuit capable of adding two one bit numbers together is called a half adder

A programmable logic array is sufficient for building a half adder
However, using programmable logic arrays is a bit like a brute force solution
It is possible to greatly simplify the circuit and use less gates/transistors
Referring to the above table describing the half adder’s functionality, look at each output independently
- \(S\) is 1 only when either of the input bits are 1
  This is the functionality of XOR
- \(C\) is 1 only when both input bits are 1
  This is the functionality of AND
In other words, instead of using 5 gates with a programmable logic array, a half adder can be built with only 2 gates
Below is the typical configuration of a half adder

Unfortunately, a half adder is only capable of adding two one bit numbers together
To add numbers with more bits, one may be tempted to chain half adders together
However, this will not work as the carry bit has no way to be accounted for in the next bit’s addition
- Think about regular base 10 addition
- If the sum of one digit is 10 or more, the 10s value is carried over and included in the sum of the next digit
Thus, the half adder must be modified to incorporate an input of a carry bit

A full adder is a circuit designed to add binary numbers of arbitrary size
The idea is the same as a half adder, but they provide a way to input carry bits to be accounted for in the sum
Below is a table showing the desired functionality of a full adder

Full Adder Functionality
\(A\)	\(B\)	\(C_{in}\)	\(C_{out}\)	\(S\)
`0`	`0`	`0`	`0`	`0`
`0`	`0`	`1`	`0`	`1`
`0`	`1`	`0`	`0`	`1`
`0`	`1`	`1`	`1`	`0`
`1`	`0`	`0`	`0`	`1`
`1`	`0`	`1`	`1`	`0`
`1`	`1`	`0`	`1`	`0`
`1`	`1`	`1`	`1`	`1`

Again, observe each output independently and find the patterns of when the output should be active
- \(S\) is high only when one or three of the inputs are 1; when an odd number of inputs are 1
  This is, again, XOR’s functionality
  
  Remember from earlier, XOR can be used as a way to check even/odd
- \(C_{out}\) is 1 when any combination of two or more input bits are 1
  If \(A\) and \(B\) are both 1
  
  Or if \(A\) and \(C_{in}\) are both 1
  
  Or if \(B\) and \(C_{in}\) are both 1
  
  Or if \(A\), \(B\), and \(C_{in}\) are all 1
\(C_{out}\) can be simplified to check if
- \(A\) and \(B\) are both 1
- Or if the sum of \(A\) and \(B\) is 1 and \(C_{in}\) is 1
  Note, if the sum of \(A\) and \(B\) is 1, then at least one of the inputs was 1

The full adder design scales to arbitrary size to enable the addition of large binary numbers
This is achieved by chaining multiple full adders together
- A full adder is required for each bit
- Each full adder’s \(C_{out}\) is fed into the next significant bit’s full adder’s \(C_{in}\)
Below is an example of full adder capable of adding two four bit numbers together