Truth tables and circuit design

Condensing a truth table

A B C B & C A | B & C
0 0 0 0 0
0 0 1 0 0
0 1 0 0 0
0 1 1 1 1
1 0 0 0 1
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

⟺

A B C A | B & C
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

Two forms of truth table

A B C A | B & C
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

⟺

AB\C 0 1
00 0 0
01 0 1
10 1 1
11 1 1

The first form is easier to fill in but the second is obviously more compact.

More interestingly the second form is very close to something called a Karnaugh Map which has several uses in analyzing logical expressions and designing circuits.

Making a Karnaugh Map

AB\C 0 1
00 0 0
01 0 1
10 1 1
11 1 1

Reorder the rows in a compact truth table so only one variable’s value changes as we go from one row to the next.

AB\C 0 1
00 0 0
01 0 1
11 1 1
10 1 1

(If we had four variables we’d reorder the columns the same way.)

The cool thing about Karnaugh Maps (also called K-maps) is that because of the ways the rows and columns are arranged, we can extract the terms of our logical expression by circling contiguous, rectangular, power-of-two-sized blocks of 1s (i.e. one 1, two 1s, four 1s, etc.).

Extract expression: step 1

Draw boxes around the largest possible, rectangular, power-of-two-sized groups of 1s. The groups may wrap around the edges of the table and they may overlap.

Extract expression: step 2

Select groups, starting with ones that are the only group to cover one or more 1s. Keep going until all 1s are covered at least once by a selected group.

Extract expression: step 3

For each selected group, write an AND expression using each of the variables that doesn’t change in the group with the variable if it’s value is 1 and NOT the variable if it’s value is 0.

(The variable whose value changes across the group obviously doesn’t effect the output of the cells in that group.)

Extract expression: step 4

OR together all the AND expressions.

(Since any of the AND’d together expressions are sufficient to make the whole expression true, OR’ing them together gives us the whole expression.)

Let’s try

AB\C 0 1
00 0 0
01 0 1
11 1 1
10 1 1
  • In 2x2 orange group only A doesn’t change, and it’s 1, so the term is just A.
  • In overlapping 1x2 green group B and C don’t change and are both 1, so the term is B & C.
  • OR’d together: A | B & C.
  • Back where we started!

But wait!

There’s more!

Consider this circuit

Logical expression: S & A | !S & B

SA + S'B A S B 1 0 1

This is called a multiplexer because one input, S, picks one of the other two inputs to pass through. I.e. when S is 1, the value of the circuit is A and otherwise it’s B.

Steady state: A=1, B=1, S=1. If we don’t change A or B the output should always be 1 because changing S only changes which one we’re selecting.

Now set S to 0. If it takes time for the change of S to propagate down both paths and we could get something like this: the circuit is outputting 0 even though A and B are both 1. because the value coming out of the NOT gate is stale.

Then everything catches up and we land in the expected state. But for a brief moment the circuit was outputting the wrong value!

Can we fix it?

Yes.

With a Karnaugh Map.

Step 1: make a truth table

S A B !S A & S !S & B A & S | !S & B
0 0 0 1 0 0 0
0 0 1 1 0 1 1
0 1 0 1 0 0 0
0 1 1 1 0 1 1
1 0 0 0 0 0 0
1 0 1 0 0 0 0
1 1 0 0 1 0 1
1 1 1 0 1 0 1

Step 2: Condense

S A B A & S | !S & B
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1

Step 3: Compact

SA\B 0 1
00 0 1
01 0 1
10 0 0
11 1 1

Step 4: Convert

SA\B 0 1
00 0 1
01 0 1
11 1 1
10 0 0

Just reorder the rows to make it into a Karnaugh Map.

SA\B 0 1
00 0 1
01 0 1
11 1 1
10 0 0
  • The pair of 1s with the orange background represent !S & B.
  • The pair of 1s with the green background represent S & A.
  • And the pair of 1s with blue mixed in represent another term A & B.

While the orange and green groups cover all the 1s, the two adjacent 1s that are not part of either of those groups represent a hazard, exactly the problem we saw with our actual circuit.

Fixed multiplexer

So we can fix our circuit by adding a seemingly redundant AND gate to cover the hazard.

The order we put the rows in a Karnaugh Map is a thing that comes up in other contexts, whenever we want to number positions in a way that each transition from one number to the next only changes one bit.

Regular counting order is no good because, for instance, going from 3 to 4 changes 3 bits: 011 to 100.

Gray Codes

Any sequence of numbers that have the property that moving from one number to the next only changes one bit is called a Gray code after Frank Gray who invented them at Bell Labs in the 1940s.

The most commonly used Gray code is the Reflected Binary Code.

Constructing an RBC

Put a 0 in front of the original four rows.

And a 1 in front of the mirrored four. That’s the three-bit code.

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

Start with the one-bit code: 0, then 1.

Mirror it below itself: the 1 first…

…then the 0.

Put a 0 in front of the original rows.

And a 1 in front of the mirrored rows. That’s the two-bit code.

Now mirror the two-bit code below itself: 10…

…11…

…01…

…and 00.