1. DLD

Chapter 1
Number Systems
LEARNING OBJECTIVES
 Digital circuits  Numeric codes

 Number system with different base  Weighted and non-weighted codes
 Conversion of number systems  Error detection and correction code
 Complements  Sequential, reflective and cyclic codes
 Subtraction with complement  Self complementing code
DiGital CirCuits Example 5: (658)8 = 6 × 82 + 5 × 81 + 8 × 80

Computers work with binary numbers, which use only the digits = 384 + 40 + 8 = (432)10
‘0’ and ‘1’. Since all the digital components are based on binary
operations, it is convenient to use binary numbers when analyzing Hexadecimal number system
or designing digital circuits. In hexadecimal number system, there are 16 numbers 0 to 9, and
digits from 10 to 15 are represented by A to F, respectively. The
Number Systems with Different Base base of hexadecimal number system is 16.
Decimal number system Example 6: (1A5C)16 = 1 × 163 + A × 162 + 5 × 161 + C × 160
Decimal numbers are usual numbers which we use in our day-to- = 1 × 4096 + 10 × 256 + 5 × 16 + 12 × 1
day life. The base of the decimal number system is 10. There are = 4096 + 2560 + 80 + 12 = (6748)10 .
ten numbers 0 to 9. Table 1 Different number systems
The value of the nth digit of the number from the right side Decimal Binary Octal Hexadecimal
= nth digit × (base)n–1 0 000 0 0
Example 1: (99)10 → 9 × 101 + 9 × 100 1 001 1 1
= 90 + 9 = 99 2 010 2 2
Example 2: (332)10 → 3 × 102 + 3 × 101 + 2 × 100 3 011 3 3
= 300 + 30 + 2 4 100 4 4
Example 3: (1024)10 → 1 × 103 + 0 × 102 + 2 × 101 + × 100 5 101 5 5
= 1000 + 0 + 20 + 4 = 1024 6 110 6 6
7 111 7 7
Binary number system 8 1000 10 8
In binary number system, there are only two digits ‘0’ and ‘1’. 9 1001 11 9
Since there are only two numbers, its base is 2. 10 1010 12 A
Example 4: (1101)2 = 1 × 23 + 1 × 22 + 0 × 21 + 1 × 20 11 1011 13 B
= 8 + 4 + 1 = (13)10 12 1100 14 C
13 1101 15 D
Octal number system 14 1110 16 E
Octal number system has eight numbers 0 to 7. The base of the 15 1111 17 F
number system is 8. The number (8)10 is represented by (10)8. (Continued )
1.4 | Unit 1 • Digital Logic
Table 1 (Continued ) Example 9: (105.75)10

Decimal Binary Octal Hexadecimal
2 105
16 10000 20 10
17 10001 21 11 2 52 1
18 10010 22 12 2 26 0
19 10011 23 13 2 13 0
20 10100 24 14 6
2 1
1. For a number system with base n, the number of different 2 3 0
symbols in the number system will be n. Example: octal 1 1
number system will have total of 8 numbers from 0 to 7.
2. The number ‘n’ in the number system with base ‘n’ is (105)10 = (1101001)2
represented as (10)n. (0.75)10
3. The equivalent of number (a3a2a1a0 · a–1a–2)n in decimal Multiply 0.75 by 2 = 1.50
is a3 × n3 + a2 × n2 + a1 × n1 + a0 × n0 + a–1 × n–1 + a–2 Multiply 0.50 by 2 = 1.00
× n–2. Reading integers from top to bottom 0.75 = (0.11)2
\ (105.75)10 = (1101001.11)2
Conversion of Number Systems
The conversion of decimal to any other number system Binary to decimal conversion
involves successive division by the radix until the dividend
Example 10: (10100011)2
reaches 0. At each division, the remainder gives a digit of
converted number; and the last one is most significant digit, = 1 × 27 + 0 × 26 + 1 × 25 + 0 × 24 + 0 × 23 + 0 × 22 + 1
the remainder of the first division is least significant digit. × 21 + 1 × 20
The conversion of other number system to decimal involves = 128 + 0 + 32 + 0 + 0 + 0 + 2 +1
multiplying each digit of number system with the weight of = (163)10
the position (in the power of radix) and sum the products cal-
Example 11: (11010011.101)2
culated, the total is the equivalent value in decimal.
= 1 × 27 + 1 × 26 + 0 × 25 + 1 × 24 + 0 × 23 + 0 × 22 + 1
Decimal to binary conversion × 21 + 1 × 20 + (1 × 2–1) + (0 × 2–2) + (1 × 2–3)
Example 7: (66)10 = 128 + 64 + 0 + 16 + 0 + 0 + 2 + 1 + 0.5 + 0 + 0.125
= (211.625)10
2 66
2 33 0 Decimal to octal conversion
2 16 1 Reading remainders Example 12: (16)10
2 8 0 from bottom to top
8 16
2 4 0 0
2
2 0
Remainder from bottom to top = (20)8
1 0
Example 13: (347.93)10
= (1000010)2 (.93)10
Example 8: (928)10 0.93 × 8 = 7.44
2 928 0.44 × 8 = 3.52
0.52 × 8 = 4.16
2 464 0
0.16 × 8 = 1.28
2 232 0 ……..
2 116 0 Read the integers of octal point from top to bottom.
2 58 0 \ (0.93)10 = (0.7341)8
(347)10
2 29 0
14 8 347 3
2 1
7 8 43 3
2 0
2 3 1 5
1 1 \ (347)10= (533)8
Ans: (533.7341)8
= (1110100000)2
Chapter 1 • Number Systems | 1.5
Octal to decimal conversion 0.675 × 16 10.8

Example 14: (33)8 0.800 × 16 12.8
3 × 81 + 3 × 80 = 24 + 3 0.800 × 16 12.8
(27)10 0.800 × 16 12.8
Example 15: (1023.06)8 Decimal Hexa
10 A
1 × 83 + 0 × 82 + 2 × 81 + 3 × 80+ 0 × 8–1 + 6 × 8–2
12 C
= 512 + 0 + 16 + 3 + 0 + 0.0937 = (2095.0937)10
12 C
Octal to binary conversion 12 C
= (0.ACCC)16
To convert octal to binary, replace each octal digit with their \ Hexadecimal equivalent is
equivalent 3-bit binary representation. = (12.AC CC)16
Example 16: (7777)8
Convert each octal digit to binary Hexadecimal to decimal conversion
7 7 7 7 Example 22: (A3F)16
=
111 111 111 111 Decimal Hexa
= (111 111 111 111)2 A – 10
Example 17: (567.62)8 3 – 3
5 6 7 . 6 2 F – 15
101 110 111 . 110 010 → 10 × 162 + 3 × 161 + 15 × 160
= (101110111.110010)2 → 2560 + 48 + 15 → (2623)10
Example 23: (1F63.0EB)16
Binary to octal conversion
1 1
To convert a binary number to an octal number, starting
F 15
from the binary point, make groups of 3-bits each on either
6 6
side of the binary point, and replace each 3-bit binary group
3 3
by the equivalent octal digit. 0 0
Example 18: (010011101)2 E 14
010 011 101 B 11
= (235)8
2 3 5 → 1 × 16 + 15 × 162 + 6 × 161 + 3 × 160 × (0 × 16–1)
3
Example 19: (10010111011.1011)2 + (14 × 16–2) + (11 × 16–3)

010 010 111 011 101 100 → 4096 + 3840 + 96 + 3 + 0 + 0.0546 + 0.0026
⋅ = (2273.54)8 → (8035.0572)10
2 2 7 3 5 4
Hexadecimal to binary number system
Decimal to hexadecimal conversion
To represent hexadecimal in binary, represent each HEX
Example 20: (527)10 number with its 4-bit binary equivalent.
16 527
Example 24: (34F)16
16 32 15
Hexa Decimal Binary
2 0
3 3 0011
Decimal Hexa 4 4 0100
2 → 2 F 15 1111
0 → 0 = (001101001111)2
15 → F

= (20F)16 Example 25: (AFBC . BED) 16
Hexa Decimal Binary
Example 21: (18.675)10
A 10 1010
(18)10
F 15 1111
16 18 B 11 1011
1 2 C 12 1100
Decimal Hexa B 11 1011
1 – 1 E 14 1110
2 – 2 (18)10= (12)16 D 13 1101
(0.675)10 = (1010111110111100.101111101101)2
Binary to hexadecimal number system Example 32: 10’s complement of (2657)10 is (10)4 – 2657
To convert binary number to a hexadecimal number, start- 10000
ing from the binary point, make groups of 4-bits each on 2657
either side of the binary point and replace each 4-bit group 7343
by the equivalent hexadecimal digit. Example 33: 9’s complement of (2657)10 is (104 -1) - 2657
Example 26: (11001001)2 10000
1100 1001 – 1
→ 9999
12 9
2657
→ (C9)16
7342
Example 27: (1011011011.01111)2
•• r’s complement can be obtained by adding 1 to (r – 1)’s
0010 1101 1011 0111 1000 complement.
⋅ = (2 DB.78)16
2 D B 7 8 r m – N = {(r m - 1) – N} + 1
Example 34: 2’s complement of (101101)2 is
Hexadecimal to octal number system = (2)6 – 101101
The simplest way to convert hexadecimal to octal is, first (26)10 = (100000)2
convert the given hexadecimal number to binary and the 2’s complement is 100000
Binary number to Octal. –101101
Example 28: (C3AF)16 010011
→ 001100001110101111 Example 35: 1’s complement of (101101)2 is
→ (141657)8 26 – 1 = 1000000
Example 29: (C6.AE)16 – 1
→ 0011000110.10101110 111111
→ (306.534)8 101101
1’s complement –010010
Octal to hexadecimal number system The one’s complement of a binary number is formed by
The simplest way to convert octal to hexadecimal is first changing 1’s to 0’s and 0’s to 1’s, The 2’s complement can
convert the given octal number to binary and then the binary be formed by leaving all least significant 0’s and the first 1
number to hexadecimal. unchanged, and replacing 1’s with zeros and zeros with 1’s
in all other bits.
Example 30: (775)8
If the number M contains radix point, the point should be
→ (000111111101)2
removed temporarily in order to form r’s/ (r - 1)’s complement.
→ (1FD)16
The radix point is then restored to the complemented
Example 31: (34.7)8 number in the same relative position.
→ (00011100.1110)2
Example 36: What is 1’s complement of (1001.011)2?
→ (1C.E)16
→ Consider without radix point 1001011
Take 1’s complement 0110100
Complements Place radix point again (0110.100)2
Complements are used in digital computers to simplify the Example 37: What is 2’s complement of (1001.011)2?
subtraction operation and for logical manipulation. Consider without radix point 1001011
There are two types of complements for each base - Take 2’s complement 0110101
r-system. Place radix point again (0110.101)2
1. Radix complement (or) r’s complement: the r’s com- Complement of a complement is equal to the original
plement of an m digit number N in base r is r m – N for number r m – (r m – M) = M
N ≠ 0.
For example, N = 0, r’s complement is 0. Subtraction with Complements
2. Diminished radix complement: (or) (r -1)’s comple- Subtraction of two n digit unsigned numbers A - B in base r
ment: Given a number N in base r having m digits, then can be done as follows by r’s complement method.
(r -1)’s complement is (r m - 1) - N. Add A to the r’s complement of B. Mathematically
For example, decimal number system will have 10’s A + (r n - B) = A - B + r n
complement and 9’s complement. If A ≥ B the sum will produce an end carry r n; which can
Similarly, binary number system will have 2’s com- be discarded. (Discarding carry is equivalent to subtracting
plement and 1’s complement. r n from result). What is left is the result A – B?
A = 1100 → 1100 Other notation for representation of signed numbers is

B = 1010 (2’s complement) + 0110 signed complement system. This is convenient to use in a
Sum: 10010 computer for arithmetic operations. In this system, a nega-
discard carry (–r n) – 10000 tive number is indicated by its complement (i.e., comple-
A – B: 0010 ment of corresponding positive number) whereas the
If A < B, the sum does not produce an end carry and sign-magnitude system negates a number by changing its
result is r n - (B - A). Then take r’s complement of the sum, sign bit, the signed-complement system negates a number
and place a negative sign in front. by taking its complement. Positive numbers use same nota-
If A = 1010 tion in sign-magnitude as well as sign-complement systems.
B = 1100 The signed-complement system can be used either as the
A - B can be done as 1’s complement or the 2’s complement.
A → 1010 But 2’s complement is the most common.
B → 2’s complaint + 0100 +24 in 1’s/2’s complement representation is 011000
Sum: 1110 -24 in 1’s complement representation 100111
Here, no carry generated, so result is a negative number. -24 in 2’s complement representation 101000
2’s complement of result → 0010 = 2
Table 2 Signed binary numbers – (4-bits)
result = -2
Signed- Signed 1’s Signed 2’s
Subtraction of unsigned numbers by using (r – 1)’s com-
Decimal Magnitude Complement Complement
plement can be done in similar way. However, (r – 1)’s com-
+7 0111 0111 0111
plement is one less than the r’s complement. Because of
this, the sum produced is one less than the correct difference +6 0110 0110 0110
when an end carry occurs. So end carry will be added to the +5 0101 0101 0101
sum. Removing the end carry and adding 1 to the sum is +4 0100 0100 0100
referred to as an end-around-carry. +3 0011 0011 0011
Consider A = 1100, B = 1010 +2 0010 0010 0010
For A - B +1 0001 0001 0001
A → 1100 +0 0000 0000 0000
B → (1’s complement) + 0101 –0 1000 1111 –
Sum: 10001 –1 1001 1110 1111
End around carry + 1 –2 1010 1101 1110
A - B = 0010 –3 1011 1100 1101
For B - A –4 1100 1011 1100
B → 1010 –5 1101 1010 1011
A → (1’s complement) + 0011 –6 1110 1001 1010
Sum: 1101 –7 1111 1000 1001
There is no end carry, for there result is –8 – – 1000
– (B – A) = –(1’s complement of 1101)
= –0010 = –2 The ranges of signed binary numbers
with n-bits
Signed Binary Numbers
Signed-magnitude: −2n-1 + 1 to +2n-1 − 1
Positive integers can be represented as unsigned numbers;
1’s complement representation: −2n-1 + 1 to +2n-1 − 1
but to represent negative integer, we need a notation for
2’s complement representation: −2n-1 to +2n-1 − 1
negative values in binary.
It is customary to represent the sign with a bit placed in Signed 2’s complement representation can be directly
the left most position of the number. The convention is to used for arithmetic operations. The carryout of the sign bit
make the sign bit 0 for positive and 1 for negative. This repre- position is discarded.
sentation of signed numbers is referred to as sign-magnitude In order to obtain a correct answer, we must ensure that
convention the result has a sufficient number of bits to accommodate
the sum/product.
S Magnitude
Example 38: X = 00110, Y = 11100 are represented in
+24 is 0
11000
5-bit signed 2’s complement system
sign magnitude Then their sum X + Y in 6-bit signed 2’s complemented
–24 is 1
11000
representation is?
sign magnitude
Solution: X = 00110 If it is in 1’s complement/2’s complement form, then the

Y = 11100 magnitude of negative number can be obtained by taking 1’s
are 5-bit numbers complement/2’s complement for the number, respectively.
But result needs to be in 6-bit format. 10111011 ⇒ 1’s complement ⇒ 01000100 = (68)10.
Operands X and Y also should be in 6-bit format In 1’s complement format, the number is –68.
X= 000110 10111011 ⇒ 2’s complement ⇒ 01000101 = (69)10.
Y= 111100 In 2’s complement format, the number is –69.
X + Y = (1) 000010 Example: Find (–9.625)10 in signed 2’s complement repre
The carry out of sign bit position is discarded result is sentation.
000010. Signed binary fraction can be represented in the same
Example 39: (36x 70)10 is 10’s complement of (yzyz0)10 way of signed integer.
Then values of x, y, z are? 2 9
(A) 4, 5, 2 (B) 4, 6, 3 2 4 −1
(C) 3, 6, 3 (D) 3, 5, 4 2 2−0
Solution: (C) 1− 0
(36x70)10 is 10’s complement of (yzyz0)10. 0.625 × 2 = 1.25
10’s complement of (yzyz0)10 is 0.25 × 2 = 0.5
105 - yzyz0 = 36 × 70 0.5 × 2 = 1.0
So 36x70 + yzyz0 = 100000 = 0.101
36x70 +(9.625) = 01001.101
+yzyz0 –9.625 = 10110.011 (by taking 2’s complement)
100000
so 7 + z = 10, Binary Multipliers
1 + x + y = 10 z = 3 Multiplication of binary number is done in the same way as
1 + 6 + z = 10 y = 6 multiplication of decimal.
1 + 3 + y = 10, The multiplicand (m) is multiplied by each bit of the
→x=3 multiplier (N), starting from the LSB.
Let
Example 40: The 10’s complement of (843)11 is? M = B3 B2 B1 B0
(A) (157)11 (B) (267)11 N = A3 A2 A1 A0
(C) (156)11 (D) (268)11 If M × N = P
Solution: (B) A0B3 A0B2 A0B1 A0B0
Given (843)11 is base 11 number system and the number in A1B3 A1B2 A1B1 A1B0
the number system range from 0 to 9 & A (A = 10) A2B3 A2B2 A2B1 A2B0
10’s complement for (843)11 means (r - 1)’s complement. A3B3 A3B2 A3B1 A3B0
P7P6 P5 P4 P3 P2 P1 P0 =P
So (r n - 1) - N = [(11)n - 1] - N
(11)n - 1 ⇒ 1000 Example: Let M = 1 0 1 1
– 1 N = 1 1 0 0
AAA M × N = P
– 843 1011 ×
267 1100
10’s complement is (267)11 0000
Example 41: Consider the signed binary number to be 0000
10111011. What is the decimal equivalent of this number 1011
if it is in Sign-Magnitude form, or 1’s complement form, or 1011
2’s complement form? 111 _
10000100=P
Solution: Given binary number = 10111011. As sign bit is
1, it is a negative number. If it is in sign-magnitude format,
Binary Codes
then MSB is sign bit, and remaining bits represent the mag-
nitude, Binary codes can be classified as numeric codes and alpha-
(0111011)2 = 32 + 16 + 8 + 2 + 1 = 59. So if the given numeric codes. The figure below shows the classification
number is in sign-magnitude format, then the number is –59. of codes.
Codes
Numeric Alphanumeric
Weighted Non- Self- Sequential Error detecting Cyclic Reflecting

weighted complementing and correcting
Gray Gray
ASCII EBCDIC Hollerith

Excess 3 Gray Five bit 8421 Excess 3
BCD codes
Binary BCD 2421 5211 Excess 3 Parity Hamming
8421 2421 3321 4221 5221 5311 5421 631-1 7421 74-2-1 84-2-1
Numeric Codes Reflective codes

Numeric Codes are the codes which represent numericals in Binary code in which the n least significant bits for code
binary, i.e., only numbers as a series of 0s and 1s. words 2n through 2n + 1 – 1 are the mirror images of than for
0 through 2n – 1 is called reflective codes.
Weighted and non-weighted codes Example: Gray Code
•• The weighted codes are those which obey the position-
weighting principle. Each position of a number repre- Self-complementing codes
sents a specific weight. A code is said to be self-complementing, if the code word
Example: BCD, Binary, 84-2-1, 2421, of the 9’s complement of number ‘N’, i.e., of “9-N” can be
•• Non-weighted codes are codes which are not assigned obtained from the code word of ‘N’ by interchanging all
fixed values. the zeros and ones, i.e., by taking 1’s complement. In other
Example: Excess-3, Gray code words, logical complement of number code is equivalent to
2421, 5211, 84 – 2 – 1 are examples of weighted codes, in representation of its arithmetic complement.
which weight is assigned to each position in the number.
(27)10 in 2421 code → 0010 1101 Example: 84-2-1, 2421, XS -3.
(45)10 in 5211 code → 0111 1000 All weighted BCD codes are self-complementing codes.
(36)10 in 84 – 2 – 1 code → 0101 1010
Any digit in decimal will be represented by the weights
Binary-coded decimal (BCD)
represented by the code. In BCD, each decimal digit 0 to 9 is coded by a 4-bit binary
number. BCD codes are convenient to convert to/or from
Error-detecting and correcting codes decimal number system.
Codes which allow only error detection are error-detecting codes.
Decimal BCD Digit
Example: Parity
0 0000
Codes which allow error detection as well as correction are
1 0001
called error correcting codes.
2 0010
Example: Hamming codes
3 0011
Sequential codes 4 0100
A sequential code is one in which each succeeding code word 5 0101
is one binary number greater than the preceding code word. 6 0110
Example: XS–3, BCD 7 0111
8 1000
Cyclic codes (unit distance codes)
9 1001
Cyclic codes are those in which each successive code word
differs from the preceding one in only one bit position.
Example 42: (628)10 = (0110 0010 1000) BCD
Example: Gray code
BCD addition Excess-3 (XS-3) code

•• BCD addition is performed by individually adding the Excess-3 code is a non-weighted BCD code, where each
corresponding digits of the decimal number expressed in digit binary code word is the corresponding 8421 code word
4-bit binary groups starting from the LSB. plus 0011.
•• If there is no carry and the sum term is not an illegal code, Find the XS-3 code of
no correction is needed. Example 47: (3)10 → (0011)BCD = (0110)xS3
•• If there is a carry out of one group to the next group or if
the sum term is an illegal code, the (6)10 is added to the Example 48: (16)10 → (0001 0110)BCD
sum term of that group, and the resulting carry is added
→ (0100 1001)xS3
to the next group. Gray code
Example 43: 44 + 12 Each gray code number differs from the preceding number
by a single bit.
0100 0100 (44 in BCD)
Decimal Gray Code
0001 0010 (12 in BCD)
0 0000
0101 0110 (56 in BCD)
1 0001
Example 44: 76.9+ 56.6 2 0011
0111 0110 . 1001 3 0010
4 0110
0101 0110 . 0110
5 0111
1100 1100 . 1111 (all are illegal
0110 0110 . 0110 codes) Binary to gray conversion
0010 0010 . 0101 Step I: Shift the binary number one position to the right,
+1 +1 +1 (propagate carry) LSB of the shifted number is discarded.
0001 0011 0011 . 0101 Step II: Exclusive or the bits of the binary number with
1 3 3 . 5 those of the binary number shifted.
BCD subtraction BCD subtraction is performed by sub- Example 49: Convert (1001)2 to gray code
tracting the digits of each 4-bit group of the subtrahend Binary → 1010
from the corresponding 4-bit group of the minuend in Shifted Binary → 101 ⊕
binary starting from the LSB. Gray → 1111
Gray to binary conversion
Example 45: 42 0100 0010 ( 42 in BCD) (a) Take the MSB of the binary number is same as MSB of
−12 −0001 0010 (12 IN BCD) gray code number.
30 0011 0000 (No borrow, so this is (b) X-OR the MSB of the binary to the next significant bit
the correct difference) of the gray code.
Example 46: (c) X-OR the 2nd bit of binary to the 3rd bit of Gray code
(Borrow to get 3rd bit binary and so on.
247.7 0010 0100 0111 . 0111 (d) Continue this till all the gray bits are exhausted.
are
−156.9 0001 0101 0110 . 1001 present, Example 50: Convert, gray code 1010 to binary
90.8 0000 0111 ⋅0000 . 1110 subtract Gray 1 0 1 0
0110)
−01001 − 0110 1010 ⇓ ⊕ || ⊕ || ⊕ ||
1001 000 ⋅ 1000 Corrected 1100 1 1 0 0
difference
= (1100)2
(90.8)
Exercises
Practice Problems 1 2. If (84)x (in base x number system) is equal to (64)y (in
base y number system), then possible values of x and y
Directions for questions 1 to 15: Select the correct alterna-
are
tive from the given choices.
(A) 12, 9 (B) 6, 8
1. Assuming all the numbers are in 2’s complement rep- (C) 9, 12 (D) 12, 18
resentation, which of the following is divisible by
11110110? 3. Let A = 1111 1011 and B = 0000 1011 be two 8-bit
(A) 11101010 (B) 11100010 signed 2’s complement numbers. Their product in 2’s
(C) 11111010 (D) 11100111 complement representation is
(A) 11001001 (B) 10011100 code. For example, the base -6 number 35 will be rep-
(C) 11010101 (D) 10101101 resented by its BCH code 011101.
In this numbering system, the BCH code
4. Let r denotes number system’s radix. The only value(s)
001001101011 corresponds to the following number
of r that satisfy the equation 3 (1331) r = (11) r is/are in base -6 system.
(A) 10 (B) 11 (A) 4651 (B) 4562
(C) 10 and 11 (D) any r > 3 (C) 1153 (D) 1353
5. X is 16-bit signed number. The 2’s complement repre- 11. The signed 2’s complement representation of (-589)10
sentation of X is (F76A)16. The 2’s complement repre- in Hexadecimal number system is
sentation of 8 × X is (A) (F24D)16 (B) (FDB3)16
(A) (1460)16 (B) (D643)16 (C) (F42D)16 (D) (F3BD)16
(C) (4460)16 (D) (BB50)16
12. The base of the number system for which the following
6. The HEX number (CD.EF)16 in octal number system is 66
(A) (315.736)8 (B) (513.637)8 operation is to be correct = 13
5
(C) (135.673)8 (D) (531.367)8 (A) 6 (B) 7
7. 8-bit 2’s complement representation a decimal number (C) 8 (D) 9
is 10000000. The number in decimal is 13. The solution to the quadratic equation x2 - 11x + 13 = 0
(A) +256 (B) 0 (in number system with radix r) are x = 2 and x = 4.
(C) -128 (D) -256 Then base of the number system is (r) =
8. The range of signed decimal numbers that can be rep- (A) 7 (B) 6
resented by 7-bit 1’s complement representation is (C) 5 (D) 4
(A) -64 to + 63 (B) -63 to + 63 14. The 16’s complement of BADA is
(C) -127 to + 128 (D) -128 to +127 (A) 4525 (B) 4526
9. Decimal 54 in hexadecimal and BCD number system is (C) ADAB (D) 2141
respectively 15. (11A1B)8 = (12CD)16, in the above expression A and B
(A) 63, 10000111 (B) 36,01010100 represent positive digits in octal number system and C
(C) 66, 01010100 (D) 36, 00110110 and D have their original meaning in Hexadecimal, the
10. A new binary-coded hextary (BCH) number system values of A and B are?
is proposed in which every digit of a base -6 number (A) 2, 5 (B) 2, 3
system is represented by its corresponding 3-bit binary (C) 3, 2 (D) 3, 5
Practice Problems 2 6. Signed 2’s complement representation of (–15)10 is

(A) 11111 (B) 10001
Directions for questions 1 to 20: Select the correct alterna-
(C) 01111 (D) 10000
tive from the given choices.
1. The hexadecimal representation of (567)8 is 7. (0.25)10 in binary number system is?
(A) 1AF (B) D77 (A) (0.01) (B) (0.11)
(C) 177 (D) 133 (C) 0.001 (D) 0.101
2. (2326)8 is equivalent to 8. The equivalent of (25)6 in number system with base 7

(A) (14D6)16 (B) (103112)4 is?
(C) (1283)10 (D) (09AC)16 (A) 22 (B) 23
(C) 24 (D) 26
3. (0.46)8 equivalent in decimal is?
(A) 0.59375 (B) 0.3534 9. The operation 35 + 26 = 63 is true in number system
(C) 0.57395 (D) 0.3435 with radix
4. The 15’s complement of (CAFA)16 is (A) 7 (B) 8
(A) (2051)16 (B) (2050)16 (C) 9 (D) 11
(C) (3506)16 (D) (3505)16 10. The hexadecimal equivalent of largest binary number
5. 53 in 2’s complement from is? with 14-bits is?
(A) 1001011 (B) 001010 (A) 2FFF (B) 3FFFF
(C) 0110101 (D) 001011 (C) FFFF (D) 1FFFF
11. If x is radix of number system, (211)x = (152)8, then x is 17. Match the items correctly
(A) 6 (B) 7 Column 1 Column 2
(C) 9 (D) 5 (P) 8421 (1) Cyclic code
12. The value of r for which ( 224) r = (13) r is valid (Q) 2421 (2) self-complementing
expression, in number system with radix r is? (R) 5212 (3) sequential code
(A) 5 (B) 6 (S) Gray code (4) non-sequential code
(C) 7 (D) 8
(A) P–2, Q–4, R–3, S–1
13. Which of the representation in binary arithmetic has a (B) P–1, Q–4, R–3, S–2
unique zero? (C) P–3, Q–2, R–4, S–1
(A) sign-magnitude (B) 1’s compliment (D) P–2, Q–4, R–1, S–2
(C) 2’s complement (D) All of these
18. Perform the subtraction in XS-3 code 57.6 - 27.8
14. For the binary number 101101111 the equivalent hexa-
(A) 0101 1100.1011 (B) 0010 1001.1100
decimal number is
(C) 00011101.1100 (D) 1010 1110.1011
(A) 14E (B) 9E
(C) B78 (D) 16F 19. The 2’s complement representation of -17 is
15. Subtract 1001 from 1110 (A) 101110 (B) 111110
(A) 0010 (B) 0101 (C) 101111 (D) 110001
(C) 1011 (D) 1010
20. The decimal 398 is represented in 2421 code by
16. Which of the following is a positively weighted code? (A) 110000001000 (B) 001110011000
(A) 8421 (B) 84-2-1 (C) 001111111110 (D) 010110110010
(C) EXS-3 (D) 74-2-1
Previous Years’ Questions

1. (1217)8 is equivalent to [2009] 1, 2, 3. Define another random variable Y = X1 X2 ⊕
(A) (1217)16 (B) (028F)16 X3, where ⊕ denotes XOR. Then
(C) (2297)10 (D) (0B17)16
Pr[Y = 0|X3 = 0] = ______ [2015]
2. P is a 16-bit signed integer. The 2’s complement rep-
8. The 16-bit 2’s complement representation of an inte-
resentation of P is (F87B)16. The 2’s complement rep-
ger is 1111 1111 1111 0101; its decimal representa-
resentation of 8*P is [2010]
tion is ___ . [2016]
(A) (C3D8)16 (B) (187B)16
(C) (F878)16 (D) (987B)16 9. Consider an eight - bit ripple - carry adder for com-
3. The smallest integer that can be represented by an puting the sum of A and B, where A and B are integers
8-bit number in 2’s complement form is [2013] represented in 2’s complement form. If the decimal
(A) –256 (B) –128 value of A is one, the decimal value of B that leads to
(C) –127 (D) 0 the longest latency for the sum to stabilize is _____ .
4. The base (or radix) of the number system such that the [2016]
312 10. Let x1 ⊕x2 ⊕x3 ⊕x4 = 0 where x1 ,x2 ,x3 ,x4 are Boolean
following equation holds is ––––– = 13.1 [2014]
20 variables, and ⊕ is the XOR operator. Which one of
5. Consider the equation (123)5 = (x8)y with x and y as the following must always be TRUE?[2016]
unknown. The number of possible solutions is –––––––. (A) x1 x2 x3 x4 = 0
[2014] (B) x1 x3 + x2 = 0
6. Consider the equation (43)x = (y3)8 where x and y (C) x1 ⊕ x3 = x3 ⊕ x4
are unknown. The number of possible solutions is (D) x1 + x2 + x3 + x4 = 0
_______ [2015] 11. Consider a quadratic equation x2 − 13x + 36 = 0 with
7. Suppose Xi for i = 1, 2, 3 are independent and identi- coefficients in a base b. The solutions of this equa-
cally distributed random variables whose probability tion in the same base b are x = 5 and x = 6. Then b =
mass functions are Pr[Xi = 0] = Pr[Xi = 1] = ½ for i = __________.[2017]
Answer Keys
Exercises
Practice Problems 1
1. B 2. C 3. A 4. D 5. D 6. A 7. C 8. B 9. B 10. C
11. B 12. D 13. C 14. B 15. D
Practice Problems 2
1. C 2. B 3. A 4. D 5. D 6. B 7. A 8. B 9. B 10. B
11. B 12. A 13. C 14. D 15. B 16. A 17. C 18. A 19. C 20. C

1. B 2. A 3. B 4. 5 5. 3 6. 5 7. 0.75 8. –11 9. –1.0 10. C
11. 8.0 to 8.0
Chapter 2
Boolean Algebra and
Minimization of Functions
LEARNING OBJECTIVES
 Logic gates  K-map method

 Boolean algebra  Prime implicant
 AXIOMS and Laws of Boolean algebra  Implementation of function by using NAND-NOR
 Properties of Boolean algebra Gates
 Conversion from Min term to Max term  EX-OR, EX-NOR GATE
 Minimization of Boolean function
logic gates Table 2 Truth Table

1. Inverter or NOT gate (7404 IC): The inverter performs a Input Output
basic logic operation called inversion or complementation. A B Y
The purpose of the inverter is to change one logic level to the 0 0 0
opposite level. In terms of digital circuits, it converts 1 to 0 0 1 0
and 0 to 1.
1 0 0
A Y
1 1 1
Symbol
Y=A 3. OR gate (logical adder 7432 IC): The OR gate performs
logical, addition commonly known as OR function.
Table 1 Truth Table
A
Input Output Y
B
A Y Symbol
0 1 Y=A+B
1 0 Figure 2 2 input OR gate
2. AND gate (logical multiplier 7408 IC): The AND gate per-
forms logical multiplication more commonly know as AND Table 3 Truth Table
function. The AND gate is composed of 2 or more inputs and Input Output
a single output A B Y
2 i/p AND Gate 0 0 0
A A·B 0 1 1
B
1 0 1
Y = A·B
1 1 1
Figure 1 2 input AND gate
Chapter 2 • Boolean Algebra and Minimization of Functions | 1.15
4. NAND gate (7400 IC): The NAND gate’s function is if both inputs are unequal, then the output will be low.
basically AND + NOT function. Other name for X-NOR gate is equivalent gate.
A Y A
Y
B B
Y = A·B Symbol
Y = A  B = AB + A B
Figure 3 2 input NAND gate
Figure 6 2 input X-NOR Gate
Table 4 Truth Table
Input Output Table 7 Truth Table
A B A B Y
A⋅B A + B (Y)
0 0 1
0 0 0 1
0 1 0
0 1 0 1 1 0 0
1 0 0 1 1 1 1
1 1 1 0
X-NOR Gate is complement of X-OR Gate.
5. NOR gate (7402 IC): The NOR gate is basically OR
+ NOT function. Boolean Algebra
A Boolean algebra is a system of mathematical logic. It
Y
B is an algebraic system consisting of the set of elements
Y=A+B (0, 1), two binary operators OR and AND and one
Figure 4 2 input NOR gate unary operator NOT. The Boolean algebra is governed
by certain well-developed rules and laws.
Table 5 Truth Table
Input Output AXIOMS and Laws of Boolean Algebra
A B A+B A + B (Y) 1. AXIOMS
0 0 0 1
(a) AND operation
(1) 0 ⋅ 0 = 0
0 1 1 0
(2) 0 ⋅ 1 = 0
1 0 1 0 (3) 1 ⋅ 0 = 0
1 1 1 0 (4) 1 ⋅ 1 = 1
(b) OR operation
6. Exclusive OR gate X-OR (7486 IC): X-OR is a gate
(5) 0 + 0 = 0
in which unequal inputs create a high logic level out-
(6) 0 + 1 = 1
put and if both inputs are equal, the output will be low.
(7) 1 + 0 = 1
Other name for EX-OR gate is unequivalent gate.
(8) 1 + 1 = 1
2 input X-OR Gate
(c) NOT operation
A (9) 1 = 0
Y
B
Symbol
(10) 0 = 1
Y = A ⊕ B = AB AB 2. Laws
Figure 5 2 input X-OR Gate (a) Complementation law
(1) 0 = 1
Table 6 Truth Table (2) 1= 0
A B Y (3) If A = 0, then A = 1
0 0 0 (4) If A = 1, then A = 0
0 1 1 (5)
A= A
1 0 1
(b) AND laws
1 1 0 (1) A ⋅ 0 = 0 (NULL Law)
(4) A ⋅ 1 = A (Identity Law)
7. Exclusive NOR gate (X-NOR): X-NOR is a gate in (3) A ⋅ A = A
which equal inputs create a high logic level output; and (4) A ⋅ A = 0
(c) OR laws = 0 + AC + AB + BC
(1) A + 0 = A (NULL Law)
(2) A + 1 = 1 (Identity Law) = AC + AB + BC ( A + A)
(3) A + A = A = AB + ABC + AC + ABC
(4) A + A = 1 = AB + AC
(d) Commutative laws = LHS
(1) A + B = B + A
(2) A ⋅ B = B ⋅ A (c) De Morgan’s theorem
(e) Associative laws Law 1: A + B = A ⋅ B
(1) (A + B) + C = A + (B + C)
This law states that the complement of a sum of
(2) (A ⋅ B)C = A( B ⋅ C)
variable is equal to the product of their individual
(f) Distributive laws
complements.
(1) A(B + C) = AB + AC
(2) A + BC = (A + B) (A + C) Law 2: AB = A + B
(g) Redundant literal rule (RLR) This law states that the complement of the product
(1) A + AB = A + B of variables is equal to the sum of their individual
(2) A( A + B ) = AB complements.
(h) Idempotence laws Example 1: Simplify the Boolean function Y = A( A + B )
(1) A ⋅ A = A
(2) A + A = A Y = A ⋅ A + A⋅ B
(i) Absorption laws Solution: Y = A + AB
(1) A + A ⋅ B = A = A(1 + B )
(2) A (A + B) = A =A
3. Theorems Example 2: Simplify the Boolean function Y = A + AB
(a) Consensus theorem
Theorem 1: Solution: Y = A ⋅ ( B + 1) + A ⋅ B
AB + AC + BC = AB + AC = A ⋅ B + A + AB
Proof:
= B ( A + A) + A
LHS = AB + AC + BC
= AB + AC + BC ( A + A) = A+ B
Example 3: Simplify the Boolean function
= AB + AC + BCA + BCA
= AB(1 + C ) + AC (1 + B ) Y = A( A + B) + B( A + B)

= AB(1) + AC (1) Solution: Y = A ⋅ A + A ⋅ B + B ⋅ A + B ⋅ B
= AB + AC = A + B ( A + A) + B
= RHS. = A + B ⋅1 + B
Theorem 2:
( A + B) ( A + C ) ( B + C ) = ( A + B) ( A + C ) = A+ B + B
Proof: = A+ B
LHS = ( A + B) ( A + C ) ( B + C ) Example 4: Simplify the Boolean function
= ( AA + AC + BA + BC ) ( B + C ) Y = ABC + ABC + ABC + ABC
= ( AC + BC + AB ) ( B + C ) Solution: Y = AC ( B + B) + AC ( B + B )
= ABC + BC + AB + AC + BC + ABC = AC + AC
= AC + BC + AB = C ( A + A)
RHS = ( A + B) ( A + C ) =C
= AA + AC + BC + AB Example 5: Simplify the Boolean function
Y = ABC + ABC + ABC
= AC + BC + AB
= LHS. Solution: = AC ( B + B ) + ABC
(b) Transposition theorem = AC + ABC
AB + AC = ( A + C ) ( A + B)
= A(C + BC )
Proof:
RHS = ( A + C ) ( A + B) = A(C + B)
= AA + CA + AB + CB = A+C B
Example 6: Simplify the Boolean function So the expression inside the parentheses must be evalu-
Y = AB + C B + CA + ABD ated before all the operations. The next operation to be
performed is the complement and then follows AND and
Solution: Y = AB(1 + D ) + C B + CA finally the OR.
= AB + CB + CA Complement of function The complement of a function F
= AB + CB is F′ is obtained from an interchange of 0s for 1s and 1s for
0s in the value of F. The complements of a function may be
derived algebraically through De Morgan’s theorems.
Properties of Boolean Algebra (x1 . x2 . x3… xn)′ = x1′ + x′2 + x3′ + … + xn′
n
With n variables, maximum possible distinct functions = 22 . (x1 + x2 + x3+ … +xn)′ = x′1 . x2′ . x′3 . x′4 … x′n
Duality consider the distributive law
Example 10: The complement of function F = a(b′c + bc′)
1. x (y + z) = xy + xz is?
2. x + yz = (x + y) (x + z)
Solution: (F)′ = [a(b′c + bc′)]′
Second one can be obtained from the first law if the binary = a′ + (b′c + bc′)′
operators and the identity elements are interchanged. This = a′ + (b′c)′ ⋅ (bc′)′
important property of Boolean algebra is called the duality = a′ + (b + c)′ (b′ + c)
principle. F′ = a′ + bc + b′c′
The dual of an algebraic expression can be written by
interchanging OR and AND operators, 1s by 0, and 0s x x
xy x·y
by 1s. y y
x x
x·y = x + y x+y
Example 7: x + x ′ = 1 ←
Dual
→ x ⋅ x′ = 0 y y
x x
Solution: xy + xy ′ = x ←
Dual
→ ( x + y ) ( x + y ′) = x x+y x+y
y y
x x
x + y = xy xy
x + x ′y = x + y ←
Dual
→ x( x ′ + y ) = xy y y
x x
Example 8: The dual of F = xy + xz + yz is? y
x + y = xy
y
xy
x x
Solution: Dual of F = (x + y) (x +z) (y + z) x+y=x+y x+y
y y
= (x + xz + xy + yz) (y + z) = xy + yz + xz
So dual of xy + xz + yz is same as the function itself; Figure 7 Gates with inverted inputs
For N variables maximum possible self-dual functions
n−1 n
= 2 2 = 2( 2 / 2 )
Boolean Functions, Min Terms
Example 9: Which of the following statement/s is/are true
S1: The dual of NAND function is NOR and Max Terms
S2: The dual of X-OR function is X-NOR The starting point for designing most logic circuits is the truth
(A) S1 and S2 are true table, which can be derived from the statement of problem.
(B) S1 is true The truth table is then converted into a Boolean expression
(C) S2 is true and finally create the assembly of logic gates accordingly.
(D) None of these Let us consider the example of majority circuit. This cir-
cuit takes three inputs (A, B, C) and have one output (Y)
Solution: (A)
which will give the majority of the inputs, i.e., if A, B, C are
NAND = (xy)′ = x′ + y′ having more number of zeros. Y = 0 else if A, B, C are hav-
Dual of NAND = (x + y)′ = x′ y′ ing more number of 1s, Y = 1.
X-OR = xy′ + x′y So from the statements we can derive the truth table as
Dual of X-OR = (x + y′) (x′ + y) = xy + x′y′ = X-NOR follows:
Both S1 and S2 are true
A
Operator precedence The operator precedence for evaluat- Majority
B Y
circuit
ing Boolean expression is C
1. Parentheses
2. NOT As we are using three Boolean variables A, B, C,
3. AND total number of combinations in truth table are
4. OR 23 = 8.
Similarly for n variables, the truth table will have total of Min Term and Max Term
2n combinations, for a Boolean function. All the Boolean expressions can be expressed in a standard
Input Output sum of product (SOP) form or in a standard product of sum
(POS) form.
Sl. no. A B C Y
1 0 0 0 0 → Y = 0, If inputs •• A standard SOP form is one in which a number of prod-
2 0 0 1 0 are having more uct terms, each contains all the variables of the func-
3 0 1 0 0
zeros. tion either in complement or non-complement form are
summed together.
4 0 1 1 1 → Y = 1, If inputs
•• A standard POS form is one in which a number of sum
5 1 0 0 0 are having
more 1’s terms, each one of which contain all the variable of he
6 1 0 1 1 function either in complemented or non-complemented
7 1 1 0 1 form are multiplied together.
8 1 1 1 1 •• Each of the product term in standard SOP form is called
a min term.
For some combinations, output Y = 1, and for others Y = 0. •• Each of the sum term in the standard POS form is called
The input combinations for which output Y = 1 are called a max term.
as min terms.
Similarly the input combinations for which output Y = 0
are called as max terms. Conversion from min terms to
Min terms are expressed as product terms, Similarly, max terms representation
max terms are expressed as sum terms.
The output Y = 1, only in rows 4, 6, 7, 8. Y = ABC + ABC + ABC + ABC
So the min terms combinations are 011, 101, 110, 111 in Y ′ = ( ABC + ABC + ABC + ABC )′
Boolean Algebra, 1 input will be written as A, B, C and 0 input
= ( ABC )′( ABC )′( ABC )′( ABC )′
will be written as A, B , C in complement form, we express
(Y ′)′ = [( A + B + C )( A + B + C )( A + B + C )( A + B + C )]′
these min terms as product terms, ABC , ABC , ABC , ABC .
= [p(3, 5, 6, 7)]1 = p(0, 1, 2 ,4)
To express Y as Boolean expression, we can write it as
sum of the min terms. Y = ( A + B + C )( A + B + C )( A + B + C )( A + B + C )
Y = AB C + AB C + ABC + ABC or Y = S(3, 5, 6, 7) = p(0, 1, 2, 4)
We know that AND operation is a product while OR is sum.
So the above equation is a sum of the products (SOP), (or) Conversion from normal SOP/POS form
min terms expression.
to canonical SOP/POS
The other way of expressing Y is Y = Sm (3, 5, 6, 7).
Y = m3 + m5 + m6 + m7. Let us consider f ( A, B, C ) = A + BC + AC
The min term numbers are the decimal equivalent of input The above function is in normal (minimized) SOP
binary combinations. from, to convert this function to standard SOP(or) canoni-
Similar to SOP we can have product of sums (POS) cal SOP form, include missing variable in each and every
Boolean expression. term, to make it complete. First term A, Missing literals
The output Y = 0 for the input combinations 000, 001, are B, C. Consider A X X, so possible combinations are
010, 100. For max terms 1 input will be indicated as A, B , C ABC , ABC , ABC , ABC or we can write
in complement form, 0 input will be indicated as A, B, C
and max terms are expressed as sum terms. A = A = A( B + B)(C + C ) = ABC + ABC + ABC + ABC
Second term BC-missing literal is A. Consider XBC ⇒ So
A + B + C, A + B + C , A + B + C , A + B + C
possible combinations are ABC, ABC or we can write
Any function can be expressed as product of max terms.
BC = ( A + A) BC
So Y = ( A + B + C ) ( A + B + C ) ( A + B + C ) ( A + B + C )
= ABC + ABC
The above equation is a product of sum expression (POS) or
max terms expression. Third term AC = missing literal is B. Consider AXC → so
In other way Y = pM (0, 1, 2, 4) possible combinations are ABC , A, BC or we can write
= M0 ⋅ M1 ⋅ M2 ⋅ M4
AC = A( B + B )C
The max term numbers are decimal equivalents of cor-
responding input binary combinations. = ABC + ABC
Now, f ( A, B, C ) = ABC + ABC + ABC + ABC + ABC , after m0 m1 m3 m2

removing the redundant terms. m4 m5 m7 m6
Now consider
yz
f ( A, B, C ) = ( A + B ) ( A + C ) x 00 01 11 10
0 x ′y ′z x ′y ′z x ′yz x ′y z ′
To convert this expression to canonical form or standard
1 xy ′z ′ xy ′z xyz xyz ′
POS form we can write
3-variable K-map
f ( A, B, C ) = ( A + B + C ⋅ C ) ( A + B ⋅ B + C )
Here the C variables is absent from first term and B from Four-variable K-maps
second term. So add C ⋅ C = (0) to first, and B ⋅ B to second, The K-map for four variables is shown here, 16 min terms
and using distributive law arrive at the result. are assigned to 16 squares.
yz
f ( A, B, C ) = ( A + B + C ) ( A + B + C ) ( A + B + C )( A + B + C ) 00 01 11 10
wx
00 0 1 3 2
Minimization of Boolean Functions 01 4 5 7 6

11 12 13 15 14
Simplification Procedure 10 8 9 11 10
•• Obtain truth table, and write output in canonical form or
standard form The map is considered to lie on a surface with the top
•• Generate K-map! and bottom edges as well as the right and left edge touching
•• Determine Prime implicants. each other to form adjacent squares.
•• Find minimal set of prime implicants. •• One square → a min term of four literals
•• Two adjacent square → a term of three literals
Karnaugh Map (K-map) Method •• Four adjacent square → a term of two literals
Karnaugh map method is a systematic method of simplify- •• Eight adjacent square → a term of one literal
ing the Boolean expression. K-map is a chart or a graph •• Sixteen adjacent square → The constant one
composed of an arrangement of adjacent cell, each repre-
senting a particular combination of variable in sum or prod-
uct form. (i.e., min term or max term). Don’t-care Combinations
It can often occur that for certain input combinations, the
Two-variable K-map value of the output is unspecified either because the input
combination are invalid or because the precise value of the
x y F output is of no consequence. The combination for which
0 0 m0 y 0 the values of the expression are not specified are called
0 1 m1 x 1
don’t-care combinations. During the process of design
1 0 m2 m0 m1 0 x ′y ′ x ′y
using an SOP, K-map, each don’t-care is treated as a 1 if
1 1 m3 m2 m3 1 xy ′ xy
it is helpful in Map Reduction, otherwise it is treated as
a 0 and left alone. During the process of design using a
POS K-map, each Don’t-care is treated as a 0 if it is useful
Three-variable K-map in Map Reduction, otherwise it is treated as a 1 and left
A three-variable map will have eight min terms (for three alone.
variables 23 = 8) represented by 8 squares
Example 11: Find the Minimal expression
x y z F Sm (1, 5, 6, 12, 13, 14) + d (2, 4)
0 0 0 m0
m1
Solution: CD
0 0 1 00 01 11 10
AB
0 1 0 m2 00 1 ×
0 1 1 m3 01 × 1 1
1 0 0 m4 11 1 1 1
1 0 1 m5 10
1 1 0 m6
1 1 1 m7 ∴ F = BC + BD + ACD
Pairs, Quads and Octets Octet

BC The group of eight cells will form one octet.
A 00 01 11 10
0 1 1 ZW
XY 00 01 11 10
1
00
The map contains a pair of 1s those are horizontally adja- 01 1 1 1 1
cent. Those cells represent A BC , ABC . 11 1 1 1 1
For these two min terms, there is change in the form of 10
variable B. By combining these two cells we can form a F=Y
pair, which is equal to A BC + ABC = AC ( B + B) = AC .
If more than one pair exists on K-map, OR the simplified Other variable X, Z, W changes their form in octet. Octet
products to get the Boolean function. can eliminate three variables and their complements.
CD CD
AB 00 01 11 10 AB 00 01 11 10
00 1 1 1 00 1 1
BC
A 00 01 11 10 01 1 01 1 1
0 1 1 11 1 11 1 1
1 1 1 10 1 1 1 10 1 1
F = AC + AC F = AC D + A BD + AB C + AC D F=D
Other variable A, B, C are vanished.
So Pair eliminates one variable by minimization.
Eliminating Redundant Groups
Quad
Quad is a group of four 1s those are horizontally or verti- BC BC
A 00 01 11 10 A 00 01 11 10
cally adjacent.
0 1 1 0 1 1
BC BC
00 01 11 10 00 01 11 10 1 1 1 1 1 1
A A
0 1 1 0 1 1
AB + AC + BC AB + AC
1 1 1 1 1 1
F = C F = AC + AC = ( A + A)C = C Here BC is redundant pair, which covers already covered
min terms of AB, AC .
By considering two pairs also it will be simplified to C.
Quad eliminates two variables from the function RS
CD PQ 00 01 11 10
AB 00 01 11 10 00 1
00 1 1 1 1 1
01
01 1 1 11 1 1 1
11 1 1
10 1
10 1 1
This K-map gives fourpairs and one quad.
F = BD + BD
RS
Corner min terms can from a Quad PQ 00 01 11 10
RS 00 1
PQ 00 01 11 10 01 1 1 1
00 1 1 11 1 1 1
01 10 1
11
10 1 1 But only four pairs are enough to cover all the min times,
Quad is not necessary.
F = QS P RS + PQR + PQR + PRS is minimized function.

Prime Implicant A B C
The group of adjacent min terms is called a Prime Implicant,

i.e., all possible pairs, quads, octets, etc.
BC
A 00 01 11 10
0 1 1 1
1 1 1 F
Prime implicants are B C , BC , C , A B. Minimized function

is C + A B
Essential Prime Implicant

The prime implicant which contains at least one min term
Figure 8 Logic diagram
which cannot be covered by any other prime implicant is
called Essential prime implicant. Example 13: Find the minimal expression for Sm (2, 3, 6,
BC
7, 8, 10, 11, 13, 14)
A 00 01 11 10
0 1 1
Solution: K-map is:
1 1 1 1 CD
AB 00 01 11 10
Min term 0, 6 can be grouped with only one pair each. 0 1 3 2
00 1 1
The total possible prime implicants are A B, BC , AC , AB
4 5 7 6
but min term 0, 6 can be covered with A B, AB . So we call 01 1 1
them as essential prime implicants. Min term 5 can be 12 13 15 14
paired with any of 1 or 7 min term. 11 1 1
ZW 8 9 11 10
XY 00 01 11 10 10 1 1 1
00 1 1
01 1 1
∴ F ( A, B, C , D ) = ABCD + ABD + AC + BC + CD
11 1 1
10 1 Example 14: Three Boolean functions are defined as below
f1 = Sm(0, 1, 3, 5, 6), f2 = Sm(4, 6, 7) f3 = Sm(1, 4, 5, 7),
The essential prime Implicants are XZW , X Y Z then find f.
Redundant Prime Implicant f1

f
The prime implicant whose min terms are already cov- f2
ered by at least one min term is called redundant prime
f3
implicants.
BC
A 00 01 11 10 Solution: When two Boolean functions are ANDed, the
0 1 1 resultant will contain the common min terms of both of
1 1 1
the functions (like, intersection of min terms). If two
Boolean functions are ORed, then resultant is the combi-
Here prime implicants are A B , AC , BC . But BC is nation of all the min terms of the functions (like union of
already covered by other min terms So BC is redundant min terms)
prime implicant. Here f = f1 f 2 ⋅ f 3 = f1 f 2 + f 3
Example 12: Find the minimal expression for Sm(1, 2, 4,
6, 7) and implement it using Basic gates. Here f1 ⋅ f2 = Common min terms in f1 and f2 = Sm(6)
f1 ⋅ f2 + f3 = Combination of min terms of f1 ⋅ f2 and f3
Solution: K-map is
BC
= ∑(1, 4, 5, 6, 7)
A 00 01 11 10 Example 15: What is the literal count for the minimized
0 1 1 SOP, and minimized POS form for the following function?
1 1 1 1 f(A, B, C, D) = ∑m(0, 1, 2, 5, 12) + fd(7, 8, 10, 13, 15)
Solution: f(A, B, C, D) = ∑m(0, 1, 2, 5, 12) + f (7, 8, 10,
F = AC + AB + BC + BC + ABC 13, 15)
CD
00 01 11 10
Implementation of Function
AB
00 1 1 1 by Using Nand–Nor Gates
01 1 × NAND or NOR gates are called as universal gates, because
11 1 × × any function can be implemented by using only NAND
10 × ×
gates or only using NOR gates.
A AB
AB AND gate
B
f = 1 quad + 2 pairs A A · B = A + B OR gate

A
Literal count = 1 × 2 + 2 × 3 = 8
f (A, B, C, D) = pM(3, 4, 6, 9, 11, 14) + f(7, 8, 10, 13, 15) B
B
CD A
AB 00 01 11 10 A·A
A = A NOT gate
00 1 0 1 A
01 0 × 0 A · AB
11 × × 0
A AB A · AB + B · AB = A ⊕ B
10 × 0 0 × B
AB
f will consists of 3 quads + 1pair B · AB

=3×2+1×3=6+3=9 Figure 9 Implement of basics gates by using NAND gates
A A + A = A NOT gate
A
A A + B = AB AND gate
B
B
A A+B
A + B OR gate
B
A·A+B
A A−B (A + A + B )(B + A + B ) = AB + A B = A  B
B EX–OR, EX-NOR gate
AB + AB ) = A ⊕ B
(B · A + B)
Figure 10 Implementation of basic gates by using NOR gates
Any function which is in the SOP form can be imple- B

mented by using AND-OR gates, which is also equivalent A f = AB + AC
to NAND–NAND gates.

F = AB + AC
B AB C
A f = AB + AC Now the circuit is in completely in NAND – NAND form
So the functions expressed in SOP form, can be imple-
AC mented by using AND – OR, (or) NAND–NAND gates.
Any function in POS from, can be implemented by using
C
OR–AND gates, which is similar to NOR–NOR gate.
By considering bubble at AND gate output and OR gate Example 16: How many number of NAND gates are
input, and by changing NOT gates to NAND gates the cir- required to implement f (A, B, C) = AB + BC + AC
cuit becomes as, (A) 3 (B) 4 (C) 5 (D) 6
Solution: A Now the circuit consists of all NOR gates. Three NOR
B Gates are required.
B f (A, B, C)
C Example 19: How many number of two-input NAND–
A NOR gates are required to implement three-input NAND–
C NOR gates respectively?
By considering bubbles at output of AND gate and input of (A) 2, 2 (B) 2, 3
OR gate. (C) 3, 2 (D) 3, 3
A
B Solution: f ( A, B, C ) = ABC = AB + C
B f (A, B, C) (1) Implement above function by using two-inputs gates
C
A
A
C B
So four NAND gates are required. C

Example 17: Number of NAND gates required for
implementation of f ( A, B) = A + BC is Now convert each gate to NAND gate
(A) 3 (B) 4 (C) 5 (D) 6 A AB AB
ABC =
Solution: A B
f (A, B ) C = f (A, B, C)
B Three two-input NAND gates are required.

C (2) G ( A, B, C ) = A + B + C Implement it by using two-
To convert the all gates into NAND gates, place bubble input gates
output of AND, and inputs of OR gates. Now, the circuit A
can be drawn as B
A C
f (A, B )
Now convert each gate to NOR gate
B A
C B
Four NAND gates are required.
C
Example 18: f = A + BC, the number of NOR gates required
to implement f, are? Three two-input, NOR gates are required.
(A) 3 (B) 4 (C) 5 (D) 2
Solution: A + BC is in SOP form. EX-OR, EX-NOR Gates
To implement this function by using NOR gates, we can Inverted inputs for EX OR, EX-NOR gates
write f (A, B, C) = A + BC = (A + B) (A + C)
Which is in the form of POS? A
B
A
B A ⊕ B = AB + A B = AB + A B = A B
f (A, B, C )
A
A B
C A ⊕ B = AB + A B = AB + A B = A B
By including bubbles at output of OR gate, and input of
AND gate, the circuit becomes A
B
A
B A ⊕ B = A B + A B = AB + AB = A ⊕ B
f (A, B, C ) A
B
A
C A B = AB + A B = AB + AB = A ⊕ B
A Example 20: For the logic circuit shown in figure, the

B required input condition (A, B, C) to make the output X = 0 is?
A B = AB + A B = AB + AB = A ⊕ B A
B
A
X
B
C
A B = A B + AB = A B + AB = A B
From the above discussions we can conclude that inverted (A) 1, 1, 1 (B) 1, 0, 1
input EXOR gate is EX-NOR gate. (C) 0, 1, 1 (D) 0, 0, 1
Similarly, inverted input EX-NOR gate is EX-OR gate. If Solution: (D)
both inputs are inverted the EX-OR / EX-NOR will remain To get output X = 0, all inputs to the NAND gate should be
as it is. 1, so C = 1.
Consider a three-inputs X-OR gates by using two-input When C = 1, the output of X-OR gate B⊕C = 1 only when
XOR gates. B = 0.
If B = 0 the output of X-NOR gate A ⊙ B = 1.
A Only when A = 0
A⊕B⊕C
B So X = 1, only when (A, B, C) = (0, 0, 1).
C Example 21: The minimized expression of
A
A ·B ·C ( A + B) ( AB + AC ) ( AC + B) is
B
Solution: ( A + B) ( AB + AC ) ( AC + B)
C
= ( A + B ) ( AB ⋅ AC + AB ⋅ B + AC ⋅ AC + AC ⋅ B)
A
B
A⊕B · C = ( A + B) ( AB + ABC ) = ( A + B) AB(1 + C )
= AB + AB = AB
C
Example 22: The Boolean function f is independent of
A
A ⊕B ⊕C (A) a (B) b
B
(C) c (D) None of these
C Solution: (A)
So we can conclude that A ⊕ B ⊕ C = A ⊙ B ⊙ C A
B F
A⊕ B ⊕C = A B C
A C
B
F = ab ⋅ bc
C
= ab + bc = ab + b + c
A
A⊕B · C
B = b + c is independent of ‘a’.
Example 23:
C
A
A
A B
A · B⊕C
B
C B
C
A⊕ B ⊕C = A B C = A⊕ B C f=?
A
=A⊙B⊕C
C
A⊕B⊕C⊕D=A⊕B⊙C⊙D=A⊙B⊙C⊕D=A
⊙B⊕C⊙D
A B C D = A⊕ B ⊕C ⊕ D A
A⊙B⊙C⊙D=A⊕B⊕C⊙D=A⊕B⊙C⊕D B
Y = ( A ⋅ B ⋅ AB ) = ( A + B ) ( A + B) ∵ ( A ⋅ B = A + B )
Solution: f = {A ⊕ B ⊕ B ⊕ C } ⊕ {A ⊕ C ⊕ B ⊕ A}
={A ⊕ 0 ⊕ C} ⊕ {0 ⊕ C ⊕ B} = ( A + B) + ( A + B) = A ⋅ B + A ⋅ B
=A ⊕ C ⊕ C ⊕ B = A ⊕ 0 ⊕ B = A ⊕ B = A⋅ B + A⋅ B = A ⊕ B
Example 4: Simplify the Boolean function A ⊕ A B ⊕ A

Solved Examples Solution: A ⊕ A B ⊕ A
Example 1: Simplify the Boolean function, x y + x′z + y z
Associativity
Solution: x y + x′ z+ y z
By using consensus property = 1 ⊕ AB = A B
xy + x′z + yz = xy + x′z = A + B (∵ De Morgan’s)
Y = xy + x′z
Example 5: AB
Example 2: The output of the given circuit is equal to CD 00 01 11 10
A 00 0 0 1 1
B 01 0 × × 1
11 × × 1 ×
10 1 0 1 1
A
The minimized expression for the given K–map is
B
Solution: AB
CD 00 01 11 10
Solution: A B = AB + AB
00 0 0 1 1
A 01 0 × × 1
1
B 11 × × 1 ×
3 y 10 1 0 1 1
A
2 X OR gate = A+ BC
B
Example 6: In the figure shown, y2, y1, y0 will be 1s
A B = AB + AB complement of x2 x1 x0 if z = ?
So the output of above circuit is ‘0’. As two inputs are same x0

y0
at third gate.
Output of XOR gate with two equal inputs is zero.
x1
\y=0 y1
Example 3: The circuit shown in the figure is functionally

x2
equivalent to y2
A
z=?
B
A Solution: We are using X-OR gate
∴ XOR out-put is complement of input only when other
B input is high.
∴Z=1
Solution:
Example 7: The output y of the circuit shown is the figure is
A
A A·B A
(A + B )
y=A⊕B B
B
A C y
B A · B (A + B ) D
B E
Solution: Example 8: Simplify the following function

A A+B
B (A + B ) · C f = A( AB) ⋅ B( AB)
C y
Solution: A( AB) ⋅ B( A⋅ B )
D DE
E DE
[ A + ( AB)]⋅[ B + ( AB)] = A + ( AB) + ( B + AB)
y = ( A + B) ⋅ C ⋅ DE = ( A + B) ⋅ C + DE
= A⋅( AB ) + B⋅( AB ) = A ⋅ ( A + B ) + B( A + B)
= ( A + B )C + DE ( x ⋅ y = x + y ) = A⋅ A + A B + B A + B⋅ B = A + B = AB
Exercises
Practice Problems 1 are high. The minimized Boolean expression for the
Directions for questions 1 to 25: Select the correct alternative out put is
from the given choices. (A) AB + BC + AC
1. The output of the following circuit is (B) ABC + ABC + ABC + ABC
A (C) ABC + ABC + ABC
(D) AB + BC + AC
6. Consider the following logic circuit whose inputs are
(A) 0 (B) 1 functions f1, f2, f3 and output is f.
(C) A (D) A′ f1(x, y, z)
2. The circuit which will work as OR gate in positive level
will work as ___ gate in negative level logic f 2(x, y, z) f (x, y, z)
(A) NOR gate
(B) NAND gate f 3(x, y, z)
(C) Both NAND and NOR gate Given that f1(x, y, z) = ∑(0, 1, 3, 5) f2 (x, y, z) = ∑(6, 7)
(D) AND gate and f(x, y, z) = ∑(1, 4, 5), then f3 is
3. Four logical expressions are given below: (A) ∑(1, 4, 5) (B) ∑(6, 7)
(a) A ⋅ B ⋅C ⋅ D E ⋅ F ⋅ G ⋅ H (C) ∑(0, 1, 3, 5) (D) None of these
(b) AB ⋅CD ⋅ EF ⋅GH 7. The circuit shown above is to be used to implement
the function z = f ( A, B) = A + B what values are to be
(c) A + B + C + D + E + F + G + H selected for I and J?
(d) ( A + B) (C + D ) ( E + F ) (G + H ) I J
Two of these expression are equal. They are
(A) c and d (B) b and d
A
(C) a and b (D) a and c Z
4. For the logic circuit shown in figure, the simplified
Boolean expression for the out put y is
A (A) I = 0, J = B (B) I = 1, J = B
B (C) I = B, J = 1 (D) I = B, J = 0
8. Parity checker output from the below figure, if input is
11111 (D4 D3 D2 D1 D0) and 10000 (D4 D3 D2 D1 D0).
y
{1 = error, 0 = no error}
D4
C E
D3
(A) A+B+C (B) A D2
(C) ABC (D) BC
D1
5. In a digital system, there are three inputs A, B and C.
The output should be high when at least two inputs D0
(A) error, error 13. The Boolean expression for P is

(B) error, no error A
(C) no error, error B
(D) no error , no error P
9. For the given combinational network with three inputs Y

A, B and C, three intermediate outputs P, Q and R, and C
two final outputs X = P ⋅ Q = ∑(0, 2, 4) and Y = P ⋅ R
= ∑(1, 2, 4, 6) as shown below. Find the smallest
function P(containing minimum number of min terms (A) AB (B) AB
that can produce the output x and y) (C) A + B (D) A + B
Q 14. The Boolean expression for the truth table is
A x = ∑(0, 2, 4)
A B C f
B 4:1 P
0 0 0 0
C y = ∑(1, 2, 4, 6)
R 0 0 1 0
0 1 0 0
(A) ∑(2, 4)
0 1 1 1
(B) ∑(0, 1, 2, 4, 6)
1 0 0 0
(C) ∑(3, 5, 7)
(D) ∑(1, 2, 6) 1 0 1 0
1 1 0 1
10. The standard form of expression AB + ACD + AC is 1 1 1 0
(A) ABCD + ABCD + ABCD + ABCD + ABCD
(A) B( A + C ) ( A + C ) (B) B ( A + C ) ( A + C )
+ ABCD + ABCD + A BCD + ABCD
(C) B( A + C ) ( A + C ) (D) B ( A + C ) ( A + C )
(B) AB + ACD + AC
15. Simplify (d represents don’t-care)
(C) ABC + ABC + ABCD + ACB + ACB D AB
(D) ABC D + ABCD + ABC + ABD + ABC C 00 01 11 10
0 1 d 1
11. Factorize ABC D + ABCD + ABCD + ABCD 1 1 d 1
(A) B + C (B) AB + CD
(C) BC (D) AC (A) B (B) B + C
12. The K-map of a function is as shown. Find the function. (C) B + A (D) A + C
yz
wx 00 01 11 10
1 1 16. Simplify ( AB + C ) ( A + B + C )
1 1 1 1
(A) ( A + B + C ) ⋅ ( A + B + C )
1 1
1 1 (B) ( A + B + C ) ⋅ ( A + B + C )
(A) wx (B) z (C) ( A + B ) ⋅ ( A + B + C )
(C) w ( z + z ) + zw (D) wx + z (D) None of these
17. The point P in the figure is stuck at 1. The output f will be

1 8 9
3 5 A
f
B P
7
4 6
2
(A) ABC (B) A (C) ABC (D) A

18. Find the function represented by the figure (A) ABC + DBC, 4 (B) ABC + DAC , 3
4
1 A (C) DAC + DBC , 1 (D) ABC + DBC , 2
A
21. The function f = A ⊕ B ⊕ C ⊕ D is represented as
B
5 (A) f (A, B, C, D) = ∑(2, 6, 10, 11, 12, 13, 14)
2 B
B Output (B) f (A, B, C, D) = ∑(3, 5, 7, 10, 11, 12, 13, 14)
(C) f (A, B, C, D) = ∑(1, 2, 6, 8, 10, 12, 13, 14)
C
6 (D) f (A, B, C, D) = ∑(1, 2, 4, 7, 8, 11, 13, 14)
3 C
A 22. Find the function represented
B x0
…… f
x1
(A) A + B + C (B) AB x2 x3 xn − 2 xn − 1 xn
(C) AB + C (D) B + C
(A) (x0 + x1) (x2 + x3) (x4 + x5) … (xn-1 + xn)
19. A staircase light is controlled by two switches, one is (B) x0 + x1 + x2 + x3 + … + xn
at the top of the stairs and other at the bottom of stairs. (C) x0x2x4 … xn + x1x2 … xn + xn-1 xn
Realization of this function using NAND logic results (D) x0x1 + x2x3 + … + xn-1 xn
in which of the following circuits? (Assume S1 and S2 23. The minimum number of NAND gates required to
are the switches) implement A ⊕ B ⊕ C is
(A) (A) 8 (B) 10
S1 (C) 9 (D) 6
f
24. Which of the following circuit will generate an odd
S2 parity for a 4-bit input? (Assume ABCD as input)
(A) A
B
Output
(B) S1
C
S2
f D
(B) A
S1 B Output
S2
C
(C)
D
S1
f (C) A
B Output
C
S2
(D) D
S1
(D) A
S2
B Output
f
C
S1
D
S2
25. For the output F to be 1 in the circuit, the input combi-
20. For the given figure simplify the expression and find nation should be
which is the redundant gate?
A A
B 1 B
C
4 X
D
A 2 F
C
C
D
B 3 (A) A = 1, B = 1, C = 0 (B) A = 1, B = 0, C = 0
C (C) A = 0, B = 1, C = 0 (D) A = 0, B = 0, C = 1
Practice Problems 2 (A) w = z , x = y (B) = w z= ,x z

Directions for questions 1 to 25: Select the correct alternative
(C) w = y (D) w = y = z
from the given choices.
1. An OR Gate has six inputs. How many input words are 8. For the logic circuit shown in the figure, the required in
there in its truth table? put condition (A, B, C) to make the output (x) = 1 is
(A) 6 (B) 36 A
(C) 32 (D) 64 B
2. Sum of product form can be implemented by using
(A) AND – OR
X
(B) NAND – NAND C
(C) NOR – NOR
(D) Both A and B
3. Which one of the following is equivalent to the Boolean (A) 0, 0, 1 (B) 1, 0, 1
expression? (C) 1, 1, 1 (D) 0, 1, 1
Y = AB + BC + CA 9. Which of the following is a basic gate?
(A) AB + BC + CA (A) AND (B) X-OR
(C) X-NOR (D) NAND
(B) ( A + B) ( B + C ) ( A + C )
10. Which of the following represent the NAND gate?
(C) ( A + B) ( B + C ) ( A + C )
(a)
(D) ( A + B) ( B + C ) (C + A)
4. What Boolean function does the following circuit
(b)
represents?
B
(c)
A C G
D Y (A) a only (B) a, b, c
(C) b, a (D) a, c
F
E 11. The universal gates are
(A) A [F+ (B + C) ⋅ (D + E)] G (A) NAND and NOR (B) AND, OR, NOT
(B) A + BC + DEF + G (C) X-OR and X-NOR (D) All of these
(C) A [(B + C) + F (D + E)] G 12. In the circuit the value of input A goes from 0 to 1 and
(D) ABG + ABC + F (D + E) part of B goes from 1 to 0. Which of the following rep-
5. The minimum number of two input NOR gates are resent output under a static hazard condition?
required to implement the simplified value of the fol- A
lowing equation B Y
f(w, x, y, z) = Sm(0, 1, 2, 3, 8, 9, 10, 11)

(A) One (B) Two (a)
(C) Three (D) Four
6. The out put of a logic gate is ‘1’ when all inputs are at (b)
logic ‘0’. Then the gate is either
(1) NAND or X-OR gate (c)
(2) NOR or X-OR gate (d)
(3) NOR or X-NOR gate (A) Output a (B) Output b
(4) NAND or X-NOR gate (C) Output c (D) Output d
(A) 1 and 2 (B) 2 and 3
13. The consensus theorem states that
(C) 3 and 4 (D) 4 and 1
(A) A + AB = A + B
7. If the functions w, x, y, and z are as follows.
(B) A + AB = A
w = R + PQ + RS (C) AB + AC + BC = AB + AC
x = PQRS + PQ RS + PQ RS (D) ( A + B)⋅ ( A + B ) = A
y = RS + PR + PQ + P ⋅ Q 14. The dual form of expression
z = R + S + PQ + P ⋅ Q ⋅ R + P ⋅ Q ⋅ S AB + AC + BC = AB + AC is
(A) ( A + B) ( A + C ) ( B + C ) = ( A + B) ( A + C ) (C) logic 0 voltage level is lower than logic 1 voltage

level.
(B) ( A + B) ( A + C ) ( B + C ) = ( A + B ) ( A + C ) (D) logic 0 voltage level is higher than logic 1 voltage
(C) ( A + B ) ( A + C ) ( B + C ) = ( A + B ) ( A + C ) level.
(D) AB + AC + BC = AB + AC 21. If the input to a gate is eight in number, then its truth
15. The max term corresponding to decimal 12 is table contains _______ input words.
(A) 128 (B) 8
(A) A + B + C + D (B) A + B + C + D
(C) 64 (D) 256
(C) ABCD (D) ABC D 22. The X-OR gate implementation using NAND gate is
16. The given circuit is equivalent to (A) A
A
B
Y
B
C Output
(B) A
D
b Y
(A) (A + C) (B + D) (B) AC + BD B
(C) (A + D) (B + C) (D) ( A + B ) (C + D ) (C) A
17. Minimized expression for Karnaugh map is
AB Y
C 00 01 11 10 B
0 1 1
(D) A
1 1 1
(A) AB + C (B) AB + C Y
B
(C) B (D) B + C
18. An XOR gate will act as ________ when one of its input
23. The equivalent of AND–OR logic circuit is
is one and as ________ when one of its input is zero.
(A) NAND–NOR (B) NOR–AND
(A) buffer, buffer (B) buffer, inverter
(C) NAND–NAND (D) NAND–OR
(C) inverter, buffer (D) inverter, inverter
24. The X-OR is equivalent to
19. The minimum number of two input NAND gates
required to implement A ⊙ B if only A and B are (A) (B)
available
(A) 6 (B) 3
(C) 5 (D) 4 (C) (D)
20. Negative logic in a logic circuit is one in which
(A) logic 0 and 1 are represented by GND and positive
25. Simplify ABC + B + BD + ABD + AC
voltage respectively.
(B) logic 0 and 1 are represented by negative and posi- (A) B (B) B + C
tive voltage. (C) C + A (D) A + B

1. Let f ( w , x, y, z ) = ∑(0, 4, 5, 7, 8, 9, 13, 15) . Which 5. If P, Q, R are Boolean variables, then
of the following expressions are NOT equivalent ( P + Q )( P ⋅ Q + P ⋅ R)( P ⋅ R + Q ) simplifies to [2008]
to f ? [2007]
(P) x′y′z′ + w′xy′ + wy′z + xz (A) P ⋅Q (B) P ⋅ R
(Q) w′y′z′ + wx′y′ + xz
(C) P ⋅Q + R (D) P ⋅ R + Q
(R) w′y′z′ + wx′y′ + xyz + xy′z
(S) x′y′z′ + wx′y′ + w′y
6. What is the minimum number of gates required to
(A) P only (B) Q and S
implement the Boolean function (AB + C), if we have
(C) R and S (D) S only
to use only two-input NOR gates? [2009]
2. Define the connective * for the Boolean variables X (A) 2 (B) 3
and Y as: X * Y = XY + X ′ Y ′. Let Z = X * Y. Consider (C) 4 (D) 5
the following expressions P, Q and R. [2007]
P : X = Y * Z Q:Y=X*Z 7. The binary operation ÿ is defined as follows [2009]
R: X * Y * Z = 1 P Q PÿQ
Which of the following is TRUE?
T T T
(A) Only P and Q are valid.
T F T
(B) Only Q and R are valid.
(C) Only P and R are valid. F T F
(D) All P, Q, R are valid. F F T
3. In the Karnaugh map shown below, × denotes a don’t- Which one of the following is equivalent to PÚQ?
care term. What is the minimal form of the function (A) ¬Qÿ¬P (B) Pÿ¬Q
represented by the Karnaugh map? [2008] (C) ¬PÿQ (D) ¬Pÿ¬Q
ab 8. The min term expansion of f(P, Q, Q) = PQ +
cd 00 01 11 10 QR + PR is [2010]
00 1 1 1
(A) m2 + m4 + m6 + m7
01 × 1
(B) m0 + m1 + m3 + m5
11 ×
(C) m0 + m1 + m 6+ m7
10 1 1 ×
(D) m2 + m3 + m4 + m5
(A) b ⋅ d + a ⋅ d 9. What is the Boolean expression for the output f of
(B) a ⋅ b + b ⋅ d + a ⋅ b ⋅ d the combinational logic circuit of NOR gates given
below? [2010]
(C) b ⋅ d + a ⋅ b ⋅ d
P
(D) a ⋅ b + b ⋅ d + a ⋅ d Q
4. Given f1, f3 and f in canonical sum of products form
(in decimal) for the circuit [2008]
Q
f1 R
f2 f
f
P
f3 R
f1 = Sm(4, 5, 6, 7, 8)
f3 = Sm(1, 6, 15) Q
R
f = Sm(1, 6, 8, 15)
then f2 is
(A) Q + R (B) P + Q
(A) Sm(4, 6) (B) Sm(4, 8)
(C) Sm(6, 8) (D) Sm(4, 6, 8) (C) P + R (D) P + Q + R
10. The simplified SOP (Sum of Product) form of the 16. The dual of a Boolean function f(x1, x2, … xn, +, .,‘),
Boolean expression. [2011] written as FD, is the same expression as that of F with
(P + Q + R) ( P + Q + R) ( P + Q + R) is + and . swapped. F is said to be self-dual if F = FD.
The number of self-dual functions with n Boolean
(A) ( PQ + R) (B) ( P + Q R) variables is [2014]
(A) 2n (B) 2n-1
(C) ( PQ + R) (D) (PQ + R) n n−1
(C) 22 (D) 22
11. Which one of the following circuits is NOT equiva- 17. Consider the following min term expression for F:
lent to a two-input X-NOR (exclusive NOR) gate?
[2011] F(P, Q, R, S) = Sm(0, 2, 5, 7, 8, 10, 13, 15)
(A) The min terms 2, 7, 8 and 13 are ‘don’t-care terms.
The minimal sum of products form for F is [2014]
(B) (A) QS + QS
(B) Q S + QS
(C) (C) Q R S + Q R S + Q R S + QRS
(D) P Q S + P QS + PQS + PQ S
18. The binary operator ≠ is defined by the following
(D) truth table
p q p≠q
0 0 0
12. The truth table [2012] 0 1 1
X Y F(X, Y) 1 0 1
1 1 0
0 0 0
0 1 0
Which one of the following is true about the binary
1 0 1 operator ≠? [2015]
1 1 1 (A) Both commutative and associative
(B) Commutative but not associative
represents the Boolean function
(C) Not commutative but associative
(A) X (B) X + Y
(D) Neither commutative nor associative
(C) X ⊕ Y (D) Y
13. What is the minimal form of the Karnaugh map shown 19. Consider the operations [2015]
below? Assume that × denotes a don’t-care term.[2012] f(X, Y, Z) = X 1 YZ + XY 1 + Y 1Z 1 and
ab g(X, Y, Z) = X 1 YZ + X 1 YZ 1 + XY.
cd 00 01 11 10
Which one of the following is correct?
00 1 × × 1
(A) Both {f } and {g} are functionally complete
01 × 1
(B) Only {f } is functionally complete
11 (C) Only {g} is functionally complete
10 1 × (D) Neither {f } nor {g} is functionally complete
20. The number of min-terms after minimizing the fol-
(A) bd (B) bd + bc
lowing Boolean expression is _______ [2015]
(C) bd + abcd (D) bd + bc + cd [D1 + AB1 + A1C + AC 1 D + A1C 1D]1
14. Which one of the following expressions does not rep- 21. Let # be a binary operator defined as [2015]
resent exclusive NOR of x and y? [2013] X # Y = X + Y where X and Y are Boolean variables.
1 1
(A) xy + x′y′ (B) x ⊕ y′ Consider the following two statements.

(C) x′ ⊕ y (D) x′ ⊕ y′
(S1) (P # Q) # R = P # (Q # R)
15. Consider the following Boolean expression for F:
(S2) Q # R = R # Q
F ( P , Q, R, S ) = PQ + PQR + PQRS
Which of the following is/are true for the Boolean
The minimal sum of products form of F is [2014] variables P, Q and R?
(A) PQ + QR + QS (B) P + Q + R + S (A) Only S1 is true
(C) P + Q + R + S (D) PR + P R S + P (B) Only S2 is true
(C) Both S1 and S2 are true Assume for all inputs (a, b, c, d), the respective com-
(D) Neither S1 nor S2 are true plements (a , b, c , d ) are also available. The above
22. Given the function F = P 1 + QR, where F is a function logic is implemented using 2-input NOR gates only.
in three Boolean variables P, Q and R and P 1 = !P, The minimum number of gates required is ________.
consider the following statements. [2015] [2017]
(S1) F = Σ(4, 5, 6) 26. If w, x, y, z are Boolean variables, then which one of
the following is INCORRECT? [2017]
(S2) F = Σ(0, 1, 2, 3, 7)
(A) wx + w(x + y) + x(x + y) = x + wy
(S3) F = p(4, 5, 6)
(B) w x ( y + z ) + w x = w + x + yz
(S4) F = p(0, 1, 2, 3, 7)
Which of the following is true?
(C) (w x ( y + x z ) + w x ) y = x y
(A) (S1) – False, (S2) – True, (S3) – True, (S4) - False (D) (w + y) (wxy + wyz) = wxy + wyz
(B) (S1) – True, (S2) – False, (S3) – False, (S4) - True 27. Given f(w, x, y, z) = ∑m(0,l,2,3,7,8,10) + ∑d(5,6,ll,15),
(C) (S1) – False, (S2) – False, (S3) – True, (S4) - True where d represents the don’t-care condition in
(D) (S1) – True, (S2) – True, (S3) – False, (S4) - False Karnaugh maps. Which of the following is a mini-
mum product-of-sums (POS) form of f(w, x, y, z)?
23. The total number of prime implicants of the function [2017]
f(w, x, y, z) = Σ(0, 2, 4, 5, 6, 10) is ______ [2015]
(A) f = ( w + z )( x + z )
24. Consider the Boolean operator # with the following (B) f = ( w + z )( x + z )
properties: [2016]
x # 0 = x, x # 1 = × , x # x = 0 and (C) f = ( w + z )( x + z )
x # × = 1. Then x # y is equivalent to (D) f = ( w + z )( x + z )
(A) x y + × y (B) x y + × y 28. Let ⊕ and ⊙ denote the Exclusive OR and Exclusive
(C) × y + x y (D) x y + × y NOR operations, respectively. Which one of the fol-
25. Consider the Karnaugh map given below, where X lowing is NOT CORRECT? [2018]
represents “don’t care” and blank represents 0. (A) P ⊕ Q = P Q
(B) P ⊕ Q = P Q
ba
00 01 11 10 (C) P ⊕ Q = P ⊕ Q
dc
(D) ( P ⊕ P ) ⊕ Q = ( P P ) Q
00
X X
29. Consider the minterm list form of a Boolean function
01 1 X
F given below.
F(P, Q, R, S) = ∑ m(0, 2, 5, 7, 9, 11)
11 1 1 + d (3, 8, 10, 12, 14)
Here, m denotes a minterm and d denotes a don’t care
X X
10 term. The number of essential prime implicants of the
function F is ______. [2018]
Answer Keys
Exercises
Practice Problems 1
1. B 2. D 3. B 4. C 5. A 6. A 7. B 8. A 9. B 10. A
11. C 12. D 13. A 14. A 15. A 16. A 17. D 18. B 19. A 20. D
21. D 22. C 23. A 24. C 25. D
Practice Problems 2
1. D 2. D 3. D 4. C 5. A 6. C 7. B 8. D 9. A 10. C
11. A 12. D 13. A 14. A 15. A 16. C 17. C 18. C 19. C 20. D
21. D 22. C 23. C 24. B 25. B

1. D 2. D 3. A 4. C 5. A 6. B 7. B 8. A 9. A 10. B
11. D 12. A 13. B 14. D 15. A 16. D 17. B 18. A 19. B 20. 1
21. B 22. A 23. 3 24. A 25. 1 26. C 27. A 28. D 29. 3
Chapter 3
Combinational Circuits
LEARNING OBJECTIVES
 Combinational logic design  Code converter

 Arithmetic circuit  Decoder
 Half adder  Designing high order decoders from lower order
 Full adder decoder
 Half subtractor  Combinational logic implementation
 Full subtractor  Encoders
 n-bit comparator  Multiplexer
 Parity bit generator and parity bit checker  Demultiplexer
introduCtion aritHMetiC CirCuits

Combinational logic is a type of logic circuit whose output is a Arithmetic circuits are the circuits that perform arithmetic opera-
function of the present input only. tion. The most basic arithmetic operation is addition.
Inputs Combinational Outputs Half Adder

X circuits Z = F (X ) Addition is an arithmetic operation, and here to implement addi-
tion in digital circuits we have to implement by logical gates. So
the addition of binary numbers will be represented by the logical
expressions. Half adder is an arithmetic circuit which performs
the addition of two binary bits, and the result is viewed in two
CoMBinational loGiC desiGn outputsum and carry.
The design of combinational circuit starts from the problem, state- The sum ‘S’ is the X-OR of ‘A’ and ‘B’ where A and B are
ment and ends with a gate level circuit diagram. inputs.
The design procedure involves the following steps:
∴ S = AB + BA = A ⊕ B
1. Determining the number of input variables and output
variables required, from the specifications. The carry ‘C’ is the AND of A and B.
2. Assigning the letter symbols for input and output. ∴ C = AB
3. Deriving the truth table that defines the required relationship
between input and output. Table 1 Truth Table
4. Obtaining the simplified Boolean function for each output Inputs Outputs
by using K-map or algebraic relations. A B S C
5. Drawing the logic diagram for simplified expressions. 0 0 0 0
We will discuss combinational circuits under the following 0 1 1 0
categories: 1 0 1 0
• Arithmetic circuits 1 1 0 1
• Code converters So, half adder can be realized by using one X-OR gate and
• Data processing circuits one AND gate.
A A
S S
B B Full adder
C out
C in
C Figure 1 Block diagram

Table 2 Truth Table
Half adder can also be realized by universal logic such as
A B Cin S Cout
only NAND gate or only NOR gate as given below.
0 0 0 0 0
0 0 1 1 0
NAND logic 0 1 0 1 0
0 1 1 0 1
S = AB + AB 1 0 0 1 0
= AB + AA + AB + BB 1 0 1 0 1
1 1 0 0 1
= A( A + B ) + B( A + B ) 1 1 1 1 1
S = ABCin + ABCin + AB Cin + ABCin

= AAB ⋅ B AB
= A ⊕ B ⊕ Cin
C = AB = A ⋅ B
Cout = ABCin + ABCin + ABCin + ABCin
= AB + (A ⊕ B) Cin
A A·B
S = AB + A Cin + B Cin
B
Full adder can also be realized using universal logic gates,
i.e., either only NAND gates or only NOR gates as explained
below.
C
AB C out = (A ⊕ B )C in + AB
A
Half adder using NAND logic HA A⊕B
B S = A ⊕ B ⊕ C in
(NC) HA
NoR logic C in
S = A ⋅ B + AB Figure 2 Block diagram of full adder by using Half adder

= AB + AA + AB + BB A S + A ⊕ B ⊕ C in
= A( A + B ) + B( A + B ) B
= ( A + B) ( A + B ) (A ⊕ B)C in + AB
= A + B + ( A + B) C out
C = A⋅ B = A ⋅ B = A + B
C in
C
Figure 3 Logic diagram of full adder
A S
B NAND logic
A ⊕ B = AAB B AB
Half adder using NOR logic So A ⊕ B ⊕ Cin
Let A ⊕ B = x then s = X ⋅ XCin Cin X ⋅ Cin
Full Adder = X ⊕ Cin
Full adder is an arithmetic circuit that performs addition of
two bits with carry input. The result of full adder is given by
two outputssum and carry. The full adder circuit is used A
S
in parallel adder circuit as well as in serial adder circuit. B
For full adder, if total number of 1’s is odd at input lines,
the sum output is equal to logic 1, and if total number of C in
C out
1’s at input lines are more than or equal to 2, then the carry
output is logic 1. Figure 4 Logic diagram of a full adder using only 2-input NAND gates
Chapter 3 • Combinational Circuits | 1.37
NOR logic nor logic

Full adder outputs
Sum = a ⊕ b ⊕ c, carry = ab + bc + ac are self dual d = A⊕ B
functions = AB + AB
∴
[ A function is called as self dual if its dual is same as
= AB + BB + AB + AA
the function itself f D = f ]
For self dual functions, the number of NAND gates are = B ( A + B) + A( A + B)
same as number of NOR gates. = B + A+ B + A+ A+ B
By taking the dual for above NAND gate implementa-
tion, all gates will become NOR gates, and the output is b = AB
dual of the sum and carry, but they are self dual (f D = f ). = A( A + B )
So, output remain same, and only 9 NOR gates are required for
full adder, structure similar to NAND gate circuit. = A ( A + B)
= A + ( A + B)
Half Subtractor
Half subtractor is an arithmetic circuit which performs subtrac-
A+A+B
tion of one bit (subtrahend) from other bit (minuend), and the b
result gives difference and borrow each of one bit. The borrow
A
output is logic 1 only if there is any subtraction of 1 from 0. d
B
When a bit ‘B’ is subtracted from another bit ‘A’, a dif-
ference bit (d) and a borrow bit (b) result according to the
rule given below. B+A+B
Table 3 Truth Table Figure 6 logic diagram of half subtractor using NOR gate
A B d b
0 0 0 0
1 0 1 0 full Subtractor
1 1 0 0 Full subtractor is an arithmetic circuit similar to half sub-
0 1 1 1 tractor but it performs subtraction with borrow, it involves
subtraction of three bitsminuend, subtrahend and borrow-
d = AB + BA in, and two outputsdifference and borrow. The subtrac-
=A⊕B tion of 1 from 0 results in borrow to become logic 1. The
b = AB presence of odd number of 1’s at input lines make difference
A as logic 1.
d
B
Table 4 Truth Table
A B bi d b
b
0 0 0 0 0
0 0 1 1 1
Figure 5 Logic diagram of a half subtractor
0 1 0 1 1
A half subtractor can also realized using universal logic either
using only NAND gates or only NOR gates as explained below. 0 1 1 0 1
1 0 0 1 0
NAND logic 1 0 1 0 0
d=A⊕B 1 1 0 0 0
= AAB ⋅ B AB 1 1 1 1 1
b = AB = B( A + B ) = B( AB) = B ⋅ AB
d = ABbi + AB bi + AB bi + ABbi
A · AB
= bi ( AB + AB ) + bi ( AB + AB)
A d
B = bi ( A ⊕ B) + bi ( A ⊕ B)
b = A ⊕ B ⊕ bi
B · AB
and Four bit parallel adder the output carry from each full adder
b = A Bbi + ABbi + ABbi is connected to the input carry of next full adder.
The bits are added with full adders, starting from the
= AB + ( A ⊕ B)bi LSB position to form the sum bit and carry bit.
A The longest propagation delay time in parallel adder
d = A ⊕ B ⊕ bi is the time it takes the carry to propagate through the full
B
adders.
bi For n-bit parallel adders consider tpds is the propagation
delay for sum of each full adder and tpdc is the propagation
b delay of carry.
The total time required to add all n-bits at the nth full
adder is
NAND logic TS = tpds + (n – 1)tpdc
d = A ⊕ B ⊕ bi So propagation delay increases with number of bits. To
overcome this difficulty we use look ahead carry adder,
= ( A ⊕ B)( A ⊕ B)bi bi ( A ⊕ B)bi
which is the fastest carry adder.
b = AB + bi ( A ⊕ B)
Ai Pi
Pi ⊕ Ci
= AB + bi ( A ⊕ B) Bi Si
= AB bi ( A ⊕ B)
Gi Pi Ci + Gi
= B( A + B ) bi bi + ( A ⊕ B) Ci + 1
Ci
A
B d
Consider the full adder circuit for ith stage, in parallel adder,
with two binary variables Ai, Bi, input carry Ci are:
bi Carry propagate (Pi) and carry generate (Gi)
b Pi = Ai ⊕ Bi
Gi = Ai ⋅ Bi
Figure 7 Logic diagram of a full subtractor using NAND logic
The output sum and carry can be expressed as
NOR logic Si = Pi ⊕ Ci
Output of full subtractor is also self dual in nature. So, same Ci + 1 = Pi Ci + Gi
circuit, with all NAND gates, replaced by NOR gates gives Now, the Boolean functions for each stage can be calculated
the NOR gate full subtractor. 9 NOR gates required. as substitute i = 0
Example 1: How many NAND gates are required for C0 is input carry
implementation of full adder and full subtractor respectively? C1 = G0 + P0 C0
(A) 11, 10 (B) 11, 11 (C) 9, 9 (D) 9, 10 Substitute i = 1, 2 …
Solution: (C) C2 = G1 + P1C1 = G1 + P1 (G0 + P0C0)
From the circuit diagrams in the previous discussion, full = G1 + P1 G0 + P1 P0 C0
adder requires 9 NAND gates and full subtractor requires
9 NAND gates. C3 = G2 + P2 C2 = G2 + P2 (G1 + P1 G0 + P1 P0 C0)
= G2 + P2 G1 + P2 P1 G0 + P2 P1 P0 C0
Binary Adder Since the Boolean function for each output carry is
A binary adder is a digital circuit that produces the arithme- expressed in SOP form, each function can be implemented
tic sum of two binary numbers. with AND–OR form or two level NAND gates.
B 3 A3 B 2 A2 B 1 A1 B 0 A0 From the above equations we can conclude that this cir-
cuit can perform addition in less time as C3 does not have to
C3 C2 C1 wait for C2 and C1 to propagate. C3, C2, C1 can have equal
F ·A F ·A F ·A F ·A C in
time delays.
The gain in speed of operation is achieved at the expense
Cout S3 S2 S1 S0 of additional complexity (hardware).
n-bit Comparator 1 0 1 1 1 0 0
The comparison of two numbers is an operation that deter- 1 1 0 0 0 0 1
mines whether one number is greater than, less than, or 1 1 0 1 0 0 1
equal to the other number. 1 1 1 0 0 0 1
A magnitude comparator is a combinational circuit that 1 1 1 1 0 1 0
compares two input numbers A and B, and specifies the out-
put with three variables, A > B, A = B, A < B: (a < b) = S(1, 2, 3, 6, 7, 11)
(a > b) = S(4, 8, 9, 12, 13, 14)
A L AB 00 1 1 1
G
01 1 1
a L ab
a b = a0b1′b0′ + a1a0b0′ + a1b1′
a b ab
0 0 0 1 0 G = a1 b1 + ( a1 b1 ) a0 b0
0 1 1 0 0 a = b is possible when a1 = b1, a0 = b0
1 0 0 0 1
So (=a b= ) ( a1 b1 )( a0 b0 )
1 1 0 1 0
A3
By considering minterms for each output. A2
A1 L A b) = ab′ B3 Comparator
B2
G A>B
B1
a1 L ab
bit of input A is equal to corresponding bit in input B.
Figure 9 2-bit comparator will have 2-bit inputs a1 a0 and b1 b0. So we can write (A = B) = (A3 ⊙ B3) (A2 ⊙ B2) (A1 ⊙ B1)
(A0 ⊙ B0).
L E G To determine whether A is greater or less than B, we
a1 a0 b1 b0 ab inspect the relative magnitudes of pairs of significant bits,
0 0 0 0 0 1 0 starting from MSB. If the two bits of a pair are equal, we
0 0 0 1 1 0 0 compare the next lower significant pair of bits. The com-
0 0 1 0 1 0 0 parison continues until a pair of unequal bits is reached.
0 0 1 1 1 0 0 for A < B, A = 0, B = 1
0 1 0 0 0 0 1 for A > B, A = 1, B = 0
0 1 0 1 0 1 0 A<B=A 3′B3 + (A3 ⊙ B3) A2′B2 + (A3 ⊙ B3)(A2 ⊙ B2)
0 1 1 0 1 0 0 × A1′B1 + (A3 ⊙ B3)(A2 ⊙ B2) (A1 ⊙ B1) A0′B0
0 1 1 1 1 0 0 A>B=A 3B3′ + (A3 ⊙ B3) A2B2′ + (A3 ⊙ B3) (A2 ⊙ B2)
1 0 0 0 0 0 1 × A1B1′ + (A3 ⊙ B3)(A2 ⊙ B2) (A1 ⊙ B1) A0B0′
1 0 0 1 0 0 1 4-bit comparator will have total 8 inputs and 28 = 256 input
1 0 1 0 0 1 0 combinations in truth table.
For 16 combinations (A = B) = 1, and for 120 combina- Decimal B2 B1 B0 G2 G1 G0

tions A B = 1 1 0 0 1 0 0 1
2 0 1 0 0 1 1
Parity Bit Generator and Parity Bit Checker
3 0 1 1 0 1 0
When digital information is transmitted, it may not be 4 1 0 0 1 1 0
received correctly by the receiver. To detect one bit error at 5 1 0 1 1 1 1
receiver we can use parity checker.
6 1 1 0 1 0 1
For detection of error an extra bit, known as parity bit, is
7 1 1 1 1 0 0
attached to each code word to make the number of 1’s in the
code even (in case of even parity) or odd (in case of odd parity). For conversion we have to find out minimized functions of
For n-bit data, we use n-bit parity generator at the trans- G2(B2, B1, B0) = ∑m(4, 5, 6, 7)
mitter end. With 1 parity bit and n-bit data, total n + 1 bit G1(B2, B1, B0) = ∑m(2, 3, 4, 5)
will be transmitted. At the receiving end n + 1 parity checker G0(B2, B1, B0) = ∑m(1, 2, 5, 6)
circuit will be used to check correctness of the data. B2
For even parity transmission, parity bit will be made 1 B0B1 00 01 11 10
or 0 based on the data, so that total n + 1 bits will have 0 1 1
even number of 1’s. For example, if we want to transmit data 1
1 1
1011 by even parity transmission, then we will use parity bit
as 1, so data will have even number of 1’s, i.e., data trans- G0(B2, B1, B0) = B′1B0+ B1B′0= B1 ⊕ B0
mitted will be 11011. At the receiving end this data will be
B2
received and checked for even number of ones. B0B1 00 01 11 10
To transmit data B3B2B1B0 using even parity, we will 0 1 1
transmit sequence P B3B2B1B0, where P = B3 ⊕ B2 ⊕ B1 ⊕ B0. 1 1 1
(Equation for parity generator)
G1(B2, B1, B0) = B′1B2+ B1B′2= B2 ⊕ B1
At the receiving end we will check data received
PB3B2B1B0 for error, E = P ⊕ B3 ⊕ B2 ⊕ B1 ⊕ B0 (equation B2
for parity checker). If E = 0 (no error), or if E = 1 (1 bit error). B0B1 00 01 11 10
0
We use EX-OR gates for even parity generator/checker
1 1 1 1 1
as EX-OR of bits gives output 1 if there are odd number of
1’s else EX-OR output is 0. G2(B2, B1, B0) = B2
Odd parity generator/checker is complement of even B2 G2
parity generator/checker. Odd parity circuits check for pres-
ence of odd number of 1’s in data.
G1
B1
Code Converters
There are many situations where it is desired to convert G0
B0
from one code to another within a system. For example, the
In similar fashion we can derive n-bit binary to gray code
information from output of an analog to digital converter is
conversion as
often in gray code, before it can be processed in arithmetic
Gn = Bn
unit, conversion to binary is required.
Gn-1 = Bn-1 ⊕ Bn
Let us consider simple example of 3-bit binary to gray
Gi-1 = Bi-1 ⊕ Bi
code converter. This will have input lines supplied by binary
codes and output lines must generate corresponding bit com- Thus conversion can be implemented by n - 1 X-OR gates
bination in gray code. The combination circuit code con- for n-bits.
verter performs this transformation by means of logic gates. For reverse conversion of gray to binary, by following
The output logic expression derived for code converter similar standard principle of conversion, we will get
can be simplified by using the usual techniques including B0 = G0 ⊕ G1 ⊕ G2, B1 = G1 ⊕ G2, B2 = G2
‘don’t-care’ if any present. For example, BCD code uses
G0
only codes from 0000 to 1001 and remaining combinations B0
are treated as don’t-care combinations. Similarly, EXS-3
uses only combinations from 0011 to 1100 and remaining
G1
combinations are treated as don’t-care. B1
The relationship between the two codes is shown in the
following truth table: G2 B2
In general for n-bit gray to binary code conversion Y0

Bi = Gn ⊕ Gn-1 ⊕ Gn-2 …⊕ Gi-1 ⊕ Gi B1 2×4 Y1
B0 Decoder Y2
Bn = Gn (MSB is same in gray and binary). It also requires
Y3
n-1 X-OR gates for n-bits.
Example 2: Design 84-2-1 to XS-3 code converter. EN
Solution: Both 84-2-1 and XS-3 are BCD codes, each needs Figure 11 2 × 4 decoder
4-bits to represent. The following table gives the relation
between these codes. 84-2-1 is a weighted code, i.e., each Table 5 Truth Table
position will have weight as specified. XS-3 is non-weighted EN B1 B0 Y3 Y2 Y1 Y0
code; the binary code is 3 more than the digit in decimal. 0 X X 0 0 0 0
84-2-1 XS-3 1 0 0 0 0 0 1
Decimal B3B2B1B0 X3X2X1X0 1 0 1 0 0 1 0
0 0000 0011 1 1 0 0 1 0 0
1 0111 0100 1 1 1 1 0 0 0
2 0110 0101
3 0101 0110
Y 0 = EN · A · B
4 0100 0111
5 1011 1000
Y 1 = EN · A · B
6 1010 1001 A
7 1001 1010
8 1000 1011 B Y 2 = EN · A · B
9 1111 1100 EN
Y 3 = EN · A · B
We will consider minterm don’t-care combinations as 1, 2, 3,
12, 13, 14. For these combinations 84-2-1 code will not exist
Figure 12 2 × 4 decoder
and the remaining minterms can be found from truth table.
X0(B3, B2, B1, B0) = ∑m(0, 4, 6, 8, 10) Decoder outputs are implemented by AND gates, but reali-
+ ∑ Φ(1, 2, 3, 12, 13, 14) = B0 zation of AND gates at circuit level is done by the NAND
gates (universal gates). So, the decoders available in IC form
X1(B3, B2, B1, B0) = ∑m(0, 4, 5, 8, 9, 15) are implemented with NAND gates, i.e., the outputs are in
+ ∑ Φ(1, 2, 3, 12, 13, 14) = B1 complemented form and outputs are maxterms of the inputs
rather than minterms of inputs as in AND gate decoders.
X2(B3, B2, B1, B0) = ∑m(4, 5, 6, 7, 15) Furthermore, decoders include one or more enable inputs
+ ∑Φ(1, 2, 3, 12, 13, 14) = B2 to control the circuit operation. Enable can be either active
X3(B3, B2, B1, B0) = ∑m(8, 9, 10, 11, 15) low/high input.
+ ∑Φ(1, 2, 3, 12, 13, 14) = B3
EN
Decoder 2×4
Y 0 = EN + B1 + B0
A binary code of n-bits is capable of representing up to 2 n B1 Decoder Y 1 = EN + B1 + B0
elements of distinct elements of coded information. B0 with NAND Y 2 = EN + B1 + B0
gates
The three inputs are decoded into eight outputs, each rep- Y 3 = EN + B1 + B0
resenting one of the minterms of the three input variables.
A decoder is a combinational circuit that converts binary Figure 13 Active low 2 × 4 decoder
information from n input lines to a maximum 2n unique out-
put lines. Table 6 Truth Table
A binary decoder will have n inputs and 2n outputs. EN B1 B0 Y3 Y2 Y1 Y0
EN 1 X X 1 1 1 1
0 0 0 1 1 1 0
2n
Outputs 0 0 1 1 1 0 1
n n × 2n
Inputs Decoder 0 1 0 1 0 1 1
0 1 1 0 1 1 1
The block diagram shown here is 2 × 4 decoder with Designing High Order Decoders from Lower
active low output and active low enable input. Order Decoders
The logic diagram is similar to the previous 2 × 4 decoder,
Decoder with enable input can be connected together to
except, all AND gates are replaced by NAND gates and EN
form larger decoder circuit.
will have inverter, EN is connected to all NAND inputs, as
The following configuration shows 3 × 8 decoder with
EN is active low input for this circuit.
2 × 4 decoders.
The decoder is enabled when EN is equal to 0.
As shown in the truth table, only one output can be equal B2
to 0 at any given time, all other outputs are equal to 1. The EN Y0
output whose value is equal to 0 represents the minterm B1 2×4 Y1
selected by inputs, enable. B0 Decoder Y2
Y3
Consider a 3–8 line decoder
Table 7 Truth Table Y4

EN
Inputs Outputs B1 2×4 Y5
A B C D0 D1 D2 D3 D4 D5 D6 D7 B0 Decoder Y6
Y7
0 0 0 1 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 0 0 0
When B2 = 0, top decoder is enabled and other is disa-
0 1 0 0 0 1 0 0 0 0 0
0 1 1 0 0 0 1 0 0 0 0 bled, for 000–011 inputs, outputs are Y0–Y3, respectively,
1 0 0 0 0 0 0 1 0 0 0 and other outputs are 0.
1 0 1 0 0 0 0 0 1 0 0 For B2 = 1, the enable conditions are reversed.
1 1 0 0 0 0 0 0 0 1 0 The bottom decoder outputs generates minterms 100–
1 1 1 0 0 0 0 0 0 0 1
111, while the outputs of top decoder are all 0’s. 5 × 32
A 3–8 decoder has 3 input lines and 8 output lines, based decoder with 3 × 8 decoders, 2 × 4 decoders
on the combination of inputs applied for the 3 inputs, one of
the 8 output lines will be made logic 1 as shown in the truth EN Y0
table. So, each output will have only one minterm. B2 3×8
B1 Dec
B0 Y7
A
B
C
D 7 = ABC EN Y8
EN B2 3×8
B1 Dec
B4 B0 Y 15
D6 = ABC 2×4
B3 Decoder
EN Y 16
B2 3×8
D5 = ABC
B1 Dec
B0 Y 23
D4 = ABC
EN Y 24
B2 3×8
B1 Dec
D 3 = ABC B0 Y 31
5 × 32 decoder will have 5 inputs B4 B3 B2 B1 B0. 3 × 8 decoder

will have 8 outputs, so 5 × 32 requires four 3 × 8 decoders, and
D2 = ABC
we need one of the 2 × 4 decoders to select one 3 × 8 decoders
and the connections are as shown in the circuit above.
D1 = ABC
Combinational Logic Implementation
An n × 2n decoder provides 2n minterms of n input variables.
Since any Boolean function can be expressed in sum-of-
D0 = ABC
minterms form, a decoder that generates the minterms of
the function, together with an external OR gate that forms (A) PQ + PR (B) P + QR
their logical sum, provides a hardware implementation of
the function. (C) P (Q + R) (D) Q( P + R)
Similarly, any function with n inputs and m outputs can
be implemented with n × 2n decoders and m OR gates. 0
Example 3: Implement full adder circuit by using 2 × 4 R B2 1
decoder. 2
Sum = S (1, 2, 4, 7), Carry = S (3, 5, 6, 7) Q B1
3×8 3 F (P, Q, R)
Decoder 4
0 5
A B2 1 Sum P 6
B0
2 7
3×8 3
B B1
Decoder 4
5 Solution: (C)
C B0 6 Carry The outputs of decoder are in normal form. 0, 2, 3, 4, 6
7 outputs are connected to NOR gate to form F(P, Q, R)
So F = Y0 + Y2 + Y3 + Y4 + Y6
Figure 14 Implementation of full adder circuit with decoder
= Y0 ⋅ Y2 ⋅ Y3 ⋅ Y4 ⋅Y6
The 3 × 8 decoder generates the 8 minterms for A, B, and
C. The OR gate for output sum forms the logical sum of Y0, Y1,…, Y7 indicate minterms, whereas Y0 , Y1 , , Y7 are
minterms 1, 2, 4 and 7. The OR gate for output carry forms maxterms.
the logical sum of minterms 3, 5, 6 and 7. So F = p (0, 2, 3, 4, 6)
Here, from the decoder circuit MSB is R, LSB is P.
Example 4: The minimized SOP form of output F(x, y, z) is
By using K-map
(A) x′ y + z′ (B) x′ y′ + z′
(C) x′ y′ + z′ (D) x′ + y′ z
QP
R 00 01 11 10
0 0 0 0
0
x B2 1 1 0 0
2
3×8 3 F F ( P , Q , R) = P ( R + Q )
y B1
Decoder 4
5
z B0 6 Encoders
7 It is a digital circuit that performs the inverse operation of
a decoder.
An encoder has 2n (or fewer) input lines and n output
Solution: (C) lines.
The outputs of decoder are in active low state. So, we can It is also known as an octal to binary converter.
express outputs as Y7 , Y6 Y0 Consider an 8–3 line encoder:
Outputs 0, 1, 3, 5, 7 are connected to NAND gate to form
function F(x, y, z) Table 8 Truth Table
So F = Y0 ⋅ Y1 ⋅ Y3 ⋅Y5 ⋅Y7 Inputs Outputs
=Y0 + Y1 + Y3 + Y5 + Y7 D0 D1 D2 D3 D4 D5 D6 D7 A B C
=S(0, 1, 3, 5, 7) 1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 1
By using K-maps
yz 0 0 1 0 0 0 0 0 0 1 0
x 00 01 11 10
0 0 0 1 0 0 1 0 0 1 1
0 1 1 1
0 0 0 0 1 0 0 1 1 0 0
1 1 1
0 0 0 0 0 1 0 0 1 0 1
F = z + x′y′ 0 0 0 0 0 0 1 0 1 1 0
Example 5. The minimal POS form of output function f(P, 0 0 0 0 0 0 0 1 1 1 1
Q, R) is
Octal inputs The MUX has several data input lines and a single output
line. It also has data select inputs that permits digital data
D1 D2 D3 D4 D5 D6 D7
on any one of the inputs to be switched to the output line.
Binary outputs Depending upon the binary code applied at the selection
C = D1 + D3 + D5 + D 7 inputs, one (out of 2n) input will be gated to single output.
It is one of the most widely used standard logic circuits in
digital design. The applications of multiplexer include data
B = D2 + D 3 + D6 + D 7 selection, data routing, operation sequencing, parallel to
serial conversion, and logic function generation.
A = D4 + D5 + D6 + D 7 2n inputs will be controlled by n selection lines and mul-
tiplexer will have 1 output, we denote it as 2n × 1 multi-
plexer (data selector).
Figure 15 Logic diagram
In other words, a multiplexer selects 1 out of n input data
sources and transmits the selected data to a single output
Priority Encoder channel, this is called as multiplexing.
A priority encoder is an encoder circuit that includes the
priority function. Basic 2 × 1 Multiplexer
When two or more inputs are present, the input with The figure shows 2 × 1 multiplexer block diagram; it will
higher priority will be considered. have 2 inputsI0 and I1, one selection line S, and one output
Consider the 4 × 2 priority encoder. Y. The function table is as shown here.
I0 B1 EN S Y
I1 4×2 B0 0 x 0
I2 Encoder
I3 V 1 0 I0
1 1 I1
I3 I2 I1 I0 B1 B0 V
1 X X X 1 1 1
0 1 X X 1 0 1
EN
0 0 1 X 0 1 1 I0 Y
0 0 0 1 0 0 1 2×1
0 0 0 0 X X 0 MUX
I1
I3-I0 are inputs and B1 B0 are binary output bits, valid (V) S
output is set to 1, when at least one input is present at input
(I3 - I0).
When there is no input present, (I3 - I0 = 0000) then V = 0,
for this combination the output B1B0 will not be considered. The output equation of 2 × 1 multiplexer is
The higher the subscript number, the higher the priority Y = EN ( I 0 S + I1S ).
of the input. Input I3 has the highest priority, I2 has the next When enable is 1, the multiplexer will work in normal
priority level. Input I0 has lowest priority level. The Boolean mode, else the multiplexer will be disabled.
expressions for output B1 B0 are Sometimes enable input will be active low enable EN ,
then Y = EN ( I 0 S + I1S ).
B1 = I 3 + I 3 I 2
= I3 + I2 The 4 × 1 Multiplexer
B0 = I 3 + I 3 I 2 I1
D0
= I 3 + I 2 I1 D1 Output
4×1
V = I3 + I2 + I1 + I0 D2 MUX y
D3
Data input’s
Multiplexer
A multiplexer (MUX) is a device that allows digital infor- S1 S0
mation from several sources to be converted on to a single
Selected
line for transmission over that line to a common destination. lines
If a binary zero S1 = 0 and S0 = 0 as applied to the data select Solution: Y = ( I 0 S + I1S ) = A. It Implements NOT gate.
line the data input D0 appear on the data output line and so on.
S1 S0 y Example 7: What should be the connections to implement
0 0 D0
NAND gate by using 2 × 1 MUX?
0 1 D1 Solution: Y = AB = A + B = A + AB = 1 ⋅ A + B ⋅ A
1 0 D2
By considering I0 = 1, I1 = B, S = A, we can implement
1 1 D3
NAND gate, or by interchanging A and B also we can get
the same answer.
y = S1 S0 D0 + S1S0 D1 + S1S0 D2 + S1S0 D3
S0
1 I0 Y
S1 0 I1
4×1
0 I2 MUX
D0
1 I3
S1 S2
D1
A B
y
For the above 4 × 1 multiplexer Y = AB + AB = X-NOR gate,
D2 similarly to implement 2 input gates by using 4 × 1 multiplexer,
the inputs I0, I1, I2, I3 should be same as the terms in the truth
table of that gate.
D3
Logic Function Implementation
Figure 16 Logic diagram by Using Multiplexer
Let us consider a full subtractor circuit (borrow) to be
For 8 × 1 multiplexer with 8 inputs from I0–I7 based on
implemented by using multiplexer.
selection inputs S2 S1 S0, the equation for output
Full subtractor borrow (B) is a function of 3 inputs X, Y,
Y = I 0 S2 S1S0 + I1 S2 S1S0 + I 2 S2 S1 S0 + I 3 S2 S1S0 Z. The truth table is
+ I 4 S2 S1S0 + I 5 S2 S1S0 + I 6 S2 S1 S0 + I 7 S2 S1S0 X Y Z B 4 × 1 MUX 2 × 1 MUX
From multiplexer equation, we can observe, each input is 0 0 0 0
B=Z
associated with its minterm (in terms of selection inputs). 0 0 1 1
B=Y+Z
0 1 0 1
Basic Gates by Using MUX B=1
0 1 1 1
B I0 1 0 0 0
Y B=0
1 0 1 0
2×1 B = YZ
MUX 1 1 0 0
B I1 B=Z
1 1 1 1
S
To implement borrow by using 8 × 1 multiplexer, connect
the three variables X, Y, Z directly to selection lines of the
A multiplexer, and connect the corresponding values of B to
inputs, i.e., for I0 = 0, I1 = 1, I2 = 1, etc. as per above truth table.
Figure 17 X-OR gate by using 2 × 1 MUX
To implement borrow by using 4 × 1 multiplexer, con-
Y = AB + AB = X-OR gate, we can interchange inputs A nect any two variables to selection lines (in this case X, Y)
and B also, and write output (B) in terms of other variable, for XY = 00,
By interchanging inputs I0 and I1, Y = A B + AB, X-NOR output B is same as Z, so connect I0 = Z, similarly 1, 0, Z for
gate. remaining inputs.
Similarly, we can build all basic gates by using 2 × 1 To implement the function by using 2 × 1 multiplexer,
multiplexer. connect 1 variable as selection line (in this case consider X)
Example 6: If I0 = 1, I1 = 0, S = A, then Y is and write output (B) in terms of other variables, for X = 0,
output B is varies as B = Y + Z, so connect I0 = Y + Z. For X In a similar fashion, to design 4 × 1 MUX, we require 3, 2 × 1

= 1, output B varies as B = YZ, connect I1 = YZ. multiplexers, and to design 8 × 1 multiplexer, we require 7,
N–variable function can be implemented by using 2N-1 × 2 × 1 multiplexers.
1 multiplexer without any extra hardware.
Demultiplexer
Implementation of Higher Order The demultiplexer [DeMUX] basically serves opposite of
Multiplexer by Using Lower the multiplexing function. It takes data from one line and
Order Multiplexers distributes them to a given number of output lines.
By using lower order multiplexers, we can implement higher The other name for demultiplexer is data distributor, as it
order multiplexers, for example by using 4 × 1 multiplexer, receives information on a single line and distributes it to a
we can implement 8 × 1 MUX or 16 × 1 MUX or other possible 2n output lines, where n is the number of selection
higher order multiplexers. lines, and value of n selects the line.
Let us consider implementation of 16 × 1 MUX by using D0
4 × 1 MUX. 16 × 1 MUX will have inputs I0–I15 and selec-
D1
tion lines S0–S3, whereas 4 × 1 MUX will have only 4 input E
1×4
lines, and 2 selection lines, so we require four 4 × 1 MUX DEMUX D2
input
to consider all inputs I0–I15, and again to select one of the D3
four outputs of these four multiplexers one more 4 × 1 mul-
tiplexer is needed (for which we will connect higher order
selection lines S2 and S3). So, total of 5, 4 × 1 multiplexers
S1 S0
are required to implement 16 × 1 MUX.
Multiplexer S1 S0 D3 D2 D1 D0
I0 S1 D 0 0 0 0 0 E
0 1 0 0 E 0
1 0 0 E 0 0
I3 S4
C1 C2 1 1 E 0 0 0
When S1S0 = 10; D2 will be same as input E, and other

S0 S1
outputs will be maintained at zero (0).
Multiplexer E
D 0 = ES 1S 0
I4 S1 D
D 1 = ES 1S 0
Multiplexer
I7 S4
C1 C2 S1 D
D 2 = ES 1S 0
S0 S1
Multiplexer S4 D 3 = ES 1S 0
I8 S1 D C1 C2
S1 S0
S2 S3 Figure 17 Logic diagram
I 11 S4
C1 C2
Solved Examples
S0 S1
Example 1: The multiplexer shown in the figure is a 4 : 1
Multiplexer multiplexer. The output z is
I 12 S1 D
I3
C
I2 MUX
I 15 S4 Z
I1 4×1
C1 C2 C
I0
S1 S0
S0 S1
Figure 18 Realization of 16 x 1 multiplexer by using 4 x 1 multiplexers A B

Solution: = A + CB
A1 B0 Z
= A + C + B = ABC
0 0 C \ NAND Gate
0 1 C
Example 4: In the TTL circuit in figure, S2–S0 are select
1 0 C
lines and x7–x0 are input lines. S0 and X0 are LSBs. The
1 1 C output Y is
1
∴ Z = A BC + ABC + ABC + AB C
0
= B( AC + AC ) + B( AC + AC ) X0 X1 X2 X3 X4 X5 X6 X7
0 S2
= ( AC + AC )( B + B)( x + x = 1) A 8 : 1 MUX y
∴ = AC + AC = A ⊕ C B S1

C S0
Example 2: The logic circuit shown in figure implements
D0
Solution: S2 = A, S1 = B, S0 = C
C I0 D1
D2 S2(A) S1(B) S0(C) Y
I1 3 to 8 D3
B 0 0 0 1
Decoder
D4
0 0 1 0
A I2 D5
0 1 0 0
D6
D7 0 1 1 1
1 0 0 0
D 1 0 1 1
1 1 0 1
1 1 1 0
Solution: z = D( A B C + A BC + ABC + AB C + ABC )
= D( A B(C + C ) + BC ( A + A) + AB C ) Y = A B C + ABC + ABC + ABC

× D( B A + B C + BC ) = C ( A B + AB ) + C ( AB + AB )
= D( B Θ C + AB) Y = C ( A ⊕ B) + C ( A ⊕ B) = A ⊕ B C

Example 3. The network shown in figure implements Example 5: The logic realized by the adjoining circuit is
A 0
A 1 MUX
f2 1 MUX
F
1 0 2
Select
S0 A 3 lines
S1 S0
MSB
B 1 MUX
B C
f1
0 0 Solution: F = B CA + BCA + BC A + BC A
S0 × C ( BA + B A) + C ( BA + B A)
× AB + AB(C + C ) = A ⊕ B
c
Example 6: Consider the following multiplexer, where I0,
Solution: f1 = C 0 + CB = CB, f1 = CB I1, I2, I3 are four date input lines selected by two address
F2 = f1 + f1 A = A ⋅ CB + CB line combinations AIA0 = 00, 01, 10, 11, respectively and f
is the output of the multiplexer. EN is the enable input, the Solution: A1 = y ⋅ A0 = z , EN = z

function f (x, y, z) implemented by the below circuit is
A1 A0 S I
x I0 0 0 x
(yz )
I1
0 1 (y z) x
y I2
1 0 (y z ) y
4×1 F (x, y, z)
I3
MUX
A1 1 1 (yz) y
z A0
EN
f ( x, y, z ) = S.I = ( xy + 0 + yz ) ⋅ EN
= xy ⋅ z
Exercises
Practice Problems 1 (A) are high; and G, G2 are low
Directions for questions 1 to 21: Select the correct alterna- (B) are high; and G is low G2 is high
tive from the given choices. (C) are high; and G, G2 are high
(D) are high; and G is high G2 is low
1. The binary number 110011 is to be converted to gray
code. The number of gates and type required are 5. The MUX shown in figure is 4 × 1 multiplexer the
(A) 6, AND (B) 6, X-NOR output z is
(C) 6, X-OR (D) 5, X-OR
2. The number of 4-to 16-line decoder required to make
an 8- to 256-line decoder is C I0
(A) 16 (B) 17 I1 MUX
(C) 32 (D) 64 Z
I2 4×1
3. f (x2, x1, x0) = ?
I3
S1 S0
D0
x0 I0 D1
D2 +5 V A B
x1 I1 3 to 8 D3 f
Decoder
D4 (A) ABC
x2 I2 D5 (B) A⊕B⊕C
D6 (C) AQBQC
D7
(D) A+B+C
(A) p(1, 2, 4, 5, 7) (B) Σ(1, 2, 4, 5, 7) 6. If a 4 to 1 MUX (shown below) realizes a three vari-
(C) Σ(0, 3, 6) (D) p(0, 2, 3, 6) able function f ( x, y, z ) = xy + xz then which of the
following is correct?
4. A 3-to-8 decoder is shown below
8
I0
3 7
6 I1 4 to 1
F(x, y, z)
5 Output I2 MUX
Input 2
4
I3
3 S1 S0
1
2
(MSB)
G2 G 1
Y Z
Enable Signal (A) I0 = X, I1 = 0, I2 = X, I3 = X

decoder decoder (B) I0 = 0, I1 = 1, I2 = Y1, I3 = X
(C) I0 = X, I1 = 1, I2 = 0, I3 = X
All the output lines of the chip will be high except pin
8, when all the inputs 1, 2, and 3 (D) I0 = X, I1 = 0, I2 = X, I3 = Z
7. The circuit shown in the figure is same as (C) AB + BC + AC

(D) AB + BC + AC
I0 4:1 11. Find the function implemented.
I1
y
I2 P I3
P I2
I3
Q 4×1 Z
S1 S0
a P I1
b I0
P
c S1 S2
Q
(A) two input NAND gate with a and c inputs
(B) two input NOR gate with a and c inputs R S
(C) two input X-OR gates with a and b inputs
(D) two input X-NOR gate with b and c inputs (A) PQ + PS + Q RS
(B) PQ + PQR + PQS
8. If the input x3, x2, x1, x0 to the ROM in the figure are
8421 BCD numbers, then the outputs y3, y2, y1, y0 are (C) PQ R + PQR + PQRS + Q RS
x3 x2 x1 x0 (D) PQR + PQRS + PQRS + Q R S
12. Which function is represented by the given circuit?
A
B x
ROM
C y
BCD to Decimal decoder
(A) Full adder (B) Full subtractor
(C) Comparator (D) Parity generator
D0 D1 D8 D9
13. Which of the following represents octal to binary
y3 encoder?
y2 (A) D0 D1 D2 D3 D4 D5 D6 D7
y1
y0 A2
A1
(A) gray code numbers (B) 2421 BCD
(C) Excess – 3 code numbers (D) 84–2–1 A0
9. A 4-bit parallel full adder without input carry requires
(A) 8 HA, 4 OR gates (B) 8 HA, 3 OR gates D0 D1 D2 D3 D4 D5 D6 D7
(B)
(C) 7 HA, 4 OR gates (D) 7 HA, 3 OR gates
10. In the circuit find X.
A2
0 I0 0 I0 A1
1 I1 1 I1
4×1 y 4×1 y x A0
1 I2 1 I2
0 I3 0 I3 (C) D0 D1 D2 D3 D4 D5 D6 D7
S1 S0 S1 S0
A2
A B C
A1
(A) ABC + ABC + ABC + ABC
A0
(B) ABC + ABC + ABC + ABC
(D) D0 D1 D2 D3 D4 D5 D6 D7 (A) X = A′BC′ + B′C′, y = A + B

(B) X = A′C′ + B′C′, y = 1
A2
(C)=
X A=
, y 0
A1 (D)= X A= , y 1
18. A relay is to operate with conditions that it should be on
A0 when the input combinations are 0000, 0010, 0101, and
0111. The states 1000, 1001, 1010 don’t occur. For
14. For a MUX to function as a full adder what should be rest of the status, relay should be off. The minimized
the input provided to the I0, I1, I2, I3 if the A and B are the Boolean expression notifying the relationship is
select lines? (A) BC + ACD
(B) BD + ABD
I0
(C) BD + AC
I1
4×1 F (D) AB + CD
I2
19. If a function has been implemented using MUX as
I3
S1 S0 shown, implement the same function with a and c as
the select lines
A B
a
(A) I =
0 I=1 Cin ; I=
2 I=
3 Cin 0
4×1 y
1
(B) I =
0 I=1 Cin ; I=
2 I=
3 Cin a
(C) I=
0 I=
3 Cin ; I=
1 I=
2 Cin
b c
(D) I=0 I=
3 Cin ; I=
1 I=
2 Cin
15. The given circuit act as (A) b
(B) 0
b 1
4×1 4×1
c 1 0 b
MUX y1 0 b
c 0
S0
a 1
y0 a c a c
MUX
a 0
S0 S0
c 1 (C) (D)
MUX y2 b 1
b b 0 b 1
4×1
4×1 1
1
0 1
(A) Full adder (B) Half adder
(C) Full subtractor (D) Half subtractor a c a c
16. For a 4 × 16 decoder circuit, the outputs of decoder
(y0, y1, y4 . y5 . y10 . y11 . y14 . y15) are connected to 8 input 20. The circuit is used to convert one code to another.
NOR gate, the expression of NOR gate output is Identify it.
(A) A ⊕ D (B) A ⊙ D
A3 B3
(C) A ⊙ C (D) A ⊕ C
17. The function implemented by decoder is B2
A2
D0
A D1 A1 B1
X
D2
3 to 8 D3 A0 B0
B
Decoder
D4
C D5 Y
(A) Binary to gray
D6 (B) Gray to binary
D7 (C) Gray to XS–3
(D) Gray to 8421
21. The Boolean function realised by logic circuit is (A) F = Σm(0, 1, 3, 5, 9, 10, 14)
(B) F = Σm(2, 3, 5, 7, 8, 12, 13)
C I0
(C) F = Σm(1, 2, 4, 5, 11, 14, 15)
D I1 4:1
MUX Y F(A, B, C, D) (D) F = Σm(2, 3, 5, 7, 8, 9, 12)
I2
I3
S1 S0
A B
Practice Problems 2 C I0
Directions for questions 1 to 21: Select the correct alterna- C I1
tive from the given choices. 4:1 F
C I2 MUX
1. For a binary half subtractor having two input A and B,
the correct set of logical expression for the outputs D C I3
S0 S1
= (A minus B) and X (borrow) are
B
(A) D = AB + AB, X = AB A
(B) D = AB + AB +, AB, X = AB
(A) AB + BC + CA + BC (B) A ⊕ B ⊕ C
(C) D = AB + AB, X = AB (C) A ⊕ B (D) B ⊕ C
(D) D = AB + A B, X = AB 5. Full subtractor can be implemented by using
2. The function ‘F’ implemented by the multiplexer chip (A) 3-to-8 line decoder only
shown in the figure is (B) 3-to-8 line decoder and one OR gate
0 1 0 1 (C) 3-to-8 line decoder and two OR gates
(D) None
I0 I1 I2 I3 6. What are the difference and borrow equations for the
A S1 above circuit?
Y F (A) D = x Q y Q z, B = x′y + yz + zx′
B S0
(B) D = X ⊕ y ⊕ z, B = xy + yz + zx
(C) D = x ⊕ y ⊕ z, B = x′y + yz + zx′
(A) A (B) B (D) A and C both
(C) AB (D) AB + AB 7. Combinational circuits are one in which output depends
_________, whereas sequential circuit’s output depends
3 The following multiplexer circuit is equal to _________
(A) only on present input, only on past input
0 4:1 (B) only on present input, only on past and future input
MUX
1 (C) only on present input, only on present input and
y past output
2
(D) on present input, on past and present output
3
S1 S0 8. The sum output of the half adder is given by (assume A
a
b
and B as inputs)
c (A) S = AB( A + B) (B) S = ( A + B) AB
(C) S = ( A + B)( AB) (D) S = ( A + B )( AB )
(A) implementation of sum equation of full adder
(B) implementation of carry equation of full adder 9. MUX implements which of the following logic?
(C) implementation of borrow equation of full (A) NAND–XOR (B) AND–OR
substractor (C) OR–AND (D) XOR–NOT
(D) all of the above 10. A DeMUX can be used as a
4 The output ‘F’ of the multiplexer circuit shown in the (A) Comparator (B) Encoder
figure will be (C) Decoder (D) Adder
11. If we have inputs as A, B and C and output as S and D. (C) a 0 (D) a 0

We are given that S = A ⊕ B ⊕ C. D = BC + AB + AC .
Which of the circuit is represented by it?
Y F A F A
1 1
X
A B A B A B A B s c s c
C D C D C D C
S S S S 16. Identify the circuit.
Y1
D A
B Y2
Output
(A) 4-bit adder giving X + Y
(B) 4-bit subtractor giving X - Y
(C) 4-bit subtractor giving Y - X Y3
(D) 4-bit adder giving X + Y + S
12. The Boolean function f implemented in the figure using (A) Half adder
two input multiplexers is (B) Full adder
(C) 1-bit magnitude comparator
D 0 1 0 (D) Parity generator
f
17. In order to implement n variable function (without any
C 1 B 1 extra hardware) the minimum order of MUX is
S0 S0
(A) 2n × 1 (B) 2n × 1
(C) (2 - 1) × 1
n
(D) (2n - 1) × 1
A
18. A full adder circuit can be changed to full subtractor by
(A) AC + AD + DC + ABD + ABC adding a
(B) A + AC + AD + DC (A) NOR gate (B) NAND gate
(C) B + AC + AD + DC (C) Inverter (D) AND gate
(D) AC + AD + A + B 19. The half adder when implemented in terms of NAND
13. The carry generate and carry propagate function of the logic is expressed as
look ahead carry adder is (A) A ⊕ B (B) A⋅ AB ⋅ B ⋅ AB
(A) CG = A + B, CP = A ⊕ B
(B) CG = A ⊕ B, CP = A + B (C) A ⋅ AB ⋅ B ⋅ AB (D) A ⋅ ABB⋅ AB
(C) CG = AB, CP = A ⊕ B
20. For a DeMUX to act as a decoder, what is the required
(D) CG = AB, CP = A + B
condition?
14. If we have a comparator and if E represents (A) Input should be left unconnected and select lines
the condition for equality i.e., (An ⊕ Bn), if An behave as a input to decoder
and Bn are to be compared then the expression (B) Input should be always 0 and select line behave as
A3 B3 + E3 A2 B2 + E3 E2 A1 B1 + E3 E2 E1 A. B. r e p r e s e n t s inputs to decoder
which of the condition for a 4-bit number? (C) Both are same
(A) A > B (B) B > A (D) Input should become enable and select lines
(C) A = B (D) None of these behave as inputs to decoder
15. When full adder is used to function as a 1-bit incremen- 21. For a full subtractor, which of the combination will give
tor, which of the circuit configurations must be used? the difference?
(A) a 0 (B) a 0
(A) ( A ⊕ B)( A ⊕ B)bi ⋅ bi ( A ⊕ B)bi
F A
0
F A (B) B ⋅ AB ⋅ bi ( A ⊕ B)
0
(C) A + B + bi + A ⊕ B
c s c s (D) None of these

1. A 4-bit carry look ahead adder, which adds two 4-bit 16 value of the number. Which one of the following
numbers, is designed using AND, OR, NOT, NAND, functions is correct?[2006]
NOR gates only. Assuming that all the inputs are (A) g0 (h3h2h1h0) = Σ(1, 2, 3, 6, 10, 13, 14, 15)
available in both complemented and uncomplemented (B) g1 (h3h2h1h0) = Σ(4, 9, 10, 11, 12, 13, 14, 15)
forms and the delay of each gate is one time unit, what (C) g2 (h3h2h1h0) = Σ(2, 4, 5, 6, 7, 12, 13, 15)
is the overall propagation delay of the adder? Assume (D) g3 (h3h2h1h0) = Σ(0, 1, 6, 7, 10, 11, 12, 13)
that the carry network has been implemented using
6. How many 3-to-8 line decoders with an enable input
two-level AND–OR logic. [2004]
are needed to construct a 6-to-64 line decoder without
(A) 4 time units (B) 6 time units
using any other logic gates? [2007]
(C) 10 time units (D) 12 time units
(A) 7 (B) 8
(C) 9 (D) 10
2. x
0 MUX 7. Suppose only one multiplexer and one inverter are
1 allowed to be used to implement any Boolean function
y of n variables. What is the minimum size of the multi-
z 0 MUX plexer needed? [2007]
f
1 (A) 2n line to 1 line (B) 2n+1 line to 1 line
x
(C) 2n–1 line to 1 line (D) 2n–2 line to 1 line
y
8. In a look-ahead carry generator, the carry generate
Consider the circuit above. Which one of the follow- function Gi and the carry propagate function Pi for
ing options correctly represents f (x, y, z)? [2006] inputs Ai and Bi are given by:
(A) xz + xy + yz (B) xz + xy + yz Pi = Ai ⊕ Bi and Gi = AiBi
(C) xz + xy + yz (D) xz + xy + yz The expressions for the sum bit Si and the carry bit
Ci+1 of the look-ahead carry adder are given by:
3. Given two 3-bit numbers a2a1a0 and b2b1b0 and c, the
carry in, the function that represents the carry generate Si = Pi ⊕ Ci and Ci+1 = Gi + PiCi, where C0 is the input
function when these two numbers are added is [2006] carry.
(A) a2b2 + a2a1b1 + a2a1a0b0 + a2a0b1b0 + a1b2b1 + a1a0b2b0 Consider a two-level logic implementation of the
+ a0b2b1b0 look-ahead carry generator. Assume that all Pi and
Gi are available for the carry generator circuit and
(B) a2b2 + a2b1b0 + a2a1b1b0 + a1a0b2b1 + a1a0b2 + a1a0b2b0
that the AND and OR gates can have any number
+ a2a0b1b0
of inputs. The number of AND gates and OR gates
(C) a2 + b2 + (a2 ⊕ b2) (a1 + b1 + (a1 ⊕ b1)(a0 + b0))
needed to implement the look-ahead carry generator
(D) a2 b2 + a2 a1b1 + a2 a1a0 b0 + a2 a0 b1b0 for a 4-bit adder with S3, S2, S1, S0 and C4 as its outputs
are respectively: [2007]
+ a1 b2 b1 + a1a0 b2 b0 + a0 b2 b1b0 (A) 6, 3 (B) 10, 4
(C) 6, 4 (D) 10, 5
4. We consider the addition of two 2’s complement num-
9. The Boolean expression for the output f of the multi-
bers bn-1bn-2 … b0 and an-1an-2 … a0. A binary adder
plexer shown below is
for adding unsigned binary numbers is used to add
the two numbers. The sum is denoted by cn-1cn-2 … c0
R 0
and the carry-out by cout. Which one of the following R 1
options correctly identifies the overflow condition? R 2 f
[2006] R 3
S1 S0
(A) cout ( an −1 ⊕ bn −1 )
(B) an −1 bn −1 cn −1 + an −1 bn −1 cn −1
(C) cout ⊕ cn-1 P Q
(D) an-1 ⊕ bn-1 ⊕ cn-1 (A) P ⊕ Q ⊕ R
5. Consider numbers represented in 4-bit gray code. Let (B) P ⊕ Q ⊕ R
h3h2h1h0 be the gray code representation of a number (C) P + Q + R
n and let g3g2g1g0 be the gray code of (n + 1) modulo (D) P + Q + R
10. The amount of ROM needed to implement a 4-bit if (x is 1) y = a;

multiplier is [2012] else y = b;
(A) 64 bits }
(B) 128 bits
Which one of the following digital logic blocks is the
(C) 1K bits
most suitable for implementing this function?
(D) 2K bits
(A) Full adder (B) Priority encoder
11. In the following truth table, V = 1 if and only if the input (C) Multiplexer (D) Flip–flop
is valid.
14. Let ⊕ denote the Exclusive OR (X-OR) operation.
Let ‘1’ and ‘0’ denote the binary constants. Consider
Inputs Outputs
the following Boolean expression for F over two vari-
D0 D1 D2 D3 X0 X1 V ables P and Q:
0 0 0 0 x x 0 F(P, Q) = ((1 ⊕ P) ⊕ (P ⊕ Q)) ⊕ ((P ⊕ Q)
1 0 0 0 0 0 1 ⊕ (Q ⊕ 0)) [2014]
x 1 0 0 0 1 1
The equivalent expression for F is
x x 1 0 1 0 1 (A) P + Q (B) P + Q
x x x 1 1 1 1 (C) P ⊕ Q (D) P ⊕ Q
15. A half adder is implemented with XOR and AND

What function does the truth table represent? [2013] gates. A full adder is implemented with two half adders
(A) Priority encoder and one OR gate. The propagation delay of an XOR
(B) Decoder gate is twice that of an AND/OR gate. The propaga-
(C) Multiplexer tion delay of an AND/OR gate is 1.2 microseconds.
A 4-bit ripple-carry binary adder is implemented by
(D) Demultiplexer using four full adders. The total propagation time of
12. Consider the 4-to-1 multiplexer with two select lines this 4-bit binary adder in microseconds is _____
S1 and S0 given below. [2015]
16. Consider the two cascaded 2-to-1 multiplexers as

0 0
shown in the figure.
1 1 4 to 1
F
Multiplexer
R 2
R 3
S1 S0
minimal sum of products form of the output x is
P Q The minimal sum of products form of the output X is
[2016]
The minimal sum-of-products form of the Boolean
expression for the output F of the multiplexer is (A) P Q + PQR (B) P Q + QR
[2014] (C) PQ + P Q R (D) P Q + PQR
(A) PQ + QR + PQR 17. When two 8-bit numbers A7… A0 and B7… B0 in 2’s
(B) P Q + PQR + PQR + PQR complement representation (with A0 and B0 as the
least significant bits) are added using a ripple-carry
(C) PQR + PQR + QR + PQR
adder, the sum bits obtained are S7…S0 and the carry
(D) PQR PQR + PQR + QR + PQR bits are C7…C0. An overflow is said to have occurred
if[2017]
13. Consider the following combinational function block
(A) the carry bit C7 is 1
involving four Boolean variables x, y, a, b, where x, a,
(B) all the carry bits (C7,…,C0) are 1
b are inputs and y is the output. [2014]
f(x, y, a, b) (C) ( A7 ⋅ B7 ⋅ S7 + A7 ⋅ B7 ⋅ S7 ) is 1
{ (D) ( A0 ⋅ B0 ⋅ S0 + A0 ⋅ B0 ⋅ S0 ) is 1
Answer Keys
Exercises
Practice Problems 1
1. D 2. B 3. B 4. D 5. D 6. A 7. C 8. B 9. D 10. A
11. A 12. B 13. B 14. C 15. C 16. D 17. D 18. B 19. C 20. A
21. D
Practice Problems 2
1. C 2. B 3. A 4. D 5. C 6. C 7. C 8. B 9. B 10. C
11. B 12. C 13. C 14. A 15. C 16. C 17. B 18. C 19. C 20. D
21. A

1. B 2. A 3. A 4. B 5. C 6. C 7. C 8. B 9. B 10. D
11. A 12. A 13. C 14. D 15. 19.2 16. D 17. C
Chapter 4
Sequential Circuits
LEARNING OBJECTIVES
 Sequential circuit  Asynchronous counter design

 Basic storage elements  Synchronous counter design
 Latches (SR Latch, D Latch, JK Latch)  Registers
 Flip-flops (JK flip-flop, T flip-flop, D flip-flop)  Various types of registers
 Counters  Application of shift register
seQuentiaL circuits Sequential circuits are of two types:

In sequential circuits the output depends on the input as well as on 1. Clocked or synchronous
the previous history of output, i.e., they contain memory elements. 2. Unclocked or asynchronous
Outputs In synchronous sequential circuits the logic circuits action is allowed to
Inputs X
Combinational Z = F(X, Y ) occur in synchronization with the input clock pulse from a system clock.
States Y circuit In asynchronous sequential circuits the logic sequential action
is allowed to occur at any time.
Memory Basic Storage Elements

Clk pulses elements
Latches and flip-flops
Clk pulses A storage element in digital circuit can maintain a binary state
Figure 1 Block diagram of sequential circuit indefinitely until directed by an input signal to switch states.
Storage elements that operate with signal levels (i.e., level trigger-
Table 1 Comparison between combinational and sequential circuits ing of signal inputs) are referred to as latches. Those controlled by
Combinational Circuits Sequential Circuits a clock transition (i.e., edge triggering) are flip-flops.
1. Output at any time depends Output depends on the present input Latches and filp-flops are related because latches are basic cir-
on the combine set of input as well as on the previous history of cuits from which all flip-flops are constructed. Latches are useful
applied to it simultaneously at output
for storing binary information and for the design of asynchronous
that instant of time
sequential circuits. But latches are not practical for use in synchro-
2. Contains no memory element Contains at least one memory element
nous sequential circuits, so we use flip-flops.
3. Easy to design due to absence Difficult to design
of memory
4. Totally described by the set of Its performance is totally described Flip-flops
output values by the set of subsequent values as They are also known as bistable multivibrators. This is a basic
well as set of output values
memory element to store 1-bit of information 0 or 1 and is used in
5. Faster in speed because all Slower in speed because secondary storage circuits, counters, shift register, and many other computer
inputs are primary inputs and inputs are also needed which are
applied simultaneously applied after delay
applications. It has two stable states: 1 and 0. The high state is
6. It need more hardware for Less hardware required
called set state and zero as reset.
realization It has two outputs one being the complement of the other usu-
7. Expensive in cost Cheap in cost ally designated by Q and Q.
Chapter 4 • Sequential Circuits | 1.57
Q R
Q
i/p F.F
Q
Clk Q′
S
There are different types of flip-flops S-R flip-flop, D-flip- Figure 2 Logic diagram for SR latch
flop, T-flip-flop, J-K flip–flops, etc.
S R Qn+1 ′
Qn+1
Latches
0 0 Qn Qn′ (no change)
(i) S-R Latch: The simplest latch is called S-R latch. S-R
0 1 0 1 (Reset)
means Set-Reset. It has two outputs Q and Q and two
inputs S and R, which represent set or reset signal. 1 0 1 0 (set)
1 1 0 0 (invalid)
S G1
G3 Q R
Q
G4 Q
R G2 Q′
S
Figure 3 S R Latch
Above figure shows two cross coupled gates G3 and
G4 and inverters G1 and G2. Here output of G3 is con-
nected to the input of G4 and output of G4 is applied to S R Qn+1 Qn +1
the input of G3. S = 1, R = 0 output of G1 = 0 and G2 =
0 0 1 1 (Invalid)
1. Since one of the input of G3 is 0, so its output will be
0 1 1 0 (Set)
certainly 1 and consequently both input of G4 will be 1
and the output Q = 0. 1 0 0 1 (Reset)
For S = 1, R = 0, Q = 1, Q = 0. S = 0, R = 1 the 1 1 Qn Qn′ (No change)
output will be Q = 0 and Q = 1. The first of the input
condition S = 1 and R = 0 makes Q = 1 which referred
S R latch is active low SR latch
as the set state and the second condition S = 0 and R = (iii) SR latch with control input: The working of gated
1 makes Q = 0 which is referred as reset state. SR latch is exactly the same as SR latch when the EN
For S = 0 and R = 0 output of both G1 and G2 will be pulse is present. When the EN pulse is not present (EN
one and hence there will be no change in Q and Q. pulse = 0) the gates G1 and G2 are inhibited and will not
For S = R = 1, both the outputs Q and Q will try respond to the input.
to become one, which produces invalid results and
should not be used for the above latch. S
Q
Input Output
State EN
S R Q Q
1 0 1 0 Set
Q
0 1 0 1 Reset
R
0 0 0 0 No change
1 1 ? ? Invalid Characteristic table of SR latch shows the operation
of latch in tabular form. Qt stands as the binary state
(ii) SR latch by using NAND/NOR gates: The SR latch of the latch before the application of latch pulse and
is a circuit with two cross-coupled NOR gates or two referred to as the present state. The S and R columns
cross-coupled NAND gates. Two inputs labelled S for give the possible values of the inputs and Qt+1 is the
set and R for reset. Latch will have two outputs: state of the latch after the application of a single pulse,
•• Q: output state in normal form and referred to as next stage. EN input is not included in
•• Q′: output state in complemented form. the characteristic table.
Characteristic
table for SR latch is given below: Pr
Qt S R Qt+1
0 0 0 0 S Q
0 0 1 0
SR
0 1 0 1 EN
Latch
0 1 1 X
R Q
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 X Clr
Characteristic equation of the latch is derived from the

(v) D latch (Transparent latch): One way to eliminate
K-map. the invalid condition of SR latch (when S = R = 1) is
SR
00 01 11 10
to ensure that inputs S and R are never equal to 1 at the
Qt
same time.
0 × 1
By connecting a NOT gate between S and R inputs.
1 1 × 1
i.e, complement of S will be given to R, we can form D
latch as shown in block diagram.
∴ Qt +1 = S + RQt
This equation specifies the value of the state as a func-
D S Q
tion of the present state and the inputs. D
(iv) Preset and clear inputs: For the latch/flip-flop, when the Latch
power is switched ON, the state of the circuit is uncertain. R EN Q
It can be either Q = 0 (reset) or Q = 1 (set) state.
In many applications it is desired to set or reset the
circuit, so that initial state of the circuit will be known. Figure 5 Block diagram for D latch
This is accomplished by using the asynchronous,
inputs referred to as preset (Pr) and clear (Clr), inputs. Pr
These inputs can be applied any time, and are not D
synchronized with EN input/Clr input.
Present (Pr) EN
S Q
EN Clr
Figure 6 Logic diagram for D latch

R Q
EN D Qn+1
Clear (Clr)
0 X Qn – No change (Disabled)
Figure 4 SR latch with Pr and Clr inputs 1 0 0 – Reset state
If Pr = Clr = 1, the circuits operates as of S–R latch 1 1 1 – Set state
explained previously.
If Pr = 0, Clr = 1, the output Q will become 1, which in When EN = 0, the circuit will be disabled and input D
turn changes Q = 0. will not have only effect on output, and output will be
If Pr = 1, Clr = 0 the output Q will become 1, which in same as previous state.
turn changes Q = 0. When EN = 1, D = 0, i.e., S = 0, R = 1 which makes
If Pr = Clr = 0, both Q and Q will become 1, which is output Q = 0 and Q = 1 (Reset state).
invalid case, so Pr = Clr = 0 condition must not be used. When EN = 1, D = 1, i.e., S = 1, R = 0 which makes
output Q = 1, and Q = 0 (Set state).

Pr Clr Qn+1
1 1 Q – No change (vi) JK latch: The function of JK latch is identical to
0 1 1 – Set that of SR latch except that it has no invalid state
1 0 0 – Reset as that of SR latch where S = R = 1. In this case the
0 0 X – Invalid
state of the output is changed as complement of pre-
vious state.
Preset (A) 10, 01, 10 or 01 (B) 11, 00, 10

(C) 01, 00, 10 or 01 (D) 10, 11, 10 or 01
J
G1 G3 Q Solution: (C)
Given circuit is RS latch with NOR gates.
EN By comparing with RS latch A = R, B = S, and X = Q,
Y = Q, so from truth table of RS latch
G2 G4 Q
K Q/X
S/B R/A Q /Y
0 1 0 1 Reset (Invalid)
Clr
1 1 0 0
EN J K Qt+
0 0 1 0 (Same as previous state)
1 0 0 Qt No change
0 1
1 0 1 0 Reset
1 1 0 1 Set After invalid case S = 1, R = 1, i.e., A = B = 1,
1 1 1 Qt Toggle The output= Q 0= , Q 0, i.e., X= Y= 0
0 x x No change
By applying A = 0, B = 0
Qt
The output X becomes (0 + 0) = 1and which in turn changes
JK latch by using SR latch: The uncertainty of SR flip-flop Y = ( B + X ) = (0 + 1) = 0

(when S = 1, R = 1) can be eliminated by converting it into
JK latch. A=0
X=0
The data inputs J and K, which are ANDed with Q and Q 0
respectively, to obtain S and R inputs.
S = J ⋅ Q, R=K⋅Q 0
Y=0
B=0
J S Q
(or) the output Y becomes (0 + 0) = 1 and which in turn
EN SR latch changes X = (Y + A) = (0 + 1) = 0. So, output (X, Y) cannot
be predicted after the invalid condition. So, X = 0, Y = 1 or
K R Q X = 1, Y = 0
Example 2: Refer to the NAND and NOR latches shown
Figure 7 JK latch by using SR latch in the figure the inputs (P, Q) for both the latches are first
made (1, 0) and then after a few seconds, made (0, 0). The
J K S R Qn+1 Qn+1 corresponding stable outputs (X, Y ) are
0 0 0 0 Qn Qn -No change P P
X X
0 1 0 Qn 0 1-Reset
1 0 Qn 0 1 0-Set
1 1 Qn Qn Qn Qn-Toggle Y Y
Q Q
Example 1: The following binary values were applied to A (A) NAND: first (0, 1) then (0, 1); NOR: first (1, 0) then (1, 0)
and B inputs of NOR gate latch shown in the figure, in the (B) NAND: first (0, 1) then (1, 1); NOR: First (0, 1) then
sequence indicated below. A = 1, B = 0; A = 1, B = 1; A = 0, (0, 1)
B = 0. The corresponding stable X, Y outputs will be (C) NAND: first (1, 0) then (0, 0); NOR: first (1, 0) then (1, 0)
(D) NAND: first (1, 0), then (1, 0); NOR: first (1, 0) then
A
X (1, 1)
Solution: (B)
From the truth table of SR latch and S R latch SR latch with
NOR gates:
Y
B For (P, Q) = (1, 0) = (R, S) output (=
X , Y ) (=
Q, Q ) (0, 1)
Then (P, Q) are made (0, 0), i.e., (R, S) = (0, 0), which G1m
J
results in no change at output. So, (=X , Y ) (=
Q, Q ) (0,1) Qm
SR latch with NAND gates: Q
For (P, Q) = (1, 0) = (S, R) output (X, Y) = (Q, Q ) = (0,1). Clk
Then (P, Q) are made (0, 0), i.e., (S, R) = (0, 0) which is G 2m Qm Q
K
invalid conditions for S R latch. So, (=
X , Y ) (=
Q, Q ) (1,1)
(vii) Race around condition: The difficulties of both the
inputs (S = R = 1) being not allowed in an SR latch is
eliminated in JK latch by using the feedback connec- Figure 8 Logic diagram of JK flip-flop
tion from the output to the input of the gate G1 and G2. Positive clock pulse is applied to the first latch and
In a normal JK latch if J = K = 1 and Q = 0 and enable the clock pulse will be inverted before its arrival at
signal is applied without RC differentiator, after a the second latch. When Clk = 1, the first latch is ena-
time interval ∆t (the propagation delay through two bled and the outputs Qm and Qm responds to the inputs
NAND gate in series) the output will change to Q = 1. J and K, according to the truth table of JK latch. At
Now we have J = K = 1 and Q = 1 and after another this time the 2nd latch is inhibited because its clock
time interval of ∆t the output will change back to Q = is low (Clk = 0). When the clock goes low (Clk = 0),
0. Hence for the duration of (tp) of the enable signal the first latch is inhibited and the second is enabled.
the output will oscillates back and forth between 0 and Therefore, the outputs Q and Q follow the outputs
1. At the end of the enable signal the values of Q is Qm and Qm , respectively. Since the second latch sim-
uncertain. This situation is referred to as race around ply follows the first one, it is referred to as slave and
condition. the first one as the master. Hence this configuration is
The race around condition can be avoided if enable known as master-slave JK flip-flop. In this circuit, the
time period tp < ∆t but it may be difficult to satisfy this input to the gate G1m and G2m do not change, during
condition, because of very small propagation delays the clock pulse levels.
in ICs. To solve this problem the enable signals are
converted to narrows spike using RC differentiator The race around condition does not exist.
circuit having a short time constant. Its output will be
Table 2 State/characteristic Table
high during the high transmission time of the enable.
Another method to avoid this problem is master-slave Clk J K Qt Qt+1
JK flip-flop. ↓
↓
0
0
0
0
0
1
0
1
}Q1
Flip-flops ↓ 1 0 0 1
}1
↓ 1 0 1 1
(i) Master-slave JK flip-flop: This is a cascade of 2 SR
latches with feedback from the output of the second SR
latch to the inputs of the first as shown in the figure below.
↓
↓
0
0
1
1
0
1
0
}
0 0
↓
↓
1
1
1
1
0
1
1
}
0 Qt
J S
Q S Q JK
Clk Q 00 01 11 10
Q R Q
K R 0 1 1
1 1 1
Qt +1 = J Qt + Qt K
(ii) Flip-flop switching time: In designing circuits with

flip-flop the following parameters are important:
1. Set-up time: The minimum amount of time
Pr required for the data input to be present before the
J Q
clock arrived.
Clk
2. Hold time: The minimum amount of time that the
K data input to be present after the clock trigger
Clr Q
arrived.
3. Propagation delay: The amount of time it takes for
the output to change states after an input trigger.
1 flip-flop can be realized using a SR/JK as show in the

Input figure below.
t t hold
0
Set-
up
Clock D S/J Q
i/p
Clk
R/K Q
Output Propagation
tp delay
t1 t2 t3 t4 Table 3 Truth Table
For example, t setup = 50 m sec and t hold = 5 m sec,

clk D Qt+1
the data bit has to be the input at least 50 m sec before ↑ X Qt
the clock bit arrives and hold at least 5 m sec after the ↑ 0 0
clock edge. ↑ 1 1
(iii) Triggering of flip-flop: The flip-flop can be triggered There is no raising problem with D flip-flop. High or
to set or reset either at one of the edges of the clock 1 state will set the flip-flop and a low or 0 state will
pulse. There are three types of triggering as described reset the flip-flop. The presence of inverter at the input
below: ensure that S/J and R/K inputs will always be in the
1. Positive edge triggering flip-flop: These set or opposite state.
reset at the positive (rising or leading) edge of the Table 4 Characteristic Table of D Flip-flop
clock pulse depending upon the state of i/p signal
and o/p remain steady for 1 clock period. Positive Qt D Qt+1
edge triggering is indicated by an arrow head at the 0 0 0
clock terminal of the flip-flop. 0 1 1
1 0 0
S Q
1 1 1
D
R Q Q 0 1
0 1
2. Negative edge triggered flip-flop: There are flip- 1 1
flops those in which state transmissions take Q t +1=D
place only at the negative edge (falling or trailing)
From the characteristic table of D.flip-flop, the next
of the clock signal. Negative edge triggering is
state of the flip-flop is independent of the present state
indicated by arrow head with bubble at the clock
since Qt+1 = D, whether Qt = 0 or 1.
terminal.
(v) T flip-flop: In a JK flip-flop J = K = 1 and the resulting
S Q
flip-flop is referred to as a T flip-flop.
Pr
R Q
T J Q
3. Level triggering: Level triggering means the
Clk FF
specified action occurs based on the steady state
value of the input. That is, when a certain level is K Q
reached (0 or 1) the output will change states level
triggering will be used in latches. Table 5 Truth Table
(iv) D flip-flop: It receives the designation from its ability Clk T Qn+1
to hold data into its internal storage. An SR/JK flip-
↑ 0 Qn
flop has two inputs. It requires two inputs S/J and R/K
to store 1 bit. This is a serious disadvantage in many ↑ 1 Qn
application to overcome the difficulty D flip-flop has ↑ x Qn
been developed which has only one input line. A D
If T = 1, it acts as a toggle switch for every Clk pulse 10

with high input, the Q changes to its opposite state.
0× 0 1 ×0
Table 6 Characteristic Table
01
Qt T Qt+1
0 0 0 Figure 9 State diagram of SR flip-flop
0 1 1
1×
1 0 1
1 1 0 0× 0 1 ×0
1 0 1
×1
T 0 1 Figure 10 State diagram of JK flip-flop
Q
0 1
1
1 1
0 0 1 0
Qt +1 = TQt + Qt T
1
(vi) Excitation table of flip-flops: The truth table of flip- Figure 11 State diagram of T flip-flop
flop is also referred to as the characteristic table, which
specifies the operational characteristic of flip-flop. 1
Sometimes we come across situations in which pre-
0 0 1 1
sent state and the next state of the circuit are known
and we have to find the input conditions that must pre- 0
vail to cause the desired transition of the state.
Consider initially JK flip-flop output Qn = 1, Q n Figure 12 State diagram of D flip-flop
= 0, after clock pulse it changed to Qn +1 = 0, Q n + 1 = 1, (viii) Conversion of one flip-flop to other flip-flop
The input conditions, which made this transition, Conversion of T flip-flop to JK flip-flop
can be 1. Write the characteristic table of required flip-flop
Toggle – for J = 1, K = 1, Qn +1 = Q n (here JK).
or 2. Write the excitation table of available or given
Reset – for J = 0, K = 1, Qn +1 = 0, Q n +1 = 1 Flip-flop (here T).
From the above conditions we can conclude that for 3. Solve for inputs of given flip-flop in terms of
transition Qn = 1 to Qn+1 = 0 occurs when J = 0 (or) 1 required flip-flop inputs and output.
(don’t care) and K = 1.
Table 8 JK flip-flop characteristic and T flip-flop excitation table
Similarly, input conditions can be found out for all
possible situations. JK Flip-flop
Characteristic Table T Flip-flop Excitation Table
Table 7 Excitation table of flip-flop.
J K Qn Qn+1 T
Present Next SR JK T D 0 0 0 0 0
State State Flip-flop Flip-flop Flip-flop Flip-flop
0 0 1 1 0
Qn Qn+1 S R J K T D
0 1 0 0 0
0 0 0 × 0 × 0 0
0 1 1 0 1
0 1 1 0 1 × 1 1
1 0 0 1 1
1 0 0 1 × 1 1 0
1 0 1 1 0
1 1 × 0 × 0 0 1
1 1 0 1 1
These excitation tables are useful in the design of syn- 1 1 1 0 1
chronous circuits.
KQ n
(vii) State diagrams of flip-flops: State diagram is a directed J 00 01 11 10
graph with nodes connected with directed arcs. State of 0 1
the circuit is represented by the node, the directed arcs 1 1 1 1
represent the state transitions, from present state (node)
to next state (node) at the occurrence of clock pulse. T = J Q n + KQn
The circuit is
J
(A) SR flip-flop with inputs A = S, B = R
T Q Q (B) SR flip-flop with inputs= A R= ,B S
K T (C) JK flip-flop with inputs A = J, B = K
Clk Q Q (D) JK flip-flop with inputs=A K=
,B J
Solution: (C)
Figure 13 D Flip-flop by using other flip-flops
The characteristic equation of D flip-flop is
D S Q D J Q
Qn+1 = D
Clk Here input D = AQ n + BQn

R Q K Q So, output Qn +1 = AQ n + BQn
By comparing this equation with characteristic equation of JK
Clk
Qn +1 = J Q n + KQn
T Q
D If A = J, B = K, then this circuit works like JK flip-flop.
Clk Q Example 4: The input Clk frequency for the flip-flop given
is 10 kHz, then the frequency of Q will be
Figure 14 T flip-flop by using other flip-flops
S Q Q
S Q
Clk
T R Q
R Q
(A) 10 kHz (B) 5 kHz

Clk
(C) 20 kHz (D) 2.5 kHz
T J Q Solution: (B)
=
Form circuit we can say S Q=
n, R Qn .
If initially (Qn , Q n ) = (0, 1), then inputs (S, R) = (1, 0), by
K Q
applying clk pulse (Qn +1 Q n +1 ) becomes (1, 0) . . .
Clr
Clk Qn Qn S R Qn+1 Q n+1
D Q 1 0 1 1 0 1 0
T
2 1 0 0 1 0 1
Clk Q 3 0 1 1 0 1 0
4 1 0 0 1 0 1
Example 3: A sequential circuit using D flip-flop and logic
gates is shown in the figure, where A and B are inputs and The output Qn+1 toggles for every clock pulse.
Q is output.
t
Clk
A
Q
D Q Q 2t
B
Clk Q Q 1 f 10
=
So frequency of Q = = = 5 kHz
2t 2 2
Examples 5: For the D flip-flop shown, if initially Qn is set are not clocked simultaneously. Each flip-flop is trig-
then what is the output state Qn+1 for X = 0, and for X = 1? gered by the previous flip-flop.
(ii) Asynchronous counters (ripple counters):

D Q Q
X Asynchronous counters do not have a common clock
that controls all the flip-flop stages. The control clock
Clk Q is input to the first stage. The clock for each stage
subsequent is obtained from the flip-flop of the prior
(A) 0, 0 (B) 0, 1 stages. Let us analyze the 3-bit counter and its corre-
(C) 1, 0 (D) 1, 1 sponding wave form diagram shown below.
Solution: (B)
QA QB
The characteristic equation of D is Qn+1 = D
Here D = X ⊕ Qn 1 JA QA 1 JB QB 1 JC QC
So Qn +1 = X ⊕ Qn Clk
We have Qn = 1 (Qn is set) for X = 0
1 KA 1 KB 1 KC
Qn+1 = 0 ⊕ 0 = 0
We have Qn = 1 (Qn is set), for X = 1 0 1 2 3 4 5 6 7
Clk
Qn+1 = 1 ⊕ 0 = 1
QA
Applications of flip-flops:
QB
1. Data storage: A group of flip-flops connected in
series/parallel is called a register, to store a data of QC
N-bits, N-flip-flops are required. Data can be stored
in parallel or serial order. Similarly, serial to parallel
Figure 15 Timing diagrams
conversion and parallel to serial conversion can be
done by using registers.
•• The counter has three flip-flops and three output bits,
2. Counting: A number of flip-flops can be connected in
therefore it is a three stage counter.
a particular fashion to count the pulses applied (Clk)
•• The input clock does not trigger the three flip-flops,
electronically. One flip-flop can count 2 Clk pulses,
therefore it is an asynchronous counter.
two flip-flops can count up to 22 = 4 pulses, similarly
•• The J and K inputs are tied together as kept high. So
n flip-flops can count up to 2n pulses. Flip-flops may
they are considered to be toggle flip-flops.
be used to count up/down.
•• The flip-flops are negative edge triggered.
3. Frequency division: Flip-flops may be used to divide
•• The wave form analysis reveals that QA is the LSB
input signal frequency by any number. A single flip-
1
flop may be used to divide the input frequency by 2. and that its frequency is the input clock frequency.
Similarly n flip-flops may be used to divide the input 2
1
frequency by 2n. Output of a MOD-n counter (i.e., Further more, Qc is the MSB and its frequency is the
which counts n states) will divide input frequency by n. 8
input clock frequency.
•• The count sequence is 000, 001, 010, 011, 100, 101,
Counters 110, 111 where the LSB is QA. Thus it is MOD-8
Digital counters consist of a number of flip-flops. Their binary up counter.
function is to count the number of clock pulses arriving at •• Asynchronous counters are also known as ripple
its clock input. counters because the effect of the input clock ripples
through the counter until it reaches the final stage.
(i) Counter classification: Counters are classified accord-
ing to their operational characteristic. Some of these Asynchronous Counter Design
characteristics include: Step I: Write the counting sequence.
1. Counter triggering techniques Step II: Tabulate the values of reset signals. R for various
2. Frequency division characteristic state of counter.
3. Counter modulus Step III: Obtain the minimal expression for R and R using
4. Asynchronous or synchronous K-map or any other method.
In a synchronous counter all flip-flops are clocked Step IV: Provide a feedback such that R or R resets all the
simultaneously. In asynchronous counter the flip-flops flip-flops after the desired count.
Table 9 Identification of up/down Counters

After Pulses States Q3, Q2, Q1 Reset R
Clock Triggering Q Type 0 000 0
+ve edge Up 1 001 0
Q
2 010 0
+ve edge Q Down
3 011 0
-ve edge Down
Q 4 100 0
-ve edge Q Up 5 101 0
6 110 1
Clock is negative triggering pulse and Q is connected to 7 ↓↓↓

next level clock, it is acting like a up counter. 000 0
111 X
Table 10 Identification of GATE to Clear the Flip-flops From the Truth table R = Q3 Q2
For active Low R is used.
Input to the Gate Output of the Gate Type of Gate
∴ R = 0 for 000 to 101
OR
Q
Clr
R = 1 for 110
R = X for 111
Clr NOR
Q ∴ K-map is
Q2Q3
Q NAND Q1 00 01 11 10
Clr
0 1
Q Clr AND
1 ×
∴ R = Q2 Q3
Example:
Logic diagram is
1 1 1
(i) Clr
Q T2 Q2
T1 Q1 T3 Q3
Clk
Q1 Q2 Q3
(ii) Clr Clr Clr
Q Clr
Asynchronous Decode Counter

Example 6: Design and Implement a MOD-6 asynchronous A ripple counter is an asynchronous sequential circuit,
counter using T flip-flops. clock is applying only for LSB side. Decade ripple counter
Solution: Counting sequence is 00, 001, 010, 011, 100, it counts from 0 to 9 for up counter.
101 MOD-10 counter it counts starting from 0000 to 1001. If
the NAND gate output is logic ‘0’ at that instant the counter
reset to initial state.
Q3
Q2
Clr
Q1
Q0
J0 Q0 J1 Q1 J2 Q2 J3 Q3
Clock
K0 K1 K2 K3
1 Clr Q 0 1 Clr Q 1 1 Clr Q 2 1 Clr Q 3
Figure 16 MOD-10 or decade counter

To design a MOD-N counter minimum number of flip-flops

required is 1 T0 Q0 T1 Q1 T2 Q2
N ≤ 2n
Clock
where N → MOD
n → No. of flip-flops Q0 Q1 Q2
Example: Figure 17 3-bit series carry counter

MOD-5 counter
5 ≤ 2n
1
∴n=3 f Clk ≤
t pd + ( n − 2)t pd AND
Operating Clock Frequency
(i) Synchronous counter: where
tpd → Propagation delay of each flip-flop.
1 tpd AND → Propagation delay of AND gate.
f Clk ≤
t pd n → Number of flip-flops.
In this, Qo toggles for every clock pulse.
(ii) Asynchronous counter: Q1 toggles when Qo is 1.
Q2 toggles when o/p of AND gate is logic 1.
1
f Clk ≤ Note: To design a synchronous series carry down counter.
nt pd
Connect Qo to the next flip-flop input.
Output frequency of the MOD-N counter is
Design of Synchronous Counter
f Clk Step I: Determine the required number of flip-flop.
⇒ fo = . Step II: Draw the state diagram showing all possible states.
N
Step III: Select the type of flip-flop to be used and write the
(iii) Synchronous counter: When counter is clocked excitation table.
such that each flip-flop in the counter is triggered at Step IV: Obtain the minimal expressions for the excitations
the same time, the counter is called as synchronous of the FFs using the K-maps.
counter. Step V: Draw a logic diagram based on the minimal expres-
•• Synchronous counters have the advantage of high sion. Let us employ these techniques to design a
speed and less severe decoding problems. MOD-8 counter to count in the following.
•• Disadvantage is having more circuiting than that of
Example 7: Sequence: 0, 1, 2, 3, 4, 5, 6, and 7. Design a
asynchronous counter.
synchronous counter by using JK flip-flops.
Synchronous Series Carry Counters Solution:

Step I: Determine the required number of flip-flops. The
For normal ring counters to count N sequence total N flip-
sequence shows a 3-bit up counter that requires 3
flops are required.
flip-flops.
Unused states in ring counter = 2N – N. Step II: Draw the state diagram.
Unused states in Johnson ring counter = 2N – 2N.
111
Asynchronous counters are slower than the synchronous
counters. By using synchronous series carry adders we can
000
design MOD-N counter with n Flip-flops-only.
110
For non-binary counters N ≤ 2n
001
3-bit series carry up counter
It counts from initial state 000 to 111. 100
∴ MOD = 2n = 8 states 010
011
∴ MOD-8
Step III: Select the type of flip-flop to be used and write the 1

excitation table.
JK flip-flop is selected and excitation table of a 3-bit up J1 Q1 J2 Q1 J3
counter is FF1 FF2 FF3
PS NS Required Excitation J2 Q1 K2 Q K3
Q3 Q2 Q1 Q3 Q2 Q1 J3 K3 J2 K2 J1 K1
Clk
0 0 0 0 0 1 0 x 0 x 1 x
0 0 1 0 1 0 0 x 1 x x 1
0 1 0 0 1 1 0 x x 0 1 x
Table 11 Comparison between asynchronous counter and
0 1 1 1 0 0 1 x x 1 x 1 synchronous counter
1 0 0 1 0 1 x 0 0 x 1 x
Asynchronous Counter Synchronous Counter
1 0 1 1 1 0 x 0 1 x x 1
1. In this type of counter, In this type there is no con-
1 1 0 1 1 1 x 0 x 0 1 x flip-flops are connected nection between output of first
1 1 1 0 0 0 x 1 x 1 x 1 in such a way that output flip-flop and clock input of the
of first flip-flop drives the next flip-flop
clock for the next flip-flop
Step IV: Obtain the minimal expression using K-map.
2. All the flip-flops are not All the flip-flops are clocked
Q 2Q 1 clocked simultaneously simultaneously
Q 3 00 01 11 10 3. Logic circuit is very simple Design involves complex logic
0 1 even for more number of circuits as number of state
states increases
1 × × × ×
J 3 = Q 2Q 1 4. Main draw back of these As clock is simultaneously
counters is their low speed given to all flip-flops, there is no
Q 2Q 1 as the clock is propagated problem of propagation delay.
Q 3 00 01 11 10 through number of flip- Hence they are preferred when
flops before it reaches last number of flip-flops increases in
0 × × × ×
flip-flop the given design.
1 1
K 3 = Q 2Q 1
The main drawback of ripple counters is their high
Q 2Q 1 delays, if propagation delay of each flip-flop is
Q 3 00 01 11 10 assumed as x, then to get output of the first flip-flop
0 1 × × it takes x, i.e., after x seconds the second flip-flop
1 1 × × will get its clock pulse from previous stage, and out-
J2 = Q1 put of second flip-flop will be out after another x
seconds, similarly the final output of last flip-flop
Q 2Q 1
Q 3 00 01 11 10 will be after nx seconds, where n is the number of
0 × 1 × flip-flops. So the propagation delay of ripple counter
1 × 1 ×
is nx, which is directly proportionate to the number
of flip-flops.
K 3 = Q1
The maximum frequency of operation of ripple
Q 2Q 1 1
Q3 00 01 11 10 counter is inverse of delay, f max =
nx
0 1 × × 1 Maximum operating frequency is the highest fre-
1 1 × × 1 quency at which a sequential circuit can be reliably
triggered. If the clock frequency is above this maxi-
J1 = 1
mum frequency the flip-flops in the circuit cannot
Q 2Q 1 respond quickly and the operation will be unreliable.
Q3 00 01 11 10 In case of synchronous counters (synchronous
0 × 1 1 × circuits) as clock is applied simultaneously to all the
1 × 1 1 × flip-flops, the output of all the flip-flops change by x
seconds (delay of one flip-flop) and this delay is inde-
K1 = 1
pendent of number of flip-flops used in circuit.
Step V: Draw the logic diagram based on the minimal The maximum frequency of operation of synchro-
expression. 1
nous counter is inverse of delay f max =
x
Example 8: The maximum operation frequency of

a MOD-64 ripple counter is 33.33 kHz, the same flip- Serial data Serial data
input output
flops are used to design a MOD-32 synchronous counter,
and then the maximum operating frequency of the new
Serial-in–serial-out right-shift register
counter is
(A) 400 kHz (B) 200 kHz
(C) 40 kHz (D) 500 kHz (ii) Serial-in–parallel-out:
1 Serial data
Solution: For ripple counter f max = , given is a MOD-64
nx input
ripple counter, i.e., 26 states, so n = 6 flip-flops are required.
1
x= = 5µ S
33.33K × 6
Parallel data output
For synchronous counter
(iii) Parallel-in–parallel-out:
1 1
f max = = = 0.2 MHz = 200 kHz Parallel data input
x 5 µS
When multiple counters are connected in cascade, then the
total number of states of the new counter is A × B × C, i.e.,
it will work as MOD-A × B × C counter.
MOD-A MOD-B MOD-C

counter counter counter
For example, decade counter counts from 0 to 9, 10 states –

Parallel data output
If two such decade counters are connected in cascade, then
the total counting states will be 10 × 10 = 100, it will work
as MOD-100 counter, which counts from 00 to 99. (iv) Parallel-in–serial-out:
Parallel data input
Registers
A number of flip-flops connected together such that data
may be shifted into and shifted out of them is called a shift
register. There are four basic types of shift register: Serial
data
1. Serial-in–serial-out output
2. Serial-in–parallel-out
3. Parallel-in–serial-out
4. Parallel-in–serial-out Serial input and serial output register: This type of
shift register accepts data serially, i.e., one bit at a
(i) Serial-in–serial-out:
time and also outputs data serially. The logic diagram
Serial data Serial data
of 4-bit serial input, serial output, shift-right, shift
output input register is shown in the following figure. With four D
flip-flops the register can store up to four bits of data.
Q3 Q2 Q1 Q0
SET SET SET SET
Serial input D Q D Q D Q D Q Serial output
Clr Q Clr Q Clr Q Clr Q

Clk
Figure 18 Serial input and serial output register

If initially, all flip-flops are reset, then by apply-

Clk Q2 Q1 Q0
ing serial input 1101, the flip-flop states will change as
shown in below table. 0 1 0 0
Clk S.I Q3 Q2 Q1 Q0
1 0 1 0
0 1 0 0 0 0 2 0 0 1
1 0 1 0 0 0 3 1 0 0
4 0 1 0
2 1 0 1 0 0
3 1 1 0 1 0 100
4 1 1 0 1
001 010
The first data bit 1 will appear at serial output after 4
clock pulses. A ring counter with N flip-flops can count up to N states,
i.e., MOD-N counter, whereas, N-bit asynchronous counter
Application of Shift Registers can count up to 2N states. So, ring counter is uneconomi-
1. Delay line: Serial input and serial output shift register cal compared to a ripple counter, but has the advantage of
can be used to introduce delay in digital signals. requiring no decoder. Since it is entirely synchronous oper-
1 ation and requires no gates for flip-flop inputs, it has further
Delay = no.of flip-flops × = No. of
Clk frequency advantage of being very fast.
flip-flops × time period of clock pulse Twisted ring counter (Johnson counter): This counter is
2. Serial to parallel, parallel to serial converter: SIPO, obtained from a SISO shift register by connecting the comple-
PISO registers used for data conversion. ment of serial output to serial input as shown in below figure.
3. Sequence generator: A circuit, which generates a Q2 Q1 Q0
prescribed sequence of bits, with clock pulses is D
SET Q
D
SET
Q D SET Q
called as sequence generator
The minimum number of flip-flops ‘n’ required to gen-
erate a sequence of length ‘S’ bits is given by S ≤ 2n - 1
Clr Q Clr Q Clr Q
Shift register counters Clk
One of the applications of the shift register is that they
Figure 20 Twisted Ring Counter
can be arranged to work as ring counters. Ring counters
are constructed by modifying the serial-in, serial-out, shift Let initially all the FFs be reset, after each clock pulse
registers. There are two types of ring counters—basic ring the complement of last bit will appear as at MSB, and other
counter and twisted ring counter (Johnson counter). The bits shift right side by 1-bit. After 6 clock pulses the register
basic ring counter is obtained from SISO shift register by will come to initial state 000. Similarly, the 3-bit Johnson
connecting serial output to serial input. counter will oscillate between the states 101, 010.
Q2 Q1 Q0 Clk Q2 Q1 Q0
SET Q SET D SET Q
D D Q
0 0 0 0
1 1 0 0
Clr Q Clr Q Clr Q 2 1 1 0

Clk
3 1 1 1
Figure 19 Ring counter
In most instances, only a single 1 or single 0 is in the 4 0 1 1
register and is made to circulate around the register as long
as the clock pulses are applied. Consider initially first flip- 5 0 0 1
flop is set, and others are reset. After 3 clock pulses, again 6 0 0 0
we will get initial state of 100. So this is a MOD-3 counter.
1
000 Solution: N ≤
f max ⋅ t pd
001
fmax = 10 MHz N ≤ 8
100
tpd = 12 ns
1
N≤
10 × 10 × 12 × 10 −9
6
011 110
MOD counter is = 2N = 28 = 256
111 Example 6: An AB flip-flop is constructed from an SR
flip-flop as shown below. The expression for next state Q+ is
A
An n-bit Johnson counter can have 2n unique states and S Q
can count up to 2n pulses, so it is a MOD-2n counter. It is
Clk
more economical than basic ring counter but less economi-
cal than ripple counter. B R
Solution:
Solved Examples
A B Q S R Q+
Example 1: Assume that 4-bit counter is holding the count
0101. What will be the count after 27 clock pulses? 0 0 0 1 0 1
0 0 1 1 0 1
Solution: Total clock pulses: 27 = 16 + 11
0 1 0 0 1 0
0101 + 1011 = 0000
0 1 1 0 1 0
Example 2: A MOD-2 counter followed by MOD-5 1 0 0 0 0 0
counter is
1 0 1 0 0 1
Solution: A decade counter, counts 10 states (5 × 2). 1 1 0 1 1 ×
Example 3: A 4-bit binary ripple counter uses flip-flops 1 1 1 1 1 ×

with propagation delay time of 25 msec each. The maximum
possible time required for change of state will be ∴ Q + = AB + AQ = AB + BQ
Solution: The maximum time = 4 × 25 ms = 100 ms
Example 7: In the circuit shown below, the output y1 and y2
Example 4: Consider the circuit, the next state Q+ is for the given initial condition y1 = y2 = 1 and after four input
pulses will be
Y1
S
Q J Q J Q Y2
Clk
P Clk Clk
R
K Q K Q
Solution
P Q S R Q+
0 0 0 1 0 Solution:
0 1 1 0 1 After 1st pulse y1 = 0, y2 = 1
1 0 1 0 1 After 2nd pulse y1 =0, y2 = 0
After 3rd pulse y1 =1, y2 = 0
1 1 0 1 0
After 4th pulse y1 = 1, y2 = 1
So, Q+ = P ⊕ Q Example 8: A ripple counter is to operate at a frequency
Example 5: A certain JK FF has tpd = 12 n sec what is the of 10 MHz. If the propagation delay time of each flip-flop
largest MOD counter, that can be constructed from these FF in the counter is 10 ns and the storbing time is 50 ns, how
and still operate up to 10 MHz? many maximum stages can the counter have?
1 b7 b6 b5 b4 b3 b2 b1 b0
Solution: nt pd + t s ≤
f
where, n = number of stages
D Q
tpd = propagation delay time
Clk
ts = strobing time Q1
f = frequency of operation = 10 × 10– 9n + 50 × 10– 9
1
≤ Solution: The output of XOR gate is Z = bi + 1 ⊕ bi and this
10 × 106
output shift the register to left. Initially, Z = 0
(or) 10n + 50 ≤ 100
After 2nd clock Z = b7 ⊕ 0 = b7
(or) 10n ≤ 50
For max stages n = 50 After 2nd clock Z = b7 ⊕ b6
=5 3rd clock Z = b6 ⊕ b5
10
Example 9: In the circuit assuming initially Q0 = Q1 = 0. 4th clock Z = b5 ⊕ b4
Then the states of Q0 and Q1 immediately after the 33rd It is a binary to gray code converter.
pulse are
Example 12: A 4-bit MOD-16 ripple counter uses JK
Q0 flip-flops. If the propagation delay of each flip-flop is 50
J0 Q0 J1 Q1 ns sec, the maximum clock frequency that can be used is
equal to
1 K0 Q1 K1 Q2
1
Solution: Max = clock frequency = = 5 MHz
Clk 4 × 50 × 10 −9
Solution:
Example 13: What is the state diagram for the sequential
J0 K0 J1 K1 Q0 Q1 Count circuit shown?
1 1 0 1 0 0 Initial
1 1 1 0 1 0 1st pulse
0 1 0 1 0 1 2nd
J Q
1 1 0 1 0 0 3rd X
1 1 1 0 1 0 4th Clk
0 1 0 1 0 1 5th pulse
Q1
After 4th pulse, output is same as after 1st one, so, sequence K
gets repeated. So output after 33rd pulse would be same as
after 3rd pulse. i.e., (00).
Example 10: The frequency of the pulse at z in the network X=1
shown in figure is
w
(A) X=0 0 1 X=0
10-bit 4-bit Parallel
Ring counter counter X=1
160 kHz
X=1
y
Mod-25 4-bit Jhonson
z
(B) X=0 0 1 X=0
x Ripple counter counter
X=0
Solution: 10-bit ring counter is a MOD-10. So, it divides
X=1
the 160 kHz input by 10. Therefore, w = 16 kHz. The 4-bit
parallel counter is a MOD-16. Thus, the frequency at x = 1 (C) X=0 0 1 X=0
kHz. The MOD-25 ripple counter produces a frequency at y
= 40 Hz (1 kHz/25 = 40 Hz). The 4-bit Johnson counter is X=1
a MOD-8. The frequency at Z = 5Hz. X=1
Example 11: The 8-bit shift left shift register, and D flip- (D) X=0 0 1 X=0
flop shown in the figure is synchronized with the same
clock. The D flip-flop is initially cleared. The circuit acts as X=0
Solution: (D) X=1

State diagram of a sequential circuit will have states (output)
X=0 0 1 X=1
of all the flip-flops.
X=0
Present state Next state Qn+1
Qn For x = 0 For x = 1
0 0 1
1 0 1
Exercises
Practice Problems 1 (A) 001 (B) 010
Directions for questions 1 to 22: Select the correct alterna- (C) 100 (D) 101
tive from the given choices. 6. 12 MHz clock frequency is applied to a cascaded coun-
1. How many flip-flops are needed for MOD-16 ring counter of MOD-3 counter, MOD-4 counter and MOD-5
ter and MOD-16 Johnson counter? counter. The lowest output frequency is
(A) 16, 16 (B) 16, 8 (A) 200 kHz (B) 1 MHz
(C) 4, 3 (D) 4, 4 (C) 3 MHz (D) 4 MHz
2. A 2-bit synchronous counter uses flip-flops with propa- 7. In the modulo-6 ripple counter shown in the figure
gation delay time of 25 n sec, each. The maximum pos- below, the output of the 2-input gate is used to clear the
sible time required for change of state will be JK flip-flops. The 2-input gate is
1
(A) 25 n sec (B) 50 n sec
(C) 75 n sec D) 100 n sec
C J0 B J1 A J2
3. For given MOD-16 counter with a 10 kHz clock input Clk
determine the frequency at Q3 C K0 B K A K
CP 1
10 kHz 2 input Reset
CP 0 MOD-16 gate
(A) a NAND gate (B) a NOR gate

(C) an OR gate (D) an AND gate
Q 3Q 2Q 1Q 0
8. In figure, J and K inputs of all the 4 flip-flops are made
high, the frequency of the signal at output y is
(A) 625 Hz (B) 10 kHz
(C) 2.5 kHz (D) 0 Hz J Q J Q J Q J Q
4. A 4-bit ripple counter and a 4-bit synchronous counter
are made using flip-flops having a propagation delay of K Clr
K Clr K Clr K Clr
10 n sec each. If the worst case delay in the ripple coun-
ter and the synchronous counter be R and S, respec- F = 10 kHz
tively, then
(A) R = 10 ns, S = 40 ns (B) R = 40 ns, S = 10 ns
(C) R = 10 ns, S = 30 ns (D) R = 30 ns, S = 10 ns
(A) 0.833 kHz (B) 1.0 kHz
5. The counter shown in the figure has initially Q2Q1Q0 =
(C) 0.91 kHz (D) 0.77 kHz
000. The status of Q2Q1Q0 after the first pulse is
9. In a number system a counter has to recycle to 0 at the
sixth count. Which of the connections indicated below
will realize this resetting? (a logic ‘0’ at the R inputs
resets the counters)
J2 Q2 J1 Q1 J0 Q0
x y z
Q Q2 Q
K2 Clk Clk Clk
Q2 K1 Q1 K0 Q0 Q Q Q
Clk Rx Ry Rz
x (A) Qn Qn+1 A B (B) Q Q A B

(A) y
Rx, Ry n n+1
0 0 0 x 0 0 1 x
y 0 1 1 x 0 1 0 x
(B) Rx, Ry, Rz
z
1 0 x 1 1 0 x 0
x 1 1 x 0 1 1 x 1
(C) y Rx, Ry, Rz
z
(C) Q Q A B (D) Q Q A B
x n n+1 n n+1
(D) Rx, Rz
z 0 0 x 0 0 0 x 0
0 1 x 1 0 1 1 x
10. Two D flip-flops, as shown below, are to be connected
1 0 x x 1 0 x 1
as a synchronous counter that goes through the follow-
ing Q1Q0 sequence 00 → 01 → 11 → 10 → 00. The 1 1 0 x 1 1 0 x
inputs D0 and D1 respectively should be connected as
15. A shift register that shift the bits 1 position to the right
at each clock pulse is initialized to 1100 (Q0, Q1, Q2,
D0 Q0 D1 Q1
LSB MSB Q3). The outputs are combined using an XOR gate cir-
Clk Q 0 Clk Q 1 cuit and fed to the D input. After which clock pulse,
will the initial pattern reappear at the output?
Clk
(A) Q 0 and Q1 (B) Q 0 and Q1

Serial input Q1 Q2 Q3
(C) Q1 Q 0 and Q1Q0 (D) Q1Q0 and Q1Q0 D
Q0
11. N flip-flops can be used to divide the input clock fre-

quency by
(A) N (B) 2N (A) 6th (B) 5th
(C) 2N (D) 2N-1 (C) 4th (D) 7th
12. For a shift register as shown, x = 1011, with initially FF 16. If we need to design a synchronous counter that goes
cleared, ABC will have value of after 3 clock pulses through the states 00 → 01 → 11 → 10 → 00 using D
FF, what should be the input to the FF?
A B C
D0 Q0 D1 Q1
Q1 MSB
X J Q J Q J Q Clk Q0 Clk
K Q K Q K
(A) 101 (B) 011 (A) D0 = Q0, D1 = Q1

(C) 001 (D) 111
(B) D0 = Q1 , D1 = Q0
13. If a FF is connected as shown what will be the output? (C) D0 = Q1 ⋅ Q0 , D1 = Q1Q0
(initially Q = 0)
(D) D0 = Q0 , D1 = Q1
17. Find the counter state sequence (Assume Q0 as MSB).

T Q
Clk
Q
(A) 11111 (B) 0000 D2

D0 Q0 D1 Q1
(C) 1010 (D) 0101
Q2
14. The excitation table for a FF whose output conditions
are if AB = 00, no change of state occurs
AB = 01, FF becomes 1 with next clock pulse
AB = 10, FF becomes 0 with next clock pulse (A) 4, 6, 7, 3, 1, 0, 4 (B) 4, 6, 5, 3, 1, 0, 4
AB = 11, FF changes its state (C) 4, 5, 6, 7, 0, 4, 5 (D) 4, 6, 7, 1, 0, 4
18. If the propagation delay of each FF is 50 ns, and for the (A) MOD-2 counter
AND gate to be 20 ns. What will be the fmax for MOD- (B) MOD-4 counter
32 ripple and synchronous counters? (C) MOD-3 counter
(A) 14.3 MHz, 4 MHz (B) 14.3 MHz, 5 MHz (D) MOD-2 generate 00, 10, 00
(C) 5 MHz, 14.3 MHz (D) 3.7 MHz, 14.3 MHz 21. The MOD number of asynchronous counter shown
19. For a given counter identify its behavior All J = K = 1
(1) (1) T Q J Q0 J J J J
T P
Clk
Clk P K Clr K Clr K Clr K Clr K Clr
Q
The output is taken from PQ.

(A) MOD-4 up counter
(B) MOD-2 down counter (A) 24 (B) 48
(C) MOD-4 down counter (C) 29 (D) 28
(D) MOD-2 up counter
22. For the oscillator, find the fundamental frequency if
20. A circuit using T FF is given. Identify the circuit. propagation delay of each inverter is 1000 psec.
T Q T Q
A B (A) 100 MHz (B) 10 MHz
Clk Q Clk Q
(C) 1 GHz (D) 10 GHz
Practice Problems 2 4. Figure below shown as ripple counter using positive edge
Directions for questions 1 to 30: Select the correct alterna- triggered flip-flops. If the present state of the counters is
tive from the given choices. Q2 Q1 Q0 = 011, then its next state (Q2Q1Q0) will be
1. Match List 1 (operation) with List 2 (associated device) 1 1 1
and select the correct answer using the codes given T0 Q0 T1 Q1 T2 Q2
below:
List 1 List 2 Clk Q0 Q1 Q2
(a) Frequency Ddivision (1) ROM
(b) Decoding (2) Multiplexer (A) 010 (B) 100
(c) Data selection (3) Demultiplexer (C) 111 (D) 101
(d) Code conversion (4) Counter
5. A synchronous sequential circuit is designed to detect
a bit sequence 0101 (overlapping sequence include).
(A) a–3, b–4, c–2, d–1
Every time, this sequence is detected, the circuit pro-
(B) a–3, b–4, c–1, d–2
duces output of 1. What is the minimum number of
(C) a–4, b–3, c–1, d–2
states the circuit must have?
(D) a–4, b–3, c–2, d–1
(A) 4 (B) 5
2. A MOD-5 synchronous counter is designed by using (C) 6 (D) 7
JK flip-flop, the number of counts skipped by it will be
6. What is represented by digital circuit given below?
(A) 2 (B) 3
(C) 5 (D) 0
3. A counter starts off in the 0000 state, then clock D Q
pulses are applied. Some time later the clock pulses A
are removed and the counter flip-flops read 0011. How
B
many clock pulses have occurred?
Q
(A) 3 (B) 35
(C) 51 (D) Any of these
(A) An SR flip-flop with A = S and B = R (C) S Qn

D
(B) A JK flip-flop with A = K and B = J Clk
(C) A JK flip-flop with A = J and B = K Qn
R
(D) An SR flip-flop with A = R and B = S
7. In a ripple counter, the state whose output has a fre-
1 (D) S
quency equal to th that of clock signal applied to the D Qn
8
1 R Clk Qn
first stage, also has an output periodically equal to th
8
that of the output signal obtained form the last stage.
The counter is
(A) MOD-8 (B) MOD-6
(C) MOD-64 (D) MOD-16 12. Which of the circuit is being represented by the figure?
8. A flip-flop is popularly known as t1 t1
C
(A) Astable multivibrator •
(B) Bistable multivibrator t1 Q
G1 R G2
(C) Monostable multivibrator
(D) None of these
9. Which of the following represents the truth table for JK (A) NAND gate
flip-flop? (B) Monostable multivibrator
(C) Astable multivibrator
(A) J K Output (B) J K Output (D) Schmitt trigger
0 0 Q0 0 0 Q0 13. Hold time is
(A) time for which output is held constant.
0 1 0 0 1 0
(B) time for which clock is to be held constant on
1 0 1 1 0 1
applying input.
1 1 Q0 1 1 Q0 (C) time for which input should be maintained con-
stant after the triggering edge of clock pulse.
(D) time for which input should be maintained con-
(C) J K Output (D) J K Output stant prior to the arrival of triggering edge of
0 0 Q0 0 0 1 clock pulse.
0 1 0 0 1 0 14. Shift registers are made up of
1 0 1 1 0 1 (A) MOS inverters (B) FF
1 1 Invalid 1 1 0 (C) Latches (D) None of these
15. Data from a satellite is received in serial form. If the
10. One disadvantage of master-slave FF is data is coming at 8 MHz rate, how long will it take to
(A) setup time becomes longer. serially load a word in 40-bit shift register?
(B) it requires input to be held constant before clock (A) 1.6 µs (B) 5 µs
transition. (C) 6.4 µs (D) 12.8 µs
(C) unpredictable output even if input held constant.
16. A JK FF can be converted into T FF by connecting
(D) hold time becomes longer.
11. Which of the following converts D FF to SR FF? (A) Q to 0
(B) 0 to Q
(A) S (C) 0 to Q
D Qn
(D) by connecting both J and K inputs to T
R
Clk Qn 17. The flip-flop that is not affected by race around
condition
(A) T FF (B) JK FF
(B) S (C) SR FF (D) None of these
D Qn
R 18. The characteristic equation of JK FF is
Clk Qn (A) J′Q(t) + KQ′(t) (B) J′Q(t) + KQ(t)
(C) JQ′(t) + K′Q(t) (D) None of these
19. For a D.FF input, the s Q is connected. What would be 25. A divide by 50 counter can be realized by using
the output sequence? (A) 5 no. of MOD-10 counter
(A) 0000 (B) 1111 (B) 10 no. of MOD-5 counter
(C) 010101 (D) 101010 (C) One MOD-5 counter followed by one MOD-10
counter
20. In order to implement a MOD-6 synchronous counter (D) 10 no. of MOD-10 counter
we have 3 FF and a combination of 2 input gate(s).
26. The following latch is
Identify the combination circuit.
(A) One AND gate
(B) One OR gate X S Q
(C) One AND and one OR gate
Clk
(D) Two AND gates
21. Given a MOD-5 counter. The valid states for the coun- R Q
ter are (0, 1, 2, 3, 4). The propagation delay of each FF
is TF and that of AND gate is tA. The maximum rate at
which counter will operate satisfactorily (A) D latch (B) T latch
(C) JK latch (D) RS latch
27. Which of the following represent a 3-bit ripple counter
J0 Q0 J1 Q1 J2 Q2 using D FF?
1 K0 Q0 K1 Q1 1 K2 Q2 (A)
D1 Q1 D2 Q2 D3 Q3
Clk Clk Q1 Q2 Q3
1 1
(A) (B) (B)
tF + t A 3t F
D1 Q1 D1 Q2 D3 Q3
1 1 Clk
(C) (D) Q1 Q2 Q3
2t F + t A 3t F − t A
(C) Both (A) and (B)
22. For a NOR latch as shown up A and B are made first (D) None of these
(0, 1) and after a few seconds it is made (1, 1). The cor-
responding output (Q1, Q2) are 28. For the Johnson counter with initial Q2, Q1, Q0 as 101,
the frequency of the output is (Q2, Q1, Q0)
A Q1
J2 Q 2 J 1 Q1 J0 Q0
K2 Q2 K1 Q1 K0 Q0
B Q2
(A) first (1, 0) then (0, 0) fc fc

(B) first (1, 0) then (1, 0) (A) (B)
8 6
(C) first (1, 0) then (1, 1)
fc f
(D) first (1, 0) then (0, 1) (C) (D) c
2 4
23. In order to design a pulse generator to generate the
wave form using a shift register, what is the number of 29. For the given circuit the contents of register (b7 - b0)
FF required? are 10010101, what will be the register contents after
8 clock pulses?
1 0 1 1 1 0 1
b7 b6 b5 b4 b3 b2 b1 b0
(A) 3 (B) 4
(C) 5 (D) 6
D Q
24. For what minimum value of propagation delay in each
Clk
FF will a 10-bit ripple counter skip a count when it is
clocked at 5 MHz?
(A) 10 ns (B) 20 ns
(C) 25 ns (D) 15 ns
(A) 10010101 (B) 01101010 1 0 0 1

(C) 11011111 (D) 01101011 1 0 1 1
30. A latch is to be build with A and B as input. From the 1 1 0 1
table find the expression for the next state Q+ 1 1 1 1
A B Q Q+
(A) A
0 0 0 0 (B) B
0 0 1 0 (C) A+ B
0 1 0 0
(D) AB + AB
0 1 1 0

1. Consider the following circuit. (D) f D D Q
Q
Q0 D1
D0 Q1
Clk
Q 1′
Q 0′
3. Consider the circuit in the diagram. The ⊕ operator
represents Ex-OR. The D flip-flops are initialized to
zeros (cleared). [2006]
Clk
The flip-flops are positive edge triggered D FFs. Each

Q D Q D Q D Data
state is designated as a 2-bit string Q0Q1. Let the initial q2 q1 q0
Clk Clk Clk
state be 00. The state transition sequence is [2005]
Clock
(A) 00 11 01
The following data: 100110000 is supplied to the data

(B) 00 11 terminal in 9 clock cycles. After that the values of
q2q1q0 are
00 11 01 11 (A) 000 (B) 001
(C)
(C) 010 (D) 101
(D) 00 11 01 10 4. The control signal functions of a 4-bit binary counter
are given below (where X is ‘don’t care’):
Clear Clock Load Count Function
2. You are given a free running clock with a duty cycle 1 X X X Clear to 0
of 50% and a digital waveform f which changes only
0 X 0 0 No change
at the negative edge of the clock. Which one of the
0 ↑ 1 X Load input
following circuits (using clocked D flip-flops) will
delay the phase of f by 180°? [2006] 0 ↑ 0 1 Count next
f
The counter is connected as follows:
(A) D D Q
Q
A4 A3 A2 A1
Clk
(B) f D Q D Q
Clk Count = 1
4-bit counter Load = 0
Clear Clock
(C) f D Q D Q Inputs
Clk
0 0 1 1
Assume that the counter and gate delays are negligi- (A) 000 (B) 001
ble. If the counter starts at 0, then it cycles through the (C) 010 (D) 011
following sequence: [2007]
(A) 0, 3, 4 (B) 0, 3, 4, 5 9. Let K = 2n. A circuit is built by giving the output of an
(C) 0, 1, 2, 3, 4 (D) 0, 1, 2, 3, 4, 5 n-bit binary counter as input to an n-to-2n-bit decoder.
This circuit is equivalent to a [2014)
5. In the sequential circuit shown below, if the initial (A) K-bit binary up counter
value of the output Q1Q0 is 00, what are the next four (B) K-bit binary down counter
values of Q1Q0? [2010] (C) K-bit ring counter
(D) K-bit Johnson counter
10.
1 T Q T Q
Clock
J Q2 J Q1 J Q0
C C C
K Q2 K Q1 K Q0
Q0 Q1
(A) 11, 10, 01, 00 (B) 10, 11, 01, 00 The above synchronous sequential circuit built using
(C) 10, 00, 01, 11 (D) 11, 10, 00, 01 JK flip-flops is initialized with Q2Q1Q0 = 000. The
state sequence for this circuit for the next 3 clock
6. The minimum number of D flip-flops needed to
cycles is [2014]
design a MOD-258 counter is [2011]
(A) 001, 010, 011 (B) 111, 110, 101
(A) 9 (B) 8
(C) 100, 110,111 (D) 100, 011, 001
(C) 512 (D) 258
11. Consider a 4-bit Johnson counter with an initial value
Common Data for Questions 7 and 8: Consider the fol-
of 0000. The counting sequence of this counter is
lowing circuit involving three D-type flip-flops used in a
[2015]
certain type of counter configuration.
(A) 0, 1, 3, 7, 15, 14, 12, 8, 0
(B) 0, 1, 3, 5, 7, 9, 11, 13, 15, 0
(C) 0, 2, 4, 6, 8, 10, 12, 14, 0
P
D Q (D) 0, 8, 12, 14, 15, 7, 3, 1, 0
Clock Q 12. A positive edge-triggered D–flip-flop is connected
to a positive edge-triggered JK flip-flop as follows.
Q
The Q output of the D flip-flop is connected to both
D Q the J and K inputs of the JK flip-flop, while the Q
output of the JK flip-flop is connected to the input
Clock Q
of the D flip-flop. Initially, the output of the D flip-
flop is set to logic one and the output of the JK flip-
R flop is cleared. Which one of the following is the bit
D Q
sequence (including the initial state) generated at the
Clock Q Q output of the JK flip-flop when the flip-flops are
connected to a free-running common clock? Assume
that J = K = 1 is the toggle mode and J = K = 0 is the
7. If all the flip-flops were reset to 0 at power on, what state-holding mode of the JK flip-flop. Both the flip-
is the total number of distinct outputs (states) repre- flops have non-zero propagation delays.[2015]
sented by PQR generated by the counter?[2011] (A) 0110110… (B) 0100100…
(A) 3 (B) 4 (C) 011101110… (D) 011001100…
(C) 5 (D) 6
13. The minimum number of JK flip-flops required to
8. If at some instance prior to the occurrence of the clock construct a synchronous counter with the count
edge, P, Q, and R have a value 0, 1, and 0, respec- sequence (0, 0, 1, 1, 2, 2, 3, 3, 0, 0, …) is ______
tively, what shall be the value of PQR after the clock [2015]
edge?[2011]
14. We want to design a synchronous counter that counts 16. The next state table of a 2-bit saturating up-counter is
the sequence 0-1-0-2-0-3 and then repeats. The mini- given below.
mum number of J-K flip-flops required to implement
this counteris _____ . [2016] Q1 Q0 Q1+ Q0+
0 0 0 1
15. Consider a combination of T and D flip-flops con-
nected as shown below. The output of the D flip-flop 0 1 1 0
is connected to the input of the T flip-flop and the out- 1 0 1 1
put of the T flip-flop is connected to the input of the D 1 1 1 1
flip-flop.
The counter is built as a synchronous sequential cir-
cuit using T flip-flops. The expressions for T1 and
T0are [2017]
Q1 Q0 (A) T1 = Q1Q0, T0 = Q1 Q 0
T
D
Filp-
Filp-
Flop
Flop (B) T1 = Q1Q0, T0 = Q1 + Q 0
(C) T1 = Q1 + Q0, T0 = Q1 + Q 0
Clock
(D) T1 = Q1Q0, T0 = Q1 + Q0
17. Consider the sequential circuit shown in the figure,
Initially, both Q0 and Q1 are set to 1 (before the 1st where both flip-flops used are positive edge-triggered
clock cycle). The outputs [2017] D flip-flops.
(A) Q1 Q0 after the 3rd cycle are 11 and after the 4th
cycle are 00 respectively
(B) Q1 Q0 after the 3rd cycle are 11 and after the 4th in out
D Q D Q
(C) Q1 Q0 after the 3rd cycle are 00 and after the 4th Clock
(D) Q1 Q0 after the 3rd cycle are 01 and after the 4th
cycle are 01 respectively The number of states in the state transition diagram of
this circuit that have a transition back to the same state
on some value of “in” is ______. [2018]
Answer Keys
Exercises
Practice Problems 1
1. B 2. A 3. A 4. B 5. C 6. A 7. C 8. A 9. B 10. A
11. C 12. B 13. B 14. C 15. D 16. B 17. A 18. D 19. A 20. C
21. D 22. A
Practice Problems 2
1. D 2. B 3. D 4. B 5. A 6. C 7. C 8. B 9. A 10. B
11. C 12. B 13. C 14. B 15. B 16. D 17. C 18. C 19. C 20. D
21. C 22. A 23. D 24. B 25. C 26. A 27. A 28. C 29. C 30. A

1. D 2. C 3. C 4. C 5. A 6. A 7. B 8. D 9. C 10. C
11. D 12. A 13. 3(8 = 23) 14. 3 15. B 16. B 17. 2

1. DLD

Uploaded by

Copyright:

Available Formats

1. DLD

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

1. DLD

Uploaded by

Copyright:

Available Formats

Chapter 1

 Digital circuits  Numeric codes

DiGital CirCuits Example 5: (658)8 = 6 × 82 + 5 × 81 + 8 × 80

Table 1 (Continued ) Example 9: (105.75)10

Octal to decimal conversion 0.675 × 16 10.8

Example 19: (10010111011.1011)2 + (14 × 16–2) + (11 × 16–3)

A = 1100 → 1100 Other notation for representation of signed numbers is

Solution: X = 00110 If it is in 1’s complement/2’s complement form, then the

Weighted Non- Self- Sequential Error detecting Cyclic Reflecting

ASCII EBCDIC Hollerith

Binary BCD 2421 5211 Excess 3 Parity Hamming

Numeric Codes Reflective codes

BCD addition Excess-3 (XS-3) code

Practice Problems 2 6. Signed 2’s complement representation of (–15)10 is

2. (2326)8 is equivalent to 8. The equivalent of (25)6 in number system with base 7

Previous Years’ Questions

Previous Years’ Questions

 Logic gates  K-map method

logic gates Table 2 Truth Table

Now, f ( A, B, C ) = ABC + ABC + ABC + ABC + ABC , after m0 m1 m3 m2

Minimization of Boolean Functions 01 4 5 7 6

Pairs, Quads and Octets Octet

F = QS P RS + PQR + PQR + PRS is minimized function.

The group of adjacent min terms is called a Prime Implicant,

Prime implicants are B C , BC , C , A B. Minimized function

Essential Prime Implicant

Redundant Prime Implicant f1

f = 1 quad + 2 pairs A A · B = A + B OR gate

f will consists of 3 quads + 1pair B · AB

Figure 10 Implementation of basic gates by using NOR gates

Any function which is in the SOP form can be imple- B

So four NAND gates are required. C

B Three two-input NAND gates are required.

A Example 20: For the logic circuit shown in figure, the

Example 4: Simplify the Boolean function A ⊕ A B ⊕ A

So the output of above circuit is ‘0’. As two inputs are same x0

Example 3: The circuit shown in the figure is functionally

Solution: Example 8: Simplify the following function

(A) error, error 13. The Boolean expression for P is

9. For the given combinational network with three inputs Y

(A) wx (B) z (C) ( A + B ) ⋅ ( A + B + C )

(C) w ( z + z ) + zw (D) wx + z (D) None of these

17. The point P in the figure is stuck at 1. The output f will be

(A) ABC (B) A (C) ABC (D) A

Practice Problems 2 (A) w = z , x = y (B) = w z= ,x z

f(w, x, y, z) = Sm(0, 1, 2, 3, 8, 9, 10, 11)

(A) ( A + B) ( A + C ) ( B + C ) = ( A + B) ( A + C ) (C) logic 0 voltage level is lower than logic 1 voltage

Previous Years’ Questions

(A) xy + x′y′ (B) x ⊕ y′ Consider the following two statements.

Previous Years’ Questions

 Combinational logic design  Code converter

introduCtion aritHMetiC CirCuits

Inputs Combinational Outputs Half Adder

C Figure 1 Block diagram

S = ABCin + ABCin + AB Cin + ABCin

S = A ⋅ B + AB Figure 2 Block diagram of full adder by using Half adder

NOR logic nor logic

Figure 8 1-bit comparator will have only 1 bit input a, b.

For 16 combinations (A = B) = 1, and for 120 combina- Decimal B2 B1 B0 G2 G1 G0

In general for n-bit gray to binary code conversion Y0

(A) ( A + B) ( A + C ) ( B + C ) = ( A + B) ( A + C ) (C) logic 0 voltage level is lower than logic 1 voltage

Step III: Select the type of flip-flop to be used and write the 1