subject – RBR

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 GATE 2019

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 GATE 2019

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 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 GATE 2019

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 GATE 2019

Question 5 Explanation:

f = Σ(0, 2, 5, 7, 8, 10, 13, 15)

Question 6

Consider three 4-variable functions f₁, f₂ and f₃, which are expressed in sum-of-minterms as

f₁ = Σ(0, 2, 5, 8, 14),  f₂ = Σ(2, 3, 6, 8, 14, 15),  f₃ = Σ(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 GATE 2019

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

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 7 Explanation:

Number of registers is 32. Only one register has to be selected at any instant of time.
A 2⁵x1 Multiplexer with 5 select lines selects one of the 32(= 2⁵ )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 8

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 8 Explanation:

The size of the decoder required is 10x 210i.e 10x 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 9

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 9 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 10

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 10 Explanation:

Given numbers are 0x42200000 and 0xC1200000 which are stored in the registers R1 and R2, respectively.

Question 11

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

Question 11 Explanation:

Question 12

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

Question 12 Explanation:

Let,

Now lets draw characteristic table,
D₁ = Q₀
D₀ = in

Question 13

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

₇

₆

₅

₄

₃

₂

₁

₀

where the position of the binary point is between b₃ and b₂ . Assume b₇ 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

Question 13 Explanation:

(i) (31.5)₁₀ = (11111.100)₂ = 2⁴ + 2³ + 2² + 2¹ + 2⁰ + 2^-1
= 16 + 8 + 4 + 2 + 1 + 0.5
= (31.5)₁₀
(ii) (0.875)₁₀ = (00000.111)₂
= 2^-1 + 2^-2 + 2^-3
= 0.5 + 0.25 + 0.125
= (0.875)₁₀
(iii) (12.100)₁₀
It is not possible to represent (12.100)₁₀
(iv) (3.001)₁₀ It is not possible to represent (3.001)₁₀

Question 14

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
D	6

Digital-Logic-Design K-Map Gate 2018

Question 14 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 15

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 2ⁱ
B	2^-f to (2ⁱ - 2^-f)
C	0 to 2ⁱ
D	0 to (2ⁱ - 2^-f)

Digital-Logic-Design Number-Systems Gate 2017 set-01

Question 15 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
= (2^n-f - 2 ^-f)
= (2ⁱ - 2 ^-f)

Question 16

When two 8-bit numbers A₇...A₀ and B₇...B₀ in 2’s complement representation (with A₀ and B₀ as the least significant bits) are added using a ripple-carry adder, the sum bits obtained are S₇...S₀ and the carry bits are C₇...C₀. An overflow is said to have occurred if

A	the carry bit C₇ is 1
B	all the carry bits (C₇,…,C₀) are 1
C
D

Digital-Logic-Design Ripple-Carry-Adder Gate 2017 set-01

Question 16 Explanation:

⇾ Overflow may occur when numbers of same sign are added
i.e., A₇ = B₇
⇾ Overflow can be detected by checking carry into the sign bits (C_in) and carry out of the sign bits (C_out).
⇾ Overflow occurs iff A₇ = B₇ and C_in ≠ C_out
These conditions are equivalent to

Consider

Here A₇ = B₇ = 1 and S₇ = 0
This happens only if C_in = 0

Carry out C_out=1 when

Similarly, in case of

C_in=1 and C_out will be 0.

Question 17

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-01

Question 17 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 18

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 Q₀ and Q₁ are set to 1 (before the 1^st clock cycle). The outputs

A
B
C
D

Digital-Logic-Design Sequential-Circuits Gate 2017 set-01

Question 18 Explanation:

Question 19

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-02)

Question 19 Explanation:

X = (BCA9)₁₆
Each hexadecimal digit is equal to a 4-bit binary number. So convert
X = (BCA9)₁₆ 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)₂
Note: Two zeroes added at host significant position to make number bits of a multiple of 3 (16 + 2 = 18)
X = (136251)₈

Question 20

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 × 10¹
B	1.45 × 10^-1
C	2.27 × 10^-1
D	2.27 × 10¹

Digital-Logic-Design Number-Systems GATE 2017(set-02)

Question 20 Explanation:

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

Question 21

Consider a quadratic equation x² - 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-02)

Question 21 Explanation:

x² - 13x + 36 = 0 ⇾(1)
Generally if a, b are roots.
(x - a)(x - b) = 0
x² - (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
5_b = 5₁₀
6₁₀ = 6₁₀
13_b = b+3
11 = b+3
b = 8
Now check with ab = 36
5_b × 6_b = 36_b
Convert them into decimals
5_b × 6_b = (b×3) + 6₁₀
30 = b × 3 + 6
24 = b × 3
b = 8
∴ The required base = 8

Question 22

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-02)

Question 22 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 23

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-02)

Question 23 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 24

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-02)

Question 24 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 25

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 T₁ and T₀ are

A
B
C
D

Digital-Logic-Design Sequential-Circuits GATE 2017(set-02)

Question 25 Explanation:

By using above excitation table,

Question 26

Consider the Boolean operator with the following properties:

Then x#y is equiavlent to

A
B
C
D

Digital-Logic-Design Boolean-Algebra 2016 set-01

Question 26 Explanation:

Ex-OR satisfies all the properties. Hence,

Question 27

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 2016 set-01

Question 27 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)₁₀
Hence, 1111 1111 1111 0101 = -11

Question 28

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 ﬂip-ﬂops required to implement this counter is __________.

A	4
B	5
C	6
D	7

Digital-Logic-Design Sequential-Circuits 2016 set-01

Question 28 Explanation:

Given sequence is 0-1-0-2-0-3
There are 3 transitions from 0.
Hence ⌈log₂³⌉ = 2 bits have to be added to the existing 2 bits to represent 4 unique states.

Question 29

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

The minimal sum of products form of the output X is

A
B
C
D

Digital-Logic-Design Multiplexer 2016 set-01

Question 29 Explanation:

Output of 1^st MUX is

Now

Question 30

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 2016 set-01

Question 30 Explanation:

Formula: θ(log_k (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 θ(log₂ (n)).

Question 31

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

Question 31 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 32

Let, x₁⊕x₂⊕x₃⊕x₄ = 0 where x₁, x₂, x₃, x₄ are Boolean variables, and ⊕ is the XOR operator. Which one of the following must always be TRUE?

A	x₁x₂x₃x₄ = 0
B	x₁x₃+x₂ = 0
C
D	x₁ + x₂ + x₃ + x₄ = 0

Digital-Logic-Design Boolean-Algebra GATE 2016 set-2

Question 32 Explanation:

Given expression is,
x₁ ⊕ x₂ ⊕ x₃ ⊕ x₄ = 0 -----(1)
A) x₁x₂x₃ x₄ = 0
Put x₁ = 1, x₂ = 1, x₃ = 1, x₄ = 1
The given equation will be zero, i.e.,
1 ⊕ 1 ⊕ 1 ⊕ 1 = 0
But,
x₁x₂x₃ x₄ ≠ 0
So, false.
B) x₁x₃ + x₂ = 0
Put x₁ = 1, x₂ = 1, x₃ = 0 , x₄ = 0
The given equation will be zero, i.e.,
1 ⊕ 1 ⊕ 0 ⊕ 0 = 0
But,
x₁x₃ + x₂ ≠ 0
So, false.
D) x₁ + x₂ + x₃ + x₄ = 0
Let x₁=1, x₂=1, x₃=0, x₄=0
The given equation will be zero, i.e.,
1 ⊕ 1 ⊕ 0 ⊕ 0 = 0
But,
x₁ + x₂ + x₃ + x₄ ≠ 0
So, false.
(i) True.

Question 33

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

Question 33 Explanation:

X = 2¹⁶
Since range is - 2¹⁵ to 2¹⁵ - 1
Y = 2¹⁶ - 1
Here, +0 and -0 are represented separately.
X - Y = 2¹⁶ - (2¹⁶ - 1)
= 1

Question 34

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-01)

Question 34 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 35

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-01)

Question 35 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 36

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-01)

Question 36 Explanation:

The circuit for the given data is

The characteristic equations are
Q_DN=D=Q_JK

The state table and state transition diagram are as follows:

Consider Q_DQ_JK=10 as initial state because in the options Q_JK=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 37

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 37 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.

Now and every count is unique, occuring only once.
So finally 3-flip flops is required.

Question 38

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

A	1
B	2
C	3
D	4

Digital-Logic-Design Boolean-Algebra GATE 2015 -(Set-2)

Question 38 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 39

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 39 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 40

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-03)

Question 40 Explanation:

Total 3 prime implicants are there.

Question 41

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-01)

Question 41 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 42

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-01)

Question 42 Explanation:

Let base of the number system is r.
(3r² + r + 2) / 2r= (r+3+1/r)
(3r² + r + 2) / 2r= (r²+3r+1) / r
(3r² + r + 2) = (2r²+6r+2)
r² -5r = 0
Therefor r = 5

Question 43

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-01)

Question 43 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 44

The dual of a Boolean function F(x₁, x₂, ..., x_n, +, ⋅, '), written as F^D, is the same expression as that of F with + and ⋅ swapped. F is said to be self-dual if F = F^D. The number of self-dual functions with n Boolean variables is

A	2ⁿ
B	2^(n-1)
C	2^{(2ⁿ )}
D	2^{(2^(n-1) )}

Digital-Logic-Design Self-Dual-Function Gate 2014 Set -02

Question 44 Explanation:

Number of possible minterms = 2ⁿ.
Number of mutually exclusive pairs of minterms = 2^n-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 …. 2^n-1 times.
= 2^{(2^(n-1) )}

Question 45

Let k = 2ⁿ. A circuit is built by giving the output of an n-bit binary counter as input to an n-to-2ⁿ 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 -02

Question 45 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 2ⁿ decoder is a combinational circuit with only one output line has one and all others (2ⁿ-1) have zeros.
A n-bit binary Counter produces outputs from 0 to 2ⁿ i.e 000...00 to 111...11 and repeats.
The n x 2ⁿ 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 2ⁿ - bit ring counter.

Question 46

Consider the equation (123)₅ = (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 -02

Question 46 Explanation:

First we have to fullfill all the conditios,
(123)₅ = (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,
5² × 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 47

A
B
C
D

Digital-Logic-Design Number-Systems Gate 2014 Set -03

Question 47 Explanation:

Question 48

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 -03

Question 48 Explanation:

A 2x1 Multiplexer is most suitable for implementing the function.
x is the select line, I₀ is 'b' and I₁ is a.
The output line, y = xa + x’b

Question 49

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 -03

Question 49 Explanation:

Question 50

A	P+Q
B
C	P⨁Q
D

Digital-Logic-Design Number-Systems Gate 2014 Set -03

Question 50 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 51

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 51 Explanation:

The range of 8-bit signed numbers representable is – 2^n-1 to 2^n-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 52

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 52 Explanation:

It is a 2² × 2 encoder. The inputs have priorities. So, it is a priority encoder.

Question 53

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 53 Explanation:

x ⊕ y = x’y + xy’
x’ ⊕ y’ = xy’ + x’y = x⊕y. Hence option D is correct.

Question 54

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 54 Explanation:

f(X,Y)=XY’ + XY = X(Y’ + Y) = X

Question 55

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 55 Explanation:

(0.5)₁₀ = (1.0)₂ × 2^–1
So, value of the exponent = -1
and
fraction is 000…000 (Implicit representation)

Question 56

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 56 Explanation:

To implement a 4-bit multiplier we need to store all the possible combinations of 2⁴ x 2⁴ inputs and their corresponding 8 output bits. The total ROM size needed = 2⁸ x 8 bits = 2¹¹ bits = 2 Kbits.
Hence option D is the answer.

Question 57

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 57 Explanation:

Question 58

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

A
B
C
D

Digital-Logic-Design Boolean-Algebra Gate 2011

Question 58 Explanation:

Question 59

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 59 Explanation:

Let n is the number of flip-flops.
The max Mod values is 2n.
So 2ⁿ ≥ 258 ⇒ n = 9

Question 60

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 60 Explanation:

All options except option ‘D’ gives EX-NOR gates

Question 61

Consider the following circuit involving three D-type flip-flops used in a certail 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 61 Explanation:

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

Question 62

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 62 Explanation:

So, after 010 it moves to 011.

Question 63

The minterm expansion of

A	m₂+m₄+m₆+m₇
B	m₀+m₁+m₃+m₅
C	m₀+m₁+m₆+m₇
D	m₂+m₃+m₄+m₅

Digital-Logic-Design Boolean-Algebra 2010

Question 63 Explanation:

Convert PQ + QR' + PR' into canonical form
= PQR + PQR' + PQR' + P'QR' + PQR' + PQ'R'
= PQR + PQR' + P'QR' + PQ'R'
=m₇ + m₆ + m₂ + m₄

Question 64

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*2¹⁰ nanoseconds
C	100*2²⁰ nanoseconds
D	3200*2²⁰ nanoseconds

Digital-Logic-Design Memory-Interfacing 2010

Question 64 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 ×2¹⁰ nanoseconds

Question 65

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

A	(C3D8)₁₆
B	(187B)₁₆
C	(F878)₁₆
D	(987B)₁₆

Digital-Logic-Design Number-Systems 2010

Question 65 Explanation:

(F87B)₁₆ is 2's complement representation of P.
(F87B)₁₆=(1111 1000 0111 1011)₂. (It is a negative number which is in 2's complement form)
P=1111 1000 0111 1011 (2's complement form)
8 * P = 2³* P= 1100 0011 1101 1000. ( NOTE: Left shift k times is equivalent to Multiplication by 2^k)
Hence, 1100 0011 1101 1000 is 2's complement representation of 8P.
1100 0011 1101 1000 = (C3D8)₁₆.

Question 66

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 2010

Question 66 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 67

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 2010

Question 67 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 68

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 2010

Question 68 Explanation:

The next four values of Q₁Q₀ are 11, 10, 01, 00.

Question 69

(1217)₈ is equivalent to

A	(1217)₁₆
B	(028F)₁₆
C	(2297)₁₀
D	(0B17)₁₆

Digital-Logic-Design Number-Systems 2009

Question 69 Explanation:

(1217)₈= (001 010 001 111)₂
Divide the bits into groups, each containing 4 bits.
=(0010 1000 1111)₂
=(28F)₁₆

Question 70

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 2009

Question 70 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 71

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 2009

Question 71 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 72

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 72 Explanation:

Value is ±0 if M=0 and E=0.

Question 73

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 73 Explanation:

Question 74

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

A	decimal 10
B	decimal 11
C	decimal 10 and 11
D	any value >2

Digital-Logic-Design Number-Systems Gate-2008

Question 74 Explanation:

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 75

If P, Q, R are Boolean variables, then (p+q')(p.q' + p.r)(p'.r'+q') Simplifies to

A
B
C
D

Digital-Logic-Design Boolean-Algebra Gate-2008

Question 75 Explanation:

Question 76

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 76 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 77

The following bit pattern represents a floating point number in IEEE 754 single precision format 1 10000011 101000000000000000000000 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 77 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 × 2⁴ = -(11010)₂ = -26

Question 78

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 78 Explanation:

f(A, B, C, D) = Σ(2, 3, 6, 7, 8, 9, 10, 11, 12, 13)

Independent of one variable '0'.

Question 79

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 79 Explanation:

f = (x’y’z’ + x’yz’+xy’z+xyz)’
= (x’z’ + xz)’
= x’z + xz’

Question 80

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 80 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 81

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 81 Explanation:

From the given statement:

Excitation table of JK:

Question 82

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 82 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 83

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

A	n²
B	2ⁿ
C	2^2ⁿ
D	2^n²

Digital-Logic-Design Boolean-Algebra Gate-2007

Question 83 Explanation:

Each “boolean” variable has two possible values i.e 0 and 1.
Number of variables= n
Number of input combinations is 2ⁿ.
Each “boolean” function has two possible outputs i.e 0 and 1.
Number of boolean functions possible is 2^2ⁿ.
Formula: The number of m-ary functions possible with n k-ary variables is m^kⁿ.

Question 84

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 84 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 85

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 85 Explanation:

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

Question 86

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 86 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 m₀, m₈, m₉, m₂, m₃, m₆, m₇.
(S) is not covering the minterms m₄, m₅, m₁₃, m₁₅.

Question 87

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 87 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 88

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	2ⁿ line to 1 line
B	2ⁿ⁺¹ line to 1 line
C	2^n-1 line to 1 line
D	2^n-2 line to 1 line

Digital-Logic-Design Multiplexer Gate-2007

Question 88 Explanation:

Both true and complement forms of all variables are necessary to implement any function of n variables.
A 2ⁿ 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 2^n-1 X 1 MUX.

Question 89

In a look-ahead carry generator, the carry generate function G_i and the carry propagate function P_i for inputs A_i and B_i are given by:

P_i = A_i ⨁ B_i and G_i = A_iB_i

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

S_i = P_i ⨁ C_i and C_i+1 = G_i + P_iC_i , where C₀ is the input carry.

Consider a two-level logic implementation of the look-ahead carry generator. Assume that all P_i and G_i 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 89 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 90

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

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:

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 90 Explanation:

A counter goes through a sequence of states. Given counter resets when A₁=A₃=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 91

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 91 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 92

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 92 Explanation:

RS slip-flop using NAND gates.
So, 00 input cause indeterminate state which may lead to oscillation.

Question 93

The following circuit implements a two-input AND gate using two 2-1 multiplexers. What are the values of X₁, X₂, X₃ ?

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 93 Explanation:

F = (bX1' + aX1)X3 + X2X3'
If we put
X1 = b
X2 = 0
X3 = a
Then we get,
F = ab

Question 94

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 94 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 95

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 95 Explanation:

Question 96

(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 96 Explanation:

(C012.25)_H – (10111001110.101)_B
= 1100000000010010.00100101 - 0000010111001110.10100000
= 1011101001000011.10000101
= 1011101000011.100001010
= (135103.412)_O

Question 97

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 ?
(The line T in the following figure is permanently connected to the ground)

A	0000
B	0111
C	1111
D	None of these

Digital-Logic-Design Circuits-Output Gate 2007-IT

Question 97 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 98

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

A

B

C

D

Hence, option (A) matches.

Question 99

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 99 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 100

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 100 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 101

We consider the addition of two 2’s complement numbers b_n-1b_n-2...b₀ and a_n-1a_n-2…a₀. A binary adder for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by c_n-1c_n-2c₀ and the carry-out by c_out. Which one of the following options correctly identifies the overflow condition?

A
B
C
D

Digital-Logic-Design Carry-Generator Gate-2006

Question 101 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 102

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

A	g₀(h₃h₂h₁h₀) = Σ(1,2,3,6,10,13,14,15)
B	g₁(h₃h₂h₁h₀) = Σ(4,9,10,11,12,13,14,15)
C	g₂(h₃h₂h₁h₀) = Σ(2,4,5,6,7,12,13,15)
D	g₃(h₃h₂h₁h₀) = Σ(0,1,6,7,10,11,12,13)

Digital-Logic-Design Number-Systems Gate-2006

Question 102 Explanation:

g₂(h₃h₂h₁h₀) = Σ(2,4,5,6,7,12,13,15)

Question 103

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 i₁ = 〈w₁, x₁, y₁, z₁〉 and i₂ = 〈w₂, x₂, y₂, z₂〉, we would like the function to remain true as the input changes from vectors i₁ to i₂ (i₁ and i₂ 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 103 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 = X₁ * X₂ + X₁' * X₃
If (X₁,X₂,X₃) = (1,1,1) then f=1 because X₁ * X₂ =1 X₁' * X₃ = 0.
Let the input is changed from 111 to 011 , then f = 1 because X₁ * X₂ = 0 X₁' * X₃ =1.
The output f will be momentarily 0 if AND gate X₁ * X₂ is faster than the AND gate X₁' * X3.
This Hazard can be avoided by adding the term X₂ * X₃ (because X₁ is in true form in first term and in complement form in the second term . So pick the fixed terms X₂ and X₃ from both terms) to f i.e f = X₁ * X₂ + X₁' * X₃ + X₂ * X₃
Option D is equivalent to f(w, x, y, z) = ∑(5,7,11,12,13,15)

Question 104

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 104 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 105

Given two three bit numbers a₂a₁a₀ and b₂b₁b₀ 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 105 Explanation:

Initial Carry c is not included in any option. Hence c=0.
Carry c₁ = a₀b₀
Carry c₂ = a₂b₂ + c₁(a₂ ⊕ b₂ )
= a₁b₁ +c₁ (a₁ b’₁+ a’₁ b₁ )
= a₁b₁ +c₁ a₁ b’₁+ c₁ a’₁ b₁
= (a₁b₁ + c₁a₁ b’₁)+ (c₁ a’₁ b₁ + a₁b₁ )
= a₁(b₁+c₁) +b₁ (c₁ + a₁)
= a₁b₁+b₁c₁+a₁c₁
Carry c₃ = a₂b₂ + c₂(a₂ ⊕ b₂)
= a₂b₂ + c₂(a’₂b₂ + a₂b’₂ )
= a₂b₂ + b₂c₂ + a₂c₂
= a₂b₂+a₂a₁b₁+a₂a₁a₀b₀+a₂a₀b₁b₀+a₁b₂b₁+a₁a₀b₂b₀+a₀b₂b₁b₀

Question 106

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 106 Explanation:

D2 = q1, D1= q0 ⊕ q2, D0=external input

Question 107

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 107 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 108

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 108 Explanation:

Essential prime implicants which are grouped only by only one method or way. So, in the given question cornor's ones are grouped by only one method.

Question 109

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 109 Explanation:

Output of the function is x' P + x Q.
Majority means at least two inputs should be 1.
Whenever the majority of the variables have value 1, the output is 1.
The following combinations produce output 1.
110, 101, 111, and 011
The circuit has 3 inputs namely x, y and z with x as the selection line to MUX.
Consider Majority cases.
Case 1: x=1
x y z
1 1 0 When x is 1 then at least one of y and z should be 1. Then P is OR gate.
1 0 1
1 1 1
Case 2: x=0
0 1 1
When x is 0 both y and z should be 1. So Q is AND gate

Question 110

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 110 Explanation:

⇒ -2Y and 0

Question 111

Consider the following circuit

Which one of the foloowing 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 111 Explanation:

f(X,Y,Z) = ((XY’)’ (YZ))’
= ((X’+Y) YZ)’
= (X’YZ + YZ)’
= ((X’+1) YZ)’
= (YZ)’

Question 112

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

A	- 2^n-1 to (2^n-1 - 1)
B	- (2^n-1 - 1) to (2^n-1 - 1)
C	- 2^n-1 to 2^n-1
D	- (2^n-1 + 1) to (2^n-1 - 1)

Digital-Logic-Design Number-Systems Gate-2005

Question 112 Explanation:

The maximum (positive) n bit number is 011….1 (i.e., 0 followed by n-1 ones) which is equal to 2^n-1 - 1.
The smallest (negative) n bit number is 100..0 (i.e., 1 followed by n-1 zeros) which is equal to - 2^n-1.
1000...00
0111...11 <- 1’s complement
1000..00 <- 2’s complement
= - 2^n-1

Question 113

Consider the following floating point format

Mantissa is a pure fraction in sign-magnitude form. The decimal number 0.239 × 2¹³ 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 113 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)₂
Bias= 64. So biased exponent is 13+64 = 77= (1001101)₂
0.239 × 2¹³ = 0 1001101 00111101
= 0100 1101 0011 1101
= 4 D 3 D

Question 114

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 × 2¹³) is:

A	0A 20
B	11 34
C	4D D0
D	4A E8

Digital-Logic-Design Number-Systems Gate-2005

Question 114 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)₂
0.239 × 2¹³ = 1.11101000 x 2¹⁰ <- Normalized Mantissa
Bias = 64. So biased exponent is 10+64 = 74 = (1001010)₂
0.239 × 2¹³ = 0 1001010 11101000
= 0100 1010 1110 1000
= (4 A E 8)₁₆

Question 115

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 115 Explanation:

Question 116

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	A₀ A₁ A₁' A₃ A₄
B	A₀ A₁ A₂' A₃ A₄
C	A₁ A₂ A₂' A₃ A₄
D	A₁ A₂' A₃ A₄ A₅'

Digital-Logic-Design Circuits-Output Gate-2005

Question 116 Explanation:

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

Question 117

The hexadecimal representation of 657₈ is

A	1AF
B	D78
C	D71
D	32F

Digital-Logic-Design Number-Systems Gate-2005

Question 117 Explanation:

(657)₈ = (110 101 111)₂
Make 3 zeros on the left side so that the number of bits is multiple of 4.
= (0001 1010 1111)₂
= (1 A F)₁₆

Question 118

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 118 Explanation:

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

Question 119

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 119 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 120

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 120 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 121

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	3^N
B	3^N - 1
C	2^N - 1
D	2

Digital-Logic-Design Sequential-Circuits Gate 2005-IT

Question 121 Explanation:

Answer should be 3^N-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 3^N. 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 3^N - 1.

Question 122

(34.4)₈ × (23.4)₈ evaluates to

A	(1053.6)₈
B	(1053.2)₈
C	(1024.2)₈
D	None of these

Digital-Logic-Design Number-Systems Gate 2005-IT

Question 122 Explanation:

First convert (34.4)₈ and (23.4)₈ to decimal.
(34.4)₈ = 3×8¹ + 4×8⁰ + 4×8^-1
= 24 + 4 + 0.5
= (28.5)₁₀
(23.4)₈ = 2×8¹ + 3×8⁰ + 4×8^-1
= 16 + 3 + 0.5
= (19.5)₁₀
Now,
(28.5)₁₀ × (19.5)₀₁ = (555.75)₁₀
Now,
(555.75)₁₀ = ( ? )₈
To convert the integer part,

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

∴ (555.75)₁₀ = (1053.6)₈

Question 123

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 123 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 124

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 124 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 ⌈log₂ N⌉. And in the question 5 groups contains mutually exclusive signals,
group 1 = ⌈log₂ 20⌉ = 5
group 2 = ⌈log₂ 70⌉ = 7
group 3 = ⌈log₂ 2⌉ = 1
group 4 = ⌈log₂ 10⌉ = 4
group 5 = ⌈log₂ 23⌉ = 5
Total bits required in vertical microprogramming
= 5 + 7 + 1 + 4 + 5
= 22
So, number of bits saved is
= 125 - 22
= 103

Question 125

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 125 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 126

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 126 Explanation:

The following circuit and truth table of a cross-couple SR latch with 2 NAND gates.

Output of a NAND is 1 if at least one of its input is zero.

Question 127

If 73_x (in base-x number system) is equal to 54_y (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 127 Explanation:

(73)_x = (54)_y
7x+3 = 5y+4
7x-5y = 1
Only option (D) satisfies above equation.

Question 128

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 128 Explanation:

(113. + -111.) + 7.51
= (2) + 7.51
= 9.51 (✔️)
113. + (-111. + 7.51)
= 113. + (-103.51)
= 113. + -103
= 10 (✔️)

Question 129

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 129 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 130

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 130 Explanation:

From given function 'f' we can draw,

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

Question 131

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 131 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 132

A	Q₂^c
B	Q₂ + Q₁
C	(Q₁ + Q₂)^c
D	Q₁ ⊕ Q₂

Digital-Logic-Design Sequential-Circuits Gate-2004

Question 132 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,

Question 133

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 133 Explanation:

The 4-bit addition will be calculated in 3 stages:
1) (2 time units) In 2 time units we can compute G_i and P_i in parallel, 2 time units for P_i since its an XOR operation and 1 time unit for G_i sinceits an AND operation.
2) (2 time units) Once G_i and P_i are available, we can calculate the carries, C_i, in 2 time units.
Level-1 we can compute all the conjunctions (AND). Example P₃G₂, P₃P₂G₁, P₃P₂P₁G₀ and P₃P₂P₁P₀C₀ which are required for C₄.
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 134

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 134 Explanation:

A = 1111 1010 = -6₁₀ [2's complement number]
B = 0000 1010 = 10₁₀ [2's complement number]
A×B = -6×10 = - 60₁₀
⇒ -60₁₀ = 10111100₂
= 11000011₂ (1's complement)
= 11000100₂ (2's complement)

Question 135

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 135 Explanation:

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

Question 136

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 136 Explanation:

Input: 2 lines, 8 bits each
Possible combination in ROM = (2⁸ × (2⁸) [size of truth table]
= 2¹⁶
= 64 KB
= 64 K ×16 bits

Question 137

Using a 4-bit 2’s complement arithmetic, which of the following additions will result in an overflow? (i) 1100 + 1100 (ii) 0011 + 0111 (iii) 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 137 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 138

The number (123456)₈ is equivalent to

A	(A72E)₁₆ and (22130232)₄
B	(A72E)₁₆ and (22131122)₄
C	(A73E)₁₆ and (22130232)₄
D	(A62E)₁₆ and (22120232)₄

Digital-Logic-Design Number-Systems Gate 2004-IT

Question 138 Explanation:

(123456)₈ = (001 010 011 100 101 110)₂
= (00 1010 0111 0010 1110)₂
= (A72E)₁₆
Also,
(001 010 011 100 101 110)₂
= (00 10 10 01 11 00 10 11 10)₂
= (22130232)₄

Question 139

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 139 Explanation:

For given min term the K-map is,

⇒ A'C + AC' + AB'

Question 140

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? I. 0010111 II. 0110110 III. 1011010 IV. 0111010

A	I and III
B	I, II and III
C	II and IV
D	I, II, III and IV

Digital-Logic-Design Number-Systems Gate 2004-IT

Question 140 Explanation:

Let x₁, x₂, x₃ are data bits, and c₁, c₂, c₃ and c₄ 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 141

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 141 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)₁₀
(B) 11100100 - (-28)_{10

(C) 11010111 - (-41)₁₀

(D) 11011011 - (-37)₁₀

Answer: Option A (-25 is divisible by -5)}

Question 142

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	Θ (n²)

Digital-Logic-Design Multiplexer Gate-2003

Question 142 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 143

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

Bit position 15           14 . . . 9            8 . . . . .0
       s                      e                      m
     Sign                  Exponent               Mantissa

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	2²²
D	2³¹

Digital-Logic-Design Number-Systems Gate-2003

Question 143 Explanation:

Largest gap will be in between two most largest numbers.
The largest number is 1.111111111× 2^62-31 = (2−2⁻⁹)×2³¹
Second largest number is 1.111111110×2^62-31 = (2−2^-8)×2³¹
Difference = (2−2⁻⁹)×2³¹ - (2−2^-8)×2³¹
= (2^-8−2⁻⁹) ×2³¹
= 2⁻⁹×2³¹
= 2²²

Question 144

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 144 Explanation:

Let q is the initial state.

q₀ ← Number of zeros is one more than number of ones.
q₁ ← Number of ones is one more than number of zeros.
q₀₀ ← Number of zeros is two more than number of ones.
q₁₁ ← Number of ones is two more than number of zeros.

Question 145

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 145 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 146

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 146 Explanation:

The circuits performs
1) A+B when K=0 and C₀ = 0. It is binary adder which performs addition of two binary numbers.
2) A - B = A+ B' + 1 when K=1 and C₀ = 1 ;
Here XOR gates produce B' if K=1. Since 1⊕b= b'.
"1" in (A+B+1) is coming from C₀.
Note: 2's complement of B is (B'+1). 3) A+1 when B=0, K=0, C₀= 1.
Increments A.

Question 147

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

The non-inverting buffers have delays d1 = 2 ns and d2 = 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 147 Explanation:

⇒ a will always be equal to A.

Question 148

A	xz+y'z
B	xz'+zx'
C	x'y+zx'
D	None of the above

Digital-Logic-Design K-Map Gate-2002

Question 148 Explanation:

⇒ xz' + zx'

Question 149

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 149 Explanation:

1^st Multiplication iteration:
Multiply 0.25 by 2.
0.25×2 = 0.50 (product)
Fractional part = 0.50
Carry = 0
2^nd Multiplication iteration:
Multiply 0.50 by 2.
0.50×2 = 1.00 (product)
Fractional part = 0.00
Carry = 1
The fractional part in the 2^nd iteration becomes zero and so we stop the multiplication iteration.
Carry from 1^st multiplication iteration becomes MSB and carry from 2^nd iteration becomes LSB. So the result is 0.01.

Question 150

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 150 Explanation:

15 = 1111
-15 = 11111
1's complement = 10000
2's complement = 10001

Question 151

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 151 Explanation:

Sign extension is a step in converting a signed integer from on size to another.

Question 152

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 152 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 153

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 153 Explanation:

f(x,y,z) = (f₁', (x,y,z) ⋅ f₂'(x,y,z) + f₃'(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 154

A	xyz'
B	xy+z
C	x+y
D	None of the above

Digital-Logic-Design Multiplexer Gate-2002

Question 154 Explanation:

F = (A'A₀'10 + A'A₀'11 + A'A₀'12 + A₁A₀13) 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 155

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 155 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 156

A	Theory Explanation is given below.

Digital-Logic-Design Boolean-Expression-and-Logic-Gates Gate-2002

Question 156 Explanation:

A	Theory Explanation is given below.

Digital-Logic-Design Clock-Pulse Gate-2002

Question 158

A	Theory of Explantion is given below.

Digital-Logic-Design Number-Systems Gate-2002

Question 159

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 159 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 160

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 160 Explanation:

Just put the values of each options in the equation and check it.

Question 161

A
B
C
D	None of the above

Digital-Logic-Design K-Map Gate-2000

Question 161 Explanation:

The K-map represents the following expression Minimal POS: w(x+y) minimal SOP: wx+wy SOP(not minimal): (w+x) (w’+y) (x’ +y)

Question 162

A	1, 0
B	1, 1
C	0, 0
D	0, 1

Digital-Logic-Design Sequential-Circuits Gate-2000

Question 162 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 163

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 163 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 * 10³⁰, C = 1.0
So, A + C should make the 31^st digit to 1, which is surely outside the precision level of A (it is 31^st digit and not 31^st 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 164

A	Theory Explanation is given below.

Digital-Logic-Design Descriptive Gate-2000

Question 165

A	x NAND X
B	x NOR x
C	x NAND 1
D	x NOR 1

Digital-Logic-Design Logic-Gates Gate-1999

Question 165 Explanation:

Question 166

A
B
C
D

Digital-Logic-Design K-Map Gate-1999

Question 166 Explanation:

⇒ CD+AD = D(A+C)

Question 167

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 167 Explanation:

Represent the multiplier in 2's complement form.
-57 = 1100 0111
In Booth's algorithm, an operation (ADD or SUB) or/and Arithmetic Right Shift (ARS) operation is performed based on two least significant bits(Q0 Q-1) of Multiplier.
(Note: After RIGHT shift operation bits in higher significant positions move to lower significant position)

Question 168

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

A	On²
B	O(n)
C	O(log n)
D	O(1)

Digital-Logic-Design Multiplexer Gate-1999

Question 168 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 169

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 169 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 170

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 170 Explanation:

Sign magnitude:
+0 = 0000
-0 = 1000
1's complement:
+0 = 0000
-0 = 1111

Question 171

A	complements when n is even
B	complements when n is odd
C	divides by 2ⁿ always
D	remains unchanged when n is even

Digital-Logic-Design EX-OR Gate-1998

Question 171 Explanation:

B⊕(B⊕(B⊕...) n times
Consider:
B⊕(B⊕B)
= B⊕0
= 0 (if consider n times it remains unchanged)

Question 172

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 172 Explanation:

For 'n' bit data it selects 2ⁿ : 1 input
For 4 bit data it selects 2⁴ : 1 = 16: 1 input

Question 173

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 V_cc but above 2.8 V

Digital-Logic-Design Threshold-Voltage Gate-1998

Question 173 Explanation:

Voltage is to be below V_cc = 5V but above 2.8V

Question 174

The octal representation of an integer is (342)₈. 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 174 Explanation:

(342)₈ = (011 100 010)₂ = (1110 0010)₂
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 175

A	A⋅B
B	AB+BC+CA
C
D	None of the above

Digital-Logic-Design K-Map Gate-1998

Question 175 Explanation:

Question 176

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 176 Explanation:

NAND operation is commutative but not associative.

Question 177

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 177 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 178

A
B	x
C	0
D	1

Digital-Logic-Design Boolean-Expressions Gate-1997

Question 178 Explanation:

Question 179

A	proportional to N
B	proportional to log N
C	a constant
D	None of the above

Digital-Logic-Design Adder Gate-1997

Question 180

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 180 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 181

A	10
B	8
C	5
D	6

Digital-Logic-Design Number-Systems Gate-1997

Question 181 Explanation:

Question 182

A	Σ9,10
B	Σ9
C	Σ1,8,9
D	Σ8,10,15

Digital-Logic-Design Logic-Circuit Gate-1997

Question 182 Explanation:

f = f₁⋅f₂ + f₃
Since, f₁ and f₂ are in canonical sum of products form, f₁⋅f₂ will only contain their common terms that is f₁⋅f₂ = Σ8.
Now,
Σ8 + f₃ = Σ8,9
So, f₃= Σ9

Question 183

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 183 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 possibe = 2⁸ × 2⁸ = 2¹⁶ = 64K
Then total size of ROM = 64K × 16

Question 184

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 184 Explanation:

When the pairs 01 (or) 10 occur frequently in the multiplier. In that case Booth multiplication gives worst performance.

Question 185

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 185 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 186

Consider the circuit in the figure below which has a 4 bit binary number b₃b₂b₁b₀ as input and a five bit binary number d₄d₃d₂d₁d₀ as output.

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 186 Explanation:

Here ф means 0.
Whenever, b₂ = b₃ = 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 b₃ and b₂ 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 187

A
B
C
D

Digital-Logic-Design Multiplexer Gate-1996

Question 187 Explanation:

Question 188

A
B
C
D
E	None of the above

Digital-Logic-Design K-Map Gate-1996

Question 188 Explanation:

Correct option is

Question 189

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 189 Explanation:

For verification, just put up the values and check for AND, OR operations and their outputs.

Question 190

A	8
B	9
C	10
D	12

Digital-Logic-Design Number-Systems Gate-1995

Question 190 Explanation:

Question 191

A
B
C
D
E	None of the above.

Digital-Logic-Design Logic-Gates Gate-1994

Question 191 Explanation:

Question 192

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

A

⌈log₂ N⌉

Digital-Logic-Design Flip-Flops Gate-1994

Question 192 Explanation:

For mod-N counter we need ⌈log₂ N⌉ flip flops.

Question 193

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	-2^n-1 to 2^n-1 - 1

Digital-Logic-Design Number-Systems Gate-1994

Question 194

A	exclusive OR
B	exclusive NOR
C	NAND
D	NOR
E	None of the above

Digital-Logic-Design Logic-Gates Gate-1993

Question 194 Explanation:

So finally, we can write

Question 195

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 195 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 196

A	(a) 6.625, (b) (45E)_H

Digital-Logic-Design Number-Systems Gate-1993

Question 196 Explanation:

(a) 1*2² + 1*2¹ + 0*2⁰ + 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 197

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 197 Explanation:

Input will consist of 8 bit (two 4-bit numbers) = 2⁸ address.
Output will be of 8 bits.
So memory will be of 2⁸ × 8.
So, M = 256, N = 8.

Question 198

A	ABC + B'C' + A'C'

Digital-Logic-Design K-Map Gate-1992

Question 198 Explanation:

We can write this as

⇒ ABC + B'C' + A'C'

Question 199

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 200

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 200 Explanation:

NAND and NOR operation follow commutativity but do not follow associativity.

Question 201

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 201 Explanation:

NOR gate, NAND gate, Multiplexers and Half adders can also be used to realize all digital circuits.

Question 202

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 202 Explanation:

⇒ y'z + xy

Question 203

A
B
C
D

Digital-Logic-Design Sequential-Circuits Gate-2001

Question 203 Explanation:

Given clock is +edge triggered.
See the first positive edge. X is 0, and hence the output is 0, because
Y = Q_1N = D₁×Q₀' = 0⋅Q₀' = 0
At second +edge, X is 1 and Q₀' is also 1. So output is 1 (when second +ve edge of the clock arrives, Q₀' 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 Q₀' is 0, so output is 0.
Now output never changes back to 1 as Q₀' is always 0 and when Q₀' finally becomes 1, X is 0.
Hence option (A) is the correct answer.

Question 204

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

A	ABE
B	DBC
C	DE5
D	9E7

Digital-Logic-Design Number-Systems Gate-2001

Question 204 Explanation:

(539)₁₀ = (0010 0001 1011)₂
For (-539)₁₀ = (1101 1110 0100)₂
1's complement = (1101 1110 0100)₂
2's complement = (1101 1110 0101)₂
= (DE5)₁₆

Question 205

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 205 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 206

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 206 Explanation:

Question 207

A	Theory Explanation is given below.

Digital-Logic-Design Descriptive Gate-2001

Question 207 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 208

A	Theory Explanation is given below.

Digital-Logic-Design Sequential-Circuits Gate-2001

Question 208 Explanation:

Question 209

A	Out of syllabus.

Digital-Logic-Design Circuits Gate-1991

Question 210

A

9

Digital-Logic-Design Number-Systems Gate-1991

Question 210 Explanation:

Hexadecimal representation of a given no. is,
(9753)₁₆
It's binary representation is,
1001011101010011
∴ The no. of 1's is 9.

Question 211

When two 4-bit binary number A = a₃a₂a₁a₀ and B = b₃b₂b₁b₀ are multiplied, the digit c₁ of the product C is given by _________

A	c₁ = b₁a₀ ⊕ a₁b₀

Digital-Logic-Design Number-Systems Gate-1991

Question 211 Explanation:

⇒ c₁ = b₁a₀ ⊕ a₁b₀

Question 212

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 212 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 213

A	Y = ABC + DE
B	Y = ABC + DE
C	Y = ABC . DE
D	Y = ABC . DE
E	Both (C) and (D)

Digital-Logic-Design Circuits-Output Gate-1990

Question 213 Explanation:

There should be bubbled connection between two gates
Y = ((ABC)' + (DE)')'
Y = ABC . DE
Note: Open gate works as NOR gate.

Question 214

A	True
B	False

Digital-Logic-Design Combinational-and-Sequential-Circuits Gate-1990

Question 214 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 215

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

A	4
B	17
C	256
D	65,536

Digital-Logic-Design Boolean-Functions GATE-1987

Question 215 Explanation:

Total no. of Boolean functions which can be realized with four variables is:

Question 216

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 216 Explanation:

Let us suppose initially output of all JK flip flop is 1.
So we can draw below table to get the output Q₃.

From the above table Q₃ that is output is 1111 0001 0011 010.
So, answer is (C).

Question 217

The output F of the below multiplexer circuit can represented by

A
B	A⊕B⊕C
C	A⊕B
D

Digital-Logic-Design Multiplexer GATE-1987

Question 217 Explanation:

Question 218

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 218 Explanation:

To avoid extra work, excess-N code is used so that all exponent can be represented in positive numbers, starting with 0.

Question 219

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 219 Explanation:

During a 2 millisecond interval all dynamic RAM memory is refreshed.

There are 219 questions to complete.