SME
Digital Logic Design · Problem type
Select lines, decoder outputs and truth tables
Use this for “How many select lines does an 8-to-1 mux need? How many rows and functions do 3 inputs give?”
Diagram
f = Σm(0, 2, 5, 7) = AC + A′C′.
3 inputs: 2³ = 8 rows of the truth table, one cell of the map each.
Each row’s output can be 0 or 1: 2⁸ = 256 functions.
This is an example. Type your own values to start a new problem.
N
Mux data inputs
example
s
Select lines
calculated
R
Truth-table rows
calculated
D
Decoder outputs
worked out (not typed)
Nf
Possible functions
calculated
Formulas
s
=
⌈log₂
N
⌉
3 = ⌈log₂ 8⌉
R
=
2
s
8
=
2
3
D
=
R
8 = 8
Nf
=
2
R
256
=
2
8
Assumptions
•
The s select lines spell a binary number, so they can pick one of 2ˢ data inputs.
•
Inside, an s-to-2ˢ decoder raises exactly one output, the one the select lines number.
•
Wire a function’s s inputs to the select lines and each data input to 0 or 1: one row each.
Step-by-step
WE KNOW
N = 8
FIND
select lines (s), truth-table rows (R), decoder outputs (D), possible functions (Nf)
Step 1 · Find select lines (s)
Use s = ⌈log₂ N⌉
Each
select
line
doubles
the
inputs
it
can
pick
from,
so
take
the
fewest
lines
with
2ˢ
at
least
N
.
⌈log₂
8⌉
=
3,
since
2
3
=
8
s
=
3
Step 2 · Find truth-table rows (R)
Use R = 2ˢ
Each select line is 0 or 1, so every new line doubles the rows.
R
=
2
3
R
=
8
Step 3 · Find decoder outputs (D)
Use D = R
A decoder raises exactly one output for each input pattern, so it has one output per row.
D
=
8
Step 4 · Find possible functions (Nf)
Use Nf = 2ᴿ
Each
row’
s
output
is
0
or
1
on
its
own,
so
the
choices
multiply:
2
for
every
row.
Nf
=
2
8
Nf = 256
Check
Put the numbers back in. Both sides should match.
3 = ⌈log₂ 8⌉ ✓
8
=
2
3
✓
8 = 8 ✓
256
=
2
8
✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
Related lessons
Combinational logic
Main lesson
Ripple-carry adder delay
Use this for “A 32-bit ripple-carry adder has 0.5 ns of carry delay per bit. How long does an add take, and how fast can it run?”
Name the gate from its truth table
Use this for “A two-input gate outputs 0 1 1 0 for AB = 00, 01, 10, 11. Which gate is it?”