Digital-Logic-Design

Question 1

In 16-bit 2's complement representation, the decimal number -28 is:

A
1111 1111 1110 0100
B
1111 1111 0001 1100
C
0000 0000 1110 0100
D
1000 0000 1110 0100
       Digital-Logic-Design       Number-Systems       GATE 2019       Video-Explanation
Question 1 Explanation: 
+28 = 0000 0000 0001 1100

1’s complement = 1111 1111 1110 0011
2’s complement = 1’s complement + 1

2’s complement = 1111 1111 1110 0100 = (-28)
Question 2

Two numbers are chosen independently and uniformly at random from the set {1, 2, ..., 13}. The probability (rounded off to 3 decimal places) that their 4-bit (unsigned) binary representations have the same most significant bit is ______.

A
0.502
B
0.461
C
0.402
D
0.561
       Digital-Logic-Design       Number-Systems       GATE 2019       Video-Explanation
Question 2 Explanation: 
Correct answer is 0.502
1 - 0001
2 - 0010
3 - 0011
4 - 0100
5 - 0101
6 - 0110
7 - 0111
8 - 1000
9 - 1001
10 - 1010
11 - 1011
12 - 1100
13 - 1101
The probability that their 4-bit binary representations have the same most significant bit is
= P(MSB is 0) + P(MSB is 1)
= (7×7)/(13×13) + (6×6)/(13×13)
= (49+36)/169
= 85/169
= 0.502
Question 3

Consider Z = X - Y, where X, Y and Z are all in sign-magnitude form. X and Y are each represented in n bits. To avoid overflow, the representation of Z would require a minimum of:

A
n bits
B
n + 2 bits
C
n - 1 bits
D
n + 1 bits
       Digital-Logic-Design       Number-Systems       GATE 2019
Question 3 Explanation: 
In case of addition of two numbers with the same sign, there is a chance of overflow.
To store overflow/carry bit there should be extra space to accommodate it.
Hence, Z should be n+1 bits.
Question 4

Which one of the following is NOT a valid identity?

A
(x + y) ⊕ z = x ⊕ (y + z)
B
(x ⊕ y) ⊕ z = x ⊕ (y ⊕ z)
C
x ⊕ y = x + y, if xy = 0
D
x ⊕ y = (xy + x'y')'
       Digital-Logic-Design       Boolean-Expression       GATE 2019       Video-Explanation
Question 4 Explanation: 
Let x=1, y=1, z=0.
(x+y) ⊕ z = (1+1)⊕ 0 = 1 ⊕ 0 = 1
x ⊕ (y+z) = 1⊕(1+0) = 1 ⊕ 1 = 0
So,
(x+y) ⊕ z ≠ x ⊕ (y+z)
Question 5

What is the minimum number of 2-input NOR gates required to implement a 4-variable function function expressed in sum-of-minterms form as f = Σ(0, 2, 5, 7, 8, 10, 13, 15)? Assume that all the inputs and their complements are available.

A
2
B
4
C
7
D
1
E
3(Option not given)
       Digital-Logic-Design       Logic-Gates       GATE 2019       Video-Explanation
Question 5 Explanation: 
f = Σ(0, 2, 5, 7, 8, 10, 13, 15)

Question 6

Consider three 4-variable functions f1, f2 and f3, which are expressed in sum-of-minterms as

f1 = Σ(0, 2, 5, 8, 14),  f2 = Σ(2, 3, 6, 8, 14, 15),  f3 = Σ(2, 7, 11, 14)

For the following circuit with one AND gate and one XOR gate, the output function f can be expressed as:

A
Σ (2, 14)
B
Σ (7, 8, 11)
C
Σ (2, 7, 8, 11, 14)
D
Σ (0, 2, 3, 5, 6, 7, 8, 11, 14, 15)
       Digital-Logic-Design       Logic-Gates       GATE 2019       Video-Explanation
Question 6 Explanation: 
f1*f2 = ∑(2,8,14)
f3 = ∑(2,7,11,14)
f1*f2 ⊕ f3 = ∑(2,8,14) ⊕ ∑(2,7,11,14)
= ∑(8,7,11)
(Note: Choose the terms which are not common)
Question 7

Let ⊕ and ⊙ denote the Exclusive OR and Exclusive NOR operations, respectively. Which one of the following is NOT CORRECT?

A
B
C
D
       Digital-Logic-Design       Logic-Gates       GATE 2018       Video-Explanation
Question 7 Explanation: 
Question 8

Consider the sequential circuit shown in the figure, where both flip-flops used are positive edge-triggered D flip-flops.

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 ______

A
2
B
3
C
4
D
5
       Digital-Logic-Design       Sequential-Circuits       GATE 2018       Video-Explanation
Question 8 Explanation: 
Let,

Now lets draw characteristic table,
D1 = Q0
D0 = in
Question 9

Consider the unsigned 8-bit fixed point binary number representation below,

    • b
7
    • b
6
    • b
5
    • b
4
    • b
3
    •  ⋅ b
2
    • b
1
    • b
0

where the position of the binary point is between b3 and b2 . Assume b7 is the most significant bit. Some of the decimal numbers listed below cannot be represented exactly in the above representation:

    (i) 31.500    (ii) 0.875    (iii) 12.100    (iv) 3.001

Which one of the following statements is true?

A
None of (i), (ii), (iii), (iv) can be exactly represented
B
Only (ii) cannot be exactly represented
C
Only (iii) and (iv) cannot be exactly represented
D
Only (i) and (ii) cannot be exactly represented
       Digital-Logic-Design       Number-Systems       GATE 2018       Video-Explanation
Question 9 Explanation: 
(i) (31.5)10 = (11111.100)2 = 24 + 23 + 22 + 21 + 20 + 2-1
= 16 + 8 + 4 + 2 + 1 + 0.5
= (31.5)10
(ii) (0.875)10 = (00000.111)2
= 2-1 + 2-2 + 2-3
= 0.5 + 0.25 + 0.125
= (0.875)10
(iii) (12.100)10
It is not possible to represent (12.100)10
(iv) (3.001)10 It is not possible to represent (3.001)10
Question 10

Consider the minterm list form of a Boolean function F given below.

    F(P, Q, R, S) = Σm(0, 2, 5, 7, 9, 11) + d(3, 8, 10, 12, 14)

Here, m denotes a minterm and d denotes a don’t care term. The number of essential prime implicants of the function F is _______.

A
3
B
4
C
5
       Digital-Logic-Design       K-Map       GATE 2018       Video-Explanation
Question 10 Explanation: 
f = Σ(0, 2, 5, 7, 9, 11) + d(3, 8, 10, 12, 14)

There are 3 prime implicant i.e., P’QS, Q’S’ and PQ’ and all are essential.
Because 0 and 2 are correct by only Q’S’, 5 and 7 are covered by only P’QS and 8 and 9 are covered by only PQ’.
Question 11

The n-bit fixed-point representation of an unsigned real number X uses f bits for the fraction part. Let i = n-f. The range of decimal values for X in this representation is

A
2-f to 2i
B
2-f to (2i - 2-f)
C
0 to 2i
D
0 to (2i - 2-f )
       Digital-Logic-Design       Number-Systems       GATE 2017 [Set-1]       Video-Explanation
Question 11 Explanation: 
Size of the fixed point number → n-bits
Number of bits in fraction part → f-bits
Number of bits in integer part → (n – f) bits

Minimum value:
000…0.000…0 = 0
Maximum value:

= (2 n-f - 1) + (1 - 2 -f
= (2n-f - 2 -f)
= (2i - 2 -f )
Question 12

When two 8-bit numbers A7...A0 and B7...B0 in 2’s complement representation (with A0 and B0 as the least significant bits) are added using a ripple-carry adder, the sum bits obtained are S7...S0 and the carry bits are C7...C0. An overflow is said to have occurred if

A
the carry bit C7 is 1
B
all the carry bits (C7,…,C0) are 1
C
D
       Digital-Logic-Design       Ripple-Carry-Adder       GATE 2017 [Set-1]       Video-Explanation
Question 12 Explanation: 
⇾ Overflow may occur when numbers of same sign are added
i.e., A7 = B7
⇾ Overflow can be detected by checking carry into the sign bits (Cin) and carry out of the sign bits (Cout).
⇾ Overflow occurs iff A7 = B7 and Cin ≠ Cout
These conditions are equivalent to

Consider

Here A7 = B7 = 1 and S7 = 0
This happens only if Cin = 0

Carry out Cout=1 when

Similarly, in case of

Cin=1 and Cout will be 0.
Question 13

Consider the Karnaugh map given below, where X represents “don’t care” and blank represents 0.

Assume for all inputs , the respective complements are also available. The above logic is implemented using 2-input NOR gates only. The minimum number of gates required is _________.

 
A
1
B
2
C
3
D
4
       Digital-Logic-Design       K-Map       GATE 2017 [Set-1]       Video-Explanation
Question 13 Explanation: 
Given K-Map represents the function f(a, b, c, d) = a'c = a'(c')' = (a + c')'
As all variables and their complements are available we can implement the function with only one NOR Gate.
Question 14

Consider a combination of T and D flip-flops connected as shown below. The output of the D flip-flop is connected to the input of the T flip-flop and the output of the T flip-flop is connected to the input of the D flip-flop.

Initially, both Q0 and Q1 are set to 1 (before the 1st clock cycle). The outputs

A
Q1Q0 after the 3rd cycle are 11 and after the 4th cycle are 00 respectively
B
Q1Q0 after the 3rd cycle are 11 and after the 4th cycle are 01 respectively
C
Q1Q0 after the 3rd cycle are 00 and after the 4th cycle are 11 respectively
D
Q1Q0 after the 3rd cycle are 01 and after the 4th cycle are 01 respectively
       Digital-Logic-Design       Sequential-Circuits       GATE 2017 [Set-1]       Video-Explanation
Question 14 Explanation: 

Question 15

The representation of the value of a 16-bit unsigned integer X in hexadecimal number system is BCA9. The representation of the value of X in octal number system is

A
136251
B
736251
C
571247
D
136252
       Digital-Logic-Design       Number-Systems       GATE 2017 [Set-2]       Video-Explanation
Question 15 Explanation: 
X = (BCA9)16
Each hexadecimal digit is equal to a 4-bit binary number. So convert
X = (BCA9)16 to binary

Divide the binary data into groups 3 bits each because each octal digit is represented by 3-bit binary number.
X = (001 011 110 010 101 001)2
Note: Two zeroes added at host significant position to make number bits of a multiple of 3 (16 + 2 = 18)
X = (136251)8
Question 16

Given the following binary number in 32-bit (single precision) IEEE-754 format:

00111110011011010000000000000000

The decimal value closest to this floating-point number is

A
1.45 × 101
B
1.45 × 10-1
C
2.27 × 10-1
D
2.27 × 101
       Digital-Logic-Design       Number-Systems       GATE 2017 [Set-2]       Video-Explanation
Question 16 Explanation: 

For single-precision floating-point representation decimal value is equal to (-1)5 × 1.M × 2(E-127)
S = 0
E = (01111100)2 = (124).
So E – 127 = - 3
1.M = 1.11011010…0
= 20 + 2(-1) + 2(-1) + 2(-4) + 2(-5) + 2(-7)
= 1+0.5+0.25+0.06+0.03+0.007
≈ 1.847
(-1)5 × 1.M × 2(E-127)
= -10 × 1.847 × 2-3
≈ 0.231
≈ 2.3 × 10-1
Question 17

Consider a quadratic equation x2 - 13x + 36 = 0 with coefficients in a base b. The solutions of this equation in the same base b are x = 5 and x = 6. Then b=________.

A
8
B
9
C
10
D
11
       Digital-Logic-Design       Number-Systems       GATE 2017 [Set-2]       Video-Explanation
Question 17 Explanation: 
x2 - 13x + 36 = 0 ⇾(1)
Generally if a, b are roots.
(x - a)(x - b) = 0
x2 - (a + b)x + ab = 0
Given that x=5, x=6 are roots of (1)
So, a + b = 13
ab=36 (with same base ‘b’)
i.e., (5)b + (6)b = (13)b
Convert them into decimal value
5b = 510
610 = 610
13b = b+3
11 = b+3
b = 8
Now check with ab = 36
5b × 6b = 36b
Convert them into decimals
5b × 6b = (b×3) + 610
30 = b × 3 + 6
24 = b × 3
b = 8
∴ The required base = 8
Question 18

If w, x, y, z are Boolean variables, then which one of the following is INCORRECT?

A
wx + w(x + y) + x(x + y) = x + wy
B
C
D
(w + y)(wxy + wyz) = wxy + wyz
       Digital-Logic-Design       Boolean-Expressions       GATE 2017 [Set-2]       Video-Explanation
Question 18 Explanation: 
Option-A:
wx + w(x + y) + x(x + y)
= (wx + wx) + wy + (x + xy)
= wx + wy + x(1 + y)
= wx + wy + x
= (w + 1)x + wy
= x + wy
Option-B:

Option-C:

Option-D:
(w + y)(wxy + wyz) = wxy + wyz + wxy + wyz = wxy + wyz
Question 19

Given f(w,x,y,z) = Σm(0,1,2,3,7,8,10) + Σd(5,6,11,15), where d represents the don’t-care condition in Karnaugh maps. Which of the following is a minimum product-of-sums (POS) form of f(w,x,y,z)?

A
B
C
D
       Digital-Logic-Design       K-Map       GATE 2017 [Set-2]       Video-Explanation
Question 19 Explanation: 
f(w,x,y,z) = Σm(0,1,2,3,7,8,10) + Σd(5,6,11,15)
K-Map for the function f is

Consider maxterms in K-map to represent function in product-of-sums (POS) form
f(w,x,y,z) = (w' + z')(x' + z)
Question 20

Consider a binary code that consists of only four valid code words as given below:

00000, 01011, 10101, 11110

Let the minimum Hamming distance of the code be p and the maximum number of erroneous bits that can be corrected by the code be q. Then the values of p and q are

A
p=3 and q=1
B
p=3 and q=2
C
p=4 and q=1
D
p=4 and q=2
       Digital-Logic-Design       Number-Systems       GATE 2017 [Set-2]       Video-Explanation
Question 20 Explanation: 
Hamming distance of a code is minimum distance between any two code words.
Minimum Distance = p = 3

Error bits that can be corrected = (p-1)/2 = (3-1)/2 = 1
∴ p=3 and q=1
Question 21

The next state table of a 2-bit saturating up-counter is given below.

The counter is built as a synchronous sequential circuit using T flip-flops. The expressions for T1 and T0 are

A
B
C
D
       Digital-Logic-Design       Sequential-Circuits       GATE 2017 [Set-2]       Video-Explanation
Question 21 Explanation: 

By using above excitation table,
Question 22

Consider the Boolean operator with the following properties:

Then x#y is equivalent to

A
B
C
D
       Digital-Logic-Design       Boolean-Algebra       GATE 2016 [Set-1]       Video-Explanation
Question 22 Explanation: 


Ex-OR satisfies all the properties. Hence,
Question 23

The 16-bit 2’s complement representation of an integer is 1111 1111 1111 0101; its decimal representation is __________.

A
-11
B
-12
C
-13
D
-14
       Digital-Logic-Design       Number-Systems       GATE 2016 [Set-1]       Video-Explanation
Question 23 Explanation: 
Given number is 1111 1111 1111 0101.
It is a negative number because MSB is 1.
Magnitude of 1111 1111 1111 0101 is 2’s complement of 1111 1111 1111 0101.
1111 1111 1111 0101
0000 0000 0000 1010 : 1’s Complement
0000 0000 0000 1011 : 2’s complement
= (11)10
Hence, 1111 1111 1111 0101 = -11
Question 24

We want to design a synchronous counter that counts the sequence 0-1-0-2-0-3 and then repeats. The minimum number of J-K flip-flops required to implement this counter is __________.

A
4
B
5
C
6
D
7
       Digital-Logic-Design       Sequential-Circuits       GATE 2016 [Set-1]       Video-Explanation
Question 24 Explanation: 
Given sequence is 0-1-0-2-0-3
There are 3 transitions from 0.
Hence ⌈log23⌉ = 2 bits have to be added to the existing 2 bits to represent 4 unique states.
Question 25

Consider the two cascaded 2-to-1 multiplexers as shown in the figure.

The minimal sum of products form of the output X is

A
B
C
D
       Digital-Logic-Design       Multiplexer       GATE 2016 [Set-1]       Video-Explanation
Question 25 Explanation: 
Output of 1st MUX is

Now
Question 26

Consider a carry lookahead adder for adding two n-bit integers, built using gates of fan-in at most two. The time to perform addition using this adder is __________.

A
Θ(1)
B
Θ(log(n))
C
Θ(√n)
D
Θ(n)
       Digital-Logic-Design       Carry-Look-Ahead-Buffer       GATE 2016 [Set-1]       Video-Explanation
Question 26 Explanation: 
Formula: θ(logk (n))
Where n is number of bits added
and k is fan-in of the gates.
As we are adding n-bit numbers and fan-in is at most 2,
the solution is θ(log2 (n)).
Question 27

Consider an eight-bit ripple-carry adder for computing the sum of A and B, where A and B are integers represented in 2’s complement form. If the decimal value of A is one, the decimal value of B that leads to the longest latency for the sum to stabilize is _________.

A
-1
B
-2
C
-3
D
-4
       Digital-Logic-Design       Adder       GATE 2016 [Set-2]       Video-Explanation
Question 27 Explanation: 
In the question, longest LATENCY means longest DELAY for the sum to get settle.
If we do 2's complement of 1 = 0000 0001, we get -1 = "1111 1111"

So, if B = -1, every carry bit is 1.
Question 28

Let, x1⊕x2⊕x3⊕x4 = 0 where x1, x2, x3, x4 are Boolean variables, and ⊕ is the XOR operator. Which one of the following must always be TRUE?

A
x1x2x3x4 = 0
B
x1x3+x2 = 0
C
D
x1 + x2 + x3 + x4 = 0
       Digital-Logic-Design       Boolean-Algebra       GATE 2016 [Set-2]       Video-Explanation
Question 28 Explanation: 
Given expression is,
x1 ⊕ x2 ⊕ x3 ⊕ x4 = 0 -----(1)
A) x1x2x3 x4 = 0
Put x1 = 1, x2 = 1, x3 = 1, x4 = 1
The given equation will be zero, i.e.,
1 ⊕ 1 ⊕ 1 ⊕ 1 = 0
But,
x1x2x3 x4 ≠ 0
So, false.
B) x1x3 + x2 = 0
Put x1 = 1, x2 = 1, x3 = 0 , x4 = 0
The given equation will be zero, i.e.,
1 ⊕ 1 ⊕ 0 ⊕ 0 = 0
But,
x1x3 + x2 ≠ 0
So, false.
D) x1 + x2 + x3 + x4 = 0
Let x1=1, x2=1, x3=0, x4=0
The given equation will be zero, i.e.,
1 ⊕ 1 ⊕ 0 ⊕ 0 = 0
But,
x1 + x2 + x3 + x4 ≠ 0
So, false.
(i) True.
Question 29

Let X be the number of distinct 16-bit integers in 2’s complement representation. Let Y be the number of distinct 16-bit integers in sign magnitude representation.

Then X-Y is _________.

A
1
B
2
C
3
D
4
       Digital-Logic-Design       Number-Systems       GATE 2016 [Set-2]       Video-Explanation
Question 29 Explanation: 
X = 216
Since range is - 215 to 215 - 1
Y = 216 - 1
Here, +0 and -0 are represented separately.
X - Y = 216 - (216 - 1)
= 1
Question 30

Consider a 4-bit Johnson counter with an initial value of 0000. The counting sequence of this counter is

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
D
0, 8, 12, 14, 15, 7, 3, 1, 0
       Digital-Logic-Design       Sequential-Circuits       GATE 2015 [Set-1]
Question 30 Explanation: 
In a Johnson’s counter LSB is complemented and a circular right shift operation has to be done to get the next state.

The state sequence is 0,8,12,14,15,7,3,1,0.
Question 31

The binary operator ≠ is defined by the following truth table

Which one of the following is true about the binary operator ≠?

A
Both commutative and associative
B
Commutative but not associative
C
Not commutative but associative
D
Neither commutative nor associative
       Digital-Logic-Design       Truth Table and Boolean Expressions       GATE 2015 [Set-1]
Question 31 Explanation: 
It is clear that from the truth table, the binary operation # is equivalent to XOR i.e., ⊕, which satisfies both commutative and associative i.e., p#q q#p and p#(q#r) (p#q)#r.
Question 32

A positive edge-triggered D flip-flop is connected to a positive edge-triggered JK flipflop as follows. The Q output of the D flip-flop is connected to both the J and K inputs of the JK flip-flop, while the Q output of the JK flip-flop is connected to the input 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-flop is cleared. Which one of the following is the bit sequence (including the initial state) generated at the 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 state-holding mode of the JK flip-flop. Both the flip-flops have non-zero propagation delays.

A
0110110...
B
0100100...
C
011101110...
D
011001100...
       Digital-Logic-Design       Sequential-Circuits       GATE 2015 [Set-1]
Question 32 Explanation: 
The circuit for the given data is

The characteristic equations are
QDN=D=QJK

The state table and state transition diagram are as follows:

Consider QDQJK=10 as initial state because in the options QJK=0 is the initial state of JK flip-flop.
The state sequence is

0 → 1 → 1 → 0 → 1 → 1
∴ Option (a) is the answer.
Question 33

The minimum number of JK flip-flops required to construct a synchronous counter with the count sequence (0, 0, 1, 1, 2, 2, 3, 3, 0, 0,……) is ___________.

A
2
B
3
C
4
D
5
       Digital-Logic-Design       Sequential-Circuits       GATE 2015 [Set-2]
Question 33 Explanation: 
Count sequence mentioned is
00
00
01
01
10
10
11
11
In the above sequence two flip-flop's will not be sufficient. Since we are confronted with repeated sequence, we may add another bit to the above sequence.
000
100
001
101
010
110
011
111
Now and every count is unique, occurring only once.
So finally 3-flip flops is required.
Question 34

The number of min-terms after minimizing the following Boolean expression is ______.

      [D′ + AB′ + A′C + AC′D + A′C′D]′    
A
1
B
2
C
3
D
4
       Digital-Logic-Design       Boolean-Algebra       GATE 2015 [Set-2]
Question 34 Explanation: 
Lets simplify it
[D' + AB' + A'C + AC'D + A'C'D]'
[D' + AB' + A'C + C'D (A + A')']' (since A+A' = 1)
[AB' + A'C + (D' + C') (D' + D)]' (since D' + D =1)
[AB' + A'C + D' + C']'
[AB' + (A' + C') (C + C') + D']'
[AB' + A' + C' + D']'
[(A + A') (A' + B') + C' + D']'
[A' + B' + C' + D']'
Apply de-morgan's law,
ABCD
Question 35

A half adder is implemented with XOR and AND gates. A full adder is implemented with two half adders and one OR gate. The propagation delay of an XOR gate is twice that of an AND/OR gate. The propagation delay of an AND/OR gate is 1.2 microseconds. A 4-bit ripple-carry binary adder is implemented by using four full adders. The total propagation time of this 4-bit binary adder in microseconds is ____________.

A
19.1
B
19.2
C
18.1
D
18.2
       Digital-Logic-Design       Adder       GATE 2015 [Set-2]
Question 35 Explanation: 

Here, each Full Adder is taking 4.8 microseconds. Given adder is a 4 Bit Ripple Carry Adder. So it takes 4*4.8 = 19.2 microseconds.
Question 36

The total number of prime implicants of the function f(w,x,y,z) = Σ(0, 2, 4, 5, 6, 10) is ______.

A
3
B
4
C
2
D
1
       Digital-Logic-Design       K-Map       GATE 2015 [Set-3]
Question 36 Explanation: 

Total 3 prime implicants are there.
Question 37

Consider the following Boolean expression for F:

   F(P, Q, R, S) = PQ + P'QR + P'QR'S

The minimal sum-of-products form of F is

A
B
C
D
       Digital-Logic-Design       Boolean-Algebra       GATE 2014 [Set-1]
Question 37 Explanation: 
PQ + P’QR + P’QR’S
= Q(P+P’R) + P’QR’S
= Q(P+R) + P’QR’S
= QP + QR + P’QR’S
= QP + Q(R + P’R’S)
= QP + Q( R + P’S)
= QP + QR + QP’S
= Q(P+P’S) + QR
= Q(P+S)+ QR
= QP + QS + QR
Question 38

The base (or radix) of the number system such that the following equation holds is_________.

        312/20 = 13.1     
A
5
B
6
C
7
D
8
       Digital-Logic-Design       Number-Systems       GATE 2014 [Set-1]
Question 38 Explanation: 
Let base of the number system is r.
(3r2 + r + 2) / 2r= (r+3+1/r)
(3r2 + r + 2) / 2r= (r2+3r+1) / r
(3r2 + r + 2) = (2r2+6r+2)
r2 -5r = 0
Therefor r = 5
Question 39

Consider a 4-to-1 multiplexer with two select lines S1 and S0, given below

The minimal sum-of-products form of the Boolean expression for the output F of the multiplexer is

A
B
C
D
       Digital-Logic-Design       Multiplexer       GATE 2014 [Set-1]
Question 39 Explanation: 
F(P,Q,R) = P’Q’(0) + P’Q (1) + PQ’(R) + PQ(R’)
= P’Q + PQ’R + PQR’
= Q(P’ + P R’) + PQ’R
= Q(P’ + R’) + PQ’R
= P’Q + QR’ + PQ’R
Question 40

The dual of a Boolean function F(x1, x2, ..., xn, +, ⋅, '), written as FD, is the same expression as that of F with + and ⋅ swapped. F is said to be self-dual if F = FD. The number of self-dual functions with n Boolean variables is

A
2n
B
2(n-1)
C
2(2n )
D
2(2(n-1) )
       Digital-Logic-Design       Self-Dual-Function       GATE 2014 [Set-2]
Question 40 Explanation: 
Number of possible minterms = 2n.
Number of mutually exclusive pairs of minterms = 2n-1.
There are 2 choices for each pair i.e., we can choose one of the two minterms from each pair of minterms for the function.
Therefore number of functions = 2 x 2 x …. 2n-1 times.
= 2(2(n-1))
Question 41

Let k = 2n. A circuit is built by giving the output of an n-bit binary counter as input to an n-to-2n bit decoder. This circuit is equivalent to a

A
k-bit binary up counter.
B
k-bit binary down counter.
C
k-bit ring counter.
D
k-bit Johnson counter.
       Digital-Logic-Design       Sequential-Circuits       GATE 2014 [Set-2]
Question 41 Explanation: 
A ring counter is a circular shift register with only one flip-flop being set at any particular time and all others are cleared.
A n x 2n decoder is a combinational circuit with only one output line has one and all others (2n-1) have zeros.
A n-bit binary Counter produces outputs from 0 to 2n i.e 000...00 to 111...11 and repeats.
The n x 2n Decoder gets the input (000..00 to 111...11 ) from the binary counter and only one output line has one and rest have zeros.
This circuit is equivalent to a 2n - bit ring counter.
Question 42

Consider the equation (123)5 = (x8)y with x and y as unknown. The number of possible solutions is __________.

A
3
B
5
C
6
D
7
       Digital-Logic-Design       Number-Systems       GATE 2014 [Set-2]
Question 42 Explanation: 
First we have to fullfill all the conditios,
(123)5 = (x8)y
In R.H.S. since y is base so y should be greater than x and 8, i.e.,
y > x
y > 8
Now, to solve let's change all the above bases number into base 10 number,
52 × 1 +2 × 5 + 3 = y × x + 8
38 = xy + 8
xy = 30
⇒ yx = 30
So the possible combinations are
(1,30), (2,15), (3,10), (5,6)
But we will reject (5,6) because it violates the condition (y > 8).
So, total solutions possible is 3.
Question 43

Consider the following minterm expression for F:

  F(P,Q,R,S) = Σ0,2,5,7,8,10,13,15  

The minterms 2, 7, 8 and 13 are 'do not care' terms. The minimal sum-of-products form for F is:

A
B
C
D
       Digital-Logic-Design       Number-Systems       GATE 2014 [Set-3]
Question 43 Explanation: 
Question 44

Consider the following combinational function block involving four Boolean variables x, y, a, b where x, a, b are inputs and y is the output.

f (x, y, a, b)
{
   if (x is 1) y = a;
   else y = b;
}

Which one of the following digital logic blocks is the most suitable for implementing this function?

A
Full adder
B
Priority encoder
C
Multiplexor
D
Flip-flop
       Digital-Logic-Design       Boolean-Variables       GATE 2014 [Set-3]
Question 44 Explanation: 
A 2x1 Multiplexer is most suitable for implementing the function.
x is the select line, I0 is 'b' and I1 is a.
The output line, y = xa + x’b
Question 45

The above synchronous sequential circuit built using JK flip-flops is initialized with Q2Q1Q0 = 000. The state sequence for this circuit for the next 3 clock cycles is

A
001, 010, 011
B
111, 110, 101
C
100, 110, 111
D
100, 011, 001
       Digital-Logic-Design       Flip-Flops       GATE 2014 [Set-3]
Question 45 Explanation: 
Question 46

Let ⊕ denote the Exclusive OR (XOR) operation. Let ‘1’ and ‘0’ denote the binary constants. Consider the following Boolean expression for F over two variables P and Q:

     F(P,Q) = ((1⊕P)⊕(P⊕Q))⊕((P⊕Q)⊕(Q⊕0)) 

The equivalent expression for F is

A
P+Q
B
C
P⨁Q
D
       Digital-Logic-Design       Number-Systems       GATE 2014 [Set-3]
Question 46 Explanation: 
((1 ⊕ P) ⊕ (P ⊕ Q)) ⊕ ((P ⊕ Q) ⊕ (Q ⊕ 0))
⊕ is associative i.e P ⊕ (Q ⊕ R) = (P⊕Q) ⊕ R.
P ⊕ P = 0, 1 ⊕ P = P’ and 0 ⊕ Q = Q
(1 ⊕ P) ⊕ ((P ⊕ Q) ⊕ (P ⊕ Q)) ⊕ (Q ⊕ 0)
= P’⊕ (0) ⊕ Q
= P’ ⊕ Q
= (P ⊕ Q)’
Question 47

The smallest integer that can be represented by an 8-bit number in 2’s complement form is

A
-256
B
-128
C
-127
D
0
       Digital-Logic-Design       Number-Systems       GATE 2013
Question 47 Explanation: 
The range of 8-bit signed numbers representable is – 2n-1 to 2n-1 -1.
The smallest 8-bit 2’s complement number is 1000 0000.
MSB is 1. So it is a negative number.
To know the magnitude again take 2’s complement of 1000 0000.
1000 0000
0111 1111 ← 1’s complement
1000 0000 ← 2’s complement (1’s complement +1)
= 128
-128 is 1000 0000 in 2’s complement representation.
Question 48

In the following truth table, V = 1 if and only if the input is valid.

What function does the truth table represent?

A
Priority encoder
B
Decoder
C
Multiplexer
D
Demultiplexer
       Digital-Logic-Design       Combinational-Circuits       GATE 2013
Question 48 Explanation: 
It is a 22 × 2 encoder. The inputs have priorities. So, it is a priority encoder.
Question 49

Which one of the following expressions does NOT represent exclusive NOR of x and y?

A
xy+x'y'
B
x⊕y'
C
x'⊕y
D
x'⊕y'
       Digital-Logic-Design       Number-Systems       GATE 2013
Question 49 Explanation: 
x ⊕ y = x’y + xy’
x’ ⊕ y’ = xy’ + x’y = x⊕y. Hence option D is correct.
Question 50

The truth table

represents the Boolean function

A
X
B
X + Y
C
X ⊕ Y
D
Y
       Digital-Logic-Design       Boolean-Algebra       GATE 2012
Question 50 Explanation: 
f(X,Y) = XY’ + XY = X(Y’ + Y) = X
Question 51

The decimal value 0.5 in IEEE single precision floating point representation has

A
fraction bits of 000…000 and exponent value of 0
B
fraction bits of 000…000 and exponent value of −1
C
fraction bits of 100…000 and exponent value of 0
D
no exact representation
       Digital-Logic-Design       Number-Systems       GATE 2012
Question 51 Explanation: 
(0.5)10 = (1.0)2 × 2–1
So, value of the exponent = -1
and
fraction is 000…000 (Implicit representation)
Question 52

The amount of ROM needed to implement a 4 bit multiplier is

A
64 bits
B
128 bits
C
1 Kbits
D
2 Kbits
       Digital-Logic-Design       Combinational-Circuits       GATE 2012
Question 52 Explanation: 
To implement a 4-bit multiplier we need to store all the possible combinations of 24 x 24 inputs and their corresponding 8 output bits. The total ROM size needed = 28 x 8 bits = 211 bits = 2 Kbits.
Hence option D is the answer.
Question 53

What is the minimal form of the karnaugh map shown below? Assume that X denotes a don't care term

A
B
C
D
       Digital-Logic-Design       K-Map       GATE 2012
Question 53 Explanation: 
Question 54

The simplified SOP (sum of product) form of the boolean expression

 
A
B
C
D
       Digital-Logic-Design       Boolean-Algebra       GATE 2011
Question 54 Explanation: 
Question 55

The minimum number of D flip-flops needed to design a mod-258 counter is

A
9
B
8
C
512
D
258
       Digital-Logic-Design       Sequential-Circuits       GATE 2011
Question 55 Explanation: 
Let n is the number of flip-flops.
The max Mod values is 2n.
So 2n ≥ 258 ⇒ n = 9
Question 56

Which one of the following circuits is NOT equivalent to a 2-input XNOR (exclusive NOR) gate?

A
B
C
D
       Digital-Logic-Design       Logic-Gates       GATE 2011
Question 56 Explanation: 
All options except option ‘D’ gives EX-NOR gates.
Question 57

Consider the following circuit involving three D-type flip-flops used in a certain type of counter configuration.

If all the flip-flops were reset to O at power on, what is the total number of distinct outputs *states) represented by PQR generated by the counter?

A
3
B
4
C
5
D
6
       Digital-Logic-Design       Sequential-Circuits       GATE 2011
Question 57 Explanation: 

So total no. of distinct output (states) are 4.
Question 58

Consider the following circuit involving three D-type flip-flops used in a certain type of counter configuration.

If at some instance prior to the occurrence of the clock edge, P, Q and R have a value 0, 1 and 0 respectively, what shall be the value of PQR after the clock edge?

A
000
B
001
C
010
D
011
       Digital-Logic-Design       Sequential-Circuits       GATE 2011
Question 58 Explanation: 

So, after 010 it moves to 011.
Question 59

The minterm expansion of is

A
m2+m4+m6+m7
B
m0+m1+m3+m5
C
m0+m1+m6+m7
D
m2+m3+m4+m5
       Digital-Logic-Design       Boolean-Algebra       GATE 2010
Question 59 Explanation: 
Convert PQ + QR' + PR' into canonical form
= PQR + PQR' + PQR' + P'QR' + PQR' + PQ'R'
= PQR + PQR' + P'QR' + PQ'R'
= m7 + m6 + m2 + m4
Question 60

A main memory unit with a capacity of 4 megabytes is built using 1M 1-bit DRAM chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The time taken for a single refresh operation is 100 nanoseconds. The time required to perform one refresh operation on all the cells in the memory unit is

A
100 nanoseconds
B
100*210 nanoseconds
C
100*220 nanoseconds
D
3200*220 nanoseconds
       Digital-Logic-Design       Memory-Interfacing       GATE 2010
Question 60 Explanation: 
Each chip capacity = 1M x 1-bit
Required capacity = 4MB
Number of chips needed = 4M*8 bits / 1M x 1-bit = 32 (1M x 1-bit)/(1M x 1-bit) = 32
Irrespective of the number of chips, all chips can be refreshed in parallel.
And all the cells in a row are refreshed in parallel too. So, the total time for refresh will be number of rows times the refresh time of one row.
Here we have 1K rows in a chip and refresh time of single row is 100ns.
So total time required = 1K × 100
= 100 × 210 nanoseconds
Question 61

P is a 16-bit signed integer. The 2's complement representation of P is (F87B)16. The 2's complement representation of 8*P is

A
(C3D8)16
B
(187B)16
C
(F878)16
D
(987B)16
       Digital-Logic-Design       Number-Systems       GATE 2010
Question 61 Explanation: 
(F87B)16 is 2's complement representation of P.
(F87B)16=(1111 1000 0111 1011)2. (It is a negative number which is in 2's complement form)
P = 1111 1000 0111 1011 (2's complement form)
8 * P = 23* P = 1100 0011 1101 1000. ( NOTE: Left shift k times is equivalent to Multiplication by 2k)
Hence, 1100 0011 1101 1000 is 2's complement representation of 8P.
1100 0011 1101 1000 = (C3D8)16.
Question 62

The Boolean expression for the output 'f' of the multiplexer shown below is

 
A
B
P⊕Q⊕R
C
P+Q+R
D
       Digital-Logic-Design       Multiplexer       GATE 2010
Question 62 Explanation: 
f = P’Q’ R + P’Q R’ + PQ’ R’ + PQR
= (P’Q’ + PQ)R + (P’Q+PQ’)R’
= (P⊕Q)’R + (P⊕Q)R’
= (P⊕Q⊕R)
Question 63

What is the Boolean expression for the output f of the combinational logic circuit of NOR gates given below?

A
B
C
D
       Digital-Logic-Design       Logic-Gates       GATE 2010
Question 63 Explanation: 
f = ((P’Q’ + Q’R’)’ + ( P’R’ + Q’R’)’ )’
= (P’Q’ + Q’R’)( P’R’ + Q’R’)
= (P’Q’P’R’ + P’Q’Q’R’ + Q’R’P’R’ + Q’R’Q’R’)
= (P’Q’R’ + P’Q’R’ + P’Q’R’ + Q’R’)
= (P’Q’R’ + Q’R’)
= (Q’R’)
= (Q+R)’
Question 64

In the sequential circuit shown below,if the initial value of the output Q1Q0 is 00,what are the next four values of Q1Q0?

A
11, 10, 01, 00
B
10, 11, 01, 00
C
10, 00, 01, 11
D
11, 10, 00, 01
       Digital-Logic-Design       Sequential-Circuits       GATE 2010
Question 64 Explanation: 

The next four values of Q1Q0 are 11, 10, 01, 00.
Question 65

(1217)8 is equivalent to

A
(1217)16
B
(028F)16
C
(2297)10
D
(0B17)16
       Digital-Logic-Design       Number-Systems       GATE 2009
Question 65 Explanation: 
(1217)8 = (001 010 001 111)2
Divide the bits into groups, each containing 4 bits.
= (0010 1000 1111)2
= (28F)16
Question 66

What is the minimum number of gates required to implement the Boolean function (AB+C) if we have to use only 2-input NOR gates?

A
2
B
3
C
4
D
5
       Digital-Logic-Design       Logic-Gates       GATE 2009
Question 66 Explanation: 
NOR is Complement of OR
AB+C
= (A+C)(B+C) ← Distribution of + over
= ((A+C)’+(B+C)’)’
1st NOR- (A+C)’. Let X = (A+C)’
2nd NOR- (B+C)’. Let Y = (B+C)’
3rd NOR- (X+Y)’
Question 67

How many 32K × 1 RAM chips are needed to provide a memory capacity of 256K-bytes?

A
8
B
32
C
64
D
128
       Digital-Logic-Design       Memory-Interfacing       GATE 2009
Question 67 Explanation: 
Each chip capacity = 32K × 1- bit
Needed memory capacity = 256K - bytes = 256K*8 bits
Number of chips needed = 256K*8 / 32K×1 = 64
Question 68

In the IEEE floating point representation, the hexadecimal value 0×00000000 corresponds to

A
the normalized value 2 - 127
B
the normalized value 2 - 126
C
the normalized value + 0
D
the special value + 0
       Digital-Logic-Design       Number-Systems       GATE 2008
Question 68 Explanation: 
Value is ±0 if M=0 and E=0.
Question 69

In the Karnaugh map shown below, X denotes a don’t care term. What is the minimal form of the function represented by the Karnaugh map?

 
A
B
C
D
       Digital-Logic-Design       K-Map       GATE 2008
Question 69 Explanation: 
Question 70

Let r denote number system radix. The only value(s) of r that satisfy the equation is/are

A
decimal 10
B
decimal 11
C
decimal 10 and 11
D
any value > 2
       Digital-Logic-Design       Number-Systems       GATE 2008
Question 70 Explanation: 
√121r = 11r
(r2 + 2r + 1)1/2 = r + 1
(r + 1)2 * 1/2 = r + 1
r + 1 = r + 1 Any value of r will satisfy the above equation. But the radix should be greater than 2 because the 121 has 2. So r > 2 is correct.
Question 71

If P, Q, R are Boolean variables, then

Simplifies to

A
B
C
D
       Digital-Logic-Design       Boolean-Algebra       GATE 2008
Question 71 Explanation: 
Question 72

What is the maximum number of different Boolean functions involving n Boolean variables?

A
n2
B
2n
C
22n
D
2n2
       Digital-Logic-Design       Boolean-Algebra       GATE 2007
Question 72 Explanation: 
Each “boolean” variable has two possible values i.e 0 and 1.
Number of variables= n
Number of input combinations is 2n.
Each “boolean” function has two possible outputs i.e 0 and 1.
Number of boolean functions possible is 22n.
Formula: The number of m-ary functions possible with n k-ary variables is mkn.
Question 73

How many 3-to-8 line decoders with an enable input are needed to construct a 6-to-64 line decoder without using any other logic gates?

A
7
B
8
C
9
D
10
       Digital-Logic-Design       Decoder       GATE 2007
Question 73 Explanation: 
Each 3-to-8 lines decoder has 8 output lines.
So, we can say that
8 lines covered by ----- 1 decoder
1 line covered by ----- 1/8 decoder
64 lines covered by ----- 64/8 = 8 decoders
8 lines covered by ----- 8/8 = 1 decoder
Hence total no. of decoder needed is,
8 + 1 = 9 decoders.
Question 74

Consider the following Boolean function of four variables:

f(w,x,y,z) = ∑(1,3,4,6,9,11,12,14)

The function is:

A
independent of one variable.
B
independent of two variables.
C
independent of three variables.
D
dependent on all the variables.
       Digital-Logic-Design       Boolean-Variables       GATE 2007
Question 74 Explanation: 

w and y are not needed to represent the function f. So f is independent of two variables.
Question 75

Let f(w, x, y, z) = ∑(0, 4, 5, 7, 8, 9, 13, 15). Which of the following expressions are NOT equivalent to f?

    (P) x'y'z' + w'xy' + wy'z + xz
    (Q) w'y'z' + wx'y' + xz
    (R) w'y'z' + wx'y' + xyz + xy'z
    (S) x'y'z' + wx'y' + w'y
A
P only
B
Q and S
C
R and S
D
S only
       Digital-Logic-Design       Boolean-Expressions       GATE 2007
Question 75 Explanation: 

(P), (Q), (R) cover all the minterms and are equivalent to f(w,x,y,z) = Σ(0,4,5,7,8,9,13,15).
(S) covers the minterms m0, m8, m9, m2, m3, m6, m7.
(S) is not covering the minterms m4, m5, m13, m15.
Question 76

Define the connective * for the Boolean variables X and Y as: X * Y = XY + X'Y'. Let Z = X * Y.

Consider the following expressions P, Q and R.

P: X = Y⋆Z 
Q: Y = X⋆Z 
R: X⋆Y⋆Z = 1

Which of the following is TRUE?

A
Only P and Q are valid.
B
Only Q and R are valid.
C
Only P and R are valid.
D
All P, Q, R are valid.
       Digital-Logic-Design       Boolean-Expressions       GATE 2007
Question 76 Explanation: 
P: Y*Z = YZ + Y’Z’
= Y(XY + X’Y’) + Y’(XY+X’Y’)’
= XY+Y’(X ⊕ Y)
= XY+Y’(XY’+X’Y)
= XY+XY’
= X(Y+Y’) = X
Q: X*Z = (XZ + X’Z’)
= X(XY + X’Y’) + X’(XY + X’Y’)’
= XY+X’(X’Y+XY’)
= XY+X’Y
= (X+X’)Y = Y
R: X* Y*Z
= X*X Since P: Y*Z= X
= XX + X’X’
= 1
Question 77

Suppose only one multiplexer and one inverter are allowed to be used to implement any Boolean function of n variables. What is the minimum size of the multiplexer needed?

A
2n line to 1 line
B
2n+1 line to 1 line
C
2n-1 line to 1 line
D
2n-2 line to 1 line
       Digital-Logic-Design       Multiplexer       GATE 2007
Question 77 Explanation: 
Both true and complement forms of all variables are necessary to implement any function of n variables.
A 2n X 1 multiplexer can implement any function of n variables. As n variables are given to select lines, so that true and complement forms of all variables get generated inside the MUX.
As one inverter is available, we can generate complement of one variable outside of the Multiplexer. And remaining (n-1) variables are given to select lines. With this we have true and complement form of all n variables.
So, the answer is 2n-1 X 1 MUX.
Question 78

In a look-ahead carry generator, the carry generate function Gi and the carry propagate function Pi for inputs Ai and Bi are given by:

Pi = Ai ⨁ Bi and Gi = AiBi

The expressions for the sum bit Si and the carry bit Ci+1 of the look-ahead carry adder are given by:

Si = Pi ⨁ Ci and Ci+1 = Gi + PiCi , where C0 is the input carry.

Consider a two-level logic implementation of the look-ahead carry generator. Assume that all Pi and Gi are available for the carry generator circuit and that the AND and OR gates can have any number of inputs. The number of AND gates and OR gates needed to implement the look-ahead carry generator for a 4-bit adder with S3, S2, S1, S0 and C4 as its outputs are respectively:

A
6, 3
B
10, 4
C
6, 4
D
10, 5
       Digital-Logic-Design       Carry-Look-Ahead-Adder       GATE 2007
Question 78 Explanation: 
Formula: n(n+1)/2 AND gates and n OR gates are needed for an n-bit carry look ahead circuit for addition of two binary numbers.
Question 79

The control signal functions of a 4-bit binary counter are given below (where X is “don’t care”) The counter is connected as follows:

The counter is connected as follows:

Assume that the counter and gate delays are negligible. If the counter starts at 0, then it cycles through the following sequence:

A
0, 3, 4
B
0, 3, 4, 5
C
0, 1, 2, 3, 4
D
0, 1, 2, 3, 4, 5
       Digital-Logic-Design       Circuits-Output       GATE 2007
Question 79 Explanation: 
A counter goes through a sequence of states. Given counter resets when A1 = A3 = 1.
Here, initial state is 0000. It goes through 0001,0010,0011,0100 and 0101. When the state is 5(0101) it immediately resets to initial state 0. Here, state 5 is not considered as valid state.
So valid states are 0,1,2,3, and 4 and hence it is a Mod5 counter.
Question 80

Which of the following is TRUE about formulae in Conjunctive Normal Form?

A
For any formula, there is a truth assignment for which at least half the clauses evaluate to true.
B
For any formula, there is a truth assignment for which all the clauses evaluate to true.
C
There is a formula such that for each truth assignment, at most one-fourth of the clauses evaluate to true.
D
None of the above.
       Digital-Logic-Design       Conjunctive-Normal-Form       GATE 2007
Question 80 Explanation: 
For n=2, (means two variables a and b)
Formula: a ∧ b
Truth table:

Conjunctive normal form : (a ∨ b) ∧ (a ∨ ~b) ∧ (~a ∨ b)

Similarly,
For n=1-----TRUE=1, FALSE=1 (1/2 ARE TRUE)
For n=2-----TRUE=3, FALSE=1 (3/4 ARE TRUE)
For n=3-----TRUE=7, FALSE=1 (7/8 ARE TRUE)
(1-2-n) are TRUE.
Looking at options,
Question 81

You are given a free running clock with a duty cycle of 50% and a digital waveform f  which changes only at the negative edge of the clock. Which one of the following circuits (using clocked D flip-flops) will delay the phase of f  by 180°?

A
B
C
D
       Digital-Logic-Design       Sequential-Circuits       GATE 2006
Question 81 Explanation: 
Duty cycle is the period of time where the signal high, i.e. 1.
50% of duty cycle means, the wave is 1 for half of the time and 0 for the other half of the time. It is a usual digital signal with 1 and 0.
The waveform f changes for every negative edge, that means f value alters from 1 to 0 or 0 to 1 for every negative edge of the clock.
Now the problem is that we need to find the circuit which produces a phase shift of 180, which means the output is 0 when f is 1 and output is 1 when f is 0.
Like the below image.

Now to find the answer we can choose elimination method.
F changes for negative edge, so that output too should change at negative edge. i.e if f becomes 0, then at the same time output should become 1, vice versa.
So, whenever input changes, at the same point of time output too should change. As input changes on negative edge, the output should be changed at negative edge only.
To have the above behaviour, the second D flip-flop which produces the final output should be negative edge triggered. because whatever the 2nd flip-flop produces, that is the output of the complete circuit.
So, we can eliminate option a, d.
Now either b or c can be answer.
How the flip-flop chain works in option b and c is as below.
—> F changes at negative edge.
—> But flip-flop1 responds at next positive edge.
—> After this flip-flop2 responds at next negative edge.
That means flip-flop2 produces the same input which is given to flip-flop now after a positive edge and a negative edge, that means a delay of one clock cycle, which is 180 degrees phase shift for the waveform of f.
Option b) we are giving f’, so that the output is f’ with 180 degrees phase shift.
Option c) we are giving f, so that the output is f with 180 degrees phase shift.
Hence option C is the answer.
Question 82

Consider the circuit above. Which one of the following options correctly represents f(x,y,z)?

A
B
C
D
       Digital-Logic-Design       Multiplexer       GATE 2006
Question 82 Explanation: 
f = yx + y’ (zy’+z’x)
= xy + zy’ + y’z’x
= x(y+y’z’) + zy’
= x(y+z’) + y’z
= xy + xz’ + y’z
Question 83

Given two three bit numbers a2a1a0 and b2b1b0 and c, the carry in, the function that represents the carry generate function when these two numbers are added is:

A
B
C
D
       Digital-Logic-Design       Carry-Generator       GATE 2006
Question 83 Explanation: 
Initial Carry c is not included in any option. Hence c=0.
Carry c1 = a0b0
Carry c2 = a2b2 + c1(a2 ⊕ b2 )
= a1b1 +c1 (a1 b’1+ a’1 b1 )
= a1b1 +c1 a1 b’1+ c1 a’1 b1
= (a1b1 + c1a1 b’1)+ (c1 a’1 b1 + a1b1 )
= a1(b1+c1) +b1 (c1 + a1)
= a1b1+b1c1+a1c1
Carry c3 = a2b2 + c2(a2 ⊕ b2)
= a2b2 + c2(a’2b2 + a2b’2 )
= a2b2 + b2c2 + a2c2
= a2b2+a2a1b1+a2a1a0b0+a2a0b1b0+a1b2b1+a1a0b2b0+a0b2b1b0
Question 84

Consider the circuit in the diagram. The ⊕ operator represents Ex-OR. The D flipflops are initialized to zeroes (cleared).

The following data: 100110000 is supplied to the “data” terminal in nine clock cycles. After that the values of q2q1q0 are:

A
000
B
001
C
010
D
101
       Digital-Logic-Design       Sequential-Circuits       GATE 2006
Question 84 Explanation: 
q0N = Data, q1N = q0q22N = q1
Question 85

Consider a Boolean function f(w,x,y,z). Suppose that exactly one of its inputs is allowed to change at a time. If the function happens to be true for two input vectors i1 = 〈w1, x1, y1, z1〉 and i2 = 〈w2, x2, y2, z2〉, we would like the function to remain true as the input changes from vectors i1 to i2 (i1 and i2 differ in exactly one bit position), without becoming false momentarily. Let f(w,x,y,z) = ∑(5,7,11,12,13,15). Which of the following cube covers of f will ensure that the required property is satisfied?

A
B
C
D
       Digital-Logic-Design       K-Map       GATE 2006
Question 85 Explanation: 
Static hazard is the situation where, when one input variable changes, the output changes momentarily before stabilizing to the correct value. The most commonly used method to eliminate static hazards is to add redundant logic (consensus terms in the logic expression).
f = X1 * X2 + X1' * X3
If (X1, X2, X3) = (1,1,1) then f=1 because X1 * X2 =1 X1' * X3 = 0.
Let the input is changed from 111 to 011 , then f = 1 because X1 * X2 = 0 X1' * X3 =1.
The output f will be momentarily 0 if AND gate X1 * X2 is faster than the AND gate X1' * X3.
This Hazard can be avoided by adding the term X2 * X3 (because X1 is in true form in first term and in complement form in the second term . So pick the fixed terms X2 and X3 from both terms) to f i.e f = X1 * X2 + X1' * X3 + X2 * X3
Option D is equivalent to f(w, x, y, z) = ∑(5,7,11,12,13,15)
Question 86

We consider the addition of two 2’s complement numbers bn-1bn-2...b0 and an-1an-2…a0. A binary adder for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by cn-1cn-2c0 and the carry-out by cout. Which one of the following options correctly identifies the overflow condition?

A
B
C
D
       Digital-Logic-Design       Carry-Generator       GATE 2006
Question 86 Explanation: 
There is an overflow if
1. The sign bits are same i.e MSB bits are same.
2. Carry_in ≠ Carry_out.
In option B, the MSB are equal.
Question 87

Consider numbers represented in 4-bit gray code. Let h3h2h1h0 be the gray code representation of a number n and let g3g2g1g0 be the gray code of (n+1)(modulo 16) value of the number. Which one of the following functions is correct?

A
g0(h3h2h1h0) = Σ(1,2,3,6,10,13,14,15)
B
g1(h3h2h1h0) = Σ(4,9,10,11,12,13,14,15)
C
g2(h3h2h1h0) = Σ(2,4,5,6,7,12,13,15)
D
g3(h3h2h1h0) = Σ(0,1,6,7,10,11,12,13)
       Digital-Logic-Design       Number-Systems       GATE 2006
Question 87 Explanation: 

g2(h3h2h1h0) = Σ(2,4,5,6,7,12,13,15)
Question 88

Consider the following circuit.

Which one of the following is TRUE?

A
f is independent of X
B
f is independent of Y
C
f is independent of Z
D
None of X, Y, Z is redundant
       Digital-Logic-Design       Circuits-Output       GATE 2005
Question 88 Explanation: 
f(X,Y,Z) = ((XY’)’ (YZ))’
= ((X’+Y) YZ)’
= (X’YZ + YZ)’
= ((X’+1) YZ)’
= (YZ)’
Question 89

The range of integers that can be represented by an n bit 2's complement number system is:

A
- 2n-1 to (2n-1 - 1)
B
- (2n-1 - 1) to (2n-1 - 1)
C
- 2n-1 to 2n-1
D
- (2n-1 + 1) to (2n-1 - 1)
       Digital-Logic-Design       Number-Systems       GATE 2005
Question 89 Explanation: 
The maximum (positive) n bit number is 011….1 (i.e., 0 followed by n-1 ones) which is equal to 2n-1 - 1.
The smallest (negative) n bit number is 100..0 (i.e., 1 followed by n-1 zeros) which is equal to - 2n-1.
1000...00
0111...11 <- 1’s complement
1000..00 <- 2’s complement
= - 2n-1
Question 90

The hexadecimal representation of 6578 is

A
1AF
B
D78
C
D71
D
32F
       Digital-Logic-Design       Number-Systems       GATE 2005
Question 90 Explanation: 
(657)8 = (110 101 111)2
Make 3 zeros on the left side so that the number of bits is multiple of 4.
= (0001 1010 1111)2
= (1 A F)16
Question 91

The switching expression corresponding to f(A, B, C, D) = Σ (1, 4, 5, 9, 11, 12) is:

A
BC'D' + A'C'D + AB'D
B
ABC' + ACD + B'C'D
C
ACD' + A'BC' + AC'D'
D
A'BD + ACD' + BCD'
       Digital-Logic-Design       Minimum-Sum-Of-Product       GATE 2005
Question 91 Explanation: 

f(A,B,C,D) = A'C'D + BC'D' + AB'D
Question 92

Consider the following circuit involving a positive edge triggered D FF.

Consider the following timing diagram. Let Ai represent the logic level on the line A in the i-th clock period.

Let A' represent the complement of A. The correct output sequence on Y over the clock periods 1 through 5 is

A
A0 A1 A1' A3 A4
B
A0 A1 A2' A3 A4
C
A1 A2 A2' A3 A4
D
A1 A2' A3 A4 A5'
       Digital-Logic-Design       Circuits-Output       GATE 2005
Question 92 Explanation: 

Input will be accepted by the flipflop after the cycle gets finished, because +ve edge is occurring at the end of the clock cycle only.
Question 93

Consider the following circuit.

The flip-flops are positive edge triggered D FFs. Each state is designated as a two bit string Q0Q1. Let the initial state be 00. The state transition sequence is:

A
B
C
D
       Digital-Logic-Design       Sequential-Circuits       GATE 2005
Question 93 Explanation: 
Question 94

Consider the following floating point format.

Mantissa is a pure fraction in sign-magnitude form.

The decimal number 0.239 × 213 has the following hexadecimal representation (without normalization and rounding off:

A
0D 24
B
0D 4D
C
4D 0D
D
4D 3D
       Digital-Logic-Design       Number-Systems       GATE 2005
Question 94 Explanation: 
Sign Bit = 0
Convert 0.239 to binary
0.239 * 2 = 0.478
0.478 * 2 = 0.956
0.956 * 2 = 1.912
0.912 * 2 = 1.824
0.824 * 2 = 1.648
0.648 * 2 = 1.296
0.296 * 2 = 0.512
0.512 * 2 = 1.024
Mantissa = (0. 00111101)2
Bias = 64. So biased exponent is 13+64 = 77= (1001101)2
0.239 × 213 = 0 1001101 00111101
= 0100 1101 0011 1101
= 4 D 3 D
Question 95

Consider the following floating point format.

Mantissa is a pure fraction in sign-magnitude form.

The normalized representation for the above format is specified as follows. The mantissa has an implicit 1 preceding the binary (radix) point. Assume that only 0's are padded in while shifting a field. The normalized representation of the above number (0.239 × 213) is

A
0A 20
B
11 34
C
4D D0
D
4A E8
       Digital-Logic-Design       Number-Systems       GATE 2005
Question 95 Explanation: 
Sign Bit = 0
Convert 0.239 to binary
0.239 * 2 = 0.478
0.478 * 2 = 0.956
0.956 * 2 = 1.912
0.912 * 2 = 1.824
0.824 * 2 = 1.648
0.648 * 2 = 1.296
0.296 * 2 = 0.512
0.512 * 2 = 1.024
Mantissa = (0. 00111101)2
0.239 × 213 = 1.11101000 x 210 <- Normalized Mantissa
Bias = 64. So biased exponent is 10+64 = 74 = (1001010)2
0.239 × 213 = 0 1001010 11101000
= 0100 1010 1110 1000
= (4 A E 8)16
Question 96

The Boolean function x'y' + xy + x'y is equivalent to

A
x' + y'
B
x + y
C
x + y'
D
x' + y
       Digital-Logic-Design       Boolean-Algebra       GATE 2004
Question 96 Explanation: 
x'y' + xy + x'y
= x'y' + x'y + xy
= x'(y'+y)+xy
= x'⋅1+xy
= x'+xy
= (x'+x)(x'+y)
= 1⋅(x'+y)
= x'+y
Question 97

In an SR latch made by cross-coupling two NAND gates, if both S and R inputs are set to 0, then it will result in

A
Q = 0, Q' = 1
B
Q = 1, Q' = 0
C
Q = 1, Q' = 1
D
Indeterminate states
       Digital-Logic-Design       Sequential-Circuits       GATE 2004
Question 97 Explanation: 

Truth table for the SR latch by cross coupling two NAND gates is

So, Answer is Option (D).
Question 98

If 73x (in base-x number system) is equal to 54y (in base-y number system), the possible values of x and y are

A
8, 16
B
10, 12
C
9, 13
D
8, 11
       Digital-Logic-Design       Number-Systems       GATE 2004
Question 98 Explanation: 
(73)x = (54)y
7x+3 = 5y+4
7x-5y = 1
Only option (D) satisfies above equation.
Question 99

What is the result of evaluating the following two expressions using three-digit floating point arithmetic with rounding?

   (113. + -111.) + 7.51
   113. + (-111. + 7.51) 
A
9.51 and 10.0 respectively
B
10.0 and 9.51 respectively
C
9.51 and 9.51 respectively
D
10.0 and 10.0 respectively
       Digital-Logic-Design       Number-Systems       GATE 2004
Question 99 Explanation: 
(113. + -111.) + 7.51
= (2) + 7.51
= 9.51 (✔️)
113. + (-111. + 7.51)
= 113. + (-103.51)
= 113. + -103
= 10 (✔️)
Question 100

A circuit outputs a digit in the form of 4 bits. 0 is represented by 0000, 1 by 0001, ..., 9 by 1001. A combinational circuit is to be designed which takes these 4 bits as input and outputs 1 if the digit ≥ 5, and 0 otherwise. If only AND, OR and NOT gates may be used, what is the minimum number of gates required?

A
2
B
3
C
4
D
5
       Digital-Logic-Design       Combinational-Circuits       GATE 2004
Question 100 Explanation: 

= A + BD + BC
= A + B (D + C)
So minimum two OR gates and 1 AND gate is required. Hence, in total minimum 3 gates is required.
Question 101

Which are the essential prime implicants of the following Boolean function?

 f(a,b,c) = aȼc + acȼ + bȼc 
A
aȼc and acȼ
B
aȼc and bȼc
C
aȼc only
D
acȼ and bcȼ
       Digital-Logic-Design       K-Map       GATE 2004
Question 101 Explanation: 
From given function 'f' we can draw,

There are two EPI,
A'C and AC'.
Question 102

Consider a multiplexer with X and Y as data inputs and Z as control input. Z = 0 selects input X, and Z = 1 selects input Y. What are the connections required to realize the 2-variable Boolean function f = T + R, without using any additional hardware?

A
R to X, 1 to Y, T to Z
B
T to X, R to Y, T to Z
C
T to X, R to Y, 0 to Z
D
R to X, 0 to Y, T to Z
       Digital-Logic-Design       Multiplexer       GATE 2004
Question 102 Explanation: 
Given,

f = z'x + zy
Put z=T, x=R, y=1 in f
f = T'R + T = (T+T') (R+T) = T+R
Hence, correct option is (A).
Question 103

Consider the partial implementation of a 2-bit counter using T flip-flops following the sequence 0-2-3-1-0, as shown below

To complete the circuit, the input X should be

A
Q2c
B
Q2 + Q1
C
(Q1 + Q2)c
D
Q1 ⊕ Q2
       Digital-Logic-Design       Sequential-Circuits       GATE 2004
Question 103 Explanation: 
Sequence given is
0 - 2 - 3 - 1 - 0
or
00 - 10 - 11 - 01 - 00
From the given sequence, we have state table as,

Now we have present state and next state, so we should use excitation table of T flip-flop,

From state table,
T2 = Q2⊙Q1 and T1 = Q2⊕Q1
X = T1 = Q2⊕Q1
Question 104

A 4-bit carry lookahead adder, which adds two 4-bit numbers, is designed using AND, OR, NOT, NAND, NOR gates only. Assuming that all the inputs are available in both complemented and uncomplemented forms and the delay of each gate is one time unit, what is the overall propagation delay of the adder? Assume that the carry network has been implemented using two-level AND-OR logic.

A
4 time units
B
6 time units
C
10 time units
D
12 time units
       Digital-Logic-Design       Carry-Look-Ahead-Adder       GATE 2004
Question 104 Explanation: 
The 4-bit addition will be calculated in 3 stages:
1) (2 time units) In 2 time units we can compute Gi and Pi in parallel, 2 time units for Pi since its an XOR operation and 1 time unit for Gi since its an AND operation.
2) (2 time units) Once Gi and Pi are available, we can calculate the carries, Ci, in 2 time units.
Level-1 we can compute all the conjunctions (AND).
Example: P3G2, P3P2G1, P3P2P1G0 and P3P2P1P0C0 which are required for C4.
Level-2 we get the carries by computing the disjunction (OR).
3) (2 time units) Finally, we compute the sum in 2 time units, as its a XOR operation.
Hence, the total is 2+2+2 = 6 time units.
Question 105

Let A = 1111 1010 and B = 0000 1010 be two 8-bit 2's complement numbers. Their product in 2's complement is

A
1100 0100
B
1001 1100
C
1010 0101
D
1101 0101
       Digital-Logic-Design       Number-Systems       GATE 2004
Question 105 Explanation: 
A = 1111 1010 = -610 [2's complement number]
B = 0000 1010 = 1010 [2's complement number]
A×B = -6×10 = - 6010
⇒ -6010 = 101111002
= 110000112 (1's complement)
= 110001002 (2's complement)
Question 106

Assuming all numbers are in 2's complement representation, which of the following numbers is divisible by 11111011?

A
11100111
B
11100100
C
11010111
D
11011011
       Digital-Logic-Design       Number-Systems       GATE 2003
Question 106 Explanation: 
Given: Binary numbers = 11111011
MSB bit is '1' then all numbers are negative
1's complement = 00000100
2's complement = 00000100 + 00000001 = 00000101 = -5
(A) 11100111 - (-25)10
(B) 11100100 - (-28)10
(C) 11010111 - (-41)10
(D) 11011011 - (-37)10
Answer: Option A (-25 is divisible by -5)
Question 107

Consider an array multiplier for multiplying two n bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is

A
Θ (1)
B
Θ (log n)
C
Θ (n)
D
Θ (n2)
       Digital-Logic-Design       Multiplexer       GATE 2003
Question 107 Explanation: 
Each bit in Multiplier is ANDed with a bit in Multiplicand which produce n n-bit numbers. The multiplication takes n units of time. The n n-bit numbers are added by using (n-1) n-bit adders. The time taken by (n-1) n-bit adders is k*(n-1) units.
The total time is n+kn-k = Θ(n)
Question 108

The following is a scheme for floating point number representation using 16 bits.

Let s, e, and m be the numbers represented in binary in the sign, exponent, and mantissa fields respectively. Then the floating point number represented is:

What is the maximum difference between two successive real numbers representable in this system?

A
2-40
B
2-9
C
222
D
231
       Digital-Logic-Design       Number-Systems       GATE 2003
Question 108 Explanation: 
Largest gap will be in between two most largest numbers.
The largest number is 1.111111111× 262-31 = (2−2−9)×231
Second largest number is 1.111111110×262-31 = (2−2-8)×231
Difference = (2−2−9)×231 - (2−2-8)×231
= (2-8−2−9) ×231
= 2−9×231
= 222
Question 109

A 1-input, 2-output synchronous sequential circuit behaves as follows:

Let zk, nk denote the number of 0's and 1's respectively in initial k bits of the input (zk + nk = k). The circuit outputs 00 until one of the following conditions holds.

•   zk - nk = 2. In this case, the output at the k-th and all subsequent clock ticks is 10.
•   nk - zk = 2. In this case, the output at the k-th and all subsequent clock ticks is 01. 

What is the minimum number of states required in the state transition graph of the above circuit?

A
5
B
6
C
7
D
8
       Digital-Logic-Design       Sequential-Circuits       GATE 2003
Question 109 Explanation: 
Let q is the initial state.

q0 ← Number of zeros is one more than number of ones.
q1 ← Number of ones is one more than number of zeros.
q00 ← Number of zeros is two more than number of ones.
q11 ← Number of ones is two more than number of zeros.
Question 110

The literal count of a boolean expression is the sum of the number of times each literal appears in the expression. For example, the literal count of (xy + xz') is 4. What are the minimum possible literal counts of the product-of-sum and sum-of-product representations respectively of the function given by the following Karnaugh map ? Here, X denotes "don't care"

A
(11, 9)
B
(9, 13)
C
(9, 10)
D
(11, 11)
       Digital-Logic-Design       K-Map       GATE 2003
Question 110 Explanation: 
For SOP,

⇒ w'y' + z'wx' + xyz'
Total 8 literals are there.
For POS,

⇒ (z' + w')(z' + y')(w' + x')(x + z + w)
Total 9 literals are there.
Question 111

Consider the ALU shown below.

If the operands are in 2's complement representation, which of the following operations can be performed by suitably setting the control lines K and C0 only (+ and - denote addition and subtraction respectively)?

A
A + B, and A – B, but not A + 1
B
A + B, and A + 1, but not A – B
C
A + B, but not A – B or A + 1
D
A + B, and A – B, and A + 1
       Digital-Logic-Design       Adder       GATE 2003
Question 111 Explanation: 
The circuits performs
1) A+B when K=0 and C0 = 0. It is binary adder which performs addition of two binary numbers.
2) A - B = A+ B' + 1 when K=1 and C0 = 1 ;
Here XOR gates produce B' if K=1. Since 1⊕b= b'.
"1" in (A+B+1) is coming from C0.
Note: 2's complement of B is (B'+1). 3) A+1 when B=0, K=0, C0= 1.
Increments A.
Question 112

Consider the following circuit composed of XOR gates and non-inverting buffers.

The non-inverting buffers have delays δ1 = 2 ns and δ2 = 4 ns as shown in the figure. Both XOR gates and all wires have zero delay. Assume that all gate inputs, outputs and wires are stable at logic level 0 at time 0. If the following waveform is applied at input A, how many transition(s) (change of logic levels) occur(s) at B during the interval from 0 to 10 ns?

A
1
B
2
C
3
D
4
       Digital-Logic-Design       Logic-Gates       GATE 2003
Question 112 Explanation: 

⇒ a will always be equal to A.
Question 113

Minimum sum of product expression for f(w,x,y,z) shown in Karnaugh-map below is

A
xz+y'z
B
xz'+zx'
C
x'y+zx'
D
None of the above
       Digital-Logic-Design       K-Map       GATE 2002
Question 113 Explanation: 

⇒ xz' + zx'
Question 114

The decimal value 0.25

A
is equivalent to the binary value 0.1
B
is equivalent to the binary value 0.01
C
is equivalent to the binary value 0.00111…
D
cannot be represented precisely in binary
       Digital-Logic-Design       Number-Systems       GATE 2002
Question 114 Explanation: 
1st Multiplication iteration:
Multiply 0.25 by 2.
0.25×2 = 0.50 (product)
Fractional part = 0.50
Carry = 0
2nd Multiplication iteration:
Multiply 0.50 by 2.
0.50×2 = 1.00 (product)
Fractional part = 0.00
Carry = 1
The fractional part in the 2nd iteration becomes zero and so we stop the multiplication iteration.
Carry from 1st multiplication iteration becomes MSB and carry from 2nd iteration becomes LSB. So the result is 0.01.
Question 115

The 2’s complement representation of the decimal value -15 is

A
1111
B
11111
C
111111
D
10001
       Digital-Logic-Design       Number-Systems       GATE 2002
Question 115 Explanation: 
15 = 1111
-15 = 11111
1's complement = 10000
2's complement = 10001
Question 116

Sign extension is a step in

A
floating point multiplication
B
signed 16 bit integer addition
C
arithmetic left shift
D
converting a signed integer from one size to another
       Digital-Logic-Design       Number-Systems       GATE 2002
Question 116 Explanation: 
Sign extension is a step in converting a signed integer from on size to another.
Question 117

In 2’s complement addition, overflow

A
is flagged whenever there is carry from sign bit addition
B
cannot occur when a positive value is added to a negative value
C
is flagged when the carries from sign bit and previous bit match
D
None of the above
       Digital-Logic-Design       Number-Systems       GATE 2002
Question 117 Explanation: 
The left most bit of positive value is zero. And left most bit for negative value is one. The value of 0+1 becomes 1. Then overflow never occurs.
Question 118

Consider the following logic circuit whose inputs are functions f1, f2, f3 and output is f.

Given that

f1(x,y,z) = ∑(0,1,3,5),
f2(x,y,z) = ∑(6,7) and
f(x,y,z) = ∑(1,4,5),

f3 is:

A
Σ(1,4,5)
B
Σ(6,7)
C
Σ(0,1,3,5)
D
None of the above
       Digital-Logic-Design       Logic-Circuit       GATE 2002
Question 118 Explanation: 
f(x,y,z) = (f1', (x,y,z) ⋅ f2'(x,y,z) + f3'(x,y,z))
= (Σ(0,1,3,5) ⋅ Σ(6,7) + Σ(1,4,5))
[Σ(0,1,3,5) and Σ(6,7) ⇒ No common terms]
= (Σ(1,4,5))
Question 119

Consider the following multiplexor where 10, 11, 12, 13 are four data input lines selected by two address line combinations A1A0 = 00,01,10,11 respectively and f is "the output of the multiplexor. EN is the enable input.

The function f(x,y,z) implemented by the above circuit is:

A
xyz'
B
xy+z
C
x+y
D
None of the above
       Digital-Logic-Design       Multiplexer       GATE 2002
Question 119 Explanation: 
F = (A'A0'10 + A'A0'11 + A'A0'12 + A1A013) EN
F = (xyz' + xyz + y'zy + zy')z'
= (xyz' + xyz + y'z(y+1))z'
= (xyz' + xyz + y'z)z'
= (xy(z+z') + y'z)z'
= (xy + y'z)z'
= (xyz' + y'zz')
= (xyz')
Question 120

Let f(A,B) = A' + B. Simplified expression for function f(f(x + y, y)z) is:

A
x'+z
B
xyz
C
xy'+z
D
None of the above
       Digital-Logic-Design       Boolean-Expressions       GATE 2002
Question 120 Explanation: 
f(A,B) = A' + B
⇒ f(f((x+y), y), z)
⇒ f(((x+y)' + y), z)
⇒ f(((x'⋅y') + y), z)
⇒ f((x'⋅y') + y), z)
⇒ ((x'⋅y') + y)' + z
⇒ (x'⋅y')⋅y' + z
⇒ (x+y)⋅y' + z
⇒ (xy'+yy') + z
⇒ xy' + z
Question 121

(a) Express the function f(x,y,z) = xy' + yz' with only one complement operation and one or more AND/OR operations. Draw the logic circuit implementing the expression obtained, using a single NOT gate and one or more AND/OR gates.

(b) Transform the following logic circuit (without expressing its switching function) into an equivalent logic circuit that employs only 6 NAND gates each with 2-inputs.

A
Theory Explanation is given below.
       Digital-Logic-Design       Boolean-Expression-and-Logic-Gates       GATE 2002
Question 121 Explanation: 

(A) f(x,y,z) = xy' +yz'
It is not possible to express only one NOT gate.
Question 122

Consider the following circuit. A = a2a1a0 and B = b2b1b0 are three bit binary numbers input to the circuit. The output is Z = z3z2z1z0. R0, R1 and R2 are registers with loading clock shown. The registers are loaded with their input data with the falling edge of a clock pulse (signal CLOCK shown) and appears as shown. The bits of input number A, B and the full adders are as shown in the circuit. Assume Clock period is greater than the settling time of all circuits.

(a) For 8 clocks pulses on the CLOCK terminal and the inputs A, B as shown, obtain the output Z (sequence of 4-bit values of Z). Assume initial contents of R0, R1 and R2 as all zeros.

A=          110 011 111 101 000 000 000 000
B=          101 101 011 110 000 000 000 000
Clock No     1   2   3   4   5   6   7   8 

(b) What does the circuit implement?

A
Theory Explanation is given below.
       Digital-Logic-Design       Clock-Pulse       GATE 2002
Question 123

Consider the following 32-bit floating-point representation scheme as shown in the formal below. A value is specified by 3 fields, a one bit sign field (with 0 for positive and 1 for negative values), a 24 bit fraction field (with the binary point being at the left end of the fraction bits), and a 7 bit exponent field (in excess-64 signed integer representation, with 16 being the base of exponentiation). The sign bit is the most significant bit.

(a) It is required to represent the decimal value –7.5 as a normalized floating point number in the given format. Derive the values of the various fields. Express your final answer in the hexadecimal.

(b) What is the largest values that can be represented using this format? Express your answer as the nearest power of 10.

A
Theory of Explanation is given below.
       Digital-Logic-Design       Number-Systems       GATE 2002
Question 124

Given the following Karnaugh map, which one of the following represents the minimal Sum-Of-Products of the map?

A
xy+y'z
B
wx'y'+xy+xz
C
w'x+y'z+xy
D
xz+y
       Digital-Logic-Design       K-Map       GATE 2001
Question 124 Explanation: 

⇒ y'z + xy
Question 125

Consider the following circuit with initial state Q0 = Q1 = 0. The D Flip-flops are positive edged triggered and have set up times 20 nanosecond and hold times 0.

Consider the following timing diagrams of X and C; the clock period of C <= 40 nanosecond. Which one is the correct plot of Y?

A
B
C
D
       Digital-Logic-Design       Sequential-Circuits       GATE 2001
Question 125 Explanation: 

Given clock is +edge triggered.
See the first positive edge. X is 0, and hence the output is 0, because
Y = Q1N = D1×Q0' = 0⋅Q0' = 0
At second +edge, X is 1 and Q0' is also 1. So output is 1 (when second +ve edge of the clock arrives, Q0' would surely be 1 because the setup time of flip flop is given as 20ns and clock period is ≥ 40ns).
At third +ve edge, X is 1 and Q0' is 0, so output is 0.
Now output never changes back to 1 as Q0' is always 0 and when Q0' finally becomes 1, X is 0.
Hence option (A) is the correct answer.
Question 126

The 2’s complement representation of (-539)10 in hexadecimal is

A
ABE
B
DBC
C
DE5
D
9E7
       Digital-Logic-Design       Number-Systems       GATE 2001
Question 126 Explanation: 
(539)10 = (0010 0001 1011)2
For (-539)10 = (1101 1110 0100)2
1's complement = (1101 1110 0100)2
2's complement = (1101 1110 0101)2
= (DE5)16
Question 127

Consider the circuit shown below. The output of a 2:1 Mux is given by the function (ac' + bc).

Which of the following is true?

A
f = x1' + x2
B
f = x1'x2 + x1x2'
C
f = x1x2 + x1'x2'
D
f = x1 + x2'
       Digital-Logic-Design       Number-Systems       GATE 2001
Question 127 Explanation: 
g = (a and x1′) or (b and x1)
g = (1 and x1’) or (0 and x1)
g = x1’
f = ac’ + bc
f = (a and x2′) or (b and x2)
f = (g and x2′) or (x1 and x2)
f = x1’x2’ + x1x2
Question 128

Consider the circuit given below with initial state Q0 = 1, Q1 = Q2 = 0. The state of the circuit is given by the value 4Q2 + 2Q1 + Q0

Which one of the following is the correct state sequence of the circuit?

A
1,3,4,6,7,5,2
B
1,2,5,3,7,6,4
C
1,2,7,3,5,6,4
D
1,6,5,7,2,3,4
       Digital-Logic-Design       Sequential-Circuits       GATE 2001
Question 128 Explanation: 
Question 129

(a) Is the 3-variable function f = ∑(0,1,2,4) its self-dual? Justify your answer.
(b) Give a minimal product-of-sum form of the b output of the following excess-3 to BCD converter.

A
Theory Explanation is given below.
       Digital-Logic-Design       Descriptive       GATE 2001
Question 129 Explanation: 
(a)
The function is self dual because
→ There is no mutually exclusive pair.
→ No. of minterms = No. of maxterms
(b)
Write Minimal POS.
Question 130

A sequential circuit takes an input stream of 0’s and 1’s and produces an output stream of 0’s and 1’s. Initially it replicates the input on its output until two consecutive 0’s are encountered on the input. From then onward, it produces an output stream, which is the bit-wise complement of input stream until it encounters two consecutive 1’s, whereupon the process repeats. An example of input and output stream is shown below.

The input stream: 101100 01001011 0 11
The desired output: 101100 10110100 0 11 

J-K master-slave flip-flops are to be used to design the circuit.
(a) Give the state transition diagram.
(b) Give the minimized sum-of-product expression for J and K inputs of one of its state flip-flops.

A
Theory Explanation is given below.
       Digital-Logic-Design       Sequential-Circuits       GATE 2001
Question 130 Explanation: 

Question 131

The number 43 in 2’s complement representation is

A
01010101
B
11010101
C
00101011
D
10101011
       Digital-Logic-Design       Number-Systems       GATE 2000
Question 131 Explanation: 
Positive integers are represented in its normal binary form while negative numbers are represented in its 2′s complement form. Binary representation of 43 is 00101011.
Question 132

The simultaneous equations on the Boolean variables x, y, z and w,

      x + y + z = 1
             xy = 0
         xz + w = 1
      xy +  = 0

have the following solution for x, y, z and w, respectively.

A
0 1 0 0
B
1 1 0 1
C
1 0 1 1
D
1 0 0 0
       Digital-Logic-Design       Boolean-Algebra       GATE 2000
Question 132 Explanation: 
Just put the values of each options in the equation and check it.
Question 133

Which function does NOT implement the Karnaugh map given below?

A
(w + x)y
B
xy + yw
C
D
None of the above
       Digital-Logic-Design       K-Map       GATE 2000
Question 133 Explanation: 
Given k-map gives xy + xy + wz

⇒ wy + wz + xy
Question 134

The following arrangement of master-slave flip flops

has the initial state of P, Q as 0, 1 (respectively). After three clock cycles the output state P, Q is (respectively),

A
1, 0
B
1, 1
C
0, 0
D
0, 1
       Digital-Logic-Design       Sequential-Circuits       GATE 2000
Question 134 Explanation: 
Here clocks are applied to both flip flops simultaneously.
When 11 is applied to Jk flip flop it toggles the value of P so op at P will be 1.
Input to D flip flop will be 0(initial value of P) so op at Q will be 0.
Question 135

Consider the values A = 2.0 x 1030, B = -2.0 x 1030, C = 1.0, and the sequence

             X: = A + B    Y: = A + C
             X: = X + C    Y: = Y + B  

executed on a computer where floating-point numbers are represented with 32 bits. The values for X and Y will be

A
X = 1.0, Y = 1.0
B
X = 1.0, Y = 0.0
C
X = 0.0, Y = 1.0
D
X = 0.0, Y = 0.0
       Digital-Logic-Design       Number-Systems       GATE 2000
Question 135 Explanation: 
Given: 32 bits representation. So, the maximum precision can be 32 bits (In 32-bit IEEE representation, maximum precision is 24 bits but we take best case here). This means approximately 10 digits.
A = 2.0 * 1030, C = 1.0
So, A + C should make the 31st digit to 1, which is surely outside the precision level of A (it is 31st digit and not 31st bit). So, this addition will just return the value of A which will be assigned to Y.
So, Y + B will return 0.0 while X + C will return 1.0.
Question 136

Design a logic circuit to convert a single digit BCD number to the number modulo six as follows (Do not detect illegal input):
(a) Write the truth table for all bits. Label the input bits I1, I2, …. With I1 as the least significant bit. Label the output bits R1, R2, …. With R1 as the least significant bit. Use 1 to signify truth.
(b) Draw one circuit for each output bit using, altogether, two two-input AND gates, one two-input gate and two NOT gates.

A
Theory Explanation is given below.
       Digital-Logic-Design       Descriptive       GATE 2000
Question 137

Which of the following expressions is not equivalent to ?

A
x NAND X
B
x NOR x
C
x NAND 1
D
x NOR 1
       Digital-Logic-Design       Logic-Gates       GATE 1999
Question 137 Explanation: 
Question 138

Which of the following functions implements the Karnaugh map shown below?

A
B
C
D
       Digital-Logic-Design       K-Map       GATE 1999
Question 138 Explanation: 

⇒ CD+AD = D(A+C)
Question 139

Booth’s coding in 8 bits for the decimal number –57 is

A
0 – 100 + 1000
B
0 – 100 + 100 - 1
C
0 – 1 + 100 – 10 + 1
D
00 – 10 + 100 - 1
       Digital-Logic-Design       Number-Systems       GATE 1999
Question 139 Explanation: 
Option-B:
Question 140

The maximum gate delay for any output to appear in an array multiplier for multiplying two n bit number is

A
On2
B
O(n)
C
O(log n)
D
O(1)
       Digital-Logic-Design       Multiplexer       GATE 1999
Question 140 Explanation: 
Total no. of gates being used for 'n' bit multiplication in an array multiplier (n*n) = (2n-1)
Total delay = 1 * 2n - 1 = O(2n - 1) = n
Question 141

The number of full and half-adders required to add 16-bit numbers is

A
8 half-adders, 8 full-adders
B
1 half-adder, 15 full-adders
C
16 half-adders, 0 full-adders
D
4 half-adders, 12 full-adders
       Digital-Logic-Design       Adder       GATE 1999
Question 141 Explanation: 
For Least Significant Bit we do not need a full adder since initially carry is not present.
But for rest of bits we need full address since carry from previous addition has to be included into the addition operation.
So, in total 1 half adder and 15 full adders are required.
Question 142

Zero has two representations in

A
Sign magnitude
B
1’s complement
C
2’s complement
D
None of the above
E
Both A and B
       Digital-Logic-Design       Number-Systems       GATE 1999
Question 142 Explanation: 
Sign magnitude:
+0 = 0000
-0 = 1000
1's complement:
+0 = 0000
-0 = 1111
Question 143

What happens when a bit-string is XORed with itself n-times as shown:

  [B⊕(B⊕(B⊕(B........ n times)]  
A
complements when n is even
B
complements when n is odd
C
divides by 2n always
D
remains unchanged when n is even
       Digital-Logic-Design       EX-OR       GATE 1998
Question 143 Explanation: 
B⊕(B⊕(B⊕...) n times
Consider:
B⊕(B⊕B)
= B⊕0
= 0 (if consider n times it remains unchanged)
Question 144

A multiplexor with a 4 bit data select input is a

A
4:1 multiplexor
B
2:1 multiplexor
C
16:1 multiplexor
D
8:1 multiplexor
       Digital-Logic-Design       Multiplexer       GATE 1998
Question 144 Explanation: 
For 'n' bit data it selects 2n : 1 input
For 4 bit data it selects 24 : 1 = 16: 1 input
Question 145

The threshold level for logic 1 in the TTL family is

A
any voltage above 2.5 V
B
any voltage between 0.8 V and 5.0 V
C
any voltage below 5.0 V
D
any voltage below Vcc but above 2.8 V
       Digital-Logic-Design       Threshold-Voltage       GATE 1998
Question 145 Explanation: 
Voltage is to be below Vcc = 5V but above 2.8V
Question 146

The octal representation of an integer is (342)8. If this were to be treated as an eight-bit integer is an 8085 based computer, its decimal equivalent is

A
226
B
-98
C
76
D
-30
       Digital-Logic-Design       Number-Systems       GATE 1998
Question 146 Explanation: 
(342)8 = (011 100 010)2 = (1110 0010)2
If this can be treated as 8 bit integer, then the first becomes sign bit i.e., '1' then the number is negative.
8085 uses 2's complement then

⇒ -30
Question 147

The function represented by the Karnaugh map given below is:

A
A⋅B
B
AB+BC+CA
C
D
None of the above
       Digital-Logic-Design       K-Map       GATE 1998
Question 147 Explanation: 
Question 148

Which of the following operations is commutative but not associative?

A
AND
B
OR
C
NAND
D
EXOR
       Digital-Logic-Design       Logic-Gates       GATE 1998
Question 148 Explanation: 
NAND operation is commutative but not associative.
Question 149

Suppose the domain set of an attribute consists of signed four digit numbers. What is the percentage of reduction in storage space of this attribute if  it is stored as an integer rather than in character form?

A
80%
B
20%
C
60%
D
40%
       Digital-Logic-Design       Number-Systems       GATE 1998
Question 149 Explanation: 
We assume byte addressable memory - nothing smaller than a byte can be used.
We have four digits. So to represent signed 4 digit numbers we need 5 bytes, 4 bytes for four digits and 1 for the sign.
So required memory = 5 bytes.
Now, if we use integer, the largest no. needed to represent is 9999 and this requires 2 bytes of memory for signed representation.
9999 in binary requires 14 bits. So, 2 bits remaining and 1 we can use for sign bit.
So, memory savings,
= 5 - 2/5 × 100
= 60%
Question 150

Let * be defined as x * y = x' + y. Let z = x * y. Value of z * x is

A
x'+y
B
x
C
0
D
1
       Digital-Logic-Design       Boolean-Expressions       GATE 1997
Question 150 Explanation: 
Question 151

An N-bit carry look ahead adder, where N is a multiple of 4, employs ICs 74181 (4 bit ALU) and 74182 (4 bit carry look ahead generator).

The minimum addition time using the best architecture for this adder is

A
proportional to N
B
proportional to log N
C
a constant
D
None of the above
       Digital-Logic-Design       Adder       GATE 1997
Question 152

Let f(x, y, z) = x' + y'x + xz be a switching function. Which one of the following is valid?

A
B
xz is a minterm of f
C
xz is an implicant of f
D
y is a prime implicant of f
       Digital-Logic-Design       K-Map       GATE 1997
Question 152 Explanation: 
In sum of terms,any term is an implicant because it implies the function. So xz is an implicant and hence 'C' is the answer.
Question 153

Given √224)r = 13)r.
The value of the radix r is:

A
10
B
8
C
5
D
6
       Digital-Logic-Design       Number-Systems       GATE 1997
Question 153 Explanation: 
(√224)r = (13)r
Convert r base to decimal.
√2r2 + 25 + 4 = r + 3
Take square both sides,
2r2 + 2r + 4 = r2 + 6r + 9
r2 - 4r - 5 = 0
r2 - 5r + r - 5 = 0
r(r - 5) + (r - 5) = 0
r = -1, 5
r cannot be -1,
So r = 5 is correct answer.
Question 154

Consider a logic circuit shown in figure below. The functions f1, f2 and f (in canonical sum of products form in decimal notation) are:

f1(w,x,y,z) = ∑8,9,10
f2(w,x,y,z) = ∑7,8,12,13,14,15
f(w,x,y,z) = ∑8,9 

The function f3 is

A
Σ9,10
B
Σ9
C
Σ1,8,9
D
Σ8,10,15
       Digital-Logic-Design       Logic-Circuit       GATE 1997
Question 154 Explanation: 
f = f1⋅f2 + f3
Since, f1 and f2 are in canonical sum of products form, f1⋅f2 will only contain their common terms that is f1⋅f2 = Σ8.
Now,
Σ8 + f3 = Σ8,9
So, f3= Σ9
Question 155

A ROM is sued to store the table for multiplication of two 8-bit unsigned integers. The size of ROM required is

A
256 × 16
B
64 K × 8
C
4 K × 16
D
64 K × 16
       Digital-Logic-Design       ROM       GATE 1996
Question 155 Explanation: 
When we multiply the two 8 bit numbers result will reach upto 16 bits. So we require 16 bits for each multiplication output.
No. of results possible = 28 × 28 = 216 = 64K
Then total size of ROM = 64K × 16
Question 156

Both’s algorithm for integer multiplication gives worst performance when the multiplier pattern is

A
101010 …..1010
B
100000 …..0001
C
111111 …..1111
D
011111 …..1110
       Digital-Logic-Design       Booth\'s-Algorithm       GATE 1996
Question 156 Explanation: 
When the pairs 01 (or) 10 occur frequently in the multiplier. In that case Booth multiplication gives worst performance.
Question 157

Consider the following floating point number representation

The exponent is in 2's complement representation and mantissa is in the sign magnitude representation. The range of the magnitude of the normalized numbers in this representation is

A
0 to 1
B
0.5 to 1
C
2-23 to 0.5
D
0.5 to (1-2-23)
       Digital-Logic-Design       Number-Systems       GATE 1996
Question 157 Explanation: 
Maximum value of mantissa will be 23, is where a decimal point is assumed before first 1. So the value is 1 - 2-23.
Question 158

Consider the circuit given below which has a four bit binary number b3b2b1b0 as input and a five bit binary number d4d3d2d1d0 as output. The circuit implements:

A
Binary of Hex conversion
B
Binary to BCD conversion
C
Binary to grey code conversion
D
Binary to radix-12 conversion
       Digital-Logic-Design       Adder       GATE 1996
Question 158 Explanation: 
Here ф means 0.
Whenever, b2 = b3 = 1, then only 0100, i.e., 4 is added to the given binary number. Lets write all possibilities for b.

Note that the last 4 combinations leads to b3 and b2 as 1. So, in these combinations only 0010 will be added.
1100 is 12
1101 is 13
1110 is 14
1111 is 15
in binary unsigned number system.
1100 + 0100 = 10000
1101 + 0100 = 10001, and so on.
This is conversion to radix 12.
Question 159

Consider the circuit in below figure. f implements

A
B
A + B + C
C
A ⊕ B ⊕ C
D
AB + BC + CA
       Digital-Logic-Design       Multiplexer       GATE 1996
Question 159 Explanation: 
Question 160

What is the equivalent Boolean expression in product-of-sums form for the Karnaugh map given below.

A
B
C
D
E
None of the above
       Digital-Logic-Design       K-Map       GATE 1996
Question 160 Explanation: 
Correct option is

Question 161

What values of A, B, C and D satisfy the following simultaneous Boolean equations?

A
A = 1, B = 0, C = 0, D = 1
B
A = 1, B = 1, C = 0, D = 0
C
A = 1, B = 0, C = 1, D = 1
D
A = 1, B = 0, C = 0, D = 0
       Digital-Logic-Design       Boolean-Algebra       GATE 1995
Question 161 Explanation: 
For verification, just put up the values and check for AND, OR operations and their outputs.
Question 162

The number of 1’s in the binary representation of
(3*4096 + 15*256 + 5*16 + 3) are:

A
8
B
8
C
10
D
12
       Digital-Logic-Design       Number-Systems       GATE 1995
Question 162 Explanation: 
3 × 4096 = 3 × 212
= (11000000000000)2
15 × 256 = 15 × 28
= (111100000000)2
5 × 16 = 5 × 24
= (1010000)2
3 = (11)2
Hence, all binary numbers,

∴ 101's
Question 163

The logic expression for the output of the circuit shown in figure below is:

A
B
C
D
E
None of the above.
       Digital-Logic-Design       Logic-Gates       GATE 1994
Question 163 Explanation: 
Question 164

The number of flip-flops required to construct a binary modulo N counter is __________.

A
⌈log2 N⌉
       Digital-Logic-Design       Flip-Flops       GATE 1994
Question 164 Explanation: 
For mod-N counter we need ⌈log2 N⌉ flip flops.
Question 165

Consider n-bit (including sign bit) 2’s complement representation of integer number. The range of integer values, N, that can be represented is _________ ≤ N ≤ _________

A
-2n-1 to 2n-1 - 1
       Digital-Logic-Design       Number-Systems       GATE 1994
Question 166

A multiplexer is placed between a group of 32 registers and an accumulator to regulate data movement such that at any given point in time the content of only one register will move to the accumulator. The minimum number of select lines needed for the multiplexer is _____.

A
5
       Digital-Logic-Design       Combinational-Circuit       GATE 2020
Question 166 Explanation: 
Number of registers is 32. Only one register has to be selected at any instant of time.
A 25x1 Multiplexer with 5 select lines selects one of the 32(= 25) registers at a time depending on the selection input.
The content from the selected register will be transferred through the output line to the Accumulator.
Question 167

If there are m input lines and n output lines for a decoder that is used to uniquely address a byte addressable 1 KB RAM, then the minimum value of m + n is ____.

A
1034
       Digital-Logic-Design       Combinational-Circuit       GATE 2020
Question 167 Explanation: 
The size of the decoder required is 10 x 210 i.e., 10 x 1024.
Each output line of the decoder is connected to one of the 1K(= 1024) rows of RAM.
Each row stores 1 Byte.
m=10 and n=1024
Question 168

Consider the Boolean function z(a,b,c).

Which one of the following minterm lists represents the circuit given above?

A
Z = ∑(0,1,3,7)
B
Z = ∑(2,4,5,6,7)
C
Z = ∑(1,4,5,6,7)
D
Z = ∑(2,3,5)
       Digital-Logic-Design       Logic-Gates       GATE 2020
Question 168 Explanation: 
The output of the given circuit is a + b’c.
Convert a+b’c into canonical form which is sum of minterms.
a + b’c = a(b + b’)(c + c’) + (a + a’)b’c
= abc + abc’ + ab’c + ab’c’ + ab’c + a’b’c
= Σ(7,6,5,4,1)
Question 169

Consider three registers R1, R2 and R3 that store numbers in IEEE-754 single precision floating point format. Assume that R1 and R2 contain the values (in hexadecimal notation) 0x42200000 and 0xC1200000, respectively.

If R3 = R1/R2, what is the value stored in R3?

A
0x40800000
B
0x83400000
C
0xC8500000
D
0xC0800000
       Digital-Logic-Design       Number-Systems       GATE 2020
Question 169 Explanation: 
Given numbers are 0x42200000 and 0xC1200000 which are stored in the registers R1 and R2, respectively.

R1 = 1.0100..0 X 2132-127
= 1.0100..0 X 25
= 101.0 X 23
= 5 X 8
= 40

R2 = (-1) x 1.0100..0 X 2130-127
= (-1) x 1.0100..0 X 23
= (-1) x 101.0 X 21
= (-1) x5 X 2
= -10
R3 = R1/R2
= -4
= (-1)x 1.0 x 22
Sign = 1
Mantissa = 000..0
Exponent = 2+127 = 129

R3 = 1100 0000 1000 000..0
= 0x C 0 8 0 0 0 0 0
Question 170

Identify the logic function performed by the circuit shown in figure.

A
exclusive OR
B
exclusive NOR
C
NAND
D
NOR
       Digital-Logic-Design       Logic-Gates       GATE 1993
Question 170 Explanation: 

So finally, we can write
Question 171

For the initial state of 000, the function performed by the arrangement of the J-K flip-flops in figure is:

A
Shift Register
B
Mod-3 Counter
C
Mod-6 Counter
D
Mod-2 Counter
E
Both A and C
       Digital-Logic-Design       J-K-Flip-Flop       GATE 1993
Question 171 Explanation: 

Circuit behaves as shift register and mod-6 counter. Note that this is the Johnson counter which is the application of shift register. And Johnson counter is mod-2N counter.
Question 172

Convert the following numbers in the given bases into their equivalents in the desired bases.
(a) 110.101)2 = x)10
(b) 1118)10 = y)H

A
(a) 6.625, (b) (45E)H
       Digital-Logic-Design       Number-Systems       GATE 1993
Question 172 Explanation: 
(a) 1*22 + 1*21 + 0*20 + 1*2-1 + 0*2-2 + 1*2-3
= 4 + 2 + 0 + 0.5 + 0 + 0.125
= 6.625
(b) 1118 mod 16 = E, quotient = 69
69 mod 16 = 5, quotient = 4
4 mod 16 = 4
Writing the mods result in reverse order gives (45E)H.
Question 173

A ROM is used to store the Truth table for a binary multiple unit that will multiply two 4-bit numbers. The size of the ROM (number of words × number of  bits) that is required to accommodate the Truth table is M words × N bits. Write the values of M and N.

A
M = 256, N = 8
       Digital-Logic-Design       Truth Table       GATE 1993
Question 173 Explanation: 
Input will consist of 8 bit (two 4-bit numbers) = 28 address.
Output will be of 8 bits.
So memory will be of 28 × 8.
So, M = 256, N = 8.
Question 174

The Boolean function in sum of products form where K-map is given below (figure) is:___________

A
ABC + B'C' + A'C'
       Digital-Logic-Design       K-Map       GATE 1992
Question 174 Explanation: 
We can write this as

⇒ ABC + B'C' + A'C'
Question 175

Consider a 3-bit error detection and 1-bit error correction hamming code for 4-bit date. The extra parity bits required would be ________ and the 3-bit error detection is possible because the code has a minimum distance of ________

A
Fill in the blanks
       Digital-Logic-Design       Parity-Bits       GATE 1992
Question 176

The operation which is commutative but not associative is:

A
AND
B
OR
C
EX-OR
D
NAND
       Digital-Logic-Design       Operators       GATE 1992
Question 176 Explanation: 
NAND and NOR operation follow commutativity but do not follow associativity.
Question 177

All digital circuits can be realized using only

A
Ex-OR gates
B
Multiplexers
C
Half adders
D
OR gates
E
Both B and C
       Digital-Logic-Design       Operators       GATE 1992
Question 177 Explanation: 
NOR gate, NAND gate, Multiplexers and Half adders can also be used to realize all digital circuits.
Question 178

For the digital in figure, the expression for the output f is ________

A
Out of syllabus.
       Digital-Logic-Design       Circuits       GATE 1991
Question 179

Consider the number given by the decimal expression:

  163 * 9 + 162 * 7 + 16 * 5 + 3

The number of 1’s in the unsigned binary representation of the number is ________.

A
9
       Digital-Logic-Design       Number-Systems       GATE 1991
Question 179 Explanation: 
Hexadecimal representation of a given no. is,
(9753)16
It's binary representation is,
1001011101010011
∴ The no. of 1's is 9.
Question 180

When two 4-bit binary number A = a3a2a1a0 and B = b3b2b1b0 are multiplied, the digit c1 of the product C is given by _________

A
c1 = b1a0 ⊕ a1b0
       Digital-Logic-Design       Number-Systems       GATE 1991
Question 180 Explanation: 

⇒ c1 = b1a0 ⊕ a1b0
Question 181

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Advantage of synchronous sequential circuits over asynchronous ones is:

A
faster operation
B
ease of avoiding problems due to hazards
C
lower hardware requirement
D
better noise immunity
E
none of the above
       Digital-Logic-Design       Sequential-Circuits       GATE 1991
Question 181 Explanation: 
In synchronization, there is a less chance of hazards but it can increase the delay. Then the advantage is ease of avoiding problems due to hazards.
Question 182

Choose the correct alternatives (More than one may be correct). Two NAND gates having open collector outputs are tied together as shown in below figure.

The logic function Y, implemented by the circuit is,

A
Y = ABC + DE
B
C
Y = ABC . DE
D
E
Both (C) and (D)
       Digital-Logic-Design       Circuits-Output       GATE 1990
Question 182 Explanation: 
There should be bubbled connection between two gates
Y = ((ABC)' + (DE)')'
Y = ABC . DE
Note: Open gate works as NOR gate.
Question 183

State whether the following statements are TRUE or FALSE with reason:

RAM is a combinational circuit and PLA is a sequential circuit.
A
True
B
False
       Digital-Logic-Design       Combinational-and-Sequential-Circuits       GATE 1990
Question 183 Explanation: 
1) RAM is not a combinational circuit. For RAM, the input is the memory location selector and operation (read or write) and another byte (which can be input for write operation or output for read operation), and the output is either a success indicator (for write operation) or the byte at the selected location (for read operation). It does depend on past inputs, or rather, on the past write operations at the selected byte. This is a sequential logic circuit.
2) PLA is a combination circuit as ROM. PLA is a programmable AND array and a programmable OR array. A PLA with n inputs has fewer than 2n AND gates (otherwise there would be no advantage over a ROM implementation of the same size). A PLA only needs to have enough AND gates to decode as many unique terms as there are in the functions it will implement it.
Question 184

The total number of Boolean functions which can be realized with four variables is:

A
4
B
17
C
256
D
65,536
       Digital-Logic-Design       Boolean-Functions       GATE 1987
Question 184 Explanation: 
Total no. of Boolean functions which can be realized with four variables is:
224 = 216 = 65,536
Question 185

The above circuit produces the output sequence:

A
1111 1111 0000 0000
B
1111 0000 1111 000
C
1111 0001 0011 010
D
1010 1010 1010 1010
       Digital-Logic-Design       Sequential-Circuits       GATE 1987
Question 185 Explanation: 
Let us suppose initially output of all JK flip flop is 1.
So we can draw below table to get the output Q3.

From the above table Q3 that is output is 1111 0001 0011 010.
So, answer is (C).
Question 186

The output F of the below multiplexer circuit can be represented by

A
B
A⊕B⊕C
C
A⊕B
D
       Digital-Logic-Design       Multiplexer       GATE 1987
Question 186 Explanation: 
Question 187

The exponent of a floating-point number is represented in excess-N code so that:

A
The dynamic range is large.
B
The precision is high.
C
The smallest number is represented by all zeros.
D
Overflow is avoided.
       Digital-Logic-Design       Number-Systems       GATE 1987
Question 187 Explanation: 
To avoid extra work, excess-N code is used so that all exponent can be represented in positive numbers, starting with 0.
Question 188

The refreshing rate of dynamic RAMs is in the range of

A
2 microseconds
B
2 milliseconds
C
50 milliseconds
D
500 milliseconds
       Digital-Logic-Design       DRAM       GATE 1987
Question 188 Explanation: 
During a 2 millisecond interval all dynamic RAM memory is refreshed.
Question 189

A set of Boolean connectives is functionally complete if all Boolean functions can be synthesized using those. Which of the following sets of connectives is NOT functionally complete?

A
EX-NOR
B
implication, negation
C
OR, negation
D
NAND
       Digital-Logic-Design       Boolean-Functions       GATE 2008-IT
Question 189 Explanation: 
→ EX-NOR is not functionally complete.
→ NOR and NAND are the functionally complete logic gates, OR, AND, NOT only logic gate can be implemented by using them.
→ And (Implication, Negation) is also functionally complete.
Question 190

The following bit pattern represents a floating point number in IEEE 754 single precision format

 110000011101000000000000000000000
The value of the number in decimal form is
A
-10
B
-13
C
-26
D
None of these
       Digital-Logic-Design       Number-Systems       GATE 2008-IT
Question 190 Explanation: 
Sign bit is 1 then given number is negative.
Exponent bits - 10000011
Exponent can be added with 127 bias in IEEE single precision format then outval exponent
= 10000011 - 127
= 131 - 127
= 4
→ In IEEE format, an implied 1 is before mantissa, and hence the outval number is
→ 1.101 × 24 = -(11010)2 = -26
Question 191

Consider the following Boolean function of four variables

 f(A,B,C,D) = Σ(2, 3, 6, 7, 8, 9, 10, 11, 12, 13)
The function is
A
independent of one variable
B
independent of two variables
C
independent of three variable
D
dependent on all the variables
       Digital-Logic-Design       Boolean-Functions       GATE 2008-IT
Question 191 Explanation: 
f(A, B, C, D) = Σ(2, 3, 6, 7, 8, 9, 10, 11, 12, 13)

Independent of one variable '0'.
Question 192

What Boolean function does the circuit below realize ?

A
xz+x’z’
B
xz’+x’z
C
x’y’+yz
D
xy+y’z’
       Digital-Logic-Design       Decoder       GATE 2008-IT
Question 192 Explanation: 
f = (x’y’z’ + x’yz’+xy’z+xyz)’
= (x’z’ + xz)’
= x’z + xz’
Question 193

A processor that has carry, overflow and sign flag bits as part of its program status word (PSW) performs addition of the following two 2's complement numbers 01001101 and 11101001. After the execution of this addition operation, the status of the carry, overflow and sign flags, respectively will be:

A
1, 1, 0
B
1, 0, 0
C
0, 1, 0
D
1, 0, 1
       Digital-Logic-Design       Number-Systems       GATE 2008-IT
Question 193 Explanation: 

Carry flag = 1
Overflow flag = 0
Sign bit = 0 (MSB bit is 0)
Overflow flag:
In computer processors, the overflow flag is usually a single bit in a system status register used to indicate when an arithmetic overflow has occurred in an operation.
Question 194

Consider the following state diagram and its realization by a JK flip flop The combinational circuit generates J and K in terms of x, y and Q. The Boolean expressions for J and K are:

A
(x⊕y)’ and x’⊕y’
B
(x⊕y)’ and x⊕y
C
x⊕y and (x⊕y)’
D
x⊕y and x⊕y
       Digital-Logic-Design       Sequential-Circuits       GATE 2008-IT
Question 194 Explanation: 
From the given statement:

Excitation table of JK:
Question 195

The two numbers given below are multiplied using the Booth's algorithm.

Multiplicand : 0101 1010 1110 1110 
Multiplier: 0111 0111 1011 1101
How many additions/Subtractions are required for the multiplication of the above two numbers?
A
6
B
8
C
10
D
12
       Digital-Logic-Design       Number-Systems       GATE 2008-IT
Question 195 Explanation: 
Take the multiples and add 0 to the LSB.
Now we have some values defined for pair of bits in Booth’s Algorithm,
00 → 0
11 → 0
01 → -1
10 → 1
Now after adding 0 to the LSB of the multiplier, start traversing from left to right and accordingly put the values defined above.

Hence, total 8 additions / subtractions required.
Question 196

Which of the following input sequences for a cross-coupled R-S flip-flop realized with two NAND gates may lead to an oscillation?

A
11, 00
B
01, 10
C
10, 01
D
00, 11
       Digital-Logic-Design       Sequential-Circuits       GATE 2007-IT
Question 196 Explanation: 
RS slip-flop using NAND gates.
So, 00 input cause indeterminate state which may lead to oscillation.
Question 197

The following circuit implements a two-input AND gate using two 2-1 multiplexers. What are the values of X1, X2, X3 ?

A
X1 = b, X2 = 0, X3 = a
B
X1 = b, X2 = 1, X3 = b
C
X1 = a, X2 = b, X3 = 1
D
X1 = a, X2 = 0, X3 = b
       Digital-Logic-Design       Multiplexer       GATE 2007-IT
Question 197 Explanation: 
F = (bX1' + aX1)X3 + X2X3'
If we put
X1 = b
X2 = 0
X3 = a
Then we get,
F = ab
Question 198

The following expression was to be realized using 2-input AND and OR gates. However, during the fabrication all 2-input AND gates were mistakenly substituted by 2-input NAND gates.

(a.b).c + (a'.c).d + (b.c).d + a. d 
What is the function finally realized?

A
1
B
a’ + b’ + c’ + d’
C
a’ + b + c’ + d’
D
a’ + b’ + c + d’
       Digital-Logic-Design       Boolean-Functions       GATE 2007-IT
Question 198 Explanation: 
(a⋅b)⋅c + (a'⋅c)⋅d + (b⋅c)⋅d + a⋅d
= ((ab)'c)' + ((a'c)'d)' + ((bc)'d)' + (ad)'
= ab + c' + a'c + d' + bc + d' + a' + d'
= ab + c' + a'c + bc + a' + d'
= ab + c' + bc + a' + d'
= b + c' + bc + a' + d'
= a' + b + c' + d'
Question 199

What is the final value stored in the linear feedback shift register if the input is 101101?

A
0110
B
1011
C
1101
D
1111
       Digital-Logic-Design       Shift-register       GATE 2007-IT
Question 199 Explanation: 
Question 200

(C012.25)H – (10111001110.101)B =

A
(135103.412)O
B
(564411.412)O
C
(564411.205)O
D
(135103.205)O
       Digital-Logic-Design       Number-Systems       GATE 2007-IT
Question 200 Explanation: 
(C012.25)H – (10111001110.101)B
= 1100000000010010.00100101 - 0000010111001110.10100000
= 1011101001000011.10000101
= 1011101000011.100001010
= (135103.412)O
Question 201

The line T in the following figure is permanently connected to the ground.

Which of the following inputs (X1 X2 X3 X4) will detect the fault?

A
0000
B
0111
C
1111
D
None of these
       Digital-Logic-Design       Circuits-Output       GATE 2007-IT
Question 201 Explanation: 

Since the problem is in the link T which is connected as input to NOR gate. So to check link T we have to make the output dependent on T by deactivating link M. So to deactivate link M, the output at M should be 0, as link M is input to NOR gate. So, to output at M as 0,
X1 = 1
X2 = 1
X3 = 1
X4 = 0
∴ None of the given option is correct.
Question 202

Consider the following expression

 ad' + (ac)' + bc'd 
Which of the following Karnaugh Maps correctly represents the expression?

A
B
C
D
       Digital-Logic-Design       K-Map       GATE 2007-IT
Question 202 Explanation: 
Just draw the K-map from the given expression,
ad' + a'c' + bc'd

Hence, option (A) matches.
Question 203

Consider the following expression

 ad' + (ac)' + bc'd 
Which of the following expressions does not correspond to the Karnaugh Map obtained for the above expression?

A
c’d’+ ad’ + abc’ + (ac)’d
B
(ac)’ + c’d’ + ad’ + abc’d
C
(ac)’ + ad’ + abc’ + c’d
D
b’c’d’ + acd’ + (ac)’ + abc’
       Digital-Logic-Design       K-Map       GATE 2007-IT
Question 203 Explanation: 
Let's check for option (C):
a'c' + ad' + abc' + c'd

Not equivalent to the K-map, we get in previous question.
Question 204

The addition of 4-bit, two’s complement, binary numbers 1101 and 0100 results in

A
0001 and an overflow
B
1001 and no overflow
C
0001 and no overflow
D
1001 and an overflow
       Digital-Logic-Design       Number-Systems       GATE 2006-IT
Question 204 Explanation: 
2's complement of 1101 = 0011
2's complement of 1100 = 1100
Add = 1111
Now convert 1111 to normal form.
⇒ 0000 (1's complement)
⇒ 0001 (2's complement) No carry bit.
Question 205

The boolean function for a combinational circuit with four inputs is represented by the following Karnaugh map.

Which of the product terms given below is an essential prime implicant of the function?

A
QRS
B
PQS
C
PQ'S'
D
Q'S'
       Digital-Logic-Design       K-Map       GATE 2006-IT
Question 205 Explanation: 
Essential prime implicants which are grouped only by only one method or way. So, in the given question corner's ones are grouped by only one method.
Question 206

The majority function is a Boolean function f(x, y, z) that takes the value 1 whenever a majority of the variables x, y, z and 1. In the circuit diagram for the majority function shown below, the logic gates for the boxes labeled P and Q are, respectively,

A
XOR, AND
B
XOR, XOR
C
OR, OR
D
OR, AND
       Digital-Logic-Design       Boolean-Functions       GATE 2006-IT
Question 206 Explanation: 

Thus we have OR and AND which gives different outputs on (0,0) and (1,1).
The encodes can be hence select from the two and decide output of the function according to x.
Question 207

When multiplicand Y is multiplied by multiplier X = xn-1xn-2 ...x0 using bit-pair recoding in Booth's algorithm, partial products are generated according to the following table.

The partial products for rows 5 and 8 are

A
2Y and Y
B
-2Y and 2Y
C
-2Y and 0
D
0 and Y
       Digital-Logic-Design       Number-Systems       GATE 2006-IT
Question 207 Explanation: 

⇒ -2Y and 0
Question 208

A two-way switch has three terminals a, b and c. In ON position (logic value 1), a is connected to b, and in OFF position, a is connected to c. Two of these two-way switches S1 and S2 are connected to a bulb as shown below.

Which of the following expressions, if true, will always result in the lighting of the bulb ?

A
B
C
D
       Digital-Logic-Design       Circuits-Output       GATE 2005-IT
Question 208 Explanation: 
The bulb will be on when both the switch S1 and S2 are in same state, either OFF (or) ON:

From this we can clearly know that given is EX-NOR operation i.e.,
(S1⊙S2) = (S1⊕S2)'
Question 209

How many pulses are needed to change the contents of a 8-bit up counter from 10101100 to 00100111 (rightmost bit is the LSB)?

A
134
B
133
C
124
D
123
       Digital-Logic-Design       Sequential-Circuits       GATE 2005-IT
Question 209 Explanation: 
The 8 bit counter will be 0-255 to move from 10101100 (172) to 1000111 (39).
→ First counter is move from 172 to 255 = 83 pulses
→ 255 to 0 = 1 pulse
→ 0 to 39 = 39 pulses
Total = 83 + 1 + 39 = 123 pulses
Question 210

A line L in a circuit is said to have a stuck-at-0 fault if the line permanently has a logic value 0. Similarly a line L in a circuit is said to have a stuck-at-1 fault if the line permanently has a logic value 1. A circuit is said to have a multiple stuck-at fault if one or more lines have stuck at faults. The total number of distinct multiple stuck-at faults possible in a circuit with N lines is

A
3N
B
3N - 1
C
2N - 1
D
2
       Digital-Logic-Design       Sequential-Circuits       GATE 2005-IT
Question 210 Explanation: 
Answer should be 3N-1.
This is because the total possible combinations (i.e., a line may either be at fault (in 2 ways i.e., stuck at 0 or 1) or it may not be, so there are only 3 possibilities for a line) is 3N. In only one combination the circuit will have all lines to be correct (i.e., not a fault). Hence, total combinations in which distinct multiple stuck-at-faults possible in a circuit with N lines is 3N - 1.
Question 211

(34.4)8 × (23.4)8 evaluates to

A
(1053.6)8
B
(1053.2)8
C
(1024.2)8
D
None of these
       Digital-Logic-Design       Number-Systems       GATE 2005-IT
Question 211 Explanation: 
First convert (34.4)8 and (23.4)8 to decimal.
(34.4)8 = 3×81 + 4×80 + 4×8-1
= 24 + 4 + 0.5
= (28.5)10
(23.4)8 = 2×81 + 3×80 + 4×8-1
= 16 + 3 + 0.5
= (19.5)10
Now,
(28.5)10 × (19.5)01 = (555.75)10
Now,
(555.75)10 = ( ? )8
To convert the integer part,

We get, 1053.
To convert the fractional part, keep multiplying by 8 till decimal part becomes 0,

∴ (555.75)10 = (1053.6)8
Question 212

The circuit shown below implements a 2-input NOR gate using two 2-4 MUX (control signal 1 selects the upper input). What are the values of signals x, y and z?

A
1, 0, B
B
1, 0, A
C
0, 1, B
D
0, 1, A
       Digital-Logic-Design       Sequential-Circuits       GATE 2005-IT
Question 212 Explanation: 
In MUX1, the equation is
g = Ax + Bz'
In MUX2, the equation is
f = xg + yg'
= x(Az+Bz') + y(Az+Bz')'
Function f should be equal to (A+B)'.
Just try to put the values of option (D), i.e., x=0, y=1, z=A,
f = 0(AA+BA') +1(AA+BA')'
= (A+B)'
∴ Option (D) is correct.
Question 213

n instruction set of a processor has 125 signals which can be divided into 5 groups of mutually exclusive signals as follows:

Group 1 : 20 signals, Group 2 : 70 signals, 
Group 3 : 2 signals,  Group 4 : 10 signals, 
Group 5 : 23 signals. 

How many bits of the control words can be saved by using vertical microprogramming over horizontal microprogramming?

A
0
B
103
C
22
D
55
       Digital-Logic-Design       CPU-Control-Design-and-Interfaces       GATE 2005-IT
Question 213 Explanation: 
In horizontal microprogramming we need 1 bit for every control word, therefore total bits in horizontal microprogramming
= 20 + 70 + 2 + 10 + 23
= 125
Now lets consider vertical microprogramming. In vertical microprogramming no. of bits required to activate 1 signal in group of N signals, is ⌈log2 N⌉. And in the question 5 groups contains mutually exclusive signals,
group 1 = ⌈log2 20⌉ = 5
group 2 = ⌈log2 70⌉ = 7
group 3 = ⌈log2 2⌉ = 1
group 4 = ⌈log2 10⌉ = 4
group 5 = ⌈log2 23⌉ = 5
Total bits required in vertical microprogramming
= 5 + 7 + 1 + 4 + 5
= 22
So, number of bits saved is
= 125 - 22
= 103
Question 214

What is the minimum number of NAND gates required to implement a 2-input EXCLUSIVE-OR function without using any other logic gate?

A
3
B
4
C
5
D
6
       Digital-Logic-Design       Logic-Gates       GATE 2004-IT
Question 214 Explanation: 

To create 2-input Exclusive-OR function we require 4 NAND gates.
Question 215

What is the minimum size of ROM required to store the complete truth table of an 8-bit × 8-bit multiplier?

A
32 K × 16 bits
B
64 K × 16 bits
C
16 K × 32 bits
D
64 K × 32 bits
       Digital-Logic-Design       Multiplexer       GATE 2004-IT
Question 215 Explanation: 
Input: 2 lines, 8 bits each
Possible combination in ROM = (28 × (28) [size of truth table]
= 216
= 64 KB
= 64 K ×16 bits
Question 216

Using a 4-bit 2’s complement arithmetic, which of the following additions will result in an overflow?

1. 1100 
  +1100 
2. 0011 
  +0111 
3. 1111 
  +0111 
A
1 only
B
2 only
C
3 only
D
1 and 3 only
       Digital-Logic-Design       Number-Representation       GATE 2004-IT
Question 216 Explanation: 
In 2's complement arithmetic, overflow happens only when
1) Sign bit of two input numbers is 0, and the result has sign bit 1.
2) Sign bit of two input numbers is 1, and the result has sign bit 0.
So, only (2) causes overflow.
Question 217

The number (123456)8 is equivalent to

A
(A72E)16 and (22130232)4
B
(A72E)16 and (22131122)4
C
(A73E)16 and (22130232)4
D
(A62E)16 and (22120232)4
       Digital-Logic-Design       Number-Systems       GATE 2004-IT
Question 217 Explanation: 
(123456)8 = (001 010 011 100 101 110)2
= (00 1010 0111 0010 1110)2
= (A72E)16
Also,
(001 010 011 100 101 110)2
= (00 10 10 01 11 00 10 11 10)2
= (22130232)4
Question 218

The function AB’C + A’BC + ABC’ + A’B’C + AB’C’ is equivalent to

A
AC’+ AB + A’C
B
AB’+ AC’+ A’C
C
A’B+ AC’+ AB’
D
A’B + AC + AB’
       Digital-Logic-Design       Minimization       GATE 2004-IT
Question 218 Explanation: 
For given min term the K-map is,

⇒ A'C + AC' + AB'
Question 219

Consider a parity check code with three data bits and four parity check bits. Three of the code words are 0101011, 1001101 and 1110001. Which of the following are also code words?

1. 0010111             
2. 0110110         
3. 1011010             
4. 0111010 
A
1 and 3
B
1, 2 and 3
C
2 and 4
D
1, 2, 3 and 4
       Digital-Logic-Design       Number-Systems       GATE 2004-IT
Question 219 Explanation: 
Let x1, x2, x3 are data bits, and c1, c2, c3 and c4 are parity check bits.
Given transmitted codewords are

By inspection we can find the rule for generating each of the parity bits,

Now from above we can see that (I) and (III) are only codewords.
Question 220
Consider the following representation of a number in IEEE 754 single-precision floating point format with a  bias of 127.         S : 1      E : 10000001      F : 11110000000000000000000 Here S, E and F denote the sign, exponent and fraction components of the floating point representation. The decimal value corresponding to the above representation (rounded to 2 decimal places) is _______
A
-7.75
       Digital-Logic-Design       Number-Systems       GATE 2021 CS-Set-1
Question 220 Explanation: 

Sign bit S= 1. The given number is a negative number. 

Biased Exponent E = 27 + 1= 129 

Actual Exponent e = E-127 

= 129- 127

= 2

The decimal value= (-1)s x 1.M x 2e 

= (-1) 1 x 1.1111 x 22 

= - (111.11) 

= - (7 + 0.75) 

= -7.7

Question 221
Let the representation of a number in base 3 be 210. What is the hexadecimal representation of the number?
A
21
B
528
C
D2
D
15
       Digital-Logic-Design       Number-Systems       GATE 2021 CS-Set-1
Question 221 Explanation: 

On converting (210)3 in decimal, we will get:=>

 2*32+1*3=2*9+3=2110 

=>(15)16

Question 222
 Consider the following Boolean expression.
A
B
C
D
       Digital-Logic-Design       Boolean-Function       GATE 2021 CS-Set-1
Question 222 Explanation: 

XY’+Z’ is a minimal SoP expression which represents the function (X,Y,Z).

The expression XY’ + YZ’ + X’Y’Z’ can be reduced to XY’+Z’

XY’ + YZ’ + X’Y’Z

= Y’(X+X’Z’) + YZ

= Y’(X+Z’) + Y

= XY’ + Y’Z’ + YZ’

= XY’ + (Y’+Y)Z’

= XY’ + Z’.

The expression (X+Z’)(Y’+Z’) is a PoS expression which also represents the same function (X,Y,Z).

Question 223
Which one of the following choices gives the correct values of x and y?
A
x is 1 and y is 1
B
x is 0 and y is 1
C
x is 1 and y is 0
D
x is 0 and y is 0
       Digital-Logic-Design       Number-Systems       GATE 2021 CS-Set-1
Question 223 Explanation: 

C2 checks the bits d1, d3, d4, d6, d7.

C2=1, d1= 1, d3= 1, d4= 0, d6= 0, d7= 1.

The number of 1s is even. So, even parity is used in this problem.

C1 checks the bits d1, d2, d4, d5, d7.

C1=0, d1= 1, d2= 0, d4= 0, d5= x, d7= 1.

As the parity used is even parity, the value of d5 should be 0.

x=d5=0

 

C8 checks the bitsa d5, d6, d7, d8.

C8=y, d5= x=0, d6= 0, d7= 1, d8= 1.

As the parity used is even parity, the value of C8 should be 0.

C8=y=0.

x=y=0.

Question 224
Consider a 3-bit counter, designed using T flip-flops, as shown below: Assuming the initial state of the counter given by PQR as 000, what are the next three states?
A
011, 101, 000
B
001, 010, 111
C
001, 010, 000
D
011, 101, 111
       Digital-Logic-Design       Sequential-Circuits       GATE 2021 CS-Set-1
Question 224 Explanation: 

The truth table will be

RQP

Rn Qn Pn

000

011

011

101

101

000

 

Therefore, the next three states are : 101, 000 and 011

Question 225
A computer uses ternary system instead of the traditional binary system. An n bit string in the binary system will occupy
A
3+n ternary digits
B
2n/3 ternary digits
C
n(log23) ternary digits
D
n(log32 ) ternary digits
       Digital-Logic-Design       Number-Systems       ISRO-2018
Question 225 Explanation: 
→ Binary numbers are maximum 2n-1.
→ But in question they are given ternary numbers, it means 3x-1.
→ Both will take different no. of bits to represent the same number.
3x -1 = 2n -1
3x = 2n
Apply log on both side
x= log3( 2n)
x=n*log32 .
Question 226
The Boolean expression Y = (A + B' + A'B)C' is given by
A
AC'
B
BC'
C
C'
D
A
       Digital-Logic-Design       Boolean-Algebra       ISRO-2007
Question 226 Explanation: 
Y = (A + B' + A'B)C'
Y = AC' + B'C' + A'BC'
Y = (A + A'B)C' + B'C'
Y = (A + B)C' + B'C'
Y = AC' + BC' + B'C'
Y = AC' + C'(B + B') → B + B' = 1
Y = AC' + C'
Y = C'
Question 227
The circuit shown in the following figure realizes the function
A
(( A + B )’ +C ) ( D’E’ ))
B
(( A + B )’ + C ) ( DE’ ))
C
( A + ( B + C )’ ) ( D’E )
D
( A + B + C’ ) ( D’E’ )
       Digital-Logic-Design       Combinational-Circuit       ISRO-2007
Question 227 Explanation: 
The given function is equivalent to the following expression:
Y = (((A + B)' + C)' + ((D + E)')')'
Y = ((A + B)' + C)')' . (D + E)'
Y = ((A + B)' + C) (D'E')
Question 228
The circuit shown in the given figure is a
A
full adder
B
full subtractor
C
shift register
D
decade counter
       Digital-Logic-Design       Combinational-Circuit       ISRO-2007
Question 228 Explanation: 
The above diagram is full subtractor. The equation is D=X⊕Y⊕Bin and Bout=X'Bin+X'Y+YBin
Question 229
When two numbers are added in excess-3 code and the sum is less than 9, then in order to get the correct answer it is necessary to
A
subtract 0011 from the sum
B
add 0011 to the sum
C
subtract 0110 from the sum
D
add 0110 to the sum
       Digital-Logic-Design       Number-Systems       ISRO-2007
Question 229 Explanation: 
Subtract 0011 if there is no carry otherwise add 0011.
Example:
x+3
y+3
-------
(x+y+6)
Here, sum is excess-6. Hence, subtract 0011 to make it excess-3.
Question 230
In the diagram above, the inverter (NOT gate) and the AND-gates labelled 1 and 2 have delays of 9, 10 and 12 nanoseconds(ns), respectively. Wire delays are negligible. For certain values of a and c, together with the certain transition of b, a glitch (spurious output) is generated for a short time, after which the output assumes its correct value. The duration of the glitch is
A
7ns
B
9ns
C
11ns
D
13ns
       Digital-Logic-Design       Logic-Gates       ISRO-2018
Question 230 Explanation: 
Step-1: Inverter→ NOT gate(b’) will generate 9ns
Step-2: 1st AND gate(ab’) takes 19ns because combining NOT gate(9ns)+extra(10ns)
Step-3: Second AND gate(bc) takes only 12ns because we are not using inverter here.
Step-4: A glitch will take 1st AND gate(ab’) - Second AND gate(bc)
=19-12
=7ns
Question 231
The characteristic equation of an SR flip-flop is given by
A
Qn+1 = S + RQn
B
Qn+1= RQn + SQn
C
Qn+1= S + RQn
D
Qn+1 = S + RQn
       Digital-Logic-Design       Sequential-Circuits       ISRO-2007
Question 231 Explanation: 
The characteristic table of an SR flip-flop is:

So, by simplifying using k-maps:
characteristic equation of an SR flip-flop = Qn+1 = S + RQn
Question 232
By using an eight-bit optical encoder the degree of resolution that can be obtained is (approximately)
A
1.8o
B
3.4o
C
2.8o
D
1.4o
       Digital-Logic-Design       Combinational-Circuit       ISRO-2007
Question 232 Explanation: 
An optical encoder is an electromechanical device which has an electrical output in digital form proportional to the angular position of the input shaft.
Optical encoders enable an angular displacement to be converted directly into a digital form.
Encoder resolution is often referred to in bits, which are binary units: a 16 bit resolution rotary encoder will have 65,536 (216) increments per turn, or PPR.
In the given question, 8-bit optical encoder will have 28 increments Resolution = 360/2n = 360/28 = 1.4o
Question 233
The number of digit 1 present in the binary representation of 3 × 512 + 7 × 64 + 5 × 8 + 3
A
8
B
9
C
10
D
12
       Digital-Logic-Design       Number-Systems       ISRO-2007
Question 233 Explanation: 
3 × 512 + 7 × 64 + 5 × 8 + 3
= (2 + 1)× 512 + (4 + 2 + 1)× 64 + (4 + 1)× 8 + 2 + 1
= 1024 + 512 + 64 x 4 + 64 x 2 + 64 + 32 + 8 + 2 + 1
= 1024 + 512 + 256 + 128 + 64 + 32 + 8 + 2 + 1
As 1024 has ten 0’s followed by 1, 512 has nine 0’s followed by 1 and so on..
So, the expression will contain total nine 1’s and will be be represented as 11111101011.
Question 234
Any set of Boolean operators that is sufficient to represent all Boolean expressions is said to be complete. Which of the following is not complete?
A
{ AND, OR }
B
{ AND, NOT }
C
{ NOT, OR }
D
{ NOR }
       Digital-Logic-Design       Boolean-Algebra       ISRO-2018
Question 234 Explanation: 
→ NOT, AND and OR gates are basic gates
→ NAND and NOR gates are universal gates.
→ With the help of universal gates, we can construct any boolean expressions. These gates are also called functionally complete.
→ AND+NOT=NAND→ Functionally Complete
→ OR+NOT=NOR→ Functionally Complete
→ NOR→ Functionally Complete
→ AND+OR→ Not functionally complete
Question 235
0.75 decimal system is equivalent to ____ in octal system
A
0.60
B
0.52
C
0.54
D
0.50
       Digital-Logic-Design       Number-Systems       ISRO-2007
Question 235 Explanation: 
0.75 = (0.110)2
= (0.6)8
Option (A) is correct.
Question 236
In an SR latch made by cross-coupling two NAND gates, if both S and R inputs are set to 0, then it will result in
A
Q = 0, Q’ = 1
B
Q = 1, Q’ = 0
C
Q = 1, Q’ = 1
D
Indeterminate states
       Digital-Logic-Design       Sequential-Circuits       ISRO-2007
Question 236 Explanation: 
Question 237
Ring counter is analogous to
A
Toggle Switch
B
Latch
C
Stepping Switch
D
S-R flip flop
       Digital-Logic-Design       Sequential-Circuits       ISRO-2007
Question 237 Explanation: 
→ A ring counter is a type of counter composed of flip-flops connected into a shift register, with the output of the last flip-flop fed to the input of the first, making a "circular" or "ring" structure.
There are two types of ring counters:
1. A straight ring counter, also known as a one-hot counter, connects the output of the last shift register to the first shift register input and circulates a single one (or zero) bit around the ring.
2. A twisted ring counter, also called switch-tail ring counter, walking ring counter, Johnson counter, or Möbius counter, connects the complement of the output of the last shift register to the input of the first register and circulates a stream of ones followed by zeros around the ring.
Note: Ring counter is analogous to Stepping Switch
Question 238
Digital-Logic-Design
A
0.1 and 5V
B
0.6 and 3.5 V
C
0.9 and 1.75 V
D
-1.75 and 0.9 V
       Digital-Logic-Design       TTL       ISRO-2007
Question 238 Explanation: 
→ TTL high signal would be 5.00 volts exactly, and a TTL low signal 0.00 volts exactly.
→ However, real TTL gate circuits cannot output such perfect voltage levels, and are designed to accept “high” and “low” signals deviating substantially from these ideal values.
Question 239
Consider a computer system that stores a floating-point numbers with 16-bit mantissa and an 8-bit exponent, each in two’s complement. The smallest and largest positive values which can be stored are
A
1 × 10-128 and 215× 1015
B
1 × 10-256 and 215× 10255
C
1 × 10-128 and 215× 10127
D
1 × 10-128and 215– 1 × 10127
       Digital-Logic-Design       Number-Systems       ISRO-2007
Question 239 Explanation: 

According to question 16 bit mantissa and 8 bit Exponent.
Since the mantissa is always 1.xxxxxxxxx in the normalised form, no need to represent the leading 1.
Single Precision: mantissa ===> 1 bit + 15 bits
The largest mantissa value value is 215-1 (one bit meant for sign)
The largest exponent value is 27-1=127
The smallest mantissa value is 0000 0000 0000 0000(one bit is always 1) =1
The Smallest (largest negative) exponent value is 1111 1111 (which is 2’s complement form) 2-8=-128
Question 240
In comparison with static RAM memory, the dynamic RAM memory has
A
lower bit density and higher power consumption
B
higher bit density and higher power consumption
C
lower bit density and lower power consumption
D
higher bit density and lower power consumption
       Digital-Logic-Design       RAM       ISRO-2007
Question 240 Explanation: 
DRAM (Dynamic Random Access Memory)
→ DRAM stands for Dynamic Random Access Memory. It is used in most of the computers. It is the least expensive kind of RAM. It requires an electric current to maintain its electrical state. The electrical charge of DRAM decreases with time that may result in loss of DATA.
→ DRAM is recharged or refreshed again and again to maintain its data. The processor cannot access the data of DRAM when it is being refreshed. That is why it is slow.
SRAM (Static Random Access Memory)
→ SRAM stands for Static Random Access Memory. It can store data without any need of frequent recharging. CPU does not need to wait to access data from SRAM during processing. That is why it is faster than DRAM. It utilizes less power than DRAM.
→ SRAM is more expensive as compared to DRAM. It is normally used to build a very fast memory known as cache memory
Question 241
The Hexadecimal equivalent of 01111100110111100011 is
A
CD73E
B
ABD3F
C
7CDE3
D
FA4CD
       Digital-Logic-Design       Number-Systems       ISRO-2007
Question 241 Explanation: 
Binary number = 0111 1100 1101 1110 0011
7 C D E 3

(7CDE3)16
Question 242
One approach to handling fuzzy logic data might be to design a computer using ternary (base-3) logic so that data could be stored as “true,” “false,” and “unknown.” If each ternary logic element is called a flit, how many blits are required to represent at least 256 different values?
A
4
B
5
C
6
D
7
       Digital-Logic-Design       Number-Systems       ISRO-2007
Question 242 Explanation: 
In binary representation, to represent 256 different values, you need log_2 (256) = 8 bits. Similarly in ternary representation, you would require log_3 (256) which is 5.something. Now rounding off to the upper integer (since number of bits is an integer) and we get 6
Question 243
If a variable can take only integral values from 0 to n, where n is an integer, then the variable can be represented as a bit field whose width is (the log in the Solutions are to the base 2, and [log n] means the floor of log n)
A
[log(n)] + 1 bits
B
[log (n-1)) + 1 bits
C
[log (n+1)] + 1 bits
D
None of the above
       Digital-Logic-Design       Number-Systems       ISRO-2018
Question 243 Explanation: 
Question 244
Given √(224)r = 13r the value of radix r is
A
10
B
8
C
6
D
5
       Digital-Logic-Design       Number-Systems       ISRO-2018
Question 244 Explanation: 
√(224)r = 13r
For f(x) to be maximum
f'(x) = 4x - 2 = 0
⇒ x = 1/2
So at x = 1/2, f(x) is an extremum (either maximum or minimum).
f(2) = 2(2)2 - 2(2) + 6 = 10
f(1/2) = 2 × (1/2)2 - 2 × 1/2 + 6 = 5.5
f(0) = 6
So, the maximum value is at x=2 which is 10 as there are no other extremum for the given function.
Question 245
The Boolean theorem AB + A’C + BC = AB + A’C corresponds to
A
(A + B) ∙ (A’ + C) ∙ (B + C) = (A + B) ∙ (A’ + C)
B
AB + A’C + BC = AB + BC
C
AB + A’C + BC = (A + B) ∙ ( A ‘+ C) ∙ (B + C)
D
(A + B) ∙ (A’ + C) ∙ (B + C) = AB + A’C
       Digital-Logic-Design       Boolean-algebra       ISRO CS 2008
Question 245 Explanation: 
(X+Y)*(X+Z)*(Y+Z)=(X+Y)*(X+Z) Consensus Law
XY+XZ+YZ=XY+XZ Consensus Law

For min-term: AB + A'C +BC = AB + A'C
AND for max-term : ( A + B ).( A' + C ).( B + C ) = ( A + B ).(A' + C )
Question 246
In the given network of AND and OR gates, f can be written as
A
X0X1X2 … Xn + X1X2 … Xn + X2X3 … Xn + ⋯ + Xn
B
X0X1 + X2X3 + … Xn-1 Xn
C
X0 + X1 + X2 + … + Xn
D
X0X1 + X3 … Xn−1 + X2X3 + X5 … Xn−1 + ⋯ + Xn−2Xn−1 + Xn
E
None of the above
       Digital-Logic-Design       Boolean-algebra       ISRO CS 2008
Question 246 Explanation: 
(X0X1+X2)X3+X4)X5+⋯+XN
=(X0X1X3+X2X3+X4)X5+⋯+XN

=X0X1X3X5+X2X3X5+X4X5+⋯+XN

=X0X1X3X5⋯XN−1+X2X3X5⋯XN−1+X4X5X7⋯XN−1+⋯+XN
Question 247
If N2 = (7601)8 where N is a positive integer, then the value of N is
A
(241)5
B
(143)6
C
(165)7
D
(39)16
       Digital-Logic-Design       Number-system       ISRO CS 2008
Question 247 Explanation: 
N2 = (7601)8
N2 = 7*8*8*8 + 6*8*8 + 0 + 1*8
N2 = 3969
N = (63)10
Now, (241)5 = 2*5*5 + 4*5 + 1 = 71
Option (A) is incorrect.
(143)6 = 1*6*6 + 4*6 + 3 = 63
Option (B) is correct.
Question 248
If (12x)3 = (123)x then the value of x is
A
3
B
3 or 4
C
2
D
None of these
       Digital-Logic-Design       Number-system       ISRO CS 2008
Question 248 Explanation: 
Given, (12x)3 = (123)x
Since LHS has 3 as the base and RHS has ‘x’ base,
1 * 3*3 + 2 * 3 + x * 1 = 1 * x*x + 2 * x + 3
9 + 6 + x = x2 + 2x + 3
x2 + x - 12 = 0
x2 + 4x - 3x - 12 = 0
x( x + 4 ) - 3(x + 4) = 0
(x + 4)(x - 3) = 0
x = 3 and -4
But, both the values are infeasible.

Alternative explanation :
According to the rules of number systems , the numbers present in a number system should not be greater than the base of the number system.
According to LHS , (12x)3 tells us that the value of x should be less than 3.
According to RHS , (123)x tells us that the value of x should be greater than 3 as largest digit in 123 is 3.
Therefore, any combination is not possible.
Question 249
A computer uses 8 digit mantissa and 2 digit exponent. If a = 0.052 and b = 28E + 11 then b + a – b will
A
result in an overflow error
B
result in an underflow error
C
be 0
D
be 5.28 E + 11
       Digital-Logic-Design       Number-system       ISRO CS 2008
Question 249 Explanation: 

The computer uses 8 digit mantissa and 2 digit exponent:

a = 0.052 We can represent the number in M*E So a= 0.052 = 0.52*10-1

mantissa = 0.52, exponent = −1.

b = 28E+11, We can represent the number in M*E So b = 28E+11= 0.28*1013

mantissa = 0.28, exponent = 13.

To add b+a, Small exponent number, a is shifted

to 13-(-1) = 14 places to right side

a = 0.0000000000000052E+13

From the given data computer uses only 8 digit mantissa, so digits beyond 8th position will be discarded.

So a = 0.00000000E+13 = 0.0 E+13

b + a = (0.28E + 13) + (0.0E + 13 )

= 0.28E + 13

Then b + a - b = (0.28E + 13) - (0.28E + 13)

= 0
Question 250
The Boolean expression ( A + C’)(B’+ C’) simplifies to
A
C’ + AB’
B
C’ (A’ + B)
C
B’C’ + AB’
D
None of these.
       Digital-Logic-Design       Boolean-algebra       ISRO CS 2008
Question 250 Explanation: 

The following expression can be simplified as:

(A + C')(B'+ C')

= AB' + AC' + B'C' + C
'
= AB' + C'(A + B' + 1) // 1 + A = 1

= AB' + C'
Question 251
In the expression A'(A’ + B’) by writing the first term A as A + 0, the expression is best simplified as
A
A + AB
B
AB
C
A'
D
A + B
       Digital-Logic-Design       Boolean-Algebra       ISRO CS 2008
Question 251 Explanation: 

A'(A’ + B’)

This expression can be simplified as:

= A'A' + A'B'

= A' + A'B'

= A'(1 + B') // 1 + B' = 1

= A'
Question 252
How many 128×8 bit RAMs are required to design 32K×32 bit RAM?
A
512
B
1024
C
128
D
32
       Digital-Logic-Design       RAM       ISRO-2017 May
Question 252 Explanation: 
Step-1: RAM size required is 32Kx32 bits
= 32x1024x32 bits. [Note: 1k=1024 bytes]

Step-2: Given RAM chip capacity is 128x8 bits
Step-3: Required size/Given size
=(32*1024*32) / (128*8)
=1024
Question 253
The logic operations of two combinational circuits in Figure-I and Figure-II are
A
entirely different
B
identical
C
complementary
D
dual
       Digital-Logic-Design       Sequential-Circuits       ISRO CS 2008
Question 253 Explanation: 

The Two functions are entirely different as:

Figure 1: The logic gates derive the following function:

F1 = ((X + Y')' + X)'

= ((X + Y')')'. X'

= (X + Y'). X'

= XX' + X'Y'

= X'Y'

Figure 2: It is simple AND gate which has 1 input already complimented.

F2 = XY'

So, these two functions are entirely different.
Question 254
The output Y of the given circuit
A
1
B
0
C
X
D
X’
       Digital-Logic-Design       Sequential-Circuits       ISRO CS 2008
Question 254 Explanation: 
The above function is implemented using XOR function, and gives output as 1 only when both the inputs are different. In this function, both the inputs of the first XOR gate are set to 0. Then the output is also 0 and the further two gates are also getting 0 as both their inputs. So, the final output Y is 0.
Question 255
Which of the following is not a valid rule of XOR?
A
0 XOR 0 = 0
B
1 XOR 1 = 1
C
1 XOR 0 = 1
D
B XOR B = 0
       Digital-Logic-Design       Boolean-Algebra       ISRO CS 2008
Question 255 Explanation: 

XOR gate only returns 1 as the output when both inputs are different and in every other case, it returns 0.

So, options (A), (C) and (D) are correct.
Question 256
What is the minimum number of two-input NAND gates used to perform the function of two input OR gate
A
One
B
Two
C
Three
D
Four
       Digital-Logic-Design       Logic-Gates       ISRO-2017 May
Question 256 Explanation: 
Question 257
When two n-bit binary numbers are added the sum will contain at the most
A
n bits
B
(n+3) bits
C
(n+2) bits
D
(n+1) bits
       Digital-Logic-Design       Number-Systems       ISRO-2017 May
Question 257 Explanation: 
→ When two n-bit binary numbers are added the sum will contain at the most (n+1) bits
Example = 2 Decimal numbers are (7)10 and (7)10
= Equivalent binary numbers are (111)2 + (111)2
= Adding two binary numbers, the final result will be n+1 number (1110)2
Question 258
The 2-input XOR has a high output only when the input values are
A
low
B
high
C
same
D
different
       Digital-Logic-Design       Logic-Gates       ISRO-2017 May
Question 258 Explanation: 
The 2-input XOR(⊕) has a high output only when the input values are different.

Question 259
(1217)8 is equivalent to
A
(1217)16
B
(028F)16
C
(2297)1o
D
(0B17)16
       Digital-Logic-Design       Number-Systems       ISRO-2017 May
Question 259 Explanation: 
(1217)8=(001 010 001 111)2
=(0010 1000 1111)2
=(2 8 F)16
Question 260
Which of the following is termed as minimum error code
A
Binary code
B
Gray code
C
Excess 3 code
D
Octal code
       Digital-Logic-Design       Number-system       ISRO CS 2008
Question 260 Explanation: 

Gray codes are less error-prone for mechanical devices that involve making and breaking electrical circuits because they only change in one bit position at a time.

So, they are considered as the minimum error code.
Question 261
Advantages of synchronous sequential circuits over asynchronous one is
A
Lower hardware requirement
B
Better noise immunity
C
Faster operation
D
None of the above
       Digital-Logic-Design       Sequential-Circuits       ISRO-2017 May
Question 261 Explanation: 
Excluded for evaluation.
Question 262
Repeated execution of simple computation may cause compounding of
A
round-off errors
B
syntax errors
C
run-time errors
D
logic errors
       Digital-Logic-Design       Compilers-and-Parsers       ISRO CS 2008
Question 262 Explanation: 
→A syntax error in computer science is an error in the syntax of a coding or programming language, entered by a programmer. Syntax errors are caught by a software program called a compiler, and the programmer must fix them before the program is compiled and then run
→A runtime error is a program error that occurs while the program is running.
→A logic error is a bug in a program that causes it to operate incorrectly, but not to terminate abnormally (or crash). A logic error produces unintended or undesired output or other behaviour, although it may not immediately be recognized.
→Roundoff error is the difference between an approximation of a number used in computation and its exact (correct) value. In certain types of computation, roundoff error can be magnified as any initial errors are carried through one or more intermediate steps and repeated execution.
Question 263
How many 2-input multiplexers are required to construct a 2<sup>10<sup>-input multiplexer?
A
1023
B
31
C
10
D
127
       Digital-Logic-Design       Multiplexer       ISRO CS 2008
Question 263 Explanation: 

210 x1 MUX has 210 inputs.
Level-1 has 29 (=512) 2x1 multiplexers which take 2*29 = 210 inputs and produces 512 outputs.
Similarly,
Level-2 has 256 MUX.
Level-3 has 128 MUX.
Level-4 has 64 MUX.
Level-5 has 32 MUX.
Level-6 has 16 MUX.
Level-7 has 8 MUX.
Level-8 has 4 MUX.
Level-9 has 2 MUX.
Level-10 has 1 MUX.
Total number of Multiplexers= 512+256+128+64+32+16+8+4+2+1
=1023
Question 264
The minimum number of NAND gates required to implement the Boolean function A + AB’+ AB’C is equal to
A
0
B
1
C
4
D
7
       Digital-Logic-Design       Boolean-Function       ISRO-2016
Question 264 Explanation: 
A + AB’+ AB’C = A(1+B’+B’C) = A
No GATE is required to implement the function A.
Question 265
The minimum Boolean expression for the following circuit is:
A
AB + AC + BC
B
A + BC
C
A + B
D
A + B + C
       Digital-Logic-Design       Boolean-Expression       ISRO-2016
Question 265 Explanation: 
If the switches are in parallel then use “+”, and if they are serial then use “ ”.
A(B+C) + AB + (A+B)C = AB + AC + AB + AC + BC
= (AB+AB) + (AC+AC) + BC
= AB + AC + BC
Question 266
For a binary half-subtractor having two inputs A and B, the correct set of logical expressions for the outputs D (= A minus B) and X (=borrow) are
A
D = AB + A’B , X = A’B
B
D = A’B + AB’ , X = AB’
C
D = A’B + AB’ , X = A’B
D
D = AB + A’B , X = AB’
       Digital-Logic-Design       Combinational-Circuit       ISRO-2016
Question 266 Explanation: 
The function table for the Half Subtractor is as follows
A-B= D= A’B + AB’
X= A’B
Question 267
Consider the following gate network Which one of the following gates is redundant?
A
Gate No. 1
B
Gate No. 2
C
Gate No. 3
D
Gate No. 4
       Digital-Logic-Design       Logic-Gates       ISRO-2016
Question 267 Explanation: 
W’ + W’Z + Z’XY = W’(1+Z) + Z’XY
= W’ + Z’XY
The term W’Z is redundant which is represented by GATE 2.
Question 268
The dynamic hazard problem occurs in
A
combinational circuit alone
B
sequential circuit only
C
Both (a) and (b)
D
None of the above
       Digital-Logic-Design       Hazards       ISRO-2016
Question 268 Explanation: 
→ A dynamic hazard is the possibility of an output changing more than once as a result of a single input change.
→ Dynamic hazards often occur in larger logic circuits where there are different routes to the output (from the input).
→ If each route has a different delay, then it quickly becomes clear that there is the potential for changing output values that differ from the required / expected output. e.g.
→ A logic circuit is meant to change output state from 1 to 0, but instead changes from 1 to 0 then 1 and finally rests at the correct value 0. This is a dynamic hazard.
→ As a rule, dynamic hazards are more complex to resolve, but note that if all static hazards have been eliminated from a circuit, then dynamic hazards cannot occur.
Question 269
The logic circuit given below converts a binary code y1,y2,y3 into
A
Excess-3 code
B
Gray code
C
BCD code
D
Hamming Code
       Digital-Logic-Design       Number-Systems       ISRO-2016
Question 269 Explanation: 
X1= Y1
X2= Y1⊕ Y2
X3= Y2 ⊕ Y3
Question 270
The circuit given below in the figure below is
A
An oscillating circuit and its output is a square wave
B
The one whose output remains stable in ‘1’ state
C
The one having output remains stable in ‘0’ state
D
has a single pulse of three times propagation delay
       Digital-Logic-Design       Logic-Gates       ISRO-2016
Question 270 Explanation: 
The square wave has alternating amplitudes(0 and 1) with duty cycle 1.
An odd number of cascaded NOT gates produce a square wave.

Note: Duty cycle= Ratio of durations in which the circuit is ON and OFF in a cycle.
Question 271
If 12A7C16 = X8, then the value of X is
A
224174
B
425174
C
6173
D
225174
       Digital-Logic-Design       Number-Systems       ISRO-2016
Question 271 Explanation: 
Given, (12A7C)16 = (0001 0010 1010 0111 1100)2
MAke blocks of 3 bits each from LSB to MSB.
(Note: In the last block append zeros (as MSBs) if number bits is not three)
(000 010 010 101 001 111 100)
Each of the above blocks represents a digit in base 8 and they can be converted to base 8 as shown below.
= (0 2 2 5 1 7 4)8
Question 272
The Excess-3 code is also called
A
Cyclic Redundancy Code
B
Weighted Code
C
Self-Complementing Code
D
Algebraic Code
       Digital-Logic-Design       Number-Systems       ISRO-2016
Question 272 Explanation: 
Excess-3 code is also called Self-Complementing Code. Because 1’s complement of an excess-3 number is equivalent to 9’s complement of the corresponding decimal digit.
→ In excess-3 code, each of the 4-bit numbers represents decimal digit which is 3 less than the actual decimal digit. So the bits have no fixed weight.
Excess-3 code is neither CRC nor Algebraic Code which is used for error detection and/or correction.
Question 273
The simplified SOP (Sum of Product) form the Boolean expression (P + Q’ + R’)(P + Q’ + R)(P + Q + R’)
A
(P’Q + R)
B
(P + Q’R’)
C
(P Q’ + R )
D
(PQ + R)
       Digital-Logic-Design       Boolean-Expression       ISRO-2016
Question 273 Explanation: 
Question 274
Which of the following binary number is the same as its 2’s complement?
A
1010
B
0101
C
1000
D
1001
       Digital-Logic-Design       Number-Systems       ISRO-2016
Question 274 Explanation: 
Hint: Number of bits=4
(Decimal value of maximum 4-bit number +1 )/2= (15+1)/2=8
Question 275
The functional difference between SR flip-flop and JK flip-flop is that
A
JK Flip-flop is faster than SR flip-flop
B
JK flip-flop has a feedback path
C
JK flip-flop accepts both inputs 1
D
None of them
       Digital-Logic-Design       Sequential-Circuits       ISRO-2016
Question 275 Explanation: 
-> JK flip flop accepts input J=K=1. When J=K=1, the state of the flip-flop gets complimented. But it's not a valid input in SR flip-flop.
-> JK flip flop doesn’t have a feedback path.
Question 276
The range of integers that can be represented by n bit 2’s complement number system is:
A
-2n-1 to (2n-1 – 1)
B
-(2n-1 – 1)to (2n-1 – 1)
C
-2n-1 to (2n-1 )
D
-(2n-1 + 1)to (2n-1 – 1)
       Digital-Logic-Design       Number-system       ISRO CS 2009
Question 276 Explanation: 
The range of integers that can be represented by n bit 2’s complement number system is -2n-1 to (2n-1 – 1).
Question 277
A processor that has carry, overflow and sign flag bits as part of its program status word (PSW) performs addition of the following two 2’s complement numbers 01001101 and 11101001. After the execution of this addition operation, the status of the carry, overflow and sign flags, respectively will be
A
1, 1, 0
B
1, 0, 0
C
0, 1, 0
D
1, 0, 1
       Digital-Logic-Design       Number-system       ISRO CS 2009
Question 277 Explanation: 

Question 278
The two numbers given below are multiplied using the Booth’s algorithm Multiplicand: 0101 1010 1110 1110 Multiplier: 0111 0111 1011 1101 How many additions/subtractions are required for the multiplication of the above two numbers?
A
6
B
8
C
10
D
12
       Digital-Logic-Design       Booth\'s-algorithm       ISRO CS 2009
Question 278 Explanation: 

Question 279
The addition of 4-bit, two’s complement, binary numbers 1101 and 0100 results in
A
0001 and an overflow
B
1001 and no overflow
C
0001 and no overflow
D
1001 and an overflow
       Digital-Logic-Design       Number-Systems       ISRO CS 2009
Question 279 Explanation: 
Number one is 0100 (4-Decimal value)
Another number is 1101(-3 is decimal value)
Adding of -3 and 4, the result is 1 and there is no overflow
Question 280
The switching expression corresponding to F(A,B,C,D)= Σ(1,4,5,9,11,12) is:
A
BC’D’ + A’C’D + AB’D
B
ABC’ + ACD + B’C’D
C
ACD’ + A’BC’ + AC’D’
D
A’BD + ACD’ + BCD’
       Digital-Logic-Design       K-Map       ISRO CS 2009
Question 280 Explanation: 
The K-Map for the boolean function of four variables can be drawn as:
Question 281
Consider the following boolean function of four variables, f (w, x, y,z) = Σ(1, 3, 4, 6, 9, 11, 12, 14], the function is
A
Independent of one variable
B
Independent of two variables
C
Independent of three variables
D
Dependent on all variables
       Digital-Logic-Design       Boolean-Function       ISRO CS 2009
Question 281 Explanation: 

w and y are not needed to represent the function f. So f is independent of two variables.
Question 282
Evaluate (X XOR Y) XOR Y?
A
All 1’s
B
All 0’s
C
X
D
Y
       Digital-Logic-Design       Boolean-Expression       ISRO CS 2011
Question 282 Explanation: 

Question 283
What is the decimal value of the floating-point number C1D00000 (hexadecimal notation)? (Assume 32-bit, single precision floating point IEEE representation)
A
28
B
-15
C
-26
D
-28
       Digital-Logic-Design       Number-Systems       ISRO CS 2011
Question 283 Explanation: 
Floating Point number in Hexadecimal = C1D00000
Floating Point number in Binary = 1100 0001 1101 0000 0000 0000 0000 0000
In 32-bit, single precision floating point IEEE representation, first MSB represents sign of mantissa: 1 is used to represent a negative mantissa and 0 for a positive value of mantissa, next 8 bits are for exponent value and then 23 bits represents mantissa.
Value of exponent = 131-127 = 4
Mantissa = -1.1010000 0000 0000 0000 0000
Floating point number = -1.1010000 0000 0000 0000 0000
Converting the above one into decimal no -(1*20+1*2-1*0*2-2+1*2-2+0* 2-3 +.....)
= -(1+½+⅛)=-13/8
Decimal value =sign*Exponent*mantissa=1*4*-13/8

= -26
Question 284
In Boolean algebra, rule (X+Y)(X+Z) =
A
Y+XZ
B
X+YZ
C
XY+Z
D
XZ+Y
       Digital-Logic-Design       Boolean-Algebra       ISRO CS 2011
Question 284 Explanation: 
in Boolean algebra,
(X+Y)(X+Z) = X + XZ + XY + YZ
= X(1 + Z + Y) + YZ // as (1 + A = A)
= X.1 + YZ
= X + YZ
Question 285
In an RS flip-flop, if the S line (Set line) is set high (1) and the R line (Reset line) is set low (0), then the state of the flip-flop is
A
Set to 1
B
Set to 0
C
No change in state
D
Forbidden
       Digital-Logic-Design       Flip=flops       ISRO CS 2011
Question 285 Explanation: 
Question 286
The output expression of the following gate network is
A
X. Y + X’ Y’
B
X. Y + X. Y
C
X. Y
D
X + Y
       Digital-Logic-Design       Boolean-Function       ISRO CS 2011
Question 286 Explanation: 
AND operation is represented by ‘.’ and OR operation is representation is represented with ‘+’. According to diagram, option (A) is correct
Question 287
Number of chips (128 x 8 RAM) needed to provide a memory capacity of 2048 bytes
A
2
B
4
C
8
D
16
       Digital-Logic-Design       Memory-interfacing       ISRO CS 2011
Question 287 Explanation: 
Given memory capacity is 2048 Bytes RAM memory is 128x8
Number of chips needed are = total memory capacity / RAM memory
= 2048 bytes / 128 x 8 =2048x8/128x8
= 16
Question 288
The hamming distance between the octets of 0xAA and 0x55 is
A
7
B
5
C
8
D
6
       Digital-Logic-Design       Number-system       ISRO CS 2011
Question 288 Explanation: 
→ The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.
→ In other words, it measures the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other.
→ Given HexaDecimal numbers are 0xAA and 0x55.
Decimal equivalent of 0xAA is 170
Binary form of 0xAA is 1010 1010
Decimal equivalent of 0x55 is 85
Binary form of 0xAA is 0101 0101
The two numbers binary length length is 8.
→ If you observe all the bits of above two binary numbers, both numbers have different bits in all positions.
→ So according to definition , the number of positions at which the corresponding symbols are different which is 8.
Question 289
How many 3-to-8 line decoders with an en