### 1. Arithmetic Based on Logical Functions

• A key requirement of digital computers is the ability to use logical functions to perform arithmetic operations.

• If we can add two binary numbers, then we should be able to:

• subtract them, and

• perform multiplication and division.

### 2. Adding Binary Numbers

• How, then, could we add two binary numbers?

• For two input bits there are four possible combinations of inputs.

• These four possibilities, and the resulting sums, are:

```     0 + 0 =  0
0 + 1 =  1
1 + 0 =  1
1 + 1 = 10
```
• The last line indicates that we have a carry output.

•

INPUTS OUTPUTS
A B CARRY SUM
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

 Therefore, we can transform our results into a truth table, shown on the right. Suddenly, this looks familiar: The carry output is a simple AND function. The sum is an XOR.
• Corresponding logic gate circuit, which adds inputs A and B, is known as half adder.

### 3. Half Adder Discussion

• A half adder circuit has one significant drawback:

• since pair of bits can produce an output carry,

• in addition to the inputs A and B, we need to account for a possible carry over from a bit of the lower order of magnitude.

• Unfortunately, half adder has no support for such carry over input by design.

• Therefore, the combination requires not two, but three inputs to make the adder circuit more useful.

• The circuit that does the entire job is called a full adder.

### 4. The Full Adder

• To construct a full binary adder circuit, we need three inputs and two outputs, as specified by the following truth table:

INPUTS OUTPUTS
A B CARRY IN CARRY OUT SUM
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

•

• The truth table includes five columns as follows:

1. input A

2. input B

3. carry IN for the current column

4. resulting carry OUT (carry-over), generated for the next column

5. the resulting SUM.

•

### 5. One-bit Full Adder Example

• To implement the adder logic, we could combine two half-adder circuits together:

• For the reasons explained later, we will examine a different version of the full adder circuit, as well as its functional details.

• The second version of the full adder will have more primitive, brute force(*) implementation.

• _____________

•      (*) Hacker Slang

### 6. One-bit Full Adder

 The new circuit combines three inputs: two input bits and a carry. The gate-level description of a full adder follows: Combination of AND-gates is a decoder circuit for each possible combination of inputs. Decoder produces output of a single 1 (with the rest of 0s) for each unique combinaton of input signals. The OR gates re-combine unique output 1 into desired combination of carry and sum outputs. Note that AND-gate on top of the circuit is not connected to either of the OR-gates, because it should never produce any 1s in either output.
•

### 7. Multibit Addition

 A circuit for adding two 4-bit binary numbers: So far we explored a one-bit full adder. To add multiple binary bits together, we must include a possible carry over from the lower order of magnitude, and send it as an input carry to the next higher order of magnitude bit. Multibit addition requires full adders with carry lines to be cascaded (chained together.) See also: binary subtraction article.
•

### 8. Programmable Logic Array

 One-bit full adder logic demonstrates a programmable logic array, or PLA, which is a collection of logic functions between: unique input pattern, presorted by AND-gate array (decoder) on the left side, and OR-gate array one the right side. AND array corresponds to the number of rows in the truth table.
• For n rows we need 2n input AND-gates to construct the circuit.

• For example, one-bit full adder had 3 inputs and required 8 = 23 input AND gates.

### 9. Programmable Logic Array, Cont.

 The number of OR-gates corresponds to the number of output columns in the truth table. PLA implementation is very simple: connect AND-gate output to the input of OR-gate as follows: If row of the corresponding AND-gate requires output 1, make a connection. If the truth table raw requires output 0, do not make a connection.
• This kind of approach to implement the truth table implies the notion of being programmable.

• We program our connections between the AND- and OR-gates while implementing desired logic functions.

• Note that besides AND and OR the PLA may also include inverters.

### 10. Logical completeness

• We say that a set of gates

• {AND, OR, NOT}

is logically complete, if we are able to:

1. draw a set of programmable connections between gates without any other kind of gate, and

2. completely satisfy the requirements of the truth table.

• We may also say that such set of gates {AND, OR, NOT}

• is sufficient to build an implementation of a given truth table, and

• we don't need any other gates to do the job.