+
Chapter 2
Digital Logic
+
What is digital computer
~ represent digital digit
Why binary? Instead decimal or other number system
+
Integrated circuit <- transistor
Transistor operates on Boolean algebra
Switching between on/off to represent 0 and 1
Combined to form logic gates
+
Boolean Algebra
Mathematical discipline used to design and analyze the behavior of the
digital circuitry in digital computers and other digital systems
Named after George Boole
English mathematician
Proposed basic principles of the algebra in 1854
Claude Shannon suggested Boolean algebra could be used to solve
problems in relay-switching circuit design
Is a convenient tool:
Analysis
It is an economical way of describing the function of digital circuitry
Design
Given a desired function, Boolean algebra can be applied to develop a
simplified implementation of that function
+
Boolean Variables and Operations
Makes use of variables and operations
Are logical
A variable may take on the value 1 (TRUE) or 0 (FALSE)
Basic logical operations are AND, OR, and NOT
AND
Yields true (binary value 1) if and only if both of its operands are true
In the absence of parentheses the AND operation takes precedence over the OR operation
When no ambiguity will occur the AND operation is represented by simple concatenation
instead of the dot operator
OR
Yields true if either or both of its operands are true
NOT
Inverts the value of its operand
Table 11.1
Boolean Operators
(a) Boolean Operators of Two Input Variables
(b) Boolean Operators Extended to More than Two Inputs (A, B, . . .)
Table 11.2
Basic Identities of Boolean Algebra
Table 11.2 Basic Identities of Boolean Algebra
+
Basic Logic Gates
+
Uses of
NAND Gates
+
Uses of
NOR Gates
An interconnected set of gates
Combinational Circuit whose output at any time is a
function only of the input at that
time
The appearance of the input is
followed almost immediately by
the appearance of the output,
with only gate delays
Consists of n binary inputs and
m binary outputs
Can be defined in three ways:
• Truth table
• For each of the 2n possible
combinations of input signals, the
binary value of each of the m
output signals is listed
• Graphical symbols
• The interconnected layout of gates
is depicted
• Boolean equations
• Each output signal is expressed as
a Boolean function of its input
signals
+
Boolean Function of Three Variables
Table 11.3 A Boolean Function of Three Variables
+
Sum-of-Products
Implementation of Table
11.3
+
Product-of-Sums
Implementation
of Table 11.3
+
Algebraic Simplification
Involves the application of the identities of Table 11.2 to reduce the Boolean
expression to one with fewer elements
+
Karnaugh Map
A convenient way of representing a Boolean function of a small number (up to
four) of variables
Example
Karnaugh
Maps
+
Overlapping
Groups
+
+
Table 11.4
Truth Table for the One-Digit Packed Decimal Incrementer
Table 11.4 Truth Table for the One-Digit Packed Decimal Incrementer
Figure
11.10
+
Table 11.5
First Stage of
Quine-McCluskey Method
Table 11.5 First Stage of Quine-McCluskey Method
Table 11.6
Last Stage of
Quine-McCluskey Method
Table 11.6 Last Stage of Quine-McCluskey Method
+
NAND and NOR
Implementations
+
Multiplexers
- connect multiple inputs to a
single output
+
4-to-1
Multiplexer Truth Table
Table 11.7 4-to-1 Multiplexer Truth Table
+
Multiplexer Input to Program Counter
+
Decoders
- combinational circuits with a
number of output lines, only one
of which is asserted at any time
Address Decoding
Implementation of a Demultiplexer
Using a Decoder
+
Read-Only Memory (ROM)
Memory that is implemented with combinational circuits
Combinational circuits are often referred to as “memoryless” circuits
because their output depends only on their current input and no history of
prior inputs is retained
Memory unit that performs only the read operation
Binary information stored in a ROM is permanent and is created during the
fabrication process
A given input to the ROM (address lines) always produces the same output
(data lines)
Because the outputs are a function only of the present inputs, ROM is a
combinational circuit
Table
11.8
+
Truth Table for a ROM
Binary Addition Truth Tables
Table 11.9 Binary Addition Truth Tables
4-Bit Adder
+
Implementation of an
Adder
Construction of a 32-Bit Adder Using
8-Bit Adders
Sequential Circuit
Current output depends not
only on the current input,
but also on the past history
of inputs
Sequential
Circuit
Makes use of
combinational circuits
+
Flip-Flops
Simplest form of sequential circuit
There are a variety of flip-flops, all of which share two properties:
1. The flip-flop is a bistable device. It exists in one of two states
and, in the absence of input, remains in that state. Thus, the flip-
flop can function as a 1-bit memory.
2. The flip-flop has two outputs, which are always the complements
of each other.
+
The S-R Latch
+
NOR S-R Latch Timing Diagram
Table 11.10 The S-R Latch
Clocked S-R Flip-Flop
D Flip-Flop
J-K Flip Flop
+
Basic Flip-Flops
Parallel Register
5-Bit Shift Register
+
Counter
A register whose value is easily incremented by 1 modulo the
capacity of the register
After the maximum value is achieved the next increment sets the
counter value to 0
An example of a counter in the CPU is the program counter
Can be designated as:
Asynchronous
Relatively slow because the output of one flip-flop triggers a change in
the status of the next flip-flop
Synchronous
All of the flip-flops change state at the same time
Because it is faster it is the kind used in CPUs
Ripple Counter
+
Design of a
Synchronous Counter
Table 11.11
Programmable
Logic
Devices (PLD)
Terminology
+
Programmable Logic
Array (PLA)
+
Structure of a
Field-Programmable
Gate Array
(FPGA)
Simple FPGA Logic Block
+ Summary Digital
Logic
Chapter 11
Boolean Algebra Sequential Circuits
Gates Flip-Flops
Combinational Circuits Registers
Implementation of Boolean Counters
Functions
Programmable Logic Devices
Multiplexers
Programmable Logic Array
Decoders
Field-Programmable Gate Array
Read-Only-Memory
Adders