Digital Logic Design

 Basics
 Combinational Circuits
 Sequential Circuits

Pu-Jen Cheng

Adapted from the slides prepared by S. Dandamudi for the book,

Fundamentals of Computer Organization and Design.
 Introduction to Digital Logic Basics
 Hardware consists of a few simple building blocks
 These are called logic gates
 AND, OR, NOT, …

 NAND, NOR, XOR, …

 Logic gates are built using transistors

 NOT gate can be implemented by a single transistor
 AND gate requires 3 transistors
 Transistors are the fundamental devices
 Pentium consists of 3 million transistors
 Compaq Alpha consists of 9 million transistors
 Now we can build chips with more than 100 million
transistors
 Basic Concepts
 Simple gates
 AND
 OR
 NOT
 Functionality can be
expressed by a truth table
 A truth table lists output for
each possible input
combination
 Precedence
 NOT > AND > OR
 F=AB+AB
= (A (B)) + ((A) B)
 Basic Concepts (cont.)
 Additional useful gates
 NAND
 NOR
 XOR
 NAND = AND + NOT
 NOR = OR + NOT
 XOR implements
exclusive-OR function
 NAND and NOR gates
require only 2 transistors
 AND and OR need 3
transistors!
 Basic Concepts (cont.)
 Number of functions
 With N logical variables, we can define
22N functions
 Some of them are useful
 AND, NAND, NOR, XOR, …

 Some are not useful:

 Output is always 1

 Output is always 0

 “Number of functions” definition is useful in proving

completeness property
 Basic Concepts (cont.)
 Complete sets
 A set of gates is complete
 If we can implement any logical function using only

the type of gates in the set

 You can uses as many gates as you want
 Some example complete sets
 {AND, OR, NOT} Not a minimal complete set
 {AND, NOT}

 {OR, NOT}

 {NAND}

 {NOR}

 Minimal complete set

 A complete set with no redundant elements.
 Basic Concepts (cont.)
 Proving NAND gate is universal
 Basic Concepts (cont.)
 Proving NOR gate is universal
Logic Chips (cont.)
 Logic Chips (cont.)
 Integration levels
 SSI (small scale integration)
 Introduced in late 1960s

 1-10 gates (previous examples)

 MSI (medium scale integration)

 Introduced in late 1960s

 10-100 gates

 LSI (large scale integration)

 Introduced in early 1970s

 100-10,000 gates

 VLSI (very large scale integration)

 Introduced in late 1970s

 More than 10,000 gates

 Logic Functions
 Logical functions can be expressed in several
ways:
 Truth table
 Logical expressions
 Graphical form
 Example:
 Majority function
 Output is one whenever majority of inputs is 1

 We use 3-input majority function

 Logic Functions (cont.)
3-input majority function  Logical expression form
A B C F F=AB+BC+AC

0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
 Logical Equivalence
 All three circuits implement F = A B function
 Logical Equivalence (cont.)
 Proving logical equivalence of two circuits
 Derive the logical expression for the output of each
circuit
 Show that these two expressions are equivalent
 Two ways:

 You can use the truth table method

 For every combination of inputs, if both expressions

yield the same output, they are equivalent

 Good for logical expressions with small number of

variables
 You can also use algebraic manipulation
 Need Boolean identities
 Logical Equivalence (cont.)
 Derivation of logical expression from a circuit
 Trace from the input to output
 Write down intermediate logical expressions along the path
 Logical Equivalence (cont.)
 Proving logical equivalence: Truth table method

A B F1 = A B F3 = (A + B) (A + B) (A + B)
0 0 0 0
0 1 0 0
1 0 0 0
1 1 1 1
Boolean Algebra
Boolean Algebra (cont.)
 Boolean Algebra (cont.)
 Proving logical equivalence: Boolean algebra
method
 To prove that two logical functions F1 and F2 are
equivalent
 Start with one function and apply Boolean laws to

derive the other function

 Needs intuition as to which laws should be applied

and when
 Practice helps
Sometimes it may be convenient to reduce both
functions to the same expression
 Example: F1= A B and F3 are equivalent
 Logic Circuit Design Process
 A simple logic design process involves
 Problem specification
 Truth table derivation
 Derivation of logical expression
 Simplification of logical expression
 Implementation
 Deriving Logical Expressions
 Derivation of logical expressions from truth tables
 sum-of-products (SOP) form
 product-of-sums (POS) form
 SOP form
 Write an AND term for each input combination that
produces a 1 output
 Write the variable if its value is 1; complement

otherwise
 OR the AND terms to get the final expression
 POS form
 Dual of the SOP form
 Deriving Logical Expressions (cont.)
 3-input majority function  SOP logical expression
A B C F  Four product terms
 Because there are 4 rows
0 0 0 0 with a 1 output
0 0 1 0
0 1 0 0
0 1 1 1 F=ABC+ABC+
1 0 0 0 ABC+ABC
1 0 1 1
1 1 0 1
1 1 1 1
 Deriving Logical Expressions (cont.)
 3-input majority function  POS logical expression
A B C F  Four sum terms
 Because there are 4 rows
0 0 0 0 with a 0 output
0 0 1 0
0 1 0 0
0 1 1 1 F = (A + B + C) (A + B + C)
1 0 0 0 (A + B + C) (A + B + C)
1 0 1 1
1 1 0 1
1 1 1 1
 Logical Expression Simplification
 Two basic methods
 Algebraic manipulation
 Use Boolean laws to simplify the expression

 Difficult to use
 Don’t know if you have the simplified form
 Karnaugh map (K-map) method
 Graphical method

 Easy to use

 Can be used to simplify logical expressions with a few

variables
 Algebraic Manipulation
 Majority function example
Added extra
ABC+ABC+ABC+ABC =
ABC+ABC+ABC+ABC+ABC+ABC

 We can now simplify this expression as

BC+AC+AB

 A difficult method to use for complex expressions

Karnaugh Map Method

Note the order

Karnaugh Map Method (cont.)
Simplification examples
Karnaugh Map Method (cont.)
First and last columns/rows are adjacent
Karnaugh Map Method (cont.)
Minimal expression depends on groupings
Karnaugh Map Method (cont.)
No redundant groupings
 Karnaugh Map Method (cont.)
 Example
 Seven-segment display
 Need to select the right LEDs to display a digit
Karnaugh Map Method (cont.)
Karnaugh Map Method (cont.)
Don’t cares simplify the expression a lot
 Implementation Using NAND Gates
 Using NAND gates
 Get an equivalent expression

AB+CD=AB+CD
 Using de Morgan’s law

AB+CD=AB.CD
 Can be generalized
 Majority function

A B + B C + AC = A B . BC . AC
Idea: NAND Gates: Sum-of-Products, NOR Gates: Product-of-Sums
 Implementation Using NAND Gates
(cont.)
 Majority function
 Introduction to Combinational Circuits

 Combinational circuits
 Output depends only on the current inputs
 Combinational circuits provide a higher level of
abstraction
 Help in reducing design complexity
 Reduce chip count
 We look at some useful combinational circuits
 Multiplexers
 Multiplexer
 2n data inputs 4-data input MUX
 n selection inputs
 a single output

 Selection input
determines the
input that should
be connected to
the output
Multiplexers (cont.)
4-data input MUX implementation
Multiplexers (cont.)

MUX implementations
Multiplexers (cont.)

Example chip: 8-to-1 MUX

 Multiplexers (cont.)

Efficient implementation: Majority function

Demultiplexers
Demultiplexer (DeMUX)
 Decoders
 Decoder selects one-out-of-N inputs
Decoders (cont.)
Logic function implementation

(Full Adder)
 Comparator
 Used to implement comparison operators (= , > , < ,  , )
 A=B: Ox = Ix (x=A<B, A=B, & A>B)
Comparator (cont.)

4-bit magnitude comparator chip

 Comparator (cont.)

Serial construction of an 8-bit comparator

 1-bit Comparator
x>y
CMP x=y
x<y
x y

x y x>y x=y x<y

 8-bit comparator

xn>yn x>y
xn=yn CMP x=y
xn<yn x<y
x y
 Adders
 Half-adder
 Adds two bits
 Produces a sum and carry

 Problem: Cannot use it to build larger inputs

 Full-adder
 Adds three 1-bit values
 Like half-adder, produces a sum and carry

 Allows building N-bit adders

 Simple technique

 Connect Cout of one adder to Cin of the next

 These are called ripple-carry adders
Adders (cont.)
Adders (cont.)

A 16-bit ripple-carry adder

 Adders (cont.)
 Ripple-carry adders can be slow
 Delay proportional to number of bits
 Carry lookahead adders
 Eliminate the delay of ripple-carry adders
 Carry-ins are generated independently
 C = A B
0 0 0
 C = A B A + A B B + A B
1 0 0 1 0 0 1 1 1
 ...
 Requires complex circuits
 Usually, a combination carry lookahead and ripp
le-carry techniques are used
 Programmable Logic Arrays
 PLAs
 Implement sum-of-product expressions
 No need to simplify the logical expressions

 Take N inputs and produce M outputs

 Each input represents a logical variable

 Each output represents a logical function output

 Internally uses
 An AND array

 Each AND gate receives 2N inputs

 N inputs and their complements

 An OR array
Programmable Logic Arrays (cont.)
A blank PLA with 2 inputs and 2 outputs
Programmable Logic Arrays (cont.)
Implementation examples
Programmable Logic Arrays (cont.)
Simplified notation
1-bit Arithmetic and Logic Unit
Preliminary ALU design

2’s complement
Required 1 is added via Cin
1-bit Arithmetic and Logic Unit
(cont.)
Final design
Arithmetic and Logic Unit (cont.)
16-bit ALU
Arithmetic and Logic Unit (cont’d)

4-bit ALU
 Introduction to Sequential Circuits
 Output depends on current as well as past inputs
 Depends on the history
 Have “memory” property
 Sequential circuit consists of
 Combinational circuit
 Feedback circuit

 Past input is encoded into a set of state variables

 Uses feedback (to feed the state variables)

 Simple feedback
 Uses flip flops
 Introduction (cont.)

Main components of a sequential circuit

Clock Signal
 Clock Signal (cont.)
 Clock serves two distinct purposes
 Synchronization point
 Start of a cycle

 End of a cycle

 Intermediate point at which the clock signal changes

levels
 Timing information
 Clock period, ON, and OFF periods

 Propagation delay
 Time required for the output to react to changes in the
inputs
Clock Signal (cont.)
 Latches
 Can remember a bit
 Level-sensitive (not edge-sensitive)

A NOR gate implementation of SR latch

 Latches (cont.)
 SR latch outputs follow inputs
 In clocked SR latch, outputs respond at specific instances
 Uses a clock signal
 Latches (cont.)
 D Latch
 Avoids the SR = 11 state
 Flip-Flops
 Edge-sensitive devices
 Changes occur either at positive or negative edges

Positive edge-triggered D flip-flop

 Flip-Flops (cont.)
 Notation
 Not strictly followed in the literature
 We follow the following notation for latches and flip-flops

Latches Flip-flops

Low level High level Positive edge Negative

edge
Flip-Flops (cont.)
 Example Sequential Circuits (cont.)

74164 shift
Register chip
Memory Design with D Flip Flops
Require separate data in and out lines