Ilovepdf Merged

Download as pdf or txt
Download as pdf or txt
You are on page 1of 746

Lecture 01: INTRODUCTION

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Main Objectives of the Course
Switching Circuits and Logic Design
1. Learn about number systems, logic gates, and Boolean algebra.
2. Learn about the representation, manipulation and minimization of Boolean functions.
3. Learn how to design combinational and sequential circuits.
4. Understand the concepts of finite state machines, state minimization, and algorithmic
state machines.
5. Learn about analysis and synthesis of asynchronous circuits.
6. Learn about the basic concepts in testing and fault diagnosis of digital circuits..

Switching Circuits & Logic Design 2


Number Systems
• Systematic way to represent and manipulate numbers.
• Some examples:
– Decimal number system
– Roman number system
– Binary number system
– Sexagesimal number system
• Broad classification:
a) Weighted: decimal, binary, etc.
b) Non-weighted: Roman, Gray code, etc.

Switching Circuits & Logic Design 3


Some Basic Concepts
• We are accustomed to the so-called decimal number system.
– Ten digits :: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
– Every digit position has a weight which is a power of 10.
– Base or radix is 10.
• Examples:
234 = 2 x 102 + 3 x 101 + 4 x 100
250.67 = 2 x 102 + 5 x 101 + 0 x 100 + 6 x 10-1 + 7 x 10-2

Switching Circuits & Logic Design


4
Binary Number System
• Two digits: 0 and 1.
– Every digit position has a weight that is a power of 2.
– Base or radix is 2.
– Binary digits are called bits.
• Examples:
110 = 1 x 22 + 1 x 21 + 0 x 20
101.01 = 1 x 22 + 0 x 21 + 1 x 20 + 0 x 2-1 + 1 x 2-2

Switching Circuits & Logic Design


5
Generalization: Radix-based Number System
• Radix (r): Number of distinct digits.
– Assume that the digits are 0, 1, 2, …, (r-1)
– Every digit position has a weight that is some power of r (say, rk).
• k ≥ 0, for the integer part
• k < 0, for the fractional part
• A (n+m)-digit number representation:
D = dn-1 dn-2 …..d1 d0 . d-1 d-2 ….. d-m

Switching Circuits & Logic Design 6


Binary to Decimal Conversion
• Each digit position of a binary number has a weight.
– Some power of 2.
• A binary number:
B = bn-1 bn-2 …..b1 b0 . b-1 b-2 ….. b-m
where bi are the binary digits.

Corresponding value in decimal:


n-1
D =  bi 2i
i = -m

Switching Circuits & Logic Design


7
Some Examples
1. 101011  1x25 + 0x24 + 1x23 + 0x22 + 1x21 + 1x20 = 43
(101011)2 = (43)10

2. .0101  0x2-1 + 1x2-2 + 0x2-3 + 1x2-4 = .3125


(.0101)2 = (.3125)10

3. 101.11  1x22 + 0x21 + 1x20 + 1x2-1 + 1x2-2 = 5.75


(101.11)2 = (5.75)10

Switching Circuits & Logic Design


8
Decimal to Binary Conversion
• Consider the integer and fractional parts separately.
• For the integer part:
– Repeatedly divide the given number by 2, and go on accumulating the remainders, until
the number becomes zero.
– Arrange the remainders in reverse order.
• For the fractional part:
– Repeatedly multiply the given fraction by 2.
• Accumulate the integer part (0 or 1).
• If the integer part is 1, chop it off.
– Arrange the integer parts in the order they are obtained.

Switching Circuits & Logic Design


9
Examples
2 239 2 64 .634 x 2 = 1.268 37.0625
2 119 --- 1 2 32 --- 0
.268 x 2 = 0.536 (37)10 = (100101)2
2 59 --- 1 2 16 --- 0
2 29 --- 1 2 8 --- 0 .536 x 2 = 1.072
(.0625)10 = (.0001)2
2 14 --- 1 2 4 --- 0 .072 x 2 = 0.144
2 7 --- 0 2 2 --- 0 .144 x 2 = 0.288
2 3 --- 1 2 1 --- 0 : (37.0625)10 =
2 1 --- 1 2 0 --- 1
2 0 --- 1 (.634)10 = (.10100……)2 (100101 . 0001)2
(64)10 = (1000000)2
(239)10 = (11101111)2

Switching Circuits & Logic Design


10
END OF LECTURE 01

Switching Circuits & Logic Design 11


Lecture 02: OCTAL AND HEXADECIMAL NUMBER SYSTEMS

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Octal Number System
Octal Binary
• A compact way to represent
0 000
binary numbers.
1 001
– Group of three binary digits are 2 010
represented by a octal digit.
3 011
– Octal digits are 0 to 7. 4 100
5 101
6 110
7 111

Switching Circuits & Logic Design


2
Binary to Octal Conversion
• For the integer part:
– Scan the binary number from right to left.
– Translate each group of three bits into the corresponding octal digit.
• Add leading zeros if necessary.
• For the fractional part:
– Scan the binary number from left to right.
– Translate each group of three bits into the corresponding octal digit.
• Add trailing zeros if necessary.

Switching Circuits & Logic Design


3
Examples (Binary to Octal)
1. (101 101 000 011)2 = (5503)8
2. (1 010 100 001)2 = (1241)8 Two leading 0s are added

3. (.100 001 1)2 = (.414)8 Two trailing 0s are added

4. (11 . 010 111 1)2 = (3.274)8 A leading 0 and two


trailing 0s are added

Switching Circuits & Logic Design


4
Octal to Binary Conversion
• Translate every octal digit into its 3-bit binary equivalent.
• Examples:
(1645)8 = (001 110 100 101)2
(22.172)8 = (010 010 . 001 111 010)2
(1.54)8 = (001 . 101 100)2

Switching Circuits & Logic Design


5
Hexadecimal Number System
• A compact way to represent binary Hex Binary Hex Binary
numbers. 0 0000 8 1000
– Group of four binary digits are 1 0001 9 1001
represented by a hexadecimal digit. 2 0010 A 1010
– Hexadecimal digits are 0 to 9, A to F. 3 0011 B 1011
4 0100 C 1100
5 0101 D 1101
6 0110 E 1110
7 0111 F 1111

Switching Circuits & Logic Design


6
Binary to Hexadecimal Conversion
• For the integer part:
– Scan the binary number from right to left.
– Translate each group of four bits into the corresponding hexadecimal digit.
• Add leading zeros if necessary.
• For the fractional part:
– Scan the binary number from left to right.
– Translate each group of four bits into the corresponding hexadecimal digit.
• Add trailing zeros if necessary.

Switching Circuits & Logic Design


7
Examples (Binary to Hexadecimal)
1. (1011 0100 0011)2 = (B43)16
2. (10 1010 0001)2 = (2A1)16 Two leading 0s are added

3. (.1000 010)2 = (.84)16 A trailing 0 is added

4. (101 . 0101 111)2 = (5.5E)16 A leading 0 and trailing 0


are added

Switching Circuits & Logic Design


8
Hexadecimal to Binary Conversion
• Translate every hexadecimal digit into its 4-bit binary equivalent.
• Examples:
(3A5)16 = (0011 1010 0101)2
(12.3D)16 = (0001 0010 . 0011 1101)2
(1.8)16 = (0001 . 1000)2

Switching Circuits & Logic Design


9
Decimal to Radix-r and Vice Versa
• We follow a principle similar to decimal-binary and binary-decimal conversion
as discussed earlier.
• Radix-r to decimal:
– Multiply each digit by corresponding weight and add them up.
• Decimal to radix-r:
– For the integer part, repeatedly divide the number by r and accumulate the
remainder. Remainders are arranged in reverse order.
– For the fractional part, repeatedly multiply by r, and accumulate & discard the
integer part. The digits are arranged in the order they are generated.

Switching Circuits & Logic Design 10


END OF LECTURE 02

Switching Circuits & Logic Design 11


Lecture 03: SIGNED AND UNSIGNED BINARY
NUMBER REPRESENTATION
PROF. INDRANIL SENGUPTA
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Why are Binary Numbers Important?
• We implement circuits using electronic components like transistors.
– A transistor acts like a switch: either conducting (ON) or non-conducting (OFF).
– There are billions of such miniature switches in modern-day VLSI chips.
• A switch can represent two states.
– Binary number system also has two digits, 0 and 1.
– We can follow some convention:
• Open switch represents 0, closed switch represents 1.
• Low voltage represents 0, high voltage represents 1.
• Absence of current represents 0, flow of current represents 1.
• Absence of light represents 0, presence of light represents 1.

Switching Circuits & Logic Design 2


• We concentrate on binary numbers in this course.
• Some conventions followed:
– Bit: single binary digit (0 or 1)
– Nibble: collection of 4 bits
– Byte: collection of 8 bits
– Word: collection of 16/32/64 bits

Switching Circuits & Logic Design 3


Representing Numbers in Binary
• How many distinct numbers can be represented in n bits?
– Each bit can be in one of two states.
– Total number of possible combinations:
2 x 2 x …. to n terms = 2n
• Numbers can be either unsigned or signed:
– An unsigned number has only a magnitude, bit no sign.
– A signed number has both a magnitude and also a sign (positive or negative).

Switching Circuits & Logic Design 4


Unsigned Binary Numbers
• An n-bit binary number can have 2n distinct combinations.
– Minimum: 0, Maximum: 2n – 1.
– For example, for n=3, the 8 distinct combinations are:
000, 001, 010, 011, 100, 101, 110, 111 (0 to 23-1 = 7 in decimal).

Number of bits (n) Range of Numbers


8 0 to 28-1 (255)
16 0 to 216-1 (65,535)
32 0 to 232-1 (4,294,967,295)
64 0 to 264-1

Switching Circuits & Logic Design


5
• An n-bit binary integer:
bn-1bn-2 … b2b1b0

• Equivalent unsigned decimal value:


D = bn-12n-1 + bn-22n-2 + … + b222 + b121 + b020
• Each digit position has a weight that is some power of 2.

Switching Circuits & Logic Design


6
Decimal Unsigned Decimal Unsigned
Unsigned Number binary binary
Representation in +0 0000 +8 1000
4 Bits +1 0001 +9 1001
+2 0010 +10 1010
+3 0011 +11 1011
+4 0100 +12 1100
+5 0101 +13 1101
+6 0110 +14 1110
+7 0111 +15 1111

Switching Circuits & Logic Design 7


Signed Integer Representation
• Many of the numerical data items that we use are signed
(positive or negative).
– Question:: How to represent sign?
• Three possible approaches:
a) Sign-magnitude representation
b) One’s complement representation
c) Two’s complement representation

Switching Circuits & Logic Design 8


(a) Sign-magnitude Representation
• For an n-bit number representation:
– The most significant bit (MSB) indicates sign (0: positive, 1: negative).
– The remaining (n-1) bits represent the magnitude of the number.
• Range of numbers: – (2n-1 – 1) to + (2n-1 – 1)

bn-1 bn-2 b1 b0
Sign Magnitude
• A problem: Two different representations for zero.
+0: 0 00..000 and -0: 1 00..000

Switching Circuits & Logic Design 9


Decimal Unsigned Decimal Unsigned
Sign-Magnitude binary binary
Number +0 0000 -0 1000
Representation in 4 +1 0001 -1 1001
Bits
+2 0010 -2 1010
+3 0011 -3 1011
+4 0100 -4 1100
+5 0101 -5 1101
+6 0110 -6 1110
+7 0111 -7 1111

Switching Circuits & Logic Design 10


(b) Ones Complement Representation

• Basic idea:
– Positive numbers are represented exactly as in sign-magnitude form.
– Negative numbers are represented in 1’s complement form.
• How to compute the 1’s complement of a number?
– Complement every bit of the number (1 to 0, and 0 to 1).
– Most Significant Bit (MSB) will indicate the sign of the number (0: positive, 1:
negative).

Switching Circuits & Logic Design 11


Example for n=4
Decimal 1’s Decimal 1’s
complement complement
To find the representation of,
+0 0000 -7 1000
say, -4, first note that
+1 0001 -6 1001
+2 0010 -5 1010 +4 = 0100
+3 0011 -4 1011 -4 = 1’s complement of
+4 0100 -3 1100 0100 = 1011
+5 0101 -2 1101
+6 0110 -1 1110
+7 0111 -0 1111

Switching Circuits & Logic Design 12


• Range of numbers that can be represented in 1’s complement:
Maximum :: + (2n-1 – 1)
Minimum ::  (2n-1 – 1)
• A problem (same as in sign magnitude):
Two different representations of zero.
+0  0 000….0
-0  1 111….1
• Advantage of 1’s complement representation:
– Subtraction can be done using addition.
– Leads to substantial saving in circuitry.

Switching Circuits & Logic Design 13


(c) Twos Complement Representation
• Basic idea:
– Positive numbers are represented exactly as in sign-magnitude form.
– Negative numbers are represented in 2’s complement form.
• How to compute the 2’s complement of a number?
– Complement every bit of the number (1 to 0 and 0 to 1), and then add one to
the resulting number.
– MSB will indicate the sign of the number (0: positive, 1: negative).

Switching Circuits & Logic Design 14


Example for n=4
Decimal 2’s Decimal 2’s
complement complement
To find the representation of,
+0 0000 -8 1000
say, -4, first note that
+1 0001 -7 1001
+2 0010 -6 1010 +4 = 0100
+3 0011 -5 1011 -4 = 2’s complement of
+4 0100 -4 1100 0100 = 1011 + 1
= 1100
+5 0101 -3 1101
+6 0110 -2 1110
+7 0111 -1 1111

Switching Circuits & Logic Design 15


• Range of numbers that can be represented in 2’s complement:
Maximum :: + (2n-1 – 1)
Minimum ::  2n-1
• Advantage of 2’s complement representation:
– Unique representation of zero.
– Subtraction can be done using addition.
– Leads to substantial saving in circuitry.
• Almost all computers today use 2’s complement representation for storing
negative numbers.

Switching Circuits & Logic Design 16


• Some other features of 2’s complement representation
a) Weighted number representation, with the MSB having weight -2n-1.
-2n-1 2n-2 21 20
bn-1 bn-2 b1 b0
D = -bn-12n-1 + bn-22n-2 + … + b222 + b121 + b020
b) Shift left by k positions with zero padding multiplies the number by 2k.

00010011 = +19 :: Shift left by 2 :: 01001100 = +76

11100011 = -29 :: Shift left by 2 :: 10001100 = -116

Switching Circuits & Logic Design 17


c) Shift right by k positions with sign bit padding divides the number by 2k.

00010110 = +22 :: Shift right by 2 :: 00000101 = +5

11100100 = -28 :: Shift right by 2 :: 11111001 = -7

d) The sign bit can be copied as many times as required in the beginning to extend
the size of the number (called sign extension).

X = 00101111 (8-bit number, value = +47) X = 10100011 (8-bit number, value = -93)
Sign extend to 32 bits: Sign extend to 32 bits:
00000000 00000000 00000000 00101111 11111111 11111111 11111111 10100011

Switching Circuits & Logic Design 18


END OF LECTURE 03

Switching Circuits & Logic Design 19


Lecture 04: BINARY ADDITION AND SUBTRACTION

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Binary Arithmetic
• The binary number system is widely used in digital systems.
• It is necessary to understand some essential concepts about binary arithmetic.
Input Bits a+b a–b a.b
a b Sum Carry Difference Borrow Product
0 0 0 0 0 0 0
0 1 1 0 1 1 0
1 0 1 0 1 0 0
1 1 0 1 0 0 1

Switching Circuits & Logic Design 2


(a) Binary Addition
• Binary addition is performed in a manner similar to that of decimal addition.
– Corresponding bits are added, and if a carry 1 is produced, it is added to the binary
digits at the left.
– Examples:
Carry: 1 1 1 0 1 1 1 1 1 1 0 0
0 1 0 1 0 0 1 1 1 1 0 1 1 0 1
1 0 1 1 1 0 0 0 0 1 0 0 1 1 0
------------ ------------ -----------
1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 1

Switching Circuits & Logic Design 3


(b) Binary Subtraction
• Binary subtraction is again performed similar to decimal subtraction.
– Borrow bits are generated, and used in a similar manner.
– Examples:
Borrow: 0 1 0 0 1 0 0 0 1 1 0 0
1 0 0 1 0 1 0 1 1 1 0 0 0 1 1
0 1 1 0 0 0 1 0 0 1 0 0 1 0 0
------------ ------------ -------------
0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1

Switching Circuits & Logic Design 4


Subtraction Using Addition :: 1’s Complement
• How to compute A – B ?
– Compute the 1’s complement of B (say, B1).
– Compute R = A + B1
– If a carry is obtained after addition is ‘1’:
• Add the carry back to R (called end-around carry).
• That is, R = R + 1.
• The result is a positive number.
Else
• The result is negative, and is in 1’s complement form in R.

Switching Circuits & Logic Design 5


Example 1 :: 6 – 2
1’s complement of 2 = 1101

6 :: 0110 Assume 4-bit representations.


-2 :: 1101
Since there is a carry, it is
1 0011
added back to the result.
1
End-around The result is positive.
carry 0100 = +4

Switching Circuits & Logic Design 6


Spring Semester Programming and Data
Example 2 :: 3 – 5
1’s complement of 5 = 1010

3 :: 0011
Assume 4-bit representations.
-5 :: 1010
1101 = -2 Since there is no carry, the result is
negative.
1101 is the 1’s complement of
0010, that is, it represents –2.

Switching Circuits & Logic Design 7


Subtraction Using Addition :: 2’s Complement
• How to compute A – B ?
– Compute the 2’s complement of B (say, B2).
– Compute R = A + B2
– If a carry is obtained after addition is ‘1’:
• Ignore the carry.
• The result is a positive number.
Else
• The result is negative, and is in 2’s complement form in R.

Switching Circuits & Logic Design 8


Example 1 :: 6 – 2
2’s complement of 2 = 1101 + 1 = 1110

6 :: 0110
Assume 4-bit representations.
-2 :: 1110
1 0100 = +4 Presence of carry indicates that
the result is positive.

Ignore carry No need to add the end-around


carry like in 1’s complement.

Switching Circuits & Logic Design 9


Example 2 :: 3 – 5

2’s complement of 5 = 1010 + 1 = 1011

3 :: 0011
-5 :: 1011 Assume 4-bit representations.
1110 = -2 Since there is no carry, the result is
negative.
1110 is the 2’s complement of
0010, that is, it represents –2.

Switching Circuits & Logic Design 10


How to Detect Overflow?
• When the sign of two numbers are different, adding them can never result in
overflow.
• When can overflow occur?
– Sign of the two numbers are the same.
– Sign of the sum is different from the sign of either of the numbers.

Switching Circuits & Logic Design 11


END OF LECTURE 04

Switching Circuits & Logic Design 12


Lecture 05: BCD AND GRAY CODE REPRESENTATIONS

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Binary Coded Decimal (BCD) Number Representation
• It is sometimes desirable to manipulate numbers in decimal instead of
converting them to binary.
– Decimal-to-binary and binary-to-decimal conversion process is complex.
• One popular code to represent decimal digits is BCD.
– Each decimal digit is represented by its 4-bit binary equivalent.
– Conversion is much easier.
• Examples: The six 4-bit combinations
– Decimal: 238 BCD: 0010 0011 1000 1010, 1011, 1100, 1101,
– Decimal: 12.39 BCD: 0001 0010 . 0011 1001 1110 and 1111 and unused.

Switching Circuits & Logic Design 2


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

Switching Circuits & Logic Design 3


Addition of BCD Numbers
• When we add two BCD numbers, we may have to go for a correction step
where 6 (0110) is added to one of the nibbles.
– Either when a nibble is one of the six invalid combinations, or there is a carry in
from the previous nibble.
• Examples:
23 + 46 23 + 48 28 + 39
0010 0011 0010 0011 0010 1000
0100 0110 0100 1000 0011 1001
----------- ----------- -----------
0110 1001 0110 1011 0110 0001
+ 0110 + 0110 (carry generated)
----------- -----------
0111 0001 0110 0111

Switching Circuits & Logic Design 4


Gray Codes
• Gray code is a type of non-weighted binary code where successive code words
differ in only one bit.
– Any code with this property is called cyclic code.
• Gray code is useful in many practical applications that require analog to digital
conversion.
– To reduce error in conversion.
– Also, binary-to-Gray and Gray-to-binary conversions are easy.
– Example: to measure the angle of rotation of a wheel.
• 4-bit Gray code is illustrated on the next slide.

Switching Circuits & Logic Design 5


Decimal Gray Code Binary Code Decimal Gray Code Binary Code
g3 g2 g1 g0 b3 b2 b1 b0 g3 g2 g1 g0 b3 b2 b1 b0
0 0 0 0 0 0 0 0 0 8 1 1 0 0 1 0 0 0
1 0 0 0 1 0 0 0 1 9 1 1 0 1 1 0 0 1
2 0 0 1 1 0 0 1 0 10 1 1 1 1 1 0 1 0
3 0 0 1 0 0 0 1 1 11 1 1 1 0 1 0 1 1
4 0 1 1 0 0 1 0 0 12 1 0 1 0 1 1 0 0
5 0 1 1 1 0 1 0 1 13 1 0 1 1 1 1 0 1
6 0 1 0 1 0 1 1 0 14 1 0 0 1 1 1 1 0
7 0 1 0 0 0 1 1 1 15 1 0 0 0 1 1 1 1

Switching Circuits & Logic Design 6


• Gray code is also called self reflecting code.
– Suppose we have the Gray code representation for m bits.
– To obtain the Gray code representation for (m+1) bits, we write down two m-bit
representations one below the other, with the second one being the mirror image
of the first one.
– We then add a 0 at the beginning of every code in the first group, and a 1 at the
beginning of every code in the second group.

Switching Circuits & Logic Design 7


00 0 00 0 000
01 0 01 0 001
11 0 11 0 011
10 0 10 0 010
Illustration of self 1 10 0 110
reflection in Gray code 1 11 0 111
1 01 0 101
generation 1 00 0 100
1 100
1 101
1 111
1 110
1 010
1 011
1 001
1 000

Switching Circuits & Logic Design 8


Binary to Gray Code Conversion
• Let gn-1gn-2…g2g1g0 and bn-1bn-2…b2b1b0 denote n-bit Gray code and its binary
equivalent respectively.
gi = bi  bi+1, for 0 ≤ I ≤ n-2
gn-1 = gn-1
• Here, the symbol  denotes modulo-2 sum, defined as:
0  0 = 1, 0  1 = 1, 1  0 = 1, 1  1 = 0
• An example: b5 b4 b3 b2 b1 b0
1 0 1 1 0 1

+ + + + + +
1 1 1 0 1 1
g5 g4 g3 g2 g1 g0

Switching Circuits & Logic Design 9


Gray to Binary Code Conversion
• We start with the leftmost bit and proceed to the least significant bit, and set:
bi = gi if no. of 1’s preceding gi is even
bi = gi’ if no. of 1’s preceding gi is odd

Switching Circuits & Logic Design 10


Gray Code to Measure Angular Rotation

Switching Circuits & Logic Design 11


• If binary code was used instead of Gray code, error during reading the position
can be considerably high.
– Say, when there is a transition from 7 (0111) to 8 (1000); all 4 bits change.
– But in Gray code, error can only be in a single bit during readout.

Switching Circuits & Logic Design 12


END OF LECTURE 05

Switching Circuits & Logic Design 13


Lecture 06: ERROR DETECTION AND CORRECTION

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Error Detection and Correction
• Basic concept:
– Extra bits are added to the data bits that we want to represent, to get codewords.
– Codewords are divided into two categories: valid codewords and invalid codewords.
– A bit error changes a valid codeword to an invalid codeword.
• Definition:
– The distance between two codewords Ci and Cj, denoted by dist (Ci, Cj), denotes the
number of bit positions in which the codewords differ.
– Example: distance between codewords 01001 and 11100 is 3.

Switching Circuits & Logic Design 2


Valid Invalid
Codewords Codewords

• We can check whether a given codeword is valid or invalid.


• For detecting single bit error, the distance between any pair of valid
codewords must be at least 2.
 For detecting k errors, the distance must be at least (k+1).
• For single error correction, the distance must be at least 3.

Switching Circuits & Logic Design 3


Parity Code for Error Detection
• The parity of a given binary word is 3-bit Binary Word Parity Bit
defined by whether the number of 0 0 0 0
1’s is odd or even. 0 0 1 1
– We can add an extra bit, called parity 0 1 0 1
bit, to make the number if 1’s in 0 1 1 0
every valid codeword even (say).
1 0 0 1
– An example for 3-bit words is shown.
1 0 1 0
– Any odd number of bit errors can be
1 1 0 0
detected.
1 1 1 1

Switching Circuits & Logic Design 4


Hamming Code for Single Error Correction
• A code with minimum distance of 2k+1 can detect up to k bit errors.
• Basic principle of Hamming code:
– To each group of m information bits, k parity bits are added to form a (m+k)-bit
code.
– Each of the (m+k) bit locations in a codeword is assigned a value.
• 1 to the MSB, 2 to the second MSB, …, (m+k) to the LSB.
– k must satisfy the inequality: 2k ≥ m + k + 1 (e.g. for m=4, k will be 3)
– The parity check bits are assigned position numbers that are powers of 2 (that is, 1,
2, 4, …).
– The parity check bits are computed based on some well-defined formula.

Switching Circuits & Logic Design 5


b1 b2 b3 b4 b5 b6 b7
Example: Hamming Code for
Digit p1 p2 m1 p3 m2 m3 m4 BCD (m=4)
0 0 0 0 0 0 0 0 p1 = m1  m2  m4 (1, 3, 5, 7)
1 1 1 0 1 0 0 1
p2 = m1  m3  m4 (2, 3, 6, 7)
2 0 1 0 1 0 1 0
p3 = m2  m3  m4 (4, 5, 6, 7)
3 1 0 0 0 0 1 1
4 1 0 0 1 1 0 0
1 2 3 4 5 6 7
5 0 1 0 0 1 0 1
p3 0 0 0 1 1 1 1
6 1 1 0 0 1 1 0
7 0 0 0 1 1 1 1 p2 0 1 1 0 0 1 1

8 1 1 1 0 0 0 0 p1 1 0 1 0 1 0 1
9 0 0 1 1 0 0 1

Switching Circuits & Logic Design 6


How to correct errors?
• Calculate the three check bits:
c1 = b1  b3  b5  b7
c2 = b2  b3  b6  b7
c3 = b4  b5  b6  b7
• If c3c2c1 = 000, there is no error.
• Else, the bit position of the error is given by c3c2c1.

Switching Circuits & Logic Design 7


An Exercise
• Design a Hamming code for m = 5.
• For 2k ≥ m + k + 1, we get k = 4.
• The bit assignments are carried out as follows:

1 2 3 4 5 6 7 8 9
b1 b2 b3 b4 b5 b6 b7 b8 b9 p4 0 0 0 0 0 0 0 1 1
p1 p2 m1 p3 m2 m3 m4 p4 m5 p3 0 0 0 1 1 1 1 0 0

p2 0 1 1 0 0 1 1 0 0

p1 1 0 1 0 1 0 1 0 1

Switching Circuits & Logic Design 8


END OF LECTURE 06

Switching Circuits & Logic Design 9


Lecture 07: Logic Gates

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Introduction
• Digital circuits are built using basic building blocks called logic gates.
– NOT gate, AND gate, OR gate, NAND gate, NOR gate, EXOR gate, etc.
• Integrated circuits or chips contain a large number of such gates.
– Small Scale Integration (SSI) < 12 gates/chip
– Medium Scale Integration (MSI) < 100 gates/chip
– Large Scale Integration (LSI) 1000’s gates/chip
– Very Large Scale Integration (VLSI) 104 gates/chip
– VLSI as of today > 108 gates/chip

Switching Circuits & Logic Design 2


Moore’s Law
• Refers to an observation made by Intel co-founder Gordon Moore in 1965. He
noticed that the number of transistors per square inch on integrated circuits
had doubled every year since their invention.
• Moore's law predicts that this trend will continue into the foreseeable future.
• Although the pace has slowed, the number of transistors per square inch has
since doubled approximately every 18 months. This is used as the current
definition of Moore's law.

Switching Circuits & Logic Design 3


Switching Circuits & Logic Design 4
Binary Logic
• Digital logic gates typically operate on binary logic.
– Two distinct values in binary logic, denoted by 0 and 1.
• Why binary logic?
– It is easy to design electronic circuits with two distinct states.
– Examples:
• An electronic switch is either open, or closed.
• The voltage at a line is either low, or high.
• Current in a line is either flowing, or not flowing.
• Resistance value is either high, or low.
• … and so on

Switching Circuits & Logic Design 5


Basic Logic Gates
• NOT gate
Truth Table
– A single input A, and an output A’.
A A’
• Behavior can be expressed by a truth
0 1
table, which shows all possible input
combinations and the corresponding 1 0
output value.

A A’

Switching Circuits & Logic Design 6


• AND gate
Truth Table
– For two inputs (say, A and B), the
output will be 1 if both the inputs A B A.B
are at 1; will be 0 otherwise. 0 0 0
– AND operation denoted as A.B 0 1 0
– Definition can be extended to any 1 0 0
number of inputs. 1 1 1

A
A.B
B

Switching Circuits & Logic Design 7


• OR gate
Truth Table
– For two inputs (say, A and B), the
output will be 1 if at least one of the A B A+B
inputs are at 1; will be 0 otherwise. 0 0 0
– OR operation denoted as A+B 0 1 1
– Definition can be extended to any 1 0 1
number of inputs. 1 1 1

A
A+B
B

Switching Circuits & Logic Design 8


• NAND gate
Truth Table
– For two inputs (say, A and B), the
output will be 1 if at least one of the A B (A.B)’
inputs are at 0; will be 0 otherwise. 0 0 1
– NAND operation denoted as (A.B)’ 0 1 1
– Definition can be extended to any 1 0 1
number of inputs. 1 1 0

A
(A.B)’
B

Switching Circuits & Logic Design 9


• NOR gate
Truth Table
– For two inputs (say, A and B), the
output will be 1 if both the inputs A B (A+B)’
are at 0; will be 0 otherwise. 0 0 1
– NOR operation denoted as (A+B)’ 0 1 0
– Definition can be extended to any 1 0 0
number of inputs. 1 1 0

A
(A+B)’
B

Switching Circuits & Logic Design 10


• Exclusive OR (EXOR) gate
Truth Table
– For two inputs (say, A and B), the
output will be 1 if odd number of A B (AB)
inputs are at 1; will be 0 otherwise. 0 0 0
– EXOR operation denoted as AB 0 1 1
– Definition can be extended to any 1 0 1
number of inputs. 1 1 0

A
AB
B

Switching Circuits & Logic Design 11


• Exclusive NOR (EXNOR) gate
Truth Table
– For two inputs (say, A and B), the
output will be 1 if even number of A B (AB)’
inputs are at 1; will be 0 otherwise. 0 0 1
– EXNOR operation denoted as (AB)’ 0 1 0
– Definition can be extended to any 1 0 0
number of inputs. 1 1 1

A
(AB)’
B

Switching Circuits & Logic Design 12


How to Construct these Gates?
• Various logic families exist:
– Diode transistor logic (DTL)
– Transistor transistor logic (TTL)
– Emitter Coupled Logic (ECL)
– Complementary Metal Oxide Semiconductor (CMOS) Logic
• CMOS is almost universally used today.
• Some emerging technologies also exist:
– All-optical implementation of logic
– Memristor based logic
– Quantum dot logic, and many more

Switching Circuits & Logic Design 13


END OF LECTURE 07

Switching Circuits & Logic Design 14


Lecture 08: Logic Families to Implement Gates

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
How to Construct Logic Gates?
• Various logic families exist:
– Diode transistor logic (DTL)
– Transistor transistor logic (TTL)
– Emitter Coupled Logic (ECL)
– Complementary Metal Oxide Semiconductor (CMOS) Logic
• CMOS is almost universally used today.

Switching Circuits & Logic Design 2


Diode Transistor Logic
• Uses semiconductor diodes and bipolar transistors, along with resistances.

2-input AND gate 2-input NAND gate

Switching Circuits & Logic Design 3


Transistor Transistor Logic

2-input NOR gate 2-input NAND gate

Switching Circuits & Logic Design 4


Basic Concepts of Switch Based Circuits
• They rely on the operation of tiny switches, which can be in one of two states.
– open or closed, ON or OFF, voltage or no voltage, etc.

Switch open:
• No current flows.
• Light is OFF.
Switch closed:
• Current flows.
V
• Light is ON.

Switching Circuits & Logic Design 5


Digital Voltage Ranges and Noise Margin
• A range of voltages is treated as logic 0, while another range of voltages is
treated as logic 0.
– The exact range of voltages depends on the implementation technology.
– For reliable operation of circuits, there must be considerable gap between the two
ranges, called noise margin.
• Example for Transistor Transistor Logic (TTL) family:

Digital Value 0 1
Noise Margin

Analog Value 0V 0.8 V 2.0 V 5V

Switching Circuits & Logic Design 6


n-type MOS Transistor
• When Gate has positive voltage, there is low resistance between source and
drain (points #1 and #2) – switch closed.
• When Gate has zero voltage, there is high resistance between source and drain
(points #1 and #2) – switch open.

Gate = 1 Gate = 0

Switching Circuits & Logic Design 7


p-type MOS Transistor
• When Gate has positive voltage, there is high resistance between source and
drain (points #1 and #2) – switch open.
• When Gate has zero voltage, there is low resistance between source and drain
(points #1 and #2) – switch closed.

Gate = 0 Gate = 1

Switching Circuits & Logic Design 8


Complementary MOS (CMOS) NOT Gate

In Out
0 1
1 0

Switching Circuits & Logic Design 9


CMOS NAND Gate

A B Out
0 0 1
0 1 1
1 0 1
1 1 0

Switching Circuits & Logic Design 10


CMOS NOR Gate

C D Out
0 0 1
0 1 0
1 0 0
1 1 0

Switching Circuits & Logic Design 11


CMOS AND Gate
• Requires composition: a NAND gate followed by a NOT gate.

A B Out
0 0 0
0 1 0
1 0 0
1 1 1

Switching Circuits & Logic Design 12


CMOS OR Gate
• Requires composition: a NOR gate followed by a NOT gate.

C D Out
0 0 0
0 1 1
1 0 1
1 1 1

Switching Circuits & Logic Design 13


END OF LECTURE 08

Switching Circuits & Logic Design 14


Lecture 09: Emerging Technologies (Part 1)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Building Multiplexers using CMOS
• Multiplexers are more complex switches.

4-to-1 multiplexer:
• If S0 = 0 and S1 = 0, then Z = A
2-to-1 multiplexer:
• If S0 = 1 and S1 = 0, then Z = B
• If S0 = 0, then Z = A • If S0 = 0 and S1 = 1, then Z = C
• If S0 = 1, then Z = B • If S0 = 1 and S1 = 1, then Z = D

Switching Circuits & Logic Design 2


• How to build multiplexers using CMOS switches?
– Provide parallel paths from each input to the output.
– Ensure that depending on the values on the select lines, exactly one of the paths is
ON and all others are OFF.
– The input corresponding to the ON path is selected.
• A good CMOS switch is designed by connecting an nMOS and a pMOS
transistor in parallel.
– Called a transmission gate.

Switching Circuits & Logic Design 3


A 2-to-1
multiplexer

MUX

Schematic Switch-level Model

Switching Circuits & Logic Design 4


• A 4-to-1 multiplexer can be designed in a similar way.

Switching Circuits & Logic Design 5


All-Optical Implementation of Logic Gates
• All computations are carried out using light, using various devices that can
manipulate light.
– Interferometers, beam splitter, optical coupler, etc.
• Presence of light can be used to denote logic 1, while absence of light can be
used to denote logic 0.
• We shall briefly discuss one such all-optical technology.
– Based on Mach-Zehnder Interferometer (MZI) switches.

Switching Circuits & Logic Design 6


What is Mach Zehnder Interferometer?
• It is a device that works on the basis of relative phase shift variations between
two collimated beams derived by splitting light from a single source.

Switching Circuits & Logic Design 7


Building Logic using Optical Switches
• Convention: Presence of light – logic 1, Absence of light – logic 0

Incoming Bar Port


Signal (A) SOA-1 (A.B)

C-1 C-1
Control Cross Port
Signal (A) SOA-2 (A.B’)

Switching Circuits & Logic Design 8


• Building logic gates using MZI switches.
– For inputs A and B, the MZI switch produces two outputs A.B and A.B’
– We can directly realize the AND function.
– If we apply a constant 1 to A, the second output becomes B’. That is, we can also
realize the NOT function.
• We shall see later that {AND, NOT} forms a functionally complete set.
– Any logic circuit can be built using AND and NOT gates only.
• Therefore, by connecting MZI switches we can realize any circuit functionality.

Switching Circuits & Logic Design 9


• Advantages of all-optical implementation:
– High speed.
– Low power consumption during computation.
– All-optical data communication is becoming popular; no need for electrical-to-
optical and optical-to-electrical conversions.
• Some of the disadvantages / challenges:
– Although MZI switches can be fabricated, they are still quite large as compared to
MOS switches.
– Cascading many MZI switches is not easy; light intensity tends to degrade.
– Circuitry to drive the switches consume more power.

Switching Circuits & Logic Design 10


END OF LECTURE 09

Switching Circuits & Logic Design 11


Lecture 10: Emerging Technologies (Part 2)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Memristor: An Emerging Technology
• In 1971, Leon Chua predicted the
Resistor Current
existence of a fourth fundamental Voltage
(v) v = Ri (i)
passive circuit element called
Memristor. Capacitor v = dΦ/dt Inductor
– Memristor = Memory + Resistor q = Cv i = dq/dt Φ=
– Resistance value changes in Li
Φ=
response to applied voltage. Charge Flux
Mq (Φ)
(q) Memristor
– Can memorize its last resistance
value even when the voltage is
withdrawn.

Switching Circuits & Logic Design 2


How Memristor Works?
• In 2008, a team at HP Labs successfully fabricated a memristor.
• They used a material with two regions between two platinum electrodes.
– A region of TiO2-x (e.g. Ti4O7) with free oxygen vacancies. (Low Resistance)
– A region of pure TiO2. this region is highly resistive. (High Resistance)
• The boundary between the two regions moves in response to the voltage
applied across the device.
Pt TiO2-x TiO2 Pt 3 nm x 3 nm

10-12 nm

Switching Circuits & Logic Design 3


Resistance Switching in Memristors
• The voltage-current characteristics
exhibit a pinched hysteresis loop.
• Two distinct resistive regions exist on
the curve (RON and ROFF).
• Possible to switch from RON to ROFF, or
from ROFF and RON by applying a RON
suitable voltage.
• This property makes it useful for ROFF
storage as well as logic design
applications.

Switching Circuits & Logic Design 4


Some Properties of Memristors
• Very small in size.
• Very low power consumption, and non-volatile property.
• Can be laid out on a crossbar structure in a very compact way.
• Applications:
– Implementing non-volatile memory systems (Resistive RAM).
– Modeling neural networks / neuromorphic computing.
– Implementing digital circuits.
• Allows a new computing paradigm called in-memory computing (both memory and
processing carried out in the same hardware unit).

Switching Circuits & Logic Design 5


Implementing Logic Gates using Memristors
• Memristor Aided Logic (MAGIC) design style
– We can implement all basic gates like AND, OR, NOT, NAND and NOR.
– Stateful design style :: inputs are not applied as voltages, but as resistive states in
memristors (High resistance – 0, Low resistance – 1).
– As a matter of convention, the memristor representing the gate output must be
initialized before the computation.
• AND, OR : initialized to 0.
• NOT, NAND, NOR : initialized to 1.
– A voltage Vo of appropriate magnitude is applied for gate evaluation; Vo must be
large enough to enable the output memristor to switch state when required.

Switching Circuits & Logic Design 6


MAGIC Gate Examples

Switching Circuits & Logic Design 7


• IMPLY function implementation using memristors
– Material Implication function: A  B = A’ + B
– Can be implemented using two memristors and one resistor.
– The inputs are applied by initializing the resistive states of the two memristors.
– The output gets stores as resistive state in the second memristor.
• The IMPLY function along with constant 0 is functionally complete.
– We can realize any basic gate, and hence any arbitrary function.

Switching Circuits & Logic Design 8


IMPLY Realization

Switching Circuits & Logic Design 9


END OF LECTURE 10

Switching Circuits & Logic Design 10


Lecture 11: SWITCHING ALGEBRA

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Basic Concepts
• Switching Algebra:
– An algebraic system defined on the set {0, 1}, with two binary operations AND and
OR, and one unary operation NOT.
– AND operation, also called logical product, is denoted by ‘.’ or ‘∧’
– OR operation, also called logical sum, is denoted by ‘+’ or ‘∨’
– NOT operation, also called complement, is denoted by single-quote or ‘~’
• Switching Variables:
– Two-valued variables that can take on two distinct values 0 and 1.
• Switching Expressions:
– An expression consisting of switching variables, constants and operators.

Switching Circuits & Logic Design 2


• Given a switching expression, how to prove it?
a) By verifying the expression for all possible values of the variables.
• Called truth table verification, or perfect induction.
b) By using algebraic manipulation using some rules.
• We first show some basic laws or rules of switching algebra, and use perfect
induction to verify them.
– Let x, y, z denote switching variables.

Switching Circuits & Logic Design 3


Basic Laws of Switching Algebra
• Basic identities: • Commutative Law:
x+1=1 x+y=y+x
x+0=0 x.y=y.x
x.1=x • Complementation Law:
x.0=0 x + x’ = 1
• Idempotent Law: x . x’ = 0
x+x=x • Associative Law:
x.x=x (x + y) + z = x + (y + z)
(x . y) . z = x . (y . z)

Switching Circuits & Logic Design 4


Basic Laws of Switching Algebra (contd.)
• Distributive Law:
x . (y + z) = x . y + y . z
x + (y . z) = (x + y) . (x + z)
• Absorption Law:
x + (x . y) = x
x . (x + y) = x
• Useful Law:
x + (x’ . y) = x + y
x . (x’ + y) = x . y

Switching Circuits & Logic Design 5


Basic Laws of Switching Algebra (contd.)
• Consensus Theorem:
x y + x’ z + y z = x y + x’ z
(x + y) (x’ + z) (y + z) = (x + y) (x’ + z)
• Involution:
(x’)’ = x

Switching Circuits & Logic Design 6


Function Minimization
• Given a switching expression, we can simplify it by using the basic laws of
switching algebra.
– Reduce the number of terms.
– Reduce the number of literals.
• There are other rules of transforming switching expressions, which shall be
discussed later.
– De Morgan’s theorem, for example.

Switching Circuits & Logic Design 7


END OF LECTURE 11

Switching Circuits & Logic Design 8


Lecture 12: ALGEBRAIC MANIPULATION

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Principle of Duality
• Most of the rules discussed in the last lecture appear in pairs.
• Principle of duality states that:
– A switching expression T2 can be obtained from a given switching expression T1 by
interchanging the operations AND & OR, and constants 0 & 1.
– T1 and T2 are said to be dual of each other.
• Examples:
– x + 1 = 1 is the dual of x . 0 = 0
– x + x.y = x is the dual of x . (x + y) = x
– x + x’.y = x + y is the dual of x . (x’ + y) = x . y

Switching Circuits & Logic Design 2


Simplification of Switching Expressions
• Important point to note:
x + y = x + z does not imply y = z
• A counterexample: x = 1, y = 0, z = 1
• What is the reason?
– Inverse operations are not defined in switching algebra; hence cancellations are not
allowed.

Switching Circuits & Logic Design 3


Simplification Example 1
• F = A.B’ + A.B + B.C

Switching Circuits & Logic Design 4


Simplification Example 2
• F = A’.B.C + A.B’.C + A.B.C’ + ABC

Switching Circuits & Logic Design 5


Simplification Example 3
• F = A’.B + B’.C’ + A.B + B’.C

Switching Circuits & Logic Design 6


De Morgan’s Theorems
• For two variables x and y, De Morgan’s theorems state that:
(x + y)’ = x’ . y’
(x . y)’ = x’ + y’
• Can be easily extended to any number of variables.
x y (x + y)’ x’ . y’ (x.y)’ x’ + y’
0 0 1 1 1 1
0 1 0 0 1 1
1 0 0 0 1 1
1 1 0 0 0 0

Switching Circuits & Logic Design 7


Using De Morgan’s Theorem: Example 1
• F = (A + B)’ . (A’ + B’)

Switching Circuits & Logic Design 8


Using De Morgan’s Theorem: Example 2
• F = (A . B’ + A’ . B)’

Switching Circuits & Logic Design 9


Using De Morgan’s Theorem: Example 3
• F = (A B C’ + D)’ + (A B’ + B C’)’

Switching Circuits & Logic Design 10


Using De Morgan’s Theorem: Example 4
• F = (A B C)’ (A + C) (A + C’)

Switching Circuits & Logic Design 11


Using De Morgan’s Theorem: Example 5
• f (w, x, y) = w x’ y + w x + w y’ + w x y’

Switching Circuits & Logic Design 12


Mapping Problems to Switching Expressions
• A safe has five locks v, w, x, y and z, all of which must be unlocked for the safe to be
open. The keys to the locks are distributed among five security officers as follows:
– Officer A has keys for locks v and x
– Officer B has keys for locks v and y
– Officer C has keys for locks w and y
– Officer D has keys for locks x and z
– Officer E has keys for locks v and z
Find all combinations of security officers that can open the safe.

Switching Circuits & Logic Design 13


Another Problem
• Five soldiers A, B, C, D and E volunteer to perform a mission where the following
conditions must be satisfied:
– Either A or B or both must go.
– Either C or E, but not both, must go.
– Either both A and C go, or neither goes.
– If D goes, then E must also go.
– If B goes, then A and D must also go.

Switching Circuits & Logic Design 14


END OF LECTURE 12

Switching Circuits & Logic Design 15


Lecture 13: PROPERTIES OF SWITCHING FUNCTIONS

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Minterm and Maxterm
• For a switching function, a literal is defined as a variable in uncomplemented
or complemented form.
– Example: x, x’, y, y’, etc.
• Consider an n-variable switching function f (x1, x2, …, xn).
– A product term (that is, an AND operation) of all the n literals is called a minterm.
– A sum term (that is, an OR operation) of all the n literals is called a maxterm.
• Consider a 3-variable function f (A, B, C).
– Examples of minterm: A’.B’.C’, A.B’.C, A.B.C, etc.
– Examples of maxterm: (A + B’ + C’), (A’ + B’ + C’), (A + B + C), etc.

Switching Circuits & Logic Design 2


• Properties of minterms and maxterms:
– A minterm assumes value 1 for exactly one combination of variables.
– A maxterm assumes the value 0 for exactly one combination of variables.
• Example:

Switching Circuits & Logic Design 3


• For a given switching function, and for given values of the input variables,
– All the minterms that have the value 1 are called true minterms.
– All the minterms that have the value 0 are called false minterms.
– All the maxterms that have the value 1 are called true maxterms.
– All the maxterms that have the value 0 are called false maxterms.

• Example:
– f (x, y, z) = x’.y + x.y.z  True minterms are: x’.y.z’, x’.y.z, x.y.z
– f (x, y, z) = (x + y) . (y +z)  True maxterms are: x+y+z, x+y+z’, x’+y+z

Switching Circuits & Logic Design 4


A Full Adder Example
• A full adder adds three bits A, B, C, and A B C S Co
generates a sum S and a carry Co. 0 0 0 0 0
S = A’.B’.C + A’.B.C’ + A.B’.C + A.B.C 0 0 1 1 0
Co = A.B + B.C + C.A 0 1 0 1 0

• For the sum function S, true minterms 0 1 1 0 1


are: A’.B’.C, A’.B.C’, A.B’.C, A.B.C 1 0 0 1 0

• For the carry function Co, true minterms 1 0 1 0 1


are: A’.B.C, A.B’.C, A.B.C’, A.B.C 1 1 0 0 1
1 1 1 1 1

Switching Circuits & Logic Design 5


Unate Functions
• A switching function is said to be unate if no variable appears in both
complemented and uncomplemented forms in the minimized expression for
the function.
• A switching function is said to be positive unate if all variables appear in only
uncomplemented form in the minimized expression for the function.
• A switching function is said to be negative unate if all variables appear in only
uncomplemented form in the minimized expression for the function.
• If a function is not unate, it is said to be non-unate.
– For the full adder, Co is positive unate, but S is non-unate.

Switching Circuits & Logic Design 6


Canonical Form of Representing Functions
• A canonical form is a unique representation of a function.

• We can derive two canonical representations directly from the truth table:
a) Canonical sum-of-products (also called disjunctive normal form)
b) Canonical product-of-sums (also called conjunctive normal form)

Switching Circuits & Logic Design 7


Canonical Sum-of-Products Form
• From the truth table, identify all the true minterms.
– Corresponding to rows for which the output function is 1.
• Take the sum of all the minterms.
• Example for the full adder:
S = A’.B’.C + A’.B.C’ + A.B’.C’ + A.B.C
Co = A.B.C’ + A’.B.C + A.B’.C + A.B.C
• We can write down the canonical s-o-p expressions in a compact way by
noting down the decimal equivalents of the input combinations:
S = Σ (1, 2, 4, 7)
Co = Σ (3, 5, 6, 7)

Switching Circuits & Logic Design 8


A B C S Co
0 0 0 0 0 S = Σ (1, 2, 4, 7)
Co = Σ (3, 5, 6, 7)
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

Switching Circuits & Logic Design 9


Canonical Product-of-Sums Form
• From the truth table, identify all the false maxterms.
– Corresponding to rows for which the output function is 1.
– For each false maxterm, form a sum term where a variable will appear in
uncomplemented (complemented) form if it has value 0 (1) in the row.
• Example for the full adder:
S = (A + B + C) . (A + B’ + C’) . (A’ + B + C’) . (A’ + B’ + C)
Co = (A + B + C) . (A + B + C’) . (A + B’ + C) . (A’ + B + C)
• We can write down the canonical s-o-p expressions in a compact way by noting
down the decimal equivalents of the input combinations:
S = Π (0, 3, 5, 6)
Co = Π (0, 1, 2, 4)

Switching Circuits & Logic Design 10


A B C S Co
0 0 0 0 0 S = Π (0, 3, 5, 6)
0 0 1 1 0 Co = Π (0, 1, 2, 4)
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

Switching Circuits & Logic Design 11


END OF LECTURE 13

Switching Circuits & Logic Design 12


Lecture 14: Obtaining Canonical Representations of
Functions
PROF. INDRANIL SENGUPTA
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Algebraic Procedure to Obtain Canonical s-o-p
a) Examine each term of a given sum-of-products expression; if it is not a minterm, go to
the next step.
b) For all missing variable xi, multiply the term by (xi’ + xi).
c) Multiply out all products and eliminate redundant product terms.

Example: f (a, b, c) = a.b’ + b + a.b.c


= a.b’ (c + c’) + b (a + a’)(c + c’) + a.b.c
= a.b’.c + a.b’.c’ + a.b.c + a.b.c’ + a’.b.c + a’.b.c’ + a.b.c
= a.b’.c + a.b’.c’ + a.b.c + a.b.c’ + a’.b.c + a’.b.c’

Switching Circuits & Logic Design 2


Algebraic Procedure to Obtain Canonical p-o-s
a) Examine each term of a given product-of-sums expression; if it is not a maxterm, go to
the next step.
b) For all missing variable xi, add the term xi’ xi
c) Obtain the sum terms, and eliminate redundant terms.

Example: f (a, b, c) = a’ (b’ + c)


= (a’ + bb’ + cc’) (b’ + c + aa’)
= (a’ + b + c)(a’ + b + c’)(a’ + b’ + c)(a’ + b’ + c’)(a + b’ + c)(a’ + b’ + c)
= (a’ + b + c)(a’ + b + c’)(a’ + b’ + c)(a’ + b’ + c’)(a + b’ + c)

Switching Circuits & Logic Design 3


Transforming One Form to Another
• Double complement the given function and apply De Morgan’s theorem.
• Rule to be followed:
– Complement of a sum of true minterms is the same as the sum of the false
minterms.
• Example:
f (a, b, c) = a’.b’.c’ + a’.b’.c + a’.b.c’ + a.b.c’ + a.b.c
f = (f’)’ = [(a’.b’.c’ + a’.b’.c + a’.b.c’ + a.b.c’ + a.b.c)’]’
= [a’.b.c + a.b.c’ + a.b’.c]’ (Consider remaining minterms)
= (a + b’ + c’)(a’ + b’ + c)(a’ + b + c)

Switching Circuits & Logic Design 4


Canonical s-o-p from the Truth Table
• Consider rows of the truth table for which the output is 1.
• For each such row, form a minterm.
– If the input variable is 0, the corresponding variable will appear in complemented
form in the minterm.
– If the input variable is 1, the corresponding variable will appear in uncomplemented
form in the minterm.
• Take the sum of all such minterms.
• We get the canonical sum-of-products expression.

Switching Circuits & Logic Design 5


Example
A B C S Co
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

Switching Circuits & Logic Design 6


Converting to Gate Level Realization

Switching Circuits & Logic Design 7


Canonical p-o-s from the Truth Table
• Consider rows of the truth table for which the output is 0.
• For each such row, form a maxterm.
– If the input variable is 0, the corresponding variable will appear in uncomplemented
form in the maxterm.
– If the input variable is 1, the corresponding variable will appear in complemented
form in the maxterm.
• Take the product of all such maxterms.
• We get the canonical product-of-sums expression.

Switching Circuits & Logic Design 8


Example
A B C S Co
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

Switching Circuits & Logic Design 9


Converting to Gate Level Realization

Switching Circuits & Logic Design 10


END OF LECTURE 14

Switching Circuits & Logic Design 11


Lecture 15: Functional Completeness

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Basic Concept
• In switching algebra, the basic operations are NOT, AND and OR.
– Any switching expression can be realized using these three operators.
– We say that the set {NOT, AND, OR} is functionally complete.
• Example: Consider the switching function f = A’.B + B.C’.D
– There are only NOT, AND and OR operations.
– We can implement the circuit using NOT, AND and OR gates only.
• Other set of gates can also be shown to be functionally complete.
– Some examples will follow.

Switching Circuits & Logic Design 2


{NAND} is Functionally Complete
• It can be shown that NAND is a universal gate, i.e. it is functionally complete.
• How to prove that?
– We can show that we can realize NOT, AND and OR functions using NAND only.
• The NAND function is:
– NAND (A, B) = (A . B)’
• How to realize basic gates?
– NOT :: A’ = (A . A)’
– AND :: A.B = ((A.B)’)’ = ((A.B)’ . (A.B)’)’
– OR :: A + B = (A’ . B’)’ = ( (A . A)’ . (B . B)’ )’

Switching Circuits & Logic Design 3


{NOR} is Functionally Complete
• It can be shown that NORis a universal gate, i.e. it is functionally complete.
• How to prove that?
– We can show that we can realize NOT, AND and OR functions using NOR only.
• The NOR function is:
– NOR (A, B) = (A + B)’
• How to realize basic gates?
– NOT :: A’ = (A + A)’
– AND :: A.B = (A’ + B’)’ = ((A + A)’ + (B + B)’)’
– OR :: A + B = ((A + B)’)’ = ( (A + B)’ + (A + B)’ )’

Switching Circuits & Logic Design 4


{AND, NOT} is Functionally Complete
• We have already shown that NAND is functionally complete.
• NAND can be realized as an AND followed by NOT.
– Hence {AND, NOT} is also functionally complete.

Switching Circuits & Logic Design 5


{OR, NOT} is Functionally Complete
• We have already shown that NOR is functionally complete.
• NOR can be realized as an OR followed by NOT.
– Hence {OR, NOT} is also functionally complete.

Switching Circuits & Logic Design 6


{AND, EXOR, 1} is Functionally Complete
• AND and EXOR gates are also functionally complete, but we also need the
constant value 1.
• Recall that EXOR (A, B) = A’.B + A.B’
• How to realize basic bates?
– NOT :: A’ = EXOR (A, 1) = A’.1 + A.0 = A’ + 0 = A’
– And we already know that {NOT, AND} is a functionally complete set.

Switching Circuits & Logic Design 7


{OR, EXOR, 1} is Functionally Complete
• OR and EXOR gates are also functionally complete, but we also need the
constant value 1.
• Recall that EXOR (A, B) = A’.B + A.B’
• How to realize basic bates?
– NOT :: A’ = EXOR (A, 1) = A’.1 + A.0 = A’ + 0 = A’
– And we already know that {NOT, OR} is a functionally complete set.

Switching Circuits & Logic Design 8


{2x1 MUX, 0, 1} is Functionally Complete
• A 2-to-1 multiplexer has two inputs A and B, a select input S, and one output F.
• It realizes the function: F = MUX21 (A, B, S) = A.S’ + B.S
– If S = 0, we have F = A; and if S = 1, we have F = B.
• How to realize other gates?
– NOT :: A’ = MUX21 (1, 0, A) = 1.A’ + 0.A = A’ + 0 = A’
– AND :: A.B = MUX21 (A, 0, B’) = A.B + 0.B’ = A.B
– Since NOT and AND can be realized, it is functionally complete.

Switching Circuits & Logic Design 9


Two-level AND-OR is Equivalent to NAND-NAND
• Any two-level AND-OR realization can be converted to an equivalent NAND-
NAND realization by replacing all the AND and OR gates by NAND gates.
• Why is this possible?
– Because of De Morgan’s Law :: A.B + C.D = ( (A.B)’ . (C.D)’ )’

Switching Circuits & Logic Design 10


Two-level OR-AND is Equivalent to NOR-NOR
• Any two-level OR-AND realization can be converted to an equivalent NOR-NOR
realization by replacing all the AND and OR gates by NOR gates.
• Why is this possible?
– Because of De Morgan’s Law :: (A + B) . (C + D) = ( (A + B)’ + (C + D)’ )’

Switching Circuits & Logic Design 11


Realize AND-OR-NOT Circuits using NAND
• We have seen earlier how two-level AND-OR circuits can be transformed to
circuits using NAND gates only.
• By repeated use of De Morgan’s law and the basic laws of switching algebra,
we can transform any multilevel AND-OR-NOT circuit using NAND gates only.
– We shall show some examples.
– Similar approach can be used for realizing circuits using NOR gates.
• Some examples:

Switching Circuits & Logic Design 12


END OF LECTURE 15

Switching Circuits & Logic Design 13


Lecture 16: Minimization using Karnaugh Maps (Part 1)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
What are Karnaugh Maps?
• A graphical method for representation and minimization of functions.
– Provides an alternate way of simplifying switching functions.
– Instead of using algebraic simplification techniques, we use a pictorial representation
of the function, called Karnaugh map or K‐map.
• For an n‐variable function, there are 2n cells in the map (one for each minterm).
– Adjacent 2 cells differ in only 1 variable.
– Adjacent 22 = 4 cells differ in 2 variables.
– Adjacent 2m cells differ in m variables.
• We try to group 2m adjacent cells corresponding to true minterms.
– Try to make the cubes (groups) bigger, ensure all true minterms are covered.

Switching Circuits & Logic Design 2


• How are the cells in a K‐map labelled?
– Such that two adjacent cells differ in the value of only one variable.
– Helps in combining cells into cubes:
A.B.C + A.B’.C = A
A.B’.C’ + A.B’.C + A.B.C’ + A.B.C = A
• Drawback:
– Since it is a pictorial approach, it is difficult to visualize functions with more than 5
or 6 variables.
– We shall give examples with up to 4 variables.

Switching Circuits & Logic Design 3


Basic Approach
1. Fill up the cells of the K‐map with true minterms of the function.
2. Group the true minterms of the function into cubes such that:
– The size of the cubes are maximized.
– Every true minterms is covered by at least one cube.
3. Write down the minimized sum‐of‐products expression for the function by
creating one product term out of every cube that has been selected.

Switching Circuits & Logic Design 4


3‐variable Karnaugh Map

BC BC
A 00 01 11 10 A 00 01 11 10
0 0 0 1 3 2

1 1 4 5 7 6

Switching Circuits & Logic Design 5


Example 1

BC
A 00 01 11 10
0 1 1

1 1 1

Switching Circuits & Logic Design 6


Example 2

BC
A 00 01 11 10
0 1 1 1 1

1 1

Switching Circuits & Logic Design 7


Example 3

BC
A 00 01 11 10
0 1 1 1 1

1 1 1

Switching Circuits & Logic Design 8


Example 4

BC
A 00 01 11 10
0 1 1 1

1 1 1 1

Switching Circuits & Logic Design 9


Sum and Carry of Full Adder
Sum =  (1, 2, 4, 7) Carry =  (3, 5, 6, 7)

BC BC
A 00 01 11 10 A 00 01 11 10
0 1 1 0 1

1 1 1 1 1 1 1

Switching Circuits & Logic Design 10


END OF LECTURE 16

Switching Circuits & Logic Design 11


Lecture 17: Minimization using Karnaugh Maps (Part 2)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Introduction
• We now show how the K‐map can be extended to four variables.
– It will be a 4 x 4 cell array.
• The basic concept of labeling the variables remains the same:
– Adjacent cells differ in the value of a single variable.
– Top‐bottom and left‐right cells are also considered adjacent.
– The four corner cells are considered adjacent to each other.

Switching Circuits & Logic Design 2


4‐variable Karnaugh Map

CD CD
AB 00 01 11 10 AB 00 01 11 10
00 00 0 1 3 2
01 01 4 5 7 6
11 11 12 13 15 14

10 10 8 9 11 10

Switching Circuits & Logic Design 3


Example 1

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

10 1

Switching Circuits & Logic Design 4


Example 2

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

10 1

Switching Circuits & Logic Design 5


Example 3

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

10 1 1

Switching Circuits & Logic Design 6


Example 4

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

10 1 1

Switching Circuits & Logic Design 7


Example 5

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

10 1

Switching Circuits & Logic Design 8


Example 6: A 2‐bit adder

A1
A0 S2
2‐bit Adder S1
B1 S0
B0

Switching Circuits & Logic Design 9


A1 A0 B1 B0 S2 S1 S0
0 0 0 0 0 0 0 Example: 2‐bit adder – S2
0 0 0 1 0 0 1
B1B0
0 0 1 0 0 1 0
A1A0 00 01 11 10
0 0 1 1 0 1 1
0 1 0 0 0 0 1
00
0 1 0 1 0 1 0
01 1
0 1 1 0 0 1 1
0 1 1 1 1 0 0 11 1 1 1
1 0 0 0 0 1 0
1 0 0 1 0 1 1 10 1 1
1 0 1 0 1 0 0
1 0 1 1 1 0 1
1 1 0 0 0 1 1
1 1 0 1 1 0 0
1 1 1 0 1 0 1
1 1 1 1 1 1 0 Switching Circuits & Logic Design 10
A1 A0 B1 B0 S2 S1 S0
0 0 0 0 0 0 0 Example: 2‐bit adder – S1
0 0 0 1 0 0 1
B1B0
0 0 1 0 0 1 0 A1A0 00 01 11 10
0 0 1 1 0 1 1
00 1 1
0 1 0 0 0 0 1
0 1 0 1 0 1 0 01 1 1
0 1 1 0 0 1 1
0 1 1 1 1 0 0 11 1 1
1 0 0 0 0 1 0
1 0 0 1 0 1 1
10 1 1
1 0 1 0 1 0 0
1 0 1 1 1 0 1
1 1 0 0 0 1 1
1 1 0 1 1 0 0
1 1 1 0 1 0 1
1 1 1 1 1 1 0 Switching Circuits & Logic Design 11
A1 A0 B1 B0 S2 S1 S0
0 0 0 0 0 0 0 Example: 2‐bit adder – S0
0 0 0 1 0 0 1
B1B0
0 0 1 0 0 1 0 A1A0 00 01 11 10
0 0 1 1 0 1 1
00 1 1
0 1 0 0 0 0 1
0 1 0 1 0 1 0 01 1 1
0 1 1 0 0 1 1
0 1 1 1 1 0 0 11 1 1
1 0 0 0 0 1 0
1 0 0 1 0 1 1
10 1 1
1 0 1 0 1 0 0
1 0 1 1 1 0 1
1 1 0 0 0 1 1
1 1 0 1 1 0 0
1 1 1 0 1 0 1
1 1 1 1 1 1 0 Switching Circuits & Logic Design 12
END OF LECTURE 17

Switching Circuits & Logic Design 13


Lecture 18: Minimization using Karnaugh Maps (Part 3)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Handling Don’t care Inputs
• There exists functions for which some of the inputs are treated as don’t cares,
and the corresponding output values do not matter.
– Such inputs will never appear.
• The don’t care minterms are labeled as “X” in the K‐map.
– When creating the cubes, we can include cells marked as “X” along with those
marked as “1” to make the cubes larger.
– But it is not necessary to cover all the cells marked by “X”.

Switching Circuits & Logic Design 2


F =  (1, 5, 9, 11, 12, 13) + Φ (3, 10, 14, 15)

CD
AB 00 01 11 10
00 1 X
01 1
11 1 1 X X

10 1 1 X

Switching Circuits & Logic Design 3


F =  (0, 7, 10) + Φ (2, 5, 8, 15)

CD
AB 00 01 11 10
00 1 X
01 X 1
11 X

10 X 1

Switching Circuits & Logic Design 4


Some Definitions
• Implicant
– Given a function F of n variables, a minterm P is an implicant of F if and only if, for
all combinations of the n variables for which P = 1, F is also 1.
• Prime Implicant
– An implicant is said to be a prime implicant if after deleting any literal from it, the
resulting product term is no longer an implicant.
– With respect to K‐map, it is a cube that is not completely covered by another
implicant representing a larger cube.
– Example: For F = A’.B + A.C + B’.C’ , one prime implicant is A’.B.

Switching Circuits & Logic Design 5


CD
AB 00 01 11 10
00 1 The set of all prime implicants of the function is
{BD, A’C’D’, AB’C’, B’C’D’, AC’D}
01 1 1 1
11 1 1

10 1 1

Switching Circuits & Logic Design 6


• Essential Prime Implicant
– A prime implicant of a function F is said to be an essential prime implicant if it
covers at least one minterm of F that is not covered by any other prime implicant.
– It is a prime implicant representing a cube in the K‐map, such that at least one cell
of the cube is not covered by any other prime implicant.
CD
AB 00 01 11 10
00 1 1 1 All the prime implicants are essential.

01 1 1
11 1

10 1

Switching Circuits & Logic Design 7


BC
A 00 01 11 10
None of the prime implicants are essential
0 1 1 1
 CYCLIC PRIME IMPLICANT CHART
1 1 1 1

Switching Circuits & Logic Design 8


5‐variable Karnaugh Map

CDE CDE
AB 000 001 011 010 110 111 101 100 AB 000 001 011 010 110 111 101 100

00 00 0 1 3 2 6 7 5 4
01 01 8 9 11 10 14 15 13 12
11 11 24 25 27 26 30 31 29 28

10 10 16 17 19 18 22 23 21 20

Switching Circuits & Logic Design 9


Some Results
1. Every irredundant sum‐of‐products expression equivalent to a function F is a
union of prime implicants of F.

2. The set of all essential prime implicants must be contained in any irredundant
sum‐of‐products expression.

3. Any prime implicant covered by the sum of the essential prime implicants
must not be contained in an irredundant sum‐of‐products expression.

Switching Circuits & Logic Design 10


Determination of Minimal Product‐of‐Sums
• Process is similar to that for sum‐of‐products, with the following
differences:
– Cubes are formed of the 0‐cells (false minterms) instead of the 1‐cells.
– When writing out the expression, a variable corresponding to a 1 is
complemented, while a variable corresponding to a 0 is not
complemented.

Switching Circuits & Logic Design 11


F =  (1, 4, 5, 6, 11, 12, 13, 14, 15) = π (0, 2, 3, 7, 8, 9, 10)
CD CD
AB 00 01 11 10 AB 00 01 11 10
00 1 00 0 0 0
01 1 1 1 01 0
11 1 1 1 1 11

10 1 10 0 0 0

Switching Circuits & Logic Design 12


END OF LECTURE 18

Switching Circuits & Logic Design 13


Lecture 19: Minimization using Tabular Method (Part 1)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Introduction
• The Karnaugh map method of minimization can be used only for functions with
up to 5 or 6 variables.
– Also, difficult to automate on computer.
• For larger functions, a more systematic procedure is required.
– We can use Quine‐McCluskey method (also known as tabular method).
– Suitable for hand computation and can also be automated easily.
• Basic concept remains the same.
– Repeated application of the theorem: A.x + A.x’ = A to all adjacent pair of terms.
– Yields the set of all prime implicants at the end.

Switching Circuits & Logic Design 2


• An example illustrated:
F (A,B,C,D) = A’B’C’D’ + A’B’C’D + AB’C’D’ + AB’C’D
• Combining first two and last two terms, we get
F = A’B’C’ (D + D’) + AB’C’ (D + D’) = A’B’C’ + AB’C’
• Now combining the resulting product terms, we get
F = B’C’ (A + A’) = B’C’
• We get the prime implicant B’C’
• Basically, we can go on combining any pair of product terms that differ in the
value of a single literal.

Switching Circuits & Logic Design 3


The Basic Concept
• Two k‐variable terms can be combined into a single (k‐1)‐variable term, if and
only if they differ in only one literal.
– We use the binary representation of the minterms for convenience.
– Two minterms can be combined if their binary representations differ in only one
position.
– We use the symbol ‘‐’ to indicate the absence of a literal.
• An example:
– A’B’C’D denoted by 0001, AB’C’D denoted by 1001.
– After combining, we get ‐001.

Switching Circuits & Logic Design 4


The Tabular Method :: Identify all Prime Implicants
1. Arrange all the minterms in groups, based on the number of 1’s.
– The number of 1’s in a term is called the index.
2. Compare every term of index i with each term in the group with index (i+1).
– Where possible, merge them using the rule: A.x + A.x’ = A.
– Place a check mark next to every term that has been combined with at least one term.
3. Now compare the terms generated in Step‐2 in the same fashion; generate a
new term by combining two terms that differ by only a single 1 and whose
dashes are in the same position.
– The process continues until no further combinations are possible.
– The remaining unchecked terms are the prime implicants of the function.

Switching Circuits & Logic Design 5


Example 1: F (w,x,y,z) =  (0, 1, 2, 5, 7, 8, 9, 10, 13, 15)
Step (i) Step (ii) Step (iii)
w x y z w x y z w x y z
0 0 0 0 0 0,1 0 0 0 -- 0,1,8,9 -- 0 0 -- A
1 0 0 0 1 0,2 0 0 -- 0 0,2,8,10 -- 0 -- 0 B
2 0 0 1 0 0,8 -- 0 0 0 1,5,9,13 -- -- 0 1 C
8 1 0 0 0 1,5 0 -- 0 1 5,7,13,15 -- 1 -- 1 D
5 0 1 0 1 1,9 -- 0 0 1
9 1 0 0 1 2,10 -- 0 1 0
10 1 0 1 0 8,9 1 0 0 --
7 0 1 1 1 8,10 1 0 -- 0
The set of prime implicants are:
13 1 1 0 1 5,7 0 1 -- 1 {x’y’, x’z’, y’z, xz}
15 1 1 1 1 5,13 -- 1 0 1
9,13 1 -- 0 1
7,15 -- 1 1 1
13,15 1 1 -- 1

Switching Circuits & Logic Design 6


Example 2: F (A,B,C,D) =  (1, 2, 4, 8, 10, 14, 15)

Switching Circuits & Logic Design 7


Example 3: F (A,B,C,D) =  (0, 3, 5, 8, 10, 13) + φ (2, 7, 11)

Switching Circuits & Logic Design 8


The Next Step
• What we have obtained?
– Set of all prime implicants of the function.
– Some are essential, while some are non‐essential.
• What do we need to do now?
– Select a minimal set of prime implicants that covers all the true minterms of the
function.
– Of course, the essential prime implicants must be selected.
• We shall discuss a tabular method of minimization.

Switching Circuits & Logic Design 9


END OF LECTURE 19

Switching Circuits & Logic Design 10


Lecture 20: Minimization using Tabular Method (Part 2)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
What we Discussed Earlier?
• How to generate the set of all prime implicants for a given function?
– Using the systematic procedure of the tabular method.

• What we shall see now?


– How to select the smallest set of prime implicants that cover all the true minterms
of the function.
– We shall again use a tabular method using prime implicant chart.

Switching Circuits & Logic Design 2


Prime Implicant Chart
• It is a tabular data structure, which pictorially depicts the covering relationship
between prime implicants and minterms.
– Useful to select the minimum set of prime implicants.
– Minterms listed along columns, while prime implicants listed along rows.
– A ‘x’ is entered in the table if the corresponding prime implicant covers the
corresponding minterm.
• A row of the table is said to cover all the columns where there are ‘x’.
• If a column has a single ‘x’, the prime implicant corresponding to the row in
which the ‘x’ appears is an essential prime implicant.

Switching Circuits & Logic Design 3


• What do we have to do?
– Select a minimal subset of prime implicants such that each column contains at least
one ‘x’ in the rows corresponding to the selected subset, and the total number of
literals in the prime implicants is as small as possible.

Here, B and D are essential prime


implicants.
In addition, we have to select either
A or C (to cover the minterms 1 & 9).

Switching Circuits & Logic Design 4


• Two minimal expressions are possible for the function:
F = x’z’ + xz + x’y’
F = x’z’ + xz + y’z

Switching Circuits & Logic Design 5


What about Don’t Care Combinations?
• We do not list the don’t care minterms as column headings in the prime
implicant chart.
– Because it is not necessary to cover all of them.
13 15 17 18 19 20 21 23 25 27 29 31
A = vz F(v,w,x,y,z) =  (13,15,17,18,19,20,21,23,25,
B = wxz 27,29,31) + Φ (1,2,12,24)
C = vwx y
D = vw xy Essential prime implicants are A, B and D.
E = vw x y
F = v wxy
Only minterm 18 is not covered, which can be
G = w x yz ensured by including either E or G.
H=wxyz

Switching Circuits & Logic Design 6


An Example
0 1 4 20 22
D
0 1 3 4 7 13 15 19 20 22 23 29 31
E
A = wxz
F
B = xyz
G
C = w yz
H
D = vw xy
I
E = vw xz
F = w xy z (b) Reduced prime implicant chart.
G=vwxz
H=vwyz Condition for selection:
I=vwxy (H+I)(G+I)(F+H)(E+F)(D+E)
(a) Prime implicant chart. = EHI + EFI + DFI + EGH + DFGH

Switching Circuits & Logic Design 7


Another Example

Switching Circuits & Logic Design 8


• Some heuristic rules may be used to simplify the problem.
– A row U of the prime implicant chart dominates row V, if U covers every column
covered by V.
– If U does not have more literals that V, then V can be deleted from the chart.

We can select the prime implicants: A,


B, J, K, C, and E.

Switching Circuits & Logic Design 9


• Another rule for reducing table size:
– A column C1 of the chart dominates column C2 if C1 has an ‘x’ in every row in
which C2 has an ‘x’.
– The dominating column C1 can be deleted.
10 11 18 19 26
C
D
E Columns 11 and 19 can be deleted.
F
G
H
I

(b) Reduced prime implicant chart.

Switching Circuits & Logic Design 10


END OF LECTURE 20

Switching Circuits & Logic Design 11


Lecture 21: Design of Adders (Part 1)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Introduction
• We shall be discussing the design of various commonly used combinational
circuit modules.
• What is a combinational circuit?
– Whose output depends only on the inputs that have been applied, and have no
bearing on the past history of the inputs.
– Common examples:
• Adders and subtractors
• Multiplexer
• Decoder / Demultiplexer
• Encoder, etc.

Switching Circuits & Logic Design 2


Addition of Two Binary Digits (Bits)
• When two bits A and B are added, a sum (S) and carry (C) are generated as per
the following truth table:

Inputs Outputs S = A’.B + A.B’ = A  B


A B S C 0 + 0 = 00 C = A.B
A S
0 + 1 = 01
0 0 0 0 HA
1 + 0 = 01 B C
0 1 1 0 1 + 1 = 10
1 0 1 0 HALF ADDER
1 1 0 1

Switching Circuits & Logic Design 3


Addition of Multi-bit Binary Numbers
0010110 Carry 1111110 Carry
0101011 Number A 0111111 Number A
+ 0001001 Number B + 0000001 Number B
0110100 Sum S 1000000 Sum S

• At every bit position (stage), we require to add 3 bits:


 1 bit for number A
 1 bit for number B WE NEED A FULL ADDER
 1 carry bit coming from the previous stage

Switching Circuits & Logic Design 4


What is a Full Adder?
• A full adder has three inputs and two outputs:
– Inputs: two input bits A and B, the the carry input Cin.
– Outputs: the sum S, and the carry output Cout.
• To add two multi-bit numbers, we can use a cascade of full adders.

A S
B FA
Cin Cout

Switching Circuits & Logic Design 5


Full Adder A S
B FA
Inputs Outputs Cin Cout
A B Cin S Cout
S = A’.B’.Cin + A’.B.Cin’ + A.B’.Cin’ + A.B.Cin
0 0 0 0 0
= A  B  Cin
0 0 1 1 0
0 1 0 1 0 Cout = A’.B.Cin + A.B’.Cin + A.B.Cin’ + A.B.Cin
0 1 1 0 1 = A.B + B.Cin + A.Cin
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

Switching Circuits & Logic Design 6


Gate-Level Implementation of Full Adder

Switching Circuits & Logic Design 7


Designing a Full Adder using Half Adders
A A HALF C
OR Cout
B B ADDER S A HALF C
Cin B ADDER S S

Switching Circuits & Logic Design 8


• Delay of a full adder:
– Assume that the delay of all basic gates
(AND, OR, NAND, NOR, NOT) is δ.
– Delay for Carry = 2δ
– Delay for Sum = 3δ
(AND-OR delay plus one inverter delay)

Switching Circuits & Logic Design 9


Parallel Adder Design
• We shall look at the various designs of n-bit parallel adder.
a) Ripple carry adder
b) Carry look-ahead adder
c) Carry select adder
d) Carry save adder

Switching Circuits & Logic Design 10


END OF LECTURE 21

Switching Circuits & Logic Design 11


Lecture 22: Design of Adders (Part 2)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Parallel Adder Design
• We shall look at the various designs of n-bit parallel adder.
a) Ripple carry adder
b) Carry look-ahead adder
c) Carry select adder
d) Carry save adder

Switching Circuits & Logic Design 2


Ripple Carry Adder
• Cascade n full adders to create a n-bit parallel adder.
• Carry output from stage-i propagates as the carry input to stage-(i+1).
• In the worst-case, carry ripples through all the stages.

1111110 Carry
0111111 Number A
+ 0000001 Number B
1000000 Sum S

Switching Circuits & Logic Design 3


An-1 Bn-1 A2 B 2 A1 B 1 A0 B 0

FAn-1
Cn-1
…… C3
FA2
C2
FA1
C1
FA0
C0

Delay for C1 = 2δ
Cn Sn-1 S2 S1 S0 Delay for C2 = 4δ
Delay for Cn-1 = 2(n-1)δ
Two numbers: An-1…A2A1A0 and Bn-1…B2B1B0 Delay for Cn = 2nδ
Input carry: C0
Delay for S0 = 3δ
Sum: Sn-1…S2S1S0
Delay for S1 = 2δ + 3δ = 5δ
Output carry: Cn
Delay for S2 = 4δ + 3δ = 7δ
Delay for Sn-1 = 2(n-1)δ + 3δ = (2n+1) δ
Delay is proportional to n

Switching Circuits & Logic Design 4


How to Design a Parallel Subtractor?
• Observation:
– Computing A-B is the same as adding the 2’s complement of B to A.
– 2’s complement is equal to 1’s complement plus 1.
– Let Xi = Bi’.
An-1 Xn-1 A2 X 2 A1 X1 A0 X0

FAn-1
Cn-1
…… C3
FA2
C2
FA1
C1
FA0
C0 = 1

Cn Sn-1 S2 S1 S0

Switching Circuits & Logic Design 5


A Parallel Adder/Subtractor
An-1 A1 A 0 Bn-1 B1 B0
ADD’ / SUB
… xor … xor xor

Cn n-bit Parallel Adder C0


Sn-1 S2 S 1 S0

Switching Circuits & Logic Design 6


• Main drawback of ripple-carry adder:
– The total delay is proportional to the number of bits n.
– Performance degradation for large values of n.
– The main bottleneck is the carry, which propagates sequentially from one stage to
the next.
• How this can be overcome?
– Generate all the carry bits in parallel before the actual addition starts.
– After the initial delay, all the additions can be done in parallel.

Switching Circuits & Logic Design 7


Carry Look-ahead Adder (CLA)
• The propagation delay of an n-bit ripple carry order has been seen to be
proportional to n.
– Due to the rippling effect of carry sequentially from one stage to the next.
• One possible way to speedup the addition.
– Generate the carry signals for the various stages in parallel.
– Time complexity reduces from O(n) to O(1).
– Hardware complexity increases rapidly with n.

Switching Circuits & Logic Design 8


• Consider the i-th stage in the addition process.
• We define the carry generate and carry propagate
functions as: Ai Si
Bi FA
Gi = Ai.Bi
Ci Ci+1
Pi = Ai  Bi
– Gi = 1 represents the condition when a carry is generated
in stage-i independent of the other stages.
– Pi = 1 represents the condition when an input carry Ci will
be propagated to the output carry Ci+1.
• We can generate the output carry in terms of Gi and Pi. Ci+1 = Gi + Pi.Ci

Switching Circuits & Logic Design 9


Unrolling the Recurrence
Ci+1 = Gi + PiCi = Gi + Pi (Gi-1 + Pi-1Ci-1) = Gi + PiGi-1 + PiPi-1Ci-1
= Gi + PiGi-1 + PiPi-1 (Gi-2 + Pi-2Ci-2)
= Gi + PiGi-1 + PiPi-1 Gi-2 + PiPi-1Pi-2Ci-2 = …..

i-1 i i
Ci+1 = Gi +  Gk  Pj + C0  Pj
k=0 j=k+1 j=0

Switching Circuits & Logic Design 10


Design of 4-bit CLA Adder
C4 = G3 + G2P3 + G1P2P3 + G0P1P2P3 + C0P0P1P2P3 4 AND2 gates
3 AND3 gates
C3 = G2 + G1P2 + G0P1P2 + C0P0P1P2
2 AND4 gates
C2 = G1 + G0P1 + C0P0P1 1 AND5 gate
C1 = G0 + C0P0 1 OR2, 1 OR3, 1 OR4
and 1 OR5 gate
S0 = A0  B0  C0 = P0  C0
S1 = P1  C1
4 XOR2 gates
S2 = P2  C2
S3 = P3  C3

Switching Circuits & Logic Design 11


Design of 4-bit CLA Adder (contd.)
C4 = G3 + G2P3 + G1P2P3 + G0P1P2P3 + C0P0P1P2P3 4 AND2 gates
3 AND3 gates
C3 = G2 + G1P2 + G0P1P2 + C0P0P1P2
2 AND4 gates
C2 = G1 + G0P1 + C0P0P1 1 AND5 gate
C1 = G0 + C0P0 1 OR2, 1 OR3, 1 OR4
and 1 OR5 gate
S0 = A0  B0  C0 = P0  C0
S1 = P1  C1
4 XOR2 gates
S2 = P2  C2
S3 = P3  C3

Switching Circuits & Logic Design 12


Design of 4-bit CLA Adder (contd.)
C4 = G3 + C3P3 4 AND2 gates
2 AND3 gates
C3 = G2 + G1P2 + G0P1P2 + C0P0P1P2
1 AND4 gates
C2 = G1 + G0P1 + C0P0P1 1 AND5 gate
C1 = G0 + C0P0 1 OR2, 1 OR3, 1 OR4
and 1 OR2 gate
S0 = A0  B0  C0 = P0  C0
S1 = P1  C1
4 XOR2 gates
S2 = P2  C2
S3 = P3  C3

Switching Circuits & Logic Design 13


C4
The 4-bit CLA P3
Circuit G3

C3
P2
G2

C2 P1
G1
P0
C1 G0
C0

Switching Circuits & Logic Design 14


B 3 A3 B 2 A2 B 1 A1 B 0 A0

Gi and Pi Generator 3δ

G3 P3 G2 P2 G1 P1 G0 P0

4-bit Carry Look Ahead Circuit 2δ

C3 C2 C1 C0

xor xor xor xor 3δ

C4 Total Time = 8δ
S3 S2 S1 S0

Switching Circuits & Logic Design 15


END OF LECTURE 22

Switching Circuits & Logic Design 16


Lecture 23: Design of Adders (Part 3)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
16-bit Adder Using 4-bit CLA Modules
A15-A12 B15-B12 A11-A8 B11-B8 A7-A4 B7-B4 A3-A0 B3-B0

4-bit CLA 4-bit CLA 4-bit CLA 4-bit CLA C0


Adder C12 Adder C8 Adder C4 Adder

C16 S15-S12 S11-S8 S7-S4 S3-S0

Problem: Carry propagation between modules still slows down the adder

Switching Circuits & Logic Design 2


• Solution:
– Use a second level of carry look-ahead mechanism to generate the input
carries to the CLA blocks in parallel.
– The second level of CLA generates C4, C8, C12 and C16 in parallel with two gate
delays (2δ).
– For larger values of n, more CLA levels can be added.
• Delay calculation of a 16-bit adder:
a) For original single-level CLA: 14δ
b) For modified two-level CLA: 10δ

Switching Circuits & Logic Design 3


Delay of a k-bit Adder

n TCLA TRCA
4 8δ 9δ
16 10δ 33δ TCLA = (6 + 2 log4 n ) δ
32 12δ 65δ
64 12δ 129δ
TRCA = (2n + 1) δ
128 14δ 257δ
256 14δ 513δ

Switching Circuits & Logic Design 4


Carry Select Adder
• Basically consists of two parallel adders (say, ripple-carry adder) and a
multiplexer.
• For two given numbers A and B, we carry out addition twice:
– With carry-in as 0
– With carry-in as 1
• Once the correct carry-in is known, the correct sum is selected by a
multiplexer.

Switching Circuits & Logic Design 5


Basic building block of a
carry-select adder, with
block size of 4.

• For a multi-bit adder, the number


of bits in each carry select block
can be either uniform or variable.

Switching Circuits & Logic Design 6


Uniform sized adder
• A 16-bit carry select adder with a uniform block size of 4 is shown.
• The least significant block needs a single adder (since the carry-in is known).
• Total delay is 4 full adder delays, plus 3 MUX delays.

Switching Circuits & Logic Design 7


Variable-sized adder
• A 16-bit carry select adder with variable block sizes of 2-2-3-4-5 is shown.
• Total delay is 2 full adder delays, plus 4 MUX delays.

Switching Circuits & Logic Design 8


Carry Save Adder
• Here we add three operands (say, X, Y and Z) together.
• For adding multiple numbers, we have to construct a tree of carry save adders.
– Used in combinational multiplier design.
• Each carry save adder is simply an independent full adder without carry
propagation.
• A parallel adder is required only at the last stage.

Switching Circuits & Logic Design 9


• An illustrative example:
X: 10011
Y: + 11001
X: 10011 X: 10011 Z: + 01011
Y: + 11001 Y: + 11001 S: 00001
Z: + 01011 Z: + 01011 C: 11011
C: 11011 S: 00001 Sum: 110111

A set of full adders generate carry The sum and carry vectors are
and sum bits in parallel added later (with proper shifting)

Switching Circuits & Logic Design 10


An n-bit Carry Save Adder
Xn-1 Yn-1 Zn-1 X2 Y2 Z2 X1 Y1 Z1 X0 Y0 Z0

Full …. Full Full Full


Adder Adder Adder Adder

Cn-1 Sn-1 C2 S2 C1 S1 C0 S0

The carry input of the full adder is used as the third input

Switching Circuits & Logic Design 11


Adding m Numbers: Some
Examples CSA CSA

m=3
CSA m=6
CSA
m=4
CSA CSA
CSA

Parallel Adder Parallel Adder


Parallel Adder

Switching Circuits & Logic Design 12


END OF LECTURE 23

Switching Circuits & Logic Design 13


Lecture 24: Logic Design (Part 1)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Introduction
• We shall discuss some of the common functional blocks used in logic design.
• We shall discuss the following:
a) Multiplexer
b) Decoder / Demultiplexer
c) Encoder
d) Comparator

Switching Circuits & Logic Design 2


Data Selectors or Multiplexers
• A multiplexer is an electronic switch that has:
– A set of n data input lines D = {D0, D1, …, Dn-1}
– A set of m select input lines S = {S0, S1, …, Sm-1}
– One output line f
– One of the input data lines is connected to the output depending upon the value of
the select lines (f = D0 if S = 0, f = D1 if S = 1, f = D2 if S = 2, and so on).
• Usually, n = 2m.
• Also called a 2m-to-1 multiplexer.

Switching Circuits & Logic Design 3


D0
D1
2m-to-1 f
MUX
Dn-1

S0 S1 Sm-
1

Switching Circuits & Logic Design 4


Implement a 2-to-1 MUX using Gates

D0
2-to-1 f
D1 MUX

S0

f = S0’.D0 + S0.D1

Switching Circuits & Logic Design 5


Implement a 4-to-1 MUX using Gates
S1 S0 D0 D1 D2 D3 f
D0 0 0 0 X X X 0
D1 0 0 1 X X X 1
4-to-1 f
D2 0 1 X 0 X X 0
MUX
0 1 X 1 X X 1
D3
1 0 X X 0 X 0
1 0 X X 1 X 1

S0 S1 1 1 X X X 0 0
1 1 X X X 1 1

f = S1’.S0’.D0 + S1’.S0.D1 + S1.S0’.D2 + S1.S0.D3

Switching Circuits & Logic Design 6


Implement a 4-to-1 MUX using 2-to-1 MUX-es
D0
2-to-1
D1 MUX

2-to-1 f
S0 MUX

D2
2-to-1
D3 MUX S1

S0

Switching Circuits & Logic Design 7


Implement a 8-to-1 MUX using Smaller MUX-es
D0
D1 S2 S1 S0 Function
4-to-1
D2 MUX 0 0 0 f = D0
D3 0 0 1 f = D1
0 1 0 f = D2
S0 S1 2-to-1
f 0 1 1 f = D3
MUX
1 0 0 f = D4
D4
S2 1 0 1 f = D5
D5 4-to-1
D6 MUX 1 1 0 f = D6
D7 1 1 1 f = D7

Switching Circuits & Logic Design 8


Implement Logic Functions using MUX
• Implement an n-variable function using 2n-to-1 MUX.
– Connect the n variables to the select lines.
– Connect the truth table output column values to data inputs.
A B C f
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0
Switching Circuits & Logic Design 9
• Implement an n-variable function using 2n-1-to-1 MUX.
– Connect (n-1) variables to the select lines.
– Apply the remaining variable, its complement, 0 or 1 to the data inputs.
– For this, we partition the truth table into groups of two rows each.
A B C f
D0
0 0 0 0
D1
0 0 1 1 4-to-1 f
0 1 0 0 D2 MUX
0 1 1 0 D3
1 0 0 1
1 0 1 1
1 1 0 1 S0 S1
1 1 1 0
Switching Circuits & Logic Design 10
A B C D f
0 0 0 0 0 D0
0 0 0 1 0
D1
0 0 1 0 1
0 0 1 1 1
D2
0 1 0 0 1 D3 8-to-1
0 1 0 1 0 f
D4 MUX
0 1 1 0 0
0 1 1 1 0
D5
1 0 0 0 0 D6
1 0 0 1 1
D7
1 0 1 0 1
1 0 1 1 1
1 1 0 0 0 S0 S1 S2
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0 Switching Circuits & Logic Design 11
Implement Arbitrary Functions using 2-to-1 MUX
• We repeatedly split a function into two smaller sub-functions by using
Shannon’s decomposition theorem.
• Shannon’s Decomposition Theorem:
– An n-variable function f (x1, x2, …, xn) can be decomposed with respect to any of the
n variables (say, x1) as:
f (x1, x2, …, xn) = x1’. f (0, x2, …, xn) + x1. f (1, x2, …, xn) = x1’.f10 + x1.f11
• Each application of Shannon’s decomposition theorem is like using a 2-to-1
MUX:
– Apply x1 to the select inputs, and f10 and f11 to the data inputs.

Switching Circuits & Logic Design 12


An Example Worked Out
Given function: f = A’.B + B.C + A.C’
Expanding w.r.t. A, we get:
f = A’.(B + B.C) + A.(B.C + C’) = A’.(B) + A.(B + C’)
Expanding (B + C’) w.r.t. B, we get:
B + C’ = B’.(C’) + B.(1)

Switching Circuits & Logic Design 13


END OF LECTURE 24

Switching Circuits & Logic Design 14


Lecture 25: Logic Design (Part 2)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
De-Multiplexers
• A demultiplexer is an electronic switch that works in a reverse manner as
compared to a multiplexer:
– A set of n output lines D = {D0, D1, …, Dn-1}
– A set of m select input lines S = {S0, S1, …, Sm-1}
– One data input line IN
– The input data line will be connected to one of the outputs depending upon the
value of the select lines (D0 = IN if S = 0, D1 = IN if S = 1, D2 = IN if S = 2, and so on).
– The outputs that are not selected are set to 0.
• Usually, n = 2m.
• Also called a 1-to-2m demultiplexer.

Switching Circuits & Logic Design 2


D0
D1
IN 1-to-2m
DEMUX

Dn-1

S0 S1 Sm-
1

Switching Circuits & Logic Design 3


MUX-DEMUX for Data Communication

Switching Circuits & Logic Design 4


Implement a 1-to-2 DEMUX using Gates

D0
IN 1-to-2
DEMUX D1

S0

D0 = S0’.IN
D1 = S0.IN

Switching Circuits & Logic Design 5


Implement a 1-to-4 DEMUX using Gates

D0

IN 1-to-2 D1
DEMUX D2
D3

S0 S1
D0 = S1’.S0’.IN D2 = S1.S0’.IN
D1 = S1’.S0.IN D3 = S1.S0.IN

Switching Circuits & Logic Design 6


Decoder
• A decoder can be considered as a special case of a demultiplexer.
– A DEMUX with the data input IN always set to 1.
– It has n inputs and 2n outputs (typically).
– Depending on the applied input, exactly one of the output lines is set to 1, while all
the other lines are set to 0.
– In some decoder, the reverse convention is also followed – the selected output line
is set to 0, while all others are set to 1.
• Many applications:
– Selecting one out of many functional blocks (e.g. memory).
– Code conversion, data distribution, etc.

Switching Circuits & Logic Design 7


Example: A 2-to-4 decoder

D1 D0 f0 f1 f2 f3
f0
D0 0 0 1 0 0 0
2-to-4 f1
f2 0 1 0 1 0 0
decoder
D1 1 0 0 0 1 0
f3
1 1 0 0 0 1

f0 = D1’.D0’ f2 = D1.D0’
f1 = D1’.D0 f3 = D1.D0

Switching Circuits & Logic Design 8


• A decoder typically has an enable input G.
– If G = 0, the decoder is enabled; if G = 1, all the outputs are deactivated.

G D1 D0 f0 f1 f2 f3
f0 0 0 0 1 0 0 0
D0
2-to-4 f1 0 0 1 0 1 0 0
decoder f2 0 1 0 0 0 1 0
D1
f3
0 1 1 0 0 0 1
1 X X 0 0 0 0
G f0 = D1’.D0’.G’ f2 = D1.D0’.G’
f1 = D1’.D0.G’ f3 = D1.D0.G’

Switching Circuits & Logic Design 9


Constructing 4-to-16 Decoder using 2-to-4 Decoders
• Four inputs D0, D1, D2 and D3, and 16 outputs f0, f1, …, f15.
• We require five 2-to-4 decoders.
– Four decoders to generate the 16 outputs.
– One decoder to select one of the four decoders.

Switching Circuits & Logic Design 10


f0
Constructing a 4-to-16 2-to-4 f1
decoder f2
Decoder using 2-to-4 f3

Decoders
f4
2-to-4 f5
decoder f6
f7 f8
2-to-4 2-to-4 f9
decoder f10
decoder f1
1

f1
2-to-4 f21
decoder f31
f41
5

Switching Circuits & Logic Design 11


Realizing Logic Functions using Decoder
• We can use an n-to-2n decoder and an OR gate to realize any function of n
variables.
– The n input variables are connected to the decoder inputs.
– All the outputs corresponding to the true minterms are fed to the inputs of the OR
gate.
– The OR gate output generates the function.
• We shall be illustrating the process with an example.

Switching Circuits & Logic Design 12


A B C f
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0

Switching Circuits & Logic Design 13


END OF LECTURE 25

Switching Circuits & Logic Design 14


Lecture 26: Logic Design (Part 3)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Special Decoder Designs
f0 f1 f2 f3
Example: 4-to-16 f0
decoder using two 2-to-4 f1
f4 f5 f6 f7

decoders and a gate- w


x 2-to-4 f8 f9 f10 f11
switching matrix.
f2
f12 f13 f14 f15
f3
f1 f2
f0 f3

2-to-4

y z

Switching Circuits & Logic Design 2


w x y z

Example: BCD-to-Decimal Decoder


f0

f0 f1
w f1 f2
x f2 f3
y f3 f4
z f4
BCD-to-Decimal f5

Decoder f5
f6
f6
Enable f7
f7

f8
f8
f9
f9
Enable
(c) Logic diagram.

Switching Circuits & Logic Design 3


BCD to Seven-Segment Decoder
• 7-segment displays are commonly used for numerical displays.
– There are seven display segments, designed using LED, LCD, or any other technology.
– Depending on the digit to be displayed, the appropriate segments should glow.

A
A
x1 B F
x2 BCD to C G B
7-segment D
x3 E
decoder
F
x4 G E C

Switching Circuits & Logic Design 4


BCD Code 7-segment Code
Digit x1 x2 x3 x4 A B C D E F G
0 0 0 0 0 1 1 1 1 1 1 0
1 0 0 0 1 0 1 1 0 0 0 0
2 0 0 1 0 1 1 0 1 1 0 1 A = x1 + x2’x4’ + x2x4 + x3x4
3 0 0 1 1 1 1 1 1 0 0 1 B = x2’ + x3’x4’ + x3x4
4 0 1 0 0 0 1 1 0 0 1 1 C = x2 + x3’ + x4
5 0 1 0 1 1 0 1 1 0 1 1
D = x2’x4’ + x2’x3 + x3x4’ + x2x3’x4
6 0 1 1 0 0 0 1 1 1 1 1
E = x2’x4’ + x3x4’
7 0 1 1 1 1 1 1 0 0 0 0
8 1 0 0 0 1 1 1 1 1 1 1 F = x1 + x2x3’ + x2x4’ + x3’x4’
9 1 0 0 1 1 1 1 0 0 1 1 G = x1 + x2’x3 + x2x3’ + x3x4’

Switching Circuits & Logic Design 5


Encoders
• An encoder typically has 2n input lines and n D0
output lines. D1
D2
– Only one of the input lines is at 1 at a time; f0
and the rest are all 0’s. D3 8-to-3
f1
D4 Encoder
– The outputs will contain the binary code of f2
D5
the input line that is at 1.
D6
D7

Switching Circuits & Logic Design 6


D7 D6 D5 D4 D3 D2 D1 D0 f2 f1 f0
0 0 0 0 0 0 0 1 0 0 0 • What happens for the other
0 0 0 0 0 0 1 0 0 0 1 input combinations?
0 0 0 0 0 1 0 0 0 1 0 • There is ambiguity.
0 0 0 0 1 0 0 0 0 1 1 • We typically use a priority
0 0 0 1 0 0 0 0 1 0 0 encoder, where the input
0 0 1 0 0 0 0 0 1 0 1 lines have some priority.
0 1 0 0 0 0 0 0 1 1 0
1 0 0 0 0 0 0 0 1 1 1

Switching Circuits & Logic Design 7


Priority Encoder
• Basic concept:
– The input lines are assumed to represent units that request some service.
– When two inputs Di and Dj (i > j) request service simultaneously, line Di is assumed
to have higher priority than line Dj.
– The outputs of the encoder gives the binary code indicating which of the input
lines requesting service has the highest priority.

Switching Circuits & Logic Design 8


D7 D6 D5 D4 D3 D2 D1 D0 f2 f1 f0
D0 0 0 0 0 0 0 0 1 0 0 0
D1 0 0 0 0 0 0 1 X 0 0 1
D2 f0 0 0 0 0 0 1 X X 0 1 0
8-to-3
D3 0 0 0 0 1 X X X 0 1 1
Priority f1
D4
Encoder f2 0 0 0 1 X X X X 1 0 0
D5
D6 0 0 1 X X X X X 1 0 1
D7 0 1 X X X X X X 1 1 0
1 X X X X X X X 1 1 1

Switching Circuits & Logic Design 9


• The switching expressions for the outputs:
f2 = D4D5’D6’D7’ + D5D6’D7’ + D6D7’ + D7 = D4 + D5 + D6 + D7

f1 = D2D3’D4’D5’D6’D7’ + D3D4’D5’D6’D7’ + D6D7’ + D7


= D2D4’D5’ + D3D4’D5’ + D6 + D7

f0 = D1D2’D3’D4’D5’D6’D7’ + D3D4’D5’D6’D7’ + D5D6’D7’ + D7


= D1D2’D4’D6’ + D3D4’D6’ + D5D6’ + D7

Switching Circuits & Logic Design 10


Comparators
• An n-bit comparator compares the magnitude of two numbers A and B, and
produces three outputs GT, EQ and LT:
– GT = 1, if and only if A > B
– EQ = 1, if and only if A = B
– LT = 1, if and only if A < B

Switching Circuits & Logic Design 11


1-bit Comparator
• If A and B are 1-bit numbers, then
GT = A.B’
LT = A’.B
EQ = A’.B’ + A.B = A xnor B

Switching Circuits & Logic Design 12


2-bit Comparator A1 A2 B1 B2

A1A2
B1B2 00 01 11 10 2-bit Comparator
00 EQ GT GT GT

01 LT EQ GT GT
GT EQ LT
11 LT LT EQ LT GT = A1A2B2’ + A2B1’B2’ + A1B1’
10 LT LT GT EQ EQ = A1’A2’B1’B2’ + A1’A2B1’B2 + A1A2’B1B2’ + A1A2B1B2
LT = A2’B1B2 + A1’A2’B2 + A1’B1

Switching Circuits & Logic Design 13


4-bit Comparator
• Suppose the two numbers: A = A3A2A1A0 and B = B3B2B1B0

• Let xi = Ai’.Bi’ + Ai.Bi (xi = 1 if Ai and Bi are equal)

• The switching expressions for comparison:


EQ = x3.x2.x1.x0
GT = A3.B3’ + x3.A2.B2’ + x3.x2.A1.B1’ + x3.x2.x1.A0.B0’
LT = A3’.B3 + x3.A2’.B2 + x3.x2.A1’.B1 + x3.x2.x1.A0’.B0

Switching Circuits & Logic Design 14


END OF LECTURE 26

Switching Circuits & Logic Design 15


Lecture 27: Binary Decision Diagrams (Part 1)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Binary Decision Diagrams (BDD)
• A data structure used to represent a Boolean function.
• Represented as a rooted, directed, acyclic graph, which consists of several
decision nodes and two terminal nodes, called 0-terminal and 1-terminal.
– Each decision node is labeled by a Boolean variable and has two child nodes called
low child, and high child.
– The edge from a node to a low (high) child represents an assignment of the
variable to 0 (1).
• A BDD is said to be ordered if different variables appear in the same order on
all paths from the root.

Switching Circuits & Logic Design 2


Example f
a b c f
0 0 0 1
0 0 1 0
a 0 1 0 0
0 1 1 1
b b 1 0 0 0
1 0 1 0
1 1 0 1
c c c c 1 1 1 1

1 0 0 1 0 0 1 1

Switching Circuits & Logic Design 3


• Construction of a BDD is based on the Shannon expansion of a
function.

Switching Circuits & Logic Design 4


Shannon Expansion
• Given a Boolean function f (x1, x2, …, xi , …, xn)
• Positive cofactor
fi1 = f (x1, x2, …, 1, …, xn)
• Negative cofactor
fi0 = f (x1, x2, …, 0, …, xn)
• Shannon’s expansion theorem states that
f = x i ′ f i 0 + xi f i 1
f = (xi + fi0 )(xi′ + fi1 )

Switching Circuits & Logic Design 5


How to construct BDD?
f = ac + bc + a’b’c
= a’ (b’c’ + bc) + a (c + bc)
= a’ (b’c’ + bc) + a (c) f This is the first step.
The process is continued
a for all input variables.

Low High
child child
b’c’ + bc c

Switching Circuits & Logic Design 6


f = ac + bc + a′b′c′
= a′ (b′c′ + bc) + a (c + bc) Expand by a
= a′ (b′c′ + bc) + a (c)

b′(c′) + b(c) b′(c) + b(c) Expand by b

c′(1) + c(0) c′(0) + c(1) c′(0) + c(1) c′(0) + c(1) Expand by c

Variable ordering: a, b, c

Switching Circuits & Logic Design 7


f

b b

c c c c

1 0 0 1 0 1 0 1

Switching Circuits & Logic Design 8


Another Example: f = a’bc + b’c’ + ac’

Switching Circuits & Logic Design 9


Variable Ordering (OBDD)
• The size of a BDD is determined both by the function being represented
and the chosen ordering of the variables.
– For some functions, the size of a BDD may vary between a linear to an
exponential range depending upon the ordering of the variables.
• An example:
f(x1,…,x2n) = x1x2 + x3x4 + … + x2n-1x2n
Variable ordering: x1 < x3 < … < x2n-1 < x2 < x4 < … < x2n
BDD requires 2n+1 nodes to represent the function.
Variable ordering: x1 < x2 < x3 < x4 < … < x2n-1 < x2n
BDD requires 2n nodes to represent the function.

Switching Circuits & Logic Design 10


BDD for the function
f(x1, ..., x8) = x1x2 + x3x4 +
x5x6 + x7x8 using bad
variable ordering

Switching Circuits & Logic Design 11


Same function using good
variable ordering

Switching Circuits & Logic Design 12


• Important point to note:
– It is essential to find a good variable ordering when using the OBDD data structure
in practice.
– The problem of finding the best variable ordering is NP-hard.
– Several heuristics for variable ordering have been proposed.

Switching Circuits & Logic Design 13


END OF LECTURE 27

Switching Circuits & Logic Design 14


Lecture 28: Binary Decision Diagrams (Part 2)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Reduced Ordered BDD (ROBDD)
• An ordered binary decision diagram is said to be reduced ordered BDD
(ROBDD) if the following two graph reduction rules are applied:
– Merge any isomorphic subgraphs.
– Eliminate any node whose two children are isomorphic.

• The advantage of an ROBDD is that it is canonical (unique) for a given function.


– There is exactly one ROBDD for a given variable ordering.
– This property makes it useful in functional equivalence checking.

Switching Circuits & Logic Design 2


Some Properties of ROBDD
• The following properties hold in a ROBDD:
a) Uniqueness: No two distinct nodes u and v are labeled with the same variable
name and have the same low and high successor.
b) Non-redundant: No variable node u has identical low and high successor.

Switching Circuits & Logic Design 3


Reduction Rules: Merge Isomorphic Subtrees

x x x

y z y z y z

x x x

y z y z y z

Switching Circuits & Logic Design 4


Reduction Rule: Remove Redundant Nodes

y y

Switching Circuits & Logic Design 5


Construction of ROBDD: an example
Given function: f (x1, x2, x3) = x1.x2 + x1’.x3 + x1.x2’.x3

Switching Circuits & Logic Design 6


x1 x1
0 1 0 1

x2 x2 x2 x2
0 1 0 1 0 1 0 1
x3 x3 x3 x3 x3 x3 x3
x3 1 0 0
0 1 0 1 0 1 0 1 0 1
1 1
0 1 0 1 0 1 1 1 0
0 1

x1 1 x1
0 1
x2 x2 0
1 0 x2
0
0
x3 1 1 x3 1 1
0 0
0 1 0 1

Switching Circuits & Logic Design 7


Some Benefits of BDD
• Checking for tautology is trivial.
– BDD is a constant 1.

• Complementation.
– Given a BDD for a function f, the BDD for f′ can be obtained by simply interchanging
the terminal nodes.

• Equivalence check.
– Two functions f and g are equivalent if their BDDs (under the same variable
ordering) are the same.

Switching Circuits & Logic Design 8


Use of BDD in Synthesis
• BDD is canonical for a given variable ordering.
• It implicitly uses factored representation:
x
x’h + xh = h
h y h y

a b a b

h x h x h x
ah + bh = (a+b)h
y z y z y z

Switching Circuits & Logic Design 9


• Variable reordering can reduce the size of BDD.
– Implicit logic minimization.

• Some redundancy is also removed during the construction of BDD itself.

Switching Circuits & Logic Design 10


MUX realization of functions

f f

x x
0 1

f g
f g

Switching Circuits & Logic Design 11


MUX-based Functional Decomposition
f f

0 1
h

g
h
f g f

An example ===>

Switching Circuits & Logic Design 12


f f

a ab′
0 1
b a
c d
c b
d
0 1
0 1

Switching Circuits & Logic Design 13


A Complete Mapping Example
x1
1
0
0 x2
x3 1 1
0
0 1

Switching Circuits & Logic Design 14


To Summarize
• BDDs have been used traditionally to represent and manipulate Boolean
functions.
– Used in synthesis systems.
– Used in formal verification tools.
– Efficient packages to manipulate BDDs are available.

Switching Circuits & Logic Design 15


END OF LECTURE 28

Switching Circuits & Logic Design 16


Lecture 29: Logic Design using AND-EXOR Network

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Introduction
• We have studied various method of logic design using the basic gates.
• There are many applications (e.g. arithmetic, error correction, etc.), where
effective use of EXOR gates can reduce the complexity of gate networks.
– Also it is easy to test such circuits.
• We shall consider AND-EXOR 2-level expressions and their simplication.

Switching Circuits & Logic Design 2


Classification of AND-EXOR Expressions
• Any n-variable switching function f (x1, x2, …, xn) can be expanded with respect
to any given variable (say, x1) in several ways:
a) f (x1, x2, …, xn) = f0 ⊕ x1 f2 Positive Davio Expansion
b) f (x1, x2, …, xn) = x1’f2 ⊕ f1 Negative Davio Expansion

c) f (x1, x2, …, xn) = x1’f0 ⊕ x1 f1 Shannon Expansion


where f0 = f(0, x2, …, xn), f1 = f(1, x2, …, xn), and f2 = f0 ⊕ f1.

Switching Circuits & Logic Design 3


• Some properties of the EXOR operation:
a) (x ⊕ y) ⊕ z = x ⊕ (y ⊕ z)
b) x (y ⊕ z) = xy ⊕ xz
c) x⊕y = y⊕x
d) x⊕x = 0
e) x ⊕ 1 = x’
f) If xy = 0, then x + y = x ⊕ y

Switching Circuits & Logic Design 4


Reed Muller Expression
• By expanding any given function f using the Positive Davio Expansion
recursively, we get a switching expression with only un-complemented literals:
a0 ⊕ a1x1 ⊕ … anxn ⊕ a12x1x2 ⊕ a13x1x3 ⊕ … ⊕ an-1,nxn-1xn ⊕ …… ⊕ a12…nx1x2…xn
– This expression is known as Positive-Polarity Reed-Muller (PPRM) expression.
– The co-efficients a are either 0 or 1.
• Example: Consider the function f = x1’x2’x3’.
– If we substitute x1’ = x1 ⊕ 1, x2’ = x2 ⊕ 1, and x3’ = x3 ⊕ 1, we get
f = (x1 ⊕ 1) (x2 ⊕ 1) (x3 ⊕ 1)
= 1 ⊕ x1 ⊕ x2 ⊕ x3 ⊕ x1x2 ⊕ x2x3 ⊕ x1x3 ⊕ x1x2x3

Switching Circuits & Logic Design 5


• In general, we can use either Positive Davio expansion or Negative Davio
expansion for a given function.
– We can get an expression similar to PPRM, where each variable appears in either
complemented or un-complemented form.
– Such an expression is called Fixed Polarity Reed-Muller (FPRM) expression.
• Example: Consider the function f = x1x2x3x4 + x1’x2’x3’x4’
– We can write: f = x1x2x3x4 ⊕ x1’x2’x3’x4’ [since the product terms are disjoint]
– We apply positive Davio expansion to x1 and x2, and negative Davio to x3 and x4:
f = x1x2 (x3’ ⊕ 1)(x4’ ⊕ 1) ⊕ (x1 ⊕ 1)(x2 ⊕ 1) x3’x4’
= x1x2 (1 ⊕ x3’ ⊕ x4’ ⊕ x3’x4’) ⊕ (1 ⊕ x1 ⊕ x2 ⊕ x1x2) x3’x4’
= x1x2 ⊕ x1x2x3’ ⊕ x1x2x4’ ⊕ x3’x4’ ⊕ x1x3’x4’ ⊕ x2x3’x4’

Switching Circuits & Logic Design 6


2-level AND-EXOR Realization
f = x1x2 ⊕ x1x2x3’ ⊕ x1x2x4’ ⊕ x3’x4’ ⊕ x1x3’x4’ ⊕ x2x3’x4’
– We need two AND2 gates, four AND3 gates, and one XOR6 gate.
– Two NOT gates are required to generate x3’ and x4’, and a constant 1 for some
functions.

Switching Circuits & Logic Design 7


Cascade of XOR2 Gates
• Instead of a large XOR gate, we can use a chain of XOR2 gates.
– Makes the circuit easier to implement, but incurs more delay.

Switching Circuits & Logic Design 8


An Example Worked Out
• Show the Reed-Muller form for the function: f (x1, x2, x3) = ∑ (0, 3, 5, 6)
f = x1’x2’x3’ + x1’x2x3 + x1x2’x3 + x1x2x3’

= x1’x2’x3’ ⊕ x1’x2x3 ⊕ x1x2’x3 ⊕ x1x2x3’

= (1 ⊕ x1) (1 ⊕ x2) (1 ⊕ x3) ⊕ (1 ⊕ x1) x2x3 ⊕ (1 ⊕ x2) x1x3 ⊕ (1 ⊕ x3) x1x2

= (1 ⊕ x1 ⊕ x2 ⊕ x3 ⊕ x1x2 ⊕ x2x3 ⊕ x1x3 ⊕ x1x2x3) ⊕ (x2x3 ⊕ x1x2x3)


⊕ (x1x3 ⊕ x1x2x3) ⊕ (x1x2 ⊕ x1x2x3)

= 1 ⊕ x1 ⊕ x2 ⊕ x3

Switching Circuits & Logic Design 9


END OF LECTURE 29

Switching Circuits & Logic Design 10


Lecture 30: Threshold Logic and Threshold Gates

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Basic Concepts
• Schematic of a Threshold element or Threshold gate:
x1
w1

x2 w2 T y

wn
xn

• How does it work?


– y =1, if and only if w1x1 + w2x2 + … + wnxn ≥ T
– y =0, if and only if w1x1 + w2x2 + … + wnxn < T

Switching Circuits & Logic Design 2


Why Important?
• Threshold logic can be used for neuromorphic computing.
– Can model neurons in brains.

• An interesting alternative in logic design:


– Can result in much simpler circuit realizations for many functions.
– Technologies for implementation are also available (e.g. memristors).

Switching Circuits & Logic Design 3


An Example
Consider the function: Inputs Weighted Sum Output
y = f (x1,x2,x3) = ∑ (1,2,3,6,7) = x1’x3 + x2 x1 x2 x3 -x1+2x2+x3 y
0 0 0 0 0

x1
0 0 1 1 1
-1 0 1 0 2 1
x2 2 _
1
2
y 0 1 1 3 1
1 1 0 0 -1 0
x3
1 0 1 0 0
1 1 0 1 1
1 1 1 2 1

Switching Circuits & Logic Design 4


Threshold Gate is Functionally Complete
• Threshold gate is a generalization of conventional gates.
– More powerful than conventional gates because it can realize a larger class of
functions.
– Any conventional gate can be realized with a threshold gate.
– Thus, threshold gates are functionally complete.
• Example: NAND implementation
x1
-1
_
-11 y
2
-1
x2

Switching Circuits & Logic Design 5


Can Any Function be Realized using a Single Threshold Gate?
• The answer is no.
w1 + w2 ≥ T
• A counterexample: w3 + w4 ≥ T
– Consider the function: f (x1,x2,x3,x4) = x1x2 + x3x4 So, w1 + w2 + w3 + w4 ≥ 2T
– Output must be 1 for the minterms: x1x2x3’x4’ and x1’x2’x3x4

– Output must be 0 for the minterms: x1’x2x3’x4 and x1x2’x3x4’


w2 + w4 < T
CONFLICT ::- Not Possible w1 + w3 < T
So, w1 + w2 + w3 + w4 < 2T

Switching Circuits & Logic Design 6


A Function that Requires Two T-gates

f = (x1x2 + x3) x4x5 + x6

Switching Circuits & Logic Design 7


Threshold Logic: The Basic Design Problem
• Given a switching function f (x1,x2, …,xn), determine whether it is realizable by a
single threshold element, and if so, find appropriate weights and threshold.
– Such a function is called a threshold function.

• A straightforward approach:
– Obtain inequality constraints from each row of the truth table.
– Solve the set of 2n simultaneous inequalities.

Switching Circuits & Logic Design 8


An Example
• Consider the function: f (x1, x2, x3) = x1’x2’ + x1’x3
D x1 x2 x3 f Inequality
D = 0  T must be negative 0 0 0 0 1 0≥T
D = 2  w2 must be negative 1 0 0 1 1 w3 ≥ T
D = 4  w1 must be negative 2 0 1 0 0 w2 < T
D = 3,5  w2 > w1 3 0 1 1 1 w2 + w 3 ≥ T
D =1  w3 ≥ T 4 1 0 0 0 w1 < T
Thus, w3 ≥ T > w2 > w1 5 1 0 1 0 w1 + w 3 < T
6 1 1 0 0 w1 + w2 < T
w1 = -2, w2 = -1, w3 = 1, T = -0.5 7 1 1 1 0 w1 + w2 + w3 < T

Switching Circuits & Logic Design 9


Properties of Threshold Gates
• A threshold gate is characterized by the weight threshold vector:
– V = {w1,w2, …,wn;T}

• A property:
– Let f (x1,x2, …,xn) be realized by V1 = {w1,w2, …,wj, …,wn;T}.
– If xj is complemented, f can be realized by V2 = {w1,w2, …,-wj, …,wn;T-wj} with inputs
x1, x2, …, xj’, …, xn .

Switching Circuits & Logic Design 10


• Another property:
– If f (x1,x2, …,xn) is realizable by a single threshold element with
V1 = {w1,w2, …,wn;T}, then its complement f’ is realizable by a single
threshold element with V2 = {-w1,-w2, …,-wn; -T} .

– From V1:

– Multiplying both sides by -1:

Switching Circuits & Logic Design 11


END OF LECTURE 30

Switching Circuits & Logic Design 12


Lecture 31: Latches and Flip-Flops (Part 1)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Introduction
• We shall now start our discussion on sequential circuits.
– Outputs depend not only on the present inputs, but also on the past history of the
system.
– The system memorizes the state in which it is in.
• How does the circuit memorize state?
– Using basic memory elements called latches and flip-flops.
• We shall be discussing various design alternatives for latches and flip-flops.

Switching Circuits & Logic Design 2


Basic Idea Behind Storing a Bit
• Consider a cascade of two inverters with feedback.
– Constitutes a stable state of the system.
– The circuit can memorize the output values as long as power is on.

• In practice, we need something more.


– We should be able to set the output values to 0 or 1 as per our requirement.
– Need some additional circuitry.
– The exact functionality distinguishes between different types of latches and flip-
flops.

Switching Circuits & Logic Design 3


Vin1 Vout1 = Vin2 Vout2

Vin1 = Vout2

Switching Circuits & Logic Design 4


Design of Latches
• A latch is a temporary storage device that has two stable states, 0 and 1.
– Level sensitive storage element (also called bistable multivibrator).
– A flip-flops is a special kind of latch where a clock signal triggers the change in the
stored value.
• Various types of latches:
– S-R (Set-Reset) type
– D (Delay) type
– J-K type
– T (Toggle) type

Switching Circuits & Logic Design 5


The Set-Reset (S-R) Latch
• Consists of a pair of cross-coupled NOR or NAND gates.
– Two inputs (S and R) and two outputs (Q and Q’).
– The output can be set to 0 or 1 by applying suitable values on S and R inputs.

S’ S R Q Q’
0 0 No change No change
0 1 0 1
1 0 1 0
R’ 1 1 ? ? Invalid

Switching Circuits & Logic Design 6


Why is S = R = 1 an invalid input?

S’

Logic symbol for R’


S-R latch

Switching Circuits & Logic Design 7


• Race condition:
– A scenario where the final result or output depends on the relative speeds of
various components (here gates).
– If we apply S = R = 1, and then apply S = R = 0, the outputs will settle to either Q =
0, Q’ = 1 or Q = 1, Q’ = 0 depending on the relative speeds of the two gates.

Switching Circuits & Logic Design 8


Gated S-R Latch
• A gated latch requires an enable input (E).
– When E = 1, the latch is active.
– When E = 0, the latch is de-active and the outputs do not change.
E S R Q Q’
0 X X NC NC
1 0 0 NC NC
1 0 1 0 1
1 1 0 1 0
1 1 1 ? ?

Switching Circuits & Logic Design 9


Gated S-R Latch :: Alternate Design

E S R Q Q’
0 X X NC NC
1 0 0 NC NC
1 0 1 0 1
1 1 0 1 0
1 1 1 ? ?

Switching Circuits & Logic Design 10


Gated D Latch
• A D-latch has a single input D.
– When the latch is enabled, the value at D gets stored in Q.
• A gated D-latch:

E D Q Q’
0 X NC NC
1 0 0 1
1 1 1 0

Switching Circuits & Logic Design 11


A D flip-flop using a S-R flip-flop

Switching Circuits & Logic Design 12


END OF LECTURE 31

Switching Circuits & Logic Design 13


Lecture 32: Latches and Flip-Flops (Part 2)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Notion of Clock
• A clock is a periodic (repetitive) rectangular pulse train that synchronizes the
operation of a synchronous sequential circuit.
• For synchronous operation, the storage elements must be clock triggered.
– Flip-flops (as opposed to latches, which are level triggered).

CLK

Switching Circuits & Logic Design 2


Edge-Triggered Flip-Flop
• An edge-triggered flip-flop changes its state in synchronism with a clock pulse.
– Either at the positive-edge or at the negative-edge.
– Useful in the design of synchronous sequential circuits, where all changes in the
circuit outputs occur in synchronism with the clock.

CLK

Time period f = frequency


ON period
OFF period T = time period
T=1/f

Switching Circuits & Logic Design 3


Edge-Triggered S-R Flip-Flop
Positive edge triggered state table
S Q CK S R Q Q’
CK 0/1 X X NC NC
R Q’  0 0 NC NC
Positive edge triggered  0 1 0 1
 1 0 1 0
S Q  1 1 ? ?
SR
CK Q(t) 00 01 11 10 Characteristic equation:
R Q’ 0 0 0 X 1 R.S = 0
Negative edge triggered Q(t+1) = R’.Q(t) + S
1 1 0 X 1

Switching Circuits & Logic Design 4


• Excitation table for S-R flip-flop:
Circuit changes Required value
From To S R
0 0 0 X
0 1 1 0
1 0 0 1
1 1 X 0

Switching Circuits & Logic Design 5


Timing Diagram Example

Switching Circuits & Logic Design 6


Edge-Triggered D Flip-Flop
Positive edge triggered state table
D Q
CK D Q Q’
CK 0/1 X NC NC
Q’  0 0 1
Positive edge triggered  1 1 0

D Q Characteristic equation:
Q(t+1) = D
CK
Q’
Negative edge triggered

Switching Circuits & Logic Design 7


• Excitation table for D flip-flop:
Circuit changes Required
value
From To D
0 0 0
0 1 1
1 0 0
1 1 1

Switching Circuits & Logic Design 8


Edge-Triggered J-K Flip-Flop
• The J-K flip-flop is the most versatile flip-flop.
– Like in S-R flip-flop, it has two inputs J and K, but does not have any invalid inputs.
Positive edge triggered state table
CK J K Q(t+1) Q(t+1)’
J Q
0/1 X X Q(t) Q(t)’
CK
 0 0 Q(t) Q(t)’
K Q’
 0 1 0 1
Positive edge triggered
 1 0 1 0
 1 1 Q(t)’ Q(t)

Switching Circuits & Logic Design 9


JK
Q(t) 00 01 11 10
0 0 0 1 1 Excitation Table
Circuit changes Required value
1 1 0 0 1
From To J K
Characteristic equation: 0 0 0 X

Q(t+1) = J.Q(t)’ + K’.Q(t) 0 1 1 X


1 0 X 1
1 1 X 0

Switching Circuits & Logic Design 10


Gate-Level Implementation of J-K Flip-Flop

CK acts like an enable input; edge detection circuit is not shown.

Switching Circuits & Logic Design 11


Edge-Triggered T Flip-Flop
T Q Positive edge triggered state table
CK CK T Q(t+1) Q(t+1)’

Q’ 0/1 X Q(t) Q(t)’

Positive edge triggered  0 Q(t) Q(t)’


 1 Q(t)’ Q(t)
T Q
Characteristic equation:
CK Q(t+1) = T ⊕ Q(t)
Q’
Negative edge triggered

Switching Circuits & Logic Design 12


Excitation Table
Circuit changes Required T J Q
value
CK
From To T
K Q’
0 0 0
0 1 1
1 0 1
1 1 0

Switching Circuits & Logic Design 13


END OF LECTURE 32

Switching Circuits & Logic Design 14


Lecture 33: Latches and Flip-Flops (Part 3)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Flip-flops with Asynchronous Preset and Clear
• It is often necessary to initialize a flip-flop to a known state before the circuit
operation starts.
– Preset (sets Q = 1) and Clear (sets Q = 0).
– These are asynchronous operations, and can be easily implemented by using
additional inputs on the cross-coupled gates.
• The term “asynchronous” means that it does not depend on the clock.

Switching Circuits & Logic Design 2


How is Edge Triggering Implemented?
• Why is edge triggering required?
– In latches with ENABLE input, the latch remains open as long as the ENABLE input is
active (if inputs change, outputs also change).
– Not desirable in many applications, where flip-flop outputs drive other circuits.
– One solution is to apply a very narrow ENABLE signal so that the circuit changes
state only once.

Switching Circuits & Logic Design 3


CK
Narrow ENABLE
pulse

A simple solution.
Width of the pulse depends on
the delay of the NOT gate. Drawback: circuit-
We can use any odd number of dependent delay
NOT gates.

Switching Circuits & Logic Design 4


A positive-edge triggered D flip-
flop.
Remembers the clock edge in
the cross-coupled latch in the
first stage.

Switching Circuits & Logic Design 5


Master-Slave Flip-Flops
• A master-slave flip-flop has two latch stages, called Master and Slave.
• Data gets stored in the Master stage one one edge or level of an control signal
(clock), and is transferred to the Slave on the other edge or level of the control
signal.
• Aims to address the problem in latches when the ENABLE signal may cause
multiple changes in the storage cell (for J-K and T types).
• Suffers from a problem called 0’s catching and 1’s catching that may be
undesirable for many applications.
– Edge-triggered versions are preferred in such cases.

Switching Circuits & Logic Design 6


(a) S-R master-slave flip-flop

Switching Circuits & Logic Design 7


(b) D master-slave flip-flop

Switching Circuits & Logic Design 8


(c) J-K master-slave flip-flop

Switching Circuits & Logic Design 9


Converting One Flip-Flop Type to Another

Switching Circuits & Logic Design 10


END OF LECTURE 33

Switching Circuits & Logic Design 11


Lecture 34: Clocking and Timing (Part 1)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Timing Issues
• For correct operation of a synchronous sequential circuit, several timing issues
need to be considered.
– Some of these issues relate to the properties of flip-flops.
– Some of these issues relate to circuits external to the flip-flops.

• All these taken together determines the maximum speed with which the
circuit can operate.
– Typically specified in terms of the clock frequency.

Switching Circuits & Logic Design 2


Some Definitions
• Clock width (tw): Minimum time duration for which the clock signal needs to be
high in order that the flip-flops it feeds work properly.

• Setup time (tsetup): Amount of time the input to a flip-flop must be stable before
the clock transitions high (for positive-edge triggered), or transitions low (for
negative-edge triggered).

• Hold time (thold): Amount of time the input to a flip-flop must be stable after the
clock transitions high (for positive-edge triggered), or transitions low (for negative-
edge triggered).

Switching Circuits & Logic Design 3


• Propagation delays (tp-lh and tp-hl): Delay between clocking event (low-to-high
or high-to-low transition) and change in the output.

Switching Circuits & Logic Design 4


tsetup thold
tsetup thold
D flip-flop
D

D Q tw
CLK

CLK Tp-lh
Q Tp-hl

Switching Circuits & Logic Design 5


Cascading Flip-flops
• Suppose that the flip-flop IN Q0 Q1
propagation delay exceeds the D Q D Q
hold time.
• Second stage can commit its
input before Q0 changes.
CLK

Switching Circuits & Logic Design 6


IN Q0 Q1
D Q D Q

IN
tsetup tsetup
CLK
Q0
tp-lh tp-hl
Q1
The correct
scenario CLK

thold thold

Switching Circuits & Logic Design 7


Edge-triggered Clocking
• Edge-triggered operation (either positive or negative edge triggered)
– Data leaving at time t must arrive at the next flip-flop one setup time before t+T,
where T is the clock period.

• Clocking relationships are relatively simple:


– Delay from each input flip-flop to each output flip-flop of a combinational block
should be less that (T – tsetup).

• Ideally, the clock signal should arrive all flip-flops at exactly the same time.
– In practice, clock skew exists.

Switching Circuits & Logic Design 8


Example 1
• Given a clock signal of frequency f Hz, how to generate another clock of
frequency f/2 Hz.
– Frequency division.

Switching Circuits & Logic Design 9


Example 2
• Given a clock signal of frequency f Hz, how to generate another clock of
frequency f/2k Hz, for some integer k.
– Frequency division by some power of 2.

Switching Circuits & Logic Design 10


END OF LECTURE 34

Switching Circuits & Logic Design 11


Lecture 35: Clocking and Timing (Part 2)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Minimum clock period T ?
tpINV = 2 ns
tpFF = 5 ns
tsetup = 3 ns

Switching Circuits & Logic Design 2


tpINV = 2 ns
tpFF = 5 ns
tsetup = 3 ns

Tmin = tpFF + tpINV + tsetup = 10 ns


fmax = 1 / Tmin = 100 MHz

thold does not affect the calculation here

Switching Circuits & Logic Design 3


Another Example

Switching Circuits & Logic Design 4


Clock Skew
• The clock signal may not reach all the flip-flops simultaneously.
– Due to unequal propagation delays along the various paths.
– During clock net design, we try to reduce clock skew as much as possible.

• It tskew denotes the maximum possible clock skew, then the minimum time
period should also include this tolerance.
– Tmin = tpFF + tpCOMB + tsetup + tskew
– Clock frequency can reduce further.

Switching Circuits & Logic Design 5


Static and Dynamic Hazards
• Hazards represent a momentary transition to the opposite logic value at the
output of a circuit.

• Two types of hazards are possible:


– Static Hazard: Indicates a momentary transition when the initial and final values
are the same.
• Examples: 0  1  0, or 1  0  1
– Dynamic Hazard: Indicates a momentary transition when the initial and final values
are different.
• Examples: 0  1  0  1, or 1  0  1  0

Switching Circuits & Logic Design 6


Examples Illustrating Hazards
A
S
F
S’
B

Delay of NOT = 1
Delay of AND, OR = 2

Switching Circuits & Logic Design 7


A Y
F

X
B

Delay of NOT = 1
Delay of NAND, NOR = 2

Switching Circuits & Logic Design 8


Serial Adder Example
• We have discussed the design of a parallel adder earlier.
• Suppose that the two input numbers are coming serially, one bit at a time
(LSB first).
– It is required to design a serial adder.

Switching Circuits & Logic Design 9


END OF LECTURE 35

Switching Circuits & Logic Design 10


Lecture 36: Synthesis of Synchronous Sequential
Circuits (Part 1)
PROF. INDRANIL SENGUPTA
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Introduction
• Combinational and Sequential Circuits
– In a combinational circuit, the outputs depend only on the applied input values and
not on the past history.
– In a sequential circuit, the outputs depend not only on the applied input values but
also on the internal state.
• The internal states also change with time.
• The number of states is finite, and hence a sequential circuit is also referred to as a Finite
State Machine (FSM).
• Most of the practical circuits are sequential in nature.

Switching Circuits & Logic Design 2


How are the States Stored and Changed?
• In a sequential circuit, we need some mechanism to store the internal states.
– We use flip-flops or latches to store the internal states.
– If we use k flip-flops, there can be a maximum of 2k internal states.
• Depending upon the way the states change, sequential circuits can be
categorized into two types:
a) Synchronous: The states change in synchronism with a clock pulse.
b) Asynchronous: There is no clock pulse for synchronism; all state changes occur
depending on the delays of the circuit elements (e.g. gates).

Switching Circuits & Logic Design 3


Finite State Machine (FSM)
• A FSM can be represented either in the form of a state table or in the form of a
state transition diagram.
– Variations exist, e.g. Algorithmic State Machine (ASM) chart.

• Example:
– A circuit to detect 3 or more 1’s in a serial bit stream.
– The bits are applied serially in synchronism with a clock.
– The output will become 1 whenever it detects 3 or more consecutive 1’s in the
stream.

Switching Circuits & Logic Design 4


State Table State Transition Diagram
Reset PS Input NS Output 0/0
1 - - A 0 0/0
0 A 0 A 0 A B
0 A 1 B 0 1/0
0 B 0 A 0 Reset
0/0 1/0
0 B 1 C 0
0 C 0 A 0 0/0
0 C 1 D 1
0 D 0 A 0 D C
1/1
0 D 1 D 1
1/1

Switching Circuits & Logic Design 5


More Formal Way to Write State Table
0/0
0/0
A B PS NS, Z
1/0 RX = 00 RX = 01 RX = 10 RX = 11
Reset A A,0 B,0 A,0 A,0
0/0 1/0
B A,0 C,0 A,0 A,0
0/0 C A,0 D,1 A,0 A,0
D A,0 D,1 A,0 A,0
D C
1/1 R: Reset
1/1 X: Input

Switching Circuits & Logic Design 6


Mealy and Moore FSM Types
• A deterministic FSM can be mathematically defines as a 5-tuple
M = (Σ, Γ, S, s0, δ, λ)
where Σ is the set of input combinations, Γ is the set of output combinations,
S is a finite set of states, s0 ε S is the initial state, δ is the state-transition
function, and λ is the output function.
• Here, δ : S x Σ  S
– Present state (PS) and present input determines the next state (NS).
• For Mealy machine, λ : S x Σ  Γ (output depends on state + inputs)
• For Moore machine, λ : S  Γ (output depends only on the state)

Switching Circuits & Logic Design 7


Pictorial Depiction

PI NS NS Output Mealy
F/F PS P
Logic Logic Machine
O

PI NS NS PS Output
P Moore
F/F
Logic Logic Machine
O

Switching Circuits & Logic Design 8


Model of Synchronous Sequential Machines
X1 Z1 Input variables X = {X1, X2, …, Xn}
Xn Combinational Zm Output variables Z = {Z1, Z2, …, Zm}
Logic State variables Y = {y1, y2, …, yk}
Input alphabet Σ :: set of 2n input patterns
y1 Y1 Output alphabet Γ :: set of 2m output patterns
y2 Y2 States S :: set of 2k k-tuples
Present State :: {y1, y2, …, yk}
yk Yk Next State :: {Y1, Y2, …, Yk}
Memory When clock comes, Next State gets copied to Present State.
elements

Switching Circuits & Logic Design 9


Synthesis of Synchronous Sequential Circuits
1. From a description of the problem, form a state diagram or state table.
2. Check whether the table contains any redundant states; if so, remove them.
– To be discussed later.
3. Select a state assignment and determine the type of memory elements.
– We can choose any type of memory elements (flip-flops) to maintain states.
– Final circuit complexity shall depend on this selection.
4. Derive transition and output tables.
5. Derive the excitation table, and obtain excitation and output functions.
6. Minimize the functions, and obtain the circuit diagram.

Switching Circuits & Logic Design 10


The Overall Flow Diagram
Problem Form state diagram Identify and eliminate State
Description / state table redundant states Assignment

Derive excitation table.


Obtain excitation and Derive transition and Select type of memory
output functions output tables elements

Draw the final circuit


diagram

Switching Circuits & Logic Design 11


END OF LECTURE 36

Switching Circuits & Logic Design 12


Lecture 37: Synthesis of Synchronous Sequential
Circuits (Part 2)
PROF. INDRANIL SENGUPTA
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
State Transition Diagram and State Table
• A state transition diagram specifies the different states of a FSM, the
conditions under which state changes occur, and the corresponding outputs.
– States are denoted as circles, and labeled with unique symbols.
– Transitions are represented as directed arrows between pair of states.
– Each transition is labeled by α/β, where α denotes an input combination and β
denotes an output combination.
• A state table is an alternate depiction of the state transition diagram.
– For every value of the present state, it specifies the next state and the output for
every input combination.

Switching Circuits & Logic Design 2


Example 1
• There are three lamps, RED, GREEN and YELLOW, that should glow cyclically
with a fixed time interval (say, 1 second).
• Some observations:
– The FSM will have three states, corresponding to the glowing state of the lamps.
– The input set is null; state transition will occur whenever clock signal comes.
– This is a Moore Machine, since the lamp that will glow only depends on the state
and not on the inputs (here null).
φ/010 RED φ/100
RED
clock GREEN φ/001
YELLOW GREEN YELLOW

Switching Circuits & Logic Design 3


PS NS, Z

RED RED GREEN, 010


φ/010 φ/100
GREEN YELLOW, 001
φ/001
GREEN YELLOW YELLOW RED, 100

State Transition Diagram State Table

Switching Circuits & Logic Design 4


Example 2
• Design of a serial parity detector.
– A continuous stream of bits is fed to a circuit in synchronism with a clock. The
circuit will be generating a bit stream as output, where a 0 will indicate “even
number of 1’s seen so far” and a 1 will indicate “odd number of 1’s seen so far”.
– Also a Moore Machine.

0/0 0/1
1/1
X
Z EVEN ODD
clk
Initial 1/0
state

Switching Circuits & Logic Design 5


NS, Z
PS
0/0 0/1 X=0 X=1
1/1
EVEN EVEN, 0 ODD, 1
EVEN ODD ODD ODD, 1 EVEN, 0
1/0
State Transition Diagram State Table

Switching Circuits & Logic Design 6


Example 3
• Design of a sequence detector.
– A circuit accepts a serial bit stream “X” as input and produces a serial bit stream “Z”
as output.
– Whenever the bit pattern “0110” appears in the input stream, it outputs Z = 1; at
all other times, Z = 0.
– Overlapping occurrences of the pattern are also detected.
– This is a Mealy Machine.
– Example: x :- 0 1 0 1 0 1 1 0 1 1 0 0 1 0 1 1 0 1 1 1 0
z :- 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0

Switching Circuits & Logic Design 7


X The input bits “X” are applied in
Z
clock synchronism with the clock.

reset
1/0
1/0 0/0
0/0 1/0 1/0
S0 S1 S2 S3

0/0
reset 0/1

Switching Circuits & Logic Design 8


Example 4
• A 2-bit serial adder which takes two serial bit streams X1 and X2 as inputs, and
generates a serial bit stream Z as output.
00/0 01/0
01/1 10/0
10/1 11/0 11/1
X1
X2 Z A B
clk 00/1

The state represents the carry; A means


carry is 0, B means carry is 1.

Switching Circuits & Logic Design 9


00/0 01/0 NS, Z
01/1 10/0 PS X= X= X= X=
10/1 11/0 11/1
00 01 10 11
A B A A, 0 A, 1 A, 1 B, 0
00/1 B A, 1 B, 0 B, 0 B, 1
State Transition Diagram State Table

Switching Circuits & Logic Design 10


Example 5
• A 3-bit binary counter that counts in the sequence 000, 001, 010, 011, 100, 101, 110,
111, and then back again to 000.
PS NS, Z
φ/000
S0 S7 S0 S1, 001
φ/001 φ/111 S1 S2, 010

S1 S6 S2 S3, 011
φ/010 φ/110 S3 S4, 100

S2 S5 S4 S5, 101
φ/011 φ/101 S5 S6, 110
S6 S7, 111
S3 S4
φ/100 S7 S0, 000

Switching Circuits & Logic Design 11


Example 6
• A 4-bit counter that counts in the sequence 0000, 0011, 0110, 1100, 1001, 1010, and
then back again to 0000. If the counter starts with any of the other states, it will go to
0000 at the next clock.

S1 S2 S4 S5 S7 S8 S11 S13 S14 S15

…….. φ/0000
φ/0000

S0 S3 S6 S12 S9 S10
φ/0011 φ/0110 φ/1100 φ/1001 φ/1010

φ/100
Switching Circuits & Logic Design 12
END OF LECTURE 37

Switching Circuits & Logic Design 13


Lecture 38: Synthesis of Synchronous Sequential
Circuits (Part 3)
PROF. INDRANIL SENGUPTA
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
FSM Synthesis
• We have seen how the state transition diagram / state table can be
constructed from the problem description.
• To construct the circuit, the following further steps are required:
a) Assign unique binary code to each state: state assignment.
b) Construct the transition/output table.
c) Select type of memory elements: SR or JK or D or T, and construct excitation table.
d) Obtain the excitation and output functions, and minimize them.
e) Realize the functions using gates or any other combinational circuit modules.
• We shall illustrate the process with examples.

Switching Circuits & Logic Design 2


Example 1: Serial Adder X1
X2 Z
clk

00/0 01/0
NS, Z
01/1 10/0 PS
10/1 11/0 11/1 X = 00 X = 01 X = 10 X = 11

A B A A, 0 A, 1 A, 1 B, 0

00/1 B A, 1 B, 0 B, 0 B, 1

State Transition Diagram State Table

Switching Circuits & Logic Design 3


• State assignment:
– Two states, and so one bit is sufficient.
– Suppose we assign 0 for state A, and 1 for state B.

NS, Z PS NS Output Z
PS
X = 00 X = 01 X = 10 X = 11 X1X2 00 01 10 11 00 01 10 11
0 0, 0 0, 1 0, 1 1, 0 0 0 0 0 1 0 1 1 0
1 0, 1 1, 0 1, 0 1, 1 1 0 1 1 1 1 0 0 1

After state assignment Transition/output Table

Switching Circuits & Logic Design 4


• Select memory element, and PS NS Output Z
construct excitation/output 00 01 10 11 00 01 10 11
function. 0 0 0 0 1 0 1 1 0
– Suppose we use D flip-flop.
1 0 1 1 1 1 0 0 1
Transition/output Table
X1
Z
X2 y NS (Y) Output Z
00 01 10 11 00 01 10 11
0 0 0 0 1 0 1 1 0
y Y
1 0 1 1 1 1 0 0 1
Excitation and Output Function

Switching Circuits & Logic Design 5


X1X2 X1X2 X1
Z
y 00 01 11 10 y 00 01 11 10 X2
0 1 0 1 1

1 11 1 1 1 1 1 1
y Y
Y = X1X2 + X1y + X2y Z = X1 ⊕ X2 ⊕ y

y NS (Y) Output Z
00 01 10 11 00 01 10 11
0 0 0 0 1 0 1 1 0
1 0 1 1 1 1 0 0 1

Switching Circuits & Logic Design 6


• Alternate design. PS NS Output Z
– Suppose we use SR flip-flop 00 01 10 11 00 01 10 11
0 0 0 0 1 0 1 1 0
1 0 1 1 1 1 0 0 1
Transition/output Table
X1
Z
X2 y SR Output Z
00 01 10 11 00 01 10 11
0 0X 0X 0X 10 0 1 1 0
y Y
1 10 00 00 00 1 0 0 1
Excitation and Output Function

Switching Circuits & Logic Design 7


X1X2 X1X2 X1
Z
y 00 01 11 10 y 00 01 11 10 X2
0 1 0 1 1
S
1 1 1 1 1 1 1
y R
S = X1X2y’ + X1’X2’y Z = X 1 ⊕ X2 ⊕ y
X1X2
y 00 01 11 10 y SR Output Z
0 X X X 00 01 10 11 00 01 10 11

1 1 0 0X 0X 0X 10 0 1 1 0
1 10 00 00 00 1 0 0 1
R=0

Switching Circuits & Logic Design 8


END OF LECTURE 38

Switching Circuits & Logic Design 9


Lecture 39: Synthesis of Synchronous Sequential
Circuits (Part 4)
PROF. INDRANIL SENGUPTA
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Example 2: Sequence Detector
• Design of a sequence detector.
– A circuit accepts a serial bit stream “X” as input and produces a serial bit stream “Z”
as output.
– Whenever the bit pattern “0110” appears in the input stream, it outputs Z = 1; at
all other times, Z = 0.
– Overlapping occurrences of the pattern are also detected.
X
Z
clock
– Example: X :- 0 1 0 1 0 1 1 0 1 1 0 0 1 0 1 1 0 1 1 1 0
Z :- 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0

Switching Circuits & Logic Design 2


1/0
1/0 0/0
0/0 1/0 1/0
S0 S1 S2 S3

0/0
0/1

PS NS, Z PS NS, Z PS NS Output Z


X=0 X=1 X=0 X=1 X=0 X=1 X=0 X=1
S0 S1, 0 S0, 0 00 01, 0 00, 0 00 01 00 0 0
S1 S1, 0 S2, 0 01 01, 0 10, 0 01 01 10 0 0
S2 S1, 0 S3, 0 10 01, 0 11, 0 10 01 11 0 0
S3 S1, 1 S0, 0 11 01, 1 00, 0 11 01 00 1 0

Switching Circuits & Logic Design 3


• Suppose we use T flip-flop.
– Two flip-flops, inputs T1 and T2.

PS NS Output Z y1y2 T1 T2 Z
X=0 X=1 X=0 X=1 X=0 X=1 X=0 X=1
00 01 00 0 0 00 01 00 0 0
01 01 10 0 0 01 00 11 0 0
10 01 11 0 0 10 11 01 0 0
11 01 00 1 0 11 10 11 1 0

Switching Circuits & Logic Design 4


y1y2 T1 T2 Z
X=0 X=1 X=0 X=1
00 01 00 0 0
01 00 11 0 0
10 11 01 0 0
11 10 11 1 0
y1y2 y1y2 y1y2
X 00 01 11 10 X 00 01 11 10 X 00 01 11 10
0 1 1 0 1 1 0 1

1 1 1 1 1 1 1 1 1

T1 = X’ y1 + X y2 T2 = X’ y2’ + y1 y2’ + X y2 Z = X’ y1 y2

Switching Circuits & Logic Design 5


• Let us repeat the process using J-K flip-flop.

PS NS Output Z y1y2 J1 K1 J2 K2 Z
X=0 X=1 X=0 X=1 X=0 X=1 X=0 X=1
00 01 00 0 0 00 0X 1X 0X 0X 0 0
01 01 10 0 0 01 0X X0 1X X1 0 0
10 01 11 0 0 10 X1 1X X0 1X 0 0
11 01 00 1 0 11 X1 X0 X1 X1 1 0

Switching Circuits & Logic Design 6


y1y2 J1 K1 J2 K2 Z
X=0 X=1 X=0 X=1
00 0X 1X 0X 0X 0 0
01 0X X0 1X X1 0 0
10 X1 1X X0 1X 0 0
11 X1 X0 X1 X1 1 0

Switching Circuits & Logic Design 7


END OF LECTURE 39

Switching Circuits & Logic Design 8


Lecture 40: Minimization of Finite State Machines
(Part 1)
PROF. INDRANIL SENGUPTA
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Elimination of Redundant States
• Basic concept:
– Identify equivalent states and merge them into a single state.
– Can lead to more compact representation.
• State Equivalence:
– Two states Si and Sj of a FSM are said to be equivalent iff for every single input
sequence X, the outputs are the same and the next states are equivalent:
λ (Si, X) = λ (Sj, X)
δ (Si, X) ≅ δ (Sj, X)
where λ (Si, X) is the output for the present state Si and input X, and δ (Si, X) is the
corresponding next state.

Switching Circuits & Logic Design 2


Minimization Using Implication Table
1. Construct an Implication Chart that contains a square for every pair of states.
2. Compare each pair of rows in the State Table. If the outputs associated with states i and
j are different, place an ‘x’ in square i-j to indicate i and j are not equivalent.
If the outputs are the same, place the Implied Pairs in square i-j. (If the next states of i
and j are m and n respectively for some input X, then m-n is an implied pair)
If the outputs and the next states are the same (or if i-j only implies itself), place a
check (✓) in square i-j to indicate i and j are equivalent.
3. Go through the table square by square. If square i-j contains the implied pair m-n, and
square m-n contains a ‘x’, then i and j are not equivalent, and place a ‘x’ in square i-j.

Switching Circuits & Logic Design 3


4. If any ‘x’ is added in Step 3, repeat Step 3 until no more ‘x’ can be added.
5. For each square i-j that does not contain ‘x’, the states i and j are equivalent.

Switching Circuits & Logic Design 4


Example 1: A Moore Machine B
State Table
PS NS Output C
X=0 X=1 z
D
A D C 0
B F H 0 E
C E D 1
F
D A E 0
E C A 1 G
F F B 1
G B H 0 H
H C G 1 A B C D E F G

Switching Circuits & Logic Design 5


D-F D-F
B B
C-H C-H

C x x C x x After first
Initial
pass
A-D A-F A-F
D x D C-E x
C-E E-H E-H
C-E
E x x x E x x A-D x
A-D
E-F C-F E-F C-F
F x x x F x x x
B-D A-B B-D A-B
B-D A-B B-D A-B
G B-F x x x G B-F x x x
C-H E-H C-H E-H
C-E C-F C-E C-F
H x x x A-G x H x x x A-G x
D-G B-G D-G B-G
A B C D E F G A B C D E F G

Switching Circuits & Logic Design 6


D-F
B
C-H
After Reduced State Table
C x x
second pass PS NS Output
A-F
D C-E x X=0 X=1 z
E-H
A A C 0
E x x A-D x
B F H 0
E-F C-F
F x x x C C A 1
B-D A-B
B-D A-B F F B 1
G B-F x x x
C-H E-H G B H 0
C-E C-F H C G 1
H x x x A-G x
D-G B-G
A B C D E F G

Switching Circuits & Logic Design 7


Example 2: A Mealy Machine
State Table
PS NS, z B x B x
X=0 X=1
C B-D x C B-D x
A E, 0 D, 1
B F, 0 D, 0 D x ✓ x D x ✓ x
C E, 0 B, 1 C-E C-E C-E
D F, 0 B, 0
E x x E x B-F x
D-F B-F D-F
E C, 0 F, 1 B-F B-F B-F
F x x x F x C-D x x
F B, 0 C, 0
C-D B-C B-C
A B C D E A B C D E

Switching Circuits & Logic Design 8


State Table
PS NS, z B x B x
X=0 X=1
C B-D x C B-D x
A E, 0 D, 1
B F, 0 D, 0 D x ✓ x D x ✓ x
C E, 0 B, 1 C-E C-E
D F, 0 B, 0
E x x x E x x x
D-F D-F
E C, 0 F, 1 F x x x x x F x x x x x
F B, 0 C, 0
A B C D E A B C D E

Switching Circuits & Logic Design 9


B x Reduced State Table
PS NS, z
C ✓ x
X=0 X=1
D x ✓ x A E, 0 B, 1
B F, 0 B, 0
E x x x x E A, 0 F, 1
F B, 0 A, 0
F x x x x x
A B C D E

Switching Circuits & Logic Design 10


END OF LECTURE 40

Switching Circuits & Logic Design 11


Lecture 41: Minimization of Finite State Machines
(Part 2)
PROF. INDRANIL SENGUPTA
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Equivalent FSMs
• Two finite state machines N1 and N2 are said to be equivalent if for every state
p in N1, there is a state q in N2 such that p and q are equivalent; and
conversely, for each state s in N2, there is a state t in N1, such that s and t are
equivalent.
• An approach similar to implication tables can be used to verify equivalence.

Switching Circuits & Logic Design 2


An Example
• Consider two FSMs N1 and N2, whose reduced state tables are shown.
• We shall create a 4 x 4 implication chart to test state equivalence.

PS NS, z PS NS, z
X =0 X=1 X =0 X=1
A B, 0 A, 0 S0 S3, 0 S1, 0
B C, 0 D, 1 S1 S3 0 S0, 1
C A, 0 C, 1 S2 S0, 0 S2, 1
D C, 0 B, 0 S3 S2, 0 S3, 0
N1 N2

Switching Circuits & Logic Design 3


PS NS, z PS NS, z
X =0 X=1 X =0 X=1
A B, 0 A, 0 S0 S3, 0 S1, 0
B C, 0 D, 1 S1 S3 0 S0, 1
C A, 0 C, 1 S2 S0, 0 S2, 1
D C, 0 B, 0 S3 S2, 0 S3, 0

C-S3 A-S3 C-S3 A-S3


S0 x x S0 x x
D-S1 C-S1 D-S1 C-S1 Equivalent states:
S1
B-S3
x x
C-S3
S1
B-S3
x x
C-S3 A – S2
A-S0 B-S0 A-S0 B-S0 B – S0
B-S0 C-S0 B-S0 C-S0 C – S3
S2 x x S2 x x
A-S2 B-S2 A-S2 B-S2 D – S1
C-S2 A-S2 C-S2 A-S2
S3 x x S3 x x
D-S3 C-S3 D-S3 C-S3
A B C D A B C D

Switching Circuits & Logic Design 4


PS NS, z Another Example
X =0 X=1
S0 S5, 0 S1, 0
S1 S5, 0 S6, 0
S2 S2, 0 S6, 0 PS NS, z
S3 S0, 1 S1, 0 X =0 X=1
S4 S4, 0 S3, 0 A A, 0 B, 0
S5 S0, 0 S1, 0 B A, 0 C, 0
S6 S5, 1 S1, 0 C A, 1 B, 0
Machine N1 Machine N2

Switching Circuits & Logic Design 5


Incompletely Specified Machines
• The number of input combinations that can be applied may be a subset of all
possible input combinations.
– Other input combinations may be treated as don’t cares.
• A FSM where the next state and output are not specified for all input
combinations, is said to be incompletely specified.
– We can extend the approach already discussed by adding don’t cares to take care
of this situation.

Switching Circuits & Logic Design 6


An Example
x z
Circuit A Sequential Circuit B Circuit C

• Assume that circuit A can only generate two possible output sequences, x = 100 and 110.
• After the sequence is received, the output of B will be z = 0 if 100 was received, and z = 1
if 110 was received.
– Assume that circuit C ignores the value of z at all other times.
0,0 S2
PS NS, z
t t1 t2 t0 t1 t2 0,-
x=0 x=1 1,-
0 S0 S1
x= 1 0 0 z - - 0 S0 -, - S1, - 1,-
= S1 S2, - S3, -
0,1 S3
1 input/output
Possible 1 0 - -
sequences 1 S2 S0, 0 -, -
S3 S0, 1 -, -
Switching Circuits & Logic Design 7
• We can fill up the don’t cares suitably, so that the number of states can be reduced
using row matching.
0,0 1,-
0,0 S2 1,-
S1 x S0 S1
0,-
1,- 0,1
S0 S1 S2 ✓ x
1,-

0,1 S3 S3 x S2-S0 x
PS NS, z
PS NS, z S0 S1 S2 x=0 x=1
x=0 x=1
S0, S2 are equivalent S0 S0, 0 S1, -
S0 S0, 0 S1, -
S1, S3 are equivalent S1 S0, 1 S1, -
S1 S2, 1 S3, -
S2 S0, 0 S1, -
S3 S0, 1 S3, -
Switching Circuits & Logic Design 8
END OF LECTURE 41

Switching Circuits & Logic Design 9


Lecture 42: Design of Registers (Part 1)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Introduction
• A register consists of a group of flip-flops with a common clock input, used for
storing binary data.
• Depending on the configuration, there can be several different variations:
a) Parallel-in parallel-out (PIPO)
b) Serial-in serial-out (SISO)
c) Parallel-in serial-out (PISO)
d) Serial-in parallel-out (SIPO)
• If the register supports serial-in and serial-out modes, it is also called a shift
register.

Switching Circuits & Logic Design 2


Basic PIPO Register
D1 D2 D3 D4
D Q D Q D Q D Q

CLR CLR CLR CLR


’ ’ ’ ’
CLR
CLK

Q1 Q2 Q3 Q4
When the active clock edge arrives,
input word D1D2D3D4 gets stored in
the register, and available on the
outputs Q1Q2Q3Q4.

Switching Circuits & Logic Design 3


Symbolic Representation (using vector notation)
D
4

CLK PIPO CLR’

4
Q

Switching Circuits & Logic Design 4


Addition of LOAD signal
• In practice, the clock is coming continuously, and there is a separate signal
LOAD that specifies when the register is to be loaded with new data.
• Two possible solutions:
a) Use a gated clock:
• Not a good solution, as gating the clock with another signal can cause timing problems.

CLK
To clock inputs of the flip-flops
LOAD

Switching Circuits & Logic Design 5


b) Separate out CLK and LOAD using a multiplexer circuit.
– Better and recommended solution.
– Each flip-flop in the register gets replaced by:
D
D1 Q1
4
LOAD MUX LOAD
CLK PIPO CLR’
D Q
4
CLK
CLR Q

CLR

Switching Circuits & Logic Design 6
Addition of ENABLE input
• Many registers have an ENABLE input that can be used to force the output
lines into high impedance state, if desired.
– We need a tri-state buffer with every flip-flop output.

D1 D Q Q1
CLK
CLR
ENABLE

CLR

Switching Circuits & Logic Design 7


• Why is the ENABLE input required?
– To resolve bus conflicts in bus-based architectures.
– An example scenario:
• RA, RB, RC, RD are k-bit registers.
ENA k • Exactly one of the three enable
RA inputs must be activated at any
k given time.
k
ENB k ADDER RD • CLK is fed in parallel to all the
RB
registers.
k
ENC k • If ENA=1, RD = RD + RA
RC
• If ENB=1, RD = RD + RB
• If ENC=1, RD = RD + RC

Switching Circuits & Logic Design 8


PIPO Register using CMOS Dynamic Logic
• In dynamic storage cell, information is stored not in flip-flops, but as charge
stored on tiny capacitors.
– Charge tends to leak away with time; and therefore needs refreshing mechanism.
– Basic register structure, where X is a CMOS transmission gate:

D1 X Q1

Dk X Qk

CLK/LOAD

Switching Circuits & Logic Design 9


• For tri-state control, we can use another X-gate on the output side.
D1 X X Q1

Dk X X Qk

CLK/LOAD ENABLE

Switching Circuits & Logic Design 10


• For implementing refreshing logic, several solutions are possible.
• A simple solution is shown below for a single flip-flop stage:

X
Refresh operation is
CLK’ carried out in every
clock period when
D1 X X Q1 CLK = 0.

CLK/LOAD ENABLE

Switching Circuits & Logic Design 11


END OF LECTURE 42

Switching Circuits & Logic Design 12


Lecture 43: Design of Registers (Part 2)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Shift Register
• A shift register is a register in which the binary data can be stored, and the
data can be shifted to the left (or right) when a shift signal is applied.
– New bit gets shifted in; bit shifted out typically get lost.
• Can be constructed simply by connecting D, SR or JK flip-flops in cascade.
• A 4-bit shift register is shown below:
Serial In Serial
(SI) D1 Q1 D2 Q2 D3 Q3 D4 Q4 Out
(SO)

CLK

Switching Circuits & Logic Design 2


• Some shift registers have a shift enable signal SHIFT, which is used in the same
way as the LOAD signal of a PIPO register.
– Sample timing diagram is shown, assuming that the initial state is Q1Q2Q3Q4 =
0101.
CLK

SI

Q1 0 1 1 0 1

Q2 1 0 1 1 0
Q3 0 1 0 1 1
Q4 1 0 1 0 1

Switching Circuits & Logic Design 3


Variations of Shift Registers
• Depending upon the way the various stages are connected, there can be
various types of shift registers:
a) Ring counter
b) Twisted ring or Johnson counter
c) Bidirectional shift register
d) Universal shift register
e) Linear feedback shift register

Switching Circuits & Logic Design 4


(a) Ring Counter
• This is obtained from a SISO shift register by connecting the Q output of the
last flip-flop to the D input of the first flip-flop.
– Typically, a ring counter is initialized with a single 1 and all remaining 0’s.
– This can generate multi-phase clock, or sequence of synchronizing pulses.
• For a k-bit ring counter, the contents of the register gets repeated after k
clocks.
– Modulo-k counter.

Switching Circuits & Logic Design 5


D1 Q1 D2 Q2 D3 Q3 A 3-bit ring counter.
Assume the initial state
Q1Q2Q3 = 1 0 0.
CLK

CLK

Q1

Q2
Q3

Q1Q2Q3 generates non-overlapping pulse trains

Switching Circuits & Logic Design 6


(b) Twisted Ring or Johnson Counter
• This is obtained from a SISO shift register by connecting the Q’ output of the
last flip-flop to the D input of the first flip-flop.
– The Johnson counter can be initialized to the all-0 state.
– The 0’s and 1’s are consecutive in the generated patterns (may be required for
some applications).
• For a k-bit Johnson counter, the contents of the register gets repeated after 2k
clocks.
– Modulo-2k counter.

Switching Circuits & Logic Design 7


D1 Q1 D2 Q2 D3 Q3 D4 Q4

Q4’

CLK

Clocks 1 2 3 4 5 6 7 8 9
Q1 0 1 1 1 1 0 0 0 0 … … A 4-bit Johnson counter.
Q2 0 0 1 1 1 1 0 0 0 … … Assume the initial state
Q3 0 0 0 1 1 1 1 0 0 … … Q1Q2Q3Q4 = 0 0 0 0.
Q4 0 0 0 0 1 1 1 1 0 … …

Switching Circuits & Logic Design 8


(c) Bidirectional Shift Register
• Based on a control input, the shift register works in either the shift-right or the
shift-left modes.
• Multiplexers are used to feed the appropriate signals to the D inputs of the flip-
flops.
– A control input L/R’ selects the multiplexer inputs.
– Determines whether to shift left or to shift right.

Switching Circuits & Logic Design 9


SI Q2 Q1 Q3 Q2 Q4 Q3 SI
0 1 0 1 0 1 0 1
MUX L/R’ MUX L/R’ MUX L/R’ MUX
L/R’

D1 Q1 D2 Q2 D3 Q3 D4 Q4

CLK

A 4-bit bidirectional shift register

Switching Circuits & Logic Design 10


(d) Universal Shift Register
• A universal shift register is a bidirectional shift register, whose input can be
either in serial form or in parallel form, and whose output can also be either in
serial form or in parallel form.
D Control Action
k Inputs
0 0 No change
Shift Right SI S1
Shift Left SI Universal Shift Register 0 1 Shift right
S0
CLK
1 0 Shift left
k
1 1 Parallel load
Q

Switching Circuits & Logic Design 11


D1 D2 D3
SI SI
Q1 (right) Q2 Q2 Q1 Q3 Q3 Q2 (left)

S1 S1 S1
MUX MUX MUX
S0 S0 S0

D1 Q1 D2 Q2 D3 Q3

CLK
A 3-bit universal shift register

Switching Circuits & Logic Design 12


END OF LECTURE 43

Switching Circuits & Logic Design 13


Lecture 44: Design of Registers (Part 3)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
(e) Linear Feedback Shift Register (LFSR)
• It is basically a SISO right shift register, where the serial input is generated as a
linear combination (exclusive-OR) of some of the flip-flop outputs.

D1 Q1 D2 Q2 D3 Q3 D4 Q4

CLK

Switching Circuits & Logic Design 2


D1 Q1 D2 Q2 D3 Q3 D4 Q4

CLK

CLK pulses 0 1 2 3 4 5 6 7 8 9 10 11
Q1 0 1 1 1 1 0 1 0 1 0 0 0 …
Q2 0 0 1 1 1 1 0 0 0 1 0 0 …
Q3 0 0 0 1 1 1 1 1 0 0 1 0 …
Q4 1 0 0 0 1 1 1 1 1 0 0 1 …

Switching Circuits & Logic Design 3


• The LFSR is typically initialized to 1 0 0 … 0.
• If the taps are properly chosen, an n-bit LFSR can generate 2n-1 distinct
patterns without repeating.
– The all-0 pattern cannot be generated.
• The LFSR generated patterns has very good randomness.
– Useful in many applications.

Switching Circuits & Logic Design 4


Some Applications of Registers
1. Parallel-to-serial and serial-to-parallel conversion for data transmission
– Many device-to-device communication protocols use serial data transmission.
– Advantages: less number of wires, higher reliability, lower cost, etc.
– Data generators and receivers typically handle data in parallel.
– We require conversion, which can be done using shift registers.

Switching Circuits & Logic Design 5


2. Use in data path for performing calculations
– For implementing complex systems, we typically break the design into two parts:
(a) Data Path design, and (b) Control Path design.
– The Data Path contains the basic hardware units for performing calculation and
storage (e.g. combinational circuits modules like adders, multipliers, comparators,
multiplexers, etc. and storage elements like registers).
– The Control Path is a FSM that generates the control signals for the Data Path in
proper sequence to carry out the required operation.

Switching Circuits & Logic Design 6


Example 1: Multiplication by Repeated Addition
• We consider a simple algorithm using START
repeated addition.
– Assume B is non-zero. Read A, B
• We identify the functional blocks
required in the data path, and the P=0
corresponding control signals.
P=P+A No
• Then we design the FSM to
implement the multiplication Yes
algorithm using the data path. B=B–1 B=0 STOP

Switching Circuits & Logic Design 7


Bus

LdP LdB
LdA A P B
clrP decB

X Y
COMP

ADDER eqz

DATA PATH Z data_in

Switching Circuits & Logic Design 8


LdA
LdB
data_in
LdP
clrP

DATA PATH decB CONTROL PATH start

done

eqz

clk

Switching Circuits & Logic Design 9


START S0
CONTROL S0
start
PATH A = data_in S1
S1
B = data_in S2
P=0
S2
P=Z
B=B–1 S3
!eqz
Bout = No S3
0 eqz
Yes
done = 1 S4 S4

Switching Circuits & Logic Design 10


Example 2: GCD Computation by Repeated Subtraction
• We consider a simple algorithm using START
repeated subtraction.
Read A, B
• We identify the functional blocks
required in the data path, and the
corresponding control signals. < >
B=B–A A:B A=A–B
• Then we design the FSM to =
implement the GCD computation
Output A
algorithm using the data path.
STOP

Switching Circuits & Logic Design 11


Bus

LdA A B LdB

Aout Bout

sel1 MUX COMP MUX sel2 MUX sel_in

X lt gt eq Y
DATA PATH data_in
SUBTRACTOR
SubOut

Switching Circuits & Logic Design 12


LdA
LdB
data_in
sel1
sel2

DATA PATH sel_in CONTROL PATH start


LT
done
GT
EQ

clk

Switching Circuits & Logic Design 13


START S0
S0
CONTROL S1 start
A = data_in
PATH
S1
B = data_in S2

< > S2 S5
Aout : Bout
= LT
X = Bout X = Aout GT
LT GT
S3 Y = Aout done = 1 Y = Bout S4
B = SubOut A = SubOut S3 GT S4
S5 LT

Switching Circuits & Logic Design 14


END OF LECTURE 44

Switching Circuits & Logic Design 15


Lecture 45: Design of Counters (Part 1)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Binary Counter
• A binary counter is a set of flip-flops whose states change in response to pulses
applied at the input to the counter.
– The combined state of the flip-flops at any time is the binary equivalent of the total
number of pulses that have been applied.
• Counters are of two types:
a) Asynchronous counter
b) Synchronous counter

Switching Circuits & Logic Design 2


Asynchronous Counter (Ripple Counter)
• This type of counter is the easiest to design, and requires the least amount of
hardware.
• The counter is called asynchronous because the flip-flops are not driven by the same
clock signal, and hence do not change state simultaneously.
– Constructed using T flip-flops.
• It is called ripple counter because when the counter, for example, goes from 1111 to
0000, it temporarily goes through a number of intermediate states:
1111  0111  0011  0001  0000.
– Can lead to unwanted transitions if the outputs drive some other circuit.
– Glitches are possible.

Switching Circuits & Logic Design 3


Synchronous Counter
• In this kind of counter, the same clock signal feeds all the flip-flops.
– All the flip-flops change state simultaneously in synchronism with the clock pulse.
– No glitches in the outputs.
– Faster than asynchronous counters, but require more hardware for
implementation.
• Can be designed using the FSM design methodology discussed earlier.

Switching Circuits & Logic Design 4


Design of 4-bit Ripple Counter (Up Counting)
• We make an observation: 0: 0000 8: 1 0 0 0
– During counting, whenever a bit 1: 0001 9: 1 0 0 1
position changes from 1 to 0, the 2: 0010 10: 1 0 1 0
next higher bit position changes 3: 0011 11: 1 0 1 1
state. 4: 0100 12: 1 1 0 0
– This feature can be directly 5: 0101 13: 1 1 0 1
implemented using a T flip-flop with 6: 0110 14: 1 1 1 0
negative-edge triggered clock. 7: 0111 15: 1 1 1 1

Switching Circuits & Logic Design 5


1 T0 Q0 1 T1 Q1 1 T2 Q2 1 T3 Q3
CLK

Q0 Q1 Q2 Q3

If we are designing an up counter using positive edge-triggered T flip-flops, we


simply connect the Q’ output of a stage to the clock input of the next stage.

Switching Circuits & Logic Design 6


Timing Diagram

CLK

Q0

Q1

Q2

Q3

Switching Circuits & Logic Design 7


• Some observations:
– Suppose f denotes the frequency of the pulse train applied at CLK input.
– Then, frequency of pulse train at Q0 = f/2
– Frequency of pulse train at Q1 = f/4
– Frequency of pulse train at Q2 = f/8
– Frequency of pulse train at Q3 = f/16
• An n-bit binary counter is also called modulo-2n counter or divide-by-2n
counter.

Switching Circuits & Logic Design 8


Transient States During Counting
• Consider a 3-bit ripple counter.
• The normal counting sequence is: 000, 001, 010, 011, 100, 101, 110,110, 000, …
• However, in practice, because of the delays of the T flip-flops, there are several
transient states (shown in pink) that appear.

000 001 000 010 011 010 000

100 110 111 110 100 101 100

Switching Circuits & Logic Design 9


Design of 4-bit Ripple Counter (Down Counting)
• We make an observation: 15: 1111 7: 0111
– During counting, whenever a bit 14: 1110 6: 0110
position changes from 0 to 1, the 13: 1101 5: 0101
next higher bit position changes 12: 1100 4: 0100
state. 11: 1011 3: 0011
– This feature can be directly 10: 1010 2: 0010
implemented using a T flip-flop with 9: 1001 1: 0001
positive-edge triggered clock. 8: 1000 0: 0000

Switching Circuits & Logic Design 10


• If we use negative edge-triggered T flip-flops:
– Connect Q’ output of a stage to CLK input of next stage.
• If we use positive edge-triggered T flip flops:
– Connect Q output of a stage to CLK input of next stage.

Switching Circuits & Logic Design 11


END OF LECTURE 45

Switching Circuits & Logic Design 12


Lecture 46: Design of Counters (Part 2)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Design of Binary Ripple Counter of any Arbitrary Modulus
• Suppose we want to design a modulo-M counter, for any arbitrary value of M.
– Counter will count up from 0 to M-1, and then back to 0.
• Assume that the flip-flops have individual asynchronous CLR’ inputs.
• Basic idea:
– We first design a ripple counter with log2M stages.
– Then we design a gating circuit, which takes inputs from the counter outputs, and
generates a 0 whenever the count value reaches M.
– Connect the output of the gating circuit to the CLR’ inputs of the flip-flops.

Switching Circuits & Logic Design 2


Example: Design of a modulo-6 binary ripple counter
• Number of flip-flop stages required will be log26 = 3
• The desired count sequence will be: 000, 001, 010, 011, 100, 101, 000, …
– From state 101, instead of going to the state 110, we have to bring the state back
to 000.

1 T0 Q0 1 T1 Q1 1 T2 Q2
CLK
CLR’ CLR’ CLR’

Q0 Q1 Q2

Switching Circuits & Logic Design 3


Timing Diagram :: Input frequency is getting divided by 6 at output Q2

CLK

Q0

Q1

Q2

Switching Circuits & Logic Design 4


Example: Design of a decade (modulo-10) counter

1 T0 Q0 1 T1 Q1 1 T2 Q2 1 T3 Q3
CLK

Q0 Q1 Q2 Q3

Switching Circuits & Logic Design 5


Cascading of Ripple Counters
• If a modulo-M and a modulo-N counter are connected in cascade, the
combination will count modulo-MN.

Input Modulo-M Modulo-N f/(MN)


Clock f Counter Counter

f/M

Switching Circuits & Logic Design 6


Example: Design a modulo-1000 counter using decade
counters

Switching Circuits & Logic Design 7


Example: Design a digital clock

Switching Circuits & Logic Design 8


END OF LECTURE 46

Switching Circuits & Logic Design 9


Lecture 47: Digital-to-Analog Converter (Part 1)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Interfacing with the Analog World
a) Transducer: converts physical variable to electrical variable.
b) Analog-to-digital converter (ADC)
c) Digital System (computer)
d) Digital-to-analog converter (DAC)
e) Actuator To control
physical
variable
Physical Digital
variable Transducer ADC DAC Actuator
System

Switching Circuits & Logic Design 2


VREF = 15 V
Digital-to-Analog Converter (DAC) D3 D2 D1 D0 VOUT
0 0 0 0 0V
• Converts a given digital word D to a proportional 0 0 0 1 1V
analog voltage VOUT. 0 0 1 0 2V
0 0 1 1 3V
VOUT α D 0 1 0 0 4V
0 1 0 1 5V
0 1 1 0 6V
VREF
0 1 1 1 7V
1 0 0 0 8V
1 0 0 1 9V
D3 1 0 1 0 10 V
Digital D2 D/A Converter Analog 1 0 1 1 11 V
inputs D1 output 1 1 0 0 12 V
(DAC) 1 1 0 1 13 V
D VOUT
D0 1 1 1 0 14 V
1 1 1 1 15 V

Switching Circuits & Logic Design 3


Analog Output Signal

VOUT

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011
D
Digital Input Signal

Switching Circuits & Logic Design 4


Some Parameters of DAC
a) Resolution or step size:
– Smallest change that can occur in VOUT as a result of a change in input D.
• Equal to the weight of the LSB, also called step size.
• Same as the constant of proportionality in VOUT α D

– Can also be defined as a percentage of the full-scale voltage:


% resolution = step size / VREF x 100
= 1 / (total number of steps) x 100
= 1 / (2N – 1) x 100, for an N-bit DAC

Switching Circuits & Logic Design 5


Clock Binary Counter

D/A Converter

Switching Circuits & Logic Design 6


b) Gain Error:
– Occurs when the slope of the actual output deviates from the slope of the ideal
output.

Analog Output

Digital Input

Ideal Output Positive Offset Errorr Negative Offset Error

Switching Circuits & Logic Design 7


c) Offset Error:
– Occurs when there is a constant offset between the actual output and the ideal
output.

Analog Output

Digital Input

Ideal Output Positive Offset Errorr Negative Offset Error

Switching Circuits & Logic Design 8


d) Non-Linearity Error:
– Occurs when analog output of signal is non-linear.

Linearity (Ideal) Non-Linearity


Analog Output Signal

Analog Output Signal


0000 0001 0010 0011 0100 0101 0000 0001 0010 0011 0100 0101
Digital Input Signal Digital Input Signal

Switching Circuits & Logic Design 9


e) Monotonicity Error:
– Occurs when an increase in digital input results in a decrease in analog output.

Analog output signal

Digital input signal

Switching Circuits & Logic Design 10


f) Settling Time and Overshoot
Error: Analog
– Settling Time is the time required for Output +1/2*VLSB
the output to fall within ± ½ VLSB.
Ideal
– Overshoot occurs when analog output
Output
overshoots the ideal output.

-1/2*VLSB

Settling
Time
Time

Switching Circuits & Logic Design 11


END OF LECTURE 47

Switching Circuits & Logic Design 12


Lecture 48: Digital-to-Analog Converter (Part 2)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Introduction
• We shall discuss two different designs of digital-to-analog converters.
a) Weighted resistor type DAC
b) Resistive ladder type DAC
• The first type is easier to analyze, while the second type is more practical from
the point of view of implementation.

Switching Circuits & Logic Design 2


Weighted Resistor Type DAC
• For an n-bit DAC, it consists of n different resistance values of magnitudes
R, 2R, 4R, …, 2n-1R respectively.
– The resistances help in generating currents inversely proportional to their
magnitudes.
– The total current is added up by an operational amplifier, and is converted to the
voltage output VOUT.
• Main drawback:
– A different-valued precision resistor must be used for each bit position of the
digital input.

Switching Circuits & Logic Design 3


D3
R VOUT = - [D3 + D2 / 2 + D1 / 4 + D0 / 8] Rf / R
D2 = - [8D3 + 4D2 + 2D1 + D0] Rf / 8R
2R
αD
D1
4R

D0
8R

Switching Circuits & Logic Design 4


Resistive Ladder Type DAC
• Most widely used, and requires only two different values of precision
resistances (R and 2R).

D0 D1 D2 D3 Voltage
Follower
2R 2R 2R 2R

+ VOUT
2R R R R -

Switching Circuits & Logic Design 5


Calculation
• Let us calculate the voltages at the opamp input when exactly one of the Di
inputs is at 1 (say, +V volts).
• Case 1: Input is 1000.

GND GND GND +V +V

2R
Vx = V / 2
2R 2R 2R 2R
Vx Vx
2R R R R 2R

Switching Circuits & Logic Design 6


• Case 2: Input is 0100.
GND GND +V GND +V GND

2R 2R 2R 2R 2R 2R
Vx Vx
2R R R R 2R R

GND GND
Thevenin’s Vx = V / 4
theorem 2R 2R
+V/2 Vx +V/2 Vx
R R 2R

Switching Circuits & Logic Design 7


• Case 3: Input is 0010.
GND +V GND GND GND GND
Thevenin’s
2R 2R 2R theorem 2R 2R
2R
Vx +V/2 Vx
2R R R R 2R R

GND

Vx = V / 8
2R
+V/4 Vx
2R

Switching Circuits & Logic Design 8


• Case 4: Input is 0001.
+V GND GND GND GND GND GND

2R 2R 2R 2R 2R 2R 2R
Vx +V/2 Vx
2R R R R 2R R R

GND GND GND


Vx = V / 16
2R 2R 2R
+V/4 Vx +V/8 Vx
2R R 2R

Switching Circuits & Logic Design 9


• When all the four inputs D = D3D2D1D0 are applied (where Di = GND or +V
volts), we can apply the principle of superposition to compute the final output
voltage VA.
D0 D1 D2 D3

2R 2R 2R 2R
VA
+ VOUT
2R R R R -

Switching Circuits & Logic Design 10


VA = [D3.(V/2) + D2.(V/4) + D1.(V/8) + D0.(V/16)]
= [8D3 + 4D2 + 2D1 + D0].(V/16)
= D.(V/16)

Thus, VA α D.

For an N-bit DAC, the contribution of the k-th input Dk on the output voltage will be V / 2N-k

Switching Circuits & Logic Design 11


END OF LECTURE 48

Switching Circuits & Logic Design 12


Lecture 49: Analog-to-Digital Converter (Part 1)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Introduction
• An analog-to-digital converter (ADC) takes an analog input VA as input, and
generates a digital word D as output, where D α VA.
• Various types of ADC are possible:
a) Flash-type ADC
b) Counter-type ADC
c) Tracking-type ADC
d) Successive approximation ADC
e) Dual-slope ADC

Switching Circuits & Logic Design 2


Overall Schematic

Sample and VA Analog to Digital


Input analog D
signal Hold Circuit Converter

• If the input signal changes during the conversion, the final


value D may be erroneous.
• We use a sample-and-hold circuit to sample the input
voltage, and hold it to a constant value while the conversion
is in progress.

Switching Circuits & Logic Design 3


Sample-and-Hold Circuit

• The input voltage AI is sampled by closing the switch; the


capacitor charges to the voltage.
• During conversion, the switch is opened again, so that AO
remains reasonably constant.

Switching Circuits & Logic Design 4


How Fast We Must Sample?
• A very important decision.
– Guided by Nyquist Theorem.
• Nyquist Theorem:
– A band-limited analog signal that has been sampled can be perfectly reconstructed
from an infinite sequence of samples if the sampling rate fs exceeds 2fmax samples
per second, where fmax is the highest frequency in the original signal.
• If the analog signal does contain frequency components larger than fs/2, then there will
be an aliasing error.
• Aliasing is when the digital signal appears to have a different frequency than the original
analog signal.

Switching Circuits & Logic Design 5


• Valvano Postulate:
– If fmax is the largest frequency component of the analog signal, then you must
sample more than ten times fmax in order for the reconstructed digital samples to
look like the original signal when plotted on a voltage versus time graph.
• Some sampling examples are shown next.

Switching Circuits & Logic Design 6


• 200Hz signal sampled at 2000Hz
4000 Points are digital data, solid curve is the truth. What is the frequency?
Signal
3000

2000

1000

0
0.000 0.001 0.002 0.003 0.004 0.005 0.006 0.007 0.008
Time (sec)

Switching Circuits & Logic Design 7


• 1000Hz signal sampled at 2000Hz
4000 Points are digital data, solid curve is the truth. What is the frequency?
Signal
3000

2000

1000

0
0.000 0.001 0.002 0.003 0.004 0.005 0.006 0.007 0.008
Time (sec)

Switching Circuits & Logic Design 8


• 2200Hz signal sampled at 2000Hz (Aliasing Results)
4000 Points are digital data, solid curve is the truth. What is the frequency?
Signal
3000

2000

1000

0
0.000 0.001 0.002 0.003 0.004 0.005 0.006 0.007 0.008
Time (sec)

Switching Circuits & Logic Design 9


• 100Hz signal sampled at 1600Hz

Sampled Data Sampled Dat a 2.5 FFT Magnitude


3
T rue Dat a
2.0
2

Voltage (V)
1.5
Voltage (V)

0 1.0
0 2 4 6 8 10
-1 0.5

-2 0.0

-3 0.0 0.2 0.4 0.6 0.8 1.0


Time (ms)
Frequency (kHz)

Switching Circuits & Logic Design 10


• A signal with DC, 100Hz and 400Hz sampled at 1600Hz

Sampled Data Sampled Dat a 2.5 FFT Magnitude


3
T rue Dat a
2 2.0

Voltage (V)
1.5
Voltage (V)

0 1.0
0 2 4 6 8 10
-1 0.5

-2 0.0
-3 0.0 0.2 0.4 0.6 0.8 1.0
Time (ms)
Frequency (kHz)

Switching Circuits & Logic Design 11


• 1500Hz signal sampled at 1600Hz (Aliasing)

Sampled Data Sampled Dat a 2.5 FFT Magnitude


3
T rue Dat a
2 2.0

Voltage (V)
1.5
Voltage (V)

0 1.0
0 2 4 6 8 10
-1 0.5

-2 0.0
-3 0.0 0.2 0.4 0.6 0.8 1.0
Time (ms)
Frequency (kHz)

Switching Circuits & Logic Design 12


Sampling an waveform, and
reconstruction of the waveform
from the sampled values.

Switching Circuits & Logic Design 13


12

10

ADC count
6

0
0 2 4 6 8 10 12
-2
Vin

ADC Transfer Characteristic

Switching Circuits & Logic Design 14


END OF LECTURE 49

Switching Circuits & Logic Design 15


Lecture 50: Analog-to-Digital Converter (Part 2)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Resolution
• The least significant bit of an analog-to-digital converter (ADC) gives the
resolution.
• Related to full scale if the ADC is linear.
– LSB = A/2n, for an n-bit ADC.
– For a linear 8-bit ADC with a 1V full scale input,
Resolution = 1/28 = 3.9 mV (0.39%)

Switching Circuits & Logic Design


CERN ELEC 2002 ADC 2
Dynamic range
• Ratio between the minimum and the maximum amplitude to be measured.
• For a linear ADC the dynamic range is related to the number of bits (i.e. the
resolution).
– An 8-bit ADC has a dynamic range of 256.
• In case of large dynamic range some non-linearity has to be introduced.
• Commonly used terms:
– n-bit resolution
– n-bit dynamic range
– Example: 8-bit resolution for a 12-bit dynamic range means that a signal in the
range 1-4000 is measured with a resolution of 0.39%.

Switching Circuits & Logic Design


CERN ELEC 2002 ADC 3
Conversion Time and Bandwidth
• How often can a conversion be done?
– A few ns to a few ms depending on the technology.
• Input bandwidth
– Maximum input signal bandwidth
• Sample and hold input circuitry
• Conversion frequency

Switching Circuits & Logic Design


CERN ELEC 2002 ADC 4
ADC Transfer Characteristics
12

10 • This curve is for ideal ADC.


8
• Possible errors:
ADC count

4
– Offset
2 – Integral non-linearity
0 – Differential non-linearity
0 2 4 6 8 10 12
-2
Vin

Switching Circuits & Logic Design


CERN ELEC 2002 ADC 5
Integral linearity
12
120
10
100
8
ADC count

Vout 80
6 Ideal
Linear (Vout) 60
4
40
2

0 Non Linearity 20
0 5 10 15
0
Vin 0 20 40 60 80 100 120

• Non linearity: maximum difference between the best linear fit and the
ideal curve

Switching Circuits & Logic Design


CERN ELEC 2002 ADC 6
Differential Non-linearity
Differential non-linearity

Vmax 101.5

1 LSB = 101
2n

Frequency
100.5
Ideal Frequency
n − bit ADC
100
Measured frequency
99.5
99
98.5
0 20 40 60 80
ADC count

• Least Significant Bit (LSB) value should be constant but it is not.


• The difference with the ideal value should not exceed 0.5 LSB.
• How to check?
– random input covering the full range.
– frequency histogram should be flat.

Switching Circuits & Logic Design


CERN ELEC 2002 ADC 7
(a) Flash-type ADC
• This type of ADC provides the fastest conversion.
• Requires large amount of hardware.
– For an n-bit converter, we require 2n-1 comparators, 2n resistors, and one 2n-input
priority encoder.
• We illustrate the design for a 3-bit ADC.

Switching Circuits & Logic Design 8


R
A
A B C D E F G D2 D1 D0
R B 0 0 0 0 0 0 0 0 0 0
R C 0 0 0 0 0 0 1 0 0 1
R 0 0 0 0 0 1 X 0 1 0
D
R 0 0 0 0 1 X X 0 1 1
E 0 0 0 1 X X X 1 0 0
R
F 0 0 1 X X X X 1 0 1
R
G 0 1 X X X X X 1 1 0
R
1 X X X X X X 1 1 1

Switching Circuits & Logic Design 9


(b) Counter-Type ADC
Vin Vin

Switching Circuits & Logic Design 10


• We use a D/A converter, a counter and a comparator.
– Before a conversion starts, the counter is reset to zero.
– The counter output is fed to the input of the DAC.
– The DAC output D is compared with the input analog voltage Vin.
– If Vin > D, then the counter is incremented by 1.
– If Vin < D, the conversion is complete, and the counter output D gives the required
digital output.
• The worst-case conversion time is equal to 2n.

Switching Circuits & Logic Design 11


(c) Tracking-Type ADC
Vin
Up-down
counter

Vin

Switching Circuits & Logic Design 12


• Here we use a binary up-down counter.
– If the output of the comparator is 1 (Vin > D), the counter is incremented by 1.
– If the output of the comparator is 0 (Vin < D), the counter is decremented by 1.
– The counter output continuously tracks the input analog voltage.
• Suitable for continuous conversion of slowly-varying waveforms.
– If Vin changes too fast, the counter may not be able to track the changes.
– Here also, the worst-case conversion time is 2n.

Switching Circuits & Logic Design 13


END OF LECTURE 50

Switching Circuits & Logic Design 14


Lecture 51: Analog-to-Digital Converter (Part 3)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
(d) Successive Approximation Type ADC
• The principle of operation is analogous to binary search.
– Suppose we are searching for a number (here Vin) in a sorted list.
– We look into the middle of the list – effectively the size of the list reduces by half.
– For 2n steps, the number of steps required is only n.
• What modifications are required?
– We use a successive approximation register (SAR) instead of a counter.
– The SAR emulates binary search.
– For example, in 4 bits, it starts with 1000 (i.e. 8).
• If the input is smaller, the next value is set as 0100 (i.e. 4).
• If the input is larger, the next value is set at 1100 (i.e. 12).

Switching Circuits & Logic Design 2


• An example for a 4-bit ADC,
where the expected digital
output is 1001.
• Only 4 comparison steps
are required, once per bit
position.

Switching Circuits & Logic Design 3


SOC EOC

Vin • SOC: Start of Conversion


SAR • EOC: End of Conversion

D
DAC

Switching Circuits & Logic Design 4


Switching Circuits & Logic Design 5
(e) Dual-Slope Type ADC

Components required:
a) Opamp based integrator
b) Electronically controlled switches
c) Binary counter
d) Clock
e) Control logic
f) Voltage comparator

Switching Circuits & Logic Design 6


• Principle of operation:
– Integrates an unknown input voltage (VIN) for a fixed amount of time (TINT), then
de-integrates (TDE-INT) using a known reference voltage (VREF) for a variable amount
of time.
– Conversion result is insensitive to errors in component values. Errors introduced
during the integration cycle gets cancelled out during the de-integration phase.

Switching Circuits & Logic Design 7


• At t < 0, S1 is set to GND, S2 is closed, and counter is
cleared to 0.
• At t = 0, conversion begins and S2 is open, S1 is set to Vin.
– S1 is held for a constant time interval TINT.
– Counter begins to count; resets to 0 after TINT.
– Output of integrator at TINT is VINTINT/RC, i.e. proportional
to VIN.
• At t = TINT, S1 is set to –Vref.
– The integrator voltage drops linearly with a slope of
–Vref /RC.
– The comparator checks when the integrator output
voltage crosses zero.
– When it crosses zero, the counter value is the required D.

Switching Circuits & Logic Design 8


Switching Circuits & Logic Design 9
END OF LECTURE 51

Switching Circuits & Logic Design 10


Lecture 52: Asynchronous Sequential Circuits (Part 1)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Introduction
• Asynchronous circuits do not rely on clock; rather they exploit the delays of the
gates and other circuit elements for their operation.
• Within larger synchronous systems, it is often desirable to allow certain
subsystems to operate asynchronously to reduce delay and power
consumption.
• Structure of an asynchronous circuit:
– Delay elements in place of flip-flops.
– The combination of signals that appear at the primary input and delay outputs
define the total state.

Switching Circuits & Logic Design 2


X1 Z1
X2 Z2 • Input state:
Combinational  combination of input signals X1, X2,
Xl Zm …, Xl.
Circuit
• Secondary or internal state:
 combination of signals at the
Next outputs of the delay elements y1,
Current State
State y2, …, yk.
delay • Secondary or internal variables:
y1 Y1
 y1, y2, …, yk
y2 delay Y2
• Excitation variables:
 Y1, Y2, …, Yk
yk delay Yk

Switching Circuits & Logic Design 3


Definition
• Stable state:
– For a given input state, the circuit is said to be in a stable state if and only if yi = Yi
for i = 1, 2, …, k.
• In response to a change in the input state, the combinational logic produces a
new set of values for the excitation variables, entering an unstable state.
• When the secondary variables assume their new values (when y’s become
equal to the corresponding Y’s), the circuit enters its next stable state.
• Thus, a transition from one stable state to another occurs only in response to a
change in the input state.

Switching Circuits & Logic Design 4


Modes of Operation
• Fundamental mode of operation:
– When a change in input values has occurred, no other change in any input value
occurs until the circuit enters a stable state.
• Two types:
– Single-input change (SIC) fundamental mode: a single input value is allowed to
change at a time.
– Multiple-input change (MIC) fundamental mode: multiple input values can change
at a time.

Switching Circuits & Logic Design 5


Hazards
• Hazards (glitches) cause some unwanted transition(s) in the output(s) before
settling down to stable value(s).
• Two types of hazards:
a) Logic hazard: caused by non-instantaneous changes in circuit signals.
b) Function hazard: inherent in the functional specification.
• Can result in erroneous behaviour:
– The glitches when fed to some other circuit may result in incorrect behaviour.

Switching Circuits & Logic Design 6


Design of SIC Hazard-Free Circuits
• Example: T(x,y,z) = Σ (2,3,5,7)
– Static-1 logic hazard (SIC).
x
xy x G1 y 1
z 00 01 11 10
y 1
x 1 T
0 1 z 1
T
1 1 1 1 G2 y 1 1
x z 1
z 1
(a) Map for T = x y + xz.
(b) Gate network. (c) SIC hazard-free network

• Adjacent combinations: differ in the value of a single variable.


– For example, x’yz and xyz.

Switching Circuits & Logic Design 7


• SIC Static Logic Hazard:
– Transition between a pair of adjacent input combinations, which correspond to
identical output values, that may generate a momentary spurious output value.
– Occurs when no cube in the K-map contains both combinations.
• Solution: cover both combinations with a cube.

Switching Circuits & Logic Design 8


Transition and Required Cubes
• Transition cube [m1,m2] is a set of all minterms that can be reached from
minterm m1 and ending at minterm m2.
– Example: Transition cube [010,100] contains minterms: 000, 010, 100, 110
• Required cube is a transition cube that must be included in some product of
the sum-of-products realization in order to get rid of the static-1 logic hazard.
– Example: Required cube is [011,111]. z
xy
00 01 11 10

0 1

1 1 1 1

Switching Circuits & Logic Design 9


Static-0 / Dynamic Hazard
• Since in the sum-of-products realization of a function, no cube for any product
term can contain either of the two input combinations involved in a 0 → 0
output transition, a static-0 logic hazard can only occur if a product term has
both xi and xi’ as input literals.
– Since there is no need to include such products, such hazards can be avoided.
• During a 0 → 1 output transition, if the 0 may change to 1 and then 0 and
finally stabilize at 1, then the sum-of-products realization is said to have a
dynamic 0 → 1 logic hazard.
– A dynamic 1 → 0 hazard can be similarly defined.
– Dynamic hazards are not possible under the SIC scenario.

Switching Circuits & Logic Design 10


END OF LECTURE 52

Switching Circuits & Logic Design 11


Lecture 53: Asynchronous Sequential Circuits (Part 2)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Design of MIC Hazard-Free Circuits
• In the MIC scenario, several inputs can change values monotonically, i.e. at
most once.
– If in this transition, the function changes values more than once, then the
transition is said to have a function hazard.
– Example: Function hazard: dotted arrow; static-1 logic hazard: solid arrow.
wx x
yz 00 01 11 10 y 1

00 1 w 1
Static-1 logic hazard,
x but no function hazard.
01 1 1 f
y 1

11 1 1 1
z

w 1
10 1 1 1 1 z

Switching Circuits & Logic Design 2


Avoiding Static-1 Logic Hazard
• Example (contd.): cover the solid arrow with a cube to get rid of the static-1 logic
hazard.
x
wx 1
yz 00 01 11 10 y

w 1
00 1
x

y 1 1
01 1 1
z

11 1 1 1 w 1
z
10 1 1 1 1 w 1 1
y 1

• Avoiding a static-0 logic hazard is simple, just as in the SIC case.


– Avoid any product term with both xi and xi’.

Switching Circuits & Logic Design 3


MIC Dynamic Hazards
x 0
0
wx y 1
yz 00 01 11 10
w
00 1 x 1

y 1
01 1 1 f
z
Example: solid arrow G1

(1110  0111)
11 1 1 1 w
z
10 1 1 1 1 w
y 1

• Necessary condition for the dynamic transition to be hazard-free:


– Make sure each of its 11 sub-transitions is also hazard-free; ensured by including these sub-
transitions in some product of the sum-of-products realization.
– Sub-transitions: [1110,1111], [1110,0110] – called required cubes of the dynamic transition.
• Necessary condition met in this example for these required cubes.

Switching Circuits & Logic Design 4


Avoiding Dynamic Hazards
• Ensure that no AND gate turns on during the MIC transition.
– G1 temporarily turns on because product term wz intersects the dynamic MIC
transition 1110  0111; called illegal intersection.
– The corresponding dynamic transition is called a privileged cube.
– During this transition: inputs could be momentarily at 1111, which is a minterm of
wz.
– Disallow illegal intersections of privileged cubes: reduce the product term wz to
wy’z.

Switching Circuits & Logic Design 5


0 wx 0
wx x 0 x 0
yz 00 01 11 10 y 1 yz 00 01 11 10 y 1

00 1 w 00 1 w
x 1 x 1
01 1 1 y 1 01 1 1 1
f y
z f
z
11 1 1 1 G1 11 1 1 1
w w
y 0 0
z
10 1 1 1 1 10 1 1 1 1 z
w
w
y 1
y 1

Switching Circuits & Logic Design 6


Avoiding Hazards for a MIC Transition
• To summarize:
– 1  1 MIC transition: must be completely covered by a product term.
– 0  0 MIC transition: does not lead to a hazard.
– 1  0 (0  1) MIC transition: ensure that every product term that intersects the
MIC transition also contains its starting (end) point.

Switching Circuits & Logic Design 7


• To obtain a hazard-free sum-of-products implementation H of function f, we
need to ensure:
– Each required cube is contained in some implicant of H.
– No implicant of H illegally intersects any specified dynamic transition.
• Such an implicant is called a dynamic-hazard-free implicant (dhf-implicant).
• A dhf-prime implicant is a dhf-implicant not contained in any other dhf-implicant.
– This problem requires that we only make use of dhf-prime implicants while
covering every required cube in sum-of-products minimization.
• Similar to Quine-McCluskey minimization.

Switching Circuits & Logic Design 8


wx wx wx
yz 00 01 11 10 yz 00 01 11 10 yz 00 01 11 10

00 0 0 1 1 00 0 0 1 1 00 0 0 1 1

01 0 1 1 1 01 0 1 1 1 01 0 1 1 1

11 1 1 1 1 11 1 1 1 1 11 1 1 1 1

0 1 1 0 1 1 0 1 1
10 1 10 1 10 1
Required Cubes
(a) Required cubes. (b) Privileged c ubes. (c) Prime implicants with no
dhf-
illegal intersecti ons.wy’ wy xy‘z w‘yz w‘x’y
wx wx
yz 00 01 11 10 yz 00 01 11 10 PI
00 0 0 1 1 00 0 0 1 1
w X X
01 0 1 1 1 01 0 1 1 1
yz X
An 11 1 1 1 1 11 1 1 1 1
x‘y X
Example 10 1 0 1 1 10 1 0 1 1
xy‘z X
(d) Prime implicant xz has an (e) Prime implicant xz reduced to
illegal intersection. dhf-prime implicant xy z.
Hazard-free sum-of-products:
w + yz + x’y + xy’z

Switching Circuits & Logic Design 9


Hazard-non-increasing Logic Transformations
• Used to derive hazard-free multi-level realization from hazard-free two-level
realization.
• The following constitute some hazard-nonincreasing transformations:
– Associative law and its dual: (x + y) + z  x + (y + z); (x y) z  x (y z)
– De Morgan’s theorem and its dual: (x + y)’  x’ y’; (x y)’  x’ + y’
– Distributive law: x y + x z => x (y + z)
– Absorption law: x + x y => x
– x + x’ y => x + y
– Insertion of inverters at primary inputs and circuit output.

Switching Circuits & Logic Design 10


• Example: AND-OR realization free of dynamic hazard for 1110  0111.
– So is the multi-level realization:
x’ y + w x + y z’ + w y’ z + w y = (x’ + z’ + w) y + w x + w y’ z
wx
yz 00 01 11 10
x 0 0
y 1 x
z
00 1 w
w
x 1 1
01 1 1 y
y 1
z f w
11 1 1 1 y 0 f
w 0 z
y 0
10 1 1 1 1
z w
w x
y 1

Switching Circuits & Logic Design 11


END OF LECTURE 53

Switching Circuits & Logic Design 12


Lecture 54: Algorithmic State Machine (ASM) Chart

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Introduction
• Algorithmic State Machine (ASM) Charts are useful for specifying detailed logic
for sequential circuits, similar to flowcharts.
• It describes the sequence of events as well as timing relationship between the
states of a FSM.
• The ASM chart is composed of three basic elements:
a) State Box
b) Decision Box
c) Conditional Box

Switching Circuits & Logic Design 2


(a) State Box
– It is a rectangular box representing a state of the machine, and contains a state
name or an optional output list.
– The state box may contain register operation R ← 0, which indicates that a register
R is to be initialized to 0.
– After a state assignment has been made, a state code may be placed at the upper
right corner of the box.

Switching Circuits & Logic Design 3


(b) Decision Box
– It is a diamond-shaped box that represents a decision;
in the simple case, it represents a binary decision with
two outgoing arrows (yes and no).

(c) Conditional Box


– It is an oval box that represents a conditional output
list.
– The input path to the conditional box must come from
a decision box.

Switching Circuits & Logic Design 4


ASM Block
• An ASM Block is a structure consisting of
one state box, and all the decision and
conditional boxes connected to its exit
path.
– An ASM block has one entrance path and
one or more exit paths.

Switching Circuits & Logic Design 5


• When the system enters state S1, the outputs Z1 and
Z2 become 1.
• If input X1 is 0, the outputs Z3 and Z4 also become 1.
• If both X1 and X3 are 0, the output Z5 becomes 1, and
the system exits to the next state.

Switching Circuits & Logic Design 6


Rules to be Followed
• Several ASM charts can be drawn for the same system. The following rules
must be followed:
– For every valid combination of input variables, there must be exactly one exit path.
– No internal feedback within an ASM block is allowed.
– Parallel paths that lead to the same exit path is allowed.
– More than one of the parallel paths can be active at the same time.
– An ASM Chart can have multiple exit paths.

Switching Circuits & Logic Design 7


Creating ASM Charts
• It is straightforward to convert a state diagram for a
FSM to an equivalent ASM chart.
• We consider the example of a sequence detector that
detects the sequence 101, with an output Z.
– Since the FSM has three states, the ASM chart will have
three blocks.
– The output Z will appear in conditional output boxes.
– Since there is only one input X, each block must have two
exit paths.
– The state assignments (S0 = 00, S1 = 01, S2 = 11) are also
shown.

Switching Circuits & Logic Design 8


Switching Circuits & Logic Design 9
END OF LECTURE 54

Switching Circuits & Logic Design 10


Lecture 55: Testing of Digital Circuits

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Why do we need Testing?

• There are possibilities of various kinds of errors during manufacturing:


– Errors during the design process.
– Bugs during synthesis (viz. in the CAD tools used).
– Faults during fabrication / packaging.
• Necessary to test each and every chip before they can be used.
• Billions of transistors is present-day VLSI chips.
– Chances of faults creeping in is also quite significant.

Switching Circuits & Logic Design 2


Basic Objective

• We use testing to determine the presence of faults in a given circuit / chip.


– Fallacy: Testing is used to guarantee that a circuit / chip is fault-free.
– No amount of testing can give this guarantee.
– Using testing, we can increase out confidence in the correct working of the circuit
/ chip.
• We usually use verification along with testing.
– Distinctly different objectives.

Switching Circuits & Logic Design 3


Verification Testing
• Guarantees the correctness of design. • Tries to guarantee correctness of the
• Performed once before the actual manufactured circuits / chips.
manufacturing of the circuits / chips. • Performed on every manufactured
• Primarily responsible for the quality of device.
the design. • Primary responsible for the quality of the
• Uses formal methods, simulation, etc. devices that go to the market.
• Two steps involved: (a) Test Generation,
(b) Test Application.

Switching Circuits & Logic Design 4


When to do Testing?

• Can be carried out at various levels:


– At the chip-level, when chips are manufactured.
– At the board-level, when chips are integrated on the boards.
– At the system-level, when several boards are assembled together.
• Rule of thumb:
– Detecting a fault early reduces the cost of testing.
– Empirical Rule: It is 10 times more expensive to test a device as we move to
the next higher level (chip  board  system).

Switching Circuits & Logic Design 5


The Problem in Fault Enumeration

• The number of possible physical defects can be too huge.


– Not possible to enumerate.
– So how do we judge the quality of a test?
• Solution: abstract physical defects and define some logical fault models.
– Easy to analyze and quantify.
– Possible to judge the quality of a set of test vectors.
– How many faults are getting tested?

Switching Circuits & Logic Design 6


Fault Coverage

• Fault Coverage: Percentage of the total number of logical faults that can
be tested using a given test set T.

Number of detected faults


FC =
Total number of faults
• Often expressed as a percentage.

Switching Circuits & Logic Design 7


Why Testing is Considered Difficult?

• Consider a combinational circuit with N inputs. Suppose we use a naïve


way of testing where we apply all 2N inputs and verify the truth table.

N Number of Test Vectors


Not feasible as N
25 33.55 x 106
increases.
50 1.13 x 1015
100 1.26 x 1030

Switching Circuits & Logic Design 8


• Now consider a synchronous sequential circuit with N inputs and S state
variables.
– For any given input, the output will depend on the internal state.
– 2N possible inputs and 2S possible states  complexity of O(2N+S).

• Thus, verifying the state table of the sequential circuit for testing is infeasible.
– Need some mechanism to enhance the controllability and observability of the
state variables.
– Design for Testability is a standard technique that is used in practice.

Switching Circuits & Logic Design 9


Various Processes during Testing

• Fault Modeling
– Abstract the physical defects and define a suitable logical fault model.
– Limits / simplifies the scope of test generation.
• Test Generation
– Given a circuit and a set of faults F, determine a set of test vectors T that
detects all faults in F.
• Fault Simulation
– Given a circuit, a set of faults F, and a set of test vectors T, determine the
faults in F that are tested by the vectors in T.

Switching Circuits & Logic Design 10


• Design for Testability (DFT)
– Formulate a set of design rules that, if followed, results in a circuit that will be
easily testable.
– Typically introduces both area overhead and performance degradation.

• Built-in Self-Test (BIST)


– Test generation and response evaluation of the circuits are performed on-chip.
– The chip can test itself.
– Additional area overhead.

Switching Circuits & Logic Design 11


Basic Testing Principle

Circuit
Input patterns Under Output response
Test

Golden response Comparator Good / Bad

Switching Circuits & Logic Design 12


END OF LECTURE 55

Switching Circuits & Logic Design 13


Lecture 56: Fault Modeling

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Why Fault Models?

• The number of physical defects in a chip can be too many.


– Difficult to count and analyze all possible faults.
• We abstract physical defects and define some logical fault models.
– Drastically reduces the number of faults to be considered.
– Makes test generation and fault simulation possible.
– We can evaluate fault coverage and compare test sets.
• We discuss some of the fault models at the functional and structural
levels.

Switching Circuits & Logic Design 2


Functional Level Fault Model
• Circuit is specified at the register transfer level (RTL).
– Netlist of functional blocks like registers, adders, multiplexers, etc.
• Fault models are block-specific and not general.
– Very efficient for certain types of blocks and the test set can be generated directly.
• Example: 4-to-1 multiplexer.
– Four data inputs A0, A1, A2, A3; two select inputs S0, S1; and one output F.
– Test vectors can be generated directly from functional behavior of MUX.

Switching Circuits & Logic Design 3


A0
A1 F A0 A1 A2 A3 S0 S1 F
A2 MUX
A3
0 1 1 1 0 0 0
1 0 0 0 0 0 1
S0 S1
1 0 1 1 1 0 0
• For a 2n-to-1 MUX, 2n+1 test patterns are 0 1 0 0 1 0 1
required. 1 1 0 1 0 1 0
• All functional faults can be detected. 0 0 1 0 0 1 1
• An input line is incorrectly selected.
1 1 1 0 1 1 0
• Some line is fixed at 0 or 1.
0 0 0 1 1 1 1

Switching Circuits & Logic Design 4


Structural Level Fault Model
• Circuit is specified as a netlist, typically at the level of gates and flip-flops.
• The assumption:
– The blocks (e.g. gates) are fault-free.
– The interconnections between blocks can be faulty.
• We discuss one popular structural level fault model, viz. stuck-at fault
model.

Switching Circuits & Logic Design 5


Stuck-at Fault Model

• Here we assume that some of the circuit lines are permanently fixed at
logic-0 or logic-1 due to some failures.
• Very popular fault model, as it can model many realistic physical failures.
– Faults on a line A are denoted as: A s-a-0 or A/0, and A s-a-1 or A/1.
– Fanout stems and fanout branches are considered as separate lines.

F1
A F
B
F2

Switching Circuits & Logic Design 6


• Single stuck-at fault
– Only one line of the circuit has a stuck-at fault at any given time.
– Most widely used fault model in the industry.
– For a circuit with k lines, total number of single stuck-at faults is 2k.
A1 D
A A2 C C1
B F
B1 C2

B2 E

k =12  Number of single stuck-at faults = 24

Switching Circuits & Logic Design 7


• Multiple stuck-at fault
– Any number of circuit lines can have stuck-at faults at any given time.
– For a circuit with k lines, total number of multiple stuck-at faults is 3k-1.

A1 D
A A2 C C1
B F
B1 C2

B2 E

k =12  Number of multiple stuck-at faults = 312-1 = 5,31,440

Switching Circuits & Logic Design 8


Single Stuck-at Fault Testing Examples
T = {01, 10, 11}
A 01 : detects A/1 and F/1
B F
10 : detects B/1 and F/1
11 : detects A/0, B/0 and F/0

A T = {0111, 1011, 1101, 1110, 1111}


B F 0111 : detects A/1 and F/1
C 1011 : detects B/1 and F/1
D 1101 : detects C/1 and F/1
1110 : detects D/1 and F/1
1111 : detects A/0, B/0, C/0, D/0 and F/0

Switching Circuits & Logic Design 9


• 3-input XOR gate T = {000, 111}
– 000 detects all input stuck-at-1 faults and also output stuck-at-1 fault.
– 111 detects all input stuck-at-0 faults and also output stuck-at-0 fault
• 4-input XOR gate T = {0000, 1111, 0111}
– 0000 detects all input stuck-at-1 faults and also output stuck-at-1 fault.
– 1111 detects all input stuck-at-0 faults and also output stuck-at-1 fault
– 0111 detects additionally the output stuck-at-0 fault.
• For m-input XOR gate, number of test vectors required will be either
2 (if m is odd) or 3 (if m is even).

Switching Circuits & Logic Design 10


How to Reduce Number of Faults?

• Some properties of faults that occur in gates can help us in reducing the
effective number of faults to be considered.
• Some techniques used for fault collapsing:
a) Fault equivalence
b) Fault dominance

Switching Circuits & Logic Design 11


(a) Fault Equivalence
• Two faults in a circuit are said to be equivalent if the corresponding faulty
functions are identical.
– Input stuck-at-0 and output stuck-at-0 in AND gate.
– Input stuck-at-0 and output stuck-at-1 in NAND gate.
– Input stuck-at-1 and output stuck-at-1 in OR gate.
– Input stuck-at-1 and output stuck-at-0 in NOR gate.
– Input stuck-at-0 (1) and output stuck-at-1 (0) in NOT gate.
• For every such equivalence class, we retain only one fault and remove the rest.
– Called equivalence fault collapsing.

Switching Circuits & Logic Design 12


sa0 sa1 sa0 sa1
sa0 sa1
sa0 sa1
sa0 sa1 sa0 sa1
sa0 sa1 sa0 sa1
sa0 sa1
sa0 sa1
sa0 sa1
sa0 sa1
sa0 sa1
sa0 sa1
sa0 sa1
sa0 sa1 Total number
of faults = 32

Switching Circuits & Logic Design 13


sa1 sa0
sa1
sa1
sa0 sa1 sa0
sa1 sa0 sa1
sa0 sa1
sa1
sa0
sa0 sa1
sa1
sa1
sa0 Number of
sa1
faults after
collapsing = 20

Switching Circuits & Logic Design 14


(b) Fault Dominance
• If all tests for some fault fi also detect another fault fj, then fj is said to
dominate fi, denoted as fj  fi.
– Output stuck-at-1 dominates input stuck-at-1 in AND gate.
• For every such dominance relation fj  fi, we retain fi and remove fj.
– Called dominance fault collapsing.
• If two faults dominate each other, they are equivalent.

Switching Circuits & Logic Design 15


An example: A F
B
• 3-input AND gate. C
• fi  s-a-1 fault in one input of the gate (say, A)
• fj  s-a-1 in the gate output F

Tests for fi : {011}


Tests for fj : {000, 001, 010, 011, 100, 101, 110}
• Remove fj and keep only fi .
Thus, fj dominates fi . • Detecting fault fi will also
detect fault fj.

Switching Circuits & Logic Design 16


END OF LECTURE 56

Switching Circuits & Logic Design 17


Lecture 57: Test Pattern Generation

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
The Basic Problem

• Inputs:
– A circuit netlist.
– A fault list F.
• Output(s):
– A set of test vectors T to detect the faults in F.
– A list of undetected faults.

Switching Circuits & Logic Design 2


Motivation

• Drastically reduce the number of required test vectors as compared to


naïve approach (e.g. verify the truth table).
• Some examples for single stuck-at faults:
– 4-input AND gate
• Needs 5 vectors {0111,1011,1101,1110,1111} as compared to 24 = 16.
– 5-input EXOR gate
• Needs 2 vectors {00000,11111} as compared to 25 = 32.

Switching Circuits & Logic Design 3


A
B E Fault Test Vector
G
A/0, C/0, D/0, F/0, G/0 1011
C F A/1, B/1, E/1, G/1 0011
D B/0, C/0, D/0, E/0, F/0, G/0 0111
C/1, F/1, G/1 0101
D/1, F/1, G/1 0110

T = {0011, 0101, 0110, 0111, 1011}

Switching Circuits & Logic Design 4


Generating Test from Truth Table
Inputs (a b c) f fα
• How to generate test for the stuck-
000 0 0
at-0 fault α?
001 0 0
010 0 0
a α: stuck-at-0
b 011 0 0
f 100 0 0
101 1 1
c Condition: f ⊕ fα = 1 110 1 0
111 1 1

Switching Circuits & Logic Design 5


Method of Boolean Difference

• This is an algebraic method to generate all the possible test vectors to


detect a given fault.
– Simple in concept, but difficult to automate.
• The Boolean difference of a function f(x1,x2,…,xn) with respect to one of its
variables xi is defined as
df
dxi = f(x1,…,xi-1,0,xi+1,…,xn) ⊕ f(x1,…,xi-1,1,xi+1,…,xn)
= fi(0) ⊕ fi(1)

Switching Circuits & Logic Design 6


• The Boolean difference df/dxi specifies the condition under which any
change in line xi will propagate to the output.
• Necessary and sufficient conditions to detect a fault xi /c :
– A reverse logic value c’ must be applied to xi to excite the fault.
• Line xi will have different values in fault-free and faulty circuits.
– The change on line xi must be propagated to the output(s).
• Condition specified by the Boolean difference df/dxi .

Switching Circuits & Logic Design 7


• The set of test vectors that can detect the fault xi /0 is given by

xi df(X) = 1
dxi
• The set of test vectors that can detect the fault xi /1 is given by

xi’ df(X) = 1
dxi

Excite the fault, and propagate the fault

xi or xi’ df(X)/dxi

Switching Circuits & Logic Design 8


A
B
Generate tests for
F
C/0 and C/1
C
D 1X10
X110
F = (A + B)C’ + CD For C/0 :: C. dF/dC = 1 0011
ACD’ + BCD’ + A’B’CD = 1
dF/dC = (A + B) ⊕ D 1X00
= AD’ + BD’ + A’B’D X100
For C/1 :: C’. dF/dC = 1
AC’D’ + BC’D’ + A’B’C’D = 1 0001

Switching Circuits & Logic Design 9


Test Generation using Path Sensitization

• Similar in concept to Boolean difference, in the sense that we excite the


fault and then propagate the fault effects.
– Boolean difference works from function specification.
– Path sensitization directly works with circuit netlist.
• To propagate change in a gate input to the output, the other input(s) must
be set to the corresponding non-controlling value.

Switching Circuits & Logic Design 10


Basic Principle
1. At the site of the fault, assign a logic value that is complementary to the
polarity of the fault being tested.
2. Forward Drive Phase
– Select a path from the site of the fault to one of the circuit outputs.
– Sensitize the path by assigning non-controlling values to the inputs of the
gates along the path so as to propagate the effect of the fault.
3. Backward Trace Phase
– Determine the primary inputs that will produce the necessary signal values as
specified in Steps 1 and 2.
– Requires tracing the signals back towards the primary inputs.

Switching Circuits & Logic Design 11


Example: Generate a test for E/1

A
E
B H
C1 F Z

C C2 G
D

Switching Circuits & Logic Design 12


Example: Generate a test for E/1

A
E
B 0 H
C1 F Z

C C2 G
D
A reverse logic value is
applied at the site of the
fault.

Switching Circuits & Logic Design 13


Example: Generate a test for E/1

A
E
B 0 H
C1 F 1 Z
0
C C2 G
D Propagate the fault
effect to the output by
applying non-controlling
values to the side inputs
of gates along the path.

Switching Circuits & Logic Design 14


Example: Generate a test for E/1

A 0
E
B 0 H
0
C1 F 1 Z
0 0
C 0 C2 G
D X Back-trace towards the
primary inputs and
assign values to gate
Test Vector: {0 0 0 X} inputs as required.

Switching Circuits & Logic Design 15


Points to Note
• Path sensitization is not as simple as the example shows.
– There can be conflicts during back-tracing that requires a backtracking
algorithm.
– More than one path may need to be sensitized together.
• Practical test generators are quite complex and sophisticated.
– Good combinational ATPG tools exist.
– Sequential ATPG is much more time consuming.
• Test generation is slower than fault simulation.

Switching Circuits & Logic Design 16


END OF LECTURE 57

Switching Circuits & Logic Design 17


Lecture 58: Design for Testability

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
What is Design for Testability (DFT)?

• Design technique that makes test generation and test application easier
and cost-effective.
• Mainly addresses the difficulty of testing sequential circuits.
– Difficult to control and observe the internal flip-flops.
• DFT techniques help in making the internal flip-flops easily controllable
and observable.
– Basically converts the sequential circuit test generation problem to
combinational circuit test generation problem.

Switching Circuits & Logic Design 2


Model of a Sequential Circuit

Primary Inputs Primary Outputs


Combinational
Logic
With every clock,
Present the next state
Next
State becomes the
State present state.
Flip
flops
Clock

Switching Circuits & Logic Design 3


Scan Path Design

• Most widely used DFT technique.


• Scan path can be inserted in a non-scan sequential circuit netlist in an
automated way.
• What is actually done:
– All the flip-flops are replaced by scan flip-flops.
– Connect the scan flip-flops as configurable shift-register.
– Add one Test Control (TC) primary input.
– Add a SCANIN input and SCANOUT output for the shift register.

Switching Circuits & Logic Design 4


What is Scan Flip-Flop?
D Master latch Slave latch
TC
Q

MUX Q
SD
Logic overhead
CK

Master-Slave D flip-flop

TC = 1 :: Normal Mode (MUX selects D) FF requires 10 gates


TC = 0 :: Test Mode (MUX selects SD) SFF requires 10 + 4 = 14 gates

Switching Circuits & Logic Design 5


Scan-Inserted Sequential Circuit
PI PO

Combinational SFF SCANOUT


logic SFF

SFF

TC
SCANIN

Switching Circuits & Logic Design 6


How are Test Vectors Applied?
PI Present State PO Next State

Required I1 S1 O1 N1
inputs to be I2 S2 O2 N2
applied
I3 S3 O3 N3
… … … …

PI can be applied directly


PS has to be applied serially (after setting TC = 1)
NS has to be observed serially (after setting (TC = 1)

Switching Circuits & Logic Design 7


Test Vectors Converted to Scan Sequence

PI
I1 I2

SCANIN S1 S2 Don’t care


TC 0000000 1 0000000 1 0000000 or random
bits

PO
O1 O2

SCANOUT N1 N2

Switching Circuits & Logic Design


8
Scan Sequence Length

• Specifies the total number of clock cycles required to apply all the test
patterns and observe the responses.
– PS has to be shifted in serially in the scan shift register through SCANIN.
– NS has to be shifted out serially through SCANOUT.

• Scan Sequence Length = (ns + 1) nc +ns


where nc is the number of combinational test vectors
ns is the number of scan flip-flops

Switching Circuits & Logic Design 9


An Example of Generating Scan Sequence
3 inputs, 2 outputs, and 3 state variables

PI Present State PO Next State


010 100 01 101
011 010 11 001
101 100 10 111
001 101 01 010

Switching Circuits & Logic Design 10


Clock PI SCANIN TC PO SCANOUT
1 xxx 1 0 xx x
2 xxx 0 0 xx x
3 xxx 0 0 xx x
4 010 x 1 01 x
5 xxx 0 0 xx 1
6 xxx 1 0 xx 0
7 xxx 0 0 xx 1
8 011 x 1 11 x

Switching Circuits & Logic Design 11


Scan Testing Time

• The flip-flops in the scan register must be tested prior to the application of
the test vectors.
– Apply a shift sequence 0 0 1 1 0 0 1 1 … of length ns+4.
– Produces all possible transitions in the flip-flops.
• Thus, total scan test length is:
(ns + 1) nc + ns + (ns + 4)
• Example: ns = 2000, nc = 500  Test length = 106

Switching Circuits & Logic Design 12


Scan Overheads

• IO pins: One pin necessary.


• Area overhead:
Gate overhead = [4 ns / (ng + 10ns)] x 100%
where ng = number of gates in combinational logic
ns = number of flip-flop
– Example:
• ng = 100k gates, ns = 2k flip-flops, overhead = 6.7%.
– More accurate estimate must consider scan wiring and layout area.

Switching Circuits & Logic Design 13


Performance Overheads

• Multiplexer delay added in combinational path.


– FF replaced by SFF.
– Approximately two gate-delays.
• Flip-flop output loading due to one additional fanout.
– SFF output driving two inputs instead of one.
– Approximately 5-6% degradation in clock frequency.

Switching Circuits & Logic Design 14


END OF LECTURE 58

Switching Circuits & Logic Design 15


Lecture 59: Built-in Self-Test (Part 1)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Basic Concept

• We add extra hardware to the chip for test generation and response
evaluation.
– Done on chip.
– Additional hardware overhead.
• Only a few external pins to control BIST operation.
– Input pin: TEST CONTROL (TC)
– Output pin: GOOD/BAD

Switching Circuits & Logic Design 2


Test Generator
Test CHIP
Control

Circuit Under Test


(CUT)
Good /
Bad
Response Compactor

Switching Circuits & Logic Design 3


Why do we need BIST?
• Can be used for field test and diagnosis.
– Do not need an expensive Automated Test Equipment (ATE).
• An alternative is to have software tests for field test / diagnosis.
– Low hardware fault coverage.
– Poor diagnostic resolution.
– Time consuming.
• Advantages of doing this in hardware:
– Lower system test effort and better diagnosis.
– Improved system maintenance and repair.

Switching Circuits & Logic Design 4


BIST Architecture
Test
Control Test Controller ROM

Pattern M Circuit Response


Generator U =
under Compactor
X
test
PI
 Note: BIST cannot test wires and transistors: PO Good / Bad
 From PI pins to input MUX
 From POs to output pins

Switching Circuits & Logic Design 5


Random Pattern Testing

• We use pseudo-random patterns as input test vectors.


– Typically using Linear Feedback Shift Register (LFSR).
• Fault coverage can be determined using fault simulation.
– Test length is larger.
– Much faster test generation.
– Continue until fault coverage reaches 60-80%; then switch to ATPG.

Switching Circuits & Logic Design 6


100%

%
Fault
Coverage

Number of test vectors

Switching Circuits & Logic Design 7


Linear Feedback Shift Register (LFSR)

• A simple hardware circuit based on shift register.


– A feedback circuit that is linear (composed of XOR gates).
– Very good source of pseudo-random patterns.
• Used in many applications:
– For random number generation (testing, communication, etc.).
– Error checking (Cyclic Redundancy Check).
– Response compression.

Switching Circuits & Logic Design 8


Structure of a LFSR
+
Type-1 LFSR
D1 D2 D3 D4

Type-2 LFSR
D1 D2 D3 + D4

Switching Circuits & Logic Design 9


D4 D3 D2 D1
Pattern Generation Example
1 0 0 0
0 0 0 1
0 0 1 1
+ 0 1 1 1
1 1 1 1
1 1 1 0
D1 D2 D3 D4 1 1 0 1
1 0 1 0
0 1 0 1
f(x) = x4 + x1 + 1 1 0 1 1
0 1 1 0
1 1 0 0
1 0 0 1
Characteristic Polynomial 0 0 1 0
0 1 0 0
1 0 0 0

Switching Circuits & Logic Design 10


Some Definitions

• If the sequence generated by an n-stage LFSR has period 2n-1, then it is


called a maximum-length sequence or m-sequence.
• The characteristic polynomial associated with maximum-length sequence
is called a primitive polynomial.
• An irreducible polynomial is one that cannot be factored; i.e., it is not
divisible by any other polynomial other than 1 and itself.
– Primitive polynomial is an irreducible polynomial.

Switching Circuits & Logic Design 11


Some Example Primitive polynomials
3: 1 0 x3 + x + 1
4: 1 0 x4 + x + 1
5: 2 0 x5 + x2 + 1 A comprehensive list
6: 1 0 x6 + x + 1 is available.
7: 1 0 x7 + x + 1
8: 6 5 1 0 x8 + x6 + x5 + x + 1
16: 5 3 2 0 x16 + x5 + x3 + x2 + 1
32: 28 27 1 0 x32 + x28 + x27 + x + 1
64: 4 3 1 0 x64 + x4 + x3 + x + 1

Switching Circuits & Logic Design 12


Some Interesting Properties of m-sequence

1. The period of {an} is p = 2n-1, that is, ap+i = ai, for all i ≥ 0.
2. Starting from any nonzero state, the LFSR that generates {an} goes
through all 2n-1 states before repeating.
3. The number of 1’s differs from the number of 0’s by one.
4. If a window of width n is slid along an m-sequence, then each of the 2n-1
nonzero binary n-tuples is seen exactly once in a period.
5. In every period of an m-sequence, one-half the runs have length 1, one-
fourth have length 2, one-eighth have length 3, and so on.

Switching Circuits & Logic Design 13


Randomness Properties of m-sequence

• m-sequences generated by LFSR are also called pseudo-random sequences.


– The autocorrelation of any output bit is close to zero.
– The correlation of any two output bits is close to zero.
– However, the cross-correlation between two output bits is poor.
• In a typical test environment, we can generate as many patterns as required
to achieve desired fault coverage.
– Testing at maximum clock rate (AT-speed testing).

Switching Circuits & Logic Design 14


END OF LECTURE 59

Switching Circuits & Logic Design 15


Lecture 60: Built-in Self-Test (Part 2)

PROF. INDRANIL SENGUPTA


DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
LFSR
Pseudo-random
patterns

Circuit Under Test

Output Response

Switching Circuits & Logic Design 2


Test Response Compaction

• Huge volume of data in CUT response:


– Generate 5 million random patterns.
– CUT has 200 outputs.
– Leads to 5 million x 200 = 1 billion bits response.
• Uneconomical to store all these responses on-chip and compare during
BIST operation.
• Mandatory to compact the responses before comparison.

Switching Circuits & Logic Design 3


• An issue:
– Large volume of response is compacted into a signature before comparison.
– The golden signature is stored on-chip.
– Basically a many-to-one mapping.
• Many different responses may get mapped to the same signature.
• Some of the faults might go undetected.
• So ??

Switching Circuits & Logic Design 4


Some Relevant Definitions
• Aliasing
– The signature in the presence of a fault matches with the golden signature and
the fault goes undetected.
• Compaction
– Drastically reduces number of bits in original circuit response (109 to 32).
– Loss of information.
• Compression
– Reduces number of bits in circuit response (not as drastic as compaction).
– No information loss :: fully invertible.

Switching Circuits & Logic Design 5


LFSR Based Response Compaction

• Two approaches are possible:


a) Compact a single serial bit stream into a LFSR based compactor,
called Signature Analyzer.
b) Compact several serial bit streams into a special LFSR based
compactor called Multi-Input Signature Register (MISR).

Switching Circuits & Logic Design 6


(a) LFSR Based Signature Analyzer
• Use a LFSR based circuit as response compacter.
– Similar to cyclic redundancy code (CRC) generator.
– Divide a polynomial by another polynomial and take the remainder.
• Treat data bits from circuit POs as a decreasing order coefficient polynomial.
• The circuit divides the PO polynomial by its characteristic polynomial.
– Leaves remainder of division in LFSR.
– Must initialize LFSR to seed value (usually 0) before testing.
• After testing – compare signature in LFSR to golden signature.

Switching Circuits & Logic Design 7


Input Bit Characteristic Polynomial :: P(X) = X5 + X3 + X + 1
Stream
01010001
+ D0 + D1 D2 + D3 D4

X0 X1 X2 X3 X4

Initial Seed = 00000


Input Polynomial :: F(X) = X7 + X3 + X

Divide F(X) by P(X) and take the remainder  X3 + X2 + 1

Switching Circuits & Logic Design 8


Simulating the Process of Division
Inputs X0 X1 X2 X3 X4
Initial State 0 0 0 0 0
1 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
Input Polynomial :: 1 1 0 0 0 1
F(X) = X7 + X3 + X 0 1 0 0 1 0
1 1 1 0 0 1
0 1 0 1 1 0

Remainder Polynomial ::
F(X) = X3 + X2 + 1

Switching Circuits & Logic Design 9


Probability of Aliasing

• Let m: test length, n: LFSR length.


• An m-bit string is being compacted to an n-bit stream.
– Number of possible input combinations = 2m
– Number of possible signatures = 2n
– One of these input combinations is good, and one signature is golden.
• Assume that the input patterns are uniformly distributed among all signatures.
– 2m-n patterns map to a particular signature.

Switching Circuits & Logic Design 10


• We define the probability of aliasing as the ratio of the number of faulty bit
streams that map to the golden signature (called aliasing) to the total number
of faulty signatures.
– Number of faulty bit streams that map to golden signature = 2m-n – 1
– Number of faulty bit streams = 2m – 1

Palias = (2m-n – 1) / (2m – 1) ≅ 2-n

If n = 32, Palias = 2.33 x 10 -10

Switching Circuits & Logic Design 11


(b) Multi-Input Signature Register (MISR)

• Problem with LFSR-based response compacter:


– Too much hardware if there are multiple outputs.
– We need a compactor on each output.
• Solution: MISR – compacts all outputs into one LFSR
– Works because LFSR is linear – obeys superposition principle.
– Superimpose all responses in one LFSR .
– Final remainder is XOR sum of remainders of polynomial divisions of
each output by the characteristic polynomial.

Switching Circuits & Logic Design 12


A 5-bit MISR

+ D0 + D1 + D2 + D3 + D4

Output O0 Output O1 Output O2 Output O3 Output O4

Circuit Under Test

Switching Circuits & Logic Design 13


To Summarize
• Preferred BIST method.
– LFSR-based pattern generation and MISR-based compaction.
• BIST has a lot of overheads.
– Additional hardware and also performance degradation.
• Advantages of BIST:
– Reduction in test cost.
– Field testing and diagnosis.
– AT-speed testing.

Switching Circuits & Logic Design 14


END OF LECTURE 60

Switching Circuits & Logic Design 15

You might also like