ECE 2300

Digital Logic & Computer Organization

Spring 2018

Combinational Building Blocks

Lecture 5: 1
 Announcements
• Lab 2 prelab due tomorrow

• HW 1 due Friday

• HW 2 to be posted on Thursday

• Lecture 4 to be replayed on Thursday

– Instructor office hour moved to Friday (2/9)
10-11:30am @ Rhodes 320 (one-time change)

Lecture 5: 2
Example: K-Map to Simplify SOP
ABC Y
AB 000 1
C 00 01 11 10
001 1
010 1
0 1 1 1 1
011 0
C’
100 1
1 1 101 0
110 1
A’B’ 111 0

Lecture 5: 3
 Review: K-Map to Simplify POS
F=πA,B,C,D(0, 2, 6, 7, 8, 10)

AB
CD 00 01 11 10
Corners:
00 0 0 B+D
01 Other:
11 0 A+B’+C’

10 0 0 0
F=(B+D)•(A+B’+C’)

Lecture 5: 4
 Don’t Cares Combinations
• Sometimes the output for a particular input
combination is unspecified or irrelevant
– Such as an input combination that will never happen

• Represent as a ‘d’ (or ‘x’) in the truth table

• Example: Detect all even decimal digits except 6

– Four input bits are still required, but inputs 0-9 would
appear
– 10-15 are “don’t care” values

Lecture 5: 5
 Don’t Cares in Karnaugh Map
• Represent as a ‘d’ (or ‘x’) in the K-Map

• Don’t cares can be used as 1- or 0-cells as

needed

• Only circle if doing so creates a larger prime

implicant (and thus a more minimal expression)

Lecture 5: 6
 Don’t-Care Example
• Detect all even decimal digits except 6
– Inputs 10-15 will never occur

AB
CD 00 01 11 10

00 1 1 d 1

01 d

11 d d

10 1 d d

F = C’D’ + B’D’
Lecture 5: 7
 Multi-Level Logic
• So far we have primarily focused on two-level
representations for combinational logic

• Multi-level logic is typically more compact (i.e.,

cost-efficient) in practice

Lecture 5: 8
 Combinational Building Blocks
• More complex functions built from basic gates
– Comparators
– Multiplexers
– Decoders
– Encoders
…

• Typically tens to hundreds of transistors

– Used to be called Medium Scale Integration (MSI)

• Common building blocks for digital systems

Lecture 5: 9
 XOR Gate
X Y XÅY (XÅY)’
0 0 0 1
0 1 1 0
1 0 1 0
1 1 0 1

• XOR: F=X•Y’+X’•Y
– Similar to OR gate, except when inputs are 1
– Used for comparisons, error checking, etc.

• XNOR: F=X’•Y’+X•Y
– Complemented version of XOR Lecture 5: 10
 Equality Comparators Using XOR

X different
1-bit comparator Y

A0
B0
A1
4-bit comparator B1 different
A2
B2
A3
B3
Lecture 5: 11
 Multiplexer (“mux”)
• Connects one of n inputs to the output
– select control signals pick one of the n sources
• élog2nù select bits

• Useful when multiple data sources need to be

routed to a single destination
– Often arises from resource sharing
– Example: select 1-of-n data inputs to an adder

Lecture 5: 12
 2-to-1 Mux
• Selects one of two inputs to appear at the output

• Y = S’•I0 + S•I1
I1
Y = I1
2-to-1 mux I0
I1
Y S=1
I0
S
I1
Y = I0
I0

S=0

Lecture 5: 13
 4-to-1 Mux
4-to-1 mux
• Selects one of four inputs
to appear at the output I3
I2
Y
I1
• Y = S1’•S0’•I0 + I0
S1 S0
S1’•S0•I1 +
S1•S0’•I2 +
S1•S0•I3
I3 I3
I2 I2
I1 I1
I0 I0

0 0 1 0
Lecture 5: 14
 Cascading Multiplexers
• Large multiplexers can be implemented by
cascading smaller ones
S1 S0 S2 ? ? ?

I7 I7 2:1
I6 4:1 I6 mux
I5 mux
I4 I5 2:1
2:1 I4 mux
Y 4:1
I3 mux Y
mux
I2 4:1 I3 2:1
I1 mux 8:1 I2 mux
I0 mux I1 2:1
I0 mux

Lecture 5: 15
 Logic Functions Using Muxes
• Any function of n variables can be implemented
with a 2n:1 multiplexer
– Input variables connected to select inputs
– Data inputs tied to 0 or 1 according to truth table

A B Cin S
S Cout
0 0 0 00 0 0 0
0 0 1 11 0 0 1
0 2
0 1 0 11 0 1 3
Cout
0 1 1 00 1 0
1
4
5
8:1 MUX

1 0 0 11 0 1 6
1 7
1 0 1 00 1 S2 S1 S0

1 1 0 00 1
A B Cin
1 1 1 11 1
Lecture 5: 16
 Getting Away with a Smaller Mux
A B C D Y
• Can use 2n-1:1 0 0 0 0 1
multiplexer 0 0 0 1 1
and at most one 0 0 1 0 0
0 0 1 1 0
inverter
0 1 0 0 0
– Connect n-1 input 0 1 0 1 0 1 0
8:1 MUX
variables 0 1 1 0 0 0
0
1
2
to select inputs 0 1 1 1 1 D 3
Y
1 0 0 0 0 0 4
– Data inputs tied D’ 5
1 0 0 1 0 0 6
to 0, 1, 1 0 1 0 1 0 7
S2 S1 S0
nth variable, or 1 0 1 1 0
inverted 1 1 0 0 0 A B C
nth variable 1 1 0 1 0
1 1 1 0 0
1 1 1 1 0
Lecture 5: 17
 Decoder
• Binary decoders
– n inputs, 2n outputs
– Each output corresponds to a unique input value
– At most one output asserted at a time

• Example: A 1-to-2 decoder

A Y1 Y0
0 0 1
1 1 0

Lecture 5: 18
 2-to-4 Decoder
2:4
Decoder A1 A0
11 Y3
A1
10 Y2
A0
01 Y1
00 Y0
Y3

A1 A0 Y3 Y2 Y1 Y0
0 0 0 0 0 1 Y2
0 1 0 0 1 0
1 0 0 1 0 0 Y1
1 1 1 0 0 0
Y3 = A1 ⦁ A0
Y0
Y2 = A1 ⦁ A0’
Y1 = A1’ ⦁ A0
Y0 = A1’ ⦁ A0’ Lecture 5: 19
 Logic Functions Using Decoders
• n:2n decoder can be used
to implement any function 15 ABCD
of n variables 4:16
Decoder 14 ABCD'
13 ABC'D
– Connect variables to inputs 12 ABC'D'
11 AB'CD
– Appropriate minterms A I3 10 AB'CD'
B I2
summed using extra gates C I1
9 AB'C'D
8
to form the function D I0 7
AB'C'D'
A'BCD
6 A'BCD'
5 A'BC'D
4 A'BC'D'
3 A'B'CD
2 A'B'CD'
1 A'B'C'D
0 A'B'C'D'

Lecture 5: 20
Logic Functions Using Decoders
• F1 = A’B’C’D’ + AB’CD’ + ABC’D’
• F2 = A’B’C’ + A’B’CD
• F3 = A+B+C+D = (A’B’C’D’)’
15 ABCD
4:16
Decoder 14 ABCD'
13 ABC'D F1
12 ABC'D'
11 AB'CD
A I3 10 AB'CD'
B I2 9
C I1 AB'C'D
8 AB'C'D'
D I0 7 A'BCD F2
6 A'BCD'
5 A'BC'D
4 A'BC'D'
3 A'B'CD
2 A'B'CD'
1 A'B'C'D
0 A'B'C'D' F3

Lecture 5: 21
 Decoder with Enable

E A1 A0 Y3 Y2 Y1 Y0
2:4
Decoder 0 X X 0 0 0 0
11 Y3 1 0 0 0 0 0 1
A1
10 Y2 1 0 1 0 0 1 0
A0
01 Y1 1 1 0 0 1 0 0
E 00 Y0
1 1 1 1 0 0 0

X: don’t care input

Here 0XX covers 000, 001, 010, 011

Lecture 5: 22
 Decoder with Enable (2)
E A1 A0

Y3 = A1 ⦁ A0 ⦁ E Y3
Y2 = A1 ⦁ A0’ ⦁ E
Y1 = A1’ ⦁ A0 ⦁ E Y2
Y0 = A1’ ⦁ A0’ ⦁ E
Y1

Y0

Lecture 5: 23
 Encoders
• Opposite of decoders

• Binary encoders: 2n inputs and n outputs

Decoder Encoder

Lecture 5: 24
 4-to-2 Encoder
Exactly one input is asserted I3
Y1
I2
at any given time I1
Y0
I0

I3 I2 I1 I0 Y1 Y0
0 0 0 1 0 0
I2
Y1
0 0 1 0 0 1
I3
0 1 0 0 1 0
Y0
1 0 0 0 1 1 I1

Lecture 5: 25
 Priority Encoder
• Highest numbered inputs have priority when
multiple inputs are asserted at the same time
• Example: 4-to-2 priority encoder

I3 I2 I1 I0 Y1 Y0 None I3
Y1
1 X X X 1 1 0 I2
I1 Y0
0 1 X X 1 0 0 I0 None
0 0 1 X 0 1 0
0 0 0 1 0 0 0 Y1=I3+I3’I2=I3+I2
0 0 0 0 0 0 1 Y0=I3+I3’I2’I1=I3+I2’I1
None=I3’I2’I1’I0’

Lecture 5: 26
 Example: Microprocessor Interrupts
• In order for devices to get service, they interrupt
the microprocessor

• Most important requests are given priority

8:3
Priority
Encoder
power failure I7
disk error I6 Y2
I5 Y1
I4 Y0
I/O device requests I3 Microprocessor
I2
I1 None
I0

Lecture 5: 27
 Before Next Class
• H&H 3.1-3.2

Next Time

Sequential Logic: Clocks, Latches, Flip-Flops

Lecture 5: 28