Professor: Dinh Duc Anh Vu, PhD.

Office: A2.713
Email: ddavu@hcmiu.edu.vn

 Code: IT67IU
 Credit: 3
 Prerequisite: None
 Co-requisite:
Digital Logic Design Lab
 Textbook: Digital Systems: Principles and
Applications, 10th edition, Pearson Edu. Intl.,
2007, by Ronald J. Tocci and Neal S. Widmer,
Gregory L. Moss
 Class and recitation notes

Introduction 2
  Class Time:
◦ Wednesdays
 Office Hours:
◦ by appointment
◦ office: A2.713
◦ Email / Conversation (Teams)

Introduction 3

 Introduction to digital logic

◦ Digital system fundamentals; number system;
fundamentals of digital circuits and computer
systems stressing general techniques for the
analysis and synthesis of combinational and
sequential logic systems.
 What will you learn?
◦ To learn simple digital circuits in preparation for
computer engineering and science
◦ Understanding and designing digital logic circuits
with respect to different quality metrics such as
functionality, timing, power and area.

Introduction 4
  Chapter 1 (this chapter): Introduction
 Chapter 2: Number Systems
 Chapter 3: Logic Circuits
 Chapter 4: Boolean algebra & Combinational
logic circuits
 Chapter 5: Flip-Flop and related devices
 Chapter 6: Counters and registers
 Chapter 7: MSI logic circuits

Introduction 5

 Number representation:
binary, decimal, hexadecimal
…
 Logic gates: AND, OR, NOT,
NAND, NOR …
 Flip-flop, latch, register …
 Combinational circuit: adder,
comparator, multiplexer …
 Sequential circuit:
asynchronous/synchronous
counters, shifters …

Introduction 6
  Grade distribution:
◦ Homework, quizzes, hourly exams: 30%
◦ Midterm exam: 30%
◦ Final exam: 40%
 Exams: open-book
 NO MAKE UP EXAM WILL BE GIVEN!!!

Introduction 7

 You will have at least 4 sets of homework.

 The point is to give you practical experience
with what you’re learning.
 No problem if you want to work together.
 You need to write down your own solution.
 You need to credit anybody you work with!

Introduction 9
  Homework assignments will be posted. All
homework questions will be graded for
correctness. Questions will come both from the
textbook as well as created by the instructor.
 Solutions for homework assignments will be
posted after the expiration of the grade period.
 Quiz solutions will be discussed in class and will
only be posted online if they cannot be
discussed before an exam.
 Exam solutions will only be discussed in class.

Introduction 10

 Copying (program or assignment) files from

another person or source, including retyping
their files, changing variable names, copying
code without explicit citation from previously
published works (except the textbook), etc.
 Copying on quizzes or exams.
 Allowing someone else to copy your code or
written assignment, either in draft or final
form.
 Inappropriately obtaining course information
from instructors and TAs.

Introduction 11
  As research on learning shows, unexpected noises
and movement automatically divert and capture
people's attention, which means you are affecting
everyone’s learning experience if your cell phone,
pager, laptop, etc. makes noise or is visually
distracting during class.
 For this reason,
- You must turn off your mobile devices during
class.
 - You can take notes on your laptop, but you must
turn the sound off so that you do not disrupt other
students' learning. If you are doing anything other
than taking notes on your laptop, please sit in the
back row so that other students are not distracted
by your screen.

Introduction 12

 Classroom activities may be recorded by a

student for the personal, educational use of
that student or for all students presently
enrolled in the class only, and may not be
further copied, distributed, published or
otherwise used for any other purposes.
 All students are advised that classroom
activities may be taped by students for this
purpose.

Introduction 13
  All assignments are expected to be turned in during class
on the due date unless otherwise noted.
 If an assignment is turned in after that time, I will accept it
and assign a 25% penalty for each 24-hour period it is
late.
◦ Examples: A turns his assignment in at 8 AM the day after the
due date. He loses 25%. B turns his in at 3 PM the next day. He
loses 50%.
◦ This will be calculated by simply multiplying your earned score by
the appropriate penalty. Consider that A earned 30/40 points on
his assignment. After his 25% late penalty, he would receive a
final score of 23/40 (rounded up).
 Weekend days count as days too. An assignment due on
Friday that is turned in on Monday is subject to a 50%
penalty.
 If the solutions to an assignment are posted prior to the
normal expiration of this period (to facilitate studying for
an exam, for example), assignments will no longer be
accepted.
Introduction 14

 I can expect you:

◦ To come to class on time.
◦ To be attentive and engaged in class.
◦ To refrain from using laptops, cell phones and
other electronic devices during class.
◦ To spend an adequate amount of time on the
assignments, making an effort to solve and
understand each problem.
◦ To engage with both the abstract and
computational sides of the material.
◦ To seek help when appropriate

Introduction 15
2000
42 million transistors
1.5 GHz

Introduction 16

 the co-founder and chairman emeritus of

Intel Corporation
 Author of Moore's law: the
number of transistors in a dense integrated
circuit (IC) doubles about every two years
Introduction 20
 Twice the number of transistors,
approximately every two years
16

COMPONENTS PER INTEGRATED FUNCTION

15
14
13
12
LOG2 OF THE NUMBER OF

11
10
9
8
7
6
5
4
3
2
1
0
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
Electronics, April 19, 1965.

Introduction 21

Introduction 22
  Analog Representation
◦ Analog signals can take any value across a continuous range of current,
voltage, etc.
◦ One quantity is represented by another which is proportional to the first
◦ Examples: automobile speedometer, thermostat, …
◦ Analog quantities have an important characteristic: they can vary over a
continuous ranges of values
 Digital Representation
◦ Quantities is represented not by proportional quantities but by symbols
called digits.
◦ Restrict themselves to two discrete values of 0 and 1, low and high, false
and true
◦ Examples: digital watch, …
◦ Changes in discrete steps

 Analog: continuous
 Digital: discrete (step by step)

Introduction 24

 Which of the following involve analog quantities

and which involve digital quantities ?
◦ Ten-position switch
◦ Current meter
◦ Temperature
◦ Sand grains on the beach
◦ Radio volume control
 Concisely describe the major difference between
analog and digital quantities
◦ Analog quantities can take on any value over
continuous range; digital quantities can take on only
discrete values

Introduction 25
  Digital Systems
◦ a combination of devices designed to manipulate
logical information or physical quantities that are
represented in digital forms
◦ Examples: computer processor, robot, …

 Analog Systems
◦ Contains devices that manipulate physical
quantities that are represented in analog form
◦ Examples: TV, VCR, …

Introduction 26

 Advantages of Digital Techniques

◦ easier to design and store
◦ accuracy and precision are greater
◦ operation can be programmed
◦ less effective by noise
◦ more can be fabricated on IC chips
 Limitation of Digital Techniques
◦ The real world is mainly ANALOG!!
◦ To take advantages of digital techniques
1. convert analog inputs to digital
2. process the digital
3. convert the digital outputs to analog

Introduction 27
 Temperature (Analog) (Digital)
Measuring Analog-to-Digital Digital
(analog)
device converter processing

(Digital)

(Analog) Adjusts
Digital-to-Analog
Controller temperature
converter

 Block diagram of a temperature control system

that requires analog/digital conversions in
order to allow the use of digital processing
techniques
Introduction 28

Volts Volts

5V
1 1
Bit 1 4V

2V
Not used
0.8 V
Bit 0 0 0
0V 0V t
t0 t1 t2 t3

Typical voltage Typical digital signal timing diagram

assignments in digital
systems

Introduction 29
  Digital Circuits = Logic Circuits
 Digital IC
◦ TTL, CMOS, NMOS, and ECL vi Digital circuit vo

5V
vi
0V
t
4V
vo
0V

A digital circuit responds to an

input’s binary level (0 or 1) vi
3.7 V
and not to its actual voltage 0.5 V
t
4V
vo
0V

Introduction 30

 The exact value of an input voltage is critical for

a digital circuit?
◦ False
 Can a digital circuit produce the same output
voltage for different input voltage values?
◦ True
 A digital circuit is also referred to as a
◦ Logic circuit
 A graph that shows how one or more digital
signals change with time is called a
◦ Timing diagram

Introduction 31
 “H”: 01001000
“i”: 01101001
 Parallel
transmission
◦ uses one connecting
line per bit
◦ and all bits are
transmitted
simultaneously
 Serial transmission
◦ uses only one signal
line
◦ and the individual
bits are transmitted
serially (one at a
time)

 Describe the relative advantages of parallel

and serial transmission of binary data
◦ Parallel is faster
◦ Serial requires only one signal line

Introduction 33
  When an input is applied to a circuit, the
output will change its state, but it will
remain in the new state even after the
input is removed. This property of
retaining its response to a momentary
input is called memory.
Non-memory
circuit

Memory
circuit

Comparison of non-memory and memory operation

Introduction 34

Central Processor Unit – CPU

Arithmetic
Logic

Data Input Control Output Data

Information Information

Memory Control signal

Data/Information

Functional diagram of a digital computer

Introduction 35
  Type of Computers
◦ microcomputer, minicomputer (workstation), and
mainframe.
 Microcomputer
◦ the smallest type of computer
◦ consists of several IC chips: microprocessor,
memory, and I/O interface
 Microcontroller
◦ a more specialized type of microcomputer
◦ designed to be used as a dedicated or embedded
controller

Introduction 36

 Explain how a digital circuit that has

memory differs from one that does not ?
◦ One that has memory will have its output
changed and remain changed in response to a
momentary change in the input signal.
 Name the five major functional units of a
computer
◦ Input, output, memory, arithmetic/logic, control
 Which two units make up the CPU?
◦ Control, arithmetic/logic
 An IC chip that contains a CPU is called a
◦ Microprocessor

Introduction 37
  Lots of gates on a chip are called Integrated
Circuits.
 Initially part of a wafer, then sliced and diced
up.
 Classified by scale of integration:
◦ 1-20 Gates: Small Scale Integration
◦ 20-200 Gates: Medium Scale Integration
◦ 200-1,000,000 Gates: Large Scale Integration
◦ > 1,000,000 Gates: Very Large Scale Integration
(VLSI)

Introduction 39

 Digital design is ubiquitous and pervasive.

 There is a lot to talk about the digital
system.

Introduction 40
 Dinh Duc Anh Vu
International University – VNU HCM

 Number representations
 Common codes
 Computations (Digital arithmetic)

Number Systems 2
 Recognize the basic characteristics of the binary number system.
 Convert a binary number to its decimal equivalent.
 Count in the binary number system
 Convert a number from one number system (decimal, binary,
hexadecimal) to its equivalent in one of the other number systems.
 Cite the advantages of the hexadecimal number system.
 Count in hexadecimal.
 Represent decimal numbers using the BCD code; cite the pros and cons
of using BCD.
 Understand the difference between BCD and straight binary.
 Understand the purpose of alphanumeric codes such as the ASCII code.
 Perform binary addition, subtraction, multiplication, and division on
two binary numbers.
 Compare the advantages and disadvantages among three different
systems of representing signed binary numbers.
 Manipulate signed binary numbers using the 2’s-complement system.
 Understand the BCD addition process

Number Systems 3

Decimal system
Binary system
Hexadecimal system

Number Systems 4
 453
10112
 A number in the number system is: 25.310
◦ created by one or more digits.
◦ comprised of the integer part and fractional part
separated by the radix point (or base point)
◦ Positional number system: Each digit carries a
certain weight based on its position
decimal point

… 104 103 102 101 100 . 10-1 10-2 …

tenths position
hundreds position ones position
tens position
hundredths position

Number Systems 5

 The weight of each digit: The weight =

baseposition
 The last digit on the left: the most significant
digit (MSD)
 The last digit on the right: the least
significant digit (LSD)
 The value of the number = Σ(digit * its
weight)

Number Systems 6
1. Decimal system
2. Binary system
3. Hexadecimal system
4. Octal system

Number Systems 7

 Symbol: D
 Base: 10
 Digits used: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
 The decimal system is a positional-value system
in which the value of a digit depends on its
position.
 Example:

2745.214=2x103+7x102+4x101+5x100
+2x10-1+1x10-2+4x10-3

Number Systems 8
 Symbol: B
 Base: 2
 Digits used: 0, 1
 Example:
◦ 1011.101B

Number Systems 9

 Convert the number in binary system into

decimal system, i.e., calculate the value of
the binary number
 Any binary number can be converted to its
decimal equivalent simply by summing
together the weights of the various positions
in the binary number that contain a 1
 Example:

Number Systems 10
 The first method is the reverse of the previous process:
The decimal number is simply expressed as a sum of
powers of 2, and then 1s and 0s are written in the
appropriate bit positions

 Another method for converting

decimal integers uses
repeated division by 2: divide
the integer by 2 until the quotient
is zero. Then, collect the remainders
upward
=> 19D = 10011B

Number Systems 11

 Convert the number in decimal system into

binary system  For a fraction: multiply the
fraction and 2, then taking out the integer part
of the product.
 Repeat the multiplication of the fraction and 2,
until the fraction is zero or reaches to an
accuracy accepted. The binary obtained is the
downward collections of removed integers.
 Example: Convert 0.8125D into binary system
0.8125 x 2 = 1.625 → take out 1
0.625 x 2 = 1.25 → take out 1
0.25 x 2 = 0.5 → take out 0
0.5 x 2 = 1.0 → take out 1
 The binary obtained is 0.1101B

Number Systems 12
 Example: Convert 12.69D into Binary system
The integer part: 12D = 1100B
The fraction:
0.69 x 2 = 1.38 → take out 1
0.38 x 2 = 0.76 → take out 0
0.76 x 2 = 1.52 → take out 1
0.52 x 2 = 1.04 → take out 1
0.04 x 2 = 0.08 → take out 0

Result: 12.69D 1100.10110B

Number Systems 13

 Symbol: H
 Base: 16
 Digit used: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
◦ The digits A, B, C, D, E, F are worth 10, 11, 12, 13, 14, 15,
respectively
 Calculate the value of the hexadecimal number 2A9H
2A9H = 2x162 + 10x161 + 9x160
= 2x256 + 10x16 + 9x1
= 681D
 Hexadecimal numbers are often used to describe a
computer’s memory address space
◦ 0xF000 – 0xFFFF

Number Systems 14
  Convert the number in decimal system into
hexadecimal system
 Divide the decimal number by 16 until the quotient
is zero. The hexadecimal obtained is the upward
collections of the remainders
 Example: Convert 11512D into hexadecimal
system.

Result: 11512D = 2CF8H

Number Systems 15

 Convert the number in

hexadecimal system into
binary system: One digit in
hexadecimal system is
equivalent to 4 bits in
binary system

3D6FH = 0011 1101 0110 1111B

Number Systems 16
 Convert the number in binary system into
hexadecimal system: From the unit column,
group 4 bits of binary number together, then
convert each group into the corresponding
hexadecimal digit

Number Systems 17

 When converting from binary [or hex] to

decimal, use the method of taking the weighted
sum of each digit position.
 When converting from decimal to binary [or
hex], use the method of repeatedly dividing by
2 [or 16] and collecting remainders (Figure 2-1).
 When converting from binary to hex, group the
bits in groups of four, and convert each group
into the correct hex digit.
 When converting from hex to binary, convert
each digit into its four-bit equivalent.

Number Systems 18
Code: group of special symbols that represent numbers, letters, words

Morse code: series of dots and dashes represents letters of alphabet

Straight binary coding

BCD Code
Excess-3 Code
Gray Code
Alphanumeric Code

Number Systems 19

Code word: particular combination of n bit-values that represents different numbers

Number Systems 20
 b3 b2 b1 b0
23 22 21 20

 Binary Coded Decimal (BCD 8421) 8 4 2 1

◦ Used to represent the decimal digits 0 - 9.
◦ 4 bits are used.
◦ Each bit position has a weight associated with it
(weighted code).
◦ Weights are: 8, 4, 2, and 1 from MSB to LSB (called 8-
4-2-1 code).
0: 0000 1: 0001 2: 0010 3: 0011 4: 0100
5: 0101 6: 0110 7: 0111 8: 1000 9: 1001
 BCD Codes:
◦ Used to encode numbers for output to numerical
displays
◦ Used in processors that perform decimal arithmetic.
 Example: (9750)10 = (1001 0111 0101 0000)BCD

Number Systems 21

 Each digit of a decimal number is represented by

its binary equivalent
 Examples
8 7 4 (decimal)
↓ ↓ ↓
1000 0111 0100 (BCD)

9 4 3 (decimal)
↓ ↓ ↓
1001 0100 0011 (BCD)

Dec 0 1 2 3 4 5 6 7 8 9
BCD 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001

Number Systems 22
 Convert 0110100000111001 (BCD) to its
decimal equivalent
0110 1000 0011 1001
6 8 3 9

 Convert the BCD number 011111000001 to

its decimal equivalent
0111 1100 0001
7 Error 1
(The forbidden code group indicated an error)

Number Systems 23

 is one kind of BCD code

 used to represent a decimal number
 is a 4-bit binary combination with weights
2-4-2-1.
 characterized by complement of “base-1”
◦ Number 0 has 2421 code is 0000, complements
with number 9 having 2421 code is 1111
◦ Number 3 has 2421 code is 0011, complements
with number 6 having 2421 code is 1100
 The binary combinations from 0101 to 1010
are not included in BCD 2421

Number Systems 24
 A straight binary code takes the complete
decimal number and represents it in binary
 A BCD code converts each decimal digit to
binary individually
 Examples
◦ 17810 = 101100102 (8 bit)
◦ 17810 = 0001 0111 1000BCD (12 bit)

 BCD uses more bits, but easier to convert to

and from decimal

Number Systems 25

 Created from 8421 code by adding 3.

 Has no weight → not suited for arithmetic
operations, but similar to BCD 8421 code
 Represent a decimal digit
 Characterized by base complement
 Example:
◦ Number 0 has the Excess 3 code is 0011,
complements with number 9 having the Excess 3 code
is 1100
◦ Number 4 has the Excess 3 code is 0111,
complements with number 5 having the Excess 3 code
is 1000

Number Systems 26
 0 1 1
1 0 0

 is not BCD Code.

 has no weight → not suited for arithmetic operations
 only one bit ever changes between two successive numbers in
the sequence
 created from the binary code based on the following principle:
◦ MSB of Gray code and that of binary code is the same.
◦ Add MSB of binary number into the right bit and write the sum (ignore
the carrier)
◦ Continue to LSB.
◦ The numbers of bits in Gray Code are the same to that in binary code.

Number Systems 27

 Different:
◦ If inputs are the same, then G=0.
◦ If inputs are different, then G=1
 The bit following bit 0 of binary code is not changed, the bit following bit 1 of
binary code is reversed

Binary code 1 + 1+ 0 + 1+ 0 Gray code 1 0 0 1 1

+ + + +

Gray code 1 0 1 1 1 Binary code 1 1 1 0 1

Number Systems 28
 Codes representing letters of the alphabet,
punctuation marks, and other special
characters as well as numbers are called
alphanumeric codes
 The most widely used alphanumeric code is
the American Standard Code for Information
Interchange (ASCII). The ASCII (pronounced
“askee”) code is a 7-bit code
 Baudot Code

Number Systems 29

“JAMES BOND 007 SAYS HI!”

Number Systems 30
 Number Systems 31

 The following is a message encoded in ASCII

code. What is the message?
◦ 1001000 1000101 1001100 1010000
◦ HELP

 Encode the following message in ASCII code

using the hex representation: “Cost=$72.”
◦ 43 6F 73 74 3D 24 37 32 2D

 The following padded ASCII-coded message is

stored in successive memory location in a
computer: 01010011 01010100 01001111
01010000. What is the message?
◦ STOP

Number Systems 32
 Representing signed numbers
Addition & Subtraction in the
2’s complement system
BCD addition

Number Systems 33

 Given number N consisting of n digits in the

base system r, complement of “base -1” of N
is defined as (rn – 1 – N).
 Example:
◦ Complement 9 of a decimal number 123D is:
103 - 1 - 123 = 999 - 123 = 876D
◦ Complement 1 of a binary number 1100B is:
24 - 1 - 12 = 15 - 12 = 3 = 0011B
◦ Complement 15 of a hexadecimal number 2CH is:
162 - 1 - 44 = 255 - 44 = 211 = D3H

Number Systems 34
 To find complement 9 of a decimal number,
take 9 minus each digit
 Example: Find complement 9 of 270284D
9 9 9 9 9 9
2 7 0 2 8 4
7 2 9 7 1 5
Result: Complement 9 of 270284 is 729715

Number Systems 35

 To find complement 1 of a binary, change bit

1 to bit 0 and change bit 0 to bit 1
 Example:
◦ Complement 1 of 1100110B is 0011001B
◦ Complement 1 of 01101110B is 10010001B

Number Systems 36
 Given number N consisting of n digits in the
base system r, base complement of N is
defined:
◦ rn - N if N ≠ 0
◦ 0 if N = 0
 Example
◦ Complement 10 of a decimal number 123D is:
103 - 123 = 1000 - 123 = 877D
◦ Complement 2 of a binary number 1100B is:
24 - 12 = 16 - 12 = 4 = 0100B
◦ Complement 16 of a hexadecimal number 2CH is:
162 - 44 = 256 - 44 = 212 = D4H
Number Systems 37

 Base complement can also be calculated by

adding 1 in the complement of “base -1”
 Example
◦ Complement 9 of 456D is 543D
 Complement 10 of 456D is 543 + 1 = 544D
◦ Complement 1 of 1011B is 0100B
 Complement 2 of 1011B is 0100B + 1 = 0101B
◦ Complement 1 of 1000B is 0111B
 Complement 2 of 1000B is 0111B + 1 = 1000B

Number Systems 38
 Unsigned binary number
◦ The value of unsigned binary number ≥ 0.
◦ An unsigned binary number n bits expresses value
in range of 0 to 2n - 1.
◦ Example:
 1010B = 10D, in range of 0 to 24 – 1 (15)
 01100001B = 97D, in range of 0 to 28 – 1 (255)

Number Systems 39

 Signed binary number

◦ Three ways to represent signed numbers
1. Sign-Magnitude
2. 1’s Complement
3. 2’s Complement

Number Systems 40
 +98
-67
+123.7
-13.72

 A number consists of a magnitude and a symbol

indicating whether the magnitude is positive or
negative
 For binary system
◦ MSB is used as the sign bit (0 – plus, 1 – minus)
◦ The magnitude bits are the true binary equivalent of the
decimal value being represented

◦ Two values for zero: 0000 and 1111

◦ Range for n bits:
-(2n-1-1) through +(2n-1-1)

Number Systems 41

 The positive number is represented as in the

common binary form, and the MSB is “0”.
 The negative number is obtained by find the
1’s complement of the corresponding
positive number.
 Example:

 Two values for zero: 0000 and 1111

 Range for n bits: -(2n-1-1) through +(2n-1-1)

Number Systems 42
 The positive number is represented as in the
common binary form, and the MSB is “0”.
 The negative number is obtained by find the 2’s
complement of the corresponding positive
number.
 Example: 0110B = +6D
2’s complement of 0110B is 1010B
2′𝑠 𝑐𝑜𝑚𝑝𝑙𝑒𝑚𝑒𝑛𝑡
1010𝐵 −6𝐷
 Only one representation of zero
 Range for n bits: -2n-1 through +(2n-1-1)

Number Systems 43

 Represent -9D in 2’s complement form

◦ +9D = 01001B
◦ 2’s complement of 01001B is 10111B
◦ So -9D = 10111B

 Convert -14D into signed binary number

◦ +14D = 01110B
◦ Complement 2 of 01110B is 10010B
 -14D = 10010B

 Convert the signed binary number 11101B into

Decimal number
◦ Complement 2 of 11101B is 00011B = +3D
 11101B = -3D

Number Systems 44
 The MSB of the negative numbers in the signed
binary system = 1
 For positive numbers, adding bits 0 to the left
(in front of MSB) does not change the number’s
value.
 For negative numbers, adding bits 1 to the left
(in front of MSB) does not change the number’s
value.
 Copy sign bit to the left is called sign extension
 Example:
◦ 0110B = 00110B = 000110B = … = +6D
◦ 1010B = 11010B = 111010B = … = -6D

Number Systems 45

 Another way to take the two’s complement

of a number:
◦ copy bits from right to left until (and including)
the first “1”
◦ flip remaining bits to the left
 To negate a signed binary number by 2’s-
complementing it

Number Systems 46
 Number Systems 47

 Example: 7 + 6

 Overflow if result out of range

◦ Adding +ve and –ve operands, no overflow
◦ Adding two +ve operands
 Overflow if result sign is 1
◦ Adding two –ve operands
 Overflow if result sign is 0

Number Systems 48
  Negate the subtrahend and add this to the
minuend
 Example: 9 – 4 = 9 + (–4)

 Overflow if result out of range

◦ Subtracting two +ve or two –ve operands, no overflow
◦ Subtracting +ve from –ve operand
 Overflow if result sign is 0
◦ Subtracting –ve from +ve operand
 Overflow if result sign is 1

Number Systems 49

Example: Using 2’s complement to do the subtraction

111001 - 1010
111001
+
Complement 2 of 001010 is: 110110

1101111
Ignore the last carry:
111001 - 1010 = 101111

Number Systems 50
Example:
Using complement 2 to do subtraction 1010 - 111001
001010
+
Complement 2 of 111001 is: 0 0 0 1 1 1

010001
There is no last carry. Find 2’s complement of 010001
is 101111  1010 - 111001 = -101111

Number Systems 51

Number Systems 52
 Sum Equals 9 or Less
◦ none of the sums of the pairs of decimal digits exceeded 9;
therefore, no decimal carries were produced.
◦ the BCD addition process is straightforward and is actually
the same as binary addition
 Sum Greater than 9
◦ Sum is one of the six forbidden or invalid four-bit code
groups because the sum of the two digits exceeds 9.
◦ Whenever this occurs, the sum must be corrected by the
addition of six (0110) to take into account the skipping of
the six invalid code groups

Number Systems 53

 Using ordinary binary addition, add the BCD code

groups for each digit position.
 For those positions where the sum is 9 or less, no
correction is needed. The sum is in proper BCD
form.
 When the sum of two digits is greater than 9, a
correction of 0110 should be added to that sum to
get the proper BCD result. This case always
produces a carry into the next digit position, either
from the original addition (step 1) or from the
correction addition

Number Systems 54
 The hexadecimal number system is used in digital systems
and computers as efficient ways of representing binary
quantities
 In conversion between hex and binary, each hex digit
corresponds to 4 bits
 The repeated division method is used to convert decimal
numbers to binary or hexadecimal
 Using N bit binary number, we can represent decimal
values from 0 to 2N-1
 The BCD code for a decimal number is formed by
converting each digit of the decimal number to its 4-bit
binary equivalent
 An alphanumeric code is one that uses groups of bits to
represent all of the various characters and functions that
are part of a typical computer’s keyboard. The ASCII code
the most widely used alphanumeric code

Number Systems 55
 Logic circuits

 Boolean expression
 Truth table
 Logic diagram
 Timing diagram

Logic circuits 2
 Three basic logic operations: AND, OR, NOT
 Operation of logic circuits and construction of
truth tables
 Timing diagrams for the various logic-circuit
gates
 Boolean expression for the logic circuits
 Implement logic circuits using AND, OR, NOT
 Simplify logic expressions
◦ DeMorgan’s theorem
 Using NAND or NOR to implement a circuit
 Alternate gate symbols vs. standard logic-gate
symbols
 Active high & Active low

Logic circuits 3

 Boolean constants and variables are allowed

to have only two possible values, 0 or 1
 Boolean 0 and 1 do not represent actual
numbers but instead represent the state of
a voltage variable, or what is called its logic
level
 0/1 and Low/High are used most of the
time
 Three Logic operations:
AND, OR, NOT

Logic circuits 4
 The function x = f(A1, A2, …, AN) is called a
N-variable logic function if A1, A2, …,AN are
logic variables and x  X, with X={0,1}.
◦ The right side: logic expression.
◦ The left side: logic variable
 Logic expression (Boolean expression) is an
algebraic expression with the operands are
logic variables and operators are basic logic
operations

Logic circuits 5

 Logic functions → Logic circuits

 Logic circuits → Logic functions
 The inputs of logic circuits Logic variables
 The outputs of logic circuits The value of
function
 Logic Gates
◦ A logic circuit corresponding to a basic logic operation
of Boolean algebra is called the logic gate
◦ Logic gate is constructed from diodes, transistors, and
resistors whose output is the result of a basic logic
operation (OR, AND, NOT) performed on the inputs

Logic circuits 6
 How a logic circuit’s output
depends on the logic levels
present at the inputs
◦ List all the outputs of logic circuit
based on the a combination of inputs’
values

 Truth Table
◦ x is a logic 1 for every combination of input levels where
one or more inputs are 1
◦ Boolean expression x = A + B
 x equals A OR B
 To describe this circuit in the English language we could say
that x is true (1) WHEN A is true (1) OR B is true (1)
 OR Gate
◦ is a circuit that has two or more inputs and whose output is
equal to the OR combination of the inputs
◦ its output is HIGH (logic 1) if either input A or B or both are
at a logic 1 level; for all other cases the output will be 0

Logic circuits 8
 Logic circuits 9

 The OR operation produces a result (output)

of 1 whenever any input is a 1. Otherwise the
output is 0
 An OR gate is a logic circuit that performs an
OR operation on the circuit's input
 The expression x=A+B is read as “x equals A
OR B”

Logic circuits 10
Logic circuits 11

Logic circuits 12
 Truth Table
◦ x is a logic 1 only when both A and B are at the logic 1
level. For any case where one of the inputs is 0, the
output is 0.
◦ Boolean expression x = A.B
 x equals A AND B
 AND gate
◦ is a digital circuit performing the AND operation
◦ An AND gate output will be 1 only for the case when
all inputs are 1; for all other cases the output will be 0

Logic circuits 13
 The AND operation is performed the same as
ordinary multiplication of 1s and 0s
 An AND gate is a logic circuit that performs
the AND operation on the circuit’s inputs
 An AND gate output will be 1 only for the
case when all inputs are 1; for all other cases
the output will be 0
 The expression x=AB is read as “x equals A
AND B”

Logic circuits 15

 Determine the output x from the AND gate

for the given input waveforms.

Logic circuits 16
 Determine the output waveform for the AND
gate

Logic circuits 17

 NOT operation
◦ One variable function.
◦ Boolean expression: x = 𝐴ҧ (inverse of A, complement
of A, or NOT A)
◦ Truth table
 NOT gate
◦ is a digital circuit, Inverter, performing the
NOT operation
◦ It inverts (complements) the input signal so that
whenever the input=0, output=1, and vice versa

Logic circuits 18
 Logic circuits 19

 OR (resembles binary addition, except for

one operation)
◦ 0+0=0 0+1=1 1+0=1 1+1=1

 AND (resembles binary multiplication)

◦ 0•0=0 0•1=0 1•0=0 1•1=1

 NOT (invert)
◦ 1=0 0=1

Logic circuits 20
 Any logic circuit, no matter how complex,
can be completely described using the three
basic Boolean operations: OR, AND, NOT
◦ the basic building blocks of digital systems
 Example: logic circuit with its Boolean
expression

Logic circuits 21

 Often needed to establish precedence;

sometimes used optionally for clarity
 How to interpret A•B+C?
◦ Is it A•B ORed with C ? Is it A ANDed with B+C ?
 Order of precedence for Boolean algebra:
AND before OR. Parentheses make the
expression clearer, but they are not needed
for some cases
 Note that parentheses are needed here

Logic circuits 22
 Whenever an INVERTER is present in a logic-
circuit diagram, its output expression is
simply equal to the input expression with a
bar over it

Logic circuits 23

A
A ABC
B 1
C X = ABC(A+D)
2
A+D A+D
D

(A+B)C (A+B)C
(A+B)C + D
A A+B
B 1
1
2
C 2
D
E X = [(A+B)C + D]E

Logic circuits 24
 Rule
◦ First, perform all inversions of single terms
◦ Perform all operations with parentheses
◦ Perform an AND operation before an OR operation
unless parentheses indicate otherwise
◦ If an expression has a bar over it, perform the
operations inside the expression first and then
invert the result
 Example, 𝑥 = 𝐴𝐵𝐶(𝐴
ҧ + 𝐷)
◦ A=0, B=1, C=1, D=1

Logic circuits 25

1
A=0 1
B=1 1
C=1 X=0
2
1 0
D=1

Determine the output for the condition where all inputs are LOW?

Logic circuits 26
 Whenever you have a combinational logic circuit and you
want to know how it works, the best way to analyze it is to
use a truth table.
 The advantages of this method are:
◦ It allows you to analyze one gate or logic combination at a time.
◦ It allows you to easily double-check your work.
◦ When you are done, you have a table that is of tremendous
benefit in troubleshooting the logic circuit.

Logic circuits 27

 When the operation of a circuit is defined by a Boolean

expression, we can draw a logic circuit diagram directly from
that expression
 Suppose that we wanted to construct a circuit whose output
is 𝑥 = 𝐴𝐶 + 𝐵𝐶ҧ + 𝐴𝐵𝐶
ҧ
AC X = AC+BC+ABC
BC
ABC
A AC
1
C

BC X = AC+BC+ABC
2
B

ABC
3

Logic circuits 28
 Draw the circuit diagram to implement the
expression 𝑥 = (𝐴 + 𝐵)(𝐵 + 𝐶)

A A+B
B 1
X = (A+B)(B+C)

B+C
C 2

Logic circuits 29

 2-input NOR operation

◦ Boolean expression 𝑥 = 𝐴 + 𝐵
◦ Symbol: 𝐴 + 𝐵 (A NOR B)
◦ Truth table
 NOR gate
◦ is a digital circuit performing the NOR operation
◦ the output goes LOW when any input is HIGH

Logic circuits 30
 Logic circuits 31

 Determine the Boolean expression for a 3-

input NOR gate followed by an INVERTER

A A+B+C A+B+C = A+B+C

B
C

Logic circuits 32
 NAND operation
◦ Boolean expression x = 𝐴. 𝐵
◦ Symbol: 𝐴. 𝐵 (A NAND B)
◦ Truth table
 NAND gate
◦ is a digital circuit performing the NAND operation
◦ the output goes LOW only when all inputs are HIGH

Logic circuits 33

Logic circuits 34
 Implement the logic circuit that has the
expression 𝑥 = 𝐴𝐵 ⋅ 𝐶 + 𝐷 using only NOR
and NAND gates

C C+D
D
𝑥 = 𝐴𝐵 ⋅ 𝐶 + 𝐷
A
B

Logic circuits 35

 Determine the output level in last example

for A=B=C=1 and D=0

C
1
0 C+D 𝑥 = 𝐴𝐵 ⋅ 𝐶 + 𝐷
D
0 1 1
A
B
1

Logic circuits 36
 Exclusive-OR
◦ Boolean expression: x = 𝐴. 𝐵ത + 𝐴.ҧ 𝐵
◦ Symbol: 𝐴 ⊕ 𝐵 (A XOR B)
 XOR gate
◦ is a digital circuit performing the XOR operation
◦ The circuit produces a HIGH output whenever the
two inputs are at opposite levels.

Logic circuits 37

Logic circuits 38
 Exclusive-NOR
◦ Boolean expression: x = 𝐴. 𝐵ത + 𝐴.ҧ 𝐵
◦ Symbol: 𝐴 ⊕ 𝐵 (A XNOR B)
 XNOR gate
◦ is a digital circuit performing the exclusive-NOR
operation
◦ The XNOR produces a HIGH output whenever the two
inputs are at the same level

Logic circuits 39

Logic circuits 40
 Let X: boolean variable, 0,1: constants

1. X+0=X -- Zero Axiom

2. X•1 =X -- Unit Axiom
3. X+1 =1 -- Unit Property
4. X•0 =0 -- Zero Property
5. X+X=X -- Idepotence
6. X•X =X -- Idepotence
7. X + X’ = 1 -- Complement
8. X • X’ = 0 -- Complement
9. (X’)’ = X -- Involution

Logic circuits 41

x x
x x
0 1

𝑥+0= 𝑥 𝑥. 1 = 𝑥

x x
1 0
1 0

𝑥+1 = 1 𝑥. 0 = 0

x x
x x

𝑥+𝑥 =𝑥 𝑥. 𝑥 = 𝑥

x x
1 0

𝑥+𝑥 =1 𝑥. 𝑥 = 0

Logic circuits 42
 Commutativity
1. 𝑥+𝑦 =𝑦+𝑥
2. 𝑥𝑦 = 𝑦𝑥
 Associativity
1. 𝑥+ 𝑦+𝑧 = 𝑥+𝑦 +𝑧
2. 𝑥𝑦 𝑧 = 𝑥(𝑦𝑧)
 Distributivity
1. 𝑥 𝑦 + 𝑧 = 𝑥𝑦 + 𝑥𝑧
2. 𝑥 + 𝑦𝑧 = (𝑥 + 𝑦)(𝑥 + 𝑧)
 Absorption (covering)
1. 𝑥 + 𝑥𝑦 = 𝑥
2. 𝑥 + 𝑥𝑦ҧ =𝑥+𝑦
3. 𝑥ҧ + 𝑥𝑦 = 𝑥ҧ + 𝑦

Logic circuits 43

 Simplify the expression 𝑦 = 𝐴𝐵𝐷 + 𝐴𝐵𝐷

◦ 𝑦 = 𝐴𝐵 𝐷 + 𝐷
ഥ = 𝐴𝐵ത 1 = 𝐴𝐵ത

 Simplify 𝑧 = (𝐴ҧ + 𝐵)(𝐴 + 𝐵)

◦ 𝑧 = 𝐴𝐴
ҧ + 𝐴𝐵
ҧ + 𝐴𝐵 + 𝐵. 𝐵
ҧ + 𝐴𝐵 + 𝐵
= 𝐴𝐵
= 𝐵 𝐴ҧ + 𝐴 + 1
=𝐵

 Simplify 𝑥 = 𝐴𝐶𝐷 + 𝐴𝐵𝐶𝐷

◦ 𝑥 = 𝐶𝐷 𝐴 + 𝐴𝐵 = 𝐶𝐷 𝐴 + 𝐵 = 𝐴𝐶𝐷 + 𝐵𝐶𝐷

Logic circuits 44
 𝑥+𝑦 =𝑥⋅𝑦 𝑥⋅𝑦 =𝑥+𝑦

 Simplify the expression 𝑧 = 𝐴 + 𝐶 ⋅ 𝐵 + 𝐷

to one having only single variables inverted
◦ 𝑧 = 𝐴+𝐶 + 𝐵+𝐷
= 𝐴.ҧ 𝐶ҧ + 𝐵.
ത 𝐷ഥ
= 𝐴𝐶ҧ + 𝐵𝐷ത

Logic circuits 45

 The complement of the sum is the product of

the complements
◦ 𝑥+𝑦 =𝑥⋅𝑦

 The complement of the product is the sum of

the complements
◦ 𝑥⋅𝑦 =𝑥+𝑦

 In general,
◦ 𝑥+𝑦+𝑧 =𝑥⋅𝑦⋅𝑧
◦ 𝑥⋅𝑦⋅𝑧 =𝑥+𝑦+𝑧

Logic circuits 46
 𝑥+𝑦 = 𝑥⋅𝑦

x x
𝑥+𝑦 𝑥. 𝑦
y y

x
𝑥. 𝑦 = 𝑥 + 𝑦
y

Logic circuits 47

𝑥⋅𝑦 =𝑥+𝑦

x x
𝑥+𝑦
y y

x
𝑥 + 𝑦 = 𝑥𝑦
y

Logic circuits 48
 Determine the output expression for the
below circuit and simplify it using
DeMorgan’s Theorem

𝑧 = 𝐴𝐵𝐶
=𝐴+𝐵+𝐶
=𝐴+𝐵+𝐶

Logic circuits 49

Logic circuits 50
 Logic circuits 51

 A conveyor belt will shut down whenever specific

conditions occur. These conditions are monitored and
reflect by the states of four logic signals as follows:
◦ signal A will be HIGH whenever the conveyor belt speed is too
fast;
◦ signal B will be HIGH whenever the collection bin at the end of
the belt is full;
◦ signal C will be HIGH when the belt tension is too high;
◦ signal D will be HIGH when the manual override is off.
 A logic circuit is needed to generate a signal x that will go
HIGH whenever conditions A and B exist simultaneously or
whenever conditions C and D exist simultaneously. Clearly,
the logic expression for x will be x=AB+CD. The circuit is
to be implemented with a minimum number of ICs.
52
 14 13 12 11 10 9 8 14 13 12 11 10 9 8
VCC VCC

GND GND
1 2 3 4 5 6 7 1 2 3 4 5 6 7

74LS00 74LS08

14 13 12 11 10 9 8 14 13 12 11 10 9 8
VCC VCC

GND GND
1 2 3 4 5 6 7 1 2 3 4 5 6 7

74LS02 74LS32

Logic circuits 53

74LS08 74LS00
(1) (1)
(3) (3)
(2) 1
74LS32 74LS00
(1) (2) (9)
(3) (8)
3
74LS08 74LS00
(4) (2) (4) (10)
(6) (6)
(5) 2
(5)

1 3 5

AND 7

2 4 6

AND OR
Logic circuits 54
 55

 Invert each input and output of the standard

symbol. This is done by adding bubbles
(small circles) on input and output lines that
do not have bubbles and by removing
bubbles that are already there
 Change the operation symbol from AND to
OR, or from OR to AND. (In the special case
of the INVERTER, the operation symbol is not
changed)

Logic circuits 56
 The equivalences can be extended to gates with
any number of inputs
 None of the standard symbols have bubbles on
their inputs, and all the alternate symbols do
 The standard and alternate symbols for each gate
represent the same physical circuit; there is no
difference in the circuits represented by the two
symbols
 NAND and NOR gates are inverting gates, and so
both the standard and the alternate symbols for
each will have a bubble on either the input or the
output, AND and OR gates are non-inverting gates,
and so the alternate symbols for each will have
bubbles on both inputs and output

Logic circuits 57

 Active high/low
◦ When an input or output line on a logic circuit
symbol has no bubble on it, that line is said to be
active-high, otherwise it is active-low
◦ The presence or absence of a bubble, then,
determines the active-HIGH/active-LOW status of
a circuit’s inputs and output, and is used to
interpret the circuit operation

Logic circuits 58
 Active Active Active Active
HIGH LOW LOW HIGH

Output goes LOW only when all Output is HIGH when any
inputs are HIGH input is LOW

Logic circuits 59

Active HIGH Active LOW

Output goes HIGH when Output goes LOW only

any input is HIGH when all inputs are LOW

Logic circuits 60
 1. To obtain the alternate symbol for a logic gate,
take the standard symbol and change its
operation symbol (OR to AND, or AND to OR),
and change the bubbles on both inputs and
output (i.e., delete bubbles that are present,
and add bubbles where there are none).
2. To interpret the logic-gate operation, first
note which logic state, 0 or 1, is the active
state for the inputs and which is the active
state for the output. Then realize that the
output’s active state is produced by having all
of the inputs in their active state (if an AND
symbol is used) or by having any of the inputs
in its active state (if an OR symbol is used).

Logic circuits 61

Original circuit (all NAND gates)

Equivalent representation where output Z is active HIGH

Equivalent representation where output Z is active LOW 62

 If the circuit is being used to cause some action
(e.g., turn on an LED or activate another logic
circuit) when output Z goes to the 1 state, then
we say that Z is to be active-HIGH, and the
circuit diagram “active-HIGH” should be used.
◦ On the other hand, if the circuit is being used to cause
some action when Z goes to the 0 state, then Z is to
be active-LOW, and the diagram “active LOW” should
be used
 Bubble placement
◦ Whenever possible, choose gate symbols so that
bubble outputs are connected to bubble inputs, and
nonbubble outputs to nonbubble inputs

Logic circuits 63

 The logic circuit is being used to activate an

alarm when its output Z goes HIGH. Modify
the circuit diagram so that it represents the
circuit operation more effectively

Logic circuits 64
 When the output of the logic circuit goes
LOW, it activates another logic circuit. Modify
the circuit diagram to represent the circuit
operation more effective

Logic circuits 65

 The logic circuit generates an output, MEM, that is used to

activate the memory ICs in a particular microcomputer.
Determine the input conditions necessary to activate MEM

1. MEM is active-LOW, and it will go LOW only

when X and Y are HIGH.
2. X will be HIGH only when RD=0.
3. Y will be HIGH when either W or V is HIGH.
4. V will be HIGH when RAM=0.
5. W will be HIGH when either ROM-A or ROM-
B is 0.
6. Putting this all together, MEM will go LOW
only when RD=0 and at least one of the three
inputs ROM-A, Logic
ROM-B,
circuits or RAM is LOW. 66
 When a logic signal is in its active state, it
can be said to be asserted (=activated)
 When a logic signal is not in its active state,
it is said to be unasserted (=inactive)

 The overbar is simply a way to emphasize

that these are active-LOW signals

Logic circuits 67

 Many ways
◦ Logical statements in our own language
◦ Truth tables
◦ Traditional graphic logic symbols
◦ Boolean algebra expressions
◦ Timing diagrams

Logic circuits 68
 The following English expression
describes the way a logic circuit needs to
operate in order to drive a seatbelt warning
indicator in a car.
If the driver is present AND the driver is NOT
buckled up AND the ignition switch is on,
THEN turn on the warning light.
 Describe the circuit using Boolean algebra,
schematic diagrams with logic symbols, truth
tables, and timing diagrams.

Logic circuits 69

Logic circuits 70
 Boolean Algebra: a mathematical tool used in the
analysis and design of digital circuits
 OR, AND, NOT: basic Boolean operations
 OR: HIGH output when any input is HIGH
 AND: HIGH output only when all inputs are HIGH
 NOT: output is the opposite logic level as the input
 NOR: OR with its output connected to an INVERTER
 NAND: AND with its output connected to an
INVERTER
 Boolean theorems and rules: to simplify the
expression of a logic circuit and can lead to a
simpler way of implementing the circuit
 NAND, NOR: can be used to implement any of the
basic Boolean operations

Logic circuits 71
 Dinh Duc Anh Vu
International University – VNU HCM

 Boolean algebra
◦ Algebraic simplification
 Designing combinational circuits
 Karnaugh map simplification
 Useful combinational circuits

Boolean algebra & Combinational circuits 2

 Understanding and applying Boolean algebra in
designing logic circuits
 Convert a logic expression into a sum-of-
products expression.
 Perform the necessary steps to reduce a sum-
of-products expression to its simplest form.
 Use Boolean algebra and the Karnaugh map as
tools to simplify and design logic circuits.
 Design simple logic circuits without the help of
a truth table.
 Implement enable/disable circuits.

Boolean algebra & Combinational circuits 3

Algebra for Logic Circuits

Boolean algebra & Combinational circuits 4

 The dual of an expression is obtained by
exchanging (• and +), and (1 and 0) in it,
provided that the precedence of operations
is not changed.
 Cannot exchange 𝑥 with 𝑥ҧ

 Example:
◦ 𝐹 𝑥, 𝑦, 𝑧 = 𝑥.ҧ 𝑦. 𝑧ҧ + 𝑥.ҧ 𝑦.
ത𝑧
◦ Find 𝐻(𝑥, 𝑦, 𝑧), the dual of F
𝐻 𝑥, 𝑦, 𝑧 = 𝑥ҧ + 𝑦 + 𝑧ҧ . 𝑥ҧ + 𝑦ത + 𝑧

Boolean algebra & Combinational circuits 5

 Let X: boolean variable, and 0,1: constants

1. X + 0 = X -- Zero Axiom
2. X • 1 = X -- Unit Axiom
3. X + 1 = 1 -- Unit Property
4. X • 0 = 0 -- Zero Property
5. X + X = X -- Idempotence
6. X • X = X -- Idempotence
7. X + X’ = 1 -- Complement
8. X • X’ = 0 -- Complement

Boolean algebra & Combinational circuits 6

 Covering theorem:
◦ 𝑥+𝑥∙𝑦 =𝑥
◦ 𝑥 ∙ (𝑥 + 𝑦) = 𝑥

 Consensus theorem:
◦ 𝑥 ∙ 𝑦 + 𝑥ҧ ∙ 𝑧 + 𝑦 ∙ 𝑧 = 𝑥 ∙ 𝑦 + 𝑥ҧ ∙ 𝑧
◦ 𝑥 + 𝑦 𝑥ҧ + 𝑧 𝑦 + 𝑧 = (𝑥 + 𝑦)(𝑥ҧ + 𝑧)

Boolean algebra & Combinational circuits 7

 Unlike truth tables, expressions x y z F G

representing a Boolean function 0 0 0 1 1
are NOT unique.
0 0 1 0 0
 Example:
◦ 𝐹 𝑥, 𝑦, 𝑧 = 𝑥ҧ 𝑦ത𝑧ҧ + 𝑥𝑦
ҧ 𝑧ҧ + 𝑥𝑦𝑧ҧ 0 1 0 1 1
◦ 𝐺 𝑥, 𝑦, 𝑧 = 𝑥ҧ 𝑦ത𝑧ҧ + 𝑦𝑧ҧ 0 1 1 0 0
The corresponding truth tables

1 0 0 0 0
for F() and G() are to the right.
They are identical! 1 0 1 0 0
 Thus, F() = G() 1 1 0 1 1
1 1 1 0 0
Boolean algebra & Combinational circuits 8
  In order to design a cost-effective and efficient circuit, we must
minimize the circuit’s size (area) and propagation delay (time
required for an input signal change to be observed at the output
line)
 Observe the truth table of 𝐹 = 𝐴 + 𝐵𝐶 + 𝐴𝐵 and 𝐺 = 𝐴 + 𝐵𝐶
 Truth tables for F and G are identical, i.e. same function
 Use G to implement the logic circuit (less components)
C A B C F G
0 0 0 1 1
A F 0 0 1 1 1
0 1 0 1 1
B
0 1 1 1 1
C 1 0 0 0 0
B 1 0 1 0 0
A G
1 1 0 1 1
1 1 1 0 09

 Both circuits perform the same logic, so it should be

obvious that the simpler circuit is more desirable because
it contains fewer gates and will therefore be smaller and
cheaper than the original.
 Furthermore, the circuit reliability will improve because
there are fewer interconnections that can be potential
circuit faults

Boolean algebra & Combinational circuits 10

 Boolean algebra is a useful tool for simplifying
digital circuits.
 Why do it? Simpler can mean cheaper, smaller,
faster.
 It is not always obvious which theorems should be
applied to produce the simplest result
 Two essential steps:
◦ The original expression is put into SOP form by repeated
application of De Morgan’s theorems and multiplication of
terms.
◦ Once the original expression is in SOP form, the product
terms are checked for common factors, and factoring is
performed wherever possible. The factoring should result
in the elimination of one or more terms.

Boolean algebra & Combinational circuits 11

𝑧 = 𝐴𝐵𝐶 + 𝐴𝐵 𝐴 𝐶 = 𝐴𝐵𝐶 + 𝐴𝐵 𝐴 + 𝐶
= 𝐴𝐵𝐶 + 𝐴𝐵 𝐴 + 𝐶 = 𝐴𝐵𝐶 + 𝐴𝐵𝐴 + 𝐴𝐵𝐶 = 𝐴𝐵𝐶 + 𝐴𝐵 + 𝐴𝐵𝐶
= 𝐴𝐶 𝐵 + 𝐵 + 𝐴𝐵 = 𝐴𝐶 + 𝐴𝐵 = 𝐴(𝐶 + 𝐵)

Boolean algebra & Combinational circuits 12

 Simplify 𝐹 = 𝑥𝑦𝑧 + 𝑥𝑦𝑧 + 𝑥𝑧
𝐹 = 𝑥𝑦𝑧 + 𝑥𝑦𝑧 + 𝑥𝑧
= 𝑥𝑦 𝑧 + 𝑧 + 𝑥𝑧
= 𝑥𝑦 1 + 𝑥𝑧
= 𝑥𝑦 + 𝑥𝑧
 Simplify 𝐹 = 𝑥𝑦𝑧 + 𝑥𝑦(𝑥 𝑧)
𝐹 = 𝑥𝑦𝑧 + 𝑥𝑦 𝑥 𝑧 = 𝑥𝑦𝑧 + 𝑥𝑦 𝑥 + 𝑧
= 𝑥𝑦𝑧 + 𝑥𝑦(𝑥 + 𝑧) = 𝑥𝑦𝑧 + 𝑥𝑦 + 𝑥𝑦𝑧
= 𝑥𝑧 𝑦 + 𝑦 + 𝑥𝑦 = 𝑥𝑧 + 𝑥𝑦
= 𝑥(𝑧 + 𝑦)

Boolean algebra & Combinational circuits 13

 Prove 𝑥ҧ 𝑦ത𝑧ҧ + 𝑥𝑦
ҧ 𝑧ҧ + 𝑥𝑦𝑧ҧ = 𝑥ҧ 𝑧ҧ + 𝑦𝑧ҧ
 Proof:
𝑥ҧ 𝑦ത𝑧ҧ + 𝑥𝑦
ҧ 𝑧ҧ + 𝑥𝑦𝑧ҧ
=𝑥ҧ 𝑦ത𝑧ҧ + 𝑥𝑦ҧ 𝑧ҧ + 𝑥𝑦
ҧ 𝑧ҧ + 𝑥𝑦𝑧ҧ
=𝑥ҧ 𝑧(ҧ 𝑦ത + 𝑦) + 𝑦𝑧(ҧ 𝑥ҧ + 𝑥)
=𝑥ҧ 𝑧ҧ + 𝑦𝑧ҧ
QED.

Boolean algebra & Combinational circuits 14

 𝑧 = 𝐴𝐶 𝐴𝐵𝐷 + 𝐴𝐵𝐶 𝐷 + 𝐴𝐵𝐶

 𝑡 = (𝐴 + 𝐵)(𝐴 + 𝐵)

 𝑥 = (𝐴 + 𝐵)(𝐴 + 𝐵 + 𝐷)𝐷

Boolean algebra & Combinational circuits 15

 The complement of a function is derived by

interchanging (• and +), and (1 and 0), and
complementing each variable.
 Otherwise, interchange 1s to 0s in the truth
table column showing F.
 The complement of a function IS NOT THE
SAME as the dual of a function.

Boolean algebra & Combinational circuits 16

 Find the complement of 𝐹 = 𝑥𝑦ത𝑧ҧ + 𝑥𝑦𝑧 ҧ
 G = F’ = 𝑥 𝑦ത𝑧ҧ + 𝑥𝑦𝑧 ҧ
= 𝑥 𝑦ത𝑧ҧ ∙ 𝑥𝑦𝑧
ҧ DeMorgan
= (𝑥ҧ + 𝑦 + 𝑧)(𝑥 + 𝑦ത + 𝑧)ҧ DeMorgan

 Note: The complement of a function can also

be derived by finding the function’s dual,
and then complementing all of the literals

Boolean algebra & Combinational circuits 17

 Literal: A variable or its complement

 Product term: literals connected by •
 Sum term: literals connected by +
 Minterm: a product term in which all the
variables appear exactly once, either
complemented or uncomplemented
 Maxterm: a sum term in which all the
variables appear exactly once, either
complemented or uncomplemented

Boolean algebra & Combinational circuits 18

 A switching function can be represented by
several different, but equivalent, algebraic
expressions.
◦ There are two standard forms
 SOP (sum of product)
 POS (product of sum)
◦ The standard form is a unique algebraic
representation of each function
 Canonical form

Boolean algebra & Combinational circuits 19

 For an n-variable function, a minterm is a product term

of n variables in complemented or un-complemented
form.
◦ If the variable’s value is 0 → complemented form.
◦ If the variable’s value is 1 → un-complemented form.
 With n variables → 2n minterms
 Symbol for minterm: mi , whereas i is the decimal
equivalent of the minterm’s corresponding binary
combination (bi)
◦ Example: Assume 3 variables (A,B,C), and i=3. Then, bi = 011
and its corresponding minterm is denoted by 𝑚𝑖 = 𝐴𝐵𝐶
 If A, B and C are the input variables, the minterms are:
𝐴ҧ𝐵ത 𝐶,ҧ 𝐴ҧ𝐵𝐶,
ത 𝐴𝐵ҧ 𝐶,ҧ 𝐴𝐵𝐶,
ҧ 𝐴𝐵ത 𝐶,ҧ 𝐴𝐵𝐶,
ത 𝐴𝐵 𝐶,ҧ 𝐴𝐵𝐶
 Represents exactly one combination in the truth table

Boolean algebra & Combinational circuits 20

 For an n-variable function, a maxterm is a sum term of n
variables in complemented or un-complemented form.
◦ If the variable’s value is 1 → complemented form.
◦ If the variable’s value is 0 → un-complemented form.
 With n variables → 2n maxterms
 Symbol for maxterm: Mi , whereas i is the decimal equivalent
of the maxterm’s corresponding binary combination (bi)
◦ Example: Assume 3 variables (A,B,C), and i=3. Then, bi = 011 and its
corresponding maxterm is denoted by 𝑀𝑖 = 𝐴 + 𝐵 + 𝐶
 If A, B and C are the input variables, the maxterms are: (𝐴ҧ +
ҧ (𝐴ҧ + 𝐵ത + 𝐶), (𝐴ҧ + 𝐵 + 𝐶),
𝐵ത + 𝐶), ҧ (𝐴ҧ + 𝐵 + 𝐶), (𝐴 + 𝐵ത + 𝐶),
ҧ (𝐴 +
ҧ (𝐴 + 𝐵 + 𝐶)
𝐵ത + 𝐶), (𝐴 + 𝐵 + 𝐶),
 Represents exactly one combination in the truth table

Boolean algebra & Combinational circuits 21

Boolean algebra & Combinational circuits 22

 The complement of minterm is maxterm and
vice versa
𝑚𝑖 = 𝑀𝑖
𝑀𝑖 = 𝑚𝑖

Boolean algebra & Combinational circuits 23

 Express a Boolean function

Whereas
◦ mi is the ith minterm
◦ Fi is the F-function’s value corresponding to the ith
minterm

Boolean algebra & Combinational circuits 24

 Express the following functions in the
Standard SOP
◦ 𝐹 𝐴, 𝐵, 𝐶, 𝐷 = 𝐴𝐵𝐶𝐷 + 𝐴𝐵𝐶𝐷 + 𝐴𝐵𝐶𝐷 + 𝐴𝐵𝐶𝐷
 Already in standard SOP form
◦ 𝐹 𝐴, 𝐵, 𝐶 = 𝐴𝐶 + 𝐴𝐵
𝐹 𝐴, 𝐵, 𝐶 = 𝐴𝐶 𝐵 + 𝐵 + 𝐴𝐵 𝐶 + 𝐶
𝐹 𝐴, 𝐵, 𝐶 = 𝐴𝐵𝐶 + 𝐴𝐵𝐶 + 𝐴𝐵𝐶 + 𝐴𝐵𝐶
◦ 𝐹 𝐴, 𝐵, 𝐶, 𝐷 = (𝐴 + 𝐵)(𝐴 + 𝐶)
𝐹 𝐴, 𝐵, 𝐶, 𝐷 = 𝐴𝐴 + 𝐴𝐶 + 𝐴 𝐵 + 𝐵𝐶
𝐹 𝐴, 𝐵, 𝐶, 𝐷 = 𝐴𝐶 + 𝐴 𝐵 + 𝐵𝐶=…

Boolean algebra & Combinational circuits 25

 Write the expression form of the following

functions
 𝐹 𝐴, 𝐵, 𝐶 = σ(1,4,5,6)

 𝐹 𝐴, 𝐵, 𝐶, 𝐷 = σ(1,4,5,6)

Boolean algebra & Combinational circuits 26

 Express a Boolean function

whereas
◦ mi is the ith maxterm
◦ Fi is the F-function’s value corresponding to the ith
maxterm

Boolean algebra & Combinational circuits 27

 Write the expression form of the following

functions
 𝐹 𝐴, 𝐵, 𝐶 = ς(1,4,5,6)

 𝐹 𝐴, 𝐵, 𝐶, 𝐷 = σ(1,4,5,6)

Boolean algebra & Combinational circuits 28

 Transform the function F into the standard
form 2
 𝐹 𝐴, 𝐵, 𝐶 = σ(0,2,3,7)

𝑀𝑖 = 𝑚𝑖
𝐹 𝐴, 𝐵, 𝐶 = ෍(0,2,3,7) = ෑ(7,5,4,0)

Boolean algebra & Combinational circuits 29

 For an n-variable function, a minterm is a product term of n

variables in complemented or un-complemented form.
◦ If the variable’s value is 0 → complemented form.
◦ If the variable’s value is 1 → un-complemented form.
 Symbol for minterm: mi , whereas i is the decimal equivalent
of the minterm’s corresponding binary combination (bi)
 A maxterm is a sum term of n variables in complemented or
un-complemented form.
◦ If the variable’s value is 1 → complemented form.
◦ If the variable’s value is 0 → un-complemented form.
 Symbol for maxterm: Mi , whereas i is the decimal equivalent
of the maxterm’s corresponding binary combination (bi)
 The complement of minterm is maxterm and vice versa
◦ 𝑚𝑖 = 𝑀𝑖
◦ 𝑀𝑖 = 𝑚𝑖
 Represents exactly one combination in the truth table

Boolean algebra & Combinational circuits 30

 Transform the expression form into Standard
SOP.
 Fill values “1” in the rows having the binary
combinations equals to the minterm indices
of the expression. The other rows will have
F=0.

Boolean algebra & Combinational circuits 31

 Write the truth table of the following function

𝐹 𝐴, 𝐵, 𝐶 = 𝐴𝐶 + 𝐴𝐵
We have
𝐹 𝐴, 𝐵, 𝐶 = 𝐴𝐶 + 𝐴𝐵
= 𝐴𝐶 𝐵 + 𝐵 + 𝐴𝐵 𝐶 + 𝐶
= 𝐴𝐵𝐶 + 𝐴𝐵𝐶 + 𝐴𝐵𝐶 + 𝐴𝐵𝐶
= ෍(7,5,3,2)

Boolean algebra & Combinational circuits 32

  Transform the expression form into Standard
POS.
 Fill values “0” in the rows having the binary
combinations equals to the maxterm indices
of the expression. The other rows will have
F=1.

Boolean algebra & Combinational circuits 33

 Write the truth table of the following function

𝐹 𝐴, 𝐵, 𝐶 = 𝐴𝐶 + 𝐴𝐵

𝐹 𝐴, 𝐵, 𝐶 = 𝐴𝐶 + 𝐴𝐵
= 𝐴+𝐴 𝐴+𝐵 𝐶+𝐴 𝐶+𝐵 (dual of the distributive law)
= 𝐴+𝐵 𝐶+𝐴 𝐶+𝐵
= 𝐴 + 𝐵 + 𝐶𝐶 𝐶 + 𝐴 + 𝐵𝐵 𝐶 + 𝐵 + 𝐴𝐴
= 𝐴+𝐵+𝐶 𝐴+𝐵+𝐶 𝐶+𝐴+𝐵 𝐶+𝐴+𝐵 𝐶+𝐵+𝐴 𝐶+𝐵+𝐴
= 𝐴+𝐵+𝐶 𝐴+𝐵+𝐶 𝐶+𝐴+𝐵 𝐶+𝐴+𝐵
= ෑ(0,1,4,6)

Boolean algebra & Combinational circuits 34

 Boolean algebra & Combinational circuits 35

 Example: Write the algebraic form of the

following function

Boolean algebra & Combinational circuits 36

 Example: Write the algebraic form of the
following function

Boolean algebra & Combinational circuits 37

 In practical, there are some cases in which

the binary combinations of variables does
not exist. Thus, the output (the value of the
function) corresponding to these binary
combinations can be 0 or 1 (called “don’t
care”), symbol “d”. When filling in the Truth
Table for the “don’t care” cases, the symbol
“x” is used.

Boolean algebra & Combinational circuits 38

 Example: build Truth table for F

Boolean algebra & Combinational circuits 39

 Example: build Truth table for F

Boolean algebra & Combinational circuits 40

 Boolean algebra & Combinational circuits 41

Any logic problem can be solved using the

following step-by-step procedure.
1. Interpret the problem and set up a truth
table to describe its operation.
2. Write the AND (product) term for each case
where the output is 1.
3. Write the sum-of-products (SOP)
expression for the output.
4. Simplify the output expression if possible.
5. Implement the circuit for the final,
simplified expression.
Boolean algebra & Combinational circuits 42
 Problem: A logic circuit having 3 inputs, A, B, C will
have its output HIGH only when a majority of the inputs
are HIGH
A B C x
 Step 1 Set up the truth table
0 0 0 0
0 0 1 0
 Step 2 Write the AND term for 0 1 0 0
each case where the output is a 1. 0 1 1 1 → ABC
1 0 0 0
1 0 1 1 → ABC
1 1 0 1 → ABC
1 1 1 1 → ABC

Boolean algebra & Combinational circuits 43

 Step 3 Write the SOP form for the output

x = ABC + ABC + ABC + ABC

 Step 4 Simplify the output expression

x = ABC + ABC + ABC + ABC + ABC + ABC

= BC ( A + A) + AC (B + B ) + AB(C + C )
= BC + AC + AB

Boolean algebra & Combinational circuits 44

  Step 5 Implement the circuit

A AC
1
C

BC X = AC+BC+AC
2
B

AB
3

Boolean algebra & Combinational circuits 45

A
1
C

X = AC+BC+AC
2
B

3 1

2 4

Boolean algebra & Combinational circuits 46

 In a simple copy machine, a stop signal, S, is to be generated to
stop the machine operation and energize an indicator light
whenever either of the following conditions exists:
◦ (1) there is no paper in the paper feeder tray; or
◦ (2) the two microswitches in the paper path are activated, indicating a
jam in the paper path.
 The presence of paper in the feeder tray is indicated by a HIGH
at logic signal P. Each of the microswitches produces a logic
signal (Q and R) that goes HIGH whenever paper is passing over
the switch to activate it.
 Design the logic circuit to produce a HIGH at output signal S for
the stated conditions, and implement it using two-input NAND
gates.

Boolean algebra & Combinational circuits 47

 Step 1. Setup the truth table

 Step 2. Write the AND term

for each case where the
output is a 1

 Step 3. Write the SOP form

for the output
𝑆 = 𝑃𝑄𝑅 + 𝑃𝑄𝑅 + 𝑃𝑄𝑅 + 𝑃𝑄𝑅 + 𝑃𝑄𝑅

Boolean algebra & Combinational circuits 48

 Step 4. Simplify the output expression
𝑆 = 𝑃𝑄𝑅 + 𝑃𝑄𝑅 + 𝑃𝑄𝑅 + 𝑃𝑄𝑅 + 𝑃𝑄𝑅
= 𝑃𝑄(𝑅 + 𝑅) + 𝑃𝑄(𝑅 + 𝑅) + 𝑃𝑄𝑅
= 𝑃𝑄 + 𝑃𝑄 + 𝑃𝑄𝑅
= 𝑃 𝑄 + 𝑄 + 𝑃𝑄𝑅 = 𝑃 + 𝑃𝑄𝑅
= 𝑃 + 𝑄𝑅 (by applying 𝑥 + 𝑥𝑦 = 𝑥 + 𝑦)
 Step 5. Implement the circuit

Boolean algebra & Combinational circuits 49

Boolean algebra & Combinational circuits 50

 A B C D z
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
 Designing a circuit that has 4 logic 0 1 0 0 0

signal lines A, B, C, D representing 0 1 0 1 0

a 4-bit binary number with A as 0 1 1 0 0

→ ABCD
MSB and D as LSB. The circuit 0 1 1 1 1
1 0 0 0 1 → ABCD
produces a HIGH output only when
1 0 0 1 1 → ABCD
the binary number is greater than 1 0 1 0 1 → ABCD
01102 = 610 1 0 1 1 1 → ABCD
1 1 0 0 1 → ABCD
B
C 1 1 0 1 1 → ABCD
z = A+BCD
D 1 1 1 0 1 → ABCD
A 1 1 1 1 1 → ABCD

Boolean algebra & Combinational circuits 51

B
C z = A+BCD
D
A
B
C 1
D
3

A 2

 Process of converting a SOP circuit from AND/OR to

NAND gates as follows
1. Replace each AND/OR/INVERTER gate by a single NAND gate
2. Use a NAND gate to invert any single variable that is feeding
the final OR gate

Boolean algebra & Combinational circuits 52

 Design a logic circuit with inputs P, Q, R so
that output S is HIGH whenever P=0 or
whenever Q=R=1

Boolean algebra & Combinational circuits 53

 Write the SOP expression for a circuit with 4

inputs and an output that is to be HIGH only
when input A is LOW at the same time that
exactly two other inputs are LOW

 Implement the expression of the above

question using all NAND gates. How many
gates are required?

Boolean algebra & Combinational circuits 54

 Tool to simplify a logic
expression

Boolean algebra & Combinational circuits 55

 K Map that shows the relationship between inputs &

outputs, is a method used to simplify the Boolean
function
 Each cell of K-map expresses a value of function F
(0, 1 or x), corresponding to a row of the Truth
Table
 Horizontally & vertically adjacent squares differ only
in one variable
◦ Note that each square in the top row is considered to be
adjacent to a corresponding square in the bottom row.
 Once a K map has been filled with 0s and 1s, the
SOP expression for the output can be obtained by
ORing together those squares that contain a 1.

Boolean algebra & Combinational circuits 56

Boolean algebra & Combinational circuits 57

Boolean algebra & Combinational circuits 58

 The function F is given
◦ by the Truth table
◦ in the Standard form 1 (-form)
◦ in the Standard form 2 (-form)
◦ in algebraic expression

Boolean algebra & Combinational circuits 59

 If the function F is based on the Truth Table

◦ Fill “0”, “1” or “x” in squares having
the same binary combinations A B C F
in Truth Table. 0 0 0 0
0 0 1 0
F AB 0 1 0 1
C 00 01 11 10 0 1 1 0
0 0 0
1 2
X 6
1 4
1 0 0 1
1 0 0 0 X 1 0 1 x
1 3 7 5
1 1 0 x
1 1 1 0
Boolean algebra & Combinational circuits 60
  If the function F is given in the standard SOP form (-form)
◦ Fill “1” in squares corresponding to minterms,
◦ Fill “x” in squares corresponding to “don’t care”
◦ Fill “0” in the remained squares
 We can fill only two symbols “1” and “x” in the K-map. The
blank squares are implicit.
F AB
00 01 11 10
CD
00 0 X 0 1
0 4 12 8
𝐹 𝐴, 𝐵, 𝐶, 𝐷 = ෍(2,3,5,8,11,13,14) + 𝑑(1,4,15)
01 X 1 1 5 1 13 0 9

11 13 0 7
X15 1 11
10 12 0 6
1 14 0 10
Boolean algebra & Combinational circuits 61

 If the function F is given in the standard POS form (-

form)
◦ Fill “0” in squares corresponding to maxterms,
◦ Fill “x” in squares corresponding to “don’t care”
◦ Fill “1” in the remained squares.
 We can fill only two symbols “0” and “x” in the K-map. The
blank squares are implicit. F AB
00 01 11 10
CD
00 10 0 4
0 12 X 8
𝐹 𝐴, 𝐵, 𝐶, 𝐷 = ෑ(4,5,12,14,15) . 𝑑 3,7,8,11
01 11 0 1 1
5 13 9

11 X 3 X 7 0 15 X 11
10 1 2 1 6 0 14 1 10
Boolean algebra & Combinational circuits 62
  If the function F is given in algebraic form
◦ Convert it into Standard SOP or POS and then fill in the K-
map.
◦ If it has the form of SOP, transform it into standard SOP.
◦ If it has the form of POS, transform it into standard POS.
F AB
00 01 11 10
CD
00 00 0 4
0 12 0 8
𝐹 𝐴, 𝐵, 𝐶, 𝐷 = 𝐴𝐵𝐶𝐷 + 𝐴𝐵𝐶 + 𝐵𝐶𝐷 + 𝐴𝐷
= σ(2,6,7,9,10,11,13,15) 01 01 0 1 1
5 13 9

11 0 1 1 15 1 11
3 7

10 1 2 1 6 0 14 1 10
Boolean algebra & Combinational circuits 63

F AB
00 01 11 10
CD
00
0 4 12 8

 Looping is a process combining the

01 squares which
contain 1s. The output expression can be1 simplified
5 13 by 9

looping 11
 Adjacent squares 3 7 15 11

◦ 2 squares are adjacent if they lie close10

each other or they are
symmetric through axis. The feature of two adjacent
2 squares
6 14 is 10
they are corresponding to two minterms (or maxterms) which
are different in only 1 bit
◦ 4 squares are adjacent if they consist of 2 adjacent squares and
each square of this group is adjacent to one square of the other
◦ The above definition is applied similarly for 8 adjacent squares
and 2n adjacent squares
◦ The adjacent squares are grouped if they have the same 1 or 0

Boolean algebra & Combinational circuits 64

 When grouping the adjacent squares having
the same value “1”, we obtain a product of
variables having the same value:
◦ 0 → variables are in complemented.
◦ 1 → variables are not complemented.
(Variable with different values are omitted.)
 Because two adjacent squares have the
binary combinations which are different in
one variable
 grouping two adjacent squares can remove
one variable.

Boolean algebra & Combinational circuits 65

Looping a pair of adjacent

1s in a K map eliminates
the variable that appears in
complemented and
uncomplemented form.

Boolean algebra & Combinational circuits 66

 Similarly,
◦ When grouping 4 adjacent cells  remove 2
variables.
◦ When grouping 8 adjacent cells  remove 3
variables.
 Generally,
◦ When grouping 2n adjacent cells  remove n
variables

Boolean algebra & Combinational circuits 68

Looping a quad of
adjacent 1s
eliminates two
variables that appears
in both complemented
and uncomplemented
form

Boolean algebra & Combinational circuits 69

 Looping an octet of
adjacent 1s eliminates
three variables that
appears in both
complemented and
uncomplemented form

Boolean algebra & Combinational circuits 70

 When a variable appears in both

complemented & uncomplemented form
within a loop, that variable is eliminated
from the expression.
 Variables that are the same for all squares of
the loop must appear in the final expression

Boolean algebra & Combinational circuits 75

1. Construct the K map and place 1s and 0s in the
squares according to the truth table
2. Loop the isolated 1s which are not adjacent to any
other 1s (single loops)
3. Loop any pair which contains a 1 adjacent to only one
other 1 (double loops)
4. Loop any octet even if it contains one or more 1s that
have already been looped
5. Loop any quad that contains one or more 1s that have
not already been looped, making sure to use the
minimum number of loops
6. Loop any pairs necessary to include any 1s that have
not yet been looped, making sure to use the minimum
number of loops
7. Form the OR sum of all the terms generated by each
loop

Boolean algebra & Combinational circuits 76

 Step 1. the map was obtained from the problem truth table
 Step 2. Square 4 is the only square containing a 1 that is not
adjacent to any other 1. It is looped and is referred to as loop 4.
 Step 3. Square 15 is adjacent only to square 11. This pair is
looped and referred to as loop 11, 15.
 Step 4. There are no octets.
 Step 5. Squares 6, 7, 10, and 11 form a quad. This quad is
looped (loop 6, 7, 10, 11). Note that square 11 is used again,
even though it was part of loop 11, 15.
 Step 6. All 1s have already been looped.
 Step 7. Each loop generates a term in the expression for X.

77
 Step 1. the map was obtained from the problem truth table
 Step 2. There are no isolated 1s.
 Step 3. The 1 in square 3 is adjacent only to the 1 in square 7. Looping
this pair (loop 3, 7) produces the term 𝐴𝐶𝐷.
 Step 4. There are no octets.
 Step 5. There are two quads. Squares 5, 6, 7, and 8 form one quad.
Looping this quad produces the term 𝐴𝐵. The second quad is made up
of squares 5, 6, 9, and 10. This quad is looped because it contains two
squares that have not been looped previously. Looping this quad
produces 𝐵𝐶.
 Step 6. All 1s have already been looped.
 Step 7. Each loop generates a term in the expression for X.

78

 Step 1. the map was obtained from the problem truth table
 Step 2. There are no isolated 1s.
 Step 3. The 1 in square 2 is adjacent only to the 1 in square 6. This pair
is looped to produce 𝐴𝐶𝐷. Similarly, square 9 is adjacent only to square
10. Looping this pair produces 𝐴𝐵𝐶. Likewise, loop 7, 8 and loop 11,
15 produce the terms 𝐴𝐵𝐶 and 𝐴𝐶𝐷, respectively.
 Step 4. There are no octets.
 Step 5. There is one quad formed by squares 6, 7, 10, and 11. This
quad, however, is not looped because all the 1s in the quad have been
included in other loops.
 Step 6. All 1s have already been looped.
 Step 7. Each loop generates a term in the expression for X.

79
 Don’t-Care Conditions are certain input conditions for
which there are no specified output levels
 Don’t-care conditions should be changed to either 0 or
1 to produce K-map looping that yields the simplest
expression
 Example

Boolean algebra & Combinational circuits 80

 Let’s design a logic circuit that controls an

elevator door in a three-story building.
◦ The circuit has four inputs.
◦ M is a logic signal that indicates when the elevator is
moving (M=1) or stopped (M=0).
◦ F1, F2, and F3 are floor indicator signals that are
normally LOW, and they go HIGH only when the
elevator is positioned at the level of that particular
floor.
 For example, when the elevator is lined up level with the
second floor, F2=1 and F1=F3=0.
◦ The circuit output is the OPEN signal,
which is normally LOW
and will go HIGH when the elevator door is
to be opened.

Boolean algebra & Combinational circuits 81

 Because the elevator cannot
be lined up with more than
one floor at a time, only
one of the floor inputs can
be HIGH at any given time.
 When M=1 the elevator is
moving, so OPEN must be a
0 because we do not want
the elevator door to open.
 When M=0 (elevator
stopped) we want OPEN=1
provided that one of the
floor inputs is 1.

Boolean algebra & Combinational circuits 82

Simplify the following function:

F
AB
00 01 11 10
CD
00 1 1 1 1
01 1 1 1 1

11
10 1 1 1

Boolean algebra & Combinational circuits 83

Simplify the following function:

F
AB
00 01 11 10
CD
00 1 1
01 1 1

11
10 1 1 1

Boolean algebra & Combinational circuits 84

Simplify the following function:

F
AB
00 01 11 10
CD
00 0 0 0 0
01 0 0 0 0

11
10 0 0 0

Boolean algebra & Combinational circuits 85

Simplify the following function:
F(A,B,C,D) = (2,3,5,8,11,13,14) + d(1,6,9,10,15)
F
AB
CD
00 01 11 10 C’D
B’D 00 1
x 1 1 x
01 AB’
11 1 x 1
10 1 x 1 x
CD’

Boolean algebra & Combinational circuits 86

Simplify the following function:

F(D,C,B,A) = (2,3,5,8,11,13,14).d(1,6,9,10,15)
F
AB
CD
00 01 11 10 C+D’
B+D’ 00 0
x 0 0 x
01 A’+B
11 0 x 0
10 0 x 0 x
C’+D

Boolean algebra & Combinational circuits 87

 Compared to the algebraic method, the K-
map process is a more orderly process
requiring fewer steps and always producing a
minimum expression
◦ Algebraic simplification is considered as the trial-
and-error process
 For the circuits with large numbers of inputs
(larger than four), other more complex
techniques are used

Boolean algebra & Combinational circuits 88

• Parity generator and

checker
• Enable/Disable circuits

Boolean algebra & Combinational circuits 89

Boolean algebra & Combinational circuits 90

Boolean algebra & Combinational circuits 91

 Design a logic circuit that will allow a signal to pass to the
output only when control inputs B and C are both HIGH;
otherwise, the output will stay LOW
◦ An AND gate should be used because the signal is to be passed without
inversion, and the disable output condition is a LOW. Because the enable
condition must occur only when B=C=1, a three-input AND gate is used

 Design a logic circuit that allows a signal to pass to the output

only when one, but not both, of the control inputs are HIGH;
otherwise, the output will stay HIGH
◦ An OR gate is used because we want the output disable condition to be a
HIGH, and we do not want to invert the signal. Control inputs B and C
are combined in an XNOR gate. When B and C are different, the XNOR
sends a LOW to enable the OR gate. When B and C are the same, the
XNOR sends a HIGH to disable the OR gate.

92

 Designing a logic circuit with input signal A,

control input B and outputs X and Y to operate
as follows:
◦ When B = 1, X = A and Y = 0
◦ When B = 0, X = 0 and Y = A
◦ Pulse-steering circuit

Boolean algebra & Combinational circuits 93

 Boolean algebra
◦ SOP and POS
◦ Simplifying Boolean expression
 Design of a combinational Logic circuit
◦ construct its truth table,
◦ convert it to a SOP
◦ simplify using Boolean algebra or K mapping,
◦ implement
 K map: a graphical method for representing a circuit’s
truth table and generating a simplified expression
 Some useful logic circuits
◦ Parity generator and checker
◦ Enable/disable: Each of the basic gates can be used to enable or
disable the passage of an input signal to its output

Boolean algebra & Combinational circuits 94

 Dinh Duc Anh Vu
International University – VNU HCM

 Construct & analyze the operation of a latch FF

made from NAND or NOR gates
 Describe the difference between synchronous &
asynchronous systems
 Understand the operation of edge-triggered FFs
 Understand the major differences between
parallel and serial data transfers
 Use state transition diagrams to describe
counter operation
 Use FFs in synchronization circuits
 Connect shift registers as data transfer circuits
 Employ FFs as frequency-division and counting
circuits

Sequential Logic Circuits 2

 Combinational Outputs Memory Outputs

Combinational Memory
Logic Gates Elements

External Inputs

Sequential Logic Circuits 3

Flip-Flop (FF)
Latch
Bistable multivibrator

 A FF can have
◦ one or more inputs: These inputs are used to cause the FF to switch
back and forth (“flip-flop”) between its possible output states.
◦ two outputs, labeled Q and 𝑄, that are the inverse of each other
 The state of a FF is referred to the state of its normal output Q
 Most FF inputs need only to be momentarily activated (pulsed) in
order to cause a change in the FF output state
 The output will remain in that new state even after the input
pulse is over

Sequential Logic Circuits 4

  The two NAND gates are cross-coupled so that the output of
NAND-1 is connected to one of the inputs of NAND-2, and vice
versa.
 There are two latch inputs: the SET input is the input that sets Q
to the 1 state; the RESET input is the input that resets Q to the 0
state.
 The SET and RESET inputs are both normally resting in the HIGH
state, and one of them will be pulsed LOW whenever we want to
change the latch outputs.

Sequential Logic Circuits 5

Pulsing the SET input to the 0 state while the RESET input is kept
1 when (a) Q = 0 prior to SET pulse; (b) Q = 1 prior to SET pulse.
Note that in both cases Q ends up HIGH

Sequential Logic Circuits 6

Pulsing the CLEAR input to the LOW state while the SET input is kept 1
when (a) Q =0 prior to CLEAR pulse; (b) Q = prior to CLEAR pulse
In each case, Q ends up LOW

Sequential Logic Circuits 7

 SET = RESET = 1
◦ This condition is the normal resting state, and it has no effect on
the output state. The Q and 𝑄 outputs will remain in whatever
state they were in prior to this input condition
 SET =0; RESET = 1
◦ This will always cause the output to go to the state Q=1, where it
will remain even after SET returns HIGH. This is called setting the
latch.
 SET = 1; RESET = 0
◦ This will always produce the state Q=0, where the output will
remain even after RESET returns HIGH. This is called clearing or
resetting the latch
 SET = RESET = 0
◦ This condition tries to set and clear the latch at the same time,
and it produces 𝑄 = 𝑄 = 1. If the inputs are returned to 1
simultaneously, the resulting state is unpredictable. This input
condition should not be used.

Sequential Logic Circuits 8

  From the description of the NAND
latch operation, it should be clear
that the SET and RESET inputs are
active-LOW.
◦ The SET input will set when SET goes
LOW;
◦ The RESET input will clear when RESET
goes LOW.
 The bubbles on the inputs, as well
as the labeling of the signals as
𝑆𝐸𝑇 and 𝑅𝐸𝑆𝐸𝑇 indicate the active-
LOW status of these inputs

Sequential Logic Circuits 9

 The waveforms are applied to the inputs of

the latch. Assume that initially Q=0, and
determine the Q waveform.

Sequential Logic Circuits 10

  What is the normal resting state of the SET and
RESET inputs? What is the active state of each input?
◦ HIGH; LOW
 What will be the states of Q and 𝑄 after a FF has
been reset (cleared)?
◦ Q=0
 The SET input can never be used to make Q=0. True
or False?
◦ True
 When power is first applied to any FF circuit, it is
impossible to predict the initial states of Q and 𝑄.
What can be done to ensure that a NAND latch
always starts off in the state Q=1?
◦ Apply a momentary LOW to SET input

Sequential Logic Circuits 12

 Made of two cross-coupled NOR gates

 SET=RESET=0
◦ This is the normal resting state for the NOR latch, and it has no effect on the output
state. Q and will remain in whatever state they were in prior to the occurrence of this
input condition
 SET=1; RESET=0
◦ This will always set Q=1, where it will remain even after SET returns to 0
 SET=0; RESET=1
◦ This will always clear Q=0, where it will remain even after RESET returns to 0
 SET=RESET=1
◦ This condition tries to set and reset the latch at the same time, and it produces 𝑄 = 𝑄 =
0. If the inputs are returned to 0 simultaneously, the resulting output state is
unpredictable. This input condition should not be used

Sequential Logic Circuits 13

  Assume that Q=0 initially, and determine the
Q waveform for the NOR latch

Sequential Logic Circuits 14

 What is the normal resting state of the NOR

latch inputs? What is the active state?
◦ LOW; HIGH

 When a latch is set, what are the states of Q?

◦ Q=1

 What is the only way to cause the Q output of

a NOR latch to change from 1 to 0?
◦ Make RESET=1

Sequential Logic Circuits 15

  Digital systems can operate
◦ Asynchronously: output can change state whenever inputs
change
◦ Synchronously: output only change state at clock transitions
(edges)

 Clock signal
◦ Outputs change state at the transition (edge) of the input clock
◦ Positive-going transitions (PGT): clock changes from 0 to 1
◦ Negative-going transitions (NGT): clock changes from 1 to 0

Sequential Logic Circuits 16

 Clocked FFs have a clock input that is

typically labeled CLK, CK, or CP.
◦ Normally use CLK
◦ In most clocked FFs, the CLK input is edge-
triggered, which means that it is activated by a
signal transition; this is indicated by the
presence of a small triangle on the CLK input.
 Clocked FFs also have one or more control
inputs that can have various names,
depending on their operation
 The control inputs get the FF outputs ready
to change, while the active transition at the
CLK input actually triggers the change.
◦ The control inputs control the WHAT (i.e., what
state the output will go to); the CLK input
determines the WHEN.

Sequential Logic Circuits 17

 The S and R inputs control the state of
the FF in the same manner as the NOR
gate latch, but the FF does not respond
to these inputs until the occurrence of
the PGT of the clock signal.

Sequential Logic Circuits 18

J=K=1 condition does not

result in an ambiguous output
as S-C FF.
This condition is toggle mode

Sequential Logic Circuits 19

  True or false: A J-K flip-flop can be used as
an S-R flip-flop, but an S-R flip-flop cannot
be used as a J-K flip-flop.
◦ True
 Does a J-K flip-flop have any ambiguous
input conditions?
◦ No
 What J-K input condition will always set Q
upon the occurrence of the active CLK
transition?
◦ J-1 K=0

Sequential Logic Circuits 20

Q will go to the same state

that is present on the D input
when a PGT occurs at CLK

Sequential Logic Circuits 21

 Implement an edge-triggered D FF from a S-C FF?

Sequential Logic Circuits 22

Parallel transfer of binary data

using D flip-flops

Sequential Logic Circuits 23

Sequential Logic Circuits 24

 True or false: A D latch is in its transparent

mode when EN=0
◦ False

 True or false: In a D latch, the D input can

affect Q only when EN=1.
◦ True

Sequential Logic Circuits 25

  The S, C, J, K, and D inputs is called synchronous
inputs because their effects on the output are
synchronized with the CLK input
◦ the synchronous control inputs must be used in
conjunction with a clock signal to trigger the FF
 Asynchronous inputs (override inputs) operate
independently of the synchronous inputs and clock
and can be used to set the FF to 1/0 states at any
time
◦ the asynchronous inputs are override inputs, which can be
used to override all the other inputs in order to place the FF
in one state or the other

Clocked J-K flip-flop

with asynchronous inputs

Sequential Logic Circuits 26

Sequential Logic Circuits 27

  How does the operation of an asynchronous
input differ from that of a synchronous input?
◦ Asynchronous inputs work independently of the CLK
input.

 Can a D flip-flop respond to its D and CLK

inputs while PRE=1?
◦ Yes, because PRE is active-LOW

 List the conditions necessary for a positive-

edge-triggered J-K flip-flop with active-LOW
asynchronous inputs to toggle to its opposite
state.
◦ J=K=1, PRE=CLR=1 and a PGT at CLK

Sequential Logic Circuits 28

 Counting, storing of binary data, transferring

binary data, and many more …
 Many applications fall into the category of
sequential circuits, in which the outputs follow
a predetermined sequence of states, with a new
state occurring each time a clock pulse occurs.

Sequential Logic Circuits 29

  A FF can be used to synchronize the effect of an
asynchronous input whose randomness can produce
the unpredictable and undesirable results in digital
systems

Asynchronous signal A can produce partial pulses at X

Sequential Logic Circuits 30

An edge-triggered D FF is
used to synchronize the
enabling of the AND gate
to the NGTs of the clock

Sequential Logic Circuits 31

  In many situations an output is to be activated only when
the inputs are activated in a certain sequence.
◦ This can not be accomplished using pure combinational logic,
but FFs can do it
 An AND gate can be used to determine when two inputs A
and B are both HIGH, but its output will respond the same
regardless of which input goes HIGH first. But suppose
that we want to generate a HIGH output only if A goes
HIGH and then B goes HIGH some time later.

Sequential Logic Circuits 32

 Registers are groups of FFs used to store data.

 Synchronous transfer
◦ The logic value that is currently stored in FF A is
transferred to FF B upon the NGT of the TRANSFER
pulse.
◦ Thus, after this NGT, the B output will be the same as
the A output

Sequential Logic Circuits 33

  Asynchronous transfer

Sequential Logic Circuits 34

 Data transfer from

one register to
another using D FFs

Sequential Logic Circuits 35

  True or false: Asynchronous data transfer uses the CLK input.
◦ False

 Which type of FF is best suited for synchronous transfer because

it requires the fewest interconnections from one FF to the other?
◦ D FF

 If JK flip-flops were used in the registers of the slide 38, how

many total interconnections would be required from register X
to register Y ?
◦ 6

 True or false: Synchronous data transfer requires less circuitry

than asynchronous transfer
◦ True

Sequential Logic Circuits 36

 A shift register is a group of FFs arranged so that the

binary numbers stored in FFs are shifted from one FF to
the next for every clock pulse

The FFs are connected so that

the output of X3 transfers into
X2, X2 into X1, and X1 into X0.
Upon the occurrence of the NGT
of a shift pulse, each FF takes
on the value stored previously in
the FF on its left

Sequential Logic Circuits 37

  Serial transfer of information (from X register
into Y register)

Sequential Logic Circuits 38

 True or false: The fastest method for transferring data from one
register to another is parallel transfer.
◦ True

 What is the major advantage of serial transfer over parallel

transfer?
◦ Fewer interconnections between registers

 Refer to Figure on the slide 41. Assume that the initial contents
of the registers are . Also assume that the D input of is held
HIGH. Determine the value of each FF output after the
occurrence of the fourth shift pulse.
◦ X2X1X0 = 111 Y2Y1Y0 = 101

 In which form of data transfer does the source of the data not
lose its data?
◦ Parallel

Sequential Logic Circuits 39

 JK FFs wired as a 3-bit binary
counter (MOD-8)
◦ FF Q0 toggles on the NGT of
each input clock pulse. Thus,
the Q0 output waveform has a
frequency that is exactly one
half of the clock pulse frequency
◦ FF Q1 toggles each time the
output goes from HIGH to LOW.
The Q1 waveform has a
frequency equal to exactly one-
half the frequency of the Q0
output and therefore one-fourth
of the clock frequency
◦ FF Q2 toggles each time the
output goes from HIGH to LOW.
Thus, the Q2 waveform has one-
half the frequency of Q1 and
therefore one-eighth of the
clock frequency

Sequential Logic Circuits 40

State transition diagram shows how the states of the counter

FFs change with each applied clock pulse.

Sequential Logic Circuits 41

  MOD number indicates the number of states
in the counting sequence.
◦ Counter in slide 40 has 8 different states (000
through 111), so it is Mod-8 counter
◦ In general, if N flip-flops are connected in the
arrangement of slide 43, the counter will have 2N
different states, and so it is a MOD-2N counter
 The MOD number of a counter also indicates
the frequency division obtained from the last
FF.

Sequential Logic Circuits 42

 Consider a counter circuit that contains six FFs wired in the

arrangement of slide 43 (i.e. Q5Q4Q3Q2Q1Q0)
◦ Determine the counter’s MOD number.
 26 = 64
◦ Determine the frequency at the output of the last FF (Q5) when the input clock
frequency is 1 MHz.
 1MHz/64 = 15.625KHz
◦ What is the range of counting states for this counter?
 000000 through 111111 (i.e., 0 to 63)
◦ Assume a starting state (count) of 000000. What will be the counter’s state after
129 pulses
 000001 state
 A 20-kHz clock signal is applied to a JK flip-flop with J=K=1. What is
the frequency of the FF output waveform?
◦ 20KHz/2 = 10KHz
 How many FFs are required for a counter that will count 0 to 255?
◦ 255 = 28-1, so 8 FF are required
 What is the MOD number of the counter in question 3?
◦ MOD-256
 What is the frequency of the output of the eighth FF when the input
clock frequency is 512 kHz?
◦ 512KHz/(28) = 2KHz

Sequential Logic Circuits 43

 1. With a memory characteristics, a flip-flop’s
outputs will go to a new state in response to
an input pulse and will remain in that new
state after the input pulse is terminated.
2. A NAND latch and a NOR latch are simple FFs
that respond to the logic levels on their SET
and CLEAR inputs.
3. Clearing (resetting) a FF means that its output
ends up in the Q=0/Q’=1 state. Setting a FF
means that it ends up in the Q=1/Q’=0 state.
4. Clocked FFs are edge-triggered, meaning that
it triggers the FF on a positive-going transition
(PGT) or a negative-going transition (NGT)

Sequential Logic Circuits 44

5. Edge-triggered (clocked) FFs can be triggered

to a new state by the active edge of the clock
input according to the state of the FF’s
synchronous control inputs (S, C or J, K or D)
6. Most clocked FFs have asynchronous inputs
that can set or clear the FF independently of
the clock input.
7. D latch is a modified NAND latch that operates
like a D FF except that it is not edge-triggered.
8. Some of FF applications include data storage
and transfer, data shifting ,counting, and
frequency division.

Sequential Logic Circuits 45

 Dinh Duc Anh Vu
International University – VNU HCM

 Understand the operation and characteristics of

synchronous and asynchronous counters.
 Construct counters with MOD numbers less than 2N.
 Construct both up and down counters.
 Connect multistage counters.
 Analyze and evaluate various types of counters.
 Design arbitrary-sequence synchronous counters.
 Understand several types of schemes used to
decode different types of counters.
 Compare the major differences between ring and
Johnson counters.
 Recognize and understand the operation of various
types of IC registers.

Counters and Registers 2

  Counter is a sequential logic circuit with:
◦ The input is Clock used to count.
◦ The output displays the numbers in the specified
order.
◦ After K Clock signals, the counter returns the
beginning state.
 The counter is designed by FFs and
combinational logic circuit.
◦ Serial counter (asynchronous counter)
◦ Parallel counter (synchronous counter)

Counters and Registers 3

 An asynchronous (ripple) counter

◦ is a counter in which all FFs are controlled by different synchronous
signal
◦ The output of the previous FF is the synchronous signals for the next FF
◦ The unstable intermediate state can be appeared when states change
 Principles:
◦ N JK FFs  design an up-counter MOD 2N
◦ Clock signal is excited at pin “CLK” of the first FF.
◦ The output of the previous FF is the clock signal at pin “CLK” of the next
FF. Continue to the last FF.
◦ Pins “J” and “K” of all FFs are set at logic 1.
◦ Pins “Clear” and “Preset” are not used (they are always not active).
 Don’t mention them in the circuit diagram to make the circuit clear.

Counters and Registers 4

Counters and Registers 5

 The counter in the previous slide starts off in the 0000 state, and then
clock pulses are applied. Some time later the clock pulses are removed,
and the counter FFs read 0011. How many clock pulses have occurred?
◦ 16n+3 (n: integer)

 A counter must be able to count as many as one thousand items. How

many FFs are required?
◦ to determine what value of N is needed so that 2N>=1000, so 10 FFs are used

 Clock signal for digital clock: The 60-Hz square wave is put into a
MOD-60 counter, which is used to divide the 60Hz frequency by
exactly 60 to produce a 1Hz waveform. This 1Hz waveform is fed to a
series of counters, which then count seconds, minutes, hours, and so
on. How many FFs are required for the MOD-60 counter?
◦ 6

Counters and Registers 6

  A synchronous (parallel) counter:
◦ is a counter in which all FFs are controlled by only one
synchronous signal, the input is clock.
◦ The output’s state changes only if the synchronous
signal is excited.
◦ The interval between two synchronous signals is set
so that the output’s state is stable before changing.
 Principle:
◦ To design a synchronous counter, pins “Clear” and
“Preset” are not used (they are always not active).
 Don’t mention them in the circuit diagram to make the
circuit clear.
◦ In this counter, the output Q’s changes depend on the
inputs J, K or D.

Counters and Registers 7

 The CLK inputs of all of the FFs are connected together so that
the input clock signal is applied to each FF simultaneously.
 Only flip-flop A, the LSB, has its J and K inputs permanently at
the HIGH level. The J, K inputs of the other FFs are driven by
some combination of FF outputs.
 The synchronous counter requires more circuitry than does the
asynchronous counter.

Counters and Registers 8

  Each FF should have its J and K inputs connected so that
they are HIGH only when the outputs of all lower-order FFs
are in the HIGH state

 The counting sequence shows that the A flip-flop must

change states at each NGT. For this reason, its J and K
inputs are permanently HIGH so that it will toggle on each
NGT of the clock input.
 The counting sequence shows that flip-flop B must change
states on each NGT that occurs while A =1. For example,
when the count is 0001, the next NGT must toggle B to the
1 state. This operation is accomplished by connecting
output A to the J and K inputs of flip-flop B so that J=K=1
only when A=1.
 The counting sequence shows that flip-flop C must change
states on each NGT that occurs while A=B=1. For example,
when the count is 0011, the next NGT must toggle C to the
1 state. By connecting the logic signal AB to FF C’s J and K
inputs, this FF will toggle only when A=B=1.
 In a like manner, we can see that flip-flop D must toggle
on each NGT that occurs while A=B=C=1. When the count
is 0111, the next NGT must toggle D to the 1 state. By
connecting the logic signal ABC to FF D’s J and K inputs,
this FF will toggle only when A=B=C=1.

Counters and Registers 9

 Actual ICs
◦ 74ALS160/162, 74HC160/162: Synchronous
decade counters
◦ 74ALS161/163, 74HC161/163: Synchronous
MOD-16 counters

Counters and Registers 10

  What is the advantage of a synchronous counter
over an asynchronous counter? What is the
disadvantage?
◦ can operate at higher clock frequencies and has more
complex circuitry

 How many logic devices are required for a

MOD-64 parallel counter?
◦ 6 FFs and 4 AND gates

 What logic signal drives the J,K inputs of the

MSB flip-flop for the counter of the above
question?
◦ ABCDE

Counters and Registers 11

 Design an MOD-K
up-counter, K<2N is
the same way that in
MOD 2N in which
pins “CLR” are used
to reset the counter
to the beginning
state.
◦ E.g. MOD-6 counter
produced by clearing
a MOD-8 counter
when a count of 6
occurs.

Counters and Registers 12

  If we assume a starting count of 000, the diagram shows that
the states of the counter change normally up until the count of
101.
 When the next clock pulse occurs, the counter temporarily goes
to the 110 count before going to the stable 000 count. The
dotted lines indicate the temporary nature of the 110 state. As
stated earlier, the duration of this temporary state is so short
that for most purposes we can consider that the counter goes
directly from 101 to 000 (solid arrow).

Counters and Registers 13

 Each FF output is connected to an INVERTER

whose output provides the current path for the
LED.
◦ For example, when output C
is HIGH, the INVERTER output
goes LOW and the LED turns
ON. An LED that is turned
on indicates C=1.
◦ When output C is LOW,
the INVERTER output is
HIGH and the LED turns OFF.
When the LED is turned off,
it indicates C=0

Counters and Registers 14

  What will be the status of the LEDs when the
counter is holding the count of five?
◦ 1012 : ON, OFF, ON

 What will the LEDs display as the counter is

clocked by a 1KHz input?
◦ At 1 KHz, the LEDs will be switching ON and OFF so
rapidly that they will appear to the human eye to be
ON all the time at about half the normal brightness.

 Will the 110 state be visible on the LEDs?

◦ No.

Counters and Registers 15

 To construct a counter that starts counting

from all 0s and has a MOD number of K:
1. Find the smallest number of FFs such that 2N ≥
K and connect them as a counter. If 2N = K,
donot do steps 2 and 3
2. Connect a NAND gate to the asynchronous
CLEAR inputs of all the FFs
3. Determine which FFs will be in the HIGH state at
a count = K; then connect the normal outputs of
these FFs to the NAND gate inputs

Counters and Registers 16

  Construct MOD-10 counter that will count from 0000
through 1001

Counters and Registers 17

 Determine the MOD number of this counter

Counters and Registers 18

  Construct a MOD-60 counter

Counters and Registers 19

 What FF outputs should be connected to the

clearing NAND gate to form a MOD-13 counter?
◦ D, C, and A

 True of False: All BCD counters are decade

counters.
◦ True

 What is the output frequency of a decade

counter that is clocked from a 50-KHz signal?
◦ 5 KHz

Counters and Registers 20

  A synchronous down counter is constructed in a similar manner except
that we use the inverted FF outputs to control the higher-order J, K
inputs.
 Synchronous, MOD-16, down counter

Counters and Registers

Counters and Registers 22

  Counter is preset on the active transition of
the same clock signal that is used for
counting
 Examples of IC counters that use
synchronous presetting
◦ 74ALS160, 74ALS161, 74ALS162, 74ALS163
◦ 74HC160, 74HC161, 74HC162, 74HC163
 Examples of IC counters that use
asynchronous presetting
◦ 74ALS190, 74ALS191, 74ALS192, 74ALS193
◦ 74HC190, 74HC191, 74HC192, 74HC193

Counters and Registers 23

 What is meant when we say that a counter is

presettable?
◦ It can be preset to any desired starting count.

 Describe the difference between

asynchronous and synchronous presetting.
◦ Asynchronous presetting is independent of the
clock input, while synchronous presetting occurs
on the active edge of the clock signal.

Counters and Registers 24

  IC counters that use synchronous presetting
◦ 74ALS160, 74ALS161, 74ALS162, 74ALS163
◦ 74HC160, 74HC161, 74HC162, 74HC163

 IC counters that use asynchronous presetting

◦ 74ALS190, 74ALS191, 74ALS192, 74ALS193
◦ 74HC190, 74HC191, 74HC192, 74HC193

74xx series: Standard TTL (Transistor-Transistor Logic)

ALS: Advanced Low-Power Schottky technology
HC: High-speed CMOS technology

Counters and Registers 25

 74ALS160 and 74ALS162:

MOD-10 counters
 74ALS161 and 74ALS163:
MOD-16 counters
 74ALS160 and 74ALS161 has
an asynchronous clear input
 74ALS162 and 74ALS163: IC
counters are synchronously
cleared
 The clear input has priority
over all other functions
 The second priority function
available in this IC series is
the parallel loading of data
into the counter’s flip-flops
 RCO output is used in
connecting two or more
counter chips together in a
multistage arrangement to
create larger counters

Counters and Registers 26

  The parallel data inputs are permanently
connected as 1100.
 Assume the counter is initially in the 0000
state

Counters and Registers 27

 The parallel data inputs are permanently

connected as 0111.
 Assume the counter is initially in the 0000
state

Counters and Registers 28

  Both chips are up/down counters and have an asynchronous, active-LOW load
input
 74ALS190: MOD-10 counter
 74ALS191: MOD-16 counter
 The LOAD input has priority over counting functions. As soon as LOAD goes
LOW, the counter will be preset to the parallel data on the D, C, B, A (A is LSB
and D is MSB) input pins
 RCO output is used in connecting two or more counter chips together in a
multistage arrangement to create larger counters

Counters and Registers 29

Counters and Registers 30

  Compare the operation of two counters, one with synchronous
load and the other with asynchronous load.
◦ (a) Determine the output waveform for each counter.
◦ (b) What is the recycling count sequence and modulus for each counter?
◦ (c) Why do they have different count sequences?

Counters and Registers 31

(a) Determine the output waveform for each counter.

(b) What is the recycling count sequence and modulus for each counter?
(c) Why do they have different count sequences?

Counters and Registers 32

  Many standard IC counters have been designed to make it easy to
connect multiple chips together to create circuits with a higher
counting range.
 These previous counter chips can be simply connected in a multistage
or cascading arrangement
 two 74ALS163s are connected in a two-stage counter arrangement that
produces a recycling, binary sequence from 0 to 255 for a maximum
modulus of 256

Counters and Registers 33

 Describe the function of the inputs LOAD and D, C, B, A.

◦ LOAD is the control that enables the parallel loading of the data inputs D C B A
(A: LSB).

 Describe the function of the CLR input.

◦ CLR is the control that enables the resetting of the counter to 0000.

 True or false: The 74HC161 cannot be preset while CLR is active.

◦ True

 What logic levels must be present on the control inputs in order for the
74ALS162 to count pulses that appear on the CLK?
◦ All control inputs (CLR, LOAD, ENT, and ENP) on the 74162 must be HIGH.

 What logic levels must be present on the control inputs in order for the
74HC190 to count down with pulses that appear on the CLK?
◦ LOAD=1, CTEN=0, and D/U=1 to count down.

 What would be the maximum counting range for a four-stage counter

made up of 74HC163 ICs? What is the maximum counting range for
74ALS190 ICs?
◦ 74HC163: 0 to 65,535; 74ALS190: 0 to 9999 or 9999 to 0

Counters and Registers 34

  One of the simplest means for displaying the
contents of a counter involves just connecting
the output of each FF to a small indicator LED
 Mentally decoding the binary states of the LEDs
◦ Becomes inconvenient as the size of the counter
increases
 Electronically decoding
◦ To control the timing or sequencing of operations
automatically without human intervention.
◦ Active-High Decoding
◦ Active-Low Decoding
◦ BCD counter decoding

Counters and Registers 35

 A decoding network is a logic circuit that generates X different outputs,

each of which detects (decodes) the presence of one particular state of
the counter.
 The decoder outputs can be designed to produce either a HIGH level
when the detection occurs
 Each AND gate produces a
HIGH output for one
particular state of the
counter.
 How many AND gates are
required to decode
completely all of the
states of a MOD-32 binary
counter? What are the
inputs to the gate that
decodes for the count of
21?
◦ The decoder requires 32
AND gates. Each gate will
have five inputs, one
from each FF.

Counters and Registers 36

Counters and Registers 37

Counters and Registers 38

  How many gates are needed to decode a six-
bit counter fully?
◦ 64
 Describe the decoding gate needed to
produce a LOW output when a MOD-64
counter is at the counter of 23.
◦ 23 = 010111
◦ 6-input NAND gate with inputs 𝐹𝐸𝐷𝐶𝐵𝐴

Counters and Registers 39

Flip-flop Flip-flop Characteristic Characteristic Excitation

name symbol table equation table

S R Q(next) Q Q(next) S R
S Q 0 0 Q Q(next)=S+R’Q 0 0 0 X
SR Clk 0 1 0 0 1 1 0
SR=0
R Q’ 1 0 1 1 0 0 1
1 1 NA 1 1 X 0

J K Q(next) Q Q(next) J K
J Q
0 0 Q 0 0 0 X
JK Clk 0 1 1 X
0 1 0 Q(next)=JQ’+K’Q
K Q’ 1 0 1 1 0 X 1
1 1 Q’ 1 1 X 0

Q Q(next) D
D Q
D Q(next)
0 0 0
D Clk
Q(next)=D
0 0 0 1 1
Q’
1 1 1 0 0
1 1 1

T Q T Q(next)
Q(next)=TQ’+T’Q Q Q(next) T
T Clk 0 Q 0 0 0
Q’ 1 Q’ 0 1 1
1 0 1
1 1 0

Counters and Registers 40

 Q Q
Present Next S R J K D T
state state
0 0 0 X 0 X 0 0
0 1 1 0 1 X 1 1
1 0 0 1 X 1 0 1
1 1 X 0 X 0 1 0

Counters and Registers 41

 To analyze a synchronous counter design by

predicting the FF control inputs for each state of the
counter.
 A state transition table is a very useful tool in this
analysis process.
 Procedure
1. Write the logic expression for each FF control input.
2. Assume a PRESENT state for the counter and apply that
combination of bits to the control logic expressions.
3. The outputs from the control expressions will allow us to
predict the commands to each FF and the resulting NEXT
state for the counter after clocking.
4. Repeat the analysis process until the entire count
sequence is determined.

Counters and Registers 42

  Control input expressions
◦ 𝐽𝐶 = 𝐴𝐵 𝐾𝐶 = 𝐶
◦ 𝐽𝐵 = 𝐴 𝐾𝐵 = 𝐶
◦ 𝐽𝐴 = 𝐶 𝐾𝐴 = 𝐶
 Assume that the PRESENT state for the counter is
CBA=000.
 Applying this combination to the control expressions
above will yield JC KC=0 0, JB KB =0 0, and JA KA =1 1.
These control inputs will tell FFs C and B to hold and FF A
to toggle on the next NGT on CLK.
 Our predicted NEXT state is 001 for CBA.

Counters and Registers 43

 Continuing with this

process will result in a
recycling count
sequence of 000, 001,
010, 011, 100, 000.
◦ MOD-5 counter

 Self-correcting counter
is one in which
normally unused states
will all somehow return
to the normal count
sequence.
Counters and Registers 44
 Counters and Registers 45

Transition table of the circuit

JC=BA KC=B’ JB=C’A KB=CA JA=C’ KA=C’+B
PR C B A JC KC JB KB JA KA C+ B+ A+ N

0 0 0 0 0 1 0 0 1 1 0 0 1 1
1 0 0 1 0 1 1 1 1 1 0 1 0 2
2 0 1 0 0 0 0 0 1 1 0 1 1 3
3 0 1 1 1 0 1 1 1 1 1 0 0 4
4 1 0 0 0 1 0 1 0 0 0 0 0 0
5 1 0 1 0 1 0 0 0 0 0 0 1 1
6 1 1 0 0 0 0 1 0 1 1 0 0 4
7 1 1 1 1 0 0 0 0 1 1 1 0 6

1→2 →3 →4 →0 →1….
Counters and Registers 46
Counters and Registers 52

 Why is it desirable to avoid having asynchronous controls

on counters?
◦ We will not have to deal with transient states and possible
glitches in output waveforms.

 What tool is useful in the analysis of synchronous

counters?
◦ State transition table

 What determines the count sequence for a counter circuit?

◦ The gates control the count sequence.

 What counter characteristic is described by saying that it is

self-correcting?
◦ Unused states all lead back to the count sequence of the counter

Counters and Registers 53

  Design a custom counter that follows a sequence that is
not a regular binary count pattern, e.g., 000, 010, 101,
001, 110, 000…
 The following steps are applied to design a synchronous
counter:
◦ Step 1: Define the number of FFs used. It is defined by the
number of bits used to express the maximum number in the
counter.
◦ Step 2: Draw the count diagram including states outside the
count circle.
◦ Step 3: Based on the diagram in Step 2, display the states
transitions between the present state and next state, then fill in
the state transition table.
◦ Step 4: Define the combinational functions connected to pins J, K
or D of FFs.
◦ Step 5: Simplify the combinational functions using K-map.
◦ Step 6: Draw the circuit diagram.

Counters and Registers 54

 Design a synchronous counter, count from 0

to 4, using JK FFs

 Step 1: 3 FFs are used.

 Step 2: the count circle consists
of 5 states, 3 states outside
the count circle.
◦ Link the states outside the count
circle to any state in the count
circle.

Counters and Registers 55

  Step 3: Draw the state transition table from
the state transition diagram

Counters and Registers 56

 Step 4: Define the combinational functions

connected to pins J,K

Counters and Registers 57

  Step 5: Simplify JC , KC , JB , KB , JA , KA using
K-map

Counters and Registers 58

 Step 6: Implement the final circuit diagram

𝐽𝐴 = 𝐶
𝐾𝐴 = 1
𝐽𝐵 = 𝐴𝐶
𝐾𝐵 = 𝐴 + 𝐶
𝐽𝐶 = 𝐴𝐵
𝐾𝐶 = 1

Counters and Registers 59

  Design a synchronous counter, count from 0
to 4, using D FFs
 Step 1, 2, 3 are similar to the previous
example
 Step 4:

Counters and Registers 60

 Step 5:

 Step 6:

Counters and Registers 61

  Design a synchronous counter, count from 0
to 5 using
◦ JK FFs.
◦ D FFs

Counters and Registers 62

 List the six steps in the procedure for designing a

synchronous counter
◦ See the slide 53.

 What information is contained in a state transition table?

◦ It associates every possible PRESENT state with its desired NEXT
state.

 What information is contained in the circuit excitation

table?
◦ It shows the necessary levels at each flip-flop’s synchronous
input to produce the counter’s state transitions

 True or false:The synchronous counter design procedure

can be used for the following sequence: 0010, 0011,
0100, 0111, 1010, 1110, 1111, and repeat.
◦ True

Counters and Registers 63

  One FF can save 1 data bit  a register
comprised by n FFs is used to save n data bits.
 A register can shift data to left or right when the
clock pulse is excited.
 The various types of registers can be classified
according to the manner in which data can be
entered into the register for storage and the
manner in which data are outputted from the
register:
◦ Serial input - serial output register (SISO).
◦ Serial input - parallel output register (SIPO): 74LS164.
◦ Parallel input - serial output register (PISO): 74LS165 .
◦ Parallel input - parallel output register (PIPO):
74LS174

Counters and Registers 64

Counters and Registers 65

  Show how to connect the 74ALS174 so that it
operates as a serial shift register with data shifting
on each PGT of CP as follows: Serial input → Q5 →
Q4 → Q3 → Q2 → Q1 → Q0. In other words, serial
data will enter at D5 and will output at Q0.

 How would you

connect two
74ALS174s to
operate as a 12-bit
shift register?

Counters and Registers 66

Counters and Registers 67

Counters and Registers 68

 Eight-bit parallel in/serial out

register
 It actually has serial data entry
via DS and asynchronous
parallel data entry via P0
through P7
 CP is the clock input used for
the shifting operation.
◦ The clock inhibit input, CP INH is
used to inhibit the effect of the CP
input.
 The shift/load input, controls
which operation is taking
place—shifting or parallel
loading.
 Only accessible FF outputs are
Q7

Counters and Registers 69

  DS=0 and CP INH = 0

Counters and Registers 70

 Eight bit serial in/parallel out

shift register with each FF output
externally accessible.
 An AND gate combines inputs A and B
to produce the serial input to flip-flop Q0
 The shift operation occurs on the PGTs of the clock input
CP.
 The input provides asynchronous resetting of all FFs on a
LOW level

Counters and Registers 71

  Assume that the initial contents of the 74ALS164 register
are 00000000
 Determine the sequence of states as clock pulses are
applied

Counters and Registers 72

 What kind of register can have a complete binary number loaded into it
in one operation, and then have it shifted out one bit at a time?
◦ Parallel in/serial out
 True or false: A serial in/parallel out register can have all of its bits
displayed at one time.
◦ True
 What type of register can have data entered into it only one bit at a
time, but has all data bits available as outputs?
◦ Serial in/parallel out
 In what type of register do we store data one bit at a time and have
access to only one output bit at a time?
◦ Serial in/serial out
 How does the parallel data entry differ for the 74165 and the 74174?
◦ The 74165 uses asynchronous parallel data transfer; the 74174 uses synchronous
parallel data transfer.
 How does the CP INH input of the 74ALS165 work?
◦ A HIGH prevents shifting on CPs

Counters and Registers 73

  In asynchronous (ripple) counters, the clock signal is applied to the LSB
FF, and all other FFs are clocked by the output of the preceding FF.
 A counter’s MOD number is the number of stable states in its counting
cycle; it is also the maximum frequency-division ratio.
 The normal (maximum) MOD number of a counter is 2N. One way to
modify a counter’s MOD number is to add circuitry that will cause it to
recycle before it reaches its normal last count.
 Counters can be cascaded (chained together) to produce greater
counting ranges and frequency-division ratios.
 In a synchronous (parallel) counter, all of the FFs are simultaneously
clocked from the input clock signal.
 The maximum clock frequency for an asynchronous counter, fmax,
decreases as the number of bits increases. For a synchronous counter,
fmax remains the same, regardless of the number of bits.
 A decade counter is any MOD-10 counter. A BCD counter is a decade
counter that sequences through the 10 BCD codes (0–9).
 A presettable counter can be loaded with any desired starting count.

Counters and Registers 79

 An up/down counter can be commanded to count up or count down.

 Logic gates can be used to decode (detect) any or all states of a
counter.
 The count sequence for a synchronous counter can be easily
determined by using a PRESENT state/NEXT state table that lists all
possible states, the flip-flop input control information, and the
resulting NEXT states.
 Synchronous counters with arbitrary counting sequences can be
implemented by following a standard design procedure.
 Numerous IC registers are available and can be classified according to
whether their inputs are parallel (all bits entered simultaneously), serial
(one bit at a time), or both. Likewise, registers can have outputs that
are parallel (all bits available simultaneously) or serial (one bit available
at a time).
 A sequential logic system uses FFs, counters, and registers, along with
logic gates. Its outputs and sequence of operations depend on present
and past inputs.
 A ring counter is actually an N-bit shift register that recirculates a
single 1 continuously, thereby acting as a MOD-N counter. A Johnson
counter is a modified ring counter that operates as MOD-2N counter

Counters and Registers 80