CSE 140, Lecture 2

Combinational Logic
CK Cheng
CSE Dept.
UC San Diego

1
 Combinational Logic Outlines
1. Introduction
1. Scope
2. Review of Boolean Algebra
3. Review: Laws/Theorems and Digital Logic
2. Specification
3. Synthesis

2
1.1 Combinational Logic: Scope
• Description
– Language: e.g. C Programming, Verilog, VHDL
– Boolean algebra
– Truth table
• Design
– Schematic Diagram
– Inputs, Gates, Nets, Outputs
• Goal
– Validity: correctness, turnaround time
– Performance: power, timing, cost
– Testability: yield, diagnosis, robustness

3
Scope: Boolean Algebra for Logic
Cost: #gates, #nets, #pins
a a·b
b a·b + c·d
c y=e·(a·b+c·d)
d c·d
e
Schematic Diagram: Boolean Algebra:
5 primary inputs 5 variables
1 primary output 1 expression
4 gates (3 ANDs, 1 OR)
4 operators (3 ANDs, 1 OR)
9 signal nets
12 pins 5 literals
4
Scope: Boolean Algebra for Logic
a a·b
Schematic Diagram: b a·b + c·d
5 primary inputs c y=e·(a·b+c·d)
d c·d
4 components (gates) Boolean Algebra:
e
9 signal nets 5 literals
12 pins 4 operators
A. #inputs
B. #gates I. #operators
C. #nets II. #literals + #operators
D. #pins III. #literals + 2 #operators - 1
E. None

5
 Schematic Diagram vs. Boolean
Expression
• Boolean Expression: #literals, #operators
• Schematic Diagram: #gates, #nets, #pins

• One more example?

6
1.2 George Boole, 1815 - 1864
• Born to working class parents
• Taught himself mathematics and
joined the faculty of Queen’s
College in Ireland.
• Wrote An Investigation of the Laws
of Thought (1854)
• Introduced binary variables
• Introduced the three fundamental
logic operations: AND, OR, and
NOT.

Copyright © 2007 Elsevier 1-<7>

 Switching Algebra
• Boolean Algebra: multiple-valued logic, i.e. each variable
have multiple values.
• Switching Algebra: binary logic, i.e. each variable can be
either 1 or 0.
• Boolean Algebra ≠ Switching Algebra

Boolean Algebra

Switching Algebra

BB
Two Level Logic

<8>
 Scope: Binary Values
• Typically consider only two discrete values:
– 1’s and 0’s
– 1, TRUE, HIGH
– 0, FALSE, LOW
• 1 and 0 can be represented by specific voltage
levels, rotating gears, fluid levels, etc.
• Digital circuits usually depend on specific voltage
levels to represent 1 and 0
• Bit: Binary digit

Copyright © 2007 Elsevier 1-<9> 9

 Switching Algebra
• Two Level Logic: Sum of products, or product of sums, e.g. ab + a’c + a’b’, (a’+c )(a+b’)(a+b+c’)
• Multiple Level Logic: Many layers of two level logic with some inverters, e.g. (((a+bc)’+ab’)+b’c+c’d)’bc+c’e
Features of Digital Logic Design
• Multiple Outputs
• Don’t care sets
Handy Tools:
• DeMorgan’s Law: Complements
• Consensus Theorem
• Shannon’s Expansion
• Truth Table
• Karnaugh Map (single output, two level logic)

Boolean Algebra
Switching Algebra
BB
Two Level Logic

<10>
 Review of Boolean Algebra
Let B be a nonempty set with two 2-input operations, a
1-input operation `, and two distinct elements 0 and 1.
Then B is called a Boolean algebra if the following
axioms hold.
• Commutative laws: a+b=b+a, a·b=b·a
• Distributive laws: a+(b·c)=(a+b)·(a+c),
a·(b+c)=a·b+a·c
• Identity laws: a+0=a, a·1=a
• Complement laws: a+a’=1, a·a’=0
<11>
 1.3 Boolean algebra and switching functions:
Operators and Digital Logic Gates
Two-input operator Two-input operator One-input operator
AND (˄, ∙ ) OR (˅, + ) NOT (Complement, ` )
AND A B Y OR AB Y NOT A Y
0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1
1 1 1 1 1 1

A A
A 1
1 1
A A
0 A
0 0
0 dominates in AND 1 dominates in OR
0 blocks the output 1 blocks the output
1 passes signal A 0 passes signal A 12
 Review: Laws and Digital Logic
1. Identity A*1=A A+1=1
A*0=0 A+0=A

2. Complement A + A’ = 1 A * A’ = 0

T8. Distributive Law

A
A(B+C) = AB + AC A B
B
A
C
C

A+BC = (A+B)(A+C) A
A B
B A
C C
13
 Review: Laws and Digital Logic

T7. Associativity
C A
(A+B) + C = A + (B+C)
A B
B C

C A
(AB)C = A(BC)
A B
B C

14
 DeMorgan’s Theorem and Digital Logic
T12. DeMorgan’s Theorem (A+B)’ = A’B’ (AB)’ = A’ + B’

• Y = (AB)’ = A’ + B’ A
B
Y

A
Y
B

A
Y
B

• Y = A’ + B’= (A A
B
Y

B)’
1-<15>
DeMorgan’s Theorem: Bubble Pushing
• Pushing bubbles backward (from the output) or
forward (from the inputs) changes the body of the gate
from AND to OR or vice versa.
• Pushing a bubble from the output back to the inputs
puts bubbles on all gate inputs.

A A
Y Y
B B
• Pushing bubbles on all gate inputs forward toward the
output puts a bubble on the output and changes the
gate body.

A A
Y Y
B B
1-<16>
 Consensus Theorem
• AB+AC+B’C • (A+B)(A+C)(B’+C)
=AB+B’C =(A+B)(B’+C)

Exercise: to prove the reduction using

(1)Boolean algebra,
(2)Logic simulation and
(3) Shannon’s expansion

1-<17>
 Shannon’s Expansion
• Shannon’s expansion assumes a switching algebra
system
• Divide a switching function into smaller functions
• Pick a variable x, partition the switching function
into two cases: x=1 and x=0
– f(x,y,z,…)= xf(x=1,y,z,…) + x’f(x=0,y,z,…)
• For example
– f(x)=xf(1)+x’f(0)
– f(x,y)=xf(1,y)+x’f(0,y)

<18>
 Shannon’s Expansion: Example
f(x,y,z)=xf(?,y,z)+x’f(?,y,z)
A. ?=0
B. ?=1.

f(x,y)=(x+f(?,y))(x’+f(?,y))
• A. ?=0
• B. ?=1.

<19>
Shannon’s Expansion

<20>
Shannon’s Expansion

<21>
Shannon’s Expansion: Example
Which term in AB’+AC+BC can be
deleted?
A.AB’
B.AC
C.BC
D.None of the above

1-<22>
 Review Summary: Switching Algebra
and Karnaugh Map
Shannon’s expansion and consensus theorem
are used for logic optimization
•Shannon’s expansion divides the problem
into smaller functions
•Consensus theorem finds common terms
when we merge small functions
•Karnaugh map mimics the above two
operations in two dimensional space as a
visual aid.
1-<23>
 Part I. Combinational Logic
II) Specification
1. Language
2. Boolean Algebra
Canonical Expression: Sum of minterms and
Product of maxterms
3. Truth Table
4. Incompletely Specified Function

24
II. Specification
Decimal Addition 5
+ 7
12
Carry Sum

Binary Addition
1 1 1 Carry bits
1 0 1 5
+ 1 1 1 7
1 1 0 0 12

Carryout Sums

25
 Binary Addition: Hardware
• Half Adder: Two inputs (a,b) and two
outputs (carry, sum).

• Full Adder: Three inputs (a,b,cin) and two

outputs (carry, sum).

26
 Half Adder

Truth Table
a
a b carry sum

Sum 0 0 0 0
0 1 0 1
b 1 0 0 1
Carry 1 1 1 0

27
Switching Function
Switching Expressions:
Sum (a,b) = a’·b + a·b’
Carry (a, b) = a·b

Ex:
Sum (0,0) = 0’·0 + 0·0’ = 0 + 0 = 0
Sum (0,1) = 0’·1 + 0·1’ = 1 + 0 = 1
Sum (1,1) = 1’·1 + 1·1’ = 0 + 0 = 0
a
a
sum carry
b
b

28
 Full Adder
Truth Table

Cin Id a b cin carry sum

0 0 0 0 0 0
a 1 0 0 1 0 1
2 0 1 0 0 1
Sum 3 0 1 1 1 0
4 1 0 0 0 1
b
5 1 0 1 1 0
Carry 6 1 1 0 1 0
7 1 1 1 1 1

29
 Minterm and Maxterm

Id a b c carryout
0 0 0 0 0 a+b+c
1 0 0 1 0 a+b+c’
2 0 1 0 0 a+b’+c
3 0 1 1 1 a’ b c
4 1 0 0 0 a’+b+c
5 1 0 1 1 a b’c
6 1 1 0 1 a b c’
maxterm
7 1 1 1 1 abc

minterm

30
Minterms
f1(a,b,c) = a’bc + ab’c + abc’ + abc

a’bc = 1 iff (a,b,c,) = (0,1,1)

ab’c = 1 iff (a,b,c,) = (1,0,1)
abc’ = 1 iff (a,b,c,) = (1,1,0)
abc = 1 iff (a,b,c,) = (1,1,1)

f1(a,b,c) = 1 iff (a,b,c) = (0,1,1), (1,0,1), (1,1,0), or (1,1,1)

Ex: f1(1,0,1) = 1’01 + 10’1 + 101’ + 101 = 1

f1(1,0,0) = 1’00 + 10’0 + 100’ + 100 = 0

31
Maxterms
f2(a,b,c) = (a+b+c)(a+b+c’)(a+b’+c)(a’+b+c)

a + b + c = 0 iff (a,b,c,) = (0,0,0)

a + b + c’ = 0 iff (a,b,c,) = (0,0,1)
a + b’ + c = 0 iff (a,b,c,) = (0,1,0)
a’ + b + c = 0 iff (a,b,c,) = (1,0,0)

f2(a,b,c) = 0 iff (a,b,c) = (0,0,0), (0,0,1), (0,1,0), (1,0,0)

Ex: f2(1,0,1) = (1+0+1)(1+0+1’)(1+0’+1)(1’+0+1) = 1

f2(0,1,0) = (0+1+0)(0+1+0’)(0+1’+0)(0’+1+0) = 0

32
f1(a,b,c) = a’bc + ab’c + abc’ + abc
f2(a,b,c) = (a+b+c)(a+b+c’)(a+b’+c)(a’+b+c)
f1(a, b, c) = m3 + m5 + m6 + m7 = m(3,5,6,7)
f2(a, b, c) = M0M1M2M4 = M(0, 1, 2, 4)

iClicker: Does f1 = f2?

A.Yes
B.No.

33
The coverage of a single minterm. e.g. m4 = ab’c’

Id a b cin carry minterm 4 = ab’c’

0 0 0 0 0 0
1 0 0 1 0 0
2 0 1 0 0 0
3 0 1 1 1 0
4 1 0 0 0 1
5 1 0 1 1 0
6 1 1 0 1 0
7 1 1 1 1 0

Only one row has a 1.

34
The coverage of a single maxterm. E.g. M4 = a’+b+c

Id a b cin carry maxterm 4 = a+b+c

0 0 0 0 0 1
1 0 0 1 0 1
2 0 1 0 0 1
3 0 1 1 1 1
4 1 0 0 0 0
5 1 0 1 1 1
6 1 1 0 1 1
7 1 1 1 1 1

Only one row has a 0.

35
 Incompletely Specified Function
Don’t care set is important because it allows us to
minimize the function
Id a b f (a, b)
1) The input does not
0 0 0 1 happen.
1 0 1 0
2 1 0 1 2) The input happens, but
3 1 1 - the output is ignored.

Examples:
-Decimal number 0… 9 uses 4 bits. (1,1,1,1) does not happen.
-Final carry out bit (output is ignored).

36
 Incompletely Specified Function

Id a b c g(a,b,c)
g1(a,b,c)=a’b’c+a’bc+ab’b’+abc
=m1+m3+m4+m7
0 0 0 0 0
=∑ m(1,3,4,7)
1 0 0 1 1
2 0 1 0 -
g2(a,b,c)=(a+b+c)(a’+b’+c)
3 0 1 1 1
=M0M6
4 1 0 0 1
5 1 0 1 -
=∏M(0,6)
6 1 1 0 0
7 1 1 1 1 Exercise: Does g1(a,b,c) = g2(a,b,c)?

37