Chapter 2 • Digital Logic 73

(a) 2−40 (b) 2−9 transition(s) (change of logic levels) occur(s) at B during
(c) 222 (d) 231 the interval from 0 to 10 ns?
(GATE 2003: 2 Marks) Logic 1
A Logic 0
22. A 1-input, 2-output synchronous sequential circuit Time 0 1 2 3 4 5 6 7 8 9 10 11
behaves as follows: (ns)
Let zk, nk denote the number of 0’s and 1’s, respectively,
(a) 1 (b) 2
in initial k bits of the input (zk + nk= k). The circuit out-
puts 00 until one of the following conditions holds. (c) 3 (d) 4
(A)  zk − nk = 2. In this case, the output at the kth and all (GATE 2003: 2 Marks)
subsequent clock ticks is 10. 25. A Boolean function x′y′ + xy + x′y is equivalent to
(B)  nk − zk = 2. In this case, the output at the kth and all
(a) x′ + y′ (b) x + y
subsequent clock ticks is 01.
(c) x + y′ (d) x′ + y
What is the minimum number of states required in the
state transition graph of the above circuit? (GATE 2004: 1 Mark)
(a) 5 (b) 6 26. In an SR latch made by cross-coupling two NAND gates,
(c) 7 (d) 8 if both S and R inputs are set to 0, then it will result in
(GATE 2003: 2 Marks) (a) Q = 0, Q ′ = 1
(b) Q = 1, Q ′ = 0
23. The literal count of a Boolean expression is the sum of
the number of times each literal appears in the expres- (c) Q = 1, Q ′ = 1
sion. For example, the literal count of (xy + xz′) is 4. (d) Indeterminate states
What are the minimum possible literal counts of the (GATE 2004: 1 Mark)
product-of-sum and sum-of-product representations,
respectively, of the function given by the following 27. If 73x (in base-x number system) is equal to 54y (in base-y
­Karnaugh map? Here, × denotes “don’t care”. number system), the possible values of x and y are
(a) 8, 16 (b) 10, 12
zw 00 01 11 10 (c) 9, 13 (d) 8, 11
xy (GATE 2004: 1 Mark)
00 × 1 0 1 28. What is the result of evaluating the following two
01 0 1 × 0 expressions using three-digit floating point arithmetic
11 1 × × 0 with rounding?
10 × 0 0 × (113 + −111) + 7.51
113 + (−111 + 7.51)
(a) (11, 9) (b) (9, 13)
(a) 9.51 and 10.0, respectively
(c) (9, 10) (d) (11, 11)
(b) 10.0 and 9.51, respectively
(GATE 2003: 2 Marks) (c) 9.51 and 9.51, respectively
24. Consider the following circuit composed of XOR gates (d) 10.0 and 10.0, respectively
and non-inverting buffers. (GATE 2004: 1 Mark)
29. Consider a multiplexer with X and Y as data inputs and
A B 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
d1 = 2 d2 = 4
additional hardware?
The non-inverting buffers have delays d1 = 2 ns and (a) R to X, 1 to Y, T to Z
d2 = 4 ns as shown in the figure. Both XOR gates and (b) T to X, R to Y, T to Z
all wires have zero delay. Assume that all gate inputs,
(c) T to X, R to Y, 0 to Z
outputs and wires are stable at logic level 0 at time 0. If
the following waveform is applied at input A, how many (d) R to X, 0 to Y, T to Z
(GATE 2004: 2 Marks)

Ch wise GATE_CSIT_CH02_Digital Logic.indd 73 11/13/2018 9:43:05 AM

30. A circuit outputs a digit in the form of 4 bits, where 0 is (a) 1100 0100 (b) 1001 1100
represented by 0000, 1 by 0001, …, 9 by 1001. A combi- (c) 1010 0101 (d) 1101 0101
national circuit is to be designed which takes these 4 bits
as input and output 1 if the digit ≥ 5, and 0 otherwise. (GATE 2004: 2 Marks)
If only AND, OR and NOT gates are used, what is the 35. Consider the following circuit.
minimum number of gates required?
X
(a) 2 (b) 3
(c) 4 (d) 5
Y f
(GATE 2004: 2 Marks)
31. Which are the essential prime implicants of the follow- Z
ing Boolean function?
f (a, b, c) = a′c + ac′ + b′c Which one of the following is TRUE?
(a) a′c and ac′ (b) a′c and b′c (a) f is independent of X.
(c) a′c only (d) ac′ and bc′ (b) f is independent of Y.
(c) f is independent of Z.
(GATE 2004: 2 Marks)
(d) None of X, Y, Z is redundant.
32. Consider the partial implementation of a 2-bit counter (GATE 2005: 1 Mark)
using T flip–flops following the sequence 0-2-3-1-0, as
shown in the following figure. 36. 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) −2(2n − 1 − 1) to (2n − 1 − 1)
X (c) −2n − 1 to 2n − 1
T2 Q2 T1 Q1 (d) −2(2n − 1+ 1) to (2n − 1 − 1)
(GATE 2005: 1 Mark)
MSB LSB
37. The hexadecimal representation of 6578 is
CLK (a) 1AF (b) D78
(c) D71 (d) 32F
To complete the circuit, the input X should be
(GATE 2005: 1 Mark)
(a) Q2′ (b) Q2 + Q1 38. The switching expression corresponding to f (A, B, C,
(c) (Q1 ⊕ Q2 ) ′ (d) Q1 ⊕ Q2 D) = ∑(1,4,5,9,11,12) is
(GATE 2004: 2 Marks) (a) BC ′D ′+ A′C ′D + AB ′D
(b) ABC ′+ ACD + B ′C ′D
33. A 4-bit carry look-ahead adder, which adds two 4-bit (c) ACD ′+ A′BC ′+ AC ′D ′
numbers, is designed using AND, OR, NOT, NAND,
(d) A′BD + ACD ′+ BCD ′
NOR gates only. Assuming that all the inputs are avail-
able in both complemented and uncomplemented forms (GATE 2005: 1 Mark)
and the delay of each gate is one time unit, what is the 39. Consider the following circuit involving a positive-edge
overall propagation delay of the adder? Assume that the triggered D flip–flops.
carry network has been implemented using two-level
AND-OR logic. A
(a) 4 time units (b) 6 time units X D Q
Y
(c) 10 time units (d) 12 time units
(GATE 2004: 2 Marks) CLK
Q´
34. Let A = 1111 1010 and B = 0000 1010 be two 8-bit 2’s
complement numbers. Their product in 2’s comple- Consider the following timing diagram. Let Ai represent
ment is the logic level on the line A in the ith clock period.

Ch wise GATE_CSIT_CH02_Digital Logic.indd 74 11/13/2018 9:43:07 AM