Consider a sequential digital circuit consisting of T flip-flops and D flip-flops as shown. At the beginning, \(Q_1=0\), \(Q_2=1\), \(Q_3=1\). Which one of the given values of \((Q_1,Q_2,Q_3)\) can NEVER be obtained with this circuit?
Consider a sequential digital circuit consisting of T flip-flops and D flip-flops as shown. At the beginning, \(Q_1=0\), \(Q_2=1\), \(Q_3=1\). Which one of the given values of \((Q_1,Q_2,Q_3)\) can NEVER be obtained with this circuit?
Show Hint
- \((0,0,1)\)
- \((1,0,0)\)
- \((1,0,1)\)
- \((1,1,1)\)
The Correct Option is A
Solution and Explanation
For a T–FF: \(Q^+ = Q \oplus T\). For a D–FF: \(Q^+ = D\).
From the figure (using the labels in the question): \[ \begin{aligned} T_1 &= \overline{Q_3}, & Q_1^+ &= Q_1 \oplus \overline{Q_3}, \\ D_2 &= Q_1, & Q_2^+ &= Q_1, \\ T_3 &= Q_2, & Q_3^+ &= Q_3 \oplus Q_2. \end{aligned} \]
Step 2: Iterate from the given initial state \((Q_1,Q_2,Q_3)=(0,1,1)\)
On each rising edge (all FFs clocked together) apply the above equations: \[ \begin{array}{c|c} \text{Clock} & (Q_1,Q_2,Q_3) \\ \hline 0 & (0,1,1)\ \text{(given)} \\ 1 & (0,0,0) \\ 2 & (1,0,0) \\ 3 & (0,1,0) \\ 4 & (1,0,1) \\ 5 & (1,1,1) \\ 6 & (1,1,0) \\ 7 & (0,1,1)\ \text{(cycle repeats)} \end{array} \]
Step 3: Read off the reachable set
The reachable states are \(\{(0,1,1), (0,0,0), (1,0,0), (0,1,0), (1,0,1), (1,1,1), (1,1,0)\}\). The tuple \((0,0,1)\) never appears and the sequence repeats thereafter, so it is unreachable. \[ \boxed{\text{State }(0,0,1)\ \text{can never be obtained.}} \]
Top GATE CS Computer Science and IT Engineering Questions
- Suppose a program is running on a non-pipelined single processor computer system. The computer is connected to an external device that can interrupt the processor asynchronously. The processor needs to execute the interrupt service routine (ISR) to serve this interrupt. The following steps (not necessarily in order) are taken by the processor when the interrupt arrives:
(i) The processor saves the content of the program counter.
(ii) The program counter is loaded with the start address of the ISR.
(iii) The processor finishes the present instruction.
Which ONE of the following is the CORRECT sequence of steps? - Which ONE of the following statements is FALSE regarding the symbol table?
- Which ONE of the following techniques used in compiler code optimization uses live variable analysis?
- Consider a demand paging memory management system with 32-bit logical address, 20-bit physical address, and page size of 2048 bytes. Assuming that the memory is byte addressable, what is the maximum number of entries in the page table?
A schedule of three database transactions \(T_1\), \(T_2\), and \(T_3\) is shown. \(R_i(A)\) and \(W_i(A)\) denote read and write of data item A by transaction \(T_i\), \(i = 1, 2, 3\). The transaction \(T_1\) aborts at the end. Which other transaction(s) will be required to be rolled back?
Top GATE CS Digital Logic Questions
Consider the following Boolean expression of a function F :
𝐹(𝑃, 𝑄) = (𝑃̅ + 𝑄) ⊕(𝑃̅𝑄)
Which of the following expressions is/are equivalent to F ?Which one of the following options is not a property of Boolean Algebra?
Note: + is OR operation, . is AND operation, and ′ is NOT operationConsider a 2-bit saturating up/down counter that performs the saturating up count
when the input P is 0, and the saturating down count when P is 1. The Next State
table of the counter is as shown. The counter is built as a synchronous sequential
circuit using D flip-flops.
Input
Current
State
Next
State
𝑃
𝑄1
𝑄0
𝑄1
+
𝑄0
+
0
0
0
0
1
0
0
1
1
0
0
1
0
1
1
0
1
1
1
1
1
0
0
0
0
1
0
1
0
0
1
1
0
0
1
1
1
1
1
0
Which one of the following options corresponds to the expressions for the inputs of
the D flip-flops, 𝐷1 and 𝐷0?
Consider a Boolean function F with the following minterm expression:
𝐹(𝑃, 𝑄, 𝑅, 𝑆) = ∑𝑚 (1, 2, 3, 4, 5, 7, 10, 12, 13, 14)
Which of the following options is/are the minimal sum-of-products expression(s)
of F ?Consider the following 4-variable Boolean function
𝐹(𝐴, 𝐵, 𝐶, 𝐷) = Σ𝑚(0, 1, 2, 3, 8, 9, 10, 11)
Consider 𝐴 as MSB, 𝐷 as LSB. Which one of the following options represents the
minimal sum of products form for the above function?
Note: + is OR operation, . is AND operation, ′ is NOT operation
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?