DIGITAL LOGIC DESIGN

B.Tech CSE 2nd year

JNTU(HYDERABAD)
TELANGANA EDUCATIONAL HUB

IN ASSOCIATION WITH CYBERSOFT MEDIA

Page 1
 UNIT-I

1.1 DIGITAL SYSTEMS

Digital systems have such a prominent role in everyday life that we refer to the present
technological period as the digital age. Digital systems are used in communication, business
transactions, traffic control, spacecraft guidance, medical treatment, weather monitoring, the
Internet, and many other commercial, industrial, and scientific enterprises.

One characteristic of digital systems is their ability to represent and manipulate discrete
elements of information. Any set that is restricted to a finite number of elements contains
discrete information. Examples of discrete sets are the 10 decimal digits, the 26 letters of the
alphabet, the 52 playing cards, and the 64 squares of a chessboard. Early digital computers were
used for numeric computations.

ub
Discrete elements of information are represented in a digital system by physical
quantities called signals. Electrical signals such as voltages and currents are the most common.
Electronic devices called transistors predominate in the circuitry that implements these signals.
The signals in most present‐day electronic digital systems use just two discrete values and are
therefore said to be binary. A binary digit, called a bit, has two values: 0 and 1. Discrete
uh
elements of information are represented with groups of bits called binary codes. For example, the
decimal digits 0 through 9 are represented in a digital system with a code of four bits (e.g., the
number 7 is represented by 0111).
ed

A digital system is a system that manipulates discrete elements of information

represented internally in binary form. The general‐purpose digital computer is the best‐known
example of a digital system.
ts

TSEDUHUB EXCLUSIVE Page 2

 ub
uh
ed

1.2 DIGITAL NUMBER SYSTEM

ts

A digital system can understand positional number system only where there are only a few
symbols called digits and these symbols represent different values depending on the position
they occupy in the number.

Decimal Number System

The number system that we use in our day-to-day life is the decimal number system. Decimal
number system has base 10 as it uses 10 digits from 0 to 9. In decimal number system, the
successive positions to the left of the decimal point represent units, tens, hundreds, thousands
and so on.

TSEDUHUB EXCLUSIVE Page 3

Each position represents a specific power of the base (10). For example, the decimal number
1234 consists of the digit 4 in the units position, 3 in the tens position, 2 in the hundreds position,
and 1 in the thousands position, and its value can be written as

(1x1000) + (2x100) + (3x10) + (4xl) = (1x103) + (2x102) + (3x101) + (4xl00)

= 1000 + 200 + 30 + 1

= 1234

As a computer programmer or an IT professional, you should understand the following number

systems which are frequently used in computers.

S.N. Number System & Description

Binary Number System
1
Base 2. Digits used: 0, 1

ub
Octal Number System
2
Base 8. Digits used: 0 to 7
Hexa Decimal Number System
3
Base 16. Digits used: 0 to 9, Letters used: A- F
uh
Binary Number System

Characteristics
ed

 Uses two digits, 0 and 1.

 Also called base 2 number system
 Each position in a binary number represents a 0 power of the base (2). Example 20
 Last position in a binary number represents a x power of the base (2). Example 2 x where
ts

x represents the last position - 1.

Example

Binary Number: 101012

Calculating Decimal Equivalent:

Step Binary Number Decimal Number

Step 1 101012 ((1 x 24) + (0 x 23) + (1 x 22) + (0 x 21) + (1 x 20))10
Step 2 101012 (16 + 0 + 4 + 0 + 1)10
Step 3 101012 2110

TSEDUHUB EXCLUSIVE Page 4

Note: 101012 is normally written as 10101.

Octal Number System

Characteristics

 Uses eight digits, 0,1,2,3,4,5,6,7.

 Also called base 8 number system
 Each position in a octal number represents a 0 power of the base (8). Example 80
 Last position in a octal number represents a x power of the base (8). Example 8 x where x
represents the last position - 1.

Example

Octal Number: 125708

ub
Calculating Decimal Equivalent:

Step Octal Number Decimal Number

Step 1 125708 ((1 x 84) + (2 x 83) + (5 x 82) + (7 x 81) + (0 x 80))10
uh
Step 2 125708 (4096 + 1024 + 320 + 56 + 0)10
Step 3 125708 549610

Note: 125708 is normally written as 12570.

ed

Hexadecimal Number System

Characteristics
ts

 Uses 10 digits and 6 letters, 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F.

 Letters represents numbers starting from 10. A = 10. B = 11, C = 12, D = 13, E = 14, F =
15.
 Also called base 16 number system
 Each position in a hexadecimal number represents a 0 power of the base (16). Example
160
 Last position in a hexadecimal number represents a x power of the base (16). Example
16x where x represents the last position - 1.

Example

Hexadecimal Number: 19FDE16

Calculating Decimal Equivalent:

TSEDUHUB EXCLUSIVE Page 5

 Binary
Step Decimal Number
Number
Step 1 19FDE16 ((1 x 164) + (9 x 163) + (F x 162) + (D x 161) + (E x 160))10
((1 x 164) + (9 x 163) + (15 x 162) + (13 x 161) + (14 x
Step 2 19FDE16
160))10
Step 3 19FDE16 (65536+ 36864 + 3840 + 208 + 14)10
Step 4 19FDE16 10646210

Note: 19FDE16 is normally written as 19FDE.

1.3 NUMBER BASE CONVERSIONS

There are many methods or techniques which can be used to convert numbers from one base to
another. We'll demonstrate here the following

ub
 Decimal to Other Base System
 Other Base System to Decimal
 Other Base System to Non-Decimal
 Shortcut method - Binary to Octal
 Shortcut method - Octal to Binary
uh
 Shortcut method - Binary to Hexadecimal
 Shortcut method - Hexadecimal to Binary

Decimal to Other Base System

ed

Step 1 - Divide the decimal number to be converted by the value of the new base.
Step 2 - Get the remainder from Step 1 as the rightmost digit (least significant digit) of new
base number.
Step 3 - Divide the quotient of the previous divide by the new base.
ts

Step 4 - Record the remainder from Step 3 as the next digit (to the left) of the new base
number.
Repeat Steps 3 and 4, getting remainders from right to left, until the quotient becomes zero in
Step 3.

The last remainder thus obtained will be the most significant digit (MSD) of the new base
number.

Example

Decimal Number: 2910

Calculating Binary Equivalent:

TSEDUHUB EXCLUSIVE Page 6

Step Operation Result Remainder
Step 1 29 / 2 14 1
Step 2 14 / 2 7 0
Step 3 7/2 3 1
Step 4 3/2 1 1
Step 5 1/2 0 1

As mentioned in Steps 2 and 4, the remainders have to be arranged in the reverse order so that
the first remainder becomes the least significant digit (LSD) and the last remainder becomes the
most significant digit (MSD).

Decimal Number: 2910 = Binary Number: 111012.

Other base system to Decimal System

ub
Step 1 - Determine the column (positional) value of each digit (this depends on the position
of the digit and the base of the number system).
Step 2 - Multiply the obtained column values (in Step 1) by the digits in the corresponding
columns.
Step 3 - Sum the products calculated in Step 2. The total is the equivalent value in decimal.
uh
Example

Binary Number: 111012

ed

Calculating Decimal Equivalent:

Step Binary Number Decimal Number

Step 1 111012 ((1 x 24) + (1 x 23) + (1 x 22) + (0 x 21) + (1 x 20))10
ts

Step 2 111012 (16 + 8 + 4 + 0 + 1)10

Step 3 111012 2910

Binary Number: 111012 = Decimal Number: 2910

Other Base System to Non-Decimal System

Step 1 - Convert the original number to a decimal number (base 10).

Step 2 - Convert the decimal number so obtained to the new base number.
Example

Octal Number: 258

Calculating Binary Equivalent:

TSEDUHUB EXCLUSIVE Page 7

Step 1: Convert to Decimal

Step Octal Number Decimal Number

Step 1 258 ((2 x 81) + (5 x 80))10
Step 2 258 (16 + 5 )10
Step 3 258 2110

Octal Number: 258 = Decimal Number: 2110

Step 2: Convert Decimal to Binary

Step Operation Result Remainder

Step 1 21 / 2 10 1
Step 2 10 / 2 5 0

ub
Step 3 5/2 2 1
Step 4 2/2 1 0
Step 5 1/2 0 1

Decimal Number: 2110 = Binary Number: 101012

uh
Octal Number: 258 = Binary Number: 101012

Shortcut method - Binary to Octal

ed

Step 1 - Divide the binary digits into groups of three (starting from the right).
Step 2 - Convert each group of three binary digits to one octal digit.

Example
ts

Binary Number: 101012

Calculating Octal Equivalent:

Step Binary Number Octal Number

Step 1 101012 010 101
Step 2 101012 28 58
Step 3 101012 258

Binary Number: 101012 = Octal Number: 258

TSEDUHUB EXCLUSIVE Page 8

Shortcut method - Octal to Binary

Step 1 - Convert each octal digit to a 3 digit binary number (the octal digits may be treated as
decimal for this conversion).
Step 2 - Combine all the resulting binary groups (of 3 digits each) into a single binary
number.

Example

Octal Number: 258

Calculating Binary Equivalent:

Step Octal Number Binary Number

ub
Step 1 258 210 510
Step 2 258 0102 1012
Step 3 258 0101012
uh
Octal Number: 258 = Binary Number: 101012

Shortcut method - Binary to Hexadecimal

ed

Step 1 - Divide the binary digits into groups of four (starting from the right).
Step 2 - Convert each group of four binary digits to one hexadecimal symbol.

Example
ts

Binary Number: 101012

Calculating hexadecimal Equivalent:

Step Binary Number Hexadecimal Number

Step 1 101012 0001 0101
Step 2 101012 110 510
Step 3 101012 1516

Binary Number: 101012 = Hexadecimal Number: 1516

TSEDUHUB EXCLUSIVE Page 9

Shortcut method - Hexadecimal to Binary

Step 1 - Convert each hexadecimal digit to a 4 digit binary number (the hexadecimal
digits may be treated as decimal for this conversion).
Step 2 - Combine all the resulting binary groups (of 4 digits each) into a single binary
number.

Example

Hexadecimal Number: 1516

Calculating Binary Equivalent:

Step Hexadecimal Number Binary Number

Step 1 1516 110 510

ub
Step 2 1516 00012 01012
Step 3 1516 000101012

Hexadecimal Number: 1516 = Binary Number: 101012

uh
ed
ts

TSEDUHUB EXCLUSIVE Page 10

 ub
1.4 BINARY ARITHMETIC
Binary arithmetic is essential part of all the digital computers and many other digital systems.
uh
Binary Addition
It is a key for binary subtraction, multiplication, division. There four rules of the binary addition.
ed
ts

In fourth case, a binary addition is creating a sum of (1+1=10) i.e. 0 is write in the given column
and a carry of 1 over to the next column.

Example - Addition

TSEDUHUB EXCLUSIVE Page 11

Binary Subtraction

Subtraction and Borrow, these two words will be used very frequently for the binary
subtraction. There four rules of the binary substation.

Example - Subtraction

ub
uh
ed

Binary Multiplication
Binary multiplication is similar to decimal multiplication. It is simpler than decimal
multiplication because only 0s and 1s are involved. There four rules of the binary multiplication.
ts

TSEDUHUB EXCLUSIVE Page 12

Example - Multiplication

Binary Division
Binary division is similar to decimal division. It is called as the long division procedure.

ub
Example - Division
uh
ed
ts

1.5 COMPLEMENTS
Complements are used in the digital computers in order to simplify the subtraction operation and
for the logical manipulations. For each radix-r system (radix r represent base of number system)
there are two types of complements

S.N. Complement Description

1 Radix Complement The radix complement is referred to as the r's complement
Diminished Radix The diminished radix complement is referred to as the (r-1)'s
2
Complement complement

TSEDUHUB EXCLUSIVE Page 13

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 14

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 15

Example1:

Example2:

ub
uh
ed

Example3:
ts

TSEDUHUB EXCLUSIVE Page 16

Example4:

ub
uh
1.6 SIGNED BINARY NUMBERS
Positive integers (including zero) can be represented as unsigned numbers. However, to represent
negative integers, we need a notation for negative values. In ordinary arithmetic, a negative
ed

number is indicated by a minus sign and a positive number by a plus sign. Because of hardware
limitations, computers must represent everything with binary digits. It is customary to represent
the sign with a bit placed in the leftmost position of the number. The convention is to make the
sign bit 0 for positive and 1 for negative.
ts

As an example, consider the number 9, represented in binary with eight bits. +9 is represented
with a sign bit of 0 in the leftmost position, followed by the binary equivalent of 9, which gives
00001001. Note that all eight bits must have a value; therefore, 0’s are inserted following the
sign bit up to the first 1. Although there is only one way to represent +9, there are three different
ways to represent -9 with eight bits:

signed‐magnitude representation: 10001001

signed‐1’s‐complement representation: 11110110
signed‐2’s‐complement representation: 11110111

In signed‐magnitude, -9 is obtained from +9 by changing only the sign bit in the leftmost
position from 0 to 1. In signed‐1’s-complement, -9 is obtained by complementing all the bits of
+9, including the sign bit. The signed‐2’s‐complement representation of -9 is obtained by taking
the 2’s complement of the positive number, including the sign bit.

TSEDUHUB EXCLUSIVE Page 17

 ub
uh
Arithmetic Addition

The addition of two numbers in the signed‐magnitude system follows the rules of ordinary
ed

arithmetic. If the signs are the same, we add the two magnitudes and give the sum the common
sign. If the signs are different, we subtract the smaller magnitude from the larger and give the
difference the sign of the larger magnitude. For example, (+25) + (-37) = -(37 - 25) = -12 is done
by subtracting the smaller magnitude, 25, from the larger magnitude, 37, and appending the sign
of 37 to the result. This is a process that requires a comparison of the signs and magnitudes and
ts

then performing either addition or subtraction. The same procedure applies to binary numbers in
signed‐magnitude representation. In contrast, the rule for adding numbers in the
signed‐complement system does not require a comparison or subtraction, but only addition. The
procedure is very simple and can be stated as follows for binary numbers:

The addition of two signed binary numbers with negative numbers represented in signed-
2’s-complement form is obtained from the addition of the two numbers, including their
sign bits. A carry out of the sign-bit position is discarded.

TSEDUHUB EXCLUSIVE Page 18

Note that negative numbers must be initially in 2’s‐complement form and that if the sum
obtained after the addition is negative, it is in 2’s‐complement form. For example, -7 is
represented as 11111001, which is the 2s complement of +7.

In each of the four cases, the operation performed is addition with the sign bit included. Any
carry out of the sign‐bit position is discarded, and negative results are automatically in
2’s‐complement form.

ub
To determine the value of a negative number in signed‐2’s complement, it is necessary to convert
the number to a positive number to place it in a more familiar form. For example, the signed
binary number 11111001 is negative because the leftmost bit is 1. Its 2’s complement is
uh
00000111, which is the binary equivalent of +7. We therefore recognize the original negative
number to be equal to -7.

Arithmetic Subtraction
ed

Subtraction of two signed binary numbers when negative numbers are in 2’s‐complement form is
simple and can be stated as follows:

Take the 2’s complement of the subtrahend (including the sign bit) and add it to the
minuend (including the sign bit). A carry out of the sign‐bit position is discarded.
ts

This procedure is adopted because a subtraction operation can be changed to an addition

operation if the sign of the subtrahend is changed, as is demonstrated by the following
relationship:

But changing a positive number to a negative number is easily done by taking the 2’s
complement of the positive number. The reverse is also true, because the complement of a
negative number in complement form produces the equivalent positive number. To see this,
consider the subtraction (-6) - (-13) = +7. In binary with eight bits, this operation is written as
(11111010 - 11110011). The subtraction is changed to addition by taking the 2’s complement of
the subtrahend (-13), giving (+13). In binary, this is 11111010 + 00001101 = 100000111.
Removing the end carry, we obtain the correct answer: 00000111 (+7).

TSEDUHUB EXCLUSIVE Page 19

1.7 FLOATING POINT REPRESENTATION
Floating point numbers consists of two parts. The first part of the number is a signed fixed point
number, which is termed as mantissa, and the second part specifies the decimal or binary point
position and is termed as an Exponent. The mantissa can be an integer or a fraction.

Example:
A decimal +12.34 in a typical floating-point notation is 12.34=0.1234 * 102

ub
uh
This number in any of the above form (if represented in BCD) requires 17 bits for mantissa (1 for
sign and 4 each decimal digit as BCD) and 9 bits for exponent (1 for sign and 4 for each decimal
digit as BCD). Exponent indicates the correct decimal location. In the first case where exponent
is +2, indicates that actual position of the decimal point is 2 places to the right of the assumed
ed

position, while exponent –2 indicates that the assumed position of the point is 2 places towards
the left of assumed position. The assumption of the position of the point is normally the same in
a computer resulting in a consistent computational environment.
Floating-point numbers are often represented in normalized form. A floating-point number
whose mantissa does not contain zero as the most significant digit of the number is considered to
ts

be in a normalized form. For example, a BCD mantissa +370 which is 0 0011 0111 000 is in
normalized form because these leading zero’s are nor part of a 0 digit. On the other hand a binary
number 0 01100 is not in a normalized form. The normalized form of this number will be
0 1100
Arithmetic operations involved with floating point numbers are more complex in nature, takes
longer time for execution and require complex hardware. Yet the floating point representation is
a must as it is useful in scientific calculations. Real numbers are normally represented as floating
point numbers.

1.8 BINARY CODES

In the coding, when numbers, letters or words are represented by a specific group of symbols, it
is said that the number, letter or word is being encoded. The group of symbols is called as a code.
The digital data is represented, stored and transmitted as group of binary bits. This group is also

TSEDUHUB EXCLUSIVE Page 20

called as binary code. The binary code is represented by the number as well as alphanumeric
letter.

Advantages of Binary Code

Following is the list of advantages that binary code offers.

 Binary codes are suitable for the computer applications.

 Binary codes are suitable for the digital communications.
 Binary codes make the analysis and designing of digital circuits if we use the binary
codes.
 Since only 0 & 1 are being used, implementation becomes easy.

Classification of binary codes

The codes are broadly categorized into following four categories.

ub
 Weighted Codes
 Non-Weighted Codes
 Binary Coded Decimal Code
 Alphanumeric Codes
uh
 Error Detecting Codes
 Error Correcting Codes

Weighted Codes
ed

Weighted binary codes are those binary codes which obey the positional weight principle. Each
position of the number represents a specific weight. Several systems of the codes are used to
express the decimal digits 0 through 9. In these codes each decimal digit is represented by a
group of four bits.
ts

Non-Weighted Codes

In this type of binary codes, the positional weights are not assigned. The examples of non-
weighted codes are Excess-3 code and Gray code.

TSEDUHUB EXCLUSIVE Page 21

Excess-3 code

The Excess-3 code is also called as XS-3 code. It is non-weighted code used to express decimal
numbers. The Excess-3 code words are derived from the 8421 BCD code words adding (0011)2
or (3)10 to each code word in 8421. The excess-3 codes are obtained as follows

Example

ub
uh
ed

Gray Code
ts

It is the non-weighted code and it is not arithmetic codes. That means there are no specific
weights assigned to the bit position. It has a very special feature that has only one bit will
change, each time the decimal number is incremented as shown in fig. As only one bit changes at
a time, the gray code is called as a unit distance code. The gray code is a cyclic code. Gray code
cannot be used for arithmetic operation.

TSEDUHUB EXCLUSIVE Page 22

 ub
Application of Gray code

 Gray code is popularly used in the shaft position encoders.

 A shaft position encoder produces a code word which represents the angular position of
the shaft.
uh
Binary Coded Decimal (BCD) code

In this code each decimal digit is represented by a 4-bit binary number. BCD is a way to express
each of the decimal digits with a binary code. In the BCD, with four bits we can represent sixteen
ed

numbers (0000 to 1111). But in BCD code only first ten of these are used (0000 to 1001). The
remaining six code combinations i.e. 1010 to 1111 are invalid in BCD.
ts

Advantages of BCD Codes

 It is very similar to decimal system.

 We need to remember binary equivalent of decimal numbers 0 to 9 only.

Disadvantages of BCD Codes

 The addition and subtraction of BCD have different rules.

TSEDUHUB EXCLUSIVE Page 23
  The BCD arithmetic is little more complicated.
 BCD needs more number of bits than binary to represent the decimal number. So BCD is
less efficient than binary.

Alphanumeric codes
A binary digit or bit can represent only two symbols as it has only two states '0' or '1'. But this is
not enough for communication between two computers because there we need many more
symbols for communication. These symbols are required to represent 26 alphabets with capital
and small letters, numbers from 0 to 9, punctuation marks and other symbols.

The alphanumeric codes are the codes that represent numbers and alphabetic characters. Mostly
such codes also represent other characters such as symbol and various instructions necessary for
conveying information. An alphanumeric code should at least represent 10 digits and 26 letters
of alphabet i.e. total 36 items. The following three alphanumeric codes are very commonly used
for the data representation.

ub
 American Standard Code for Information Interchange (ASCII).
 Extended Binary Coded Decimal Interchange Code (EBCDIC).
 Five bit Baudot Code.
uh
ASCII code is a 7-bit code whereas EBCDIC is an 8-bit code. ASCII code is more commonly
used worldwide while EBCDIC is used primarily in large IBM computers.

1.9 CODES CONVERSION

ed

There are many methods or techniques which can be used to convert code from one format to
another. We'll demonstrate here the following

 Binary to BCD Conversion

ts

 BCD to Binary Conversion

 BCD to Excess-3
 Excess-3 to BCD

Binary to BCD Conversion

 Step 1 -- Convert the binary number to decimal.

 Step 2 -- Convert decimal number to BCD.

Example: convert (11101)2 to BCD.

Step 1 - Convert to Decimal

Binary Number: 111012

TSEDUHUB EXCLUSIVE Page 24

Calculating Decimal Equivalent:

Step Binary Number Decimal Number

Step 1 111012 ((1 x 24) + (1 x 23) + (1 x 22) + (0 x 21) + (1 x 20))10
Step 2 111012 (16 + 8 + 4 + 0 + 1)10
Step 3 111012 2910

Binary Number: 111012 = Decimal Number: 2910

Step 2 - Convert to BCD

Decimal Number: 2910

Calculating BCD Equivalent. Convert each digit into groups of four binary digits equivalent.

ub
Step Decimal Number Conversion
Step 1 2910 00102 10012
Step 2 2910 00101001BCD
uh
Result

(11101)2 = (00101001)BCD

BCD to Binary Conversion

ed

 Step 1 -- Convert the BCD number to decimal.

 Step 2 -- Convert decimal to binary.

Example: convert (00101001)BCD to Binary.

ts

Step 1 - Convert to BCD

BCD Number: (00101001) BCD

Calculating Decimal Equivalent. Convert each four digit into a group and get decimal equivalent
or each group.

Step BCD Number Conversion

Step 1 (00101001)BCD 00102 10012
Step 2 (00101001)BCD 210 910
Step 3 (00101001)BCD 2910

TSEDUHUB EXCLUSIVE Page 25

BCD Number: (00101001)BCD = Decimal Number: 2910

Step 2 - Convert to Binary

Used long division method for decimal to binary conversion.

Decimal Number: 2910

Calculating Binary Equivalent:

Step Operation Result Remainder

Step 1 29 / 2 14 1
Step 2 14 / 2 7 0
Step 3 7/2 3 1
Step 4 3/2 1 1

ub
Step 5 1/2 0 1

As mentioned in Steps 2 and 4, the remainders have to be arranged in the reverse order so that
the first remainder becomes the least significant digit (LSD) and the last remainder becomes the
most significant digit (MSD).
uh
Decimal Number: 2910 = Binary Number: 111012

Result
ed

(00101001)BCD = (11101)2

BCD to Excess-3
ts

 Step 1 -- Convert BCD to decimal.

 Step 2 -- Add (3)10 to this decimal number.
 Step 3 -- Convert into binary to get excess-3 code.

Example: convert (1001)BCD to Excess-3.

Step 1 - Convert to decimal

(1001)BCD = 910

Step 2 - Add 3 to decimal

(9)10 + (3)10 = (12)10

TSEDUHUB EXCLUSIVE Page 26

Step 3 - Convert to Excess-3

(12)10 = (1100)2

Result

(1001)BCD = (1100)XS-3

Excess-3 to BCD Conversion

Steps

 Step 1 -- Subtract (0011)2 from each 4 bit of excess-3 digit to obtain the corresponding
BCD code.

Example: convert (10011010)XS-3 to BCD.

ub
Given XS-3 number = 1001 1010

Subtract (0011)2 = 0011 0011

uh
--------------------

BCD = 0 1 1 0 0 1 1 1

Result
ed

(10011010)XS-3 = (01100111)BCD

1.10 BOOLEAN ALGEBRA

ts

BOOLE is one of the persons in a long historical chain who were concerned with formalizing
and mechanizing the process of logical thinking.
BOOLEAN ALGEBRA is a generalization of set algebra and the algebra of propositions.
Boolean algebra is a tool for studying and applying logic.

. We learn how Boolean algebra is used to construct and simplify electric circuits. Switching
circuits, which are used in the design of computer chips, are introduced with a discussion of the
techniques needed to simplify their design.

. We also show how a purely algebraic approach to some parts of logic is possible by using
BOOLEAN Algebras and how this technique can also be used to study set theory.

TSEDUHUB EXCLUSIVE Page 27

Definition:

Boolean algebra is an algebraic structure defined on a set of elements is together with two binary
operations, the product (or meet) and the sum (or join) provided the following
Huntington postulates are satisfied:

1. a. Closure with respect to the operator +

b. Closure with respect to the operator .

2. a. An identity element with respect to + is 0

x+0=0+x
b. An identity element with respect to . is 1
x.1=1.x=x

3. a. Commutative with respect to +

x+y=y+x

ub
b. Commutative with respect to .
x. y = y. x

4. a. . is distributive over +
x.(y + z) = x.y + x.z
uh
b. + is distributive over .
x + (y.z) = (x + y).(x + z)

5. For every element x B, there exists an element x' B (complement of x) such that:
a. x + x' = 1
ed

b. x . x' = 0

6. There exists at least two elements x, y B such that x = y.

Two Valued Boolean algebra:

ts

A two valued Boolean algebra is defined on a set of two elements, B = {0, 1}, with rules for the
two binary operators + and .

x y xy
0 0 0
0 1 0
1 0 0
1 1 1

x y x+y
0 0 0
0 1 1
1 0 1
TSEDUHUB EXCLUSIVE Page 28
1 1 1

x x'
0 1
1 0

These rules are exactly the same as the AND, OR, & NOT operations, respectively.
Now show that the Huntington postulates are valid for the set B = {0, 1} and the two binary
operators defined above.

1. Closure
The result of each operation is 1 or 0 and 1, 0 B.

2. From the table an identity element with respect to + is 0,

since 0+0=0
0+1=1+0=1

ub
An identity element with respect to . is 1,
since 1.1 = 1
1.0 = 0.1 = 0

3. Commutative law
uh
0 + 1 = 1 + 0 = 1 ( for + )
0 . 1 = 1 . 0 = 0 ( for . )

4. Distributive law
a. . is distributive over + : x. ( y + z ) = x.y + x.z
ed

b. + is distributive over . : x + ( y. z) = (x + y) . (x + z)

x y z y+z x.(y+z) x.y x.z x.y + x.z

0 0 0 0 0 0 0 0
ts

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

5. From the complement table,

a. x + x' = 1 since 0 + 0' = 0 + 1 = 1

1 + 1' = 1 + 0 = 1

TSEDUHUB EXCLUSIVE Page 29

b. x . x' = 0 since 0 . 0' = 0 . 1 = 0
1 . 1 ' = 1. 0 = 0

6. Two valued boolean algebra has two distinct elements 1 and 0.

1.11 THEOREMS AND PROPERTIES OF BOOLEAN ALGEBRA

Theorem 1:

a. x + x = x

proof:

ub
x+x = (x+x).1 by postulate (2b)
= ( x + x ) (x + x')
= (x + xx')
= x+0
= x
uh
b. x . x = x

proof:
ed

x.x = x. x + 0
= x . x + x . x'
= x (x + x')
= x.1
ts

= x

Theorem 2:

a. x + 1 = 1

proof:

x+1 = 1 . ( x + 1)
= ( x + x' )( x + 1)
= x + x' . 1
= x + x'
= 1
b. x.0 = 0 by duality

TSEDUHUB EXCLUSIVE Page 30

Theorem 3:

(x')' = x

Theorem 4:

a. x + ( y + z ) = (x+y)+z associative
b. x ( yz ) = ( xy ) z associative

Theorem 5: ( De Morgan )

a. ( x + y )' = x' y'

b. ( xy )' = x' + y'

proof:

ub
x y x+y (x+y)' x' y' x'y'
0 0 0 1 1 1 1
0 1 1 0 1 0 0
1 0 1 0 0 1 0
uh
1 1 1 0 0 0 0

Theorem 6: (Absorption)

a. x + xy = x
ed

proof:

x + xy = x.1 + xy by postulate 2 (b)

ts

= x (1 + y) by postulate 4 (a)
= x (y + 1) by postulate 3 (a)
= x. 1 by theorem 2 (a)
= x by postulate 2(b)

b. x ( x + y ) = x

proof:

x y xy x+xy
0 0 0 0
0 1 0 0
1 0 0 1
1 1 1 1

TSEDUHUB EXCLUSIVE Page 31

Operator precedence for evaluating the Boolean expression is:

1. First the expressions inside parentheses must be evaluated.

2. Complement (NOT)
3. AND
4. OR

1.12 BOOLEAN FUNCTIONS

A binary variable can take the value of 0 and 1.
A Boolean function is an expression formed with binary variables, the two binary
operators OR and AND, the unary operator NOT, parentheses, equal sign.
For a given value of the variables, the function can be either 0 or 1.

Example:

ub
F1 = xyz'
F1 = 1 if x = 1 and y = 1 and z' = 1;
Otherwise F1 = 0

A Boolean function may also be represented in a truth table.

uh
to represent a function in a truth table, we need 2n combinations of 1's and 0's of the n binary
variables.

F2 = x + y'z
ed

F2 = 1 if x = 1 or if y = 0, while z = 1

F3 = x'y'z + x'yz + xy'

ts

F4 = xy' + x'z

x y z F1 F2 F3 F4
0 0 0 0 0 0 0
0 0 1 0 1 1 1
0 1 0 0 0 0 0
0 1 1 0 0 1 1
1 0 0 0 1 1 1
1 0 1 0 1 1 1
1 1 0 1 1 0 0
1 1 1 0 1 0 0

The number of rows: 2n (n = number of binary variables)

TSEDUHUB EXCLUSIVE Page 32

 A boolean function may be transformed from an algebraic expression into a logic diagram
composed of AND, OR, NOT gates.

Example:
Simplify the boolean functions to a minimum number of literals.

1. x + x'y = ( x + x' ) ( x + y ) = 1.( x + y ) = x + y

2. x ( x' + y ) = xx' + xy = 0 + xy = xy

3. x'y'z + x'yz + xy' = x'z (y' + y) + xy' = x'z + xy'

4. xy + x'z + yz = xy + x'z + yz ( x + x' )

= xy + x'z + xyz + x'yz
= xy ( 1 + z ) + x'z ( 1 + y )
= xy + x'z

ub
5. ( x + y ) ( x'z ) ( y + z ) = ( x + y ) ( x' + z )

Complement of a Function:
uh
( A + B + C )' = ( A + X )' let B + C = X
= A' X ' De Morgan thm 5a
= A' (B + C)'
= A’. (B’ C’) De Morgan thm. 5a
= A ' B ' C’
ed

Example:

Find the complement of the functions.

F1 = x' yz' + x'y'z and F2 = x ( y'z' + yz )
ts

F1' = ( x' y z' + x' y' z )'

= ( x' y z' )' ( x' y' z )'
= ( x + y' + z ) ( x + y + z' )
F2' = [ x ( y' z' + yz ) ]'
= x' + ( y'z' + yz )'
= x' + ( y'z' )' . ( yz )'
= x' + ( y + z ) ( y' + z' )

Example:

Find the complement of the functions F1 and F2 by taking their duals and complementing each
literal.

F1 = x'yz' + x' y' z

TSEDUHUB EXCLUSIVE Page 33

The dual of F1 is : ( x' + y + z' ) ( x' + y' + z )
Complement each literal : F1' = ( x + y' + z ) ( x + y + z' )

F2 = x ( y' z' + yz )

The dual of F2 is x + ( y' + z' ) ( y + z )

Complement each literal: F2' = x' + ( y + z ) ( y' + z' )

1.13 CANONICAL AND STANDARD FORMS

Minterms and Maxterms:

 A binary variable may appear in its normal form(x) or in its complement form ( x' )
 Two binary variables x and y combined with an AND operation.

Four possible combinations: x'y'

ub
x'y
xy'
xy
 Each of these terms are called MINTERM (Standard Product)
uh
 n variables can be combined to form 2n minterms.

 Each minterm is obtained from an AND term of the n variables, with each variable being
primed if the corresponding bit of the binary number is a 0 and unprimed if a 1.
ed

 n variables forming an OR term, with each variable being primed or unprimed, provide
2n possible combinations, called MAXTERMS ( or Standard sums )

 Each MAXTERM is obtained from an OR term of the n variables, with each variable
ts

being unprimed if the corresponding bit is a 0 and primed if a 1.

MINTERMS MAXTERMS
x y z Term Designation Term Designation
0 0 0 x' y' z' m0 x+y+z M0
0 0 1 x' y' z m1 x + y + z' M1
0 1 0 x' y z' m2 x + y' + z M2
0 1 1 x' y z m3 x + y' + z' M3
1 0 0 x y' z' m4 x' + y + z M4
1 0 1 x y' z m5 x' + y + z' M5
1 1 0 x y z' m6 x' + y' + z M6
1 1 1 xyz m7 x' + y' + z' M7

TSEDUHUB EXCLUSIVE Page 34

 A BOOLEAN function may be expressed algebraically from a given truth table by forming a
MINTERM for each combination of the variables which produces a 1 in the function, than taking
the OR of all those terms.

EXAMPLE:

Functions of three variables

x y z function f1 function f2
0 0 0 0 0
0 0 1 1 0
0 1 0 0 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1

ub
1 1 1 1 1

The function f1 is determined by expressing the combinations 001, 100, 111, as x'y'z, xy'z, xy'z',
xyz.
Since each one of these minterms results in f1 = 1.
uh
f1 = x'y'z + xy'z' + xyz = m1 + m4 + m7
f2 = x'yz + xy'z + xyz' + xyz = m3 + m5 + m6 +m7

NOTE 1: Any boolean function can be expressed as a sum of minterms. (SUM - ORing of
terms)
ed

Complement:

Read from the truth table by forming a MINTERM for each combination that produces a 0 in the
ts

function and then ORing those terms.

f1' = x'y'z' + x'yz' + x'yz + xy'z +xyz'

If we take the complement of f1' we obtain the function f1.

f1 = (x+y+z) (x+y'+z) (x+y'+z) (x'+y+z') (x'+y'+ +z)

= m0 . m2 . m3 . m5 . m6

NOTE 2 : Any boolean function can be expressed as a product of MAXTERMS ( product -

AND ing of terms)

Procedure for obtaining the product of MAXTERMs from the truth table is:

* Form a maxterm for each combination of the variables which produces a 0 in the function.
TSEDUHUB EXCLUSIVE Page 35
* Form the AND of all those maxterms.

Boolean functions expressed as a SUM of MINTERMS or PRODUCT of MAXTERMS are

said to be in CANONICAL FORM.

SUM OF MINTERMS

It is sometimes convenient to express a boolean function in its sum of minterm form.

To do this we should have each term with all variables.
To expand the terms with missing variables we should AND these terms by (x + x') where x is
the missing variable.

Example:
Express F = A + B'C as a sum of minterms.
F = A + B'C

ub
= A ( B + B' ) + ( A + A' )B'C
= AB + AB' + AB'C + A'B'C
Note the terms AB and AB' are still lack the variable C, we will expand them by ( C + C ')
= AB ( C + C' ) + AB' ( C + C ' ) + AB'C + A'B'C
= ABC + ABC' + AB'C + AB'C ' + AB'C + A'B'C
uh
= ABC + ABC' + AB'C + AB'C ' + A'B'C
= m7 + m6 + m5 + m4 +m1
= ∑ ( 1, 4, 5, 6, 7 )

PRODUCT OF MAXTERMS
ed

To express the boolean function as a product of MAXTERMs it must first, be brought into a
form of OR terms. This may be done by using the distributive law:

x + yz = ( x + y ) ( x + z )
ts

Then any missing variable x in each OR term is OR ed with xx'.

EXAMPLE:

Express F = xy + x'z in product of maxterm form.

F = ( xy + x'z )
= ( x' + xy ) ( z + xy )
= ( x' + x ) ( x' + y ) ( z + x ) ( z + y )
= ( 1 ) ( x' + y ) ( x + z ) ( y + z )
= ( x' + y + zz' ) ( x + z + yy' ) ( y + z + xx' )
= (x'+y+z) (x'+y+z') (x+z+y) (x+z+y') (y+z+x) (y+z+x')
= Reduce the terms which appear twice
= (x' + y + z) (x' + y + z') (x + z + y') (x + z + y')

TSEDUHUB EXCLUSIVE Page 36

 = 100 101 000 010

F = π ( 0, 2, 4, 5 )

CONVERSION BETWEEN CANONICAL FORMS

Consider the function F ( A, B, C ) = ∑ ( 1, 4, 5, 6, 7 )

F '( A,B, C ) = π ( 0, 2, 3 )

If we take the complement of F ' by the De Morgan's theorem, we obtain F in a different form:

F ( m0 + m2 + m3 )' = m0' . m2'. m3' = M0.M2.M3 = π ( 0, 2, 3 )

m'j = Mj

To convert from one canonical form to another:

ub
. interchange the symbols and
. list those numbers missing from the original form.

EXAMPLE:
uh
F ( x, y, z ) = π( 0, 2, 4, 5 ) is expressed in the product of MAXTERM form.
It's conversion to sum of MINTERMS is:
F ( x, y, z ) = ∑( 1, 3, 6, 7 )
ed

STANDARD FORMS
Another way to express Boolean function is in standard forms. There are two types of standard
forms:
ts

. The sum of products

. The product of sums

The SUM of PRODUCTs is a boolean expression containing AND terms, called PRODUCT
terms, of one or more literals each.
The SUM denotes the OR ing of these terms.

Example:

A function expressed in sum of products is

F1 = y' + xy + x'yz'

TSEDUHUB EXCLUSIVE Page 37

The expression has three product terms of one, two, and three literals each, respectively.
The PRODUCT of SUMs is a boolean expression containing OR terms, called SUM terms. Each
term may have any number of literals. The PRODUCT denotes the AND ing of these terms.
Example:

A function expressed in product of sums is:

F2 = x ( y' + z ) ( x' + y + z' + w )
This expression has three sum terms of one, two, and four literals each. The product is an AND
operation.

* A Boolean function may be expressed in a nonstandard form.

For example,
F3 = ( AB + CD ) ( A'B' + C 'D' ) is neither in sum of products nor in product of sums.
It can be changed to a standard form by using the distributive law to remove the parentheses:
F3 = A'B'CD + ABC 'D'

ub
1.14 LOGIC GATES
Logic gates are the basic building blocks of any digital system. It is an electronic circuit having
one or more than one input and only one output. The relationship between the input and the
uh
output is based on certain logic. Based on this logic gates are named as AND gate, OR gate,
NOT gate etc.

The graphic symbols and truth tables of the eight gates are shown in Fig. 2.5. Each gate
has one or two binary input variables, designated by x and y, and one binary output variable,
ed

designated by F. The AND, OR, and inverter circuits were defined in Fig. 1.6. The inverter
circuit inverts the logic sense of a binary variable, producing the NOT, or complement, function.
The small circle in the output of the graphic symbol of an inverter (referred to as a bubble)
designates the logic complement. The triangle symbol by itself designates a buffer circuit. A
ts

buffer produces the transfer function, but does not produce a logic operation, since the binary
value of the output is equal to the binary value of the input. This circuit is used for power
amplification of the signal and is equivalent to two inverters connected in cascade.

TSEDUHUB EXCLUSIVE Page 38

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 39

1.15 ERROR DETECTION AND CORRECTION
The dynamic physical interaction of the electrical signals affecting the data path of a memory
unit may cause occasional errors in storing and retrieving the binary information. The reliability
of a memory unit may be improved by employing error‐detecting and error‐correcting codes. The
most common error detection scheme is the parity bit. A parity bit is generated and stored along
with the data word in memory. The parity of the word is checked after reading it from memory.
The data word is accepted if the parity of the bits read out is correct. If the parity checked results
in an inversion, an error is detected, but it cannot be corrected.

An error‐correcting code generates multiple parity check bits that are stored with the data
word in memory. Each check bit is a parity over a group of bits in the data word. When the word
is read back from memory, the associated parity bits are also read from memory and compared
with a new set of check bits generated from the data that have been read. If the check bits are
correct, no error has occurred. If the check bits do not match the stored parity, they generate a
unique pattern, called a syndrome, that can be used to identify the bit that is in error. A single

ub
error occurs when a bit changes in value from 1 to 0 or from 0 to 1 during the write or read
operation. If the specific bit in error is identified, then the error can be corrected by
complementing the erroneous bit.
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 40

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 41

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 42

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 43

 UNIT-II

THE MAP METHOD

The map method provides a simple, straightforward procedure for minimizing Boolean
functions. This method may be regarded as a pictorial form of a truth table. The map method is
also known as the Karnaugh map or K-map.
A K-map is a diagram made up of squares, with each square representing one minterm of
the function that is to be minimized. Since any Boolean function can be expressed as a sum of
minterms, it follows that a Boolean function is recognized graphically in the map from the area
enclosed by those squares whose minterms are included in the function. In fact, the map presents
a visual diagram of all possible ways a function may be expressed in standard form. By
recognizing various patterns, the user can derive alternative algebraic expressions for the same
function, from which the simplest can be selected.

ub
The simplified expressions produced by the map are always in one of the two standard
forms: sum of products or product of sums. It will be assumed that the simplest algebraic
expression is an algebraic expression with a minimum number of terms and with the smallest
possible number of literals in each term. This expression produces a circuit diagram with a
minimum number of gates and the minimum number of inputs to each gate.
uh
Rules of Simplifying Karnaugh Map

Looping adjacent 1’s for simplification

ed

The expression for output Y can be simplified by properly combining those squares in the K-
Map which contain 1s. The process of combining those 1s is called looping.

Pairs – Looping groups of Two 1s

ts

Any adjacent pair of cells marked by a 1 in a K-Map can be combined into one term and one
variable is eliminated which is changing i.e. from A to A’ or B’ to B etc.

Any single logical 1 on the map represents AND function. The total expression corresponding to
the logical 1s of a map are the OR function (sum) of the various variable terms, which covers all
the logical 1 in the map.

F = Σ (2, 3) = AB’ + AB = A (B’ + B) = A

Let’s understand by taking an example of 2-variable K-Map. A 2-variable K-Map will have 22 =
4 cells.

TSEDUHUB EXCLUSIVE Page 44

Boolean expression derived from K-Map = A
Since variable B is changing from B’ to B, it is eliminated right away

Quad – Looping groups of Four 1s

Four cells that are marked as a 1, they can be combined into one term and two variables can be
eliminated. A group of four 1s that are horizontal or vertical or form a square in the K-Map is
called a Quad.

ub
Octet – Lopping groups of Eight 1s
A group of eight 1s that are adjacent to each other is called an octet. When an octet is looped in a
four variable map, 3 of 4 variables are eliminated because only one variable remains unchanged.
uh
There are few tips to remember while simplifying K-Map:
 Biggest decimal number in the given function decides which K-Map is to be used. For
instance, a single variable can define only two decimal values 0 and 1, with maximum
ed

value as 1. Two variables can define 22 =4 values, 0, 1, 2 and 3, with maximum value as 3.
So if a given function has 4 as the biggest decimal number, it can not be defined by two
variables. We need to use 3 variables because by using 3 variables, we can have 23 = 8
decimal values with 7 as the maximum value.
ts

 We should try to cover all 1′s even if they become part of more than 1 loop.
 We look for the biggest loop at first. So if a K-Map has an Octet, it should be circled first,
followed by quads if any, followed by pairs if any.
 Pair eliminates 1 variable, Quad eliminates 2 variables and an Octet eliminates
3 variables.
 While looping, we can visualize folding the K-Map like a paper and can loop 1′s present
in left most and right most columns of the same row.
 We can also visualize overlapping K-Map in case of 5 and 6 variable K-Maps.
 We can fold and overlap the K-Map only in horizontal and vertical direction but not in
diagonal.

TSEDUHUB EXCLUSIVE Page 45

3-Variable K-Map

A 3-variable K-Map will have 23 = 8 cells. As told in last post, number of variables are decided
by the biggest decimal number in a given function. A function F which has maximum decimal
value of 7 can be defined and simplified by a 3-variable Karnaugh Map.

Boolean Table for 3 Variables

3-Variable K-Map
ub
uh
ed

Carefully note how cells are numbered in above diagram. A first cell is denoted by 0, second by
ts

1 and then third by 3 and not by 2. This is because, A’BC (ANDing of first row A’ and third
column BC) corresponds to decimal number 3 in the boolean table. Similarly, second row, third
column ABC is denoted by 7 and not by 6.
Now, let’s understand how to simplify 3-variables K-Map by taking couple of examples.

Example of 3-Variable K-Map

Given function, F = Σ (1, 2, 3, 4, 5, 6)
Since the biggest number in this function is 6, it can be defined by 3 variables.

Let’s draw K-Map for this function by writing 1 in cells that are present in function and 0 in rest
of the cells. You don’t necessarily need to write 0s but it is okay to have them.

TSEDUHUB EXCLUSIVE Page 46

We need to apply rules for simplifying K-Map that we read in last tutorial. So, first we need to
look for an octet i.e. 8 adjacent 1′s. There is none, so we should now look for a quad i.e. 4
adjacent 1′s. Again, there is none, so we will look for pairs. There are 3 pairs circled in red.
(1,3) – A’C (Since B is the changing variable between these two cells, it is eliminated)

(2,6) – BC’ (Since A is the changing variable, it is eliminated)

ub
(4, 5) – AB’ (Since C is the changing variable, it is eliminated)

Thus, F = A’C + BC’ + AB’

uh
4-variable K-Map

A 4-variable K-Map will have 24 = 16 cells. A function F which has maximum decimal value of
15 can be defined and simplified by a 4-variable Karnaugh Map.
ed

4-variable K-Map
ts

Example 1 of 4-Variable K-Map

Given function, F = Σ (0, 4, 6, 8, 10, 15)
Since, the biggest number is 15, we need to have 4 variables to define this function.

TSEDUHUB EXCLUSIVE Page 47

Let’s draw K-Map for this function by writing 1 in cells that are present in function and 0 in rest
of the cells.

Applying rules of simplifying K-Map, there are no Octets and Quads. There are 3 pairs, circled

ub
in red.
(0, 4) – A’C'D’ (Since B is the changing variable between these two cells, it is eliminated)

(4, 6) – A’BD’ (Since C is the changing variable, it is eliminated)

uh
(8, 10) – AB’D’ (Since C is the changing variable, it is eliminated)

There is 1 in cell 15, which can not be looped with any adjacent cell, hence it can not be
ed

simplified further and left as it is.

15 = ABCD
ts

Thus, F = A’C'D’ + A’BD’ + AB’D’ + ABCD

Example 2 of 4-Variable K-Map

Given function, F = Σ (0, 1, 3, 5, 6, 9, 11, 12, 13, 15)
Since, the biggest number is 15, we need to have 4 variables to define this function.

Let’s draw K-Map for this function by writing 1 in cells that are present in function and 0 in rest
of the cells.

TSEDUHUB EXCLUSIVE Page 48

Applying rules of K-Map, there is no octet. There are 2 quads and there are 3 pairs.
(1, 5, 13, 9) – C’D (Since A and B are changing variables, they are eliminated)

ub
(9, 11, 13, 15) – AD (Since B and C are changing variables, they are eliminated)

(0, 1) – A’B'C’ (Since D is the changing variable, it is eliminated)

uh
(1, 3) – A’B'D (Since C is the changing variable, it is eliminated)

(12, 13) – ABC’ (Since D is the changing variable, it is eliminated)

ed

There is 1 in cell 6, which can not be looped with any adjacent cell, hence it can not be
simplified further and left as it is.

6 = A’BCD’
ts

Thus, F = C’D + AD + A’B'C’ + A’B'D + ABC’ + A’BCD’

Example 3 of 4-Variable K-Map

Given function, F = Σ (0, 2, 3, 4, 5, 7, 8, 9, 13, 15)
Since, the biggest number is 15, we need to have 4 variables to define this function.

Let’s draw K-Map for this function by writing 1 in cells that are present in function and 0 in rest
of the cells.

TSEDUHUB EXCLUSIVE Page 49

Applying rules of simplifying K-Map, there is no octet. There are 1 quad and 3 pairs.
(5, 7, 13, 15) – BD (Since A and C are changing variables, they are eliminated)

(0, 4) – A’C'D’ (Since B is the changing variable, it is eliminated)

ub
(2, 3) – A’B'C (Since D is the changing variable, it is eliminated)

(8, 9) – AB’C’ (Since D is the changing variable, it is eliminated)

uh
Thus, F = BD + A’C'D’ + A’B'C + AB’C’

Example 4 of 4-Variable K-Map

ed

Given function, F = Σ (0, 3, 4, 6, 7, 9, 12, 14, 15)

Since, the biggest number is 15, we need to have 4 variables to define this function.

Let’s draw K-Map for this function by writing 1 in cells that are present in function and 0 in rest
ts

of the cells.

TSEDUHUB EXCLUSIVE Page 50

Applying rules of simplifying K-Map, there is no octet. There are two quads and two pairs.
(4, 6, 12, 14) – BD’ (Since A and C are changing variables, they are eliminated)

(6, 7, 14, 15) – BC (Since A and D are changing variables, they are eliminated)

(0, 4) – A’C'D’ (Since B is the changing variable, it is eliminated)

(3, 7) – A’CD (Since B is the changing variable, it is eliminated)

There is 1 in cell 9, which can not be looped with any adjacent cell, hence it can not be
simplified further and left as it is.

9 – AB’C'D

Thus, F = BD’ + BC + A’C'D’ + A’CD + AB’C'D

5-Variable K-Map
ub
uh
A 5-variable K-Map will have 25 = 32 cells. A function F which has maximum decimal value of
31, can be defined and simplified by a 5-variable Karnaugh Map.
ed

5-Variable K-Map
In above boolean table, from 0 to 15, A is 0 and from 16 to 31, A is 1. A 5-variable K-Map is
drawn as below.
ts

Now, we have two squares and we can loop octets, quads and pairs between these two squares.
What we need to do is to visualize second square on first square and figure out adjacent cells.

TSEDUHUB EXCLUSIVE Page 51

Example 1 of 5-Variable K-Map
Given function, F = Σ (1, 3, 4, 5, 11, 12, 14, 16, 20, 21, 30)
Since, the biggest number is 30, we need to have 5 variables to define this function.

Let’s draw K-Map for this function by writing 1 in cells that are present in function and 0 in rest
of the cells.

ub
Applying rules of simplifying K-Map, there is no octet. There is one quad that is obtained by
uh
visualizing second square on first, there are 4 adjacent cells – 4,5,20 and 21. The octet is
highlighted by a blue connecting line. There are 5 pairs. Similar to quad, there is one pair
between two squares which is highlighted by the blue connecting line.
ed

(4, 5, 20, 21) – B’CD’ (Since A & E are the changing variables, it is eliminated)

(12, 14) – A’BCE’ (Since D is the changing variable, it is eliminated)

ts

(14, 30) – BCDE’ (Since A is the changing variable, it is eliminated)

(3, 11) – A’C'DE (Since B is the changing variable, it is eliminated)

(16, 20) – AB’D'E’ (Since C is the changing variable, it is eliminated)

(1, 3) – A’B'C’E (Since D is the changing variable, it is eliminated)

Thus, F = B’CD’ + A’BCE’ + BCDE’ + A’C'DE + AB’D'E’ + A’B'C’E

TSEDUHUB EXCLUSIVE Page 52

Example 2 of 5-Variable K-Map

Given function, F = Σ (0, 2, 3, 5, 7, 8, 11, 13, 17, 19, 23, 24, 29, 30)
Since, the biggest number is 30, we need to have 5 variables to define this function.

Let’s draw K-Map for this function by writing 1 in cells that are present in function and 0 in rest
of the cells.

ub
uh
Applying rules of simplifying K-Map, there is no octet. First we need to look for quads within
each of the squares. There are none but there is a quad between two squares that is obtained by
visualizing second square on first, there are 4 adjacent cells – 3, 7, 19 and 23. This quad is
ed

highlighted by blue connecting line. There are 6 pairs, out of which two are between two
squares, highlighted by blue connecting line.
(3, 7, 19, 23) - B’DE (Since A & C are the changing variables, they are eliminated)
ts

(3, 11) – A’C'DE (Since B is the changing variables, it is eliminated)

(1, 2) – A’B'C’E’ (Since D is the changing variables, it is eliminated)

(5, 7) – A’B'CE (Since D is the changing variables, it is eliminated)

(17, 19) – AB’C'E (Since D is the changing variables, it is eliminated)

(13, 29) – BCD’E (Since A is the changing variables, it is eliminated)

(8, 24) – BC’D'E’ (Since A is the changing variables, it is eliminated)

TSEDUHUB EXCLUSIVE Page 53

There is 1 in cell 30, which can not be looped with any adjacent cell, hence it can not be
simplified further and left as it is.

30 – ABCDE’

Thus, F = B’DE + A’C'DE + A’B'C’E’ + A’B'CE + AB’C'E + BCD’E + BC’D'E’ +

ABCDE’
Example 3 of 5-Variable K-Map
Given function, F = Σ (0, 1, 2, 3, 8, 9, 16, 17, 20, 21, 24, 25, 28, 29, 30, 31)
Since, the biggest number is 31, we need to have 5 variables to define this function.

Let’s draw K-Map for this function by writing 1 in cells that are present in function and 0 in rest
of the cells.

ub
uh
ed

Applying rules of simplifying K-Map, there are 2 octets. First one is in square 2 circled in red.
Another octet is between 2 squares highlighted by blue connecting lines. There are 2 quads
ts

between each of the squares.

(16, 17, 20, 21, 28, 29, 24, 25) – AD’ (Since B, C and E are changing variables, they are
eliminated)

(0, 1, 8, 9, 16, 17, 24, 25) – C’D’ (Since A, B and E are changing variables, they are eliminated)

(0, 1, 2, 3) – A’B'C’ (Since D and E are changing variables, they are eliminated)

(28, 29, 30, 31) – ABC (Since D and E are changing variables, they are eliminated)

Thus, F = AD’ + C’D’ + A’B'C’ + ABC

TSEDUHUB EXCLUSIVE Page 54

PRODUCT-OF-SUMS SIMPLIFICATION

ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 55

The gate-level implementation of the simplified expressions obtained in the above problem is
shown in the below figure. The sum-of-products expression is implemented in (a) with a group
of AND gates, one for each AND term. The outputs of the AND gates are connected to the inputs
of a single OR gate. The same function is implemented in (b) in its product-of-sums form with a
group of OR gates, one for each OR term. The outputs of the OR gates are connected to the
inputs of a single AND gate. In each case, it is assumed that the input variables are directly
available in their complement, so inverters are not needed. AND gates are connected to a single
OR gate when in sum-of-products form; OR gates are connected to a single AND gate when in
product-of-sums form. Either configuration forms two levels of gates. Thus, the implementation
of a function in a standard form is said to be a two-level implementation.

ub
DON'T-CARE CONDITIONS

In some applications the function is not specified for certain combinations of the variables. As an
example, the four-bit binary code for the decimal digits has six combinations that are not used
uh
and consequently are considered to be unspecified. Functions that have unspecified outputs for
some input combinations are called incompletely specified functions. In most applications, we
simply don’t care what value is assumed by the function for the unspecified minterms. For this
reason, it is customary to call the unspecified minterms of a function don’t-care conditions.
These don’t-care conditions can be used on a map to provide further simplification of the
ed

Boolean expression.
A don’t-care minterm is a combination of variables whose logical value is not specified.
Such a minterm cannot be marked with a 1 in the map, because it would require that the function
always be a 1 for such a combination. Likewise, putting a 0 on the square requires the function to
ts

be 0. To distinguish the don’t-care condition from 1’s and 0’s, an X is used. Thus, an X inside a
square in the map indicates that we don’t care whether the value of 0 or 1 is assigned to F for the
particular minterm.
In choosing adjacent squares to simplify the function in a map, the don’t-care minterms
may be assumed to be either 0 or 1. When simplifying the function, we can choose to include
each don’t-care minterm with either the 1’s or the 0’s, depending on which combination gives
the simplest expression.

TSEDUHUB EXCLUSIVE Page 56

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 57

NAND AND NOR IMPLEMENTATION
Digital circuits are frequently constructed with NAND or NOR gates rather than with AND and
OR gates. NAND and NOR gates are easier to fabricate with electronic components and are the
basic gates used in all IC digital logic families. Because of the prominence of NAND and NOR
gates in the design of digital circuits, rules and procedures have been developed for the
conversion from Boolean functions given in terms of AND, OR, and NOT into equivalent
NAND and NOR logic diagrams.

NAND Circuits

The NAND gate is said to be a universal gate because any logic circuit can be implemented with
it. To show that any Boolean function can be implemented with NAND gates, we need only
show that the logical operations of AND, OR, and complement can be obtained with NAND
gates alone. The complement operation is obtained from a one-input NAND gate that behaves
exactly like an inverter. The AND operation requires two NAND gates. The first produces the

ub
NAND operation and the second inverts the logical sense of the signal. The OR operation is
achieved through a NAND gate with additional inverters in each input.
uh
ed

Logic operations with NAND gates

A convenient way to implement a Boolean function with NAND gates is to obtain the
simplified Boolean function in terms of Boolean operators and then convert the function to
NAND logic. The conversion of an algebraic expression from AND, OR, and complement to
ts

NAND can be done by simple circuit manipulation techniques that change AND–OR diagrams
to NAND diagrams.
To facilitate the conversion to NAND logic, it is convenient to define an alternative
graphic symbol for the gate. Two equivalent graphic symbols for the NAND gate are shown
below.

Two graphic symbols for a three-input NAND gate

TSEDUHUB EXCLUSIVE Page 58

Two-Level Implementation

The implementation of Boolean functions with NAND gates requires that the functions be
in sum-of-products form. To see the relationship between a sum-of-products expression and its
equivalent NAND implementation, consider the logic diagrams drawn in the below figure. All
three diagrams are equivalent and implement the function
F = AB + CD
The function is implemented in Fig (a) with AND and OR gates. In Fig (b), the AND
gates are replaced by NAND gates and the OR gate is replaced by a NAND gate with an OR-
invert graphic symbol. Remember that a bubble denotes complementation and two bubbles along
the same line represent double complementation, so both can be removed. Removing the bubbles
on the gates of (b) produces the circuit of (a). Therefore, the two diagrams implement the same
function and are equivalent.
In Fig(c), the output NAND gate is redrawn with the AND-invert graphic symbol. In
drawing NAND logic diagrams, the circuit shown in either Fig (b) or (c) is acceptable. The one
in Fig (b) is in mixed notation and represents a more direct relationship to the Boolean

ub
expression it implements. The NAND implementation in Fig(c) can be verified algebraically.
The function it implements can easily be converted to sum- of-products form by DeMorgan’s
theorem:
uh
ed
ts

Fig. Three ways to implement F = AB + CD

Example:
EEE

AM

TSEDUHUB EXCLUSIVE Page 59

PLE

ub
uh
ed
ts

3.
Multilevel NAND Circuits

The standard form of expressing Boolean functions results in a two-level implementation. There
are occasions, however, when the design of digital systems results in gating structures with three
or more levels. The most common procedure in the design of multilevel circuits is to express the
Boolean function in terms of AND, OR, and complement operations. The function can then be
implemented with AND and OR gates. After that, if necessary, it can be converted into an all-
NAND circuit. Consider, for example, the Boolean function
F = A (CD + B) + BC ‘

TSEDUHUB EXCLUSIVE Page 60

Although it is possible to remove the parentheses and reduce the expression into a standard sum-
of-products form, we choose to implement it as a multilevel circuit for illustration. The AND–
OR implementation is shown in Fig. 3.20 (a). There are four levels of gating in the circuit. The
first level has two AND gates. The second level has an OR gate followed by an AND gate in the
third level and an OR gate in the fourth level. A logic diagram with a pattern of alternating levels
of AND and OR gates can easily be converted into a NAND circuit with the use of mixed
notation, shown in Fig. 3.20 (b). The procedure is to change every AND gate to an AND-invert
graphic symbol and every OR gate to an invert-OR graphic symbol. The NAND circuit performs
the same logic as the AND–OR diagram as long as there are two bubbles along the same line.
The bubble associated with input B causes an extra complementation, which must be
compensated for by changing the input literal to B’.

ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 61

 ub
uh
ed
ts

NOR Implementation
The NOR operation is the dual of the NAND operation. Therefore, all procedures and rules for
NOR logic are the duals of the corresponding procedures and rules developed for NAND logic.
The NOR gate is another universal gate that can be used to implement any Boolean function. The
implementation of the complement, OR, and AND operations with NOR gates is shown in Fig.
3.22. The complement operation is obtained from a one input NOR gate that behaves exactly like
an inverter. The OR operation requires two NOR gates, and the AND operation is obtained with
a NOR gate that has inverters in each input.

TSEDUHUB EXCLUSIVE Page 62

The two graphic symbols for the mixed notation are shown in Fig. 3.23. The OR-invert symbol
defines the NOR operation as an OR followed by a complement. The invert-AND symbol
complements each input and then performs an AND operation. The two symbols designate the
same NOR operation and are logically identical because of DeMorgan’s theorem.

ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 63

 ub
uh
ed
ts

OTHER TWO-LEVEL IMPLEMENTATIONS

Some (but not all) NAND or NOR gates allow the possibility of a wire connection between the
outputs of two gates to provide a specific logic function. This type of logic is called wired logic.
For example, open-collector TTL NAND gates, when tied together, perform wired-AND logic.
The wired-AND logic performed with two NAND gates is depicted in Fig. 3.26 (a). The AND
gate is drawn with the lines going through the center of the gate to distinguish it from a

TSEDUHUB EXCLUSIVE Page 64

conventional gate. The wired-AND gate is not a physical gate, but only a symbol to designate the
function obtained from the indicated wired connection. The logic function implemented by the
circuit of Fig. 3.26 (a) is

ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 65

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 66

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 67

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 68

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 69

 UNIT-III
Combinational Circuits
Combinational circuit is circuit in which we combine the different gates in the circuit for
example encoder, decoder, multiplexer and demultiplexer. Some of the characteristics of
combinational circuits are following.

 The output of combinational circuit at any instant of time depends only on the levels
present at input terminals.
 The combinational circuit does not use any memory. The previous state of input does not
have any effect on the present state of the circuit.
 A combinational circuit can have a n number of inputs and m number of outputs.

Block diagram

ub
uh
ed

DESIGN PROCEDURE
ts

The design of combinational circuits starts from the specification of the design objective and
culminates in a logic circuit diagram or a set of Boolean functions from which the logic diagram
can be obtained. The procedure involves the following steps:

1. From the specifications of the circuit, determine the required number of inputs and outputs and
assign a symbol to each.
2. Derive the truth table that defines the required relationship between inputs and outputs.
3. Obtain the simplified Boolean functions for each output as a function of the input variables.
4. Draw the logic diagram and verify the correctness of the design (manually or by simulation).

A truth table for a combinational circuit consists of input columns and output columns. The input
columns are obtained from the 2n binary numbers for the n input variables. The binary values for
the outputs are determined from the stated specifications. The output functions specified in the
truth table give the exact definition of the combinational circuit. It is important that the verbal
TSEDUHUB EXCLUSIVE Page 70
specifications be interpreted correctly in the truth table, as they are often incomplete, and any
wrong interpretation may result in an incorrect truth table.

The output binary functions listed in the truth table are simplified by any available method, such
as algebraic manipulation, the map method, or a computer-based simplification program.

We're going to elaborate few important combinational circuits as follows.

Half Adder
A combinational circuit that performs the addition of two bits is called a half adder. We find that
this circuit needs two binary inputs and two binary outputs. The input variables designate the
augend and addend bits; the output variables produce the sum and carry. We assign symbols x
and y to the two inputs and S (for sum) and C (for carry) to the outputs.

The simplified Boolean functions for the two outputs can be obtained directly from the truth

ub
table. The simplified sum-of-products expressions are

The logic diagram of the half adder implemented in sum of products is shown in Fig. (a) . It can
be also implemented with an exclusive-OR and an AND gate as shown in Fig. (b). This form is
uh
used to show that two half adders can be used to construct a full adder.
ed
ts

TSEDUHUB EXCLUSIVE Page 71

Full Adder
Addition of n-bit binary numbers requires the use of a full adder, and the process of addition
proceeds on a bit-by-bit basis, right to left, beginning with the least significant bit. After the least
significant bit, addition at each position adds not only the respective bits of the words, but must
also consider a possible carry bit from addition at the previous position.

A full adder is a combinational circuit that forms the arithmetic sum of three bits. It consists of
three inputs and two outputs. Two of the input variables, denoted by x and y, represent the two
significant bits to be added. The third input, z, represents the carry from the previous lower
significant position. The two outputs are designated by the symbols S for sum and C for carry.
The binary variable S gives the value of the least significant bit of the sum. The binary variable C
gives the output carry formed by adding the input carry and the bits of the words.

ub
uh
The simplified expressions are
ed
ts

The logic diagram for the full adder implemented in sum-of-products form is shown in the below Fig.

TSEDUHUB EXCLUSIVE Page 72

It can also be implemented with two half adders and one OR gate, as shown in the below Fig.

ub
The S output from the second half adder is the exclusive-OR of z and the output of the first half
adder, giving uh
The carry output is
ed
ts

TSEDUHUB EXCLUSIVE Page 73

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).
Such a circuit is called a half-subtractor because it enables a borrow out of the current arithmetic
operation but no borrow in from a previous arithmetic operation. The truth table for the half
subtractor is given below.

ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 74

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 75

Binary Adder

ub
uh
ed
ts

Binary Subtractor

TSEDUHUB EXCLUSIVE Page 76

Binary Adder-Subtractor

ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 77

BINARY MULTIPLIER

The multiplicand is multiplied by each bit of the multiplier, starting from the least significant bit.
Each such multiplication forms a partial product. Successive partial products are shifted one
position to the left. The final product is obtained from the sum of the partial products.

To see how a binary multiplier can be implemented with a combinational circuit, consider
the multiplication of two 2-bit numbers as shown in Fig. 4.15. The multiplicand bits are B1 and
B0, the multiplier bits are A1 and A0, and the product is C3C2C1C0. The first partial product is
formed by multiplying B1B0 by A0. The multiplication of two bits such as A0 and B0 produces a
1 if both bits are 1; otherwise, it produces a 0. This is identical to an AND operation. Therefore,
the partial product can be implemented with AND gates as shown in the diagram. The second
partial product is formed by multiplying B1B0 by A1 and shifting one position to the left. The
two partial products are added with two half-adder (HA) circuits. Usually, there are more bits in
the partial products and it is necessary to use full adders to produce the sum of the partial
products. Note that the least significant bit of the product does not have to go through an adder,

ub
since it is formed by the output of the first AND gate.
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 78

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 79

Decoder
n
A decoder is a logic circuit that converts an n bit binary input code into M (=2 ) output lines
such that each output line will be activated for only one of the possible combinations of inputs.
(OR)
A decoder is a Combinational circuit that converts binary information from ‘n’ input lines to a
n
maximum of 2 unique output lines.

E.g. 2x4 line Decoder (it is also called two four line decoder)

Decoders are available in two different types of output forms:

(1) Active high output type decoders and (2) Active low output type of decoders.

Active high output type of decoders are constructed with AND gates and active low output type
of decoders are constructed with NAND gates.

ub
Truth table of active high output type of decoder is given below:
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 80

 ub
 3 to 8 line decoder is also called Binary-to-Octal decoder or converter. It is also called
1of 8 decoder, because only one of the 8 outputs is active at a time.
uh
 Decoders are widely used in the memory system of computer, where they respond to the
address code input from the CPU to activate the memory storage location specified by
the address code.
 Decoders are also used to convert binary data to a form suitable for displaying on decimal
read outs.
ed

 Decoders can be used to implement combinational circuits, Boolean functions etc.

Example: Implement full adder with a decoder.

ts

TSEDUHUB EXCLUSIVE Page 81

Example: Implement 3x8 decoder using 2x4 decoder.
Solution:

Applications of decoders

ub
1. Decoders are used in counter systems
2. They are used in analog-to-digital converters.
3. Decoder outputs can be used to drive a display system.

Encoder
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 82

Priority Encoder
A priority encoder is an encoder circuit that includes the priority function. The operation of the
priority encoder is such that if two or more inputs are equal to 1 at the same time, the input
having the highest priority will take precedence. The truth table of a four-input priority encoder
is given in Table 4.8. In addition to the two outputs x and y, the circuit has a third output
designated by V; this is a valid bit indicator that is set to 1 when one or more inputs are equal to
1. If all inputs are 0, there is no valid input and V is equal to 0. The other two outputs are not
inspected when V equals 0 and are specified as don’t-care conditions. Note that whereas X’s in
output columns represent don’t-care conditions, the X’s in the input columns are useful for
representing a truth table in condensed form. Instead of listing all 16 minterms of four variables,
the truth table uses an X to represent either 1 or 0. For example, X 100 represents the two
minterms 0100 and 1100.

According to Table 4.8, the higher the subscript number, the higher the priority of the
input. Input D3 has the highest priority, so, regardless of the values of the other inputs, when this

ub
input is 1, the output for xy is 11 (binary 3). D2 has the next priority level. The output is 10 if D2
= 1, provided that D3 = 0, regardless of the values of the other two lower priority inputs. The
output for D1 is generated only if higher priority inputs are 0, and so on down the priority levels.
uh
ed
ts

The maps for simplifying outputs x and y are shown in Fig. 4.22. The minterms for the
two functions are derived from Table 4.8. Although the table has only five rows, when each X in
a row is replaced first by 0 and then by 1, we obtain all 16 possible input combinations. For
example, the fourth row in the table, with inputs XX10, represents the four minterms 0010, 0110,

TSEDUHUB EXCLUSIVE Page 83

1010, and 1110. The simplified Boolean expressions for the priority encoder are obtained from
the maps. The condition for output V is an OR function of all the input variables. The priority
encoder is implemented in Fig. 4.23 according to the following Boolean functions:

ub
uh
MULTIPLEXERS
ed

A multiplexer is a combinational circuit that selects binary information from one of many
input lines and directs it to a single output line. The selection of a particular input line is
controlled by a set of selection lines. Normally, there are 2n input lines and n selection lines
whose bit combinations determine which input is selected.
ts

A two-to-one-line multiplexer connects one of two 1-bit sources to a common

destination, as shown in Fig. 4.24. The circuit has two data input lines, one output line, and one
selection line S. When S = 0, the upper AND gate is enabled and I0 has a path to the output.
When S = 1, the lower AND gate is enabled and I1 has a path to the output. The multiplexer acts
like an electronic switch that selects one of two sources. The block diagram of a multiplexer is
sometimes depicted by a wedge-shaped symbol, as shown in Fig. 4.24(b). It suggests visually
how a selected one of multiple data sources is directed into a single destination. The multiplexer
is often labeled “MUX” in block diagrams.

TSEDUHUB EXCLUSIVE Page 84

 A four-to-one-line multiplexer is shown in Fig. 4.25. Each of the four inputs, I0 through
I3, is applied to one input of an AND gate. Selection lines S1 and S0 are decoded to select a

ub
particular AND gate. The outputs of the AND gates are applied to a single OR gate that provides
the one-line output. The function table lists the input that is passed to the output for each
combination of the binary selection values. To demonstrate the operation of the circuit, consider
the case when S1S0 = 10. The AND gate associated with input I2 has two of its inputs equal to 1
and the third input connected to I2. The other three AND gates have at least one input equal to 0,
uh
which makes their outputs equal to 0. The output of the OR gate is now equal to the value of I2,
providing a path from the selected input to the output. A multiplexer is also called a data
selector, since it selects one of many inputs and steers the binary information to the output line.
ed
ts

TSEDUHUB EXCLUSIVE Page 85

 The AND gates and inverters in the multiplexer resemble a decoder circuit, and indeed,
they decode the selection input lines. In general, a 2n -to-1-line multiplexer is constructed from
an n -to-2n decoder by adding 2n input lines to it, one to each AND gate. The outputs of the AND
gates are applied to a single OR gate. The size of a multiplexer is specified by the number 2n of
its data input lines and the single output line. The n selection lines are implied from the 2n data
lines. As in decoders, multiplexers may have an enable input to control the operation of the unit.
When the enable input is in the inactive state, the outputs are disabled, and when it is in the
active state, the circuit functions as a normal multiplexer.

Implementation of Boolean function with Multiplexers

ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 86

Example:

ub
uh
ed

(OR)
ts

TSEDUHUB EXCLUSIVE Page 87

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 88

 ub
uh
Applications of Multiplexer:

Multiplexer are used in various fields where multiple data need to be transmitted using a single
line. Following are some of the applications of multiplexers -
ed

1. Communication system – Communication system is a set of system that enables

communication like transmission system, relay and tributary station, and communication
network. The efficiency of communication system can be increased considerably using
ts

multiplexer. Multiplexer allow the process of transmitting different type of data such as
audio, video at the same time using a single transmission line.
2. Telephone network – In telephone network, multiple audio signals are integrated on a
single line for transmission with the help of multiplexers. In this way, multiple audio
signals can be isolated and eventually, the desire audio signals reach the intended
recipients.
3. Computer memory - Multiplexers are used to implement huge amount of memory into
the computer, at the same time reduces the number of copper lines required to connect the
memory to other parts of the computer circuit.
4. Transmission from the computer system of a satellite – Multiplexer can be used for
the transmission of data signals from the computer system of a satellite or spacecraft to the
ground system using the GPS (Global Positioning System) satellites.
TSEDUHUB EXCLUSIVE Page 89
Demultiplexer
Demultiplexer means one to many. A demultiplexer is a circuit with one input and many outputs.
By applying control signal, we can steer any input to the output. Few types of demultiplexer are
1-to 2, 1-to-4, 1-to-8 and 1-to-16 demultiplexer.

Following figure illustrate the general idea of a demultiplexer with 1 input signal, m control
signals, and n output signals.

ub
uh
Demultiplexer Pin Diagram

Understanding 1- to-4 Demultiplexer

ed

The 1-to-4 demultiplexer has 1 input bit, 2 control bit, and 4 output bits. The 1-to-4
demultiplexer is shown in figure below-
ts

TSEDUHUB EXCLUSIVE Page 90

The input bit is labelled as Data D. This data bit is transmitted to the data bit of the output lines.
This depends on the value of AB, the control input.

When AB = 01, the upper second AND gate is enabled while other AND gates are disabled.
Therefore, only data bit D is transmitted to the output, giving Y1 = Data.

If D is low, Y1 is low. IF D is high, Y1 is high. The value of Y1 depends upon the value of D.
All other outputs are in low state.

If the control input is changed to AB = 10, all the gates are disabled except the third AND gate
from the top. Then, D is transmitted only to the Y2 output, and Y2 = Data.

Example of 1-to-16 demultiplexer has 1 input bit, 4 control bits and 16 output bit.

ub
Applications of Demultiplexer:

1. Demultiplexer is used to connect a single source to multiple destinations. The main

application area of demultiplexer is communication system where multiplexer are used.
uh
Most of the communication system are bidirectional i.e. they function in both ways
(transmitting and receiving signals). Hence, for most of the applications, the multiplexer
and demultiplexer work in sync. Demultiplexer are also used for reconstruction of parallel
data and ALU circuits.
ed

2. Communication System - Communication system use multiplexer to carry multiple data

like audio, video and other form of data using a single line for transmission. This process
makes the transmission easier. The demultiplexer receives the output signals of the
multiplexer and converts them back to the original form of the data at the receiving end.
ts

The multiplexer and demultiplexer work together to carry out the process of transmission
and reception of data in communication system.
3. ALU (Arithmetic Logic Unit) – In an ALU circuit, the output of ALU can be stored in
multiple registers or storage units with the help of demultiplexer. The output of ALU is fed
as the data input to the demultiplexer. Each output of demultiplexer is connected to
multiple register which can be stored in the registers.
4. Serial to parallel converter - A serial to parallel converter is used for reconstructing
parallel data from incoming serial data stream. In this technique, serial data from the
incoming serial data stream is given as data input to the demultiplexer at the regular
intervals. A counter is attach to the control input of the demultiplexer. This counter directs
the data signal to the output of the demultiplexer where these data signals are stored. When

TSEDUHUB EXCLUSIVE Page 91

 all data signals have been stored, the output of the demultiplexer can be retrieved and read
out in parallel.

MAGNITUDE COMPARATOR

The comparison of two numbers is an operation that determines whether one number is greater
than, less than, or equal to the other number. A magnitude comparator is a combinational circuit
that compares two numbers A and B and determines their relative magnitudes. The outcome of
the comparison is specified by three binary variables that indicate whether A<B, A = B, or A>B.

Example: 2-bit comparator

Similarly we can have 2 bit comparator and the table to list all the combinations at input and
their corresponding outputs is as:

ub
A B

A1A0 B1B0 f (A>B) f (A=B) f (A<B)

00 00 0 1 0
uh
01 00 1 0 0

10 00 1 0 0
ed

11 00 1 0 0

00 01 0 0 1
ts

01 01 0 1 0

10 01 1 0 0

11 01 1 0 0

00 10 0 0 1

01 10 0 0 1

10 10 0 1 0

11 10 1 0 0

TSEDUHUB EXCLUSIVE Page 92

00 11 0 0 1

01 11 0 0 1

10 11 0 0 1

11 11 0 1 0

And we get the equations for all three outputs from the K-maps as

ub
We can also obtain these equations orally as for A1A0 to be greater than B1B0 either A1 is greater
uh
than B1 (i.e. A1=1 & B1=0) or A1 is equal to B1 (or A1is not less than B1 i.e. (f(A1<B1))’ =
(A1’B1)’= (A1 + B1‘) & A0 is greater than B0 (i.e. A0=1 & B0=0).

Hence the equation we get is f (A>B) = A1B1‘+ (A1 + B1’) A0B0’ = A1B1‘+ A0 B1’B0’+ A1A0B0’
ed
ts

TSEDUHUB EXCLUSIVE Page 93

Example: 4-bit comparator

ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 94

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 95

 UNIT-IV

S.No Combinational logic circuit Sequential logic circuit

1 Block diagram:
Inputs Outputs

Inputs Outputs
Combin
Combination ational
al circuit circuit
Memor
y
element

ub
uh
2 It consists of input signal, gates and It consists of a combinational circuit to
output signals which memory elements are connected
to form a feedback path.
ed

3 The outputs at any instant of time are The outputs dependent not only on the
entirely dependent upon the inputs present present input variable but they also
at that time. depend upon the past value of the input
variable.
ts

4 Combinational circuits are faster in speed Sequential circuits are slower than the
combinational circuits.

5 Combinational circuits are easy to design Sequential circuits are comparatively

harder to design

6 Example: Parallel adder, Code converter, Example: Serial Adder, Counter, shift
Decoder register

TSEDUHUB EXCLUSIVE Page 96

Sequential circuits
Combinational circuits
 The outputs are entirely dependent on the current inputs
 Contains no storage elements, no feedback
Sequential circuits
 Consists of a combinational circuit to which storage elements are connected to form a
feedback path
 Outputs are a function of both the current inputs and the present state of the storage
elements
Storage/memory elements
 capable of storing binary information
 defining the state of the sequential circuit
 Next state is a function of external inputs and current state

ub
(inputs, current state) ⇒ (outputs, next state)
uh
ed

Fig. Block Diagram of Sequential Circuit

ts

Types of Sequential Circuits

Two major types: depending on timing of their signals

Asynchronous sequential circuits

 The transition happens at any instant of time
 Do not use clock pulses. Change of internal state occurs when there is a change in input
variables
o Instability problem: may become unstable at times
 Storage elements work as time-delay device
o May be regarded as a combinational circuit with feedback
Synchronous sequential circuits
 The transition happens at discrete instants of time
 The circuit responds only to pulses on particular inputs

TSEDUHUB EXCLUSIVE Page 97

  Storage elements are affected only with the arrival of each pulse

Synchronous Sequential Circuits

Clocked sequential circuits: most commonly used synchronous sequential circuits
— are synchronous sequential circuits that use clock pulses in the inputs of storage elements
— has a master-clock generator to generate a periodic train of clock pulses
 The clock pulses are distributed throughout the system.
 Storage elements are affected only w/ the arrival of each pulse.
— Adv.: seldom manifest instability problems
— Storage elements: flip-flops
o flip-flop: a binary cell capable of storing one bit of information
o The state of a flip-flop can change only during a clock pulse transition.
⇒ The transition from one state to the next occurs only at predetermined time
intervals dictated by the clock pulses.

ub
uh
ed
ts

Latches and Flip Flops

Latches and flip flops are the basic elements and these are used to store information. One flip
flop and latch can store one bit of data. Both Latches and flip flops are circuit elements wherein
the output not only depends on the current inputs, but also depends on the previous input and
outputs. The main difference between the latch and flip flop is that a flip flop has a clock signal,

TSEDUHUB EXCLUSIVE Page 98

whereas a latch does not. Basically, there are four types of latches and flip flops: SR, D, JK and
T. The major differences between these types of flip flops and latches are the number of i/ps they
have and how they change the states. There are different variations for each type of latches and
flip-flops which can enhance their operations.

Difference between Latches and Flip Flops

ub
uh
ed

What is Latch?
ts

A storage element in a digital circuit can maintain a binary state indefinitely (as long as power is
delivered to the circuit), until directed by an input signal to switch states. The major differences
among various types of storage elements are in the number of inputs they possess and in the
manner in which the inputs affect the binary state. Storage elements that operate with signal
levels (rather than signal transitions) are referred to as latches; those controlled by a clock
transition are flip-flops. Latches are said to be level sensitive devices; flip-flops are edge-
sensitive devices. The two types of storage elements are related because latches are the basic
circuits from which all flip-flops are constructed. Although latches are useful for storing binary
information and for the design of asynchronous sequential circuits, they are not practical for use
as storage elements in synchronous sequential circuits.

TSEDUHUB EXCLUSIVE Page 99

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 100

 ub
uh
ed

SR latch with control input

ts

TSEDUHUB EXCLUSIVE Page 101

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 102

 ub
What is Flip Flop?

Flip flops are actually an application of logic gates. With the help of Boolean logic you can
uh
create memory with them. Flip flops can also be considered as the most basic idea of a Random
Access Memory [RAM]. When a certain input value is given to them, they will be remembered
and executed, if the logic gates are designed correctly. A higher application of flip flops is
helpful in designing better electronic circuits.
ed

The most commonly used application of flip flops is in the implementation of a feedback circuit.
As a memory relies on the feedback concept, flip flops can be used to design it.

There are mainly four types of flip flops that are used in electronic circuits. They are
ts

1. The basic Flip Flop

2. RS Flip Flop
3. Delay Flip Flop [D Flip Flop]
4. J-K Flip Flop
5. T Flip Flop

1. The basic Flip Flop

The SET-RESET flip flop is designed with the help of two NOR gates and also two NAND
gates. These flip flops are also called S-R Latch.

 S-R Flip Flop using NOR Gate

TSEDUHUB EXCLUSIVE Page 103

The design of such a flip flop includes two inputs, called the SET [S] and RESET [R]. There are
also two outputs, Q and Q’. The diagram and truth table is shown below.

ub
uh
ed

From the diagram it is evident that the flip flop has mainly four states. They are

S=1, R=0—Q=1, Q’=0

This state is also called the SET state.

ts

S=0, R=1—Q=0, Q’=1

This state is known as the RESET state.

In both the states you can see that the outputs are just compliments of each other and that the
value of Q follows the value of S.

S=0, R=0—Q & Q’ = Remember

If both the values of S and R are switched to 0, then the circuit remembers the value of S and R
in their previous state.

S=1, R=1—Q=0, Q’=0 [Invalid]

TSEDUHUB EXCLUSIVE Page 104

This is an invalid state because the values of both Q and Q’ are 0. They are supposed to be
compliments of each other. Normally, this state must be avoided.

 S-R Flip Flop using NAND Gate

The circuit of the S-R flip flop using NAND Gate and its truth table is shown below.

ub
uh
ed

Like the NOR Gate S-R flip flop, this one also has four states. They are
ts

S=1, R=0—Q=0, Q’=1

This state is also called the SET state.

S=0, R=1—Q=1, Q’=0

This state is known as the RESET state.

In both the states you can see that the outputs are just compliments of each other and that the
value of Q follows the compliment value of S.

S=0, R=0—Q=1, & Q’ =1 [Invalid]

TSEDUHUB EXCLUSIVE Page 105

If both the values of S and R are switched to 0 it is an invalid state because the values of both Q
and Q’ are 1. They are supposed to be compliments of each other. Normally, this state must be
avoided.

S=1, R=1—Q & Q’= Remember

If both the values of S and R are switched to 1, then the circuit remembers the value of S and R
in their previous state.

ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 106

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 107

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 108

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 109

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 110

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 111

ANALYSIS OF CLOCKED SEQUENTIAL CIRCUITS
The behavior of a clocked sequential circuit is determined from the inputs, the outputs, and the
state of its flip-flops. The outputs and the next state are both a function of the inputs and the
present state. The analysis of a sequential circuit consists of obtaining a table or a diagram for the
time sequence of inputs, outputs, and internal states. It is also possible to write Boolean
expressions that describe the behavior of the sequential circuit. These expressions must include
the necessary time sequence, either directly or indirectly.

A logic diagram is recognized as a clocked sequential circuit if it includes flip-flops with

clock inputs. The flip-flops may be of any type, and the logic diagram may or may not include
combinational logic gates. In this section, we introduce an algebraic representation for specifying
the next-state condition in terms of the present state and inputs. A state table and state diagram
are then presented to describe the behavior of the sequential circuit. Another algebraic
representation is introduced for specifying the logic diagram of sequential circuits.

ub
State Equations
The behavior of a clocked sequential circuit can be described algebraically by means of state
equations. A state equation (also called a transition equation) specifies the next state as a
function of the present state and inputs. Consider the sequential circuit shown in Fig. 5.15. We
will later show that it acts as a 0-detector by asserting its output when a 0 is detected in a stream
uh
of 1s. It consists of two D flip-flops A and B, an input x and an output y . Since the D input of a
flip-flop determines the value of the next state (i.e., the state reached after the clock transition), it
is possible to write a set of state equations for the circuit:
ed

state equation is an algebraic expression that specifies the condition for a flip-flop state
transition. The left side of the equation, with (t + 1), denotes the next state of the flip-flop one
clock edge later. The right side of the equation is a Boolean expression that specifies the present
ts

state and input conditions that make the next state equal to 1. Since all the variables in the
Boolean expressions are a function of the present state, we can omit the designation ( t ) after
each variable for convenience and can express the state equations in the more compact form

The Boolean expressions for the state equations can be derived directly from the gates that form
the combinational circuit part of the sequential circuit, since the D values of the combinational
circuit determine the next state. Similarly, the present-state value of the output can be expressed
algebraically as

By removing the symbol (t) for the present state, we obtain the output Boolean equation:

TSEDUHUB EXCLUSIVE Page 112

 ub
uh
ed
ts

State Table
The time sequence of inputs, outputs, and flip-flop states can be enumerated in a state table
(sometimes called a transition table). The state table for the circuit of Fig. 5.15 is shown in Table
5.2. The table consists of four sections labeled present state, input, next state, and output. The
present-state section shows the states of flip-flops A and B at any given time t. The input section
gives a value of x for each possible present state. The next-state section shows the states of the
flip-flops one clock cycle later, at time t + 1. The output section gives the value of y at time t for
each present state and input condition.

The derivation of a state table requires listing all possible binary combinations of present states
and inputs. In this case, we have eight binary combinations from 000 to 111. The next-state
values are then determined from the logic diagram or from the state equations. The next state of
flip-flop A must satisfy the state equation

TSEDUHUB EXCLUSIVE Page 113

 ub
uh
ed
ts

State Diagram
The information available in a state table can be represented graphically in the form of a state
diagram. In this type of diagram, a state is represented by a circle, and the (clock-triggered)
transitions between states are indicated by directed lines connecting the circles. The state
diagram of the sequential circuit of Fig. 5.15 is shown in Fig. 5.16 . The state diagram provides
TSEDUHUB EXCLUSIVE Page 114
the same information as the state table and is obtained directly from Table 5.2 or Table 5.3. The
binary number inside each circle identifies the state of the flip-flops. The directed lines are
labeled with two binary numbers separated by a slash. The input value during the present state is
labeled first, and the number after the slash gives the output during the present state with the
given input. (It is important to remember that the bit value listed for the output along the directed
line occurs during the present state and with the indicated input, and has nothing to do with the
transition to the next state.) For example, the directed line from state 00 to 01 is labeled 1/0,
meaning that when the sequential circuit is in the present state 00 and the input is 1, the output is
0. After the next clock cycle, the circuit goes to the next state, 01. If the input changes to 0, then
the output becomes 1, but if the input remains at 1, the output stays at 0. This information is
obtained from the state diagram along the two directed lines emanating from the circle with state
01. A directed line connecting a circle with itself indicates that no change of state occurs.

ub
uh
ed
ts

The steps presented in this example are summarized below:

TSEDUHUB EXCLUSIVE Page 115

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 116

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 117

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 118

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 119

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 120

COUNTERS

A register that goes through a prescribed sequence of states upon the application of input pulses
is called a counter. The input pulses may be clock pulses, or they may originate from some
external source and may occur at a fixed interval of time or at random. The sequence of states
may follow the binary number sequence or any other sequence of states. A counter that follows
the binary number sequence is called a binary counter. An n ‐bit binary counter consists of n
flip‐flops and can count in binary from 0 through 2n - 1.

Counters are available in two categories: ripple counters and synchronous counters.

RIPPLE COUNTERS
In a ripple counter, a flip‐flop output transition serves as a source for triggering other flip‐flops.
In other words, the C input of some or all flip‐flops are triggered, not by the common clock
pulses, but rather by the transition that occurs in other flip‐flop outputs.

Binary Ripple Counter

ub
uh
A binary ripple counter consists of a series connection of complementing flip‐flops, with the
output of each flip‐flop connected to the C input of the next higher order flip‐flop. The flip‐flop
holding the least significant bit receives the incoming count pulses. A complementing flip‐flop
can be obtained from a JK flip‐flop with the J and K inputs tied together or from a T flip‐flop. A
third possibility is to use a D flip‐flop with the complement output connected to the D input. In
ed

this way, the D input is always the complement of the present state, and the next clock pulse will
cause the flip‐flop to complement.

The logic diagram of two 4‐bit binary ripple counters is shown in Fig. 6.8. The counter is
ts

constructed with complementing flip‐flops of the T type in part (a) and D type in part (b). The
output of each flip‐flop is connected to the C input of the next flip‐flop in sequence. The flip‐flop
holding the least significant bit receives the incoming count pulses. The T inputs of all the
flip‐flops in (a) are connected to a permanent logic 1, making each flip-flop complement if the
signal in its C input goes through a negative transition. The bubble in front of the dynamic
indicator symbol next to C indicates that the flip‐flops respond to the negative‐edge transition of
the input. The negative transition occurs when the output of the previous flip‐flop to which C is
connected goes from 1 to 0.

To understand the operation of the four‐bit binary ripple counter, refer to the first nine
binary numbers listed in Table 6.4. The count starts with binary 0 and increments by 1 with each
count pulse input. After the count of 15, the counter goes back to 0 to repeat the count. The least
significant bit, A0, is complemented with each count pulse input. Every time that A0 goes from 1
to 0, it complements A1. Every time that A1 goes from 1 to 0, it complements A2. Every time
that A2 goes from 1 to 0, it complements A3, and so on for any other higher order bits of a ripple
TSEDUHUB EXCLUSIVE Page 121
counter. For example, consider the transition from count 0011 to 0100. A0 is complemented with
the count pulse. Since A0 goes from 1 to 0, it triggers A1 and complements it. As a result, A1
goes from 1 to 0, which in turn complements A2, changing it from 0 to 1. A2 does not trigger A3,
because A2 produces a positive transition and the flip‐flop responds only to negative transitions.
Thus, the count from 0011 to 0100 is achieved by changing the bits one at a time, so the count
goes from 0011 to 0010, then to 0000, and finally to 0100. The flip‐flops change one at a time in
succession, and the signal propagates through the counter in a ripple fashion from one stage to
the next.

ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 122

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 123

BCD Ripple Counter
A decimal counter follows a sequence of 10 states and returns to 0 after the count of 9. Such a
counter must have at least four flip‐flops to represent each decimal digit, since a decimal digit is
represented by a binary code with at least four bits. The sequence of states in a decimal counter
is dictated by the binary code used to represent a decimal digit. If BCD is used, the sequence of
states is as shown in the state diagram of Fig. 6.9.

A decimal counter is similar to a binary counter, except that the state after 1001 (the code
for decimal digit 9) is 0000 (the code for decimal digit 0). The logic diagram of a BCD ripple
counter using JK flip‐flops is shown in Fig. 6.10. The four outputs are designated by the letter
symbol Q, with a numeric subscript equal to the binary weight of the corresponding bit in the
BCD code. Note that the output of Q1 is applied to the C inputs of both Q2 and Q8 and the
output of Q2 is applied to the C input of Q4. The J and K inputs are connected either to a
permanent 1 signal or to outputs of other flip‐flops.

ub
A ripple counter is an asynchronous sequential circuit. Signals that affect the flip‐flop
transition depend on the way they change from 1 to 0. The operation of the counter can be
explained by a list of conditions for flip‐flop transitions. These conditions are derived from the
logic diagram and from knowledge of how a JK flip‐flop operates. Remember that when the C
input goes from 1 to 0, the flip‐flop is set if J = 1, is cleared if K = 1, is complemented if J = K =
uh
1, and is left unchanged if J = K = 0.
ed
ts

TSEDUHUB EXCLUSIVE Page 124

 ub
uh
ed
ts

To verify that these conditions result in the sequence required by a BCD ripple counter, it is
necessary to verify that the flip‐flop transitions indeed follow a sequence of states as specified by
the state diagram of Fig. 6.9. Q1 changes state after each clock pulse. Q2 complements every
time Q1 goes from 1 to 0, as long as Q8 = 0. When Q8 becomes 1, Q2 remains at 0. Q4
complements every time Q2 goes from 1 to 0. Q8 remains at 0 as long as Q2 or Q4 is 0. When
TSEDUHUB EXCLUSIVE Page 125
both Q2 and Q4 become 1, Q8 complements when Q1 goes from 1 to 0. Q8 is cleared on the next
transition of Q1.

The BCD counter of Fig. 6.10 is a decade counter, since it counts from 0 to 9. To count in
decimal from 0 to 99, we need a two‐decade counter. To count from 0 to 999, we need a
three‐decade counter. Multiple decade counters can be constructed by connecting BCD counters
in cascade, one for each decade. A three‐decade counter is shown in Fig. 6.11. The inputs to the
second and third decades come from Q8 of the previous decade. When Q8 in one decade goes
from 1 to 0, it triggers the count for the next higher order decade while its own decade goes from
9 to 0.

ub
uh
ed

SYNCHRONOUS COUNTERS
In a synchronous counter, the C inputs of all flip‐flops receive the common clock. Synchronous
counters are presented in the next two sections. Here, we present the binary and BCD ripple
counters and explain their operation.
ts

Synchronous counters are different from ripple counters in that clock pulses are applied to the
inputs of all flip‐flops. A common clock triggers all flip‐flops simultaneously, rather than one at
a time in succession as in a ripple counter. The decision whether a flip‐flop is to be
complemented is determined from the values of the data inputs, such as T or J and K at the time
of the clock edge. If T = 0 or J = K = 0, the flip‐flop does not change state. If T = 1 or J = K = 1,
the flip‐flop complements.

Binary Counter
The design of a synchronous binary counter is so simple that there is no need to go through a
sequential logic design process. In a synchronous binary counter, the flip‐flop in the least
significant position is complemented with every pulse. A flip-flop in any other position is
complemented when all the bits in the lower significant positions are equal to 1. For example, if
TSEDUHUB EXCLUSIVE Page 126
the present state of a four‐bit counter is A3A2A1A0 = 0011, the next count is 0100. A0 is always
complemented. A1 is complemented because the present state of A0 = 1. A2 is complemented
because the present state of A1A0 = 11. However, A3 is not complemented, because the present
state of A2A1A0 = 011, which does not give an all‐1’s condition.

Synchronous binary counters have a regular pattern and can be constructed with
complementing flip‐flops and gates. The regular pattern can be seen from the four‐bit counter
depicted in Fig. 6.12. The C inputs of all flip‐flops are connected to a common clock. The
counter is enabled by Count_enable. If the enable input is 0, all J and K inputs are equal to 0 and
the clock does not change the state of the counter. The first stage, A0, has its J and K equal to 1 if
the counter is enabled. The other J and K inputs are equal to 1 if all previous least significant
stages are equal to 1 and the count is enabled. The chain of AND gates generates the required
logic for the J and K inputs in each stage. The counter can be extended to any number of stages,
with each stage having an additional flip‐flop and an AND gate that gives an output of 1 if all
previous flip‐flop outputs are 1.

ub
Note that the flip‐flops trigger on the positive edge of the clock. The polarity of the clock
is not essential here, but it is with the ripple counter. The synchronous counter can be triggered
with either the positive or the negative clock edge. The complementing flip‐flops in a binary
counter can be of either the JK type, the T type, or the D type with XOR gates.
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 127

Up–Down Binary Counter
A synchronous countdown binary counter goes through the binary states in reverse order, from
1111 down to 0000 and back to 1111 to repeat the count. It is possible to design a countdown
counter in the usual manner, but the result is predictable by inspection of the downward binary
count. The bit in the least significant position is complemented with each pulse. A bit in any
other position is complemented if all lower significant bits are equal to 0.For example, the next
state after the present state of 0100 is 0011. The least significant bit is always complemented.
The second significant bit is complemented because the first bit is 0. The third significant bit is
complemented because the first two bits are equal to 0. But the fourth bit does not change,
because not all lower significant bits are equal to 0.

A countdown binary counter can be constructed as shown in Fig. 6.12, except that the inputs to
the AND gates must come from the complemented outputs, instead of the normal outputs, of the
previous flip‐flops. The two operations can be combined in one circuit to form a counter capable
of counting either up or down. The circuit of an up–down binary counter using T flip‐flops is
shown in Fig. 6.13. It has an up control input and a down control input. When the up input is 1,

ub
the circuit counts up, since the T inputs receive their signals from the values of the previous
normal outputs of the flip‐flops. When the down input is 1 and the up input is 0, the circuit
counts down, since the complemented outputs of the previous flip‐flops are applied to the T
inputs. When the up and down inputs are both 0, the circuit does not change state and remains in
the same count. When the up and down inputs are both 1, the circuit counts up. This set of
uh
conditions ensures that only one operation is performed at any given time. Note that the up input
has priority over the down input.
ed
ts

TSEDUHUB EXCLUSIVE Page 128

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 129

REGISTERS
A circuit with flip‐flops is considered a sequential circuit even in the absence of combinational
gates. Circuits that include flip‐flops are usually classified by the function they perform rather
than by the name of the sequential circuit. Two such circuits are registers and counters.

A register is a group of flip‐flops, each one of which shares a common clock and is
capable of storing one bit of information. An n ‐bit register consists of a group of n flip‐flops
capable of storing n bits of binary information. In addition to the flip‐flops, a register may have
combinational gates that perform certain data‐processing tasks. In its broadest definition, a
register consists of a group of flip‐flops together with gates that affect their operation. The
flip‐flops hold the binary information, and the gates determine how the information is transferred
into the register.

A counter is essentially a register that goes through a predetermined sequence of binary

states. The gates in the counter are connected in such a way as to produce the prescribed

ub
sequence of states. Although counters are a special type of register, it is common to differentiate
them by giving them a different name.

Various types of registers are available commercially. The simplest register is one that
consists of only flip‐flops, without any gates. Figure 6.1 shows such a register constructed with
uh
four D ‐type flip‐flops to form a four‐bit data storage register. The common clock input triggers
all flip‐flops on the positive edge of each pulse, and the binary data available at the four inputs
are transferred into the register. The value of ( I 3 , I 2 , I 1 , I 0 ) immediately before the clock
edge determines the value of ( A 3 , A 2 , A 1 , A 0 ) after the clock edge. The four outputs can be
ed

sampled at any time to obtain the binary information stored in the register. The input Clear_b
goes to the active‐low R (reset) input of all four flip‐flops. When this input goes to 0, all
flip‐flops are reset asynchronously. The Clear_b input is useful for clearing the register to all 0’s
prior to its clocked operation. The R inputs must be maintained at logic 1 (i.e., de-asserted)
during normal clocked operation. Note that, depending on the flip‐flop, either Clear, Clear_b,
ts

reset, or reset_b can be used to indicate the transfer of the register to an all 0’s state.

TSEDUHUB EXCLUSIVE Page 130

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 131

SHIFT REGISTERS
A register capable of shifting the binary information held in each cell to its neighboring cell, in a
selected direction, is called a shift register. The logical configuration of a shift register consists
of a chain of flip‐flops in cascade, with the output of one flip‐flop connected to the input of the
next flip‐flop. All flip‐flops receive common clock pulses, which activate the shift of data from
one stage to the next.

The simplest possible shift register is one that uses only flip‐flops, as shown in Fig. 6.3
.The output of a given flip‐flop is connected to the D input of the flip‐flop at its right. This shift
register is unidirectional (left‐to‐right). Each clock pulse shifts the contents of the register one bit
position to the right. The configuration does not support a left shift. The serial input determines
what goes into the leftmost flip‐flop during the shift. The serial output is taken from the output
of the rightmost flip‐flop. Sometimes it is necessary to control the shift so that it occurs only with
certain pulses, but not with others. As with the data register discussed in the previous section, the
clock’s signal can be suppressed by gating the clock signal to prevent the register from shifting.

ub
A preferred alternative in high speed circuits is to suppress the clock action, rather than gate the
clock signal, by leaving the clock path unchanged, but recirculating the output of each register
cell back through a two‐channel mux whose output is connected to the input of the cell. When
the clock action is not suppressed, the other channel of the mux provides a data path to the cell.
uh
ed
ts

The binary data in a register can be moved within the register from one flip-flop to another. The
registers that allow such data transfers are called as shift registers. There are four mode of
operation of a shift register.

 Serial Input Serial Output

 Serial Input Parallel Output
 Parallel Input Serial Output
 Parallel Input Parallel Output

TSEDUHUB EXCLUSIVE Page 132

Serial Input Serial Output
Let all the flip-flop be initially in the reset condition i.e. Q3 = Q2 = Q1 = Q0 = 0. If we entry of a
four bit binary number 1 1 1 1 into the register. When this is to be done, this number should be
applied to Din bit by with the LSB bit applied first. The D input of FF-3 i.e. D3 is connected to
serial data input Din. Output of FF-3 i.e. Q3 is connected to the input of the next flip-flop i.e. D2
and so on.

Block Diagram

Operation
ub
uh
Before application of clock signal let Q3 Q2 Q1 Q0 = 0000 and apply LSB bit of the number to be
entered to Din. So Din=D3=1. Apply the clock. On the first falling edge of clock, the FF-3 is set,
and stored word in the register is Q3 Q2 Q1 Q0 = 1000.
ed
ts

Apply the next bit to Din. So Din=1. As soon as the next negative edge of the clock hits, FF-2 will
set and the stored word change to Q3 Q2 Q1 Q0 = 1100.

TSEDUHUB EXCLUSIVE Page 133

Apply the next bit to be stored i.e. 1 to Din. Apply the clock pulse. As soon as the third negative
clock edge hits, FF-1 will be set and output will be modified to Q3 Q2 Q1 Q0 = 1110.

ub
uh
Similarly with Din=1 and with the fourth negative clock edge arriving, the stored word in the
register is Q3 Q2 Q1 Q0 = 1111.
ed
ts

Truth Table

TSEDUHUB EXCLUSIVE Page 134

Serial Input Parallel Output
 In such types of operations, the data is entered serially and taken out in parallel fashion.
 Data is loaded bit by bit. The outputs are disabled as long as the data is loading.
 As soon as the data loading gets completed, all the flip-flops contain their required data,
the outputs are enabled so that all the loaded data is made available over all the output
lines at the same time.
 4 clock cycles are required to load a four bit word. Hence the speed of operation of SIPO
mode is same as that of SISO mode.

Block Diagram

ub
uh
Parallel Input Serial Output (PISO)
ed

 Data bits are entered in parallel fashion.

 The circuit shown below is a four bit parallel input serial output register.
 Output of previous Flip Flop is connected to the input of the next one via a combinational
ts

circuit.
 The binary input word B0,B1,B2,B3 is applied though the same combinational circuit.
 There are two modes in which this circuit can work namely shift mode or load mode.

Load mode

When the shift/load bar line is low (0), the AND gate 2,4 and 6 become active. They will pass
B1,B2,B3 bits to the corresponding flip-flops. On the low going edge of clock, the binary input
B0,B1,B2,B3 will get loaded into the corresponding flip-flops. Thus parallel loading takes place.

Shift mode

When the shift/load bar line is low (1), the AND gate 2,4 and 6 become inactive. Hence the
parallel loading of the data becomes impossible. But the AND gate 1,3 and 5 become active.

TSEDUHUB EXCLUSIVE Page 135

Therefore the shifting of data from left to right bit by bit on application of clock pulses. Thus the
parallel in serial out operation take place.

Block Diagram

ub
uh
Parallel Input Parallel Output (PIPO)
In this mode, the 4 bit binary input B0,B1,B2,B3 is applied to the data inputs D0,D1,D2,D3
ed

respectively of the four flip-flops. As soon as a negative clock edge is applied, the input binary
bits will be loaded into the flip-flops simultaneously. The loaded bits will appear simultaneously
to the output side. Only clock pulse is essential to load all the bits.
ts

Block Diagram

TSEDUHUB EXCLUSIVE Page 136

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 137

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 138

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 139

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 140

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 141

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 142

 UNIT-V

Memory Devices
A memory is just like a human brain. It is used to store data and instruction. Computer memory
is the storage space in computer where data is to be processed and instructions required for
processing are stored.

The memory is divided into large number of small parts. Each part is called cell. Each location or
cell has a unique address which varies from zero to memory size minus one.

For example if computer has 64k words, then this memory unit has 64 * 1024=65536 memory
location. The address of these locations varies from 0 to 65535.

Memory is primarily of two types

ub
 Internal Memory - cache memory and primary/main memory
 External Memory - magnetic disk / optical disk etc.
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 143

Characteristics of Memory Hierarchy are following when we go from top to bottom.

 Capacity in terms of storage increases.

 Cost per bit of storage decreases.
 Frequency of access of the memory by the CPU decreases.
 Access time by the CPU increases

Comparison chart
RAM ROM
Random Access Memory or RAM is Read-only memory or ROM is also a form of
a form of data storage that can be data storage that can not be easily altered or
accessed randomly at any time, in any reprogrammed. Stores instructions that are not
Definition
order and from any physical location, necessary for re-booting up to make the
allowing quick access and computer operate when it is switched off.

ub
manipulation. They are hardwired.
Stands for Random Access Memory Read-only memory
RAM allows the computer to read
ROM stores the program required to initially
Use data quickly to run applications. It
boot the computer. It only allows reading.
uh
allows reading and writing.
RAM is volatile i.e. its contents are It is non-volatile i.e. its contents are retained
Volatility
lost when the device is powered off. even when the device is powered off.
The two main types of RAM are static The types of ROM include PROM, EPROM
Types
ed

RAM and dynamic RAM. and EEPROM.

RANDOM-ACCESS MEMORY
ts

A memory unit is a collection of storage cells, together with associated circuits needed to transfer
information into and out of a device. The architecture of memory is such that information can be
selectively retrieved from any of its internal locations. The time it takes to transfer information to
or from any desired random location is always the same—hence the name random-access
memory, abbreviated RAM. In contrast, the time required to retrieve information that is stored on
magnetic tape depends on the location of the data.

A memory unit stores binary information in groups of bits called words. A word in
memory is an entity of bits that move in and out of storage as a unit. A memory word is a group
of 1’s and 0’s and may represent a number, an instruction, one or more alphanumeric characters,
or any other binary‐coded information. A group of 8 bits is called a byte. Most computer
memories use words that are multiples of 8 bits in length. Thus, a 16‐bit word contains two
bytes, and a 32‐bit word is made up of four bytes. The capacity of a memory unit is usually
stated as the total number of bytes that the unit can store.

TSEDUHUB EXCLUSIVE Page 144

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 145

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 146

 ub
uh
ed

RAM is of two types

 Static RAM (SRAM)

 Dynamic RAM (DRAM)
ts

Static RAM (SRAM)

The word static indicates that the memory retains its contents as long as power remains applied.
However, data is lost when the power gets down due to volatile nature. SRAM chips use a matrix
of 6-transistors and no capacitors. Transistors do not require power to prevent leakage, so SRAM
need not have to be refreshed on a regular basis.

Because of the extra space in the matrix, SRAM uses more chips than DRAM for the same
amount of storage space, thus making the manufacturing costs higher.

Static RAM is used as cache memory needs to be very fast and small.

TSEDUHUB EXCLUSIVE Page 147

Dynamic RAM (DRAM)

DRAM, unlike SRAM, must be continually refreshed in order for it to maintain the data. This is
done by placing the memory on a refresh circuit that rewrites the data several hundred times per
second. DRAM is used for most system memory because it is cheap and small. All DRAMs are
made up of memory cells. These cells are composed of one capacitor and one transistor.

ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 148

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 149

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 150

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 151

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 152

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 153

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 154

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 155

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 156

Types of ROM
ROM stands for Read Only Memory. The memory from which we can only read but cannot
write on it. This type of memory is non-volatile. The information is stored permanently in such
memories during manufacture.ROM stores such instruction as are required to start computer
when electricity is first turned on, this operation is referred to as bootstrap. ROM chip are not
only used in the computer but also in other electronic items like washing machine and
microwave oven.

Following are the various types of ROM

MROM (Masked ROM)

The very first ROMs were hard-wired devices that contained a pre-programmed set of data or
instructions. These kinds of ROMs are known as masked ROMs. It is inexpensive ROM.

ub
PROM (Programmable Read only Memory)

PROM is read-only memory that can be modified only once by a user. The user buys a blank
PROM and enters the desired contents using a PROM programmer. Inside the PROM chip there
uh
are small fuses which are burnt open during programming. It can be programmed only once and
is not erasable.

EPROM (Erasable and Programmable Read Only Memory)

ed

The EPROM can be erased by exposing it to ultra-violet light for duration of upto 40 minutes.
Usually, a EPROM eraser achieves this function. During programming an electrical charge is
trapped in an insulated gate region. The charge is retained for more than ten years because the
charge has no leakage path. For erasing this charge, ultra-violet light is passed through a quartz
crystal window (lid). This exposure to ultra-violet light dissipates the charge. During normal use
ts

the quartz lid is sealed with a sticker.

EEPROM (Electrically Erasable and Programmable Read Only Memory)

The EEPROM is programmed and erased electrically. It can be erased and reprogrammed about
ten thousand times. Both erasing and programming take about 4 to 10 ms (milli second). In
EEPROM, any location can be selectively erased and programmed. EEPROMs can be erased one
byte at a time, rather than erasing the entire chip. Hence, the process of re-programming is
flexible but slow.

Flash memory devices are similar to EEPROMs, but have additional built‐in circuitry to
selectively program and erase the device in‐circuit, without the need for a special programmer.
They have widespread application in modern technology in cell phones, digital cameras, set‐top
boxes, digital TV, telecommunications, nonvolatile data storage, and microcontrollers. Their low
TSEDUHUB EXCLUSIVE Page 157
consumption of power makes them an attractive storage medium for laptop and notebook
computers.

ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 158

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 159

 ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 160

 ub
uh
Sequential Access Memory
ed

Sequential access means the system must search the storage device from the beginning of the
memory address until it finds the required piece of data. Memory device which supports such
access is called a Sequential Access Memory or Serial Access Memory. Magnetic tape is an
example of serial access memory.
ts

Direct Access Memory

Direct access memory or Random Access Memory, refers to condition in which a system can go
directly to the information that the user wants. Memory device which supports such access is
called a Direct Access Memory. Magnetic disk, optical disks are an examples of direct access
memory.

Cache Memory
Cache memory is a very high speed semiconductor memory which can speed up CPU. It acts as a
buffer between the CPU and main memory. It is used to hold those parts of data and program

TSEDUHUB EXCLUSIVE Page 161

which are most frequently used by CPU. The parts of data and programs are transferred from
disk to cache memory by operating system, from where CPU can access them.

Advantages

 Cache memory is faster than main memory.

 It consumes less access time as compared to main memory.
 It stores the program that can be executed within a short period of time.
 It stores data for temporary use.

Disadvantages

 Cache memory has limited capacity.

 It is very expensive.

Virtual memory

ub
Virtual memory is a technique that allows the execution of processes which are not completely
available in memory. The main visible advantage of this scheme is that programs can be larger
than physical memory. Virtual memory is the separation of user logical memory from physical
uh
memory.

This separation allows an extremely large virtual memory to be provided for programmers when
only a smaller physical memory is available. Following are the situations, when entire program is
not required to be loaded fully in main memory.
ed

 User written error handling routines are used only when an error occurred in the data or
computation.
 Certain options and features of a program may be used rarely.
 Many tables are assigned a fixed amount of address space even though only a small
ts

amount of the table is actually used.

 The ability to execute a program that is only partially in memory would counter many
benefits.
 Less number of I/O would be needed to load or swap each user program into memory.
 A program would no longer be constrained by the amount of physical memory that is
available.
 Each user program could take less physical memory, more programs could be run the
same time, with a corresponding increase in CPU utilization and throughput.

Auxiliary Memory
Auxiliary memory is much larger in size than main memory but is slower. It normally stores
system programs, instruction and data files. It is also known as secondary memory. It can also be
used as an overflow/virtual memory in case the main memory capacity has been exceeded.
TSEDUHUB EXCLUSIVE Page 162
Secondary memories can not be accessed directly by a processor. First the data / information of
auxiliary memory is transferred to the main memory and then that information can be accessed
by the CPU. Characteristics of Auxiliary Memory are following

 Non-volatile memory - Data is not lost when power is cut off.

 Reusable - The data stays in the secondary storage on permanent basis until it is not
overwritten or deleted by the user.
 Reliable - Data in secondary storage is safe because of high physical stability of
secondary storage device.
 Convenience - With the help of computer software, authorized people can locate and
access the data quickly.
 Capacity - Secondary storage can store large volumes of data in sets of multiple disks.
 Cost - It is much lesser expensive to store data on a tape or disk than primary memory.

ub
uh
ed
ts

TSEDUHUB EXCLUSIVE Page 163