Logic gates

Below bits

When we did bit twiddling we went below the normal abstraction provided by the int datatype to deal with individual bits.

But bits are themselves an abstraction.

Boolean logic in the physical world

Ultimately, a bit is just some way of indicating on/off, true/false, 1/0.

We can build bits in the physical world in various media.

Boolean logic

Remember George Boole and Boolean logic?

AND, OR, and NOT are all we need to express any function from bits to bits.

A binary digital computer is one that implements AND, OR, and NOT in some physical medium combined with the ability to store and retrieve bits.

These days that medium is electric voltages controlled by (and controlling) transistors.

Switches

Before we get to transistors, let’s make a simpler model out of regular light switches.

A standard two-way switch is wired to power and can connect that power to one of two terminals.

If we connect a light bulb to a terminal, the light bulb turns on when the switch connects that terminal.

Not

If we think of each switch as a single bit which is on (up) or off (down) and the bulb as another bit, we can build a Boolean NOT by just wiring the bulb to the other terminal.

Switch is on but the bulb is off.

If we flipped the switch off the bulb would turn on.

And

We can wire two switches in series, one feeding the output of one into the other to create a Boolean AND of the values of the two switches.

Bulb will only be on if both switches are on.

Or

And if we wire two switches in parallel, each connected to the bulb, it creates a Boolean OR of the values of the two switches.

If either switch is on the bulb will be on.

And we can make more complex Boolean expressions by wiring together more switches.

A && B || C && D

Not a computer

We can build a circuit to compute any Boolean function by adding more bulbs and switches.

Then we can compute that function for any inputs by flipping the right switches to enter our inputs and reading the result off the bulbs.

But for true computation we need a loop.

We could put a human in the loop to read values off bulbs then enter them by flipping switches.

The big idea

But what if we could use the output of one circuit to flip a switch on or off instead of lighting a bulb?

The unlabeled switches are not controlled by a human but rather by the inputs coming in at the top left.

So the top switch is on and the bottom switch is off.

This looks more complicated since it has two more switches.

But it allows us to treat simple arrangements of switches as a unit: two switches in series computes AND and two in parallel compute OR.

And we can further abstract things by treating all the switches as controlled by some input.

Now let’s abstract away the power and the switches inside the rectangles.

Each rectangle is called a logic gate because it implements one piece of Boolean logic.

There are standard symbols for logic gates.

This is how we’d diagram the circuit on the previous slide using standard symbols.

Standard symbols

Name

Symbol

Truth table

Name

Symbol

Truth table

AND

A	B
0	0	0
0	1	0
1	0	0
1	1	1

NAND

A	B
0	0	1
0	1	1
1	0	1
1	1	0

A	B
0	0	0
0	1	1
1	0	1
1	1	1

NOR

A	B
0	0	1
0	1	0
1	0	0
1	1	0

XOR

A	B
0	0	0
0	1	1
1	0	1
1	1	0

XNOR

A	B
0	0	1
0	1	0
1	0	0
1	1	1

BUFFER

A
0	0
1	1

NOT

A
0	1
1	0

Some useful gates

Half adder

Adds two one-bit inputs A and B putting the sum on S and any carry (i.e. the two’s place) on C.

Full adder

Adds two one-bit inputs A and B plus a carry bit from a previous addition (C_in) putting the sum on S and any carry on C_out.

Ripple adder

Wiring a bunch of full adders together creates an N-bit adder (8-bit in this case).