ELECTRICAL AND COMPUTER ENGINEERING DEPARTMENT, OAKLAND UNIVERSITY

ECE-2700: Digital Logic Design Fall 2023

Unit 5 – Combinational Circuits

BASIC CIRCUITS
MULTIPLEXERS (MUXS)
▪ This logic circuit selects one of many input signals and forwards the selected input to the output line.
▪ Boolean equations for MUX2-to-1, MUX4-to-1, MUX8-to-1:
s a b y s y a
a 0 a
0 0 0 0 0 0 a 0
1 b b b
y 0 0 1 0 1 y 1
0 1 0 1
0 1 1 1 c c 2
b 1 2
1 0 0 0 d
d
1 0 1 1 3 3
y
s 1 1 0 0 e
2 4
1 1 1 1
s f 5
y = sa + sb y = s1s0a s1s0b + g
6
s1s0c + s1s0d h 7

3
s
y = s2s1s0a + s2s 1s0b + s2s 1s0c + s2s 1s0d +

s2s1s0e + s2s 1s0f + s2s 1s0g + s2s 1s0h

0
N inputs

1 ▪ Normally, a multiplexer has 𝑁 = 2𝑛 inputs, one output, and a selector with 𝑛 bits.
y
But, if a multiplexer has 𝑁 inputs, where 𝑁 is not a power of 2, the number of bits of the
...
...

▪
selector is given by: ⌈𝑙𝑜𝑔2 𝑁⌉.
N-1

n = log2N
s

MULTIPLEXERS WITH ENABLE

▪ An enable input provides us with an extra level of control. If the multiplexer is enabled, the circuit just works. If the
multiplexer is not enabled, no input is allowed into the output, and the multiplexer output becomes ‘0’ (if the output is active-
high) or ‘1’ (if the output if active-low).
▪ The enable input can be either active-high or active-low:

ACTIVE HIGH ENABLE E ACTIVE LOW ENABLE E

E s1 s0 y a E s1 s0 y a
0 0
1 0 0 a b 0 0 0 a b
1 0 1 b 1 y 0 0 1 b 1 y
1 1 0 c 0 1 0 c
c c
1 1 1 d 2 0 1 1 d 2
0 X X 0 d 1 X X 0 d
3 3
2 2
This PDF document was edited with Icecream PDF Editor.
Upgrade to PRO to remove watermark. s s

1 Instructor: Daniel Llamocca

 ELECTRICAL AND COMPUTER ENGINEERING DEPARTMENT, OAKLAND UNIVERSITY
ECE-2700: Digital Logic Design Fall 2023

BUS MULTIPLEXERS

▪ Usually we want input signals to contain more than one bit.

I(0)m-1 0
▪ In the figure, each input signal contains ‘m’ bits. I(1)m-1 1
ym-1
▪ This ‘bus multiplexer’ can be built by ‘m’ multiplexers, each

...
...
taking care of only one bit for all the inputs.
I(N-1)m-1 N-1
n
m
I(0) 0
m I(0)m-2 0
N inputs

I(1) 1
m y I(1)m-2 1
... ym-2

...

...
...
m
I(N-1) N-1
I(N-1)m-2 N-1
n = log2N n
s
▪ We have ‘N’ inputs and therefore the selector has
𝑛 = ⌈𝑙𝑜𝑔2 𝑁⌉ bits.

...
▪ Note that the selector is the same for all the multiplexers.

I(0)0 0
I(1)0 1
y0

...
...
I(N-1)0 N-1

n = log2N
s

LOGIC CIRCUITS WITH MUXs

▪ Multiplexers can be used to implement Boolean Functions. The selector can be thought as the input variables, the input bits
are fixed values that are passed onto the output according to the selector.
▪ This multiplexor with fixed inputs implements a logic function. The functionality of this circuit is similar to that of a Look-Up
Table (LUT), which is a ROM-like circuit whose values are obtained by addressing them. FPGAs implement Boolean functions
using LUTs. In the example, a 3-to-1 LUT is an LUT with 3 inputs, i.e., it contains 23 = 8 addresses.

"Read-only memory
s2 s1 s0 with 8 positions"
x y z f 0
1


0
2
0 1 3
1 3 f
1 4
1
5
0 address 6
1
7
0
0
1
function 1
s = xyz
to be 3-to-1
This PDF document was edited with Icecream PDF Editor.
implemented
Upgrade to PRO to remove watermark.
Look-up Table

2 Instructor: Daniel Llamocca

 ELECTRICAL AND COMPUTER ENGINEERING DEPARTMENT, OAKLAND UNIVERSITY
ECE-2700: Digital Logic Design Fall 2023

▪ Note that for a 𝑛-variable function, we need a MUX 2𝑛 -to-1 with fixed inputs.

▪ However, it is possible to use a MUX 2𝑛−1 -to-1. This might require extra NOT gates and non-fixed inputs.
✓ 𝐹(𝑥, 𝑦, 𝑧) = ∑(𝑚0 , 𝑚2 , 𝑚4 , 𝑚6 , 𝑚7 ).

x y z F
0 0 0 1
0 0 1 0 𝑧 𝑧 0 1 0 1 0
0 1 0 1 𝑧 1 F 0 1 F 0 1 F
0 1 1 0 𝑧 2 1 2 1 2
1 0 0 1 1 3 𝑥 3 𝑦 3
1 0 1 0
2 2 2
1 1 0 1
1 1 1 1 1 s = xy s = yz s = xz

✓ 𝐹(𝑥, 𝑦, 𝑧) = ∑(𝑚0 , 𝑚1 , 𝑚3 , 𝑚5 , 𝑚7 ).
x y z F
0 0 0 1 1 0 𝑥 0 𝑦 0
0 0 1 1 𝑧 1 F 1 1 F 1 1 F
0 1 0 0 𝑧 2 0 2 0 2
0 1 1 1 𝑧 3 1 3 1 3
1 0 0 0
1 0 1 1 2 2 2
1 1 0 0 s = xy s = yz s = xz
1 1 1 1

✓ 𝐹(𝑥, 𝑦) = ∑(𝑚0 , 𝑚1 , 𝑚2 )

x y f 1 0
1 f 1 0 1 0
0 0 1 1
1 2 f f
0 1 1 𝑦 1 1
0 3 𝑥
1 0 1
1 1 0 2
x y
s = xy

This process of using multiplexors to implement functions can be performed in a systematic fashion using Shannon’s
expansion theorem. As we will see later for LUTs, this has an important application in the implementation of Boolean
functions on FPGAs.

Example:
▪ Implement a MUX 4-to-1 using MUXes 2to-1.

a 0
x y f a 0
b 1 f b 1
0 0 a
c 2 0 fXOR
0 1 b
1 0 c d 3
1
1 1 d c 0
2
s = xy d 1

y x

This PDF document was edited with Icecream PDF Editor.

Upgrade to PRO to remove watermark.

3 Instructor: Daniel Llamocca

 ELECTRICAL AND COMPUTER ENGINEERING DEPARTMENT, OAKLAND UNIVERSITY
ECE-2700: Digital Logic Design Fall 2023

SHANNON’S EXPANSION

▪ This is useful to express a Boolean function in terms of multiplexers

▪ An 𝑛-variable Boolean function can be decomposed into two (𝑛 − 1)-variable Boolean functions:

𝑓(𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = 𝑥1 𝑓(0, 𝑥2 , … , 𝑥𝑛 ) + 𝑥1 𝑓(1, 𝑥2 , … , 𝑥𝑛 )

▪ In the equation, we use the variable 𝑥1 to decompose, but we can use any variable 𝑥𝑖 , 𝑖 = 1: 𝑛. For example, using 𝑥𝑛 :
𝑓(𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = 𝑥𝑛 𝑓(𝑥1 , 𝑥2 , … ,0) + 𝑥𝑛 𝑓(𝑥1 , 𝑥2 , … ,1)

▪ A short-hand notation of the Shannon expansion is as follows:

0
𝑓 = 𝑥̅𝑖 𝑓𝑥̅𝑖 + 𝑥𝑖 𝑓𝑥𝑖
1

Note that we can implement 𝑓 using a 2-to-1 MUX, as the equation resembles that of the MUX.

▪ Examples:
✓ 𝑓 = 𝑥1 𝑥2 + 𝑥1 𝑥3 + 𝑥2 𝑥3 x3 0
𝑓 = 𝑥1 𝑓(0, 𝑥2 , 𝑥3 ) + 𝑥1 𝑓(1, 𝑥2 , 𝑥3 ) = 𝑥1 (𝑥3 + 𝑥2 𝑥3 ) + 𝑥1 (𝑥2 + 𝑥2 𝑥3 )
x3 1
We can further apply Shannon expansion to two variable functions: 0 f
𝑓 = 𝑥1 𝑔(𝑥2 , 𝑥3 ) + 𝑥1 ℎ(𝑥2 , 𝑥3 )
𝑔(𝑥2 , 𝑥3 ) = 𝑥2 𝑔(0, 𝑥3 ) + 𝑥2 𝑔(1, 𝑥3 ) = 𝑥2 (𝑥3 ) + 𝑥2 (𝑥3 ) 1
ℎ(𝑥2 , 𝑥3 ) = 𝑥2 ℎ(0, 𝑥3 ) + 𝑥2 ℎ(1, 𝑥3 ) = 𝑥2 (0) + 𝑥2 (1) 0 0

1 1

x2 x1

✓ 𝑓 = 𝑧𝑦 + 𝑧𝑥 + 𝑥𝑦𝑧
𝑓 = 𝑥𝑓(0, 𝑦, 𝑧) + 𝑥𝑓(1, 𝑦, 𝑧) = 𝑥 (𝑧𝑦) + 𝑥(𝑧𝑦 + 𝑧 + 𝑦𝑧) 0 0

𝑓 = 𝑥𝑔(𝑦, 𝑧) + 𝑥ℎ(𝑦, 𝑧) 1
𝑔(𝑦, 𝑧) = 𝑧𝑦 = 𝑦𝑔(0, 𝑧) + 𝑦𝑔(1, 𝑧) = 𝑦(0) + 𝑦(𝑧) 0 f
ℎ(𝑦, 𝑧) = 𝑧𝑦 + 𝑧 + 𝑦𝑧 = 𝑦ℎ(0, 𝑧) + 𝑦ℎ(1, 𝑧) = 𝑦(𝑧) + 𝑦(1)
1
We can implement 𝑧 using MUXs: 0

𝑝(𝑧) = 𝑧 = 𝑧𝑝(0) + 𝑧𝑝(1) = 𝑧(1) + 𝑧(0) 1 1

Finally, we implement the function 𝑓 with only 2-to-1 multiplexors:

y x

0 0
1 0
1
0 1 0 f

1
0

1 1

z y x

This PDF document was edited with Icecream PDF Editor.

Upgrade to PRO to remove watermark.

4 Instructor: Daniel Llamocca

 ELECTRICAL AND COMPUTER ENGINEERING DEPARTMENT, OAKLAND UNIVERSITY
ECE-2700: Digital Logic Design Fall 2023

DEMULTIPLEXERS s1 s 0 a b c d a
0 a 0
▪ A demultiplexer performs the opposite
s a b y 0 0 y 0 0 0 y 1 b
operation of the multiplexers.
0 y 0 0 1 0 y 0 0
2 c
1 0 y 1 b 1 0 0 0 y 0
1 1 0 0 0 y 3 d
2
s
s
Application: Time Division Multiplexing (TDM)
1/8000 s
▪ Digital Telephony: (4 KHz bandwidth)
▪ 8000 samples per second, 8 bits per sample. This ( 0
0 1 2 3 0 1 2 3 ... 0 (
requires 64000 bits per second.
▪ In the figure, there are 4 telephone lines (4 ( 1 1 (
signals). To take advantage of the communication
channel, only one signal is transmitted at a time.
( 2 2 (
We can do this since we are only required to
transmit samples of a particular signal at the rate
( 3 3 (
2 2
of 8000 samples per second (or 125 us between
samples, this is controlled by counters).
COUNTER COUNTER

DECODERS
▪ Generally speaking, decoders are circuits that transform the inputs into outputs following a certain rule, provided that the
number of outputs is greater than or equal to the number of inputs.
▪ Here, we discuss standard decoders for which a specific input/output rule exists. These decoders have 𝑛 inputs and 2𝑛
outputs. We show examples of: a 2-to-4 decoder, 3-to-8 decoder, and a 2-to-4 decoder with enable. The output 𝑦𝑖 is
activated when the decimal value of the input 𝑤 is equal to 𝑖.

w1 w0 y3 y2 y1 y0
w n y 0 0 0 0 0 1
2n w 2
DECODER 0 1 0 0 1 0 DECODER 4 y
1 0 0 1 0 0
1 1 1 0 0 0

w2 w1 w0 y7 y6 y5 y4 y3 y2 y1 y0
0 0 0 0 0 0 0 0 0 0 1 E w1 w0 y3 y2 y1 y0
0 0 1 0 0 0 0 0 0 1 0 DECODER
0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 w 2 4 y
1 0 1 0 0 1 0 with
0 1 1 0 0 0 0 1 0 0 0 w3 8 y enable
1 0 0 0 0 0 1 0 0 0 0 DECODER 1 1 0 0 1 0 0 E
1 0 1 0 0 1 0 0 0 0 0 1 1 1 1 0 0 0
1 1 0 0 1 0 0 0 0 0 0 0 X X 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0

LOGIC CIRCUITS WITH DECODERS w2 w1 w0

y0
▪ Decoders can be used to implement Boolean x y z f y1
functions. Note that each output is actually a x w2 y2
0 0 0 0
minterm. y3
0 0 1 0 y w1
0 1 0 1 y4
▪ In the example, minterm 2 is activated when z w0 y5
xyz=010, here only y2 is 1. Also: y5 is activated 0 1 1 1
1 0 0 0 y6
when xyz=101, y7 is activated when xyz=111. y7
1 0 1 1
1 1 0 0
1 1 1 1
function
This PDF document was edited with Icecream PDF Editor. to be f
Upgrade to PRO to remove watermark. implemented

5 Instructor: Daniel Llamocca

 ELECTRICAL AND COMPUTER ENGINEERING DEPARTMENT, OAKLAND UNIVERSITY
ECE-2700: Digital Logic Design Fall 2023

IMPLEMENTING DEMULTIPLEXORS WITH DECODERS

▪ By utilizing the enable input of a decoder as our input signal, we can effectively E w1 w0 y3 y2 y1 y0
implement a demultiplexor using a decoder:
1 0 0 0 0 0 1
1 0 1 0 0 1 0
a 1 1 0 0 1 0 0


s1 s0 a b c d 0 y0 a 1 1 1 1 0 0 0
b s1 w1 0 X X 0 0 0 0
0 0 x 0 0 0 x 1 y1 b
0 1 0 x 0 0 c s0 w0
2 y2 c
1 0 0 0 x 0
d w1 w0 y3 y2 y1 y0
1 1 0 0 0 x 3 x E y3 d
0 0 0 0 0 E
2 0 1 0 0 E 0
E = x 1 0
s 0 E 0 0
1 1 E 0 0 0
Application: Memory Decoding
▪ A 20-bit address line in a processor handles up to 220 = 1 𝑀𝐵 of addresses, each address containing one-byte of
information. We want to connect four 256KB memory chips to the processor.
▪ The pink-shaded circuit: i) addresses the memory chips, and ii) enables only one memory chip (via CE: chip enable) when
the address falls in the corresponding range. Example: if 𝑎𝑑𝑑𝑟𝑒𝑠𝑠 = 0𝑥5𝐹𝐹𝐹𝐹, → only memory chip 2 is enabled (CE=1).
If 𝑎𝑑𝑑𝑟𝑒𝑠𝑠 = 0𝑥𝐷0123, → only memory chip 4 is enabled.
1 00000 256 KB 256 KB 256 KB 256 KB
...

256KB Memory 1 2 3 4
3FFFF devices
40000 CE CE CE CE
2
256KB
...

7FFFF Memory 18 18 18 18
3 80000 space
256KB
...

BFFFF
4 C0000 address 20
256KB
...

address(17..0)
FFFFF
address(18) y0
w0 y1
w1 y2
address(19)
y3
ENCODERS
▪ Generally speaking, encoders are circuits that transform the inputs into outputs following a certain rule, provided that the
number of outputs is lower than the number of inputs.
▪ Here, we discuss standard encoders for which a specific input/output rule exists. These encoders have 2𝑛 inputs and 𝑛
outputs. The operation is exactly the opposite as in the case of the decoder: whenever an input 𝑤𝑖 is activated, then the
index 𝑖 appears at the output 𝑦 (in binary form).
▪ 4 to 2 encoder:
w3 w2 w1 w0 y1 y0
w 2n n y 0 0 0 1 0 0 w 4 2 y
ENCODER 0 0 1 0 0 1 ENCODER
0 1 0 0 1 0
1 0 0 0 1 1
Assumptions:
𝑦1 = 𝑤3 𝑤2 𝑤1 . 𝑤0 + 𝑤3 𝑤2 . 𝑤1 . 𝑤0 If 𝑤3 = 1 → 𝑤2 = 𝑤1 = 𝑤0 =0 Thus:
𝑦0 = 𝑤3 . 𝑤2 𝑤1 𝑤0 + 𝑤3 . 𝑤2 . 𝑤1 . 𝑤0 If 𝑤2 = 1 → 𝑤3 = 𝑤1 = 𝑤0 =0 𝑦1 = 𝑤2 + 𝑤3
If 𝑤1 = 1 → 𝑤3 = 𝑤2 = 𝑤0 =0 𝑦0 = 𝑤1 + 𝑤3
If 𝑤0 = 1 → 𝑤3 = 𝑤2 = 𝑤1 =0

▪ 8 to 3 encoder: 𝑦2 = 𝑤7 + 𝑤6 + 𝑤5 + 𝑤4
𝑦1 = 𝑤7 + 𝑤6 + 𝑤4 + 𝑤3
𝑦0 = 𝑤7 + 𝑤5 + 𝑤3 + 𝑤1
▪ Issues:
✓ If two or more inputs are activated, the output 𝑦𝑛−1 𝑦𝑛−2 … 𝑦0 is undefined.
✓ If no
This PDF document input
was is activated,
edited the output
with Icecream 𝑦𝑛−1 𝑦𝑛−2 … 𝑦0 is undefined. In this case, the result is ambiguous, as the result would
PDF Editor.
be the same as if only 𝑤0 = 1, i.e., 𝑦𝑛−1 𝑦𝑛−2 … 𝑦0 = 00 … 0.
Upgrade to PRO to remove watermark.

6 Instructor: Daniel Llamocca

 ELECTRICAL AND COMPUTER ENGINEERING DEPARTMENT, OAKLAND UNIVERSITY
ECE-2700: Digital Logic Design Fall 2023

PRIORITY ENCODERS

▪ Standard encoder: we check whether a specific input is activated for the output to have a value.
▪ What happens when more than one input is activated? A solution is to create an extra output that is activated to indicate
than an unexpected condition has occurred.
▪ An interesting alternative is to create a priority w3 w3 w2 w1 w0 y1 y0 z
encoder: if more than one input is activated, then we y1 0 0 0 0 0 0 0
only pay attention to the input bit of the highest order. w2 PRIORITY 1 x x x 1 1 1
For example if 𝑤 = 1101, then we only pay attention to w y0
1 ENCODER 0 1 x x 1 0 1
𝑤(3) = 1, if 𝑤 = 0111, we only pay attention to 𝑤(2) =
z 0 0 1 x 0 1 1
1. This results in the following truth table for a 4-to-2 w0 0 0 0 1 0 0 1
priority encoder:
▪ What if no input is activated? Here we run out of output
bits in 𝑦 to represent this case. Thus, we include an extra output 𝑧 that it is ‘0’ when no input activated, and ‘1’ otherwise.

▪ For the priority encoder 4 to 2, we can get the Boolean functions directly from the truth table as:
𝑦1 = 𝑤2 𝑤3 + 𝑤3
𝑦0 = 𝑤3 𝑤2 𝑤1 + 𝑤3 𝑧 = 𝑤3 𝑤2 𝑤1 𝑤0 = 𝑤3 + 𝑤2 + 𝑤1 + 𝑤0

We could simplify 𝑦1 and 𝑦0 (Boolean Theorems, K-maps, or Quine-McCluskey algorithm)

▪ Alternatively, we can create the following intermediate signals:

𝑖3 = 𝑤3 𝑖3 = 1 if 𝑤3 =1
𝑖2 = 𝑤3 𝑤2 𝑖2 = 1 if 𝑤2 = 1, 𝑤3 = 0
𝑖1 = 𝑤3 𝑤2 𝑤1 𝑖3 = 1 if 𝑤1 = 1, 𝑤2 = 𝑤3 = 0
𝑖0 = 𝑤3 𝑤2 𝑤1 𝑤0 𝑖3 = 1 if 𝑤0 = 1, 𝑤1 = 𝑤2 = 𝑤3 = 0

Then, notice that 𝑖3 = 1, 𝑖2 = 1, 𝑖1 = 1, 𝑖0 = 1 are exclusive:

If 𝑖3 𝑖2 𝑖1 𝑖0 𝑦1 𝑦0 𝑧
𝑤3 =1 1 0 0 0 1 1 1
𝑤2 = 1, 𝑤3 =0 0 1 0 0 1 0 1
𝑤1 = 1, 𝑤2 = 𝑤3 =0 0 0 1 0 0 1 1
𝑤0 = 1, 𝑤1 = 𝑤2 = 𝑤3 =0 0 0 0 1 0 0 1
𝑤0 = 𝑤1 = 𝑤2 = 𝑤3 =0 0 0 0 0 0 0 0

Note that the relationship of 𝑖3 𝑖2 𝑖1 𝑖0 to 𝑦1 𝑦0 is that of a binary encoder. If 𝑧 = 0, then 𝑦1 𝑦0 = 00.

𝑤3 𝑖3
𝑦1
𝑖2
𝑤2
𝑖1 ENCODER
𝑤1
𝑖0 𝑦0
𝑤0

PRIORITY ENCODER

This procedure can be applied to any priority encoder (e.g.: 8 to 3, 16 to 4).

This PDF document was edited with Icecream PDF Editor.

Upgrade to PRO to remove watermark.

7 Instructor: Daniel Llamocca

 ELECTRICAL AND COMPUTER ENGINEERING DEPARTMENT, OAKLAND UNIVERSITY
ECE-2700: Digital Logic Design Fall 2023

COMPARATORS

UNSIGNED NUMBERS a3 e3
▪ For 𝐴 = 𝑎3 𝑎2 𝑎1 𝑎0 , 𝐵 = 𝑏3 𝑏2 𝑏1 𝑏0 b3

✓ 𝐴 > 𝐵 when: a2 e2
𝑎3 = 1, 𝑏3 = 0 b2
Or: 𝑎3 = 𝑏3 and 𝑎2 = 1, 𝑏2 = 0 A=B
Or: 𝑎3 = 𝑏3 , 𝑎2 = 𝑏2 and 𝑎1 = 1, 𝑏1 = 0 a1 e1
Or: 𝑎3 = 𝑏3 , 𝑎2 = 𝑏2 , 𝑎1 = 𝑏1 and 𝑎0 = 1, 𝑏0 = 0 b1

a0 e0
b0
A<B
4 a3
A A=B
b3
COMPARATOR A<B
4 e3
B A>B
a2 AB
b2
e2 A>B
e3
a1
b1
e1 AB
e2
e3
a0
b0

SIGNED NUMBERS
▪ If 𝐴 ≥ 0 and 𝐵 ≥ 0, we can use the unsigned comparator.
▪ If 𝐴 < 0 and 𝐵 < 0, we can also use the unsigned comparator.
Example: 10002 < 10012 (-8 < -7). The closer the number is to e3
zero, the larger the unsigned value is. A=B A=B
4
▪ If one number is positive and the other negative: A
Example: 10002 < 01002 (-8 < 4). If we were to use the unsigned UNSIGNED A<B A<B
comparator, we would get 10002 > 01002. So, in this case, we 4 COMPARATOR
B
need to invert both the A>B and the A<B bit. A>B A>B

▪ Rule: For a 4-bit number in 2’s complement:

✓ If 𝑎3 = 𝑏3 , 𝐴 and 𝐵 have the same sign. Then, we do not need to invert any bit.
✓ If 𝑎3 ≠ 𝑏3 , 𝐴 and 𝐵 have a different sign. Then, we need to invert the A>B and A<B bits of the unsigned comparator.

𝑒3 = 1 when 𝑎3 = 𝑏3 . 𝑒3 = 0 when 𝑎3 ≠ 𝑏3 .
Then it follows that: (𝐴 < 𝐵)𝑠𝑖𝑔𝑛𝑒𝑑 = 𝑒̅3 (𝐴 < 𝐵)𝑢𝑛𝑠𝑖𝑔𝑛𝑒𝑑 = 𝑒3 (𝐴 < 𝐵)𝑢𝑛𝑠𝑖𝑔𝑛𝑒𝑑
(𝐴 > 𝐵)𝑠𝑖𝑔𝑛𝑒𝑑 = 𝑒3 (𝐴 > 𝐵)𝑢𝑛𝑠𝑖𝑔𝑛𝑒𝑑

ALTERNATIVE APPROACH
▪ Here, we perform A-B in 2C. If the result is positive (MSB=0), then A  B. If the result is negative (MSB=1), then A < B. We
use an 2C adder/subtractor unit to implement this operation (R=A-B):
✓ Signed numbers: we need to sign-extend the inputs to
𝐴 𝐵
consider the worst-case scenario.
✓ Unsigned numbers: we need to zero-extend the inputs to 𝑛 𝑛
convert the values to 2C arithmetic. 𝐴 𝑛−1 𝑛 𝑛 𝐵𝑛−1 𝑅𝑛 𝑅𝑛−1 ... 𝑅0
▪ To determine whether 𝐴 is greater than 𝐵, we use the MSB (𝑅𝑛 ): ...
1→𝐴−𝐵 <0 𝑛 +1 𝑛 +1
𝑅𝑛 = {
0→𝐴−𝐵 ≥0
▪ To determine whether 𝐴 = 𝐵, we compare the 𝑛 + 1 bits of 𝑅 to +/- +/- 1
0 (𝑅 = 𝐴 − 𝐵). However, note that (𝐴 − 𝐵) ∈ [−2𝑛 + 1, 2𝑛 − 2].
So, the case 𝑅 = −2𝑛 = 10 … 0 will not occur. Thus, we only need 𝑛 +1 𝐴<𝐵 𝐴≥𝐵 𝐴=𝐵
𝑅 = 𝐴−𝐵
to compare
This PDF document the bits
was edited 𝑅𝑛−1
with Icecream 0. Editor.
to 𝑅0 toPDF
Upgrade to PRO to remove watermark.

8 Instructor: Daniel Llamocca

 ELECTRICAL AND COMPUTER ENGINEERING DEPARTMENT, OAKLAND UNIVERSITY
ECE-2700: Digital Logic Design Fall 2023

CODE CONVERTERS

BCD TO 7-SEGMENT DECODER

▪ The BCD system is useful as it provides a convenient human-readable format. For example, a keypad usually produces 4-bit
BCD codes every time a user presses a key. A big challenge is to convert a series of 4-bit BCD codes into its binary
representation. For example: 0101 1001 0111 = 597 in BCD, but 597 is 1001010101 in binary (unsigned).
▪ The BCD to 7-segment converter is a decoder because the number of outputs is greater than the number of inputs
▪ The truth table below assumes that the input and output are high-level.

b3 b2 b1 b0 a b c d e f g
a
0 0 0 0 1 1 1 1 1 1 0
0 0 0 1 0 1 1 0 0 0 0 f b 9: 6:
g
0 0 1 0 1 1 0 0 1 0 1
0 0 1 1 1 1 1 1 0 0 1 e c
0 1 0 0 0 1 1 0 0 1 1
0 1 0 1 1 0 1 1 0 1 1 d
0 1 1 0 1 0 1 1 1 1 1
0 1 1 1 1 1 1 0 0 0 0
1 0 0 0 1 1 1 1 1 1 1 4: 7: 2: 0: 1:
1 0 0 1 1 1 1 1 0 1 1
1 0 1 0 X X X X X X X
1 0 1 1 X X X X X X X
1 1 0 0 X X X X X X X
1 1 0 1 X X X X X X X
1 1 1 0 X X X X X X X
1 1 1 1 X X X X X X X

GRAY TO BCD DECODER g3g2g1g0 b3b2b1b0

▪ It is a decoder because the number of outputs is equal to the number of inputs.
▪ The figure shows the truth table for a 4-bit case. 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 0
0 0 1 0 0 0 1 1
0 1 1 0 0 1 0 0
0 1 1 1 0 1 0 1
0 1 0 1 0 1 1 0
0 1 0 0 0 1 1 1
1 1 0 0 1 0 0 0
1 1 0 1 1 0 0 1
1 1 1 1 X X X X
1 1 1 0 X X X X
1 0 1 0 X X X X
1 0 1 1 X X X X
1 0 0 1 X X X X
1 0 0 0 X X X X
BINARY TO GRAY DECODER AND GRAY TO BINARY DECODER
▪ These are decoders because the number of outputs is equal to the number of inputs
▪ For small input sizes, we can use the truth table method (see Lecture Notes – Unit 4). For large input sizes, the following
circuits are way more efficient:

b7 b6 b5 b4 b3 b2 b1 b0 g7 g6 g5 g4 g3 g2 g1 g0

This PDF document was edited with Icecream PDF Editor.

Upgrade to PRO g g6 watermark.
to7remove g5 g4 g3 g2 g1 g0 b7 b6 b5 b4 b3 b2 b1 b0

9 Instructor: Daniel Llamocca

 ELECTRICAL AND COMPUTER ENGINEERING DEPARTMENT, OAKLAND UNIVERSITY
ECE-2700: Digital Logic Design Fall 2023

PARITY GENERATORS AND PARITY CHECKERS

▪ This is defined in the context of an error detection system with transmission and reception units.
▪ Data to be transmitted: 𝑋 = 𝑥𝑛−1 𝑥𝑛−2 … 𝑥1 𝑥0 Transmitted stream: 𝑌 = 𝑥𝑛−1 𝑥𝑛−2 … 𝑥1 𝑥0 𝑝, p: parity bit
▪ Parity definition:
✓ Even Parity: 𝑌 has an even number of 1s → pe=1, 0 otherwise
✓ Odd Parity: 𝑌 has an odd number of 1s → po=1, 0 otherwise.
▪ This definition is problematic since p is not known. An alternative definition, based on the actual data X is:
✓ Even Parity: X has an odd number of 1s → pe = 1, 0 otherwise
✓ Odd Parity: X has an even number of 1s → po = 1, 0 otherwise.
▪ Parity Generator: Circuit that generates the parity bit based on the actual data X
▪ Parity Checker: Circuit that verifies whether the stream Y has the correct parity.

Example:
▪ For the following error detection system, 𝑋 = 𝑥2 𝑥1 𝑥0 , 𝑛 = 3. The parity generator and checker are always of the same parity:
✓ Even Parity Generator: It generates the parity bit pe. ✓ Odd Parity Generator: It generates the parity bit po.
✓ Even Parity Checker: It verifies that the received ✓ Odd Parity Checker: It verifies that the received stream
stream Y has even parity. If so, rpe =0, otherwise rpe=1 Y has odd parity. If so, rpo=0, otherwise rpo=1 (to signal
(to signal an error) an error)
𝑝𝑒 = 𝑥2 𝑥1 𝑥0 , 𝑟𝑝𝑒 = 𝑥2 𝑥1 𝑥0 𝑝𝑒 𝑝𝑜 = 𝑥2 𝑥1 𝑥0 , 𝑟𝑝𝑜 = 𝑥2 𝑥1 𝑥0 𝑝𝑜

x2 x2
x1 x1
x0 x0

Transmitted bits rpe

Even/Odd pe Even/Odd
Parity Parity
Generator po Checker rpo

Even Parity Even Parity Odd Parity Odd Parity

Generator Checker Generator Checker
x2 x1 x0 pe x2 x1 x0 pe rpe x2 x1 x0 po x2 x1 x0 po rpo
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1
0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 0 1 0
0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 0
0 1 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 1
1 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0
1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 1
1 1 0 0 0 1 1 0 0 1 1 0 1 0 1 1 0 1
1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0
1 0 0 0 1 1 0 0 0 0
1 0 0 1 0 1 0 0 1 1
1 0 1 0 0 1 0 1 0 1
x2 x2
pe 1 0 1 1 1 po 1 0 1 1 0
x1 x1
1 1 0 0 0 1 1 0 0 1
x0 x0
1 1 0 1 1 1 1 0 1 0
1 1 1 0 1 1 1 1 0 0
1 1 1 1 0 1 1 1 1 1
x2 x2
x1 x1
x0 rpe x0 rpo
po po

▪ In general for 𝑋 = 𝑥𝑛−1 𝑥𝑛−2 … 𝑥1 𝑥0 : 𝑝𝑒 = 𝑥𝑛−1 𝑥𝑛−2 … 𝑥1 𝑥0 . 𝑝𝑜 = 𝑥𝑛−1 𝑥𝑛−2 … 𝑥1 𝑥0
✓ If the # of 1’s in an n-bit stream is odd, the n-bit input XOR gate will return 1, 0 otherwise.
✓ If the # of 1’s in an n-bit stream is even, the n-bit input XNOR gate will return 1, 0 otherwise.
▪ 𝑟𝑝𝑒 = 𝑥𝑛−1 𝑥𝑛−2 … 𝑥1 𝑥0 𝑝𝑒 . We expect the number of 1s in Y to be even, → an XNOR will detect this. However, we want
𝑟𝑝𝑒 to be 1 when this does not happen (to signal an error). Hence, we use an 𝑛 + 1-bit input XOR gate.
▪ 𝑟𝑝𝑜 = 𝑥𝑛−1 𝑥𝑛−2 … 𝑥1 𝑥0 𝑝𝑜 . We expect the number of 1s in to be odd, → an XOR will detect this. However, we want 𝑟𝑝𝑜
to be 1 when this does not happen (to signal an error). Hence, we use an 𝑛 + 1-bit input XNOR gate.
This PDF document was edited with Icecream PDF Editor.
Upgrade to PRO to remove watermark.

10 Instructor: Daniel Llamocca

 ELECTRICAL AND COMPUTER ENGINEERING DEPARTMENT, OAKLAND UNIVERSITY
ECE-2700: Digital Logic Design Fall 2023

COMPLEX CIRCUITS
LOOK-UP TABLES (LUTS)
▪ The LUT contents are hardwired in this circuit. A 4-to-1 LUT can be seen as a ROM with 16 addresses, each address holding
one bit. It can also be seen as a multiplexor with fixed inputs.
▪ This is how FPGAs implement logic functions. A 4-to-1 LUT can implement any 4-input logic function.
data(0)
4-to-1 data(0) 0
Look-up Table data(1)
data(1) 1
(Read-only memory data(2) data(2) 2
with 16 positions) data(3) data(3) 3
data(4) data(4) 4
data(5)
data(5) 5
data(6) 6 OLUT
ILUT(3) 4 data(6) OLUT
ILUT data(7) 7
ILUT(2) LUT OLUT data(7) data(8) 8
ILUT(1) 4 to 1
address data(8) data(9) 9
ILUT(0)
data(9) data(10) 10
data(11) 11
data(10)
data(12) 12
data(11) data(13) 13
data(12) data(14) 14
data(13) data(15) 15
data(14)
4
data(15)
ILUT
LARGER LUTS
▪ A larger LUT can be generated by building a circuit that allows for more ROM positions. NI NI-1 LUT
▪ Efficient method: A larger LUT can also be built by combining LUTs with multiplexers as NI1 to 1 0
shown in the figure on the right. We can build a NI-to-1 LUT with this method.
▪ The figure below shows a case for a LUT 6-to-1 built out of two LUT 5-to-1. Each LUT 5- LUT
to-1 is built out of two LUT 4-to-1. 1
NI1 to 1
▪ We can build a NI-to-NO LUT using NO NI-to-1 LUTs. This can be seen as a ROM with 2𝑁𝐼
addresses, each address holding 𝑁𝑂 bits.
LUT NI-to-1
4 LSBs ILUT(3..0)
ILUT

6
6 bits
4 4 4 4 6 6 LUT
6 to 1
b5 ... b1 b0
b5
2 MSBs

64 words of 6 bits

6 LUT
LUT4

LUT4

LUT4

LUT4

6 to 1
b4 6
column 5

column 1
column 0
 6
...
6
...

ILUT(4)
MUX MUX
6 LUT
ILUT(5) 6 to 1
LUT5-to-1 b0
MUX

LUT 6-to-6 LUT 6-to-6

OLUT(i) LUT6-to-1

LUT DECOMPOSITION USING SHANNON EXPANSION

▪ LUT size grows exponentially with the size of the input. For a 𝑛-variable Boolean function, Shannon expansion provides a
systematic way of implementing that function with LUTs and multiplexors, thereby optimizing resources.
▪ An 𝑛-variable Boolean function can be 𝑥2
decomposed into two (𝑛 − 1)-variable 𝑥3 LUT 𝑔 𝑥2,, 𝑥3 , 𝑥4 , 𝑥5 = 𝑓 0, 𝑥2,, 𝑥3 , 𝑥4 , 𝑥5
Boolean functions and a MUX using 𝑥4 4 to 1
Shannon expansion. 𝑥5
0
𝑓 𝑥1 , 𝑥2,, 𝑥3 , 𝑥4 , 𝑥5
▪ Example: 5-variable function. Instead of
𝑥 1
using a 5-to-1 LUT, we decompose the 2
𝑥3 LUT
function using Shannon expansion. Then
𝑥4 4 to 1 ℎ 𝑥2,, 𝑥3 , 𝑥4 , 𝑥5 = 𝑓 1, 𝑥2,, 𝑥3 , 𝑥4 , 𝑥5
we canwas
This PDF document implement it using
edited with a MUXPDF
Icecream 2-to-1
Editor.
𝑥5
and two 4-to-1 LUTs.
Upgrade to PRO to remove watermark.
𝑥1
11 Instructor: Daniel Llamocca
 ELECTRICAL AND COMPUTER ENGINEERING DEPARTMENT, OAKLAND UNIVERSITY
ECE-2700: Digital Logic Design Fall 2023

Example:
▪ Using 3-to-1 LUTs and 2-to-1 MUXes, implement the following Boolean function (specify the contents of the LUTs):
𝑓(𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ) = 𝑥1 𝑥2 𝑥4 + 𝑥3 (𝑥4 + 𝑥5 ) + 𝑥1 𝑥2 𝑥5

𝑓 = 𝑥1 𝑓(0, 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ) + 𝑥1 𝑓(1, 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ) = 𝑥1 (𝑥3 (𝑥4 + 𝑥5 ) + 𝑥2 𝑥5 ) + 𝑥1 (𝑥2 𝑥4 + 𝑥3 (𝑥4 + 𝑥5 ))

✓ 𝑔(𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ) = 𝑓(0, 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ) = 𝑥3 (𝑥4 + 𝑥5 ) + 𝑥2 𝑥5

𝑔 = 𝑥2 𝑔(0, 𝑥3 , 𝑥4 , 𝑥5 ) + 𝑥2 𝑔(1, 𝑥3 , 𝑥4 , 𝑥5 ) = 𝑥2 (𝑥3 (𝑥4 + 𝑥5 ) + 𝑥5 ) + 𝑥2 (𝑥3 (𝑥4 + 𝑥5 ))

Note that: 𝑔(0, 𝑥3 , 𝑥4 , 𝑥5 ) = 𝑓(0,0, 𝑥3 , 𝑥4 , 𝑥5 ), 𝑔(1, 𝑥3 , 𝑥4 , 𝑥5 ) = 𝑓(0,1, 𝑥3 , 𝑥4 , 𝑥5 )

✓ ℎ(𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ) = 𝑓(1, 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ) = 𝑥2 𝑥4 + 𝑥3 (𝑥4 + 𝑥5 )

ℎ = 𝑥2 ℎ(0, 𝑥3 , 𝑥4 , 𝑥5 ) + 𝑥2 ℎ(1, 𝑥3 , 𝑥4 , 𝑥5 ) = 𝑥2 (𝑥3 (𝑥4 + 𝑥5 )) + 𝑥2 (𝑥4 + 𝑥3 (𝑥4 + 𝑥5 ))

Note that: ℎ(0, 𝑥3 , 𝑥4 , 𝑥5 ) = 𝑓(1,0, 𝑥3 , 𝑥4 , 𝑥5 ), ℎ(1, 𝑥3 , 𝑥4 , 𝑥5 ) = 𝑓(1,1, 𝑥3 , 𝑥4 , 𝑥5 )

These four 3-variable functions will be implemented using 3-to-1 LUTs. We are ready to sketch the circuit using 3-to-1 LUTs
and 2-to-1 MUXes. This is how multi-variable functions are implemented on FPGAs.

In order to get the LUT contents, we can either evaluate every 3-variable function that was generated, or we can just fill up
the truth table for 𝑓 and identify the LUT contents for each 3-variable function.

𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑓
0 0 0 0 0 0
0 0 0 0 1 1
0 0 0 0 0 1 0 0
𝑥3
1 1
𝑥4 LUT 𝑔(0, 𝑥3 , 𝑥4 , 𝑥5 ) = 𝑓 0,0, 𝑥3 , 𝑥4 , 𝑥5 0 0 0 1 1 1
0 1 3 to 1 0 0 1 0 0 0
𝑥5 0 0 1 0 1 1
1 1 0 𝑔(𝑥2 , 𝑥3 , 𝑥4 , 𝑥5) = 𝑓 0, 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 0 0 1 1 0 0
0 1 0 0 1 1 1 1
1 0 1 0 1 0 0 0 0
𝑥3 0 1 0 0 1 1
0 0 𝑥4 LUT
0 1 0 1 0 1
1 0 3 to 1 𝑔(1, 𝑥3 , 𝑥4 , 𝑥5 ) = 𝑓 0,1, 𝑥3 , 𝑥4 , 𝑥5
𝑥5 0 1 0 1 1 1
0 1 1 0 0 1
0 1 1 0 1 0
0 0 1 1 1 0 0
𝑓 𝑥1, 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 0 1 1 1 1 0
1 1 0 0 0 0 0
1 0 0 0 1 1
1 0 0 1 0 1
0 1
𝑥3 1 0 0 1 1 1
1 1
𝑥4 LUT ℎ(0, 𝑥3 , 𝑥4 , 𝑥5 ) = 𝑓 1,0, 𝑥3 , 𝑥4 , 𝑥5 1 0 1 0 0 1
1 0 3 to 1 1 0 1 0 1 0
𝑥5 1 0 1 1 0 0
1 0 0 1 0 1 1 1 0
1 1 1 1 0 0 0 1
0 1 1 ℎ(𝑥2, 𝑥3 , 𝑥4 , 𝑥5 ) = 𝑓 1, 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 1 1 0 0 1 1
𝑥3 1 1 0 1 0 0
0 0 𝑥4 LUT
1 1 0 1 1 0
0 0 3 to 1 ℎ(1, 𝑥3 , 𝑥4 , 𝑥5 ) = 𝑓 1,1, 𝑥3 , 𝑥4 , 𝑥5
𝑥5 1 1 1 0 0 1
1 1 1 0 1 1
1 1 1 1 0 0
𝑥2 𝑥1 1 1 1 1 1 0

This PDF document was edited with Icecream PDF Editor.

Upgrade to PRO to remove watermark.

12 Instructor: Daniel Llamocca

 ELECTRICAL AND COMPUTER ENGINEERING DEPARTMENT, OAKLAND UNIVERSITY
ECE-2700: Digital Logic Design Fall 2023

ARITHMETIC LOGIC UNIT (ALU)

▪ Two types of operation: Arithmetic and Logic (bit-wise). The sel(3..0) input selects the operation. sel(2..0) selects
the operation type within a specific unit. The arithmetic unit consist of adders and subtractors, while the Logic Unit consist
of 8-input logic gates.

a 8 sel Operation Function Unit

ARITHMETIC 0 0 0 0 y <= a Transfer 'a'
8 UNIT

ARITHMETIC
b 0 0 0 1 y <= a + 1 Increment 'a'
0 0 1 0 y <= a - 1 Decrement 'a'
0 0 0 1 1 y <= b Transfer 'b'
8 0 1 0 0 y <= b + 1 Increment 'b'
y y <= b - 1 Decrement 'b'
0 1 0 1
1 0 1 1 0 y <= a + b Add 'a' and 'b'
0 1 1 1 y <= a - b Subtract 'b' from 'a'
1 0 0 0 y <= NOT a Complement 'a'
LOGIC UNIT 1 0 0 1 y <= NOT b Complement 'b'
1 0 1 0 y <= a AND b AND

LOGIC
sel(3) 1 0 1 1 y <= a OR b OR
1 1 0 0 y <= a NAND b NAND
1 1 0 1 y <= a NOR b NOR
1 1 1 0 y <= a XOR b XOR
4 y <= a XNOR b XNOR
sel 1 1 1 1

BARREL SHIFTER
▪ Two types of operation: Arithmetic (mode=0, × 2𝑖 ) and Rotation (mode=1)
▪ Truth table for an 8-bit Barrel Shifter:
result[7..0] (output): It is shifted version of the input data[7..0]. sel[2..0]: number of bits to shift.
dir: It controls the shifting direction (dir=1: to the right, dir=0: to the left). When shifting to the right in the Arithmetic
Mode, we use sign extension so as properly account for signed input numbers.
mode = 0. ARITHMETIC MODE mode = 1. ROTATION MODE
dir dist[2..0] data[7..0] result[7..0] dir dist[2..0] data[7..0] result[7..0]
X 0 0 0 abcdefgh abcdefgh X 0 0 0 abcdefgh abcdefgh
0 0 0 1 abcdefgh bcdefgh0 0 0 0 1 abcdefgh bcdefgha
0 0 1 0 abcdefgh cdefgh00 0 0 1 0 abcdefgh cdefghab
0 0 1 1 abcdefgh defgh000 0 0 1 1 abcdefgh defghabc
0 1 0 0 abcdefgh efgh0000 0 1 0 0 abcdefgh efghabcd
0 1 0 1 abcdefgh fgh00000 0 1 0 1 abcdefgh fghabcde
0 1 1 0 abcdefgh gh000000 0 1 1 0 abcdefgh ghabcdef
0 1 1 1 abcdefgh h0000000 0 1 1 1 abcdefgh habcdefg
1 0 0 1 abcdefgh aabcdefg 1 0 0 1 abcdefgh habcdefg
1 0 1 0 abcdefgh aaabcdef 1 0 1 0 abcdefgh ghabcdef
1 0 1 1 abcdefgh aaaabcde 1 0 1 1 abcdefgh fghabcde
1 1 0 0 abcdefgh aaaaabcd 1 1 0 0 abcdefgh efghabcd
1 1 0 1 abcdefgh aaaaaabc 1 1 0 1 abcdefgh defghabc
1 1 1 0 abcdefgh aaaaaaab 1 1 1 0 abcdefgh cdefghab
1 1 1 1 abcdefgh aaaaaaaa 1 1 1 1 abcdefgh bcdefgha

data 8

shifter to shifter to rotate to rotate to

left right left right

dist 3
3

2
0
1
2

4
5
6
7

0
1
2

4
5
6
7

0
1

3
4
5
6
7

0
1

3
4
5
6
7

dir 0 1 0 1

mode 0 1
This PDF document was edited with Icecream PDF Editor.
8
Upgrade to PRO to remove watermark.
result
13 Instructor: Daniel Llamocca
 ELECTRICAL AND COMPUTER ENGINEERING DEPARTMENT, OAKLAND UNIVERSITY
ECE-2700: Digital Logic Design Fall 2023

PRACTICE EXERCISES
1. Implement the following functions using i) decoders and ii) multiplexers:
✓ 𝐹 = 𝑋 + 𝑌 + 𝑍𝑌 ✓ 𝐹 = (𝑋 + 𝑌 + 𝑍)(𝑋 + 𝑌 + 𝑍)
✓ 𝐹(𝑋, 𝑌, 𝑍) = ∑(𝑚0 , 𝑚2 , 𝑚6 ) ✓ 𝐹 = 𝑋𝑌 + 𝑌𝑍 + 𝑋𝑍
✓ 𝐹(𝑋, 𝑌, 𝑍) = ∏(𝑀2 , 𝑀4 , 𝑀7 ) ✓ 𝐹 = 𝑋𝑌𝑍

2. Using ONLY 4-to-1 MUXs, implement an 8-to-1 MUX.

3. Implement a 6-to-1 MUX using i) only NAND gates, and ii) only NOR gates.

4. Verify that the following circuit made of out of five 2-to-4 decoders with enable represents a 4-to-16 decoder with enable.
Tip: Create the truth table.

w0 y0 y0
w0
w1 y1 y1
w1
y2 y2
E y3 y3

w0 y0 y4
y1 y5
y0 w1
w2 w0 y2 y6
y1 E
w3 w1 y3 y7
y2
E E y0 y8
y3 w0
y1 y9
w1
y2 y10
E
y3 y11

w0 y0 y12
y1 y13
w1
y2 y14
E
y3 y15

5. Using only 2-to-1 MUXs, implement the XOR and XNOR gates.

6. Using only a 4-to-1 MUX, implement the following functions.

▪ 𝐹(𝑋, 𝑌, 𝑍) = ∑(𝑚1 , 𝑚3 , 𝑚5 , 𝑚7 ). ▪ 𝐹(𝑋, 𝑌, 𝑍) = ∑(𝑚3 , 𝑚5 , 𝑚7 ).
▪ 𝐹(𝑋, 𝑌, 𝑍) = ∑(𝑚1 , 𝑚3 , 𝑚5 ) ▪ 𝐹(𝑋, 𝑌, 𝑍) = ∑(𝑚5 , 𝑚7 ).

7. Complete the following timing diagram:

y3 w 10 11 01 01 11 01 00 10
w 2 3
y2 E
2
DECODER y1
E 1 P3
y0
0 P2
s1 s0
P1 Unknown
P3 P0
x1
P2
PRIORITY x0 y
P1 ENCODER
z f
P0 f
This PDF document was edited with Icecream PDF Editor.
Upgrade to PRO to remove watermark.

14 Instructor: Daniel Llamocca