P.S.R.

ENGINEERING COLLEGE
(An Autonomous Institution, Affiliated to Anna University, Chennai)
Sevalpatti (P.O), Sivakasi - 626140.
Tamilnadu State

LECTURE NOTES

191EE54
Digital Logic
Circuits

PREPARED BY

Mr.T.Balasubramanian ,AP/EEE

DEPARTMENT OF ELECTRICAL AND

ELECTRONICS ENGINEERING

Page 1
 Program Outcomes
The Program Outcomes of B.E in Electrical and Electronics Engineering are:

PO1. Apply knowledge of mathematics, physical sciences and Electrical and Electronics
Engineering fundamentals.

PO2. Able to identify, formulate, analyze and solve Electrical and Electronics Engineering
problems.

PO3. Able to design and realize Electrical and Electronics systems to meet desired needs within
practical constraints such as economical, environmental, social, political, ethical, health
and safety, manufacturability and sustainability.
PO4. Able to investigate and conduct experiments, as well as to analyze and interpret data.

PO5. Use of techniques, skills, and modern engineering tools necessary for engineering practice

PO6. Contextual knowledge to assess societal, health, safety, legal and cultural issues related to
Engineering.
PO7. Realize the impact of Electrical Engineering solutions in a global, economic and
environmental context.

PO8. Apply ethical principles and commitment to professional ethics and responsibility.
PO9. Function as an individual and as a member or leader in multidisciplinary teams.

PO10. Communicate effectively with the engineering community and society at large.

PO11. Knowledge and understanding of management and business practices and their
limitations.
PO12. Recognize the need for, and have the ability to engage in life-long learning.

Program Specific Outcomes

Engineering Graduates will be able to:
PSO1. Skilled to analyze, design and test various electrical and electronic circuits, control
systems, instrumentation systems, computer systems, microprocessor and
microcontroller based systems.
PSO2. Exhibit knowledge and hands-on competence in the application of Electrical machines
and Power Electronics based drives systems.
PSO3. Design and investigate problems in power system network along with protection
schemes and effective utilization of electrical energy.
PSO4. Develop a project management tool for solving complex electrical / electronic
problems by applying the knowledge of basic sciences, mathematics and engineering
fundamentals.

Page 2
UG Regulations 2019 P.S.R. Engineering College

191EE54 DIGITAL LOGIC CIRCUITS L-T-P C

3-0-0 3
Programme: B.E –Electrical and Electronics Engineering Sem: V Category: PC
Pre-requisites: Engineering physics
To learn the basic methods for the design of digital circuits and provide the
AIM:
fundamental concepts used in the design of digital systems.
Pre-requisite: Analog Electronic Circuits
Course Outcomes:
The Students will be able to
CO1. Represent the common forms of number system in digital electronic circuits and conversion
between them.
CO2. Design the different types of Combinational Circuits.
CO3. Develop the synchronous sequential circuits.
CO4. Design of Asynchronous sequential circuits.
CO5. Summarize the Special Characteristics of digital integrated circuits.
CO6. Design and analyze circuits with Programmable Logic Devices.

NUMBER SYSTEM & BOOLEAN ALGEBRA 9

Review of number system; types and conversion, codes. Boolean algebra: De-Morgan’s theorem,
switching functions and simplification using K-maps & Quine McCluskey method.

COMBINATIONAL CIRCUITS 9
Design of Logic gates. Design of adder, subtractor, comparators, code converters, encoders, decoders,
multiplexers and demultiplexers. Function realization using gates & multiplexers.

SYNCHRONOUS SEQUENTIAL CIRCUITS 9

Flip flops - SR, D, JK and T. Design of synchronous sequential circuits – Synchronous counters,
Sequence generator and detector with the support of state diagram; state reduction; state assignment.
Analysis of synchronous sequential circuits.

ASYNCHRONOUS SEQUENCTIAL CIRCUIT 9

Design of fundamental mode and pulse mode circuits – primitive state / flow table – Minimization of
primitive state table –state assignment – Excitation table – Excitation map- cycles – Races –Hazards:
Static –Dynamic –Essential –Hazards elimination.

PROGRAMMABLE LOGIC DEVICES, MEMORY AND LOGIC FAMILIES 9

Memories: ROM, PROM, PLA, PAL, and FPGA, digital logic families: TTL, ECL, and CMOS.

Total Periods 45
Text Books
1. M. Morris Mano, ‘Digital Logic and Computer Design’, Pearson Education, Inc., 2016.
2. John M.Yarbrough, ‘Digital Logic, Application & Design’, Cengage learning, 2006.
UG Regulations 2019 P.S.R. Engineering College

References
1. S. Salivahanan and S. Arivazhagan, ‘Digital Circuits and Design’, 4 thEdition, Vikas Publishing House
Pvt. Ltd, New Delhi, 2012.
2. Charles H.Roth. ‘Fundamentals of Logic Design’, Thomson Publication Company, 2015.
3. Donald P.Leach and Albert Paul Malvino, ‘Digital Principles and Applications’, 8th Edition, Tata
McGraw Hill Publishing Company Limited, New Delhi, 2014.
4. R.P.Jain, ‘Modern Digital Electronics’, 4thEdition, Tata McGraw–Hill publishing company limited,
New Delhi, 2009.
5. Thomas L. Floyd, ‘Digital Fundamentals’, Pearson Education, Inc., New Delhi, 2012.
6. Donald D.Givone, ‘Digital Principles and Design’, Tata McGraw-Hill Publishing company limited,
New Delhi, 2012.
7. NPTEL Course on ‘Digital Circuits’ by Santanu Chattopadhyay IIT Karagpur.

Program Specific
Course Program Outcomes (POs)
Outcomes (PSOs)
Outcomes
PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2 PSO3 PSO4

CO1 3 2 2 1 1 1 2 1 3 2 3
CO2 3 3 3 2 1 1 2 3 1 2
CO3 3 2 3 1 1 1 3 1
CO4 3 3 3 2 1 1 3 1
CO5 3 1 1 1 1 1 2 3 2 2
CO6 3 3 3 2 1 1 3 3 1 1 3
1: Slight (Low) 2: Moderate (Medium) 3: Substantial (High)
 Course Plan
191EE54 DIGITAL LOGIC CIRCUITS L-T-P C
3-0-0 3
Programme: B.E. Electrical and Electronics Engineering Sem: V Category: PC
Faculty Name Dr.R.Muniraj, Associate Professor,EEE Academic Year: 2023-24
To learn the basic methods for the design of digital circuits and provide the fundamental
AIM: concepts used in the design of digital systems.
Course Outcomes: The Students will be able to
CO1. Represent the common forms of number system in digital electronic circuits and conversion between
them.
CO2. Design the different types of Combinational Circuits.
CO3. Develop the synchronous sequential circuits.
CO4. Design of Asynchronous sequential circuits.
CO5. Summarize the Special Characteristics of digital integrated circuits.
CO6. Design and analyze circuits with Programmable Logic Devices.
COURSE CONTENTS
Comm. Ref
Unit Topics Hours
Hours Books
NUMBER SYSTEM & BOOLEAN ALGEBRA
Review of number system : Types and Conversion, Codes 1 1 T1
I Boolean algebra: De-Morgan’s theorem 2 3 T2
Switching functions and simplification using K-maps method 3 6 R1
Simplification using Quine McCluskey method 3 9 R5
COMBINATIONAL CIRCUITS
Design of Logic gates 1 10
Design of adder and subtractor 2 12 T1
II Design of comparators and code converters, 2 14 T2
Design of encoders and decoders 1 15 R1
Design of multiplexers and demultiplexers 2 17 R5
Function realization using gates & multiplexers. 1 18
SYNCHRONOUS SEQUENTIAL CIRCUITS
Flip flops - SR, D, JK and T 1 19 T1
III Design of synchronous sequential circuits – Synchronous counters 3 22 T2
Design of synchronous sequential circuits –Sequence generator and detector 3 25 R1
Analysis of synchronous sequential circuits 2 27 R5
ASYNCHRONOUS SEQUENTIAL CIRCUITS
Design of Asynchronous Sequential Circuits - fundamental mode 3 30
T1
Design of Asynchronous Sequential Circuits - pulse mode 3 33
IV T2
cycles – Races 1 34
R1
Hazards: Static –Dynamic –Essential 1 35
R4
Hazards elimination. 1 36
PROGRAMMABLE LOGIC DEVICES, MEMORY AND LOGIC FAMILIES
Memories: ROM, PROM 1 37
Memories: PLA, PAL 2 39 T1
V Memories: FPGA 1 40 T2
Digital logic families: TTL 2 42 R1
Digital logic families: ECL 1 43 R4
Digital logic families: CMOS. 2 45
TEXT BOOKS
1. M. Morris Mano, ‘Digital Logic and Computer Design’, Pearson Education, Inc., 2016.
2. John M.Yarbrough, ‘Digital Logic, Application & Design’, Cengage learning, 2006.
REFERENCE BOOKS
1. S. Salivahanan and S. Arivazhagan, ‘Digital Circuits and Design’, 4thEdition, Vikas Publishing House Pvt. Ltd, New
Delhi, 2012.
2. Charles H.Roth. ‘Fundamentals of Logic Design’, Thomson Publication Company, 2015.
3. Donald P.Leach and Albert Paul Malvino, ‘Digital Principles and Applications’, 8th Edition, Tata McGraw Hill
Publishing Company Limited, New Delhi, 2014.
4. R.P.Jain, ‘Modern Digital Electronics’, 4thEdition, Tata McGraw–Hill publishing company limited, New Delhi,
2009.
5. Thomas L. Floyd, ‘Digital Fundamentals’, Pearson Education, Inc., New Delhi, 2012.
6. Donald D.Givone, ‘Digital Principles and Design’, Tata McGraw-Hill Publishing company limited, New Delhi,
2012.
7. NPTEL Course on ‘Digital Circuits’ by Santanu Chattopadhyay IIT Karagpur.2010.

Content Delivery Methods

Conventional ICT Tools If Industrial visit
Items Chalk and Board/OHP (Video/Animation/PPT/Google planned fill out the
Class rooms) details
Total No. of hours planned 33 12 -
Program Specific
Course Program Outcomes (POs)
Outcomes (PSOs)
Outcomes PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2 PSO3 PSO4

CO1 3 2 2 1 1 1 2 1 3 2 3
CO2 3 3 3 2 1 1 2 3 1 2
CO3 3 2 3 1 1 1 3 1
CO4 3 3 3 2 1 1 3 1
CO5 3 1 1 1 1 1 2 3 2 2
CO6 3 3 3 2 1 1 3 3 1 1 3
Evaluation Continuous Assessment (30)
End Semester
Criteria & Assessment Assignment/Seminar/ Attendance Total Marks
Examination
Marks Test (60%) Mini Project (30%) (10%)
7 100
18 9 3
[Min Pass:35] [Min Pass:50]
Attendance
91% and above -10, 86-90%-8, 81-85-6, 76-80%-4, 75%-2, Below 75%-0
Mark
Grade Criteria O(90-100), A+(80-89), A(70-79), B+(60-69), B(50-59), RA(<50)-Fail

Website Referred:
https://onlinecourses.nptel.ac.in/noc22_ee110/preview
https://nptel.ac.in/courses/108105113

Faculty Incharge HoD/EEE

 NUMBER SYSTEM & BOOLEAN ALGEBRA
Numerical Presentation

In science, technology, business, and, in fact, most other fields of endeavor, we

are constantly dealing with quantities. Quantities are measured, monitored,
recorded, manipulated arithmetically, observed, or in some other way utilized in
most physical systems. It is important when dealing with various quantities that
we be able to represent their values efficiently and accurately. There are basically
two ways of representing the numerical value of quantities: analog and digital.

Analog Representation

In analog representation a quantity is represented by a voltage, current, or meter

movement that is proportional to the value of that quantity. Analog quantities
such as those cited above have an important characteristic: they can vary over a
continuous range of values. Below is a diagram of analog voltage vs time:

Digital Representation

In digital representation the quantities are represented not by proportional

quantities but by symbols called digits. As an example, consider the digital watch,
which provides the time of day in the form of decimal digits which represent
hours and minutes (and sometimes seconds). As we know, the time of day
changes continuously, but the digital watch reading does not change continuously;
rather, it changes in steps of one per minute (or per second). In other words, this
digital representation of the time of day changes in discrete steps, as compared
with the representation of time provided by an analog watch, where the dial
reading changes continuously. Below is a diagram of digital voltage vs. time:
 The major difference between analog and digital quantities, then, can be simply
stated as follows:

Analog = continuous
Digital = discrete (step by step)

Advantages and Limitations of Digital Techniques

Advantages

1. Easier to design. Exact values of voltage or current are not important, only the
range (HIGH or LOW) in which they fall.
2. Information storage is easy.
3. Accuracy and precision are greater.
4. Operation can be programmed. Analog systems can also be programmed, but the
variety and complexity of the available operations is severely limited.
5. Digital circuits are less affected by noise. As long as the noise is not large enough
to prevent us from distinguishing a HIGH from a LOW.
6. More digital circuitry can be fabricated on IC chips.

Limitations

There is really only one major drawback when using digital techniques:
The real world is mainly analog.
Most physical quantities are analog in nature, and it is these quantities that are
often the inputs and outputs that are being monitored, operated on, and controlled
by a system.

To take advantage of digital techniques when dealing with analog inputs and
outputs, three steps must be followed:

1. Convert the real-world analog inputs to digital form. (ADC)

2. Process (operate on) the digital information.
3. Convert the digital outputs back to real-world analog form. (DAC)
 The following diagram shows a temperature control system that requires
analog/digital conversions in order to allow the use of digital processing
techniques.

Number Systems

A number system specifies how values are represented. Human uses DECIMAL
Number System. There are ten digits in Decimal Number System:
0,1,2,3,4,5,6,7,8,9
Digital Computers use Binary Numbers, which have only two digits: 0,1
There are other number systems, including: Octal and Hexadecimal

Number System Terminology

In Number System, a value of an n-digit number a n-1a n-2…a1a 0 is:

N = a n-1 x r n-1 + a n-2 x r n-2 +…+ a 1 x r 1 + a 0 x r 0
where a n-1,a n-2,…,a1,a 0 are coefficients
r is called the Base or Radix
Decimal is Base-10 system, r = 10
Binary is Base-2 system, r = 2
Octal is Base-8 system, r = 8
Hexadecimal is Base-16 system, r = 16

Decimal Number System

The decimal system is composed of 10 numerals or symbols. These 10 symbols

are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9; using these symbols as digits of a number, we can
express any quantity. The decimal system, also called the base-10 system because
it has 10 digits. Values are represented by the digits and their positions in the
number and the type of number system is called Positional Number System
 103 102 101 100 10-1 10-2 10-3
=1000 =100 =10 =1 . =0.1 =0.01 =0.001
Most Least
Decimal
Significant Significant
point
Digit Digit

8973 is Eight Thousand Nine Hundred and Seventy Three:

8 = 8000 = 8 x 103 (Thousands Place)

9 = 900 = 9 x 102 (Hundreds Place)
7 = 70 = 7 x 101 (Tens Place)
3 = 3 = 3 x 100 (Units Place)

Binary Number System

An n-bit binary number a n-1a n-2…a1a 0 has a value:

N = a n-1 x 2 n-1 + a n-2 x 2 n-2 +…+ a 1 x 2 1 + a 0 x 2 0
This base-2 system can be used to represent any quantity that can be represented
in decimal or other number system.

23 22 21 20 2-1 2-2 2-3

=8 =4 =2 =1 . =1/2 =1/4 =1/8
Most Binary Least
Significant Bit point Significant Bit

e.g. A 4-bit binary number 10112 is:

N = 1 x 23 + 0 x 22 + 1 x 21 + 1 x 20
= 8 + 0 + 2 + 1 = 1110
e.g. A 6-bit binary number 1100102 is:
N = 1x25 + 1x24 + 0x23 + 0x22 + 1x21 + 0x20
= 32 + 16 + 0 + 0 + 2 = 5010

The Binary counting sequence is shown in the table:

Representing Binary Quantities

In digital systems the information that is being processed is usually presented in

binary form. Binary quantities can be represented by any device that has only two
operating states or possible conditions. Eg. a switch has only open or closed. We
arbitrarily (as we define them) let an open switch represent binary 0 and a closed
switch represent binary 1. Thus we can represent any binary number by using
series of switches.

Typical Voltage Assignment

Binary 1: Any voltage between 2V to 5V

Binary 0: Any voltage between 0V to 0.8V
Not used: Voltage between 0.8V to 2V, this may cause error in a digital circuit.
 We can see another significant difference between digital and analog systems. In
digital systems, the exact value of a voltage is not important; eg, a voltage of 3.6V
means the same as a voltage of 4.3V. In analog systems, the exact value of a
voltage is important.

Binary to Decimal Number Conversion

Binary numbers can be converted to Decimal numbers by using:

N = a n-1 x 2 n-1 + a n-2 x 2 n-2 +…+ a 1 x 2 1 + a 0 x 2 0

1 1 0 1 12 (binary)
24+23+0+21+20 = 16+8+0+2+1
= 2710 (decimal)

and

101101012 (binary)
27+0+25+24+0+22+0+20 = 128+0+32+16+0+4+0+1
= 18110 (decimal)

Decimal to Binary Number Conversion

Decimal numbers can be converted to binary numbers by dividing the decimal

number by 2 successively.

This method uses repeated division by 2. Ex. Convert 2510 to binary

25/ 2 = 12+ remainder of 1 1 (Least Significant Bit)

12/ 2 = 6 + remainder of 0 0
6/2 = 3 + remainder of 0 0
3/2 = 1 + remainder of 1 1
1/2 = 0 + remainder of 1 1 (Most Significant Bit)
Result 2510 = 1 1 0 0 12

The Flow chart for repeated-division method is as follow:

 e.g. 16810 = 101010002

Octal Number System

Octal Numbers are base 8

Octal has 8 digits: 0, 1, 2, 3, 4, 5, 6, 7
An n-bit octal number a n-1a n-2…a1a 0 has a decimal value:
a n-1 x 8 n-1 + a n-2 x 8 n-2 +…+ a 1 x 8 1 + a 0 x 8 0
83 82 81 80 8-1 8-2 8-3
=512 =64 =8 =1 . =1/8 =1/64 =1/512
 Most Least
Octal
Significant Significant
point
Digit Digit

The conversion of octal to decimal can be done with the above equation
e.g. 2638 = 2x82 + 6x81 + 3x80
= 128 + 48 + 3 = 17910

e.g 24.68 = 2 x (81) + 4 x (80) + 6 x (8-1) = 20.7510

Decimal to Octal Number Conversion

Can be done by successive division of 8

This method uses repeated division by 8.

e.g. Convert 17710 to octal and binary:

177/8 = 22+ remainder of 1 1 (Least Significant Bit)

22/ 8 = 2 + remainder of 6 6
2/8 = 0 + remainder of 2 2 (Most Significant Bit)
2618
Result 17710 =
Convert to Binary = 0101100012

e.g. 93810 = 16528

Hexadecimal Number System

Hexadecimal Numbers are base 16

There are 16 digits: 0 to 9, A, B, C, D, E, F

 163 162 161 160 16-1 16-2 16-3
=4096 =256 =16 =1 . =1/16 =1/256 =1/4096
Most Least
Hexadec.
Significant Significant
point
Digit Digit

An n-bit hexadecimal number a decimal value:

a n-1 x 16 n-1 + a n-2 x 16 n-2 +…+ a 1 x 16 1 + a 0 x 16 0

The conversion of hexadecimal to decimal can be done with the above equation
e.g. B5E16 = 11x162 + 5x161 + 14x160
= 2816 + 80 + 14 = 291010

Decimal to Hexadecimal Conversion

This method uses repeated division by 16.

e.g. Convert 37810 to hexadecimal and binary:

378/16 = 23+ remainder of 10 A (Least Significant Bit)

23/ 16 = 1 + remainder of 7 7
1 / 16 = 0 + remainder of 1 1 (Most Significant Bit)
Result 37810 = 17A16

Convert to Binary = 0001 0111 10102

e.g. 279310 = AE916

Conversion between Binary and Octal

Conversion between Binary and Octal is convenient

Each Octal digit equals to 3 bits
 e.g. 3 6 2 8 - 011 110 010 2
5 4 1 8 - 101 100 001 2

e.g. 010 101 110 2 - 2 5 6 8

111 010 001 2 - 7 2 1 8

Conversion between Binary and Hex

Conversion between Binary and Hexadecimal is also convenient

Each Hexadecimal digit equals to 4 bits

E 2 8 0 16 - 1110 0010 1000 0000 2

F B 1 16 - 1111 1011 0001 2

Conversion among number systems

7318 = 111 011 0012

= 0001 1101 10012
= 1 D 9 16
= 1x162 + 13x161 + 9x160
 = 256 + 208 + 9
= 47310
7318 = 7x82 + 3x81 + 1x80
= 448 + 24 + 1
= 47310

Signed Binary Numbers

In ordinary arithmetic, a minus sign “-” is used to represent negative

numbers,e.g.-38
In digital electronic circuits, everything is represented with bits (0, 1).There are
several ways to represent the signed binary numbers with just bits, e.g.:
 Signed Magnitude Representation
 1’s Complement Representation
 2’s Complement Representation

Signed Magnitude Number System

The most significant bit (MSB) is a sign bit

If the MSB is 0, the number is positive
If the MSB is 1, the number is negative
e.g. 01101 = +13
11101 = -13
e.g. 00000 = +0
10000 = -0
Disadvantage (a):2 patterns represent 0
(b): Handle sign bit separately

1’s Complement Number System

Positive numbers and the corresponding negative numbers complement each other
Complement is inversion (Logic NOT)
e.g. 01101 = +13
10010 = -1
e.g. 00000 = +0
11111 = -0
Disadvantage (a):2 patterns represent 0
(b): Handle sign bit separately25

2’s Complement Number Conversion

To find the 2’s complement number for a negative decimal, we can find the
binary of
the positive decimal and then take its 2’scomplement.Two’s complement is
obtained by adding one to the one’s complement
e.g. -910
 9 = 01001
Invert bits: 10110
Plus 1: 10111 = -910
Check: -16 + 0 + 4 + 2 + 1 = -9

Value Range

For 4-bit binary, the range is:

Value Range

For n-bit binary, the range is:

CODES

Group of bits assigned to represent, identify or relate to multivalued items of

information. By assigning each item of information a unique combination of bits the
information is transferred from one form to another. The group of bits may be numbers,
alphabets, control functions and special characters.
 An n-bit binary code is a group of n bits that assume up to 2n combinations of 1’s
and 0’s with each combination representing one element of the set being enclosed.

Types

Weighted codes
Non – weighted codes
Self complementing codes
Reflective codes
Alphanumeric codes
Error detecting and correcting codes

1. Weighted Codes

Each bit has a positional value of 8,4,2 or 1 in binary codes. Examples are
8421, 2421, 3321, 4221, 5211, 5311, 5421, 6311,7421, 742’1’,
842’1’
All the above codes are used to represent a given decimal digit into four bit
binary word.

S.No. Decimal 8421 2421 3321 4221 5311 5421 6311 7421 742’1’ 842’1’
Number
1. 0 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
2. 1 0001 0001 0001 0001 0001 0001 0001 0001 0111 0111
3. 2 0010 0010 0010 0010 0011 0010 0011 0010 0110 0110
4. 3 0011 0011 0011 0011 0100 0011 0100 0011 0101 0101
5. 4 0100 0100 0101 1000 0101 0100 0101 0100 0100 0100
6. 5 0101 1011 0110 0111 1000 0101 0111 0101 1010 1011
7. 6 0110 1100 0111 1100 1001 0110 1000 0110 1001 1010
8. 7 0111 1101 1101 1101 1010 0111 1001 0111 1000 1001
9. 8 1000 1110 1110 1110 1100 1011 1011 1001 1111 1000
10. 9 1001 1111 1111 1111 1101 1100 1100 1010 1110 1111

2. Non-weighted Codes:
Each bit has no positional value
1. Excess-3 code
2.Gray code
3.Five bit BCD

3. Self complementing codes (or) Reflective codes

Code for one digit will be the complement of other
1.2421
2.5211
3. Excess-3
4. Sequential Codes
 Succeeding number is one more than the previous one
1. 8421
2. Excess-3
5. Alphanumeric codes
1. ASCII
2. EBCDIC
3. Hollerith
6. Error detecting and correcting codes

For reliable transmission and storage of digital data, error detection and correction
is required. Below are a few examples of codes which permit error detection and
error correction after detection
Error Detecting Codes

When data is transmitted from one point to another, like in wireless transmission,
or it is just stored, like in hard disks and memories, there are chances that data
may get corrupted. To detect these data errors, we use special codes, which are
error detection codes.

Parity

In parity codes, every data byte, or nibble (according to how user wants to use it)
is checked if they have even number of ones or even number of zeros. Based on
this information an additional bit is appended to the original data. Thus if we
consider 8-bit data, adding the parity bit will make it 9 bit long.

At the receiver side, once again parity is calculated and matched with the received
parity (bit 9), and if they match, data is ok, otherwise data is corrupt.

There are two types of parity:

 Even parity: Checks if there is an even number of ones; if so, parity bit is
zero. When the number of ones is odd then parity bit is set to 1.
 Odd Parity: Checks if there is an odd number of ones; if so, parity bit is
zero. When number of ones is even then parity bit is set to 1.

Error-Correcting Codes

Error-correcting codes not only detect errors, but also correct them. This is used
normally in Satellite communication, where turn-around delay is very high as is
the probability of data getting corrupt.

ECC (Error correcting codes) are used also in memories, networking, Hard disk,
CDROM, DVD etc. Normally in networking chips (ASIC), we have 2 Error
detection bits and 1 Error correction bit.
Hamming Code

Hamming code adds a minimum number of bits to the data transmitted in a noisy
channel, to be able to correct every possible one-bit error. It can detect (not
correct) two-bits errors and cannot distinguish between 1-bit and 2-bits
inconsistencies. It can't - in general - detect 3(or more)-bits errors.

The idea is that the failed bit position in an n-bit string (which we'll call X) can be
represented in binary with log2(n) bits, hence we'll try to get it adding just log2(n)
bits.

First, we set m = n + log2(n) to the encoded string length and we number each bit
position starting from 1 through m. Then we place these additional bits at power-
of-two positions, that is 1, 2, 4, 8..., while remaining ones (3, 5, 6, 7...) hold the
bit string in the original order.

Now we set each added bit to the parity of a group of bits. We group bits this
way: we form a group for every parity bit, where the following relation holds:

position(bit) AND position(parity) = position(parity)

(Note that: AND is the bit-wise boolean AND; parity bits are included in the
groups; each bit can belong to one or more groups.)

So bit 1 groups bits 1, 3, 5, 7... while bit 2 groups bits 2, 3, 6, 7, 10... , bit 4
groups bits 4, 5, 6, 7, 12, 13... and so on.

Thus, by definition, X (the failed bit position defined above) is the sum of the
incorrect parity bits positions (0 for no errors).

To understand why it is so, let's call Xn the nth bit of X in binary representation.
Now consider that each parity bit is tied to a bit of X: parity1 -> X1, parity2 -> X2,
parity4 -> X3, parity8 -> X4 and so on - for programmers: they are the respective
AND masks. By construction, the failed bit makes fail only the parity bits which
correspond to the 1s in X, so each bit of X is 1 if the corresponding parity is
wrong and 0 if it is correct.

Note that the longer the string, the higher the throughput n/m and the lower the
probability that no more than one bit fails. So the string to be sent should be
broken into blocks whose length depends on the transmission channel quality (the
cleaner the channel, the bigger the block). Also, unless it's guaranteed that at most
one bit per block fails, a checksum or some other form of data integrity check
should be added.

Alphanumeric Codes
 The binary codes that can be used to represent all the letters of the alphabet,
numbers and mathematical symbols, punctuation marks, are known as
alphanumeric codes or character codes. These codes enable us to interface the
input-output devices like the keyboard, printers, video displays with the computer.

ASCII Code

ASCII stands for American Standard Code for Information Interchange. It has
become a world standard alphanumeric code for microcomputers and computers.
It is a 7-bit code representing 27 = 128 different characters. These characters
represent 26 upper case letters (A to Z), 26 lowercase letters (a to z), 10 numbers
(0 to 9), 33 special characters and symbols and 33 control characters.

The 7-bit code is divided into two portions, The leftmost 3 bits portion is called
zone bits and the 4-bit portion on the right is called numeric bits.

An 8-bit version of ASCII code is known as USACC-II 8 or ASCII-8. The 8-bit

version can represent a maximum of 256 characters.

EBCDIC Code

EBCDIC stands for Extended Binary Coded Decimal Interchange. It is mainly

used with large computer systems like mainframes. EBCDIC is an 8-bit code and
thus accomodates up to 256 characters. An EBCDIC code is divided into two
portions: 4 zone bits (on the left) and 4 numeric bits (on the right).

Hollerith code

Hollerith developed a way of feeding information into digital computers using

punched cards. The code used in this system to represent alphanumeric
information is known as Hollerith code. Punch card has 80 columns and 12 rows.
Each column represents an alphanumeric character with holes in appropriate
rows. A hole is sensed as ‘1’ and absence of hole is sensed as ‘0’ by the circuit in
card reader. The 12 rows are marked starting from top as
12,11,0,1,2,3,4,5,6,7,8,9,. Each row is 1-bit information. So, Hollerith code is
a12-bit code. The first 3 rows are zone punch rows and the remaining 9 are
numeric punch rows. The numbers are represented in the column by single punch
whereas alphabets are represented using 2 punches.

Binary Coded Decimal (BCD)

Binary numbers are used by computers and human beings are familiar with
decimals.
To facilitate the easy conversion between binary and decimal, BCD is used.
In BCD number system, each decimal digit is represented by 4 bits
 Group of 4 binary bits is a nibble. A nibble representing a number greater
than 9 is invalid BCD

Decimal to BCD Conversion

Binary 1010 to 1111 are not used in BCD

Example 1. Decimal 56 in BCD is 0101 0110

in binary is 00111000

BCD addition

 Add the given BCD numbers using binary addition

 If the sum – nibble (group of 4 bits) is equal to or less than 9 (without
carry) then it is valid BCD.
 If the sum – nibble (group of 4 bits) is greater than 9 (or) if a carry is
generated then it is invalid BCD.
 To make the invalid BCD valid add 01102 to the nibble and if a carry is
generated add it to the next higher order BCD digit.
Examples

1. Add 4 and 5
4-> 0100
5-> 0101

1001 -> 9 -> valid BCD

2. Add 4 and 8

4-> 0100
8-> 1000

1100
 1100 is invalid BCD since it is greater than 1001 so add 0110 to 1100
and
the result is 1 0010 which is equal to 12.

3. Add 8 and 9

8-> 1000
9-> 1001

10001

In the addition carry is generated so the result is invalid BCD. To make it

valid add 0110 to 10001 and the result is 1 0111 which is equal to 17.

Excess-3 (XS3) code

1. Non weighted BCD code

2. Add three to each nibble of BCD code to get the XS3 code.
3. This code helps in performing subtraction operations in the earlier
computers.
4. The table below shows the BCD and XS-3 codes for decimal digits 0 to
9

Decimal BCD Excess-3

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

Decimal to XS-3 conversion

(Ex).Convert 436 into XS-3 code

BCD equivalent of 436 is 0100 0011 0110
Add 3 (i.e) 0011 to each group of 4 bits
0100 0011 0110
0011 0011 0011

0111 0110 1001

 7 6 9 - Xs-3 in decimal

Gray code

 It is a minimum change code where only one bit in the code group changes
while going from one step to the next. Binary numbers have more than 1 bits
changing when increasing or decreasing continuously e.g. 0011 to 0100 (3 to
4): 3 bits change. In digital electronic circuits, sometimes it is desired to have
only 1 bit changed In this case, Gray Code can be used In Gray Code, the
adjacent numbers have only 1 bit different
 It is also called as unit – distance code.
 In this code no weight can be attached with each bit position therefore it is
unsuitable for arithmetic operations.
 Gray codes are useful in input and output devices and in analog and digital
converters.

Gray to Binary conversion

 MSB of the gray code is same as binary number. So write the MSB as it is.
 Add the MSB of the output with bit immediately on right in input and record
the sum. If a carry is generated it is ignored.
 Continue adding the bits in the output to immediate input bit in right till the
LSB is reached.
 The binary equivalent has same number of bits as the gray code.
 This can be achieved by using X-OR gate.

Example
Convert 1011 to binary
Binary to Gray conversion

 MSB of the binary is same as MSB of gray code.

 Add the MSB of binary with immediate bit to right in binary and that is
the next gray bit. If a carry is generated it is ignored.
 Repeat the procedure till the LSB is reached.

Example:

Convert 1011 to gray code

 BOOLEAN EXPRESSION
SIMPLIFICATION

 NEED FOR SIMPLIFICATION

 SIMPLIFICATION METHODS
1. USING BOOLEAN THEOREMS
2. KARNAUGH MAP METHOD
3.QUINE Mc CLUSKY METHOD

1
 NEED FOR SIMPLIFICATION

F = x’y’z +x’yz +xy’ ------- Eqn 1

= x’z (y + y’) + xy’
= x’z +xy’ ------- Eqn 2
Compare Eqn 1 and Eqn 2
Eqn 1 requires two 3 input AND gates, one 2 input AND gate and anOR
gate with 3 inputs
Eqn 2 requires two 2 input AND gates and an OR gate with 2 inputs

Simplified expression requires lesser number of gates and lesser number of

inputs. It is preferable since it requires less wires and lesscomponents

2
 SIMPLIFICATION USING BOOLEAN
THEOREMS
DISADVANTAGES

1. Time consuming process

2. Need better understanding of laws and theorems 3.Lack of
specific rules to predict each succeeding step in
reduction process.

3
 KARNAUGH MAP METHOD

• Karnaugh Map, invented by Maurice Karnaugh of Bell Labs

in 1953, also known as K-map, is a diagrammaticmethod for
logic minimization
• Pictorial form of truth table showing the relationship
between inputs & outputs
• More efficient than Boolean algebra
• K-map is a diagram made up of squares. Each square
represents a minterm or maxterm of the logic function
• K-map identifies the group of minterms which contains
redundant variables of the form x + x’ = 1 and then it canbe
eliminated.

4
 TWO - VARIABLE K-MAP

• For a 2-variable function, there are 4 minterms.

Therefore, the K-map for a 2- variable function has 4
squares:

In each square, the minterm is either 0 or 1

depending on the value of the function at that
square
5
Construction of 2-variable K-map
• To construct a K-map for a 2-variable function, a logic 1is
entered into the square where the corresponding minterm
exists. A logic 0 is entered otherwise (or the square is left
blank)
• (ex) f = A’B + AB’
• f is true when AB = 01 or 10
• f = Σ(1, 2)

6
 Construction of K-map from Truth
Table
• A K-map can be created directly from a truth table
• Each square of the K-map corresponds to one row of thetruth
table
• A logic 1 is entered when the function is 1
• A logic 0 is entered when the function is 0
• For example

7
 3-variable K-map

• A 3-variable logic function has 8 minterms and its truth

table has 8 rows
• Hence, a 3-variable K-map has 8 squares

8
 Logic Minimization with K-Map
• Consider a logic function with m2 and m6
• i.e. f = Σ(2, 6)
• m2 is a’bc’ and m6 is abc’
• f = m2 + m6 = a’bc’ + abc’ = bc’(a’ + a) = bc’
• The 2 minterms have a common factor bc’ In the K-map,if we
group these 2 adjacent minterms, we can reduce 1variable

9
TRUTH TABLE TO MAP

10
Example of looping pairs of adjacent 1s
PAIRS

11
Example of looping pairs of adjacent 1s
QUADS

12
Example of looping pairs of adjacent 1s
OCTETS

13
 PROCEDURE

• Construct the K map, place 1s as indicated in the truthtable.

• Check for octets (group of eight 1s)
• If octets not available check for quads (four adjacent 1s)
• Loop 1s that are adjacent to only one other 1 and
encircle such pairs.
• Loop 1s that are not adjacent to any other 1s.
• 1s which are already present in a group can be includedin
new group to group the other 1s.
• Form the sum of all product terms generated by eachloop.

14
Examples

15
 K-map for Product of Sums

• Covering logic-1 squares in K-map gives logic functionsin

sum of products form
• Covering logic-0 squares, will give logic functions in
product of sums form, e.g.
• F’ = B’C + AC
• F = (B’C + AC)’
= (B’C)’ (AC)’
= (B+C’) (A’+C’)

16
K-map for Product of Sums Example

17
 DON’T-CARE Conditions
• In logic function, sometimes we do not have the
specification for all the combinations

• We might define a logic function to be 1 for some

combinations and 0 for some others but the rest is not
define

• We do not care about the logic value of the function for

these undefined combinations called as DON’T-CARE
conditions

• DON’T-CARE conditions are usually denoted by ‘x’, or‘X’

or ‘d’

18
 Truth Table with DON’T-CARE
Conditions

• f has unknown (or don’t care) values for combinationsabc

= 100 or 110
• Usually expressed as: f(a,b,c) = Σ(1, 2, 5) + d(4, 6)
19
K-map with DON’T-CARE Conditions

• When constructing a K-map for a logic function with

don’t-care conditions, we enter ‘x’ into the squares wherethe
function is undefined
• When a K-map contains don’t-care conditions, we cantreat
the don’t-cares as either 1 or 0
• We make use of x=1for grouping them with adjacent 1’sto
make the groups larger
• We don’t group x when it is treated as 0

20
 BOOLEAN ALGEBRA AND COMBINATIONAL CIRCUITS

Boolean Variables & Truth Tables

Boolean algebra differs in a major way from ordinary algebra in that 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.

Some common representation of 0 and 1 is shown in the following diagram.

In Boolean algebra, there are three basic logic operations: AND ,OR, and NOT.
These logic gates are digital circuits constructed from diodes, transistors, and resistors
connected in such a way that the circuit output is the result of a basic logic operation
(OR, AND, NOT) performed on the inputs.

Truth Table

A truth table is a means for describing how a logic circuit's output depends on the
logic levels present at the circuit's inputs.

In the following two-input logic circuit, the table lists all possible combinations of
logic levels present at inputs A and B along with the corresponding output level X.

When either input A OR B is 1, the output X is 1. Therefore the "?" in the box is an
OR gate.

OR Operation

The expression X = A + B reads as "X equals A OR B". The + sign stands for the OR
operation, not for ordinary addition.

The OR operation produces a result of 1 when any of the input variable is 1.

The OR operation produces a result of 0 only when all the input variables are 0.
 An example of three input OR gate and its truth table is as follows:

With the OR operation, 1 + 1 = 1, 1+ 1 + 1 = 1 and so on.

AND Operation

The expression X = A * B reads as "X equals A AND B".

The multiplication sign stands for the AND operation, same for ordinary
multiplication of 1s and 0s.The AND operation produces a result of 1 occurs only for
the single case when all of the input variables are 1.The output is 0 for any case where
one or more inputs are 0
 An example of three input AND gate and its truth table is as follows:

With the AND operation, 1*1 = 1, 1*1*1 = 1 and so on.

NOT Operation

The NOT operation is unlike the OR and AND operations in that it can be performed
on a single input variable. For example, if the variable A is subjected to the NOT
operation, the result x can be expressed as x = A' where the prime (') represents the
NOT operation. This expression is read as:
x equals NOT A
x equals the inverse of A
x equals the complement of A

Each of these is in common usage and all indicate that the logic value of x = A' is o
pposite to the logic value of A. The truth table of the NOT operation is as follows:
 1'=0 because NOT 1 is 0
0' = 1 because NOT 0 is 1

The NOT operation is also referred to as inversion or complementation, and these

terms are used interchangeably.

NOR Operation

NOR and NAND gates are used extensively in digital circuitry. These gates combine
the basic operations AND, OR and NOT, which make it relatively easy to describe
then using Boolean algebra.

NOR gate symbol is the same as the OR gate symbol except that it has a small circle
on the output. This small circle represents the inversion operation. Therefore the
output expression of the two input NOR gate is:

X = (A + B)'
 An example of three inputs OR gate can be constructed by a NOR gate plus a NOT
gate:

NAND Operation

NAND gate symbol is the same as the AND gate symbol except that it has a small
circle on the output. This small circle represents the inversion operation. Therefore
the output expression of the two input NAND gate is:

X = (AB)'

Describing Logic Circuits Algebraically

 Any logic circuit, no matter how complex, may be completely described using the
Boolean operations, because the OR gate, AND gate, and NOT circuit are the basic
building blocks of digital systems.

This is an example of the circuit using Boolean expression:

If an expression contains both AND and OR operations, the AND operations are
performed first (X=AB+C: AB is performed first), unless there are parentheses in the
expression, in which case the operation inside the parentheses is to be performed first
(X= (A+B) +C: A+B is performed first).

Circuits containing Inverters

Whenever an INVERTER is present in a logic-circuit diagram, its output expression

is simply equal to the input expression with a prime (') over it.

Evaluating Logic Circuit Outputs

Once the Boolean expression for a circuit output has been obtained, the output logic
level can be determined for any set of input levels.

These are two examples of the evaluating logic circuit output:

Let A=0, B=1, C=1, D=1

X = A'BC (A+D)'
= 0'*1*1* (0+1)'
= 1 *1*1* (1)'
= 1 *1*1* 0
=0
 Let A=0, B=0, C=1, D=1, E=1

X = [D+ ((A+B)C)'] * E
= [1 + ((0+0)1 )'] * 1
= [1 + (0*1)'] * 1
= [1+ 0'] *1
= [1+ 1 ] * 1
=1

In general, the following rules must always be followed when evaluating a Boolean
expression:

1. First, perform all inversions of single terms; that is, 0 = 1 or 1 = 0.

2. Then perform all operations within parentheses.
3. Perform an AND operation before an OR operation unless parentheses indicate
otherwise.
4. If an expression has a bar over it, perform the operations of the expression first and
then invert the result.

Determining Output Level from a Diagram

The output logic level for given input levels can also be determined directly from the
circuit diagram without using the Boolean expression.

Implementing Circuits from Boolean Expression

If the operation of a circuit is defined by a Boolean expression, a logic-circuit

diagram can he implemented directly from that expression.
 Suppose that we wanted to construct a circuit whose output is y = AC+BC' + A'BC.
This Boolean expression contains three terms (AC, BC', A'BC), which are ORed
together. This tells us that a three-input OR gate is required with inputs that are equal
to AC, BC', and A'BC, respectively.

Each OR-gate input is an AND product term, which means that an AND gate with
appropriate inputs can be used to generate each of these terms. Note the use of
INVERTERs to produce the A' and C' terms required in the expression.

Boolean Theorems

Investigating the various Boolean theorems (rules) can help us to simplify logic
expressions and logic circuits.
Multivariable Theorems

The theorems presented below involve more than one variable:

(9) x + y = y + x (commutative law)

(10) x * y = y * x (commutative law)
(11) x+ (y+z) = (x+y) +z = x+y+z (associative law)
(12) x (yz) = (xy) z = xyz (associative law)
(13a) x (y+z) = xy + xz
(13b) (w+x)(y+z) = wy + xy + wz + xz
(14) x + xy = x [proof see below]
(15) x + x'y = x + y

Proof of (14)

x + xy = x (1+y)
= x * 1 [using theorem (6)]
= x [using theorem (2)]

DeMorgan's Theorem

DeMorgan's theorems are extremely useful in simplifying expressions in which a

product or sum of variables is inverted. The two theorems are:

(16) (x+y)' = x' * y'

 Theorem (16) says that when the OR sum of two variables is inverted,
this is the same as inverting each variable individually and then
ANDing these inverted variables.

(17) (x*y)' = x' + y'

Theorem (17) says that when the AND product of two variables is inverted,
this is the same as inverting each variable individually and then ORing them.
 Example

X = [(A'+C) * (B+D')]'
= (A'+C)' + (B+D')' [by theorem (17)]
= (A''*C') + (B'+D'') [by theorem (16)]
= AC' + B'D

Three Variables DeMorgan's Theorem

(18) (x+y+z)' = x' * y' * z'

(19) (xyz)' = x' + y' + z'

Universality of NAND & NOR Gates

It is possible to implement any logic expression using only NAND gates and no other
type of gate. This is because NAND gates, in the proper combination, can be used to
perform each of the Boolean operations OR, AND, and INVERT.
 In a similar manner, it can be shown that NOR gates can be arranged to implement
any of the Boolean operations.

Alternate Logic Gate Representations

The left side of the illustration shows the standard symbol for each logic gate, and the
right side shows the alternate symbol. The alternate symbol for each gate is obtained
from the standard symbol by doing the following:

1. 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.

2. 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.)
 Several points should be stressed regarding the logic symbol equivalences:

1. The equivalences are valid for gates with any number of inputs.

2. None of the standard symbols have bubbles on their inputs, and all the
alternate symbols do.

3. 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.

4. NAND and NOR gates are inverting gates, and so both the standard and
alternate symbols for each will have a bubble on either the input or the output.
AND and OR gates are noninverting gates, and so the alternate symbols for
each will have bubbles on both inputs and output.

Concept of Active Logic Levels:

When an input or output line on a logic circuit symbol has no bubble on it, that line is
said to be active-HIGH. When an input or output line does have a bubble on it, that
line is said to be 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.
Boolean Function

A Boolean function is an algebraic expression consists of binary variables, the

constants 0 & 1, and the Boolean operators.For a set of given values of the variables,
the function is evaluated to either 0 or 1
e.g. f = x • y + x • z’
The Boolean function f has 3 binaryvariables x, y and z
The function is 1 if x and y are both 1 or if x is 1 and z is 0. Otherwise, f = 0

Operator Precedence

The operator precedence is:

1. Parentheses
2. NOT
3. AND
4. OR
e.g. f = x • y + x • z’
Precedence: z’, x • y, x • z’, x • y + x • z’

e.g. f = (a +b) • (c+d’)

Precedence: a+b, d’, c+d’, (a +b) • (c+d’)
The parentheses precedence is the same as in normal algebra

Boolean Function Truth Table

Boolean function can be represented by truth table as well.If the function has n
variables, its truth table will have 2n rows
e.g. f = x • y + x • z’
f has 3 variables so 23 combinations
 f is 1 when the expression is evaluated to 1 otherwise it is 0.

Minterm

In a Boolean function, a binary variable (x) may appear either in its normal form (x)
or in its complement form (x’).Consider 2 binary variables x and y and an AND
operation, there are 4 and only 4 possible combinations: x’•y’, x’•y, x•y’ & x•y
Each of the 4 product terms is called a MINTERM or STANDARD PRODUCT

By definition, a Minterm is a product which consists of all the variables in the normal
form or the complement form but NOT BOTH.
e.g. for a function with 2 variables x and y:
x•y’ is a minterm but x’ is NOT a minterm
e.g. for a function with 3 variables x, y andz:
x’yz’ is a minterm but xy’ is NOT a minterm
Maxterm

Consider 2 binary variables x and y and an OR operation, there are 4 and only 4
possible combinations: x’+y’, x’+y, x+y’, x+y.Each of the 4 sum terms is called a
MAXTERM or STANDARD SUM.By definition, a Maxterm is a sum in which each
variable appears once and only once either in its normal form or its complement
form but NOT BOTH.

Minterms and Maxterms for 3 Variables

Minterm Boolean Expression

Boolean functions can be expressed with minterms,

e.g.f1(x,y,z) = m1 + m4 + m6 = Σm(1, 4, 6)
f2(x,y,z) = m2 + m4 + m6+ m7
= Σm(2, 4, 6, 7)

Maxterm Boolean Expression

Boolean functions can also be expressed with maxterms,

e.g.f1’ = x’y’z’+x’yz’+x’yz+xy’z+xyz
f1 = (x’y’z’+x’yz’+x’yz+xy’z+xyz)’
= (x+y+z)(x+y’+z)(x+y’+z’)(x’+y+z’)(x’+y’+z’)
= M0•M2•M3•M5•M7
= Π M(0, 2, 3, 5, 7)
f2 = M0•M1•M3•M5
= Π M(0, 1, 3, 5)
Literal

A Literal is a variable in a product or sum term

xy’ is a 2-literal product term
x’yz has 3 literals
x’ + xy’ + x’yz is an expression of sum of products with 3 product terms.The
3 product terms have 1, 2 and 3 literals respectively
x’(x+y’)(x’+y+z) is an expression of product of sums.The 3 sum terms have 1,
2 and 3 literals

Express Boolean Functions in Minterms

If product terms in a Boolean function are not minterms, they can be converted to
minterms
e.g. f(a,b,c) = a’ + bc’ + ab’c
Function f has 3 variables, therefore, each minterm must have 3 literals
Neither a’ nor bc’ are minterms.They can be converted to minterm.ab’c is a
minterm

Conversion to Minterms

e.g. f(a,b,c) = a’ + bc’ + ab’c

To convert a’ to a minterm, the 2 variables (b, c) must be added, without changing its
functionality .Since a’=a’•1 & 1 = b+b’, a’= a’(b + b’) = a’b + a’b’
Similarly, a’b = a’b(c + c’) = a’bc + a’bc’ and a’b’ = a’b’(c+c’) = a’b’c + a’b’c’
bc’ = bc’(a+a’) = abc’ + a’bc’
f = a’bc+a’bc’+a’b’c+a’b’c’+abc’+a’bc’+ab’c

Express Boolean Functions in Maxterms

By using the Distribution Law: x+yz = (x+y)(x+z), a Boolean function can

be converted to an expression in product of maxterms
e.g. f(a,b,c) = a’+bc’
= (a’+b)(a’+c’) {not maxterms}
= (a’+b+cc’)(a’+c’+bb’) {cc’=0}
= (a’+b+c)(a’+b+c’)(a’+c’+b)(a’+c’+b’)
= (a’+b+c)(a’+b+c’)(a’+c’+b’)

Boolean Function Manipulation

 Boolean functions can be manipulated with Boolean algebra.Manipulation can
transform logic expressions, but still keep the same logic functionality.Manipulation
can reduce the complexity, hence, easier to be implemented in hardware, i.e. fewer
logic gates

Boolean Function Manipulation Example

f = xy’ + xyz + x’z

= x(y’ + yz) + x’z {common factor}
= x[(y’+y)(y’+z)] + x’z {Distribution law}
= x(y’+z) + x’z {y’ + y = 1}
= xy’ + xz + x’z {Distribution law}
= xy’ + (x + x’)z {common factor}
= xy’ + z {x + x’ = 1}
Simplify f1=abc+a’b+abc’ and f2=(a+b)’(a’+b’) to the minimum literals

f1 = abc+a’b+abc’ = ab(c+c’) + a’b = ab + a’b = (a+a’)b = b

f2 =(a+b)’(a’+b’) = a’b’(a’+b’) {DeMorgan}
= a’b’a’+a’b’b’
= a’b’ + a’b’ = a’b’

QUINE-McCLUSKEY MINIMIZATION

Quine-McCluskey minimization method uses the same theorem to produce the

solution as the K-map method, namely X(Y+Y')=X

Minimization Technique

 The expression is represented in the canonical SOP form if not already in that form.
 The function is converted into numeric notation.
 The numbers are converted into binary form.
 The minterms are arranged in a column divided into groups.
 Begin with the minimization procedure.
 Each minterm of one group is compared with each minterm in the group immediately
below.
 Each time a number is found in one group which is the same as a number in the group
below except for one digit, the numbers pair is ticked and a new composite is created.
 This composite number has the same number of digits as the numbers in the pair
except the digit different which is replaced by an "x".
 The above procedure is repeated on the second column to generate a third column.
 The next step is to identify the essential prime implicants, which can be done using a
prime implicant chart.
 Where a prime implicant covers a minterm, the intersection of the corresponding row
and column is marked with a cross.
 Those columns with only one cross identify the essential prime implicants. -> These
prime implicants must be in the final answer.
 The single crosses on a column are circled and all the crosses on the same row are
also circled, indicating that these crosses are covered by the prime implicants
selected.
  Once one cross on a column is circled, all the crosses on that column can be circled
since the minterm is now covered.
 If any non-essential prime implicant has all its crosses circled, the prime implicant is
redundant and need not be considered further.
 Next, a selection must be made from the remaining nonessential prime implicants, by
considering how the non-circled crosses can be covered best.
 One generally would take those prime implicants which cover the greatest number of
crosses on their row.
 If all the crosses in one row also occur on another row which includes further crosses,
then the latter is said to dominate the former and can be selected.
 The dominated prime implicant can then be deleted.

Example

Find the minimal sum of products for the Boolean expression,

f= (1,2,3,7,8,9,10,11,14,15), using Quine-McCluskey method.

Firstly these minterms are represented in the binary form as shown in the table below.
The above binary representations are grouped into a number of sections in terms of
the number of 1's as shown in the table below.

Binary representation of minterms

Minterms U V W X
1 0 0 0 1
2 0 0 1 0
3 0 0 1 1
7 0 1 1 1
8 1 0 0 0
9 1 0 0 1
10 1 0 1 0
11 1 0 1 1
14 1 1 1 0
15 1 1 1 1

Group of minterms for different number of 1's

No of 1's Minterms U V W X
1 1 0 0 0 1
1 2 0 0 1 0
1 8 1 0 0 0
2 3 0 0 1 1
2 9 1 0 0 1
2 10 1 0 1 0
 3 7 0 1 1 1
3 11 1 0 1 1
3 14 1 1 1 0
4 15 1 1 1 1

Any two numbers in these groups which differ from each other by only one variable
can be chosen and combined, to get 2-cell combination, as shown in the table below.

2- Cell combinations

Combinations U V W X
(1,3) 0 0 - 1
(1,9) - 0 0 1
(2,3) 0 0 1 -
(2,10) - 0 1 0
(8,9) 1 0 0 -
(8,10) 1 0 - 0
(3,7) 0 - 1 1
(3,11) - 0 1 1
(9,11) 1 0 - 1
(10,11) 1 0 1 -
(10,14) 1 - 1 0
(7,15) - 1 1 1
(11,15) 1 - 1 1
(14,15) 1 1 1 -

From the 2-cell combinations, one variable and dash in the same position can be
combined to form 4-cell combinations as shown in the figure below.

Combinations U V W X
(1,3,9,11) - 0 - 1
(2,3,10,11) - 0 1 -
(8,9,10,11) 1 0 - -
(3,7,11,15) - - 1 1
(10,11,14,15) 1 - 1 -

The cells (1,3) and (9,11) form the same 4-cell combination as the cells (1,9) and
(3,11). The order in which the cells are placed in a combination does not have any
effect. Thus the (1,3,9,11) combination could be written as (1,9,3,11).

From above 4-cell combination table, the prime implicants table can be plotted as
shown in table below.
Prime Implicants Table

Prime
1 2 3 7 8 9 10 11 14 15
Implicants
(1,3,9,11) X - X - - X - X - -
(2,3,10,11) - X X - - - X X - -
(8,9,10,11) - - - - X X X X - -
(3,7,11,15) - - - - - - X X X X
- X X - X X - - - X -

The columns having only one cross mark correspond to essential prime implicants. A
yellow cross is used against every essential prime implicant. The prime implicants
sum gives the function in its minimal SOP form.

Y = V'X + V'W + UV' + WX + UW

Logic
Combinational logic blocks have the outputs depending on the combinations of the
current inputs. Sequential logic blocks have the outputs depending on the current
inputs as well as any previous inputs.

Binary Adder
Binary Adder is for binary number addition
Logic Circuit to be discussed:
 Half Adder
 Full Adder
 Ripple Adder
 Carry Look Ahead Adder

Half Adder

o Half adder is for addition of 2 single bits

o It has two 1-bit inputs and two 1-bit outputs
o The inputs are the 2 bits to be added (a, b)
o The outputs are 1-bit sum (s) & 1-bit carry (c)

The logic is:

Binary Addition

The half adder adds 2 single-bit inputs

It cannot complete a full addition

To complete a full addition, the adder needs to take in 3 inputs: a, b and the carry
from the previous bit.

Full Adder

To carry the addition, an adder with 3 inputs is required. A Full Adder takes in 3
inputs (a, b and ci) and produces 2 outputs (s, co) a & b are the 2 bits to be added, ci
is the carry input (carry over from the previous bit) and co is the carry output (to the
next bit)
Logic for Full Adder
Logic equations derived from the truth table:

s=a 
co = ab + bci + aci

Full Adder

The below implementation shows implementing the full adder with AND-OR gates,
instead of using XOR gates. The basis of the circuit below is from the above Kmap.

Circuit-SUM
Circuit-CARRY

Full adder can be built from 2 half adders

s = a  b  ci
co = ab+bci+aci
= ab+(a’bci+abci)+(abci+ab’ci)
= ab + abci + ci (a’b+ab’) = ab + ci (a  b)

n-bit Ripple Adder

To perform an addition of 2 n-bit numbers An-1…A1A0 & Bn-1…B1B0, where An-
1 & Bn-1 are theMSB & A0B0 are the LSB, we need a n-bit adder,which can be built
from ‘n ‘fulladders

Ripple Adder: Carry ripples through the chain

Carry-Look-Ahead Adder

The delay generated by an N-bit adder is proportional to the length N of the two
numbers X and Y that are added because the carry signals have to propagate from one
full-adder to the next. For large values of N, the delay becomes unacceptably large so
that a special solution needs to be adopted to accelerate the calculation of the carry
bits. This solution involves a "look-ahead carry generator" which is a block that
simultaneously calculates all the carry bits involved. Once these bits are available to
the rest of the circuit, each individual three-bit addition (Xi+Yi+carry-ini) is
implemented by a simple 3-input XOR gate. The design of the look-ahead carry
generator involves two Boolean functions named Generate and Propagate. For each
input bits pair these functions are defined as:

Gi = Xi . Yi

Pi = Xi + Yi

The carry bit c-out(i) generated when adding two bits Xi and Yi is '1' if the
corresponding function Gi is '1' or if the c-out(i-1)='1' and the function Pi = '1'
simultaneously. In the first case, the carry bit is activated by the local conditions (the
values of Xi and Yi). In the second, the carry bit is received from the less significant
elementary addition and is propagated further to the more significant elementary
addition. Therefore, the carry_out bit corresponding to a pair of bits Xi and Yi is
calculated according to the equation:

carry_out(i) = Gi + Pi.carry_in(i-1)

For a four-bit adder the carry-outs are calculated as follows

carry_out0 = G0 + P0 . carry_in0

carry_out1 = G1 + P1 . carry_out0 = G1 + P1G0 + P1P0 . carry_in0

carry_out2 = G2 + P2G1 + P2P1G0 + P2P1P0 . carry_in0

carry_out3 = G3 + P3G2 + P3P2G1 + P3P2P1G0 + P3P2P1 . carry_in0

The set of equations above are implemented by the circuit below and a complete
adder with a look-ahead carry generator is next. The input signals need to propagate
through a maximum of 4 logic gate in such an adder as opposed to 8 and 12 logic
gates in its counterparts illustrated earlier.
 Pi is called Carry Propagate

Gi is called Carry Generate

With Pi and Gi, we obtain the sum & carry for the full adder:

Ci+1= Gi + PiCi
C1 = G0 + P0C0
C2 = G1 + P1C1
= G1 + P1(G0 + P0C0)
= G1 + P1G0 + P1P0C0
C3 = G2 + P2C2
= G2 + P2(G1 + P1G0 + P1P0C0)
= G2 + P2G1 + P2P1G0 + P2P1P0C0
Carry no longer depend on its previous stage

Look-Ahead Carry Generator

 Speed: 2 gate delays for all carry
Cost: more gates

Sums can be calculated from the following equations, where carryout is taken from
the carry calculated in the above circuit.

sum_out0 = X 0 Y0 carry_out0

sum_out1 = X 1 Y1 carry_out1
 sum_out2 = X 2 Y2 carry_out2

sum_out3 = X 3 Y3 carry_out3

MSI Adder
Adders are available in Medium Scale Integration (MSI) devices
Both TTL and CMOS are available, e.g.
74183: TTL 1-bit Full Adder
7482: TTL 4-bit Carry-Look-Ahead Adder
4008: CMOS 4-bit Carry-Look-Ahead Adder
74182: 4-bit Look-Ahead Carry Generator
4-bit Addition
 To add 2 4-bit numbers: Z = X + Y

8- bit Addition

To add 2 8-bit numbers: Z = X + Y

Subtractor

Subtractor circuits take two binary numbers as input and subtract one binary number
input from the other binary number input. Similar to adders, it gives out two outputs,
difference and borrow (carry-in the case of Adder). There are two types of
subtractors.

 Half Subtractor
 Full Subtractor

Half Subtractor
 The half-subtractor is a combinational circuit which is used to perform subtraction of
two bits. It has two inputs, X (minuend) and Y (subtrahend) and two outputs D
(difference) and B (borrow). The logic symbol and truth table are shown below.

Symbol

Truth Table

X Y D B
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 0

From the above table we can draw the Kmap as shown below for "difference" and "
borrow". The boolean expression for the difference and Borrow can be written.

From the equation we can draw the half-subtractor as shown in the figure below.
Full Subtractor

A full subtractor is a combinational circuit that performs subtraction involving three

bits, namely minuend, subtrahend, and borrow-in. The logic symbol and truth table
are shown below.

Symbol

Truth Table

X Y Bin D Bout
0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
1 0 0 1 0
1 0 1 0 0
1 1 0 0 0
1 1 1 1 1

From above table we can draw the Kmap as shown below for "difference" and
"borrow".
The boolean expression for difference and borrow can be written as

D = X'Y'Bin + X'YBin' + XY'Bin' + XYBin

= (X'Y' + XY)Bin + (X'Y + XY')Bin'

= (X Y)'Bin + (X Y)Bin'

=X Y Bin

Bout = X'.Y + X'.Bin + Y.Bin

From the equation we can draw the full-subtractor as shown in figure below.

Full-subtractor circuit is more or less same as a full-adder with slight

modification.
Parallel Binary Subtractor

Parallel binary subtractor can be implemented by cascading several full-subtractors.

Implementation and associated problems are those of a parallel binary adder, seen
before in parallel binary adder section.

Below is the block level representation of a 4-bit parallel binary subtractor, which
subtracts 4-bit Y3Y2Y1Y0 from 4-bit X3X2X1X0. It has 4-bit difference output
D3D2D1D0 with borrow output Bout.

A serial subtractor can be obtained by converting the serial adder using the 2's
complement system. The subtrahend is stored in the Y register and must be 2's
complemented before it is added to the minuend stored in the X register.

The circuit for a 4-bit serial subtractor using full-adder is shown in the figure below.
Comparator
Comparator compares binary numbers.

Logic comparing 2 bits: a and b

Magnitude Comparator
Comparator compares binary numbers
4-bit Magnitude Comparator:
Inputs: A3A2A1A0 & B3B2B1B0
Outputs: Y A>B, Y A<B, Y A=B
For each bit, let:
Si = AiBi + Ai’Bi’ = (AiBi’ + Ai’Bi)’
Si is true when Ai = Bi
For A = B, we must have:
A3=B3 and A2=B2 and A1=B1 and A0=B0
Hence, Y A=B = S3•S2•S1•S0 136
Logic For A > B
For A > B, there are 4 cases:
1. A3B3 is 10 and A2 A1A0 & B2B1B0 can be anything:
A=1xxx, B=0xxx
2. A3=B3 and A2B2 is 10 and A1 A0 & B1B0 can be
anything: A=11xx, B=10xx or A=01xx, B=00xx
3. A3=B3 and A2=B2 and A1B1=10 and A0B0 is xx: e.g.
A=011x, B=010x
 4. A3=B3 and A2=B2 and A1=B1 and A0B0 is 10: e.g.
A=1011, B=1010

Y A>B=A3B3’+S3A2B2’+S3S2A1B1’+S3S2S1A0B0’

Logic For A < B

For A < B, there are also 4 cases:

1) A3B3 is 01 and A2 A1 A0 & B2B1B0 can be anything:
1. A=0xxx, B=1xxx
2) A3=B3 and A2B2 is 01 and A1A0 & B1B0 can be
1. anything: A=10xx, B=11xx or A=00xx, B=01xx
3) A3=B3 and A2=B2 and A1B1=01 and A0B0 is xx: e.g.
1. A=110x, B=111x
4) A3=B3 and A2=B2 and A1=B1 and A0B0 is 01: e.g.
1. A=1000, B=1001

Y A<B=A3 ’B3+S3A2 ’B2+S3S2A1 ’ B1+S3S2S1A0 ’ B0

4-bit Comparator Logic Circuit

MSI: 7485 4-bit Magnitude Comparator

Comparison of 4-bit Numbers

Comparison of 8 - bit Numbers

Decoder

A decoder is a multiple-input, multiple-output logic circuit that converts coded inputs

into coded outputs, where the input and output codes are different.Binary Decoder has
n inputs and 2noutputs also called as n-to-2n decoder. Inputs have all the 2n
combinations and the corresponding output will be activated for each input
combinations.Decoding is necessary in applications such as data multiplexing, 7
segment display and memory address decoding. Enable inputs must be on for the
decoder to function, otherwise its outputs assume a single "disabled" output code
word. Figure below shows the pseudo block of a decoder.

A binary decoder has n inputs and 2n outputs. Only one output is active at any one
time, corresponding to the input value. Figure below shows a representation of Binary
n-to-2n decoder
 e.g. 3-to-8 decoder has 3 inputs and 8 outputs

3-to-8 Decoder
Function Table

3-to-8 Decoder Logic Circuit

2- to-4 Decoder with Output Enable

Implement Logic Function with Decoder

 Any n-variable logic function, in canonical sum-of-minterms form can be

implemented using a single n-to-2n decoder to generate the minterms, and an OR gate
to form the sum.
 The output lines of the decoder corresponding to the minterms of the function are
used as inputs to the or gate.
 Any combinational circuit with n inputs and m outputs can be implemented with an n-
to-2n decoder with m OR gates.
 Suitable when a circuit has many outputs, and each output function is expressed with
few minterms.

(Ex) Full adder using decoder

S(x, y, z) = (1,2,4,7)

C(x, y, z) = (3,5,6,7)

Truth Table

X Y Z C S
0 0 0 0 0
Fr 0 0 1 0 1
o
0 1 0 0 1
m
th 0 1 1 1 0
e 1 0 0 0 1
tru 1 0 1 1 0
th 1 1 0 1 0
ta
1 1 1 1 1
bl
e
we know the values for which the sum (s) is active and also the carry (c) is active.
Thus we have the equation as shown above and a circuit can be drawn as shown
below from the equation derived.

Use a 3-to-8 decoder to implement:

f = x’y’z + xy’z + xyz
(m1 + m5 + m7)
MSI Decoders

1. 2-to-4 Decoder
2. 3-to-8 Decoder
3. 4-to-16 Decoder
4. BCD-to-Decimal Decoder
5. BCD-to-Seven-Segment Decoder
e.g. Low Power Schottky TTL:
74LS138 3-to-8 Decoder where G1, G2A and G2B are enable pins

Logic Symbol
74LS138 3-to-8 Decoder

Implement Logic Function with74LS138

Use a 3-to-8 decoder to implement:

f = x’y’z + xy’z + xyz
(m1 + m5 + m7)
4-to-16 Decoder

Use 2 3-to-8 decoders

Inputs: D, C, B, A
Outputs: Y0 – Y15
When D = 0, top decoder is enabled
When D = 1,bottom decoderis enabled
En’ is enable

Binary Encoders
 An encoder is a combinational circuit that performs the inverse operation of a
decoder. If a device output code has fewer bits than the input code has, the device is
usually called an encoder. e.g. 2n-to-n, priority encoders.

The simplest encoder is a 2n-to-n binary encoder, where it has only one of 2n inputs =
1 and the output is the n-bit binary number corresponding to the active input. It can be
built from OR gates

e.g. 4-to-2 Encoder

Octal-to-Binary Encoder

Octal-to-Binary take 8 inputs and provides 3 outputs, thus doing the opposite of what
the 3-to-8 decoder does. At any one time, only one input line has a value of 1. The
figure below shows the truth table of an Octal-to-binary encoder.

Truth Table

I0 I1 I2 I3 I4 I5 I6 I7 Y2 Y1 Y0
1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 1 1
0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0 1
 0 0 0 0 0 0 1 0 1 1 0
0 0 0 0 0 0 0 1 1 1 1

For an 8-to-3 binary encoder with inputs I0-I7 the logic expressions of the outputs
Y0-Y2 are:

Y0 = I1 + I3 + I5 + I7

Y1= I2 + I3 + I6 + I7

Y2 = I4 + I5 + I6 +I7

Based on the above equations, we can draw the circuit as shown below

Priority Encoder

If more then two inputs are active simultaneously, the output is unpredictable or
rather it is not what we expect it to be.This ambiguity is resolved if priority is
established so that only one input is encoded, no matter how many inputs are active at
a given point of time. The priority encoder includes a priority function. The operation
of the priority encoder is such that if two or more inputs are active at the same time,
the input having the highest priority will take precedence.

e.g. 4-to-2 PriorityEncoder

A3 has the highest priority
A0 has the lower priority
74148 8-to-3 Priority Encoder

16-to-4 Priority Encoder

Cascade two 74148 8-to-3 priority encoders. The Input 15 has highest priority

Multiplexer

A multiplexer (MUX) is a digital switch which connects data from one of n sources to
the output. A number of select inputs determine which data source is connected to the
output. The block diagram of MUX with n data sources of b bits wide and s bits wide
select line is shown in below figure.
 MUX acts like a digitally controlled multi-position switch where the binary code
applied to the select inputs controls the input source that will be switched on to the
output as shown in the figure below. At any given point of time only one input gets
selected and is connected to output, based on the select input signal.

The operation of a multiplexer can be better explained using a mechanical switch as

shown in the figure below. This rotary switch can touch any of the inputs, which is
connected to the output. As you can see at any given point of time only one input gets
transferred to output.

2x1 MUX

A 2 to 1 line multiplexer is shown in figure below, each 2 input lines A to B is

applied to one input of an AND gate. Selection lines S are decoded to select a
particular AND gate. The truth table for the 2:1 mux is given in the table below.
Design of a 2:1 Mux

To derive the gate level implementation of 2:1 mux we need to have truth table as s
hown in figure. And once we have the truth table, we can draw the K-map as
shown in figure for all the cases when Y is equal to '1'.

Combining the two 1' as shown in figure, we can drive the output y as shown below

Y = A.S’ + B.S

Truth Table

B A S Y
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 0 1
1 1 1 1

Kmap
 Circuit

MSI MUX
74150: 16-to-1
74153: Dual 4-to-1
74157: Quad 2-to-1
74151: 8-to-1
16-to-1 MUX

Use two 74151

D = 0 enables top MUX
D = 1 enables bottom MUX
W = Y’
= (Y1+Y2)’
= (W1’+W2’)’
= W1W2
Larger Multiplexers

Larger multiplexers can be constructed from smaller ones. An 8-to-1 multiplexer can
be constructed from smaller multiplexers as shown below.

8-to-1 multiplexer from Smaller MUX

16-to-1 multiplexer from 4:1 mux

Quadruple 2-to-1 MUX

It is 2-to-1 MUX with 4 bits for each input

There is 1 output of 4 bits
There is 1 select signal
When 1 input is selected, the whole group of 4 bits goes to the output
Quad 2-to-1 MUX

Implementing Functions Multiplexers

Any n-variable logic function can be implemented using a smaller 2n-1-to-1

multiplexer and a single inverter (e.g 4-to-1 mux to implement 3 variable functions)
as follows.

Express function in canonical sum-of-minterms form. Choose n-1 variables as inputs

to mux select lines. Construct the truth table for the function, but grouping inputs by
selection line values (i.e select lines as most significant inputs).
 Determine multiplexer input line i values by comparing the remaining input variable
and the function F for the corresponding selection lines value i.

We have four possible mux input line i values:

 Connect to 0 if the function is 0 for both values of remaining variable.

 Connect to 1 if the function is 1 for both values of remaining variable.
 Connect to remaining variable if function is equal to the remaining variable.
 Connect to the inverted remaining variable if the function is equal to the
remaining variable inverted

3-variable Function Using 8-to-1 mux

Implement the function F(X,Y,Z) = S(1,3,5,6) using an 8-to-1 mux. Connect the input
variables X, Y, Z to mux select lines. Mux data input lines 1, 3, 5, 6 that correspond
to the function minterms are connected to 1. The remaining mux data input lines 0, 2,
4, 7 are connected to 0.

3- variable Function Using 4-to-1 mux

Implement the function F(X,Y,Z) = S(0,1,3,6) using a single 4-to-1 mux and an
inverter. We choose the two most significant inputs X, Y as mux select lines.

Truth Table

Select i X Y Z F Mux Input i

0 0 0 0 1 1
0 0 0 1 1 1
1 0 1 0 0 Z
1 0 1 1 1 Z
2 1 0 0 0 0
2 1 0 1 0 0
3 1 1 0 1 Z'
3 1 1 1 0 Z'

We determine multiplexer input line i values by comparing the remaining input

variable Z and the function F for the corresponding selection lines value i

 when XY=00 the function F is 1 (for both Z=0, Z=1) thus mux input0 = 1
 when XY=01 the function F is Z thus mux input1 = Z
 when XY=10 the function F is 0 (for both Z=0, Z=1) thus mux input2 = 0
 when XY=11 the function F is Z' thus mux input3 = Z'
Example for logic function implementation using MUX

De-multiplexers
 They are digital switches which connect data from one input source to one of n
outputs.Usually implemented by using n-to-2n binary decoders where the decoder
enable line is used for data input of the de-multiplexer.The figure below shows a de-
multiplexer block diagram which has got s-bits-wide select input, one b-bits-wide
data input and n b-bits-wide outputs.

The operation of a de-multiplexer can be better explained using a mechanical switch

as shown in the figure below. This rotary switch can touch any of the outputs, which
is connected to the input. As you can see at any given point of time only one output
gets connected to input.

1-to-4 De-multiplexer
 SYNCHRONOUS SEQUENTIAL CIRCUIT

Introduction

Combinational logic refers to circuits whose output is strictly depended on the present
value of the inputs. As soon as inputs are changed, the information about the previous
inputs is lost, that is, combinational logics circuits have no memory. In many
applications, information regarding input values at a certain instant of time is required at
some future time. Although every digital system is likely to have combinational circuits,
most systems encountered in practice also include memory elements, which require that
the system be described in terms of sequential logic. Circuits whose outputs depends not
only on the present input value but also the past input value are known as sequential
logic circuits. The mathematical model of a sequential circuit is usually referred to as a
sequential machine.

A general block diagram of a sequential circuit is shown below in Figure 1.

Figure 1. Block Diagram of Sequential Circuit.

The diagram consists of combinational circuit to which memory elements are connected
to form a feedback path. The memory elements are devices capable of storing binary
information within them. The combinational part of the circuit receives two sets of input
signals: one is primary (coming from the circuit environment) and secondary (coming
from memory elements). The particular combination of secondary input variables at a
given time is called the present state of the circuit. The secondary input variables are
also know as the state variables.

The block diagram shows that the external outputs in a sequential circuit are a function
not only of external inputs but also of the present state of the memory elements. The next
state of the memory elements is also a function of external inputs and the present state.
Thus a sequential circuit is specified by a time sequence of inputs, outputs, and internal
states.
Synchronous and Asynchronous Operation

Sequential circuits are divided into two main types: synchronous and asynchronous.
Their classification depends on the timing of their signals.

Synchronous sequential circuits change their states and output values at discrete instants
of time, which are specified by the rising and falling edge of a free-running clock signal.
The clock signal is generally some form of square wave as shown in Figure 2 below.

Figure 2. Clock Signal

From the diagram you can see that the clock period is the time between successive
transitions in the same direction, that is, between two rising or two falling edges. State
transitions in synchronous sequential circuits are made to take place at times when the
clock is making a transition from 0 to 1 (rising edge) or from 1 to 0 (falling edge).
Between successive clock pulses there is no change in the information stored in memory.

The reciprocal of the clock period is referred to as the clock frequency. The clock width
is defined as the time during which the value of the clock signal is equal to 1. The ratio of
the clock width and clock period is referred to as the duty cycle. A clock signal is said to
be active high if the state changes occur at the clock's rising edge or during the clock
width. Otherwise, the clock is said to be active low. Synchronous sequential circuits are
also known as clocked sequential circuits.

The memory elements used in synchronous sequential circuits are usually flip-flops.
These circuits are binary cells capable of storing one bit of information. A flip-flop
circuit has two outputs, one for the normal value and one for the complement value of the
bit stored in it. Binary information can enter a flip-flop in a variety of ways, a fact which
give rise to the different types of flip-flops. For information on the different types of
basic flip-flop circuits and their logical properties, see the previous tutorial on flip-flops.

In asynchronous sequential circuits, the transition from one state to another is initiated
by the change in the primary inputs; there is no external synchronisation. The memory
commonly used in asynchronous sequential circuits are time-delayed devices, usually
implemented by feedback among logic gates. Thus, asynchronous sequential circuits may
be regarded as combinational circuits with feedback. Because of the feedback among
logic gates, asynchronous sequential circuits may, at times, become unstable due to
transient conditions. The instability problem imposes many difficulties on the designer.
Hence, they are not as commonly used as synchronous systems.
Summary of the Types of Flip-flop Behaviour

Since memory elements in sequential circuits are usually flip-flops, it is worth

summarising the behaviour of various flip-flop types before proceeding further.

All flip-flops can be divided into four basic types: SR, JK, D and T. They differ in the
number of inputs and in the response invoked by different value of input signals. The four
types of flip-flops are defined in Table 1.

Table 1. Flip-flop Types

FLIP-
FLOP FLIP-FLOP CHARACTERISTI CHARACTERISTI EXCITATION
NAM SYMBOL C TABLE C EQUATION TABLE
E
S R Q(next) Q(next
Q S R
)
0 0 Q
Q(next) = S + R'Q 0 0 0 X
SR 0 1 0
0 1 1 0
1 0 1 SR = 0
1 0 0 1
1 1 ? 1 1 X 0

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

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

Q Q(next) T
T Q(next) 0 0 0
T 0 Q Q(next) = TQ' + T'Q 0 1 1
1 Q' 1 0 1
1 1 0
Each of these flip-flops can be uniquely described by its graphical symbol, its
characteristic table, its characteristic equation or excitation table. All flip-flops have
output signals Q and Q'.

The characteristic table in the third column of Table 1 defines the state of each flip-flop
as a function of its inputs and previous state. Q refers to the present state and Q(next)
refers to the next state after the occurrence of the clock pulse. The characteristic table for
the RS flip-flop shows that the next state is equal to the present state when both inputs S
and R are equal to 0. When R=1, the next clock pulse clears the flip-flop. When S=1, the
flip-flop output Q is set to 1. The equation mark (?) for the next state when S and R are
both equal to 1 designates an indeterminate next state.

The characteristic table for the JK flip-flop is the same as that of the RS when J and K are
replaced by S and R respectively, except for the indeterminate case. When both J and K
are equal to 1, the next state is equal to the complement of the present state, that is,
Q(next) = Q'.

The next state of the D flip-flop is completely dependent on the input D and independent
of the present state.

The next state for the T flip-flop is the same as the present state Q if T=0 and
complemented if T=1.

The characteristic table is useful during the analysis of sequential circuits when the value
of flip-flop inputs are known and we want to find the value of the flip-flop output Q after
the rising edge of the clock signal. As with any other truth table, we can use the map
method to derive the characteristic equation for each flip-flop, which are shown in the
third column of Table 1.

During the design process we usually know the transition from present state to the next
state and wish to find the flip-flop input conditions that will cause the required transition.
For this reason we will need a table that lists the required inputs for a given change of
state. Such a list is called the excitation table, which is shown in the fourth column of
Table 1. There are four possible transitions from present state to the next state. The
required input conditions are derived from the information available in the characteristic
table. The symbol X in the table represents a "don't care" condition, that is, it does not
matter whether the input is 1 or 0.

State Tables and State Diagrams

We have examined a general model for sequential circuits. In this model the effect of all
previous inputs on the outputs is represented by a state of the circuit. Thus, the output of
the circuit at any time depends upon its current state and the input. These also determine
the next state of the circuit. The relationship that exists among the inputs, outputs, present
states and next states can be specified by either the state table or the state diagram.

State Table
The state table representation of a sequential circuit consists of three sections labelled
present state, next state and output. The present state designates the state of flip-flops
before the occurrence of a clock pulse. The next state shows the states of flip-flops after
the clock pulse, and the output section lists the value of the output variables during the
present state.

State Diagram

In addition to graphical symbols, tables or equations, flip-flops can also be represented

graphically by a state diagram. In this diagram, a state is represented by a circle, and the
transition between states is indicated by directed lines (or arcs) connecting the circles. An
example of a state diagram is shown in Figure 3 below.

Figure 3. State Diagram

The binary number inside each circle identifies the state the circle represents. The
directed lines are labelled with two binary numbers separated by a slash (/). The input
value that causes the state transition is labelled first. The number after the slash symbol /
gives the value of the output. For example, the directed line from state 00 to 01 is labelled
1/0, meaning that, if the sequential circuit is in a present state and the input is 1, then the
next state is 01 and the output is 0. If it is in a present state 00 and the input is 0, it will
remain in that state. A directed line connecting a circle with itself indicates that no
change of state occurs. The state diagram provides exactly the same information as the
state table and is obtained directly from the state table.

Example: This example is taken from P. K. Lala, Practical Digital Logic Design and
Testing, Prentice Hall, 1996, p.155.

Consider a sequential circuit shown in Figure 4. It has one input x, one output Z and two
state variables Q1Q2 (thus having four possible present states 00, 01, 10, 11).
 Figure 4. A Sequential Circuit

The behaviour of the circuit is determined by the following Boolean expressions:

Z = x*Q1
D1 = x' + Q1
D2 = x*Q2' + x'*Q1'

These equations can be used to form the state table. Suppose the present state (i.e. Q1Q2)
= 00 and input x = 0. Under these conditions, we get Z = 0, D1 = 1, and D2 = 1. Thus the
next state of the circuit D1D2 = 11, and this will be the present state after the clock pulse
has been applied. The output of the circuit corresponding to the present state Q1Q2 = 00
and x = 1 is Z = 0. This data is entered into the state table as shown in Table 2.

Table 2. State table for the sequential circuit in Figure 4.

Present
Next State Output
State
x=0 x=1 x=0 x=1
Q1Q2
00 11 01 0 0
01 11 00 0 0
10 10 11 0 1
11 10 10 0 1

The state diagram for the sequential circuit in Figure 4 is shown in Figure 5.
 Figure 5. State Diagram of circuit in Figure 4.

State Diagrams of Various Flip-flops

Table 3 shows the state diagrams of the four types of flip-flops.

 NAME STATE DIAGRAM

SR

All four flip-flops

have the JK same
number of states and
transitions. Each flip-
flop is in the set state
when Q=1 and in the
reset state when Q=0.
Also, each flip-flop
can move D from one
state to another, or
it can re- enter the
same state. The only
difference between the
four types lies in the
values of T input
signals that cause these
transitions.

A state diagram is
a very convenient way to visualise the operation of a flip-flop or even of large sequential
components.

Analysis of Sequential Circuits

The behaviour of a sequential circuit is determined from the inputs, the outputs and the
states of its flip-flops. Both the output and the next state are a function of the inputs and
the present state.

The suggested analysis procedure of a sequential circuit is set out in Figure 6 below.
 Figure 6. Analysis procedure of sequential circuits.

We start with the logic schematic from which we can derive excitation equations for each
flip-flop input. Then, to obtain next-state equations, we insert the excitation equations
into the characteristic equations. The output equations can be derived from the schematic,
and once we have our output and next-state equations, we can generate the next-state and
output tables as well as state diagrams. When we reach this stage, we use either the table
or the state diagram to develop a timing diagram which can be verified through
simulation.

This example is taken from D. D. Gajski, Principles of Digital Design, Prentice Hall,
1997, p.230.
Example 1.1. Modulo-4 counter

Derive the state table and state diagram for the sequential circuit shown in Figure 7.

Figure 7.
Logic
schematic
of a
sequential
circuit.

SOLUTION:

STEP 1: First we derive the Boolean expressions for the inputs of each flip-flops in the
schematic, in terms of external input Cnt and the flip-flop outputs Q1 and Q0. Since there
are two D flip-flops in this example, we derive two expressions for D1 and D0:

D0 = Cnt Q0 = Cnt'*Q0 + Cnt*Q0'

D1 = Cnt'*Q1 + Cnt*Q1'*Q0 + Cnt*Q1*Q0'

These Boolean expressions are called excitation equations since they represent the
inputs to the flip-flops of the sequential circuit in the next clock cycle.

STEP 2: Derive the next-state equations by converting these excitation equations into
flip-flop characteristic equations. In the case of D flip-flops, Q(next) = D. Therefore the
next state equal the excitation equations.

Q0(next) = D0 = Cnt'*Q0 + Cnt*Q0'

Q1(next) = D1 = Cnt'*Q1 + Cnt*Q1'*Q0 + Cnt*Q1*Q0'

STEP 3: Now convert these next-state equations into tabular form called the next-state
table.

Present State Next State

Q1Q0 Cnt = 0 Cnt = 1
00 00 01
01 01 10
10 10 11
11 11 00

Each row is corresponding to a state of the sequential circuit and each column represents
one set of input values. Since we have two flip-flops, the number of possible states is four
- that is, Q1Q0 can be equal to 00, 01, 10, or 11. These are present states as shown in the
table.

For the next state part of the table, each entry defines the value of the sequential circuit in
the next clock cycle after the rising edge of the Clk. Since this value depends on the
present state and the value of the input signals, the next state table will contain one
column for each assignment of binary values to the input signals. In this example, since
there is only one input signal, Cnt, the next-state table shown has only two columns,
corresponding to Cnt = 0 and Cnt = 1.

Note that each entry in the next-state table indicates the values of the flip-flops in the next
state if their value in the present state is in the row header and the input values in the
column header.

Each of these next-state values has been computed from the next-state equations in STEP
2.

STEP 4: The state diagram is generated directly from the next-state table, shown in
Figure 8.

Figure 8. State diagram

Each arc is labelled with the values of the input signals that cause the transition from the
present state (the source of the arc) to the next state (the destination of the arc).

In general, the number of states in a next-state table or a state diagram will equal 2 m ,
where m is the number of flip-flops. Similarly, the number of arcs will equal 2m x 2k ,
where k is the number of binary input signals. Therefore, in the state diagram, there must
be four states and eight transitions. Following these transition arcs, we can see that as
long as Cnt = 1, the sequential circuit goes through the states in the following sequence:
0, 1, 2, 3, 0, 1, 2, On the other hand, when Cnt = 0, the circuit stays in its present state
until Cnt changes to 1, at which the counting continues.

Since this sequence is characteristic of modulo-4 counting, we can conclude that the
sequential circuit in Figure 7 is a modulo-4 counter with one control signal, Cnt, which
enables counting when Cnt = 1 and disables it when Cnt = 0.

Below, we show a timing diagram, representing four clock cycles, which enables us to
observe the behaviour of the counter in greater detail.

Figure
9.
Timing
Diagram

In this timing diagram we have assumed that Cnt is asserted in clock cycle 0 at t 0 and is
disasserted in clock cycle 3 at time t 4. We have also assumed that the counter is in state
Q1Q0 = 00 in the clock cycle 0. Note that on the clock's rising edge, at t 1, the counter will
go to state Q1Q0 = 01 with a slight propagation delay; in cycle 2, after t 2, to Q1Q0 = 10;
and in cycle 3, after t 3 to Q1Q0 = 11. Since Cnt becomes 0 at t 4, we know that the counter
will stay in state Q1Q0 = 11 in the next clock cycle.

In Example 1.1 we demonstrated the analysis of a sequential circuit that has no outputs
by developing a next-state table and state diagram which describes only the states and the
transitions from one state to the next. In the next example we complicate our analysis by
adding output signals, which means that we have to upgrade the next-state table and the
state diagram to identify the value of output signals in each state.

This example is taken from D. D. Gajski, Principles of Digital Design, Prentice Hall,
1997, p.234.

Example 1.2

Derive the next state, the output table and the state diagram for the sequential circuit
shown in Figure 10.
 Figure 10. Logic schematic of a sequential circuit.

SOLUTION:

The input combinational logic in Figure 10 is the same as in Example 1.1, so the
excitation and the next-state equations will be the same as in Example 1.1.

Excitation equations:

D0 = Cnt Q0 = Cnt'*Q0 + Cnt*Q0'

D0 = Cnt'*Q1 + Cnt*Q1'*Q0 + Cnt*Q1*Q0'

Next-state equations:

Q0(next) = D0 = Cnt'*Q0 + Cnt*Q0'

Q1(next) = D0 = Cnt'*Q1 + Cnt*Q1'*Q0 + Cnt*Q1*Q0'

In addition, however, we have computed the output equation.

Output equation: Y = Q1Q0

As this equation shows, the output Y will equal to 1 when the counter is in state Q1Q0 =
11, and it will stay 1 as long as the counter stays in that state.

Next-state and output table:

Present State Next State Output

Q1 Q0 Cnt=0 Cnt=1 Z
00 00 01 0
01 01 10 0
10 10 11 0
11 11 00 1

State diagram:

Figure 11. State diagram of sequential circuit in Figure 10.

Timing diagram:

Figure 12. Timing diagram of sequential circuit in Figure 10.

Note that the counter will reach the state Q1Q0 = 11 only in the third clock cycle, so the
output Y will equal 1 after Q0 changes to 1. Since counting is disabled in the third clock
cycle, the counter will stay in the state Q1Q0 = 11 and Y will stay asserted in all
succeeding clock cycles until counting is enabled again.

Design of Sequential Circuits

The design of a synchronous sequential circuit starts from a set of specifications and
culminates in a logic diagram or a list of Boolean functions from which a logic diagram
can be obtained. In contrast to a combinational logic, which is fully specified by a truth
table, a sequential circuit requires a state table for its specification. The first step in the
design of sequential circuits is to obtain a state table or an equivalence representation,
such as a state diagram.

A synchronous sequential circuit is made up of flip-flops and combinational gates. The

design of the circuit consists of choosing the flip-flops and then finding the
combinational structure which, together with the flip-flops, produces a circuit that fulfils
the required specifications. The number of flip-flops is determined from the number of
states needed in the circuit.

The recommended steps for the design of sequential circuits are set out below.
.State Reduction

Any design process must consider the problem of minimising the cost of the final circuit.
The two most obvious cost reductions are reductions in the number of flip-flops and the
number of gates.

The number of states in a sequential circuit is closely related to the complexity of the
resulting circuit. It is therefore desirable to know when two or more states are equivalent
in all aspects. The process of eliminating the equivalent or redundant states from a state
table/diagram is known as state reduction.

Example: Let us consider the state table of a sequential circuit shown in Table 6.

Table 6. State table

Output
Next State
Present State x =x =
x=0 x=1
0 1
A B C 1 0
B F D 0 0
C D E 1 1
D F E 0 1
E A D 0 0
F B C 1 0

It can be seen from the table that the present state A and F both have the same next states,
B (when x=0) and C (when x=1). They also produce the same output 1 (when x=0) and 0
(when x=1). Therefore states A and F are equivalent. Thus one of the states, A or F can
be removed from the state table. For example, if we remove row F from the table and
replace all F's by A's in the columns, the state table is modified as shown in Table 7.

Table 7. State F removed

Output
Next State
Present State x =x =
x=0 x=1
0 1
A B C 1 0
B A D 0 0
C D E 1 1
D A E 0 1
E A D 0 0

It is apparent that states B and E are equivalent. Removing E and replacing E's by B's
results in the reduce table shown in Table 8.

Table 8. Reduced state table

Output
Next State
Present State x =x =
x=0 x=1
0 1
A B C 1 0
B A D 0 0
C D B 1 1
D A B 0 1

The removal of equivalent states has reduced the number of states in the circuit from six
to four. Two states are considered to be equivalent if and only if for every input
sequence the circuit produces the same output sequence irrespective of which one of the
two states is the starting state.
Design of Sequential Circuits

This example is taken from M. M. Mano, Digital Design, Prentice Hall, 1984, p.235.

Example 1.3 We wish to design a synchronous sequential circuit whose state diagram is
shown in Figure 13. The type of flip-flop to be use is J-K.

Figure 13. State diagram

From the state diagram, we can generate the state table shown in Table 9. Note
that there is no output section for this circuit. Two flip-flops are needed to represent the
four states and are designated Q0Q1. The input variable is labelled x.

Table 9. State table.

Present State Next State

Q0 Q1 x=0 x=1
00 00 01
01 10 01
10 10 11
11 11 00

We shall now derive the excitation table and the combinational structure. The table is
now arranged in a different form shown in Table 11, where the present state and input
variables are arranged in the form of a truth table. Remember, the excitable for the JK
flip-flop was derive in

Table 10. Excitation table for JK flip-flop

Output Transitions Flip-flop inputs

Q JK
0 0 0 X
0 1 1 X
1 0 X 1
1 1 X 0

Table 11. Excitation table of the circuit

Present State Next State Input Flip-flop Inputs

Q0 Q1 Q0 Q1 x J0 K0 J1 K1
00 00 0 0X 0X
00 01 1 0X 1X
01 10 0 1X X1
01 01 1 0X X0
10 10 0 X0 0X
10 11 1 X0 1X
11 11 0 X0 X0
11 00 1 X1 X1

In the first row of Table 11, we have a transition for flip-flop Q0 from 0 in the present
state to 0 in the next state. In Table 10 we find that a transition of states from 0 to 0
requires that input J = 0 and input K = X. So 0 and X are copied in the first row under J0
and K0 respectively. Since the first row also shows a transition for the flip-flop Q1 from
0 in the present state to 0 in the next state, 0 and X are copied in the first row under J1
and K1. This process is continued for each row of the table and for each flip-flop, with
the input conditions as specified in Table 10.

The simplified Boolean functions for the combinational circuit can now be derived. The
input variables are Q0, Q1, and x; the output are the variables J0, K0, J1 and K1. The
information from the truth table is plotted on the Karnaugh maps shown in Figure 14.

Figure 14. Karnaugh Maps

The flip-flop input functions are derived:

J0 = Q1*x' K0 = Q1*x
J1 = x K1 = Q0'*x' + Q0*x = Q0

Note: the symbol -NOR.

The logic diagram is drawn in Figure 15.

Figure 15. Logic diagram of the sequential circuit.

Design of Sequential Circuits

This example is taken from P. K. Lala, Practical Digital Logic Design and Testing,
Prentice Hall, 1996, p.176.

Example 1.4 Design a sequential circuit whose state tables are specified in Table 12,
using D flip-flops.

Table 12. State table of a sequential circuit.

Present State Next State Output

Q0 Q1 x=0 x=1 x =0 x=1
00 00 01 0 0
01 00 10 0 0
10 11 10 0 0
11 00 01 0 1

Table 13. Excitation table for a D flip-flop.

Output Transitions Flip-flop inputs

Q D

0 0 0
0 1 1
1 0
0
1 1
1

Next step is to derive the excitation table for the design circuit, which is shown in Table
14. The output of the circuit is labelled Z.

Table 14. Excitation table

Flip-flop
Present State Next State Input Output
Inputs
Q0 Q1 Q0 Q1 x Z
D0 D1
00 00 0 0 0 0
00 01 1 0 1 0
01 00 0 0 0 0
01 10 1 1 0 0
10 11 0 1 1 0
10 10 1 1 0 0
11 00 0 0 0 0
11 01 1 0 1 1

Now plot the flip-flop inputs and output functions on the Karnaugh map to derive the
Boolean expressions, which is shown in Figure 16.

Figure 16. Karnaugh maps

The simplified Boolean expressions are:

D0 = Q0*Q1' + Q0'*Q1*x
D1 = Q0'*Q1'*x + Q0*Q1*x + Q0*Q1'*x'
Z = Q0*Q1*x
Finally, draw the logic diagram.

Figure 17. Logic diagram of the sequential circuit.

Design of Counters

A sequential circuit that goes through a prescribed sequence of states upon the
application of input pulses is called a counter. The input pulses, called count pulses,
may be clock pulses. In a counter, the sequence of states may follow a binary count or
any other sequence of states. Counters are found in almost all equipment containing
digital logic. They are used for counting the number of occurrences of an even and are
useful for generating timing sequences to control operations in a digital system.

Of the various sequences a counter may follow, the straight binary sequence is the
simplest and most straight forward. A counter that follows the binary sequence is called a
binary counter. An n-bit binary counter consists of n flip-flops and can count in binary
from 0 to 2n - 1.

Design of Counters

This example is taken from T. L. Floyd, Digital Fundamentals, Fourth Edition,

Macmillan Publishing, 1990, p.395.

Example 1.5 A counter is first described by a state diagram, which is shows the
sequence of states through which the counter advances when it is clocked. Figure 18
shows a state diagram of a 3-bit binary counter.
 Figure 18. State diagram of a 3-bit binary counter.

The circuit has no inputs other than the clock pulse and no outputs other than its internal
state (outputs are taken off each flip-flop in the counter). The next state of the counter
depends entirely on its present state, and the state transition occurs every time the clock
pulse occurs. Figure 19 shows the sequences of count after each clock pulse.

Fig.19 Count sequence after each pulse

Once the sequential circuit is defined by the state diagram, the next step is to obtain the
next-state table, which is derived from the state diagram in Figure 18 and is shown in
Table 15.

Table 15. State table

Present State Next State

Q2 Q1 Q0 Q2 Q1 Q0
0 0 0 0 0 1
0 0 1 0 1 0
0 1 0 0 1 1
0 1 1 1 0 0
1 0 0 1 0 1
1 0 1 1 1 0
1 1 0 1 1 1
1 1 1 0 0 0

Since there are eight states, the number of flip-flops required would be three. Now we
want to implement the counter design using JK flip-flops.

Next step is to develop an excitation table from the state table, which is shown in Table
16.

Table 16. Excitation table

Output State Transitions Flip-flop inputs

Present State Next State
Q2 Q1 Q0 Q2 Q1 Q0 J2 K2 J1 K1 J0 K0
0 0 0 0 0 1 0X 0X 1X
0 0 1 0 1 0 0X 1X X1
0 1 0 0 1 1 0X X0 1X
0 1 1 1 0 0 1X X1 X1
1 0 0 1 0 1 X0 0X 1X
1 0 1 1 1 0 X0 1X X1
1 1 0 1 1 1 X0 X0 1X
1 1 1 0 0 0 X1 X1 X1

Now transfer the JK states of the flip-flop inputs from the excitation table to Karnaugh
maps to derive a simplified Boolean expression for each flip-flop input. This is shown in
Figure 20.
 Figure 20. Karnaugh maps

The 1s in the Karnaugh maps of Figure 20 are grouped with "don't cares" and the
following expressions for the J and K inputs of each flip-flop are obtained:

J0 = K0 = 1
J1 = K1 = Q0
J2 = K2 = Q1*Q0

The final step is to implement the combinational logic from the equations and connect the
flip-flops to form the sequential circuit. The complete logic of a 3-bit binary counter is
shown in Figure 21.

Figure 21. Logic diagram of a 3-bit binary counter

Design of Counters

This example is taken from M. M. Mano, Digital Design, Prentice Hall, 1984, p.243.
Example 1.6 Design a counter specified by the state diagram in Example 1.5 using T
flip-flops. The state diagram is shown here again in Figure 22.

Figure 22. State diagram of a 3-bit binary counter.

The state table will be the same as in Example 1.5.

Now derive the excitation table from the state table, which is shown in Table 17.

Table 17. Excitation table.

Output State Transitions Flip-flop inputs

Present State Next State
Q2 Q1 Q0 Q2 Q1 Q0 T2 T1 T0
0 0 0 0 0 1 0 0 1
0 0 1 0 1 0 0 1 1
0 1 0 0 1 1 0 0 1
0 1 1 1 0 0 1 1 1
1 0 0 1 0 1 0 0 1
1 0 1 1 1 0 0 1 1
1 1 0 1 1 1 0 0 1
1 1 1 0 0 0 1 1 1

Next step is to transfer the flip-flop input functions to Karnaugh maps to derive a
simplified Boolean expressions, which is shown in Figure 23.
 Figure 23. Karnaugh maps

The following expressions are obtained:

T0 = 1; T1 = Q0; T2 = Q1*Q0

Finally, draw the logic diagram of the circuit from the expressions obtained. The
complete logic diagram of the counter is shown in Figure 24.

Figure 24. Logic diagram of 3-bit binary counter.

Now that you have reached the end of the tutorial, you should be able to understand the
basic concept of sequential circuits. You should be able to analyse and design a basic
sequential circuit. Now you can practice some of the exercises using the analysis and
design procedures shown in the examples.

Exercises

You can try some of these exercises which covers the analysis and design of sequential
circuits.

Analysis of Sequential Circuits.

1. Derive a) excitation equations, b) next state equations, c) a state/output table, and d)

a state diagram for the circuit shown in Figure 1.1. Draw the timing diagram of the
circuit.
 Figure 1.1

2. Derive a) excitation equations, b) next state equations, c) a state/output table, and d)

a state diagram for the circuit shown in Figure 1.2.

Figure 1.2

3. Derive a) excitation equations, b) next state equations, c) a state/output table, and d)

a state diagram for the circuit shown in Figure 1.3.

Figure 1.3

4. Derive the state output and state diagran for the sequential circuit shown in Figure
1.4.
 Figure 1.4

5. A sequential circuit uses two D flip-flops as memory elements. The behaviour of the
circuit is described by the following equations:

D1 = Q1 + x'*Q2
D2 = x*Q1' + x'*Q2
Z = x'*Q1*Q2 + x*Q1'*Q2'

Derive the state table and draw the state diagram of the circuit.

Design of Sequential Circuits.

6. Design a sequential circuit specified by Table 6.1, using JK flip-flops.

Table 6.1

Present State Next State Output

Q0 Q1 x=0 x=1 x=0 x=1
00 00 01 0 0
01 00 10 0 0
10 11 10 0 0
11 00 01 0 1

7. Design the sequential circuit in question 6, using T flip-flops.

8. Design a mod-5 counter which has the following binary sequence: 0, 1, 2, 3, 4. Use
JK flip-flops.

9. Design a counter that has the following repeated binary sequence: 0, 1, 2, 3, 4, 5, 6,

7. Use RS flip-flops.
10. Design a counter with the following binary sequence: 1, 2, 5, 7 and repeat. Use JK
flip-flops.

11. Design a counter with the following repeated binary sequence: 0, 4, 2, 1, 6. Use T
flip-flops.

12. Design a counter that counts in the sequence 0, 1, 3, 6, 10, 15, using four a) D, b) SR,
c) JK and d) T flip-flops.
 UNIT – IV
ASYNCHRONOUS SEQUENTIAL
CIRCUITS

1
 Digital Circuits

Combinational Sequential
Circuits Circuits

Synchronous Asynchronous

2
 Sequential circuits
Inputs
Outputs
Combinational
circuits Memory
Elements

3
Sequential networks unsuitable
situations

• The network has inputs which may change

at any time and which cannot be synchronized
with a clock.
• Network to operate as fast as possible

4
Asynchronous Sequential Circuits
n Input m Output
Variables Variables

xn Zm
Combinational
x1 Z1
Circuit Design

y0 Y0
delay
Secondary Variables Excitaion Variables
(present State) (next state)
delay

yk Yk
delay

5
Asynchronous Sequential
Circuits
Modes of operation

Fundamental mode

Input signals will be changed only when the

circuit is in a stable state.
(no internal signals are changing)

Input signals are considered as levels

6
 Fundamental Mode Model
A
B
A Q Q+
Delay

7
Analysis of asynchronous sequential
circuits
S1 = X Q2;
S2 = Q1;
S2 Q2
S1 Q1 R1 = X Q 2 ;
R2 = Q1
R1 Q1 R2 Q2
X

8
S1 = X Q2; S2 = Q1;
R1 = X Q2 ; R2 = Q1;
Characteristic equation:
Q1+ = S1 + R1 Q1 Q2+ = S2 + R2 Q2
= XQ2 + XQ2Q1 = Q1 + Q1Q2
∴ Q1+ = X Q 2; ∴ Q2+ = Q 1

9
Transition (or) Flow Table
X
QQ 0 1
1 2
00 10
+
∴ Q 1 = X Q2;
00
01 00
0
0 ∴ Q + =Q
11 01 01 2 1

10 01 11

10
Asynchronous Sequential Circuit
Design - Steps
1). Primitive flow table
2). State reduction
3). State assignment
4). Output assignment
5). Realization using logic gates

11
Design Example:
Design a T Flip Flop where the flip flop
has two inputs T and P. The FF will
change state if T = 1 when the P input
changes from 1 to 0. Under all other
input conditions the FF Output Q
should remain constant. Assume that T
and P do not change simultaneously.

12
 Step 1: Primitive Flow Table
Assumptions:
• One Stable state per row.
• Only one input variable changes at
a time.
• Every input change must result in
a state change.

13
 TP
Row 00 01 11 10 Q
1 1 2 - 3 0
2 1 2 4 - 0
3 1 - 4 3 0
4 - 2 4 5 0
5 6 - 7 5 1
6 6 8 - 5 1
7 - 8 7 3 1
8 6 8 7 - 1
14
 Step 2: State Reduction
Necessity :

To reduce number of rows which in

turn reduces the number of state
variables in the hardware
implementation.

15
Steps to reduce number of rows

• To find equivalent stable total

states

• Merging of rows

16
Definition :
Two stable total states are equivalent
if,
i) Inputs are same.
ii) Outputs are same.
iii) Their next states are equivalent
for each possible next input.
17
Numbe 00 01 11 10 WZ
r
1 1 7 - 4 1 1
2 2 5 - 4 0 1
3 - 7 3 11 1 0
4 2 - 3 4 0 0
5 6 5 9 - 1 1
6 6 7 - 11 0 1
7 1 7 14 - 1 0
8 8 12 - 4 0 1
9 - 7 9 13 0 1
10 - 7 10 4 1 0
11 8 - 10 11 0 0
12 6 12 9 - 1 1
13 8 - 14 13 1 1
14 - 12 14 11 0 0 18
2 ≠ 6 , 6 ≠ 8, 5 ≠ 7, 7 ≠ 12, 3 ≠ 9, 9 ≠ 10,
9 ≠ 14, 10 ≠ 14, 11 ≠ 13
2 = 8 , 5 = 12, 3 = 10 and 4 = 11

19
 Numbe 00 01 11 10 WZ
r
1 1 7 - 4 1 1
2 2 5 - 4 0 1
3 - 7 3 114 1 0
4 2 - 3 4 0 0
2=8 5 6 5 9 - 1 1
3=10 6 6 7 - 11 4 0 1
7 1 7 14 - 1 0
4=11
8 8 12 - 4 0 1
5=12 9 - 7 9 13 0 1
10 - 7 10 4 1 0
11 8 - 10 11 0 0
12 6 12 9 - 1 1
13 82 13 1 1
20
14 - 12 5 14 114 0 0
Row XY
Number 00 01 11 10 WZ
1 1 7 - 4 1 1
2 2 5 - 4 0 1
3 - 7 3 4 1 0
4 2 - 3 4 0 0
5 6 5 9 - 1 1
6 6 7 - 4 0 1
7 1 7 14 - 1 0
9 - 7 9 13 0 1
13 2 - 14 13 1 1
14 - 5 14 4 0 0
21
 State Reduction
TP
Row 00 01 11 10 Q
1 1 2 - 3 0 1 ≠6
2 1 2 4 - 0 2≠8
3 1 - 4 3 0
4 - 2 4 5 0 4≠7
5 6 - 7 5 1 3≠5
6 6 8 - 5 1
7 - 8 7 3 1
8 6 8 7 - 1
22
 Merging
TP
Row 00 01 11 10 Q
1 1 2 - 3 0 1
8
2 1 2 4 - 0
3 1 - 4 3 0 2
4 - 2 4 5 07
3
5 6 - 7 5 1
6 6 8 - 5 1 6
7 - 8 7 3 1 5 4
8 6 8 7 - 1
Rows (1,2,3) can be merged
Rows (5,6,8) can be merged. 23
 MERGED ROWS
TP Q
Row 00 01 11 10 00 01 11 10

1,2,3 1 2 4 3

4 - 2 4 5
5,6,8 6 8 7 5

7 - 8 7 3

24
 OUTPUT FILLING
TP Q
Row 00 01 11 10 00 01 11 10

1,2,3 1 2 4 3 0 0 0 0

4 - 2 4 5 X 0 0 0
5,6,8 6 8 7 5 1 1 1 1

7 - 8 7 3 X 1 1 1

25
 Step 3 : State Assignment
TP Q
Row 00 01 11 10 00 01 11 10
1,2,3 1 2 4 3 0 0 0 0
4 - 2 4 5 X 0 0 0
5,6,8 6 8 7 5 1 1 1 1
7 - 8 7 3 X 1 1 1

1) (1,2,3) and 4 should have adjacent assignment

2) 4 and (5,6,8) should have adjacent assignment
3) (5,6,8) and 7 should have adjacent assignment
4) 7 and (1,2,3) should have adjacent assignment
26
 State Assignment contd...
1) (1,2,3) and 4 should have adjacent assignment
2) 4 and (5,6,8) should have adjacent assignment
3) (5,6,8) and 7 should have adjacent assignment
4) 7 and (1,2,3) should have adjacent assignment

Q2
0 1 1) States (1,2,3) → Q1Q2 = 00
Q1
7 2) State 4 → Q1Q2 = 10
0 (1,2,3)
4 3) State 7 → Q1Q2 = 01
1 (5,6,8)
4) States (5,6,8) → Q1Q2 = 11
27
 TP Q
Row 00 01 11 10 00 01 11 10
1,2,3 1 2 4 3 0 0 0 0
4 - 2 4 5 X 0 0 0
5,6,8 6 8 7 5 1 1 1 1
7 - 8 7 3 X 1 1 1

TP Q
Row Q1Q2 00 01 11 10 00 01 11 10
1,2,3(00) 00 00 10 00 0 0 0 0

4(10) 00 10 11 X 0 0 0
-
5,6,8(11) 11 11 01 11 1 1 1 1

7(01) - 11 01 00 X 1 1 1
28
 TP Q
Row Q1Q2 00 01 11 10 00 01 11 10
1,2,3(00) 00 00 10 00 0 0 0 0

4(10) 00 10 11 X 0 0 0
-
5,6,8(11) 11 11 01 11 1 1 1 1

7(01) - 11 01 00 X 1 1 1

TP TP
Q1Q2 00 01 11 10 Q1Q2 00 01 11 10

00 0 0 1 0 00 0 0 0 0
01 x 0 1 1 01 x 0 0 1
11 1 1 0 1 11 1 1 1 1
10 x 1 0 0 10 x 1 1 0
Q1+ Q2+ 29
 TP TP
Q1Q2 00 01 11 10 Q1Q2 00 01 11 10

00 0 0 1 0 00 0 0 0 0
01 x 0 1 1 01 x 0 0 1
11 1 1 0 1 11 1 1 1 1
10 x 1 0 0 10 x 1 1 0

+
Q1 = Q1T+Q2P+ Q2+ = Q1T+Q1P+Q2P

Q1TP+Q1Q2T

30
 Step 4 : Output Assignment
TP Q
Row Q1Q2 00 01 11 10 00 01 11 10

1,2,3(00) 00 00 10 00 0 0 0 0

4(10) 00 10 11 X 0 0 0
-
5,6,8(11) 11 11 01 11 1 1 1 1

7(01) - 11 01 00 X 1 1 1

Q1Q2 00 01 11 10

00 0 0 0 0
01 x 0 0 0
Z = Q1
11 1 1 1 1
10
x 1 1 1 31
 Step 5 :

LOGIC DIAGRAM

32
 Q1+ = Q1T+Q2P+ Q1TP+Q1Q2T;
T Q2+ = Q1T+Q1P+Q2P;

P
Q1
Z=Q1

Q2
P
33
Thank you

34
Digital Logic Families

Logic families can be classified broadly according to the technologies they are
built with. The various technologies are listed below.

 DL : Diode Logic.
 RTL : Resistor Transistor Logic.
 DTL : Diode Transistor Logic.
 TTL : Transistor Transistor Logic.
 ECL : Emitter coupled logic.
 MOS : Metal Oxide Semiconductor Logic (PMOS and NMOS).
 CMOS : Complementary Metal Oxide Semiconductor Logic.

Among these, only CMOS is most widely used by the ASIC (Chip) designers.

Basic Concepts

o Fan-in.
o Fan-out.
o Noise Margin.
o Power Dissipation.
o Gate Delay.
o Wire Delay.
o Skew.
o Voltage threshold

Fan – in:

Fan-in is the number of inputs a gate has, like a two input AND gate has fan-in of
two, a three input NAND gate as a fan-in of three. So a NOT gate always has a
fan-in of one. The figure below shows the effect of fan-in on the delay offered by
a gate for a CMOS based gate. Normally delay increases following a quadratic
function of fan-in.
Fan – out:

The number of gates that each gate can drive, while providing voltage levels in
the guaranteed range, is called the standard load or fan-out. The fan-out really
depends on the amount of electric current a gate can source or sink while driving
other gates. The effects of loading a logic gate output with more than its rated fan-
out has the following effects.

o In the LOW state the output voltage VOL may increase above VOLmax.
o In the HIGH state the output voltage VOH may decrease below VOHmin.
o The operating temperature of the device may increase thereby reducing the
reliability of the device and eventually causing the device failure.
o Output rise and fall times may increase beyond specifications
o The propagation delay may rise above the specified value.

Normally as in the case of fan-in, the delay offered by a gate increases with the
increase in fan-out.

Gate Delay

Gate delay is the delay offered by a gate for the signal appearing at its input,
before it reaches the gate output. The figure below shows a NOT gate with a delay
of "Delta", where output X' changes only after a delay of "Delta". Gate delay is
also known as propagation delay.
 Gate delay is not the same for both transitions, i.e. gate delay will be different for
low to high transition, compared to high to low transition.Low to high transition
delay is called turn-on delay and High to low transition delay is called turn-off
delay.

Wire Delay

Gates are connected together with wires and these wires do delay the signal they
carry, these delays become very significant when frequency increases, say when
the transistor sizes are sub-micron. Sometimes wire delay is also called flight time
(i.e. signal flight time from point A to B). Wire delay is also known as transport
delay.

Skew

The same signal arriving at different parts of the design with different phase is
known as skew. Skew normally refers to clock signals. In the figure below, clock
signal CLK reaches flip-flop FF0 at time t0, so with respect to the clock phase at
the source, it has at FF0 input a clock skew of t0 time units. Normally this is
expressed in nanoseconds.
 The waveform below shows how clock looks at different parts of the design.

Logic levels

Logic levels are the voltage levels for logic high and logic low.

 VOHmin : The minimum output voltage in HIGH state (logic '1'). VOHmin is 2.4
V for TTL and 4.9 V for CMOS.
 VOLmax : The maximum output voltage in LOW state (logic '0'). VOLmax is 0.4
V for TTL and 0.1 V for CMOS.
 VIHmin : The minimum input voltage guaranteed to be recognised as logic 1.
VIHmin is 2 V for TTL and 3.5 V for CMOS.
 VILmax : The maximum input voltage guaranteed to be recognised as logic 0.
VILmax is 0.8 V for TTL and 1.5 V for CMOS.

Current levels

 IOHmin: The maximum current the output can source in HIGH state while still
maintaining the output voltage above VOHmin.
 IOLmax : The maximum current the output can sink in LOW state while still
maintaining the output voltage below VOLmax.
 IImax : The maximum current that flows into an input in any state (1µA for
CMOS).
Noise Margin

Gate circuits are constructed to sustain variations in input and output voltage
levels. Variations are usually the result of several different factors.

 Batteries lose their full potential, causing the supply voltage to drop
 High operating temperatures may cause a drift in transistor voltage and
current characteristics
 Spurious pulses may be introduced on signal lines by normal surges of current
in neighbouring supply lines.

All these undesirable voltage variations that are superimposed on normal

operating voltage levels are called noise. All gates are designed to tolerate a
certain amount of noise on their input and output ports. The maximum noise
voltage level that is tolerated by a gate is called noise margin. It derives from I/P-
O/P voltage characteristic, measured under different operating conditions. It's
normally supplied from manufacturer in the gate documentation.

 LNM (Low noise margin): The largest noise amplitude that is guaranteed not
to change the output voltage level when superimposed on the input voltage of
the logic gate (when this voltage is in the LOW interval). LNM=VI Lmax-
VOLmax.
 HNM (High noise margin): The largest noise amplitude that is guaranteed
not to change the output voltage level if superimposed on the input voltage of
the logic gate (when this voltage is in the HIGH interval). HNM=VOHmin-
VIHmin

tr (Rise time)

The time required for the output voltage to increase from VILmax to VIHmin.

tf (Fall time)

The time required for the output voltage to decrease from VIHmin to VILmax.

tp (Propagation delay)

The time between the logic transition on an input and the corresponding logic
transition on the output of the logic gate. The propagation delay is measured at
midpoints.

Power Dissipation

Each gate is connected to a power supply VCC (VDD in the case of CMOS). It
draws a certain amount of current during its operation. Since each gate can be in a
High, Transition or Low state, there are three different currents drawn from power
supply.

 ICCH: Current drawn during HIGH state.

 ICCT: Current drawn during HIGH to LOW, LOW to HIGH transition.
  ICCL: Current drawn during LOW state.

For TTL, ICCT the transition current is negligible, in comparison to ICCH and
ICCL. If we assume that ICCH and ICCL are equal then,

Average Power Dissipation = Vcc * (ICCH + ICCL)/2

For CMOS, ICCH and ICCL current is negligible, in comparison to ICCT. So the
Average power dissipation is calculated as below.

Average Power Dissipation = Vcc * ICCT.

So for TTL like logics family, power dissipation does not depend on frequency of
operation, and for CMOS the power dissipation depends on the operation
frequency.

Power Dissipation is an important metric for two reasons. The amount of current
and power available in a battery is nearly constant. Power dissipation of a circuit
or system defines battery life: the greater the power dissipation, the shorter the
battery life. Power dissipation is proportional to the heat generated by the chip or
system; excessive heat dissipation may increase operating temperature and cause
gate circuitry to drift out of its normal operating range; will cause gates to
generate improper output values. Thus power dissipation of any gate
implementation must be kept as low as possible.

Moreover, power dissipation can be classified into Static power dissipation and
Dynamic power dissipation.

 Ps (Static Power Dissipation): Power consumed when the output or input

are not changing or rather when clock is turned off. Normally static power
dissipation is caused by leakage current. (As we reduce the transistor size,
i.e. below 90nm, leakage current could be as high as 40% of total power
dissipation).
 Pd (Dynamic Power Dissipation): Power consumed during output and
input transitions. So we can say Pd is the actual power consumed i.e. the
power consumed by transistors + leakage current.

Thus

Total power dissipation = static power dissipation + dynamic power dissipation.

Diode Logic

In DL (diode logic), all the logic is implemented using diodes and resistors. One
basic thing about the diode is that diode needs to be forward biased to conduct.
Below is the example of a few DL logic circuits.
 When no input is connected or driven, output Z is low, due to resistor R1. When
high is applied to X or Y, or both X and Y are driven high, the corresponding
diode get forward biased and thus conducts. When any diode conducts, output Z
goes high.

Resistor Transistor Logic

In RTL (resistor transistor logic), all the logic are implemented using resistors and
transistors. One basic thing about the transistor (NPN), is that HIGH at input
causes output to be LOW (i.e. like a inverter). Below is the example of a few RTL
logic circuits.

A basic circuit of an RTL NOR gate consists of two transistors Q1 and Q2,
connected as shown in the figure above. When either input X or Y is driven
HIGH, the corresponding transistor goes to saturation and output Z is pulled to
LOW.

Diode Transistor Logic

 In DTL (Diode transistor logic), all the logic is implemented using diodes and
transistors. A basic circuit in the DTL logic family is as shown in the figure
below. Each input is associated with one diode. The diodes and the 4.7K resistor
form an AND gate. If input X, Y or Z is low, the corresponding diode conducts
current, through the 4.7K resistor. Thus there is no current through the diodes
connected in series to transistor base. Hence the transistor does not conduct, thus
remains in cut-off, and output out is high.

If all the inputs X, Y, Z are driven high, the diodes in series conduct, driving the
transistor into saturation. Thus output out is Low.

Transistor Transistor Logic

In Transistor Transistor logic or just TTL, logic gates are built only around
transistors. TTL was developed in 1965. Through the years basic TTL has been
improved to meet performance requirements. There are many versions or families of
TTL.

 Standard TTL.
 High Speed TTL
 Low Power TTL
 Schhottky TTL

TTL families have three configurations for outputs.

 Totem - Pole output.

 Open Collector Output.
 Tristate Output.

The input stage, which is used with almost all versions of TTL, consists of an
input transistor and a phase splitter transistor. Input stage consists of a multi
emitter transistor as shown in the figure below. When any input is driven low, the
emitter base junction is forward biased and input transistor conducts. This in turn
drives the phase splitter transistor into cut-off.
Totem - Pole Output

Below is the circuit of a totem-pole NAND gate, which has got three
stages.

 Input Stage
 Phase Splitter Stage
 Output Stage

Input stage and Phase splitter stage have already been discussed. Output stage is
called Totem-Pole because transistor Q3 sits upon Q4.

Q2 provides complementary voltages for the output transistors Q3 and Q4, which
stack one above the other in such a way that while one of these conducts, the
other is in cut-off.

Q4 is called pull-down transistor, as it pulls the output voltage down, when it

saturates and the other is in cut-off (i.e. Q3 is in cut-off). Q3 is called pull-up
transistor, as it pulls the output voltage up, when it saturates and the other is in
cut-off (i.e. Q4 is in cut-off).

Diodes in input are protection diodes which conduct when there is large negative
voltage at input, shorting it to the ground.
Tristate Output.

Normally when we have to implement shared bus systems inside an ASIC or

externally to the chip, we have two options: either to use a MUX/DEMUX based
system or to use a tri-state base bus system.

In the latter, when logic is not driving its output, it does not drive LOW neither
HIGH, which means that logic output is floating. Well, one may ask, why not just
use an open collector for shared bus systems? The problem is that open collectors
are not so good for implementing wire-ANDs.

The circuit below is a tri-state NAND gate; when Enable En is HIGH, it works
like any other NAND gate. But when Enable En is driven LOW, Q1 Conducts,
and the diode connecting Q1 emitter and Q2 collector, conducts driving Q3 into
cut-off. Since Q2 is not conducting, Q4 is also at cut-off. When both pull-up and
pull-down transistors are not conducting, output Z is in high-impedance state.

Emitter coupled logic

 Emitter coupled logic (ECL) is a non saturated logic, which means that transistors
are prevented from going into deep saturation, thus eliminating storage delays.
Preventing the transistors from going into saturation is accomplished by using
logic levels whose values are so close to each other that a transistor is not driven
into saturation when its input switches from low to high. In other words, the
transistor is switched on, but not completely on. This logic family is faster than
TTL.

Voltage level for high is -0.9 Volts and for low is -1.7V; thus biggest problem
with ECL is a poor noise margin.

A typical ECL OR gate is shown below. When any input is HIGH (-0.9v), its
connected transistor will conduct, and hence will make Q3 off, which in turn will
make Q4 output HIGH.

When both inputs are LOW (-1.7v), their connected transistors will not conduct,
making Q3 on, which in turn will make Q4 output LOW.

Metal Oxide Semiconductor Logic

MOS or Metal Oxide Semiconductor logic uses nmos and pmos to implement
logic gates. One needs to know the operation of FET and MOS transistors to
understand the operation of MOS logic circuits.

The basic NMOS inverter is shown below: when input is LOW, NMOS transistor
does not conduct, and thus output is HIGH. But when input is HIGH, NMOS
transistor conducts and thus output is LOW.
 Normally it is difficult to fabricate resistors inside the chips, so the resistor is
replaced with an NMOS gate as shown below. This new NMOS transistor acts as
resistor.

Complementary Metal Oxide Semiconductor Logic

CMOS or Complementary Metal Oxide Semiconductor logic is built using both

NMOS and PMOS. Below is the basic CMOS inverter circuit, which follows these
rules:

 NMOS conducts when its input is HIGH.

 PMOS conducts when its input is LOW. 

So when input is HIGH, NMOS conducts, and thus output is LOW; when input is
LOW PMOS conducts and thus output is HIGH.
Field Programmable Gate Arrays(FPGA)
Field Programmable Gate Arrays are two dimensional arrays of logic blocks and flip-flops with aelectrically
programmable interconnections between logic blocks.

The interconnections consist of electrically programmable switches which is why FPGA differs from Custom
ICs, as Custom IC is programmed using integrated circuit fabrication technology to form metalinterconnections
between logic blocks.

In an FPGA logic blocks are implemented using mutliple level low fanin gates, which gives it a more compact
design compared to an implementation with two-level AND-OR logic. FPGA provides its usera way to
configure:

1. The intersection between the logic blocks and

2. The function of each logic block.

Logic block of an FPGA can be configured in such a way that it can provide functionality as simple asthat of
transistor or as complex as that of a microprocessor. It can used to implement different combinations of
combinational and sequential logic functions. Logic blocks of an FPGA can be implemented by any of the
following:

1. Transistor pairs
2. combinational gates like basic NAND gates or XOR gates
3. n-input Lookup tables
4. Multiplexers
5. Wide fan in And-OR structure.
Figure 1: Simplefied version of FPGA internal architecture.

Routing in FPGAs consists of wire segments of varying lengths which can be interconnected via electrically
programmable switches. Density of logic block used in an FPGA depends on length and number of wire
segments used for routing. Number of segments used for interconnection typically is atradeoff between density
of logic blocks used and amount of area used up for routing.

The ability to reconfigure functionality to be implemented on a chip gives a unique advantage to designer who
designs his system on an FPGA It reduces the time to market and significantly reducesthe cost of production.

Why do we need FPGAs ?

By the early 1980’s Large scale integrated circuits (LSI) formed the back bone of most of the logic
circuits in major systems. Microprocessors, bus/IO controllers, system timers etc were implemented using
integrated circuit fabrication technology. Random “glue logic” or interconnects were still requiredto help
connect the large integrated circuits in order to :

1. generate global control signals (for resets etc.)

2. data signals from one subsystem to another sub system.

Systems typically consisted of few large scale integrated components and large number of SSI (smallscale
integrated circuit) and MSI (medium scale integrated circuit) components.

Intial attempt to solve this problem led to development of Custom ICs which were to replace the largeamount
of interconnect. This reduced system complexity and manufacturing cost, and improved performance.However,
custom ICs have their own disadvantages. They are relatively very expensive to develop, and delay introduced
for product to market (time to market) because of increased design time. There are two kinds of costs involved
in development of Custom ICs:
1. cost of development and design
2. cost of manufacture
( A tradeoff usually exists between the two costs)

Therefore the custom IC approach was only viable for products with very high volume, and which werenot time
to market sensitive.

FPGAs were introduced as an alternative to custom ICs for implementing entire system on one chipand to
provide flexibility of reporogramability to the user. Introduction of FPGAs resulted in
improvement of density relative to discrete SSI/MSI components (within around 10x of custom ICs). Another
advantage of FPGAs over CustomICs is that with the help of computer aided design (CAD)tools circuits
could be implemented in a short amount of time (no physical layout process, no mask making, no IC
manufacturing)

Figure 2: FPGA comparative analysis.

Logic Block
Logic Block

Logic block in an FPGA can be implemented in ways that

differ in number of inputs and outputs, amount of area
consumed, complexity of logic functions that it can
implement, total number of transistors that it consumes. This
section will describe some important implementations of logic
blocks.

Crosspoint FPGA: consist of two types of logic blocks. One is transistor pair tiles in which transistorpairs run
in parallel lines as shown in figure below:

second type of logic blocks are RAM logic which can be used to implement random access memory.

Plessey FPGA: basic building block here is 2-input NAND gate which is connected to each other toimplement
desired function.
Both Crosspoint and Plessey are fine grain logic blocks. Fine grain logic blocks have an advantage inhigh
percentage usage of logic blocks but they require large number of wire segments and programmable switches
which occupy lot of area.

Actel Logic Block: If inputs of a multiplexer are connected to a constant or to a signal, it can be used to
implement different logic functions. for example a 2-input multiplexer with inputs a and b, select , willimplement
function ac + bc´. If b=0 then it will implement ac, and if a=0 it will implement bc´.

Typically an Actel logic block consists of multiple number of multiplexers and logic gates.

Xilinx Logic block:

In Xilinx logic block Look up table is used to implement any number of different functionality. The inputlines go
into the input and enable of lookup table. The output of the lookup table gives the result of thelogic function that
it implements. Lookup table is implemented using SRAM. A k-input logic function is implemented using 2^k * 1
size SRAM. Number of different possible functions for k input LUT is 2^2^k.Advantage of such an architecture
is that it supports implementation of so many logic functions, however the disadvantage is unusually large
number of memory cells required to implement such a
logic block in case number of inputs is large. Figure below shows 5-input LUT based implementation of

logic block. Xilinx - LUT based

LUT based design provides for better logic block utilization. A k-input LUT based logic block can be
implemented in number of different ways with tradeoff between performance and logic density.

An n-lut can be shown as a direct implementation of a function truth-table. Each of the latch holds the value of
the function corresponding to one input combination. For Example: 2-lut shown in figure belowimplements 2
input AND and OR functions.

Altera Logic Block

Altera’s logic block has evolved from earlier PLDs. It consists of wide fan in (up to 100 input) AND gates
feeding into an OR gate with 3-8 inputs. If floating gate transistor based programmable switch isprovide any
vertical wire passing near AND gate can be used as input to the AND gate. IF each input
signal is present both original and complemented form functional capability of block increases significantly. The
advantage of large fan in AND gate based implementation is that few logic blocks can implement the entire
functionality thereby reducing the amount of area required by interconnects. On the other hand disadvantage is
the low density usage of logic blocks in a design that requires fewerinput logic.

Another disadvantage is the use of pull up devices (AND gates) that consume static power. To improve power
manufacturers provide low power consuming logic blocks at the expense of delay. Such logic blocks have gates
with high Threshold as a result they consume less power. Such logicblocks can be used in non-critical paths.

Altera, Xilinx are coarse grain architecture.

Tradeoff - Size of Logic block Vs Performance

Size of logic block plays an important role in deciding density of logic blocks and area utilization in anFPGA.
It also effects the performance of the FPGA.

 A large size logic block implements more logic and hence requires less number of logic blocksto
implement a functionality on the FPGA. On the other hand a large logic block will consume more
space on the FPGA. So optimal size of logic block is one that optimally uses lesser number of logic
blocks for functionality implementation while consuming as little space as possible.
 Active logic area is generally less than total logic area due to presence of programmable
connections. Total logic area is sum of active logic area and area consumed by programmable
connections.
 Routing area in an FPGA is typically more than the active area. It is 70 to 90 percent of totalarea in
an FPGA.
 In case of Lookup table based FPGA, a 4-input lookup table gives best results in terms oflogic
synthesised and area consumed.
 Granularity of logic block has influence on performance of an FPGA. Typically higher granularity
level results in lesser delay between input and output. As the granularity of logic block increases,
number of levels of logic in critical path decreases, and hence delay in criticalpath decreases. On the
flip side with increase in granularity level average fan out increases and number of switches also
increases as each block has more pins. Also the length of wires increases with increase in size of logic
block.

FPGA Routing Techniques

Routing architecture comprises of programmable switches
and wires. Routing provides connection between I/O blocks
and logic blocks, and between onelogic block and another
logic block.

The type of routing architecture decides area consumedby

routing and density of logic blocks.

Routing technique used in an FPGA largely decides the

amount of area used by wire segments and programmable
switches as compared to area consumedby logic blocks.

A wire segment can be described as two end points of an interconnect with no programmable switchbetween
them. A sequence of one or more wire segments in an FPGA can be termed as a track.
Typically an FPGA has logic blocks, interconnects and Input/Output blocks. Input Output blocks lie in the
periphery of logic blocks and interconnect. Wire segments connect I/O blocks to wire segments through
connection blocks. Connection blocks are connected to logic blocks, depending on the designrequirement one
logic block is connected to another and so on.

Xilinx Routing architecture

In Xilinx routing, connections are made from logic block into the channel through a connection block. As
SRAM technology is used to implement Lookup Tables, connection sites are large. A logic block issurrounded
by connection blocks on all four sides. They connect logic block pins to wire segments.
Pass transistors are used to implement connection for output pins, while use of multiplexers for inputpins saves
the number of SRAM cells required per pin. The logic block pins connecting to connection blocks can then be
connected to any number of wire segments through switching blocks.

there are four types of wire segments available :

 general purpose segments, the ones that pass through switches in the switch block.
 Direct interconnect : ones which connect logic block pins to four surrounding connectingblocks
 long line : high fan out uniform delay connections
 clock lines : clock signal provider which runs all over the chip.

Actel routing methodology

Actel’s design has more wire segments in horizontal direction than in vertical direction. The input pins connect
to all tracks of the channel that is on the same side as the pin. The output pins extend across two channels above
the logic block and two channels below it. Output pin can be connected to all 4 channels that it crosses. The
switch blocks are distributed throughout the horizontal channels. All vertical tracks can make a connection with
every incidental horizontal track. This allows for the flexibility that a horizontal track can switch into a vertical
track, thus allowing for horizontal and verticalrouting of same wire. The drawback is more switches are
required which add up to more capacitive load.
Altera routing methodology

Altera routing architecture has two level hierarchy. At the first level of the hierarchy, 16 or 32 of thelogic
blocks are grouped into a Logic Array Block, structure of the LAB is very similar to a traditional PLD. the
connection is formed using EPROM- like floating-gate transistors. The channel here is set of wiresthat run
vertically along the length of the FPGA. Tracks are used for four types of connections :

 connections from output of all logic blocks in LAB.

 connection from logic expanders.
 connections from output of logic blocks in other LABs
 connections to and from Input output pads

all four types of tracks connect to every logic block in the array block. The connection block makes sure that
every such track can connect to every logic block pin. Any track can connect to into any inputwhich makes this
routing simple. The intra-LAB routing consists of segmented channel, where segments are as long as possible.
Global interconnect structure called programmable interconnect array(PIA) is used to make connections among
LABs. Its internal structure is similar to internal routing of a LAB. Advantage of this scheme is that regularity of
physical design of silicon allows it to be packedtightly and efficiently. The disadvantage is the large number of
switches required, which adds to capacitive load.
FPGA Structural Classification
Programmble Logic Devices

There is a constant effort on the part of system designers to

design systems with improved performance, efficiency and
flexibility.

Today, if one wants to make effective and competitive use of

these general purpose blocks, then one of the better ways is to
use reconfigurable hardware that allowsuser programmability.

The first form of reconfigurable device was Programmable Logic Devices which consisted of arrays of AND and
OR gates with programmable metal paths as interconnection between them. They could be programmed to into a
single chip to meet specific requirements. PLDs later evolved into what was laterknown as FPGAs.

Basic structure of an FPGA includes logic elements, programmable interconnects and memory.Arrangement of
these blocks is specific to particular manufacturer. On the basis of internal arrangement of blocks FPGAs can be
divided into three classes:

Symmetrical arrays

This architecture consists of logic elements(called CLBs) arranged in rows and columns of a matrix and
interconnect laid out between them. This symmetical matrix is surrounded by I/O blocks which connect it to
outside world. Each CLB consists of n-input Lookup table and a pair of programmable flip flops. I/O blocks also
control functions such as tri-state control, output transition speed. Interconnects
provide routing path. Direct interconnects between adjacent logic elements have smaller delaycompared
to general purpose interconnet.

Row based architecture

Row based architecture consists of alternating rows of logic modules and programmable interconnecttracks.
Input output blocks are located in the periphery of the rows. One row may be connected to adjacent rows via
vertical interconnect. Logic modules can be implemented in various combinations. Combinatorial modules
contain only combinational elements which Sequential modules contain both combinational elements along
with flip flops. This sequential modules can implement complex combinatorial-sequential functions. Routing
tracks are divided into smaller segments connected by anti-fuse elements between them.

Hierarchical PLDs

This architecture is designed in hierarchical manner with top level containing only logic blocks andinterconnects.
Each logic block contains number of logic modules. And each logic module has combinatorial as well as sequential
functional elements. Each of these functional elements is
controlled by the programmed memory. Communication between logic blocks is achieved by programmable
interconnect arrays. Input output blocks surround this scheme of logic blocks andinterconnects.

Programming Methodology
Electrically programmable switches are used to program an
FPGA. Performance of an FPGA in terms of area and logic
density is a function of properties of these switches.

Properties of these programmable switches that make

difference are on-resistance, parasitic capacitance,
volatility, re-programmability, size etc.

Various approaches to provide user programmability are :

SRAM programming technology

Static RAM cells are used to control pass gates or multiplexers. To use pass gate as closed switch,boolean one is
stored in SRAM cell. When zero is stored pass transistor provides high resistance between two wire segments.
Figure a depicts this usage of SRAM.
To use SRAM as multiplexer, state of control values stored in SRAM decides which of the multiplexerinputs are
connected to the output as shown in figure b.

Advantage of SRAM is that it provides fast re-programmability and integrated circuit fabrication
technology is required to build it. While disadvantage is the space it consumes as minimum five
transistors are required to implement a memory cell.

Floating Gate Programming

Technology found in ultaviolet erasable EPROM and electrically erasable EEPROM devices is used inFPGA
from Altera. The programmable switch is a transistor that permanently be disabled.

Here again the advantage is reprogrammability but there is another advantage no external permanentmemory
source is need to program it at power-up. However it requires three additional processing steps over CMOS
technology. Other disadvantages are high static power consumption due to pull up resistor and high ON-
resistance of EPROM transistor.

Electrically programmable EPROM is used by AMD and Lattice. Use of EEPROM gives advantage ofeasy
reprogrammability. However EEPROM cell is twice as large as EPROM cell.

Antifuse programming methodology

An Antifuse is a two terminal device with an unprogrammed state providing very high resistance between its
terminals. To create a low resistance link between the two terminals high voltage is appliedaccross the terminals
to blow the antifuse. Extra bit of circuitry is required to program an antifuse.
Antifuse technology is used by FPGA’s from Actel, QuickLogic and Crosspoint.

Advantage of Antifuse is relatively small size and hence area reduction which is anulled by area consumed
by extra circuitry to program it. Another big advantage is low series resistance and lowparasitic
capacitance.

FPGA Design Flow

One of the most important advantages of FPGA based
design is that users can design it using CAD tools provided
by design automation companies.

Generic design flow of an FPGA includes following steps:

System Design

At this stage designer has to decide what portion of his functionality has to be implemented on FPGAand how to
integrate that functionality with rest of the system.

I/O integration with rest of the system

Input Output streams of the FPGA are integrated with rest of the Printed Circuit Board, which allowsthe design
of the PCB early in design process. FPGA vendors provide extra automation software solutions for I/O design
process.

Design Description

Designer describes design functionality either by using schema editors or by using one of the variousHardware
Description Languages(HDLs) like Verilog or VHDL.

Synthesis

Once design has been defined CAD tools are used to implement the design on a given FPGA. Synthesis includes
generic optimization, slack optimizations, power optimizations followed by placement and routing.
Implementation includes Partition, Place and route. The output of designimplementation phase is bit-stream file.

Design Verification

Bit stream file is fed to a simulator which simulates the design functionality and reports errors in desired
behavior of the design. Timing tools are used to determine maximum clock frequency of thedesign. Now the
design is loading onto the target FPGA device and testing is done in real environment.

Example :

Below given circuit consists of gates and flip flops. Combinational elements of the circuit are coveredby a 4-
input Look up table(4-LUT). Sequential elements in the input circuit map to flip flops on the FPGA. Placement
of these elements is done in such a way as to minimize wiring during routing.
Truth Table

S1 S0 F0 F1 F2 F3
0 0 D 0 0 0
0 1 0 D 0 0
1 0 0 0 D 0
1 1 0 0 0 D