Metaphor: The Switch

The basic building block of a computer is the simple on-off switch. A
typical computer chip may contain several hundred thousand switches.
How do you build something that small?

Switches

A normally open switch

A normally closed switch

Basic Logic Tables

We represent true by 1 and false by 0

and
P Q PQ

1 1 1
1 0 0
0 1 0
0 0 0

or

P Q P + Q

1 1 1
1 0 1
0 1 1
0 0 0

not
P P'

1 0
0 1

Constructing a Logic Statement

Any statement can be constructed with and, or, and not operators:

(1) Write the logic table for the statement.

(2) Form a "sum of products" by the following rules:

(a) For each 1 in the definition of the statement, find the values
of the variables

(b) Build an and statement, using the variable itself if its value
in that row is 1, and the negation of that variable if its value is
0.

(3) Connect all the and statements you built with or connectives.

Examples:

€ To find an equivalent form of the statement

S = PQ + P'Q + P'Q':

P Q S

1 1 1 (this row gives the term PQ)
1 0 0
0 1 1 (this row gives the term P'Q)
0 0 1 (this row gives the term P'Q')

€ This process works with arbitrarily many variables. For n variables,
there will be 2n rows. With n = 3 variables, we have:

P Q R

1 1 1 Note that if you look at
1 1 0 these as 3-digit binaries,
1 0 1 we're just counting down
1 0 0 from 7 to 0.
0 1 1
0 1 0
0 0 1
0 0 0

Gates

We can make any circuit we want by suitably combining and, or, and not
gates.

Here's how we draw gates in circuit diagrams:

Here's how we make gates from switches:

Example: A one-bit comparator, which has output
1 if and only if both inputs are equal

The logic formula for equality is

PQ + P'Q'

so we just hook gates together appropriately:

Using Circuits to Do Arithmetic

€ If we interpret current (= true) as 1 and no current (= false) as 0, we
can use circuits to do arithmetic.

€ Here's all you need to know about binary arithmetic:

€ To design an adder is simple: The sum digit is 1 only when both inputs
are different, and the carry digit is 1 only when both the inputs are 1:

sum = ab' + a'b

carry = ab

We can use the logic formulas sum = ab' + a'b, carry = ab to build the
adder:

This is called a half adder (HA), since, although it has a carry out,
there's no provision for a carry in.

€ We can fix this by hooking two half adders together to produce a 1-bit
full adder (FA):

To represent numbers, we will use a collection of parallel lines, one
for each digit.

This is how 37 (= 100101, in binary) would be represented:

€ To add two 4-bit numbers, we add them in parallel, using four 1-bit full
adders:

Controlling the Flow of Information

+ Very Important Fact: The computer performs every operation at once, and
through switches selects which result is used.

€ Here's a simple switch, called a two-way multiplexor (MUX).

Example: A 2-bit, two-function arithmetic unit uses multiplexors to select
which output will be used.

The inputs are two 2-bit numbers, a1a0 and b1b0. Both of these are fed
simultaneously to a 2-bit adder and a 2-bit multiplier.

One MUX on each output line controls whether the output will be the sum or
the product.

To expand this to more parallel lines, we just use one MUX per line.

€ We can make more complicated multiplexors, to act as four-way switches.

Such a MUX would have two select lines, s1 and s0, and would be designed
with one output line and four input lines, i3, i2, i1, i0.

If s1s0 represented n in binary, then the output would be set equal to the
value of in.

select lines Output
s1 s0 set to

0 0 i0
0 1 i1
1 0 i2
1 1 i3

We could continue this process: 3 select lines give us 8 input
possibilities, 4 select lines give 16, and so on.

€ A decoder is a multiplexor in reverse, with one input and many outputs.

Here's a 4-way decoder with two select lines:

€ Remember that multiplexors and decoders are multiway switches:

Storage: the nand Gate

Using nand gates, we can make a latch, which remembers.

There are two cases, depending on the value of g:

(1) When g = 0, q remains the same as it was before.

(2) When g = 1, the value of q is forced to be whatever d is

Example: Setting the latch to 0 (lines with 1 are darkened

Before z has had a chance to stabilize

After z has remained 0 long enough

Building a 1-Bit Memory Cell

We will have three lines to our cell:

(1) A data line, which will pass information to and from the cell.

(2) A read/write line: Set to 0 it causes data to be read from memory,
and set to 1 it causes the data to be stored (written) in memory.

(3) A select line: When this is 1, the cell is active and works as it
should; when it is 0, no reading or writing can occur.

Building Bigger Memories

A 4-bit memory, capable of storing a 4-bit number, can be built from four
1-bit cells:

We can hook four of these together with a decoder to produce a 4 x 4-bit
memory, which can access any one of four 4-bit numbers:

The 4 x 4-bit memory requires 100 and gates and 82 not gates, counting both
memory and decoder.

€ A one megabyte memory, like that in a basic Macintosh, with storage for
220 = 1,048,576 cells of 8 bits each would require somewhere around

52,428,798 and gates, and

42,991,615 not gates

if they were made as we've described here.

These memory chips would fit comfortably in a small chip dip container from
your local grocery.

A modern one megabyte memory chip is about the size of a modern corn chip.

Architecture

Let's build a computer.

€ As in Module 3, we will build a system by combining functioning
components.

€ The architecture level of a computer is sometimes defined as "that which
is visible to the assembly language programmer."

We will design our computer, Pip, to match the PIPPIN language of Module 5.

(Normally, one designs a computer and gets the assembly language as a
consequence.)

€ Basic operation: The fetch/execute cycle, directed by an internal clock,
repeatedly gets an instruction from memory and then executes it, about a
million times per second.

Design Decisions

(1) The fundamental memory unit will be the 8-bit byte. A byte can
express 256 values, so our integers will be limited to the range 0...255.

(2) With 1-byte addresses, we can address 256 memory cells, so we will
use a 256 * 8-bit memory.

(3) The instruction format will consist of a 4-bit operation code,
followed by four unused bits, followed by an 8-bit operand, which
provides additional information for the operation.

(4) Four bits for the operation code means that Pip can have 16
instructions.

Code Assembler Action

0000 STO X accum --> X
0001 LOD X [X] --> accum (written A)
0010 SET X X --> A

0100 JMP X set program counter (PC) to X
0101 JMZ X if A = 0, then X --> PC
0110 NOP do nothing
0111 HLT halt execution

1000 ADI X A + X --> A
1001 ADD X A + [X] --> A
1010 SBI X A - X --> A
1011 SBD X A - [X] --> A
1100 AND X A and [X] --> A
1101 NOT not A --> A
1110 CPZ X if [X] = 0, then 1 --> A, else 0 --> A
1111 CPL X if [X] < 0, then 1 --> A, else 0 --> A

Pip

€ IR is the instruction register, where the current instruction is stored.
The operation code is sent to the decoder, which activates one of 16 lines
(13 of which aren't shown), to control the flow of data.

€ PC is the program counter, which stores the address of the current
instruction.

€ Pip would require about 25,000 gates and, if made today, would be about
the size of an apple seed.