Introduction: Half adder, Full adder,
Arithmetic Micro-Operations: Binary Adder
Binary Subtractor, MUX, DMUX, Encoder,
Decoder.
Introduction to Flip Flop: One bit Memory,
SR, JK, D, T (Truth table) Registers and shift
registers.
Half-Adder
Carry = A AND
Sum = A XOR B
B
2
Full-Adder
3
4-bit Adder Implementation
4
Binary Subtractor
Remember
You need to take 2’s complement to represent negative
numbers
A-B
Take 2’s complement of B and add it to A
First take 1’s complement and add 1
5
4-Bit Adder and Subtractor
6
Binary Multiplier
7
Comparators
Compare two input words
Returns 1 if A=B,
0 otherwise
8
From course book
9
Decoder
n by 2^n decoder
Converts information from n input lines into 2^n output
lines
2x4 Decoder
3x8 Decoder
10
2x4 Decoder
11
Internal Structure of 2x4 Decoder
12
Another View
13
From
course
book
14
Example
15
4x16 Decoder
From course book
16
Full Adder with Decoder
Si Ai Bi Ci
Ci 1 Ai Bi ' Ci Ai ' Bi Ci Ai Bi
17
Multiplexers
You can select information from one of many input
lines and assign it to one output line
You have input lines, control lines, and one output
line
It is called MUX
18
2x1 Multiplexer
19
4x1 Multiplexer
20
Boolean Function Implementation
How do you implement it with 8x1 MUX?
21
Example
22
Three-State Buffer
23
2x1 MUX with Three-State Buffer
24
Shifters
8-input, 8-output shifter
C=1 => right shift, C=0 => left shift
25
Study Problem
Course Book Chapter – 4 Problems
4 – 31
Construct a 16x1 multiplexer with two 8x1 and one 2x1
multiplexer. Use block diagrams
26
Study Problem
Course Book Chapter – 4 Problems
4 – 34
An 8x1 multiplexe r has inputs A, B, and C connected to
the selection inputs S2 , S1 , and S0 respective ly.
The data inputs
I1 I 2 I 7 0;
I 3 I 5 1;
I 0 I 4 D;
I 6 D '
Determine the Boolean function t hat the multiplexe r implements
Study Problems
Course Book Chapter – 4 Problems
4 – 1
4 – 4
4 – 6
4 – 11
4 – 20
4 – 21
4 – 25
4 – 32
4 – 33
4 – 35
28
Questions
29
Switching-network logic blocks
Multiplexer (MUX)
Routes one of many inputs to a single output
Also called a selector
Demultiplexer (DEMUX)
Routes a single input to one of many outputs
Also called a decoder
multiplexer demultiplexer
We construct these
devices from:
• logic gates
• networks of tran-
sistor switches
control control
The “WHY” slide
Multiplexers/Demultiplexers
If you had the ability to select which input to operate, the
same part of a circuit can be used multiple times. So if you
have a lot of inputs and all of them are supposed to go
through same complex logic functions, you can save a lot of
space on your circuit board by using a multiplexer.
Then you will also need a demultiplexer to decode the
output coming out in serial into separate output ports.
“WHY”: Sharing complex logic
functions
Share an adder: Select inputs; route sum
A0 A1 B0 B1
Sa MUX MUX Sb multiple inputs
A B
single adder
Sum
Ss DEMUX multiple output destinations
Z0 Z1
Multiplexers
Basic concept
2n data inputs; n control inputs ("selects"); 1 output
Connects one of 2n inputs to the output
“Selects” decide which input connects to output
Two alternative truth-tables: Functional and Logical
Example: A 2:1 MuxFunctional truth tableLogical truth table
Z = SIn1 + S'Ino S Z In1 In0 S Z
0 In0 0 0 0 0
I0 1 In1 0 0 1 0
0 1 0 1
Z 0 1 1 0
S 1 0 0 0
I1 1 0 1 1
1 1 0 1
1 1 1 1
Multiplexers (con't)
2:1 mux: Z = S'In0 + SIn1
4:1 mux: Z = S0'S1'In0 + S0'S1In1 + S0S1'In2 +
S0S1In3
8:1 mux: Z = S0'S1'S2'In0 + S0'S1S2In1 + ...
I0 2:1 I0 I0
I1 mux Z I1 4:1 I1
I2 mux Z I2
I3 I3 8:1
S0 I4 Z
mux
I5
S0 S1 I6
I7
S0 S1 S2
Logic-gate implementation of
multiplexers
2:1 4:1 mux
mux
I0 I0
Z
S
I1
I1
Z
I2
I3
Z
S0 S1
Cascading multiplexers
Can form large multiplexers from smaller ones
Many implementation options
8:1 mux 8:1 mux
I0 I0 2:1
I1 4:1 I1 mux
I2 mux
I3 I2 2:1
2:1 Z I3
mux mux 4:1
I4 mux Z
I5 4:1 I4 2:1
I6 mux I5 mux
I7
I6 2:1
I7 mux
S0 S1 S2
S0 S1 S2
Multiplexers as general-purpose logic
A 2n:1 mux can implement any function of n
variables
A lookup table
A 2n – 1:1 mux also can implement any function of n
variables
Example: F(A,B,C) = m0 + m2 + m6 + m7
= A'B'C' + A'BC' + ABC' + ABC
A B C F 1= A'B'(C')
0 + A'B(C') + AB(0) +
0 0 0 1 C' 0 1
AB(1)
0 0 1 0 1 2 C' 0
0 1 0 1 C' 0 3 F C' 1 F
0 1 1 0 8:1 MUX
0 4 0 2 4:1 MUX
1 0 0 0 0 0 5 1 3
1 0 1 0 1 6 S1 S0
1 1 0 1 1 1 7
1 1 1 1 S2 S1 S0 A B
A B C
Multiplexers as general-purpose logic
Implementing a 2n-1:1 mux as a function of n
variables
(n-1) mux control variables S0 – Sn–1
One data variable Sn
Four possible values for each data input: 0, 1, Sn, Sn'
Example: F(A,B,C,D) implemented using an 8:1 mux
AB A
CD 00 01 11 10 1 0
00 1 0 1 1
Choose A,B,C as D 1
control variables 0 2
1 3 8:1 F
01 1 0 0 0
D Choose D as a D' 4 MUX
D 5
11 1 1 0 1 data variable 6
C D'
D' 7
10 0 1 1 0 S2 S1 S0
B A B C
Demultiplexers (DEMUX)
Basic concept
Single data input; n control inputs (“selects”); 2n
outputs
Single input connects to one of 2n outputs
“Selects” decide which output is connected to the
input
When used as a decoder, the input is called an
1:2 Decoder: 2:4 Decoder: 3:8 Decoder:
Out0 = “enable”
G S' (G)
Out0 = G S1' S0' Out0 = G S2' S1' S0'
Out1 = G S Out1 = G S1' S0 Out1 = G S2' S1' S0
Out2 = G S1 S0' Out2 = G S2' S1 S0'
Out3 = G S1 S0 Out3 = G S2' S1 S0
Out4 = G S2 S1' S0'
Out5 = G S2 S1' S0
Out6 = G S2 S1 S0'
Out7 = G S2 S1 S0
Logic-gate implementation of
demultiplexers
1:2 demux 2:4 demux
G
Out0
Out0 Out1
G
S Out2
Out1
Out3
S1 S0
Demultiplexers as general-purpose
logic
A n:2n demux can implement any function of n
variables
DEMUX as logic building block
Use variables as select inputs
Tie enable input to logic 1
Sum the appropriate minterms (extra OR gate)
0 A'B'C' demultiplexer “decodes”
1 A'B'C appropriate minterms
2 A'BC'
3:8 3 A'BC from the control signals
1
4 AB'C'
Demux 5 AB'C
6 ABC'
7 ABC
S2 S1 S0
A B C
Demultiplexers as general-purpose
logic
Example
0 A'B'C'D'
F1 = A'BC'D + A'B'CD + 1 A'B'C'D
ABCD 2 A'B'CD' F1
3 A'B'CD
F2 = ABC'D' + ABC 4 A'BC'D'
5 A'BC'D
F3 = (A'+B'+C'+D') 6 A'BCD'
7 A'BCD
Enable = 1 4:16 8 AB'C'D'
Demux 9 AB'C'D F2
10 AB'CD'
11 AB'CD
12 ABC'D'
13 ABC'D
14 ABCD'
15 ABCD F3
A B CD
Cascading demultiplexers
5:32 demux
0 A'B'C'D'E' 0
1 1
2 2 A'BC'DE'
3:8 3 3:8 3
Demux 4 Demux 4
5 5
6 6
7 7
S2 S1 S0 S2 S1 S0
0
2:4 1
F Demux 2
S1 S0 3
0 0 AB'C'D'E'
1 1
A B 2 2
3:8 3 3:8 3
Demux 4 Demux 4
5 5
6 6
7 ABCDE 7 AB'CDE
S2 S1 S0 S2 S1 S0
C D E C D E
Programmable logic (PLAs & PALs )
Concept: Large array of uncommitted AND/OR
gates
Actually NAND/NOR gates
You program the array by making or breaking
connections
• • • block for sum-of-products logic
Programmable
inputs
AND OR
array product array
terms
outputs
• • •
Decoders
45
Decoders
A decoder has
N inputs
2N outputs
A decoder selects one of 2N outputs by
decoding the binary value on the N inputs.
The decoder generates all of the minterms of
the N input variables.
Exactly one output will be active for each
combination of the inputs.
What does “active” mean?
46
Decoders
W = A'.B'
Out0 W
B I0 Out1 X X = A.B'
A I1 Out2 Y Y = A'.B
Out3 Z
msb Z = A.B
Active-high outputs
A B W X Y Z
0 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 0 0 1
47
Decoders
W = (A'.B')'
Out0 W
B I0 Out1 X X = (A.B')'
A I1 Out2 Y Y = (A'.B)'
Out3 Z
msb Z = (A.B)'
Active-low outputs
A B W X Y Z
0 0 0 1 1 1
0 1 1 0 1 1
1 0 1 1 0 1
1 1 1 1 1 0
48
Decoders
msb
49
Decoder with Enable
Out0 W
B I0
high-level Out1 X
enable A I1
Out2 Y
Out3 Z
Enable En
En A B W X Y Z
1 0 0 1 0 0 0
1 0 1 0 1 0 0
enabled
1 1 0 0 0 1 0
1 1 1 0 0 0 1
disabled 0 x x 0 0 0 0
50
Decoder with Enable
Out0 W
B I0
low-level Out1 X
enable A I1
Out2 Y
Out3 Z
Enable En
En A B W X Y Z
0 0 0 1 0 0 0
0 0 1 0 1 0 0
enabled
0 1 0 0 0 1 0
0 1 1 0 0 0 1
disabled 1 x x 0 0 0 0
51
Decoders
Exercise:
Design a 4-to-16 decoder using
2-to-4 decoders only.
52
Encoders
53
Encoders
An encoder has
2N inputs
N outputs
An encoder outputs the binary value of the selected
(or active) input.
An encoder performs the inverse operation of a
decoder.
Issues
What if more than one input is active?
What if no inputs are active?
54
Encoders
D I0
C I1 Out0 Z
Out1 Y
B I2
A I3
A B C D Y Z
0 0 0 1 0 0
0 0 1 0 0 1
0 1 0 0 1 0
1 0 0 0 1 1
55
Priority Encoders
If more than one input is active, the higher-order
input has priority over the lower-order input.
The higher value is encoded on the output
A valid indicator, d, is included to indicate whether or
not the output is valid.
Output is invalid when no inputs are active
d=0
Output is valid when at least one input is active
d=1
Why is the valid indicator needed?
56
Priority Encoders
msb
Valid bit
57
Designing logic circuits using multiplexers
58
Using an n-input Multiplexer
Use an n-input multiplexer to realize a logic circuit for
a function with n minterms.
m = 2n, where m = # of variables in the function
Each minterm of the function can be mapped to an
input of the multiplexer.
For each row in the truth table, for the function,
where the output is 1, set the corresponding input of
the multiplexer to 1.
That is, for each minterm in the minterm expansion of the
function, set the corresponding input of the multiplexer to 1.
Set the remaining inputs of the multiplexer to 0.
59
Using an n-input Mux
Example:
Using an 8-to-1 multiplexer, design a logic circuit
to realize the following Boolean function
F(A,B,C) = Sm(2, 3, 5, 6, 7)
60
Using an n-input Mux
Example:
Using an 8-to-1 multiplexer, design a logic circuit
to realize the following Boolean function
F(A,B,C) = Sm(1, 2, 4)
61
Using an (n / 2)-input Multiplexer
Use an (n / 2)-input multiplexer to realize a logic
circuit for a function with n minterms.
m = 2n, where m = # of variables in the function
Group the rows of the truth table, for the function, into
(n / 2) pairs of rows.
Each pair of rows represents a product term of (m – 1)
variables.
Each pair of rows can be mapped to a multiplexer input.
Determine the logical function of each pair of rows in
terms of the mth variable.
If the mth variable, for example, is x, then the possible
values are x, x', 0, and 1. 62
Using an (n / 2)-input Mux
Example: F(x,y,z) = Sm(1, 2, 6, 7)
63
Using an (n / 2)-input Mux
Example: F(A,B,C,D) = Sm(1,3,4,11,12–15)
64
Using an (n / 4)-input Mux
The design of a logic circuit using an (n / 2)-input
multiplexer can be easily extended to the use of
an (n / 4)-input multiplexer.
65
Designing logic circuits using decoders
66
Using an n-output Decoder
Use an n-output decoder to realize a logic circuit for a
function with n minterms.
Each minterm of the function can be mapped to an
output of the decoder.
For each row in the truth table, for the function, where
the output is 1, sum (or “OR”) the corresponding
outputs of the decoder.
That is, for each minterm in the minterm expansion of the
function, OR the corresponding outputs of the decoder.
Leave remaining outputs of the decoder unconnected.
67
Using an n-output Decoder
Example:
Using a 3-to-8 decoder, design a logic circuit to
realize the following Boolean function
F(A,B,C) = Sm(2, 3, 5, 6, 7)
68
Using an n-output Decoder
Example:
Using two 2-to-4 decoders, design a logic circuit
to realize the following Boolean function
F(A,B,C) = Sm(0, 1, 4, 6, 7)
69
Questions?
70
All two-level logic functions are
available
You "program" the wire connections
A 3-input, 5-term,
4-function PLA
