Chapter 3
Boolean Algebra
and Digital Logic
Part 2
2
• Logic Gates are composed of
transistors or similar electronic
device.
• Transistors use voltage differences
to control the flow of electricity
3.3 Logic Gates
https://commons.wikimedia.org/w/index.php?curid=2593317
A B Out
Vss Vss Vdd
Vss Vdd Vdd
Vdd Vss Vdd
Vdd Vdd Vss
3.4 Digital Components
• Standard digital
components are
combined into single
integrated circuit
packages.
• Boolean logic can be
used to implement the
desired functions.
3
4
• The circuit below implements the Boolean
function F(x,y,z) = x + y’z:
3.4 Digital Components
3.4 Digital Components
5
6
• One of the last “gates” we will look at is tri-state buffer.
• Tri-state logic is where we can turn off a signal and
have multiple outputs share the same signal line.
3.4 Digital Components
https://en.wikipedia.org/wiki/Three-state_logic
7
• A Karnaugh map, or Kmap, is a
graphical representation of a truth
table that can be used help simplify
a Boolean expression
• Kmaps use minterms from canonical
expression forms to determine
• Kmaps have a cell for each minterm.
3A Karnaugh Maps
8
• Let’s use a Kmap to
represent and then simplify
F(x,y) = x + y
• We can simplify by grouping
1s together
• There are specific rules for
grouping
3A Karnaugh Maps
F(x,y)= x+y = x’y+xy’+xy
9
• Consider the function:
• Its Kmap is given below.
3A.3 Kmap Simplification
for Three Variables
F(X,Y,Z)= X’Y’Z + X’YZ + XY’Z + XYZ
10
• Now for a more complicated Kmap. Consider the
function:
3A.3 Kmap Simplification
for Three Variables
F(X,Y,Z)=
X’Y’Z’+ X’Y’Z + X’YZ + X’YZ’+
XY’Z’ + XYZ’
11
• We have populated the Kmap shown below with
the nonzero minterms from the function
3A.3 Kmap Simplification for Four
Variables
12
• It is possible to have a choice as to how to pick
groups within a Kmap, while keeping the groups
as large as possible.
• The (different) functions that result from the
groupings below are logically equivalent.
3A.3 Kmap Simplification for Four
Variables
13
• Real circuits don’t always need to have an output
defined for every possible input.
• If a circuit is designed so that a particular set of
inputs can never happen, we call this set of inputs
a don’t care condition.
• In a Kmap, there are maked with an X
3A.6 Don’t Care Conditions
14
• The truth table of:
differs from the truth table of:
• However, the values for which they differ, are the
inputs for which we have don’t care conditions.
3A.6 Don’t Care Conditions
F(W,X,Y,Z)= W’Y’+ YZ
F(W,X,Y,Z)= W’Z + YZ
15
• Combinational logic circuits
produce one or more outputs
from a given set of inputs.
• Can be thought of as a small
building block
• One of the simplest is the
half adder
3.5 Combinational Circuits
16
• 7-Segment Displays are a common
use case for combinational circuits
3.5 Combinational Circuits
https://en.wikipedia.org/wiki/Seven-segment_display
17
• We can take two half
adders together to form
a full adder
3.5 Combinational Circuits
18
• Just as we combined half adders to make a full
adder, full adders can be connected in series.
• The carry bit “ripples” from one adder to the next;
hence, this configuration is called a ripple-carry
adder.
3.5 Combinational Circuits
19
• Decoders are another important type of
combinational circuit.
• Decoders take n inputs and have 2n outputs
• n represents a binary number which selects one of
the output lines to make a 1
3.5 Combinational Circuits
20
• A multiplexer does just the opposite of a decoder.
• It selects a single output from several inputs.
• The input chosen for output is determined by the
value of the multiplexer’s control lines.
• To be able to select among n inputs, log2n control
lines are needed.
3.5 Combinational Circuits
Questions?
• Karnaugh Maps
• Combinational Circuits
– Half and Full Adder
– n-bit Adder
– Decoder
– Multiplexer
21
22
3.6 Sequential Circuits
• Combinational logic circuits are perfect for
situations when we require the immediate
application of a Boolean function to a set of inputs.
• There are other times, however, when we need a
circuit to change its value with consideration to its
current state as well as its inputs.
• Sequential logic circuits provide this functionality
for us.
23
• As the name implies, sequential logic circuits require
a means by which events can be sequenced.
• State changes are controlled by clocks.
– A “clock” is a special circuit that sends electrical pulses
through a circuit.
• Clocks produce electrical waveforms such as the
one shown below.
3.6 Sequential Circuits
24
• State changes occur in sequential circuits under
four conditions
3.6 Sequential Circuits
25
• To retain their state values, sequential circuits
rely on feedback.
• Feedback in digital circuits occurs when an output
is looped back to the input.
3.6 Sequential Circuits
26
• You can see how feedback works by examining
the most basic sequential logic components, the
SR flip-flop.
• The internals of an SR flip-flop are shown below,
along with its block diagram.
3.6 Sequential Circuits
27
• If we can be sure that the inputs to an SR flip-flop
will never both be 1, we will never have an
unstable circuit. This may not always be the case.
• The SR flip-flop can be modified to provide a
stable state when both inputs are 1.
• This modified flip-flop is
called a JK flip-flop,
shown at the right.
3.6 Sequential Circuits
28
• At the right, we see
how an SR flip-flop
can be modified to
create a JK flip-flop.
3.6 Sequential Circuits
29
• Another modification of the SR flip-flop is the D
flip-flop, shown below with its characteristic table.
• You will notice that the output of the flip-flop
remains the same during subsequent clock
pulses. The output changes only when the value
of D changes.
3.6 Sequential Circuits
30
• The D flip-flop is the fundamental circuit of
computer memory.
– D flip-flops are usually illustrated using the block
diagram shown below.
• The characteristic table for the D flip-flop is
shown at the right.
3.6 Sequential Circuits
31
• The behavior of sequential circuits can be
expressed using characteristic tables or finite state
machines (FSMs).
• Finite state machines can be thought of as an
abstraction over conbinational logic and sequential
circuits in the same way that boolean algebra
abstracts logic gates.
• The D flip-flop can be thought of as a simple state
machine with two states:
– 1 is stored
– 0 is stored
3.6 Sequential Circuits
32
• Looking at the components we have now:
– N-bit Full Adder
– D flip-flop
– Decoder
– Multiplexer (MUX)
• We have enough to start forming some of the tools
in our computer
– Arithmetic Logic Unit (ALU)
– Registers
– Control Logic
– Memory
3.6 Sequential Circuits
33
• Computers are implementations of Boolean logic.
• Logic gates are small circuits that implement
Boolean operators.
• The “universal gates” are NAND and NOR.
• Combinational circuits operate immediately when
inputs change.
• Sequential circuits require clocks to control their
changes of state.
Chapter 3 Conclusion