# GATE Questions & Answers of Digital Logic Computer Science and Information Technology

#### Digital Logic 73 Question(s) | Weightage 06 (Marks)

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

Which one of the following is NOT a valid identity?

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:

Consider three 4-variable functions f1, f2, and f3, which are expressed in sum-of-minterms as f1 = $\sum$ (0, 2, 5, 8, 14),   f2 = $\sum$ (2, 3, 6, 8, 14, 15),   f3 = $\sum$ (2, 7, 11, 14) For the following circuit with one AND gate and one XOR gate, the output function f can be expressed as: What is the minimum number of 2-input NOR gates required to implement a 4-variable function expressed in sum-of-minterms form as f = $\mathrm\Sigma$ (0, 2, 5, 7, 8, 10, 13, 15)? Assume that all the inputs and their complements are available. Answer: _______________.

Let $\style{font-family:'Times New Roman'}\oplus$ and $\style{font-family:'Times New Roman'}\odot$ denote the Exclusive OR and Exclusive NOR operations, respectively.

Which one of the following is NOT CORRECT?

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

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

b7 b6 b5 b4 b3 . b2 b1 b0

where the position of the binary point is between b3 and b2. Assume b7 is the most significant bit. Some of the decimal numbers listed below cannot be represented exactly in the above representation:
(i)   31.500   (ii)   0.875   (iii)   12.100   (iv)   3.001

Which one of the following statements is true?

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

$\style{font-family:'Times New Roman'}{F\left(P,Q,R,S\right)=\sum m\left(0,2,5,7,9,11\right)+d\left(3,8,10,12,14\right)}$

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

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

Consider the Karnaugh map given below, where X represents "don't care" and blank represents 0. Assume for all inputs (a, b, c, d), the respective complements  $\style{font-family:'Times New Roman'}{\left(\overline a,\;\overline b,\;\overline c,\;\overline d\right)}$  are also available. The above logic is implemented using 2-input NOR gets only. The minimum number of gates required is _____________.

Consider a combination of T and D flip-flops connected as shown below. The output of the D flip-flop is connected to the T flip-flop and the output of the T flip-flop is connected to the input of the flip-flop. Intitally, both Q0 and Q1 are set to 1 (before the 1st clock cycle) The outputs

## SET-2

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

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

00111110011011010000000000000000

The decimal value closest to this floating-point number is

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

Given $\style{font-family:'Times New Roman'}{f(w,\;x,\;y,\;z)=\sum\nolimits_m(0,\;1,\;2,\;3,\;7,\;8,\;10)+\sum\nolimits_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\left(w,x,y,z\right)$ ?

Consider a binary code that consists of only four valid codewords 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

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 expression for T1 and T0 are

Consider the Boolean operator # with the following properties:

$x\#0\;=\;x,\;x\#1\;=\;\overline x,\;x\#x\;=\;0\;and\;x\#\overline x\;=1.$ Then $x#y$ is equivalent to

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

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

Consider the two cascaded 2-to-1 multiplexers as shown in the figure. The minimal sum of products form of the output $X$ is

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

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

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

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

The binary operator $\ne$ is defined by the following truth table.

 p q p$\ne$q 0 0 0 0 1 1 1 0 1 1 1 0

Which one of the following is true about the binary operator $\ne$?

A positive edge-triggered D flip-flop is connected to a positive edge-triggered JK flip-flop 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 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.

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

The number of min-term after minimizing the following Boolean expression is _____.

$\left[D'\;+\;AB'+A'C+AC'D\;+\;A'C'D'\right]$

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 and 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 _____.

Let # be a binary operator defined as

X # Y = X' +Y' where X and Y are Boolean variables.

Consider the following two statements

S1  (P # Q) # R = P # (Q # R)
S2   Q # R = R # Q

Which of the following is/are true for hte Boolean variables P, Q and R?

Given the function F = P' + QR, where F is a function in three Boolean variables P, Q and R and P' = !P, consider the following statements.

(S1) F = ${\sum }_{}$ (4, 5, 6)
(S2) F = ${\sum }_{}$ (0, 1, 2, 3, 7)
(S3) F = $\prod$ (4, 5, 6)
(S4) F = $\prod$ (0, 1, 2, 3, 7)

Which of the following is true?

Consider the following Boolean expression for F:

$F\left(P,Q,R,S\right)=PQ+\overline{P}QR+\overline{P}Q\overline{R}S$

The minimal sum-of-products form of F is

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

$\frac{312}{20}=13.1$

Consider the 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

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

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

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

Consider the following minterm expression for F:

$F\left(P,Q,R,S\right)=\sum 0,2,5,7,8,10,13,15$

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

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? The above synchronous sequential circuit built using JK flip flop is initialized with Q2Q1Q0=000.THe state sequence for these circuit for next 3 clock cycle is

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

$F\left(P,Q\right)=\left(\left(1\oplus P\right)\oplus \left(P\oplus Q\right)\right)\oplus \left(\left(P\oplus Q\right)\oplus \left(Q\oplus 0\right)\right)$

The equivalent expression for F is

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

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

 Inputs Outputs D0 D1 D2 D3 X0 X1 V 0 0 0 0 X X 0 1 0 0 0 0 0 1 X 1 0 0 0 1 1 X X 1 0 1 0 1 X X X 1 1 1 1

What function does the truth table represent?

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

The truth table

 X Y f (X, Y) 0 0 0 0 1 0 1 0 1 1 1 1

represents the Boolean function

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

What is the minimal form of the Karnaugh map shown below? Assume that X denotes a don’t care term. Which one of the following circuits is NOT equivalent to a 2-input XNOR (exclusive NOR) gate?

The simplified SOP (Sum of Product) form of the Boolean expression

$\left(P+\overline{)Q}+\overline{)R}\right).\left(P+\overline{)Q}+R\right).\left(P+Q+\overline{)R}\right)$ is

Consider the following circuit involving three D-type flip-flop used ina certain type of  counter configuration. if at some instance prior to the occurance of the clock edge P,Q,and R have value 0, 1 and 0 respectively, what shall be the value of PQR after the clock edge?

Consider the following circuit involving three D-type flip-flop used ina certain type of  counter configuration. If all the flip-flop were reset to 0 at power on ,what is the total number of distinct outputs (states) represented by PQR generated by the counter?

The minterm expansion of $f\left(P,Q,R\right)=PQ+Q\overline{)R}+P\overline{)R}$ is

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

The Boolean expression for the output f of the multiplexer shown below is What is the Boolean expression for the output f of the combinational logic circuit of NOR gates given below? In the sequential circuit shown below, if the initial value of the output Q1Q0 is 00, what are the next four values of Q1Q0? (1217)8 is equivalent to

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?

In the IEEE floating point representation the hexadecimal value 0x00000000 corresponds to

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? Let r denote number system radix. The only value(s) of r that satisfy the equation $\sqrt{{121}_{r}}={11}_{r}$ is / are

Given f1, f3 and f in canonical sum of products form (in decimal) for the circuit f1 = ${\sum }_{}$m (4, 5, 6, 7, 8)
f3 = ${\sum }_{}$m (1, 6, 15)
f = ${\sum }_{}$m (1, 6, 8, 15)
then f2 is

If P, Q, R are Boolean variables, then

$\left(P+\overline{Q}\right)\left(P.\overline{Q}+P.R\right)\left(\overline{P}.\overline{R}+\overline{Q}\right)$

Simplifies to

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

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?

Consider the following Boolean function of four variables:

$f\left(w,x,y,z\right)=\sum \left(1,3,4,6,9,11,12,14\right)$

The function is

Let $f\left(w,x,y,z\right)=\sum \left(0,4,5,7,8,9,13,15\right)$. 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

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?

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?

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

${P}_{i}={A}_{i}\oplus {B}_{i}$ and ${G}_{i}={A}_{i}{B}_{i}$

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

${S}_{i}={P}_{i}\oplus {C}_{i}$ and ${C}_{i+1}={G}_{i}+{P}_{i}{C}_{i}$ ,where C0 is the input carry

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

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

 Clear Clock Load Count Function 1 X X X Clear to 0 0 X 0 0 No change 0 $↑$ 1 X Load input 0 $↑$ 0 1 Count next

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