AMBO UNIVERSITY HACHALU HUNDESSA CAMPUS

SCHOOL OF INFORMATICS & ELECTRICAL ENGINEERING

DEPARTMENT OF ELECTRICAL AND COMPUTER ENGINEERING

Lecture notes of Digital Logic Design

•Compiled by :Mohammed Mamo Jara
•March 2023,
  This course provides an overview of the principles underlying;
– Number systems, arithmetic operations, decimal codes, alphanumeric
codes, Boolean algebra, Karnaugh maps, implementation of digital logic
gates using universal gates(NAND and NOR gates), exclusive-OR gates,
– Integrated circuits, combinational circuits, decoders, encoders,
multiplexers, Demultiplexers adders, subtractors, multipliers, sequential
circuits, latches, flip-flops, sequential circuits analysis, and counters.
– Finally, under this course, Analysis and design of combinational and
sequential logic systems will be done.
 The major topics to be studied in this course are:
– Introduction to digital systems
– Number system, operations and codes
– Logic gates ,boolean algebra and logic simplification
– Combinational logic circuits
– Flip-flops and sequential circuits

2
 Course Objective
and Competency
– Convert between decimal, binary, octal, and hexadecimal number
systems.
– Differentiate different Codes in digital system.
– Perform two-level logic minimization using Boolean algebra and
Karnaugh maps minimization method.
– Analyze the properties and realization of the various logic gates.
– Perform binary Arithmetic operation.
– Implement the Boolean Functions using Universal Logic gates.
– Incorporate medium scale integrated circuits, like decoders,
encoders, multiplexers, etc., into circuit design.
– Differentiate and Design Combinational and Sequential circuits.
– Design and analyze clocked sequential circuits.
– Use various types of latches and flip-flops to build binary memory and
counters.
3
 COURSE CONTENTS
Chapter Course Content

 Digital and analogue quantities

 Binary digit logic level and digital waveform
1. Int r oduct ion t o Digit al
 Decimal number, Binary number, Octal number & Hexadecimal number
Syst ems and Number  Inter -conversation Between the Number systems
syst em and binar y codes  Signed number representation
(6-Lec. Hrs.)  1’s and 2’s compliment of binary number
 Binary codes (BCD, ASCII, EXCESS 3, GRAY CODE)
 Basic logic gates (inverter, AND gate & OR gate)
2. Logic gat es  Derived logic gates (NAND gate, NOR gate, X-OR and X-NOR gates)
(2 lecture hour)  Universal property of NAND and NOR gates
3. Boolean algebr a and Logic  Boolean operation and expression  Boolean analysis of logic circuit
simplif icat ion  Laws and rules of Boolean algebra  The K-map
(4-Lec. Hrs.)  De Morgan Theorems
 Functions of combinational logic  Arithmetic circuits: half-Adders, full-adders
4. Combinat ional logic  Basic combinational logic circuits  Half-subtractors, full-subtarctors.
(6-Lec. Hrs.)  Implementing Combinational logic  Decoders vs encoders, Multiplexers and demultiplexers
5. Sequent ial cir cuit s  Flip flops & Latches  Master slave flip flops and its
(4-Lec. Hrs.)  Edge triggered flip flops  Applications of
 Synchronous  Basic shift registers
6. Design of Count er s & Shif t  Asynchronous counters  Serial in - serial out registers (SI-SO)
r egist er s  Up/down counters  Serial in - parallel out Registers (SI-PO)
(8-Lec. Hrs.)  Design of synchronous counters
 Basics of semiconductor Memory  Programmable ROM; (PROM, EEPROM)
7. Memor y and st or age  Random access memory (RAM’s)  Flash memories
(4-Lec. Hrs.)  Read only memory (ROM’s)

4
 References
 Morris M. Mano: Digital Design (3rd Edition)
 Anil K. Maini: Digital Electronics- Principles, Devices and
Applications, John Wiley & Sons, Ltd., 2007 (Text Book)
 Kenneth J. Breeding: Digital Design Fundamentals, Second Edition,
The Ohio State University Prentice Hall, 1992
 Ronald. J. Tocci and Neal. S. Widmer: Digital Systems – Principles
and Applications, Prentice Hall
 T.L. Floyd: Digital Fundamentals, 9th edition, Prentice Hall
 Tony R. Kuphaldt: Lessons in Electric Circuits, Volume IV – Digital,
Fourth Edition, November 01, 2007
 Mark Balch: Complete Digital Design-A Comprehensive Guide To
Digital Electronics And Computer System Architecture, McGraw-Hill
 Stephen Brown, ZvonkoVranesic: Fundamentals of Digital Logic
with Verilog Design, McGraw- Hill Science/Engineering/Math; 1st
edition 2002
 Any other related web contents can be referred
5
 UNIT-I

INTRODUCTION TO
DIGITAL SYSTEMS

6
 UNIT
OUTLINE

 Chapter ①. Introduction to Digital Systems (2hr)

 Analogue representation vs Digital Representation
 Analogue system vs Digital system
 Digital Logic States and Logic Level
 Digital signal waveform

7
 1.1. ANALOGUE REPRESENTATION
VS DIGITAL REPRESENTATION

 There are two basic ways of representing the numerical

values of the various physical quantities with which we
constantly deal in our day-to-day lives.
– Analogue representation and
– Digital representation

8
 Continuous • A digital/discrete signal is a signal that can have one
signal versus of a finite set of possible values at any time.
Discrete • An analog/continuous signal is a signal that can have
signal one of an infinite number of possible values.

9
 i. ANALOGUE REPRESENTATION
 It expresses the numerical value of the quantity as a continuous
range of values between the two expected extreme values.
 For example, the temperature of an oven settable anywhere
from 0 to 100 °C may be measured to be 65 °C or 64.96 °C or
64.958 °C or even 64.9579 °C and so on, depending upon the
accuracy of the measuring instrument.
 Similarly, voltage across a certain component in an electronic
circuit may be measured as 6.5 V or 6.49 V or 6.487 V or 6.4869 V.
 The underlying concept in this mode of representation is that
variation in the numerical value of the quantity is continuous and
could have any of the infinite theoretically possible values
between the two extremes.
10
 II. DIGITAL REPRESENTATION
 The other possible way, referred to as digital, represents the
numerical value of the quantity in steps of discrete values.
 The numerical values are mostly represented using binary
numbers.
 For example, the temperature of the oven may be
represented in steps of 1°C as 64°C, 65°C, 66 °C and so on.
 To summarize, while an analogue representation gives a
continuous output, a digital representation produces a
discrete output.
 Analogue systems contain devices that process or work on
various physical quantities represented in analogue form.
 Digital systems contain devices that process the physical
quantities represented in digital form.
11
 Introduction to Digital System
 One of the first things we have to know is that electronics can
be broadly classified into two groups, viz.
– Analog Electronics and Digital Electronics.
 Analog electronics deals with things that are continuous in
nature and digital electronics deals with things that are
discrete in nature. But they are very much interlinked.
 For example, if we consider a bucket of water, then it is
analog in terms of the content i.e., water, but it is discrete in
terms of the container, i.e., bucket.
 So far we have mainly covered the analog realm of
electronics; circuits that accept and respond to voltages that
vary continuously over a given range.
 Such analog circuits included rectifiers, filters, amplifiers, simple
RC timers, oscillators, simple transistor switches, etc.
12
 What is a Digital system?
 Digital electronics deals with things that are discrete in nature.
 Although each of the analog circuits is fundamentally
important in its own right, these circuits lack an important
feature;
 They cannot store and process bits of information needed to
make complex logical decisions.
 To incorporate logical decision-making processes into a circuit,
we need to use digital electronics.
 Now though in nature most things are analog, still we very
often require digital concepts.
 It is because it has some specific advantages over analog,
which we will discuss in due course of time
13
 Digital system.. is
 Digital system is a system that processes discrete information.
 The discrete entities making up this information may represent
anything from simple arithmetic integers, letters of the
alphabet, or other abstract symbols to values for a voltage, a
pressure, or any other physical quantity.
 To a digital system, what these entities represent is not
important in the processing of the information.
 What they represent is important, however, to the human
observer who must interpret the results of the process.
 A digital system, then, is one that accepts as input digital
information representing numbers, symbols, or physical
quantities, processes this input information in some specific
manner, and produces a digital output.

14
 ………………continued
 Since Claude Shannon systemized and adapted the theoretical work of
George Boole in 1938, digital techniques saw a tremendous growth.
 Together with developments in semiconductor technology, and with the
progress in digital technology, a revolution in digital electronics happened
when the microprocessor was introduced in 1971 by Intel Corporation of America.
 At present, digital technology has progressed much from the era of vacuum tube
circuits to integrated circuits.

 In todays world, the term digital has become part of our everyday vocabulary
because of the dramatic way that digital circuits and digital techniques have
become so widely used in almost all areas of life:
– such as in computers, automation, robots, transportation, medical entertainment, space
exploration, telephony, radar navigation, data processing, and many other applications.

15
 COMBINED ANALOGUE AND DIGITAL
SYSTEMS

16
 Comparison of
Analogue and Digital systems
Analog system process
On the other hand, the digital
information that varies systems use discrete quantities to
continuously i.e. represent information.
• They process time varying signals
that can take on any value across a Discrete means distinct or
continuous range of voltage, current separated as opposed to continuous
or any physical parameter. or connected.

An analog/continuous signal
A digital/discrete signal is a signal
is a signal that can have one that can have one of a finite set of
of an infinite number of possible values at any time.
possible values.

17
 Digital Logic States
and Logic Level
 In digital electronics there are only two voltage states present at any point within a circuit.
 These voltage states are either high or low.
 The meaning of a voltage being high or low at a particular location within a circuit can
signify a number of things.
 The high and low states can be represented as true and false statements, which are used in
Boolean logic.
 In most cases, high = true and low = false. However, this does not have to be the case—
you could make high = false and low = true.
 In digital language, to avoid people getting confused over which convention is in use, the
term positive true logic is used when high = true, while the term negative true logic is used
when high = false.
 In Boolean logic, the symbols 1 and 0 are used to represent true and false, respectively.
 Now, unfortunately, 1 and 0 are also used in electronics to represent high and low voltage
states, where high = 1 and low = 0.
 The voltage used to represent a 1 and a 0 are called logic level.

18
 Logic levels
 As you can see, things can get a bit
confusing, especially if you are not sure which
type of logic convention is being used,
positive true or negative true logic.
 The exact voltages assigned to a high or low
voltage states depend on the specific logic
IC that is used (as it turns out, digital
components are entirely IC based).
 As a general rule of thumb, +5 V is considered
high, while 0 V (ground) is considered low.
 For example, some logic ICs may interprate a
voltage from +2.4 to +5 V as high and a
voltage from +0.8 to 0 V as low.
 Other ICs may use an entirely different range.

19
 Digital Signals and Timing diagram

 Digital signals or wave forms consist of voltage levels that

are changing back and forth between the HIGH and LOW
levels or states
 In digital system, the information that has been processed is
usually present in binary form.
 Binary quantities can be represented by any device that has
two operating states or possible condition, like a switch – on
(1) / off (0).
 In digital electronics, the discrete steps are characterized by
LOW and HIGH voltage, OPEN or CLOSED circuit.
 The digits are only 0 and 1.
 The characteristics are implemented in the binary number
system
20
 Non-periodic Pulse VS
Periodic Pulse
 Most wave forms encountered in digital
systems are composed of series of pulses,
sometime called pulse trains, can be
classified as either periodic or non-
periodic.
 A periodic pulse: wave form is one that
repeats itself at a fixed interval, called Ideal pulse characteristics
period (T).
 A non-periodic pulse wave form, of
course, does not repeat itself at fixed
intervals and may be composed of pulses
of randomly differing pulse widths and/ or
randomly differing time intervals between
the pulse. Non ideal pulse characteristics

21
  It is actually a graph of voltage versus time (t) and is
called a timing diagram.

Timing Diagram  The horizontal time scale is marked off at regular

intervals beginning at to and proceeding to t1, t2, and
so on.
 The transitions on this timing diagram are drawn as
vertical lines and so they appear to be instantaneous,
when in reality they are not.
 In many situations, however the transition times are so
short compared to the times between transitions that
we can show them on the diagram as vertical lines.

 Timing diagrams are used extensively to show how

digital signals change with time and specially to
show the relationship between two or more digital
signals in the same circuit or system.
 By displaying one or more digital signal on an
oscilloscope or logic analyzer we can compare the
signals to their expected timing diagrams.
Examples of timing diagram  This is a very important part of the testing and
troubleshooting procedures used in digital systems.

22
 Advantages and draw backs of Digital
systems
 Digital techniques and systems have the advantages of
 being relatively much easier to design and having higher accuracy,
 programmability,
 noise immunity,
 easier storage of data and
 ease of fabrication in integrated circuit form, leading to availability of more complex functions in a smaller size.
 The real world, however, is analogue. Most physical quantities – position, velocity, acceleration, force,
pressure, temperature and flowrate, for example – are analogue in nature.
 That is why analogue variables representing these quantities need to be digitized or discretized at the input if
we want to benefit from the features and facilities that come with the use of digital techniques.
 In a typical system dealing with analogue inputs and outputs, analogue variables are digitized at the input
with the help of an analogue-to-digital converter block and reconverted back to analogue form at the output
using a digital-to-analogue converter block.

23
 LIMITATIONS OF DIGITAL
TECHNIQUES
 There is really only one major drawback when using digital
techniques: The real world is mainly analog.
 The need for conversion between analog and digital forms of
information can be considered a drawback because of the added
complexity and expense.
 Another factor that is often important is the extra time required
to perform these conversions.
 In many applications, these factors are outweighed by the
numerous advantages of using digital techniques.
 and so the conversion between analog and digital quantities has
become quite common place in the current technology.

24
END OF

CHAPTER 1
 UNIT- II
NUMBER SYSTEMS AND
BINARY CODES

26
 At the end of the lesson, students
should be able to:
 Count in the binary number system.
 Convert from the decimal form to binary form and from binary
form to decimal form including fractions.
 Add and subtract binary numbers including fractions.
 Determine l’s and 2’s compliments of a binary number.
 Express signed numbers in binary form.
 Carry out arithmetic operations with signed binary numbers.
 Convert between the binary and octal number systems.
 Convert between the binary and hexadecimal number system.
 Express decimal numbers in binary coded decimal (BCD).
 Add BCD numbers.
 Understand the Gray and ASCII code is used.

27
 REVISION ON NUMBER SYSTEMS
 The study of number systems is important from the viewpoint
of understanding how data are represented before they can
be processed by any digital system including a digital
computer.
 It is one of the most basic topics in digital electronics.
 In this chapter we will discuss different number systems
commonly used to represent data.
 We will begin the discussion with the decimal number system.
 Although it is not important from the viewpoint of digital
electronics, a brief outline of this will be given to explain some
of the underlying concepts used in other number systems.
 This will then be followed by the more commonly used
number systems such as the
 Binary, Octal And Hexa-decimal Number Systems.

28
 Introduction to Number Systems
 We will begin our discussion on various number systems by briefly
describing the parameters that are common to all number
systems.
 An understanding of these parameters and their relevance to
number systems is fundamental to the understanding of how
various systems operate.
 Different characteristics that define a number system include
– The number of independent digits used in the number system,
– The place values of the different digits constituting the number and
– The maximum numbers that can be written with the given number of digits.

29
 Introduction to Number Systems

 Among the three characteristic parameters, the most fundamental is the

number of independent digits or symbols used in the number system.
 It is known as the radix or base of the number system.
 The decimal number system with which we are all so familiar can be said to
have a radix of 10 as it has 10 independent digits, i.e. 0, 1, 2, 3, 4, 5, 6, 7, 8
and 9.
 Similarly, the binary number system with only two independent digits, 0 and 1,
is a radix-2 number system.
 The octal and hexadecimal number systems have a radix (or base) of 8 and
16 respectively.

30
 Common characteristics of number systems
 We will see in the following sections that the radix of the number
system also determines the other two characteristics.
 The place values of different digits in the integer part of the
number are given
 By r0, r1, r2, r3 and so on, starting with the digit adjacent to the
radix point.
 For the fractional part,
 These are r-1, r-2, r-3 and so on, again starting with the digit next
to the radix point.
 Here, r is the radix of the number system.
 Also, maximum numbers that can be written with n digits in a
given number system are equal to rn.
31
 Table 2.1: Radix 2,10,8,16
Number Radix Independent
Example Expanded notation
System (r ) Digits

4x102+5x101+7x100
Decimal 10 0,1,2,3,4,5,6,7,8,9 (457.982)10
+9x10-1 + 8x10-2 + 2x10-3

1x22+0x21+1x20 +1x2-1 +
Binary 2 0,1 (101.101)2
0x2-2 + 1x2-3

4x82+5x81+7x80 +6x8-1 +
Octal 8 0,1,2,3,4,5,6,7 (457.632)8
3x8-2 + 2x8-3

4x162+15x161+10x160
Hexa- 0,1,2,3,4,5,6,7,8,9,A
16 (4FA.5BC)16 +5x16-1 + 11x16-2 +
decimal ,B,C,D,E,F
12x16-3
32
 Number Systems and Conversion
 When we write decimal (base 10) numbers, we use a
positional notation;
 Each digit is multiplied by an appropriate power of 10
depending on its position in the number.
For example,

 Similarly, for binary (base 2) numbers, each binary digit is

multiplied by the appropriate power of 2:

 Note that the binary point separates the positive and negative
powers of 2 just as the decimal point separates the positive
and negative powers of 10 for decimal numbers.
33
 Number Systems and Conversion(2)
 Any positive integer R (R > 1) can be chosen as the radix or base of a
number system.
 If the base is R, then R digits (0,1,. . . , R-1) are used.
 For example, if R= 8, then the required digits are 0, 1, 2, 3, 4, 5, 6, and
7.
 A number written in positional notation can be expanded in a power
series in R.
 For example,

34
 Number conversion
 If the arithmetic indicated in the power series expansion is done in base
10, then the result is the decimal equivalent of N.
 For example,

 For bases greater than 10, more than 10 symbols are needed to represent
the digits.
 In this case, letters are usually used to represent digits greater than 9.
 For example, in hexadecimal (base 16),
 A =1010 , B =1110, C =1210, D =1310, E =1410, and F represents 1510
Thus,

35
 Conversion of a decimal integer to base R
 Next, we will discuss conversion of a decimal integer to base R using
the repeated division method.
 The base R equivalent of a decimal integer N can be represented as

• This process is continued until we finally obtain ann

• Note that the remainder obtained at each division step is one of the desired digits and
• The least significant digit is obtained first.

36
 Conversion from Decimal to Binary

37
 Conversion of decimal fraction to radix R

This process is continued until we have obtained a sufficient number of digits.

Note that the integer part obtained at each step is one of the desired digits and the most
significant digit is obtained first.
38
 Conversion Of Decimal
Fraction To Binary

This process does not always terminate, but if it does not

terminate, the result is a repeating fraction.
39
 F1=0.7 F2=0.4 F3=0.8 F4=0.6 F5=0.2
X2 X2 X2 X2 X2
=1.4 =0.8 =1.6 =1.2 =0.4 Process starts repeating here because 0.4
(a-1=1) (a-2=0) (a-3=1) (a-4=1) (a-5=0) was previously obtained

F7=0.4 F8=0.8 F9=0.6 F10=0.2

X2 X2 X2 X2
=0.8 =1.6 =1.2 =0.4
(a-7=0) (a-8=1) (a-9=1) (a-10=0)

40
 Conversion from binary to hexadecimal
(and conversely)
 Conversion from binary to hexadecimal (and conversely)
can be done by inspection
 Because each hexadecimal digit corresponds to exactly
four binary digits (bits).
 Starting at the binary point, the bits are divided into groups
of four, and each group is replaced by a hexadecimal
digit:

As shown in Equation (1-1), extra 0’s are added at each end

of the bit string as needed to fill out the groups of four bits.

41
 Representation of Negative Numbers
 Up to this point we have been working with unsigned positive numbers.
 The most common methods for representing both positive and
negative numbers are
 Sign and magnitude,
 2’s complement, and
 1’s complement.
 In each of these methods, the leftmost bit of a number is 0 for positive
numbers and 1 for negative numbers.
 As discussed below, if n bits are used to represent numbers, then the sign
and magnitude and 1’s complement methods represent numbers in the
range
 −(2(n−1) − 1) to +(2(n−1) − 1) and both have two representations for 0, a positive 0 and a
negative 0.
 In 2’s complement, numbers in the range
 −2(n−1) to +(2(n−1) − 1) are represented and there is only a positive 0.
 If an operation, such as addition or subtraction, is performed on two
numbers and the result is outside the range of representation, then we
say that an overflow has occurred.
42
 Sign and Magnitude Numbers
 In an n-bit sign and magnitude system, a number is represented by a sign
bit, 0 for positive and 1 for negative, followed by n−1 bits that represent
the magnitude of the number.
 With n − 1 bits the magnitude can be 0 to 2(n−1) − 1.
 With the sign bit, numbers in the range −(2(n−1) − 1) to +(2(n−1) − 1) are
represented including a positive and negative 0.
 For example, 0011 represents +3 and 1011 represents −3.
 Note that 1000 represents minus 0, while 0000 represents +0.
 Designing logic circuits to perform arithmetic on sign and magnitude
binary numbers is awkward.
 One method is to convert the numbers into 2’s (or 1’s) complement and,
after performing the arithmetic operation, convert the result back to sign
and magnitude.
43
 1’s & 2’s Complement Numbers
 In the 1’s & 2’s complement number system, a positive number, N,
is represented by a 0 followed by the magnitude of N as in the sign
and magnitude system;
 However , a negative number, −N, is represented by its 1’s
complement 𝑁 ഥ and 2’s complement, N*.
 If the word length is n bits, the 2’s complement of a positive integer N is
defined as
 𝑁 ∗ = 2𝑛 − 𝑁 2’s complement of N
ഥ = 2 − 𝑁 − 1 = 𝑵 -1
 𝑁 𝑛 ∗
1’s complement of N
 N* is obtained by complementing N bit-by-bit and then adding 1.
 An alternative way to form the 2’s complement of N is to start at the right and leave any 0’s on
the right end and the first 1 unchanged, then complement all bits to the left of the first 1.
 For example, if n = 7 and N = 0101100,
 1’s complement of N=1010011.
 2’s complement of N =1010100

44
 TABLE 1-1 Signed Binary Integers (word length n=4)

45
 Binary Arithmetic

 Arithmetic operations in digital systems are usually done in binary

because design of logic circuits to perform binary arithmetic is
much easier than for decimal.
 Binary arithmetic is carried out in much the same manner as
decimal, except the addition and multiplication tables are much
simpler.
 The addition table for binary numbers is
 0+0=0
 0+1=1
 1+0=1
 1+1=0 and carry 1 to the next column
Carrying 1 to a column is equivalent to adding 1 to that column.
46
 1. Addition in Binary

47
 2. Subtraction in Binary

 The subtraction table for binary numbers is

 0−0=0
 0 − 1 = 1 and borrow 1 from the next column
 1−0=1
 1−1=0
 Borrowing 1 from a column is equivalent to subtracting 1 from that
column.
 Examples of Binary subtraction

48
 3. Binary multiplication
 The multiplication table for binary numbers is
 0×0=0
 0×1=0
 1×0=0
 1×1=1
 The following example illustrates multiplication of 1310 by
1110 in binary:
– 1310=11012 , 1110=10112

49
 3. Binary Division
 Consider, the same
example using unsigned
 Division is performed by repeatedly subtracting the divisor binary arithmetic.
from the dividend until the result is either zero or less than
the divisor.  25=110012
 The number of times the divisor is subtracted is called the  575=10001111112
quotient, and the number left after the final subtraction is
the remainder.
𝑑𝑖𝑣𝑖𝑑𝑒𝑛𝑑 𝑟𝑒𝑚𝑎𝑖𝑛𝑑𝑒𝑟
– That is, 𝑑𝑖𝑣𝑖𝑠𝑜𝑟
= 𝑞𝑢𝑜𝑡𝑖𝑒𝑛𝑡 + 𝑑𝑖𝑣𝑖𝑠𝑜𝑟
 Before we consider binary division let’s examine decimal
division 575/25
23
25 575
50
75
75
00

50
 4. Addition of 2’s Complement Numbers
 The addition of n-bit signed binary numbers is straightforward
using the 2’s complement system.
 The addition is carried out just as if all the numbers were
positive, and any carry from the sign position is ignored.
 This will always yield the correct result except when an
overflow occurs.
 When the word length is n bits, we say that an over- flow has
occurred if the correct representation of the sum (including
sign) requires more than n bits.
 The different cases which can occur are illustrated below for
n = 4.
51
 Examples’ addition in 2’s
complement

52
 Examples

Note that an overflow condition (cases 2 and 6) is easy to detect because in case 2
the addition of two positive numbers yields a negative result, and in case 6 the
addition of two negative numbers yields a positive answer (for four bits).
53
 5. Addition of 1’s
Complement Numbers
 The addition of 1’s complement numbers is similar to 2’s complement except that
instead of discarding the last carry, it is added to the n-bit sum in the position furthest
to the right.
 This is referred to as an end-around carry.
 The addition of positive numbers is the same as illustrated for cases 1 and 2 under 2’s
complement.
 The remaining cases are illustrated below (n = 4).

54
 Cont..

• Again, note that the overflow in case 6 is easy to detect because the addition of
two negative numbers yields a positive result.
• Alternatively An overflow occurs if and only if the carry out of the sign position is
not equal to the carry into the sign position.
55
 Exercise
1. Add −11 and −20 in 1’s complement.

2. Add −8 and +19 in 2’s complement

3. Add −18 and -19 in 2’s complement

4. Add +11 and +20 in 1’s complement.

56
 Exercise 2

 Add the following numbers in binary using 2’s complement to

represent negative numbers.
 Use a word length of 6 bits (including sign) and indicate if an
overflow occurs.
 Repeat (a), (c), (e), and (g) using 1’s complement to represent
negative numbers.
1. 21 + 11
2. (−14) + (−32)
3. (−25) + 18
4. (−12) + 13

57
 Binary Codes

 Although most large computers work internally with binary numbers, the
input- output equipment generally uses decimal numbers.
 Because most logic circuits only accept two-valued signals, the decimal
numbers must be coded in terms of binary signals.
 In the simplest form of binary code, each decimal digit is replaced by
its binary equivalent.
 For example, 937.25 is represented by

 This representation is referred to as binary-coded-decimal (BCD) or more

explicitly as 8-4-2-1 BCD.
 Note that the result is quite different than that obtained by convert- ing the
number as a whole into binary.
 Because there are only ten decimal digits, 1010 through 1111 are not valid
BCD codes.
58
 Table 1-2 binary codes for decimal digits

59
 Binary codes
 Table 1-2 shows several possible sets of binary codes for the ten
decimal digits.
 Many other possibilities exist because the only requirement for a valid
code is that each decimal digit be represented by a distinct
combination of binary digits.
 To translate a decimal number to coded form, each decimal digit is
replaced by its corresponding code.
 Thus 937 expressed in excess-3 code is 1100 0110 1010.
 The 8-4-2-1 (BCD) code and the 6-3-1-1 code are examples of weighted
codes.
 A 4-bit weighted code has the property that if the weights are w3, w2,
w1, and w0, the code a3a2a1a0 represents a decimal number N, where
– 𝑁 = 𝑤3 𝑎3 + 𝑤2 𝑎2 + 𝑤1 𝑎1 + 𝑤0 𝑎0
 For example, the weights for the 6-3-1-1 code are w3 = 6, w2 = 3, w1 = 1,
and w0 = 1. The binary code 1011 thus represents the decimal digit
 N = 6·1 + 3·0 + 1·1 + 1·1 = 8

60
 ASCII CODE
 Many applications of computers require the processing of data which
contains numbers, letters, and other symbols such as punctuation marks.
 In order to transmit such alphanumeric data to or from a computer or store
it internally in a computer, each symbol must be represented by a binary
code.
 One common alphanumeric code is the ASCII code (American Standard
Code for Information Interchange).
 This is a 7-bit code, so 27(128) different code combinations are available to
represent letters, numbers, and other symbols.
 Table 1-3 shows a portion of the ASCII code; the code combinations not
listed are used for special control functions such as “form feed” or “end of
transmission.
 ” The word “Start” is represented in ASCII code as follows:

61
62
63
 EXERCISE 3

1). Is it possible to construct a 5-4-1-1 weighted code?

2). Is it possible to construct A 6-3-2-1 weighted code? Justify your answers.

3). Construct a 5-2-2-1 weighted code for decimal digits.

4).What numbers does 1110 0110 represent in this code?

5) Represent your full name in ASCII CODE

64
 UNIT -III
BOOLEAN ALGEBRA
& LOGIC GATES

65
 INTRODUCTION
 The basic mathematics needed for the study of logic design of digital
systems is Boolean algebra.
 Boolean algebra is Developed by English Mathematician George Boole in
between 1815 – 1864 and used it to solve problems in mathematical logic.
 It is described as an algebra of logic or an algebra of two values i.e True or False.
 The term logic means a statement having binary decisions i.e True/Yes or
False/No.
 Boolean algebra has many other applications, including set theory and
mathematical logic; however, we primarily consider its application to switching
circuits.
 All of the switching devices we will use are essentially two- state devices (e.g.,
switches which are open or closed and transistors with high or low output
voltages).
 Consequently, we will emphasize the special case of Boolean algebra in which
all of the variables assume only one of two values; this two-valued Boolean
algebra is often called switching algebra.

66
 Definition of Some Terminologies
 Formal logic: In formal logic, a statement (proposition) is a
declarative sentence that is either true(1) or false (0).
– It is easier to communicate with computers using formal logic.
 Boolean variable: Takes only two values –either true (1) or
false (0).
– They are used as basic units of formal logic.
 Boolean function: Mapping from Boolean variables to a
Boolean value.
 • Truth table:
– Represents relationship between a Boolean function and its binary
variables.
– It enumerates all possible combinations of arguments and the
corresponding function values.

67
 …cont

 Boolean algebra: Deals with binary variables and logic

operations operating on those variables.
 Logic diagram: Composed of graphic symbols for logic
gates. A simple circuit sketch that represents inputs and
outputs of Boolean functions.

68
 Application of Boolean algebra
 It is used to perform the logical operations in digital computer.
 In digital computer True represent by ‘1’ (high volt) and False represent by ‘0’ (low volt)
 The symbols “0” and “1” used in Boolean algebra do not have a numeric value;
 Instead they represent two different states in a logic circuit and are the two values of a
switching variable.
 In a logic gate circuit, 0 (usually) represents a range of low voltages, and 1 represents a range of
high voltages.
 In a switch circuit, 0 (usually) represents an open switch, and 1 represents a closed circuit.
 In general, 0 and 1 can be used to represent the two states in any binary-valued system.
 Logical operations are performed by logical operators.
 The fundamental logical operators are:
1. AND (conjunction)
2. OR (disjunction)
3. NOT (negation/complement)

69
 Boolean operators
AND-OPERATOR versus OR-OPERATOR

 AND OPERATOR performs logical multiplication and denoted by

(.) dot.
 OR OPERATOR performs logical addition and denoted by (+)
plus.
X Y X.Y X+Y
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 1
 NOT OPERATOR performs logical negation and denoted by (-) bar.
 It operates on single variable.
X 𝑋ത (means complement of x)
0 1
1 0
70
 Definitions

 Literal: A variable or its complement

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

71
 Truth table
 Truth table is a table that contains all possible values of
logical variables/statements in a Boolean expression.
 It enumerates all possible combinations of arguments
and the corresponding function values.
 Represents relationship between a Boolean function
and its binary variables.
 𝑵𝒐. 𝒐𝒇 𝒑𝒐𝒔𝒔𝒊𝒃𝒍𝒆 𝒄𝒐𝒎𝒃𝒊𝒏𝒂𝒕𝒊𝒐𝒏 = 𝟐𝒏 , where n=number of
variables used in a Boolean expression.

72
 Implementation
 Boolean Algebra is applied in computers electronic circuits.
 These circuits perform Boolean operations and they are called logic
circuits or logic gates.
Logic gates:
 Refer to the hardware to implement Boolean operators.
 A Logic gate is an digital circuit which operates on one or more signals
and produce single output.
 Gates are digital circuits because the input and output signals are
denoted by either 1(high voltage) or 0(low voltage).
 They can be classified as Basic and Derived

There are three basic gates and are:

AND GATE,OR GATE & NOT / INVERTER GATE
There are Four Derived logic gates
NAND,NOR, XOR & XNOR
73
 Logic gates
Derived logic gates
Basic logic gates

74
 Four Derived logic gates

75
 Basic Identities Of Boolean
Algebra
Postulate 1 (Definition):
– A Boolean algebra is a closed algebraic system
containing a set K of two or more elements and
the two operators · and + which refer to logical
AND and logical OR

76
 Basic Theorem of Boolean Algebra
T1 : Properties of 0 T6 : Indempotence (Identity ) Law
•(a) 0+A=A
(a) A + A = A
•(b) 0·A = 0 (b) A A = A
T2 : Properties of 1 T7 : Absorption (Redundancy) Law
•(a) 1+A=1
(a) A + A  B = A
•(b) 1·A = A (b) A (A + B) = A
T3 : Commutative Law T8 : Complementary Law
•(a) A+B=B+A (a) A+A’=1
•(b) A·B = B·A (b) A.A’=0
T4 : Associative Law T9 : Involution
•(A + B) + C = A + (B + C)
•(A·B) C = A (B·C)
(a) A’’ = A
T10 : De Morgan's Theorem
T5 : Distributive Law
•(a) A (B + C) = A ·B + A C
(a) (A+B)’=A’.B’
•(b) A + (B·C) = (A + B) (A + C) (b) (A.B)’=A’+B’
•(c) A+A’B = A+B

77
 Function Minimization using Boolean Algebra

Examples:
1. a + ab = a(1+b)=a
2. a(a + b) = a.a +ab=a+ab=a(1+b)=a.
3. a + a'b = (a + a')(a + b)=1(a + b) =a+b
4. a(a' + b) = a. a' +ab=0+ab=ab
DeMorgan's Theorem
Generalized DeMorgan's Theorem
(a) (a + b + … z)' = a'b' … z'
(b) (a.b … z)' = a' + b' + …+ z'

78
 DeMorgan's example

 Show that: (a(b + z(x + a')))' =a' + b' (z' + x')

SOLUTION
(𝒂(𝒃 + 𝒛(𝒙 + 𝒂′)))′ = 𝒂′ + (𝒃 + 𝒛(𝒙 + 𝒂′))‘

= 𝒂′ + 𝒃′ (𝒛(𝒙 + 𝒂′))′ = 𝒂′ + 𝒃′ (𝒛′ + (𝒙 + 𝒂′)′)

= 𝒂′ + 𝒃′ (𝒛′ + 𝒙′(𝒂′)′) = 𝒂′ + 𝒃′ (𝒛′ + 𝒙′𝒂)

= 𝒂‘ + 𝒃′ 𝒛′ + 𝒃′𝒙′𝒂 = (𝒂‘ + 𝒃′𝒙′𝒂) + 𝒃′ 𝒛′

= (𝒂‘ + 𝒃′𝒙‘)(𝒂 + 𝒂‘) + 𝒃′ 𝒛′ = 𝒂‘ + 𝒃′𝒙‘ + 𝒃′ 𝒛‘

= 𝒂′ + 𝒃′ (𝒛′ + 𝒙′)
79
 EXERCISE

 DeMorgan's Theorem
 F = ab + c’d’ , Find F’
 F = ab + c’d’+ b’d, Find F’

80
 Canonical and Standard Forms
 We need to consider formal techniques for the
simplification of Boolean functions.
 ◦ Identical functions will have exactly the same
canonical form.
 Minterms and Maxterms
– Sum-of-Minterms and Product-of- Maxterms
 Product and Sum terms
– Sum-of-Products (SOP) and Product-of-Sums (POS)

81
 Truth Table notation for Minterms and
Maxterms

82
 Canonical Forms (cont.)

 Canonical Sum-Of-Products: The minterms included are

those mj such that F( ) = 1 in row j of the truth table for F( ).
 Canonical Product-Of-Sums: The maxterms included are
those Mj such that F( ) = 0 in row j of the truth table for F( ).

83
 Example

84
 Conversion Between Canonical Forms

 Replace ∑ with (or vice versa) and replace those j’s that
appeared in the original form with those that do not.
 Example:f1(a,b,c) = a’b’c + a’bc’ + ab’c’ + abc’
– = m1 + m2 + m4 + m6
– = ∑(1,2,4,6) = (0,3,5,7)
– = (a+b+c)•(a+b’+c’)•(a’+b+c’)•(a’+b’+c’)

85
 Conversion of POS from standard to canonical form

 Expand noncanonical terms by adding 0 in terms of

missing variables (e.g., xx’ = 0) and using the distributive
law
 Remove duplicate maxterms
 f1(a,b,c) = (a+b+c)•(b’+c’)•(a’+c’)
 = (a+b+c)•(aa’+b’+c’)•(a’+bb’+c’)
 = (a+b+c)•(a+b’+c’)•(a’+b’+c’)• (a’+b+c’)•(a’+b’+c’)
 = (a+b+c)•(a+b’+c’)•(a’+b’+c’)•(a’+b+c’)

86
 Conversion of SOP from standard to canonical form

 Expand non-canonical terms by inserting equivalent of

1 in each missing variable x: (x + x’) = 1
 Remove duplicate minterms
 f1(a,b,c) = a’b’c + bc’ + ac’
 = a’b’c + (a+a’)bc’ + a(b+b’)c’
 = a’b’c + abc’ + a’bc’ + abc’ + ab’c’
 = a’b’c + abc’ + a’bc + ab’c’

87
 Canonical Forms (Unique)

 Any Boolean function F( ) can be expressed as a unique

sum of Minterms and a unique product of Maxterms
(under a fixed variable ordering).
 In other words, every function F() has two canonical forms:
– ◦ Canonical Sum-Of-Products (sum of minterms)
– ◦ Canonical Product-Of-Sums (product of maxterms)

88
 Two Level implementation

• 1. NAND-AND
Two level • 2. AND-NOR
Implementation
• 3. NOR-OR
using:
• 4. OR-NAND

89
 NAND-AND Implementation

90
 It can also be implemented using AND-NOR
circuit as it is equivalent to NAND- AND circuit

=(XZ) .(Y’Z).(X’YZ)

AND-NOR circuit NAND- AND circuit

91
 NOR-OR & OR-NAND Implementation

92
 It can also be implemented using OR-NAND
circuit as it is equivalent to NOR-OR circuit

NOR-OR circuit
OR-NAND circuit
93
 Universal Gates

 NAND & NOR gates are known as Universal logic gates.

 Any logic gate function can be implemented using
universal gates.

94
 NAND AS A UNIVERSAL GATE

95
 NOR AS A UNIVERSAL GATE

96
 Simplification of Boolean Expressions using Karnaugh Maps
 Karnaugh maps provide a systematic method to obtain
simplified sum-of-products (SOPs) Boolean expressions.
 This is a compact way of representing a truth table and is a technique
that is used to simplify logic expressions.
 It is ideally suited for four or less variables, becoming cumbersome for five
or more variables.
 Each square represents either a minterm or maxterm.
 A K-map of n variables will have 2 squares.
 For a Boolean expression, product terms are denoted by 1's, while sum
terms are denoted by 0's.
 A K-map consists of a grid of squares, each square representing one
canonical minterms combination of the variables or their inverse.
 The map is arranged so that squares representing minterms which
differ by only one variable are adjacent both vertically and horizontally.
97
98
CHAPTER-4

Design of combinational
logic circuits
 Chapter 4 Design of combinational logic circuits

Chapter outline
I. Introduction to combinational circuits
II. How to Design Combinational Circuits
III. Design of some commonly used Combinational
circuits.
a) Design of Magnitude comparators
b) Design of arithmetic circuits
c) Design of code convertors
d) Design of medium scale circuits (Decoders ,
Encoders, Multiplexors & Demultiplexers)
10
0
 I. Introduction to combinational circuits…

 In previous lectures we learned all the fundamentals

needed for making circuits.
 Truth tables and Boolean expressions describe functions.
 Expressions can be converted to circuits.
 Boolean algebra and K-maps help simplify expressions and
circuits.
 Afterwards we’ll apply all of these foundations to work with
some larger circuits.
10
1
  A combinational circuit is one where the present
I. Introduction to
combinational circuits output at any time depends only on the present
….. (2) combination of inputs at that point of time.
 A combinational circuit consists of input variables,
logic gates and output variables.
 The logic gates accept signals from the
input variables and generate output signals.
 More complex combinational circuits such as
Adders and Subtractors, Multiplexers and
Demultiplexers, Magnitude Comparators, Decoders
and Encoders , Code Converters , etc., can be
implemented using a combination of logic gates.

10
2
 II . How to Design Combinational Circuits?...cont’d
(1)

 How to specify combinational circuit to be designed?

 The combinational circuits can be specified in one of
the following ways:
 A set of statements
 Boolean expression, and
 Truth table.

10
3
 II . How to Design Combinational Circuits?..... cont’d (2)
 The following guidelines should be followed while choosing the preferred form for hardware
implementation:

1. The implementation should have the minimum number of

gates, having the minimum number of inputs.

2. There should be a minimum number of interconnections, and the

propagation time should be the shortest.

3. Limitation on the driving capability of the gates should not be

ignored.

 It is difficult to generalize as to what constitutes an acceptable simplified

Boolean expression.
10  The importance of each of the above-mentioned aspects is governed by the
4 nature of application.
 II . How to Design Combinational
Circuits?..... cont’d (3)
 The goal in circuit design is to build hardware that solves some problem.
 The basic approach is to express the solution as a Boolean function, which can then be
converted to a circuit.

1. Figure out how many inputs and outputs

you need.
2. Describe the function as a truth table or
a Boolean expression.
3. Find a simplified Boolean expression
for the function.
4. Build the circuit based on your
simplified expression.
10
5
 II. Design of some commonly used
Combinational circuits.
 In this section we will see how to design the following
combinational circuits.
1. Design of Magnitude comparators
2. Design of arithmetic circuits
3. Design of code convertors
4. Design of medium scale circuits (Decoders , Encoders,
Multiplexors & Demultiplexers)

10
6
 a) Design of Magnitude comparators

 A magnitude comparator is a combinational circuit that compares two given

numbers and determines whether one is equal to, less than or greater than
the other.
 The output is in the form of three binary variables representing the conditions A
= B, A > B and A < B, if A & B are the two numbers being compared.
 Depending upon the relative magnitude of the two numbers, the relevant
output changes state.
 Magnitude comparator,
1. One -bit magnitude comparator or
[Link] bits magnitude comparator

10
7
 Example 1: Design of One -bit magnitude
comparator
 Let’s design a circuit that compares two One -bit numbers, A
and B.
 There are three possible results: A > B, A = B or A < B.
 We will represent the results using three separate outputs.
— G (“Greater”) should be 1 only when A > B.
— E (“Equal”) should be 1 only when A = B.
— L (“Lesser”) should be 1 only when A < B.
 Make sure you understand the problem!
 Inputs A and B will be 0 or 1(0 or 1 in decimal).
 For any inputs A and B, exactly one of the three outputs will
be 1.
10
8
 Step1: How many inputs and outputs?

 How many inputs and outputs will this circuit have?

 I n p u t s : Two 1-bit numbers means a total of Two inputs.
 Let’s say the first number consists of bits called A0
 while second number has bits B0.
The problem specifies three outputs: G, E and L.

Figure 4.2. a block

diagram of one-bit
magnitude comparator.
 Now the hard part is to design the circuitry that goes inside the
box.
10
9
 Step 2: Functional specification

 For this problem, it’s probably easiest to start with a truth table.
 This way we can explicitly show the relationship (>,=, <) between
the inputs.
 A two-input function has a four-row truth table.
 For convenience, the rows are in binary numeric order from 00
to 11 for A0 and B0.

A0 B0 G E L
0 0 0 1 0
0 1 0 0 1
1 0 1 0 0
1 1 0 1 0

110
 Step 3: Simplified Boolean expressions

A0 B0 G E L
0 0 0 1 0
0 1 0 0 1
1 0 1 0 0
1 1 0 1 0

 Let’s use Boolean algebra to simplify our circuit.

 There are three functions (each with the same inputs A0 B0).
 𝐆(𝐀𝟎, 𝐁𝟎) = 𝐀𝟎𝐁𝟎’
 𝐄(𝐀𝟎, 𝐁𝟎) = 𝐀𝟎’𝐁𝟎’ + 𝐀𝟎𝐁𝟎
 𝐋(𝐀𝟎, 𝐁𝟎) = 𝐀𝟎’𝐁𝟎

111
 Step 4: Drawing the circuits
 𝐆(𝐀𝟎, 𝐁𝟎) = 𝐀𝟎𝐁𝟎’
 𝐋(𝐀𝟎, 𝐁𝟎) = 𝐀𝟎’𝐁𝟎

 𝐄 𝐀𝟎, 𝐁𝟎 = 𝐀𝟎’𝐁𝟎’ + 𝐀𝟎𝐁𝟎 = 𝐀𝟎 ⊕ 𝐁𝟎

Figure 4.3. circuit diagram of one-bit

magnitude comparator.
112
 Example 2:
Design of 2-bitmagnitude comparator

 Let’s design a circuit that compares two 2-bit numbers, A and

B.
 There are three possible results: A > B, A = B or A < B.
 We will represent the results using three separate outputs.
 — G (“Greater”) should be 1 only when A > B.
 — E (“Equal”) should be 1 only when A = B.
 — L (“Lesser”) should be 1 only when A < B.
 Make sure you understand the problem!
 — Inputs A and B will be 00, 01, 10, or 11 (0, 1, 2 or 3 in
decimal).
 — For any inputs A and B, exactly one of the three outputs will
be 1.

113
 Step1: How many inputs and outputs?
 Step1: How many inputs and outputs?
 How many inputs and outputs will this circuit have?
 — Two 2-bit numbers means a total of four inputs.
 Let’s say the first number consists of bits called A1 and
A0 (from left to right), while second number has bits B1
and B0.
 The problem specifies three outputs: G, E and L.
 Here is a block diagram that shows the inputs and
outputs explicitly.

114
 Step 2: Functional
specification A1 A0 B1 B0 G E L
0 0 0 0 0 1 0
0 0 0 1 0 0 1
0 0 1 0 0 0 1
0 0 1 1 0 0 1
A four-input function has 0 1 0 0 1 0 0
a sixteen-row truth table.
0 1 0 1 0 1 0
For convenience, the
rows are in binary 0 1 1 0 0 0 1
numeric order from 0000 0 1 1 1 0 0 1
to 1111 for A1, A0, B1
and B0. 1 0 0 0 1 0 0
1 0 0 1 1 0 0
1 0 1 0 0 1 0
1 0 1 1 0 0 1
1 1 0 0 1 0 0
1 1 0 1 1 0 0
1 1 1 0 1 0 0
1 1 1 1 0 1 0
Truth table of 2 bit comparator.

115
 Step 3: Simplified Boolean expressions
 Let’s use K-maps to simplify our circuit.
 There are three functions (each with the same inputs A1 A0
B1 B0), so we need three K-maps.

116
 Step 3: Simplified Boolean expressions… cnt’d
 From the above three K-maps for G,L & E functions can be written as
follows.
 G = A1 A0 B0’ + A0 B1’B0’ + A1 B1’
 E = A1’A0’B1’B0’ + A1’A0 B1’B0 + A1 A0 B1 B0 + A1 A0’B1 B0’
 L = A1’A0’B0 + A0’B1 B0 + A1’B1
 These Boolean functions can be re-arranged as follows.
1. E = A1’A0’B1’B0’ + A1’A0 B1’B0 + A1 A0 B1 B0 + A1 A0’B1 B0’
E = A1B1 + A1’B1’ . A0B0 + A0’B0’ = X1.X0
,where X1 = A1B1 + A1’B1’ and X0 = A0B0 + A0’B0’
2. G = A1B1’ + X1A0B0’
3. L = A1’B1 + X1A0’B0

117
 Step 4: Drawing the circuits
𝐸 = 𝑋1 . 𝑋 0 ,
𝑤ℎ𝑒𝑟𝑒 𝑋1 = 𝐴1𝐵1 + 𝐴1’𝐵1’ 𝑎𝑛𝑑 𝑋0 = 𝐴0𝐵0 + 𝐴0’𝐵0’
𝐺 = 𝐴1𝐵1’ + 𝑋1𝐴0𝐵0’
𝐿 = 𝐴1’𝐵1 + 𝑋1𝐴0’𝐵0

118
  Half-adder,

 Full Adder,

 Half- Subtractor,
4.3 Arithmetic
Circuits  Full Subtractor And

 Full Adder-subtractor Or

 Controlled Inverter.

119
 4.3 Design of Arithmetic Circuits
 Addition and subtraction are the two most commonly used arithmetic
operations,
 We will begin with the basic building blocks that form the basis of all
hardware used to perform the aforesaid arithmetic operations on binary
numbers.
 These include
 Half-adder, Full Adder,
 Half- Subtractor, Full Subtractor And
 Full Adder-subtractor Or Controlled Inverter.

12
0
 a) Design of Half-Adder (HA)
A half-adder (HA) is an arithmetic circuit or block that can be used to add two bits,
And produce sum and carry.

Step1: How many inputs and outputs? Step 2: Functional specification

• HA Has two inputs that represent the
 The input-output variables
two bits to be added; i.e. (A , B)
• It has two outputs, i.e. ;The SUM (S) relation can be seen from truth
output and the CARRY( C ) output. table shown below on (b)
• HA block diagram is shown
below

12
1
 Step 3: Derive and Simplify Boolean expressions
 Before implementing the logic circuit we need to derive
Boolean expression for both outputs separately from the
truth table.
 SUM: 𝐒 = 𝐀’𝐁 + 𝐀𝐁’ = 𝐀 ⊕ 𝐁
 CARRY: 𝐂=𝐀⋅𝐁
 We can see that the Boolean expression cannot
simplified further.

12
2
 Step 4: Drawing the circuits
 Although the simplest way to hardware-implement a
half-adder would be to use a two-input EX-OR gate for
the SUM output and a two-input AND gate for the
CARRY output, as shown in Fig. 3.3(a),
 it could also be implemented by using an appropriate
arrangement of either NAND or NOR gates.

12
3
 4.3.2 Design of full -Adder (FA)
 A full adder circuit is an arithmetic circuit block that can be
used to add three bits to produce a SUM and a CARRY
output.
 We begin with the addition of LSBs of the two numbers.
 We record the sum under the LSB column and take the carry,
if any, forward to the next higher column bits.
 As a result, when we add the next adjacent higher column
bits, we would be required to add three bits if there were a
carry from the previous addition.
 We have a similar situation for the other higher column bits
also until we reach the MSB.
 Such a building block becomes a necessity when it comes to
adding binary numbers with a large number of bits.
12
4
 
Step1: How many inputs and outputs?
FA Has three inputs that represent the two bits to be
added; i.e. (Ai , Bi, Ci)
 It has two outputs, i.e. ;The SUM (S) output and the
CARRY( C ) output.
 FA block diagram is shown below

12
5
 Cnt’d…..

Step 3: Derive and Simplify Boolean

Step2: Functional specification expressions

A B Cn Si Co Cn
'0 '1 Cn
0 0 0 0 0 '0 '1
'00 1
0 0 1 1 0 '01 1 '00
0 1 0 1 0 AB '11 1 '01 1
AB
0 1 1 0 1 '11 1 1
'10 1
1 0 0 1 0 '10 1
b). c).
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1  𝑆𝑖 = 𝑨 ⨁𝑩 ⨁𝑪𝒏
a).
 𝑪𝟎 = 𝑨. 𝑩 + 𝑨⨁𝑩 . 𝑪𝒏
Truth table of Full Adder

12
6
 Step 4: Drawing the circuits

12
7
 
Ripple-Carry (n-bit parallel) full Adder
The problem of adding two multi digit binary numbers has
the following form.
 Two n-bit binary numbers are available, with all digits being
presented in parallel.
 The addition is performed by using a full adder to add each
corresponding pair of digits, one from each number.
 The full adders are connected in tandem so that the carry
out from one stage becomes the carry into the next stage.
 Thus, the carry ripples through each stage

12
8
 
Ripple-Carry
For binary addition,(n-bit parallel)
the carry into the full Adder
first (least significant) stage is 0.
 The last carry out (the overflow carry)
becomes the most significant bit of
the (n + 1)-bit sum.
 Since the carry of each full adder has
a propagation delay of 2tp, the total
delay in carrying out the sum of two
n-bit numbers is 2ntp.
 Not every pair of two n-bit numbers
will experience this much delay.
12
9
 Half-subtractor Vs Full-subtractor
HALF-SUBTRACTOR FULL SUBTRACTOR

 is a combinational circuit  performs subtraction operation on

that can be used to subtract two bits, a minuend and a
one binary digit from subtrahend,
another to produce a  And also takes into consideration
DIFFERENCE output and a whether a ‘1’ has already been
borrowed by the previous
BORROW output. The
adjacent lower minuend bit or not.
BORROW output here
 There are two outputs, namely the
specifies whether a ‘1’ has
DIFFERENCE output D and the
been borrowed to perform BORROW output Bo.
the subtraction.
13
0
13
1
 TWO’S-COMPLEMENT ADDER AND
SUBTRACTOR
 The design of our two’s complement adder/subtractor
circuit is complete; a version for adding 4-bit numbers
is shown in Figure 3.11.
 If the control signal M is 0, then the circuit performs A+B;
however, if M is 1, the circuit performs A - B.

13 Figure 3.11 two’s complement adder/subtractor with overflow detection.

2
 DECODERS vs ENCODERS

13
3
13
4
13
5
13
6
13
7
13
8
13
9
14
0
14
1
14
2
 Multiplexers vs Demultiplexers

14
3
14
4
14
5
14
6
14
7