Computer Systems 101 - Logic Gates

A computer must store and process data. In this article, we will explore the foundations on which a computer system process data.

All meaningful systems takes in data as inputs, and produces outputs. You tap the A key on your keyboard, and the letter 'A' appears on your text editor.

All data on your computer are stored as a combinations of bits (binary digit), which can have values of either 1s and 0s; this is also known as binary data. To process this data to produce something meaningful, we must pass it through some boolean functions, which takes these binary data as inputs, and output the processed binary data.

Boolean functions are implemented physically as logic gates. Logic gates is a type of combinational chips, because its output depends solely on its inputs, which is what a function is. Combinational chips do not have memory and thus cannot maintain state.

There are two categories of logic gates - primitive and elementary. Elementary logic gates are constructed from primitive logic gates. There are two types of primitive logic gates - Nand and Nor gates. An entire computer system can be built using just one of those gates. This, to me, is simply incredible.

Representing Boolean Functions

Logic gates, which represents boolean functions, have names like AND, OR, NAND, but it's not very informative. Instead, each boolean function has a specification detailing how it works; this specification can be represented in different ways:

  • Truth table
  • Boolean Expression
  • Canonical
Truth table

A truth table is a table of all possible sets of inputs alongside its output.

For a NOT gate, the boolean function it represents has the following truth table:

| Input | Output |
|-------|--------|
| 1     | 0      |
| 0     | 1      |

For an AND gate within puts x and y, the boolean function it represents has the following truth table:

| x | y | Output |
|---|---|--------|
| 0 | 0 | 0      |
| 0 | 1 | 0      |
| 1 | 0 | 0      |
| 1 | 1 | 1      |

As each input can receive either a 1 or 0, there are 2 possible values for that input. If a boolean function accepts 2 inputs, then there are 4 possible combination: 00, 01, 10 and 11. The number of rows on a truth table is 2n, where n is the number of inputs.

As you might have realized, the truth table can get pretty large if the number of inputs increased.

Boolean Expressions

Boolean expressions are arithmetic-like notations. Typically, there're the AND (\(x\cdot y\)), OR (\(x+y\)) and NOT (\(\overline{x}\)) operators.

Canonical

There can be an infinite number of possible Boolean Expressions for a given boolean function, since (\(\bar{x}\)) can also be (redundantly) represented as (\(\overline{x}\cdot \bar{x}\)). This is, of course, a simple example; with more complex gates, it's often difficult to see where simplification of the expression can occur.

That's why there's a canonical representation - each boolean function has a unique canonical form. However, there are different types of canonical forms.

  • Sum of minterms
  • Product of maxterms

We will focus only on sum of minterms.

Sum of minterms

Minterms are each possible combination of 0s and 1s for that boolean function. The sum of minterms method adds up all the combinations that results in a 1 output. You can generate Canonical Representations from a truth table, and vice versa.

For the OR function:

| x | y | Output |
|---|---|--------|
| 0 | 0 | 0      |
| 0 | 1 | 1      |
| 1 | 0 | 1      |
| 1 | 1 | 1      |

The Sum of Minterms representation is:

\[x\overline{y} + \overline{x}y + xy\]

Which simplifies to

\[x\overline{y} + \overline{x}y + xy\\[1ex] = x(\overline{y}+y) + \overline{x}y\\[1ex] = x + \overline{x}y\]

Since \((\overline{y}+y)\) must equal to 1. And the following completes the proof.

\[x+y\\[1ex] = ((\overline{x}+x))(x+y))\\[1ex] = \overline{x}x+\overline{x}y+xx+\overline{x}y\\[1ex] = x(\overline{x}+x+y)+\overline{x}y\\[1ex] = x + \overline{x}y\]

There's most probably more elegant proofs out there, but as someone who doesn't know much boolean algebra, this is the best I can come up with. Feel free to comment with a better proof!

The canonical representation also proves the fact that any boolean functions can be represented as combinations of NOT, AND and OR.

Two-Input Boolean Functions

The number of possible boolean functions given \(n\) inputs is \(2^{2^{n}}\). So for a boolean function with two inputs, there are sixteen different possible boolean functions.

Function x 0 0 1 1
y 0 1 0 1
Constant 0 / FALSE 0 0 0 0 0
AND x•y 0 0 0 1
x AND NOT y x•y 0 0 1 0
x x 0 0 1 1
NOT x AND y x•y 0 1 0 0
y y 0 1 0 1
XOR x•y + x•y 0 1 1 0
OR x+y 0 1 1 1
Nor x+y 1 0 0 0
Equivalence / XNOR x•y + xy 1 0 0 1
Not y y 1 0 1 0
If y then x / y → x / x OR NOT y x + y 1 0 1 1
Not x x 1 1 0 0
If x then y / x → y / y OR NOT x x + y 1 1 0 1
Nand x•y 1 1 1 0
Constant 1 1 1 1 1 1

The Power of Nand

The Nand and Nor functions can each, on its own, be used to construct all three of the boolean functions AND, OR, and NOT. And since we proved the fact that all boolean functions can be constructed from the three operations, we have also proved that all computer systems can be constructed from either Nand or Nor boolean functions alone.

x AND y = (x NAND y) NAND (x NAND y)

\[x \cdot y = \overline{(\overline{x\cdot y}) \cdot (\overline{x\cdot y})}\]

x OR y = (x NAND x) NAND (y NAND y)

\[x + y = \overline{(\overline{x\cdot x}) \cdot (\overline{y\cdot y})}\]

NOT x = x NAND x

\[\bar{x} = \overline{x\cdot x}\]

Logic Gates

A logic gate is a physical device that implements a Boolean function. There are standard symbolic notations for the elementary logic gates.

The lines sticking out of the shape represents pins. If a boolean function, \(f\), takes \(n\) inputs and produces \(m\) outputs, the gate must have \(n\) input pins, and \(m\) output pins.

When we input values \(v_{1}\ldots v_{n}\) into the input pins, we get out values \(f(v_{1}\ldots v_{n})\)

Composite Gates and Logic Design

Since all boolean functions can be constructed from AND, OR and NOT functions, gates with more complicated logics can be reduced to these gates.

For example, a simple three-way AND gate can be implemented as follows (where the rectangle represents the composite gate):

However, you also know that a certain boolean function has infinite number of implementations. Thus, we must use rules of boolean algebra to simplify our expression, and thus implementation, so it takes the least components, improving efficiency and minimizing manufacturing costs. The design of these logical circuits are known as logic design.

XOR

For example, the XOR gate can be represented as \(x\cdot \bar{y} + \bar{x}\cdot y\), which translate to a circuit below:

A XOR gate implementation using 5 elementary logic gates

But we can also implement it using only 4 elementary gates:

A XOR gate implementation using 4 elementary logic gates

With this circuit, the expression becomes \(x+y+\overline{x\cdot y}\).

AND

To implement an AND gate using only NAND, following the algebraic expression described earlier, would look something like this:

\[x \cdot y = \overline{(\overline{x\cdot y}) \cdot (\overline{x\cdot y})}\]

But in fact, this can be achieved using just two NAND gates.

The goal of logic design is thus to implement the boolean logic using the least components.

Common Gates

Here are the common gates, their symbols and their truth table.

NOT

Also known as an 'inverter'.

Traditional NOT Gate (Inverter) symbol

| A | output |
|---|--------|
| 0 | 1      |
| 1 | 0      |

AND

| A | B | output |
|---|---|--------|
| 0 | 0 | 0      |
| 0 | 1 | 0      |
| 1 | 0 | 0      |
| 1 | 1 | 1      |

OR

| A | B | output |
|---|---|--------|
| 0 | 0 | 0      |
| 0 | 1 | 1      |
| 1 | 0 | 1      |
| 1 | 1 | 1      |

NAND

| A | B | output |
|---|---|--------|
| 0 | 0 | 1      |
| 0 | 1 | 1      |
| 1 | 0 | 1      |
| 1 | 1 | 1      |

NOR

| A | B | output |
|---|---|--------|
| 0 | 0 | 1      |
| 0 | 1 | 0      |
| 1 | 0 | 0      |
| 1 | 1 | 0      |

XOR

| A | B | output |
|---|---|--------|
| 0 | 0 | 0      |
| 0 | 1 | 1      |
| 1 | 0 | 1      |
| 1 | 1 | 0      |

XNOR

| A | B | output |
|---|---|--------|
| 0 | 0 | 1      |
| 0 | 1 | 0      |
| 1 | 0 | 0      |
| 1 | 1 | 1      |

Multiplexors (Mux)

A multiplexor is a three-input gate. One of the inputs, called the "selection bit", is used to select one of the other two inputs, called the "data bits", to be the output.

| A | B | sel | output |
|---|---|-----|--------|
| 0 | 0 | 0   | 0      |
| 0 | 1 | 0   | 0      |
| 1 | 0 | 0   | 1      |
| 1 | 1 | 0   | 1      |
| 0 | 0 | 1   | 0      |
| 0 | 1 | 1   | 1      |
| 1 | 0 | 1   | 0      |
| 1 | 1 | 1   | 1      |

Demultiplexor (DMux)

Demultiplexors work in a reversed fashion to multiplexors. Demultiplexor has two inputs and two outputs.

| sel | a  | b  |
|-----|----|----|
| 0   | in | 0  |
| 1   | 0  | in |

Buses

So far we have been dealing with only components that handles 1 to 3 inputs, but components in a typical computer systems will have to deal with many (16, 32, 64) inputs at once. Why?

Because typical computer systems have to store and deal with many variables at once. The data for these variables are stored in memory, and each data has an associated address.

If there are 1024 data points, then there needs to be 1024 address. Using binary, we can create all combinations of 1024 using 10 bits. So if a system is to handle 1024 different variables at any one time, it'll need components that can process 10 input values at the same time.

These components are known as "buses" and is simply an array of the logic gates we are familar with already.

So a 32-bit AND gate is simply 32 AND independent gates next to each other, packaged into one component (the bus).

The name given to these buses have the format <gate><number>. So a 32-bit AND gate would be named And32. Individual pins are referred to by array notation - a[12] would be the twelfth input a pin on the bus.

So for a 32-bit AND gate, output[12] will have the value a[12] AND b[12]. You can have these multi-bit buses for multiplexors too.

Multi-Way

Multi-Way gates works in a similar to the 'normal' gates, only that it accepts more inputs.

An 8-Way OR gate will return 1 if any of the 8 inputs are 1. An 8-Way AND gate will return 1 only if all 8 inputs are 1.

A 4-Way Multiplexor takes 4 data bits and 2 select bits to control the output bit, which can switch between any of the 4 data bits.

A 4-Way Demultiplexor takes one input and 2 select bits to channel to input into one of the 4 outputs pins.

Boolean Arithmetic

Adders

Adders are chips that adds the inputs.

There are three types of adders:

  • Half-Adder
  • Full-Adder
  • Adder

Half-Adder

A half-adder adds the two inputs and outputs the 'sum' bit, as well as a 'carry' bit.

| a | b | carry | sum |
|---|---|-------|-----|
| 0 | 0 | 0     | 0   |
| 0 | 1 | 0     | 1   |
| 1 | 0 | 0     | 1   |
| 1 | 1 | 1     | 0   |

You might have noticed the 'carry' bit has the same output as the AND gate, and the 'sum' bit has the same output as a XOR gate. So you can recreate the half-adder chip using these two gates.

Full-Adder

The Full-Adder is the same as the Half-Adder, but takes three inputs instead of two.

| a | b | c | carry | 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   |

A full-adder can be implemented by using two half-adders and an OR gate

Or you can implement it using 5 gates.

Adder

A Multi-bit adder, or simply Adder, is a series of Full-Adders in an array. A 16-bit adder have 32 input pins and 16 output pins. Each set of corresponding pins are independent from the others, just like any other n-bit components.

Incrementer

An incrementer is a gate that adds 1 to the input value, no matter how many bits the number takes up.

Arithmetic Logical Unit (ALU)

An Arithmetic Logical Unit (ALU) is a digital electronic circuit that executes all arithmetic and bitwise logical operations on the computer, and are the fundamental building blocks of the Central Processing Unit (CPU).

A 16-bit ALU takes in two 16-bit inputs (data bits), and produces one 16-bit output. The operation for which the ALU will perform on the inputs depends on a number of control bits. For example, given 4 control bits - s, t, u, v - a control sequence of 0000 might cause the ALU to perform addition on the two sets of inputs, while a sequence of 0101 might cause the ALU to output the negative of one of the inputs.

The number of control bits and the operations that they specify is specific to each ALU, and it's specified by the designer of the ALU.

As you might have guessed, the design of the ALU can get complicated easily. Below is a diagram of a simple four-bit ALU, the 74181 integrated circuit

When designing an ALU, start with the operations that you need it to carry out. From there, figure out the lowest number of types of operations required to achieve all those operations - that's the number of control bits you need. The inner circuitry is then built upon patience and touches of genius.

comments powered by Disqus