Functional Specifications

input A
input B
input C

Logic Synthesis

Truth tables and sum-of-products

Primitive logic gates, universal gates
Logic simplification
Karnaugh Maps, Quine-McCluskey
General implementation techniques:
muxes and look-up tables (LUTs)
Lecture 2

I will generate a valid

output in no more than
2 minutes after
seeing valid inputs

1
!
1

-its systematic!
-it works!
-its easy!
-are we done yet???

6.111 Fall 2009

6.111 Fall 2009

Lecture 2

S-O-P Building Blocks

A Z

1. Write out our functional spec as a truth

table
2. Write down a Boolean expression with
terms covering each 1 in the output:

INVERTER:

A B

A B

=A
Bubble indicates
inversion

Y = A" B"C + A" B"C + A" B"C + A" B"C

AND:

= A" B

This approach creates equations of a

particular form called

SUM-OF-PRODUCTS

OR:

Sum (+): ORs

Products (): ANDs
Lecture 2

An concise, unambiguous technique for giving the functional

specification of a combinational device is to use a truth table to
specify the output value for each possible combination of input values
(N binary inputs -> 2N possible combinations of input values).

Heres a Design Approach

A

output Y

3 binary inputs
so 23 = 8 rows in our truth table

Reminder: Lab #1 due this Thursday!

6.111 Fall 2009

Output 1 if at
least 2 out of 3 of
my inputs are a 1.
Otherwise, output 0.

= A+ B

!
3

6.111 Fall 2009

Lecture 2

Straightforward Synthesis

ANDs and ORs with > 2 inputs

Replace 2-input AND gates with 2-input OR
gates to create large fan-in OR gates

We can use
SUM-OF-PRODUCTS
to implement any logic
function.

= A" B"C

Only need 3 gate types:

INVERTER, AND, OR

Chain: Propagation delay increases

linearly with number of inputs

= A" B"C" D

Propagation delay:
3 levels of logic
No more than 3 gate delays assuming gates with an arbitrary
number of inputs. But, in general, well only be able to use gates
with a bounded number of inputs (bound is ~4 for most logic
families).

6.111 Fall 2009

Lecture 2

Which one should I use?

= A" B"C" D

Tree: Propagation delay increases

logarithmically with number of inputs

6.111 Fall 2009

SOP w/ 2-input gates

Lecture 2

More Building Blocks

Previous example restricted to 2-input gates:

NAND (not AND)

= A" B

A B

NOR (not OR)

= A+ B

A B

!gates are naturally inverting so we want!to use NANDs and NORs

CMOS
in CMOS designs

INV

AND2

OR2

tPD

8ps

15ps

18ps

tCD

1ps

3ps

3ps

6.111 Fall 2009

Using the timing specs given to the

left, what are tPD and tCD for this
combinational circuit?

XOR (exclusive OR)

=A"B

Hint: to find overall tPD we need to

find max tPD considering all paths
from inputs to outputs.
Lecture 2

6.111 Fall 2009

A B

XOR is very useful when implementing

parity and arithmetic logic. Also used
as a programmable inverter: if A=0,
Z=B; if A=1, Z=~B
Wide fan-in XORs can be created with
chains or trees of 2-input XORs.
Lecture 2

SOP with NAND/NOR

Universal Building Blocks

When designing with NANDs and NORs one often makes use of
De Morgans laws:
De Morgan-ized NAND symbol

NANDs and NORs are universal:

NOR form:

A+ B = A" B

De Morgan-ized NOR symbol

of De Morgan-ized symbols to make the inversions less

!
confusing):

Lecture 2

! following SOP circuits are all equivalent (note the use

So the

Any logic function can be implemented using only NANDs

(or, equivalently, NORs). Note that chaining/treeing
technique doesnt work directly for creating wide fan-in
NAND or NOR gates. But wide fan-in gates can be created
with trees involving both NANDs, NORs and inverters.

6.111 Fall 2009

NAND form: A " B = A + B

AND/OR form

De Morgan-ized
Inverter

NAND/NAND form

NOR/NOR form

This will be handy in Lab 1 since

youll be able to use just 7400s
to implement your circuit!

All these extra inverters may seem less

than ideal but often the buffering they
provide will reduce the capacitive load on
the inputs and increase the output drive.

6.111 Fall 2009

Lecture 2

10

Boolean Minimization:

Logic Simplification

An Algebraic Approach

Can we implement the same function with fewer gates? Before

trying well add a few more tricks in our bag.
BOOLEAN ALGEBRA:
a +1=1 a + 0 = a a + a = a
OR rules:
a"
1 = a a" 0 = 0 a" a = a
AND rules:
a + b = b + a a" b = b" a
Commutative:
(a + b) + c = a + (b + c) (a " b) " c = a " (b " c)
!
Associative:
a " (b + c) = a " b + a " c a + b " c = (a + b) " (a + c)
Distributive:
!
a + a =1 a" a = 0
Complements:
!
a + a " b = a! a + a " b = a + b a " (a + b) = a a " (a + b) = a " b
Absorption:
!
De Morgans
! Law: a " b = a + b a + b = a " b
Reduction:!
a " b + a " b = b (a + b) " (a + b) = b

Lets simplify the equation from slide #3:

Y = A" B"C + A" B"C + A" B"C + A" B"C

Using the identity

!

!A + ! A = !
For any expression and variable A:
Y = A" B"C + A" B"C + A" B"C + A" B"C

!
!
Key to simplification:
equations that match the pattern of the LHS
(where b !
might be any expression) tell us that when b is true, the
value of a doesnt matter. So a can be eliminated from the equation,
getting rid of two 2-input ANDs and one 2-input OR.
6.111 Fall 2009

Lecture 2

Y = B"C + A"C + A" B

!
11

6.111 Fall 2009

The tricky part: some terms participate in more than one

reduction so cant do the algebraic steps one at a time!

Lecture 2

12

On to Hyperspace

Karnaugh Maps: A Geometric Approach

Heres a 4-variable K-map:

K-Map: a truth table arranged so that terms which differ by exactly one

variable are adjacent to one another so we can see potential reductions

easily.
A

AB

Heres the layout of a 3-variable K-map filled in

with the values from our truth table:

00

01

11

10

1
010
000

Its cyclic. The left edge is adjacent to the right

edge. Its really just a flattened out cube.

01

11

111
101
13

01

11

10

6.111 Fall 2009

Lecture 2

Finding Subcubes

Write down a product term for the portion of each

cluster/subcube that is invariant. You only need to include
enough terms so that all the 1s are covered. Result: a minimal
sum of products expression for the truth table.

AB

00

01

11

10

CD

Three 2x1 subcubes

00

01

11

00

10
1

01

11

10

AB

00

01

11

10

Three 2x2 subcubes

Lecture 2

CD

15

Y = A"C + B"C + A" B

Were done!

AB

The best strategy is generally a greedy one.

- Circle the largest N-dimensional subcube (2N adjacent 1s)
4x4, 4x2, 4x1, 2x2, 2x1, 1x1
- Continue circling the largest remaining subcubes
(even if they overlap previous ones)
- Circle smaller and smaller subcubes until no 1s are left.
6.111 Fall 2009

14

Write Down Equations

We can identify clusters of irrelevent variables by circling

adjacent subcubes of 1s. A subcube is just a lower dimensional
cube.
AB

10

We run out of steam at 4 variables K-maps are hard to draw and

use in three dimensions (5 or 6 variables) and were not equipped
to use higher dimensions (> 6 variables)!

001

Lecture 2

00

Again its cyclic. The left edge is adjacent to the right edge,
and the top is adjacent to the bottom.

011

110
100

6.111 Fall 2009

CD

Why did he
shade that
row Gray?

AB

Z
00

00

01

11

00

01

11

10

6.111 Fall 2009

10

Z = B" D+ B"C + A"C

Lecture 2

16

Two-Level Boolean Minimization

Prime Term Generation

Two-level Boolean minimization is used to find a sum-of-products

representation for a multiple-output Boolean function that is
optimum according to a given cost function. The typical cost
functions used are the number of product terms in a two-level
realization, the number of literals, or a combination of both. The
two steps in two-level Boolean minimization are:

Start by expressing your Boolean function using 0terms (product terms with no dont care care entries).
For compactness the table for example 4-input, 1output function F(w,x,y,z) shown to the right includes
only entries where the output of the function is 1 and
weve labeled each entry with its decimal equivalent.

Generation of the set of prime product-terms for a given function.

1-terms:

We will briefly describe the Quine-McCluskey method which was

the first algorithmic method proposed for two-level minimization
and which follows the two steps outlined above. State-of-the-art
logic minimization algorithms are all based on the Quine-McCluskey
method and also follow the two steps above.

0, 8
5, 7
7,15
8, 9
8,10
9,11
10,11
10,14
11,15
14,15

Example due to
Srini Devadas
Lecture 2

X
0
1
1
0
0
0
0
1
1

Y
0
0
1
0
0
1
1
1
1

Z
0
1
1
0
1
0
1
0
1

label
0
5
7
8
9
10
11
14
15

Look for pairs of 0-terms that differ in only one bit position and merge
them in a 1-term (i.e., a term that has exactly one entry). Next 1-terms
are examined in pairs to see if the can be merged into 2-terms, etc. Mark
k-terms that get merged into (k+1) terms so we can discard them later.

Selection of a minimum set of prime terms to implement the

function.

6.111 Fall 2009

W
0
0
0
1
1
1
1
1
1

17

6.111 Fall 2009

2-terms:

-000 [A]
01-1 [B]
-111 [C]
10010-0
10-1
1011-10
1-11
111-

8, 9,10,11
10,11,14,15

3-terms:

10-- [D]
1-1- [E]

none!

Label unmerged terms:

these terms are prime!
Lecture 2

18

Prime Term Table

Dominated Columns

An X in the prime term table in row R and column C signifies that the 0term corresponding to row R is contained by the prime corresponding to
column C.

Some functions may not have essential primes (Fig. 1), so make arbitrary
selection of first prime in cover, say A (Fig. 2). A column U of a prime
term table dominates V if U contains every row contained in V. Delete the
dominated columns (Fig. 3).

Goal: select the minimum

set of primes (columns)
such that there is at least
one X in every row. This
is the classical minimum
covering problem.

0000
0101
0111
1000
1001
1010
1011
1110
1111

A
X
.
.
X
.
.
.
.
.

B
.
X
X
.
.
.
.
.
.

C
.
.
X
.
.
.
.
.
X

D
.
.
.
X
X
X
X
.
.

E
.
.
.
.
.
X
X
X
X

1. Prime table

A is essential
B is essential

0000
0001
0101
0111
1000
1010
1110
1111

D is essential

E is essential

Each row with a single X signifies an essential prime term since any prime
implementation will have to include that prime term because the
corresponding 0-term is not contained in any other prime.

Lecture 2

B
.
X
X
.
.
.
.
.

C
.
.
X
X
.
.
.
.

D
.
.
.
X
.
.
.
X

E
.
.
.
.
.
.
X
X

F
.
.
.
.
.
X
X
.

G
.
.
.
.
X
X
.
.

H
X
.
.
.
X
.
.
.

0101
0111
1000
1010
1110
1111

B
X
.
.
.
.
.

C
X
X
.
.
.
.

D
.
X
.
.
.
X

E
.
.
.
.
X
X

F
.
.
.
X
X
.

G
.
.
X
X
.
.

H
.
.
X
.
.
.

C dominates B,
G dominates H

3. Table with B & H removed

0101
0111
1000
1010
1110
1111

C
X
X
.
.
.
.

D
.
X
.
.
.
X

E
.
.
.
.
X
X

F
.
.
.
X
X
.

G
.
.
X
X
.
.

C is essential
G is essential

Selecting C and G
shows that only E is
needed to complete
the cover

This gives a prime cover of {A, C, E, G}. Now backtrack to our choice of
A and explore a different (arbitrary) first choice; repeat, remembering
minimum cover found during search.

In this example the essential primes cover all the 0-terms.

6.111 Fall 2009

A
X
X
.
.
.
.
.
.

2. Table with A selected

19

6.111 Fall 2009

Lecture 2

20

The Quine-McCluskey Method

Logic that defies SOP simplification

The input to the procedure is the prime term table T.

1. Delete the dominated primes (columns) in T. Detect essential primes in T by checking to see if
any 0-term is contained by a single prime. Add these essential primes to the selected set. Repeat
until no new essential primes are detected.

Ci
0
0
0
0
1
1
1
1

2. If the size of the selected set of primes equals or exceeds the best solution thus far return
from this level of recursion. If there are no elements left to be contained, declare the selected
set as the best solution recorded thus far.
3. Heuristically select a prime.
4. Add the chosen prime to the selected set and create a new table by deleting the prime and all
0-terms that are contained by this prime in the original table. Set T to this new table and go to
Step 1.

!
!
21

6.111 Fall 2009

B
C

If C is 1 then
copy B to Y,
otherwise copy
A to Y

2-input Multiplexer

B
C

Co

FA

Ci

0
0
11S

I2
0
0
I3 1
1S

00

01

11

10

C/AB

00

01

11

10

22

... using a MULTIPLEXER

as the only circuit element:

A 4-input Mux
implemented as
a tree

I0 0
0
I1 11
S

C/AB

CO

Consider implementation of some

arbitrary Boolean function, F(A,B)

S0

S1

Gate
symbol
Lecture 2

A B

Systematic Implementation of
Combinational Logic

C
schematic

6.111 Fall 2009

Full Adder

Lecture 2

Truth Table
Y

Co
0
0
0
1
0
1
1
1

The sum S doesnt have a simple sum-of-products implementation

even though it can be implemented using only two 2-input XOR
gates.

Logic Synthesis Using MUXes

A

S
0
1
1
0
1
0
0
1

CO = A " C + B " C + A " B

The good news: this technique generalizes to multi-output functions. The

bad news: the search time grows as 2^(2^N) where N is the number of
inputs. So most modern minimization systems use heuristics to make
dramatic reductions in the processing time.
Lecture 2

B
0
1
0
1
0
1
0
1

S = A" B"C + A" B"C + A" B"C + A" B"C = A # B # C

Then, create a new table by deleting the chosen prime from the original table without adding it to
the selected set. No 0-terms are deleted from the original table. Set T to this new table and go
to Step 1.

6.111 Fall 2009

A
0
0
1
1
0
0
1
1

23

6.111 Fall 2009

Full-Adder
Carry Out Logic

0
0
0
1
1
0
1
1

0
1
2
3
4
5
6
7

Cout

A,B,Cin
Lecture 2

24

Xilinx Virtex II FPGA

Systematic Implementation of
Combinational Logic
Same function as on previous slide, but this
time lets use a 4-input mux

6.111 Fall 2009

Full-Adder
Carry Out Logic

0
Cin
Cin
1

0
1
2
3

Cout

XC2V6000:
957 pins, 684 IOBs
CLB array: 88 cols x 96/col = 8448 CLBs
18Kbit BRAMs = 6 cols x 24/col = 144 BRAMs = 2.5Mbits
18x18 multipliers = 6 cols x 24/col = 144 multipliers

A,B

Lecture 2

25

6.111 Fall 2009

Virtex II CLB

Lecture 2

Lecture 2

26

Virtex II Slice Schematic

Control signals whose values

are set at configuration time.
The Xilinx tools compile your
design and determine the
settings

16 bits of RAM which can be configured as a 16x1

single- or dual-port RAM, a 16-bit shift register,
or a 16-location lookup table
Figures from Xilinx Virtex II datasheet
6.111 Fall 2009

Figures from Xilinx Virtex II datasheet

Figures from Xilinx Virtex II datasheet

27

6.111 Fall 2009

Lecture 2

28

Virtex II Sum-of-products
Wide fan-in OR

Wide fan-in AND

Figures from Xilinx Virtex II datasheet
6.111 Fall 2009

Lecture 2

29