UCI ICS 51 – Introduction to Computer Organization Copyright 2020 – Prof. Jennifer Wong-Ma
This content is protected and may not be shared uploaded or distributed.

ICS51 - Digital Logic: Multiplexor, Decoder, and more


Module 3 - Big Picture
Multiplexor (MUX)

Multiplexor Introduction
• Multiplexors are selectors which, based on the value of the ‘selector’ bits, the corresponding input is placed
on the output line. This gate creates the ability to “CHOOSE” between inputs.
• For example, consider at 2-input multiplexor (or also known as a 1-bit selector multiplexor)

o There are two 1-bit inputs A & B, a 1-bit selector input S, and the 1-bit output C
o If the selector S has value 0, then C = A. If S = 1, then C = B.
o This function can be created using the AND–OR gate network shown on the right. The boolean
expression is C = S ' A + S B.
• Multiplexors come in a variety of sizes, 2-input, 4-input, 8-input, etc. where n inputs means ⌈log2 ⌉
‘selector’, or ‘control’, bits.
o Ex: Implementation of an 8-input multiplexor (aka 3-bit selector
multiplexor)
• The input combinations of ABC determine which of the 8
inputs (D0-D7) is outputted on F
• Boolean Expression is
F = A’B’C’(D0) + A’B’C(D1) + A’BC’(D2) + A’BC(D3) +
AB’C’(D4) + AB’C(D5) + ABC’(D6) + ABC(D7)



Multiplexor - Sizes

UCI ICS 51 – Introduction to Computer Organization Copyright 2020 – Prof. Jennifer Wong-Ma
This content is protected and may not be shared uploaded or distributed.

• Multiplexors also can perform selection between m-bit inputs.
Ex: A multiplexor that selects between a pair of 32-bit inputs built as an
array of 1-bit-wide multiplexors
• A 32-bit wide 2-input multiplexor is an array of 32 1-bit-wide
multiplexors
• Only a 1-bit selector is needed to select all 32 1-bit multiplexors

Universal (Complete) Sets
o A set of gates is complete/universal if you can implement any logical
function using only the types of gates in the set
 You can use as many gates as you want to implement the function.
o Minimal complete set is a complete set with no redundant elements
o Some examples of complete sets:
 {AND, OR, NOT} – this is a complete set, but not a minimal complete set.
 {AND, NOT}
 {OR, NOT}
 {NAND}
 {NOR}
 {MUX}


Multiplexor - Universal Gate

Aside – Creating Universal Set
o Ex: NAND is universal by building gates that form a universal set.
 It is sufficient to build a NOT gate and either an OR or an AND gate.


o Ex: NOR is universal by building gates that form a universal set.
 It is sufficient to build a NOT gate and either an OR or an AND gate.




UCI ICS 51 – Introduction to Computer Organization Copyright 2020 – Prof. Jennifer Wong-Ma
This content is protected and may not be shared uploaded or distributed.

Implementing Gate Networks with Multiplexors
• Since multiplexors are a minimal complete set {MUX}, they can be used to implement any Boolean
expression/function.
• To do so, a single or set of the input variables are chosen as the selectors for the multiplexors. The remaining
input variables (and also 0 and 1) are placed on the input options of the mux to be chosen between.
o In terms of Boolean algebra, this means factoring out all combinations of the selector input variables
from all terms in the Boolean expression.
o Note: Any term which does not have the selector variables, must be placed on all inputs. Why?
Because the selector variables are “hidden” (or multiplied by 1, ie (x+x’)) for the particular selector
variable

• Ex: Implement the function F = abc’ + a’bc’ + a’b’c’ + bc using 2-input muxes

Step 1: Select a single input variable as the selector (2-input muxes) and factor the variable out of all terms.
F = a(bc’ + bc) + a’(bc’ + b’c’ + bc)
Note: term bc must appear in both factorings. Why? Because term bc is really bc(a + a’)
Each of the factored sub-expressions (expressions in parentheses) is then the input to the multiplexor for the
selector value
• (bc’ + bc) is placed on 1 input of the multiplexor
• (bc’ + b’c’ + bc) is placed on 1 input of the multiplexor

Step 2: Simplify each of the sub-expressions using the Boolean Identities, if possible. If the sub-expression is
a single literal, 1, or 0, no further gates are needed. Otherwise, repeat the process to implement the sub-
expression with additional muxes.
• bc’ + bc = b(c’ + c) = b
• bc’ + b’c’ + bc = c’(b + b’) + bc = c’ + bc = c’ + b

Note: If complemented forms of variables are not given, then NOT gates must be built using the MUXes to
invert the uncomplemented variable.
a
b
c’ + b
MUX
0
1
S
MUX
0
1
S
c
1
b F

UCI ICS 51 – Introduction to Computer Organization Copyright 2020 – Prof. Jennifer Wong-Ma
This content is protected and may not be shared uploaded or distributed.

• Selecting different variables for use as the selector(s) will result in different gate networks, and use a
different number of mux gates.
• By selecting a variable which appears in the most terms and which appear in as close to equal number of
complemented and uncomplemented forms, the resultant gate network will be balanced (shorter critical
path for the overall circuit)


Multiplexor - 2-input Example
• Ex: Implement the function F = abc’ + a’bc’ + a’b’c’ + bc using 4-input MUXes
Step 1: Select two variables as the selector (4-input MUX) and factor the variable out of all terms. Both a and
b appear in all terms and in almost 50% complemented and uncomplemented.
F = abc’ + a’bc’ + a’b’c’ + bc
Remember bc has (a+a’) hidden. Therefore, c must be included in both ab and a’b terms
F = ab (c’+c) + a’b(c’+c) + ab’ (0) + a’b’(c’)
Note: no terms contain ab’ therefore the input to this combination s 0
F = ab (1) + a’b(1) + ab’ (0) + a’b’(c’)

All sub expressions are either constant values or a single variable, therefore
further multiplexor gates are not needed. The gate network is:


Multiplexor - 4-input Example


Multiplexor - 8-input Example


Multiplexor - More Examples


Multiplexor - Summary

Decoder
• A decoder is another unit which has n input bits and 2n output bits. The unit outputs a single 1 on the output
bit corresponding to the value of the input combination
MUX
0
1
S1S0
2
3
a b
0
c’
1
1
F
UCI ICS 51 – Introduction to Computer Organization Copyright 2020 – Prof. Jennifer Wong-Ma
This content is protected and may not be shared uploaded or distributed.

o Ex: if input is 3-bits with binary value of {0,1,1} then there are 8 output lines with binary value of
{0,0,0,1,0,0,0,0}.
• A decoder translates the minterm to its binary value.


Decoder

Ex: 2-to-4 single bit decoder implementation



• A multiplexor is built from a decoder plus extra gates.
• Ex: 4 input multiplexor
4-input
MUX
S1 S2
A
B
C
D
0
1
2
3


































































































































































































学霸联盟