Digital Logic Design GATE previous year questions with answer

Explanation:
Let us break down the sizing of each individual field in the 32-bit instruction format based on the given constraints.

1. Calculate the Sizing of the OPCODE Field (Y):
• The processor supports 150 distinct instructions, which are equally divided into two types: 75 R-type and 75 I-type instructions.
• To uniquely encode 75 distinct operations within either type, we need:
    2⁶ < 75 ≤ 2⁷ → 7 bits are required to indicate the operation.
• The problem states that in the OPCODE field, 1 extra bit is explicitly used to distinguish between I-type and R-type configurations.
    Total OPCODE bits (Y) = 1 bit (type identifier) + 7 bits (operation identifier) = 8 bits.

2. Calculate the Sizing of the Register Fields:
• The processor contains 50 architectural registers.
• To address any one of these 50 unique registers, the number of bits required per field is:
    2⁵ < 50 ≤ 2⁶ → 6 bits per register field.

3. Calculate the Sizing of the UNUSED Field (X) in R-type format:
• An R-type instruction consists of: [ OPCODE ] [ UNUSED ] [ DST Register ] [ SRC Register 1 ] [ SRC Register 2 ].
• The total instruction size is 32 bits.
    32 = Y + X + (3 × Register Field Bits)
    32 = 8 + X + (3 × 6)
    32 = 8 + X + 18
    32 = X + 26 → X = 32 - 26 = 6 bits.

4. Calculate the Sizing of the Immediate Field (Z) in I-type format:
• An I-type instruction consists of: [ OPCODE ] [ DST Register ] [ SRC Register ] [ Immediate Value/Address ].
    32 = Y + (2 × Register Field Bits) + Z
    32 = 8 + (2 × 6) + Z
    32 = 8 + 12 + Z
    32 = 20 + Z → Z = 32 - 20 = 12 bits.

5. Compute the Final Expression (X + 2Y + Z):
• X = 6
• Y = 8
• Z = 12

    X + 2Y + Z = 6 + 2(8) + 12
    X + 2Y + Z = 6 + 16 + 12 = 34.

Explanation:
Let us evaluate the output of each logic gate step-by-step using minterm sets to find the final expression for Y.
1. Analyze the AND Gate Output:
The inputs to the AND gate are f₁ and f₂. The logical AND operation corresponds to the intersection (∩) of their minterm sets (the minterms present in both functions).
• f₁ = {0, 2, 3, 5, 7, 8, 11, 13}
• f₂ = {1, 3, 5, 7, 11, 13, 15}

    Output_AND = f₁ ∩ f₂ = {3, 5, 7, 11, 13}

2. Analyze the OR Gate Output:
The inputs to the OR gate are f₃ and f₄. The logical OR operation corresponds to the union (∪) of their minterm sets (combining all elements from both functions).
• f₃ = {0, 1, 4, 11}
• f₄ = {0, 2, 6, 13}

    Output_OR = f₃ ∪ f₄ = {0, 1, 2, 4, 6, 11, 13}

3. Analyze the Final XOR Gate Output (Y):
The final output Y is the XOR of Output_AND and Output_OR. The logical XOR operation corresponds to the symmetric difference (Δ) of the two sets (elements that are in either of the sets, but not both).
• Output_AND = {3, 5, 7, 11, 13}
• Output_OR = {0, 1, 2, 4, 6, 11, 13}

Let's find the common elements (intersection) first:
• Common minterms shared by both paths = {11, 13}

Filter out these common elements from the combined set to get the symmetric difference:
    Y = ∑(0, 1, 2, 3, 4, 5, 6, 7)

4. Evaluate the Minterm Options:
• Option (a): Y = ∑(0, 1, 2, 11, 13) — Incorrect.
• Option (c): Y = ∑(0, 1, 2, 3, 4, 5, 6, 7) — Correct.

5. Convert to Maxterm Form:
Since this is a 4-variable function, the total possible minterms span from 0 to 15. The product-of-maxterms (∏) expression consists of all the numbers missing from our sum-of-minterms list:
    Missing terms = {8, 9, 10, 11, 12, 13, 14, 15}
    Y = ∏(8, 9, 10, 11, 12, 13, 14, 15)

• Option (b): Y = ∏(3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15) — Incorrect.
• Option (d): Y = ∏(8, 9, 10, 11, 12, 13, 14, 15) — Correct.

6. Conclusion:
Options c and d are the logically valid statements for this digital network.

Explanation:
To determine the missing elements, let's break down how three-address code triples represent array accesses and assignments. A triple consists of three fields: op (operator), arg1, and arg2. When referencing the result of a previous operation, the row number enclosed in parentheses—like (0)—is used.
1. Analyze Triple (1): Array Indexing of s[i]
• The sub-expression is s[i].
• In three-address code triples, an array access/r-value lookup uses the array base address and index. The operator is represented as =[].
• Therefore, row (1) evaluates s[i]:
    (1) =[] s i
• This eliminates options (b) and (d), which specify []= (used for array assignment/l-value, not lookup).
2. Analyze Triple (2): Unary Minus
• Looking at the table, row (2) computes uminus (1), which represents -s[i]. This confirms our deduction for row (1) is correct.
3. Analyze Triple (3): Multiplication
• The expression requires multiplying (p+r) by -s[i].
• Row (0) computed + p r (which is p+r).
• Row (2) computed -s[i].
• Therefore, row (3) must perform the multiplication of row (0) and row (2):
    (3) * (0) (2)
4. Analyze Triples (4) and (5): Addition with u/w
• Row (4) computes / u w (which is u/w).
• Row (5) adds row (3) and row (4) together: + (3) (4). This represents the entire right-hand side of our assignment equation.
5. Analyze Triple (6): Target Array Location x[i]
• The value calculated in row (5) needs to be stored into the left-hand side array position x[i].
• Before a value can be assigned to an array element, we define its l-value location using the array base address and index with the element assignment operator []=.
• Therefore, row (6) targets the x[i] element:
    (6) []= x i
6. Analyze Triple (7): Assignment
• Row (7) shows = (6) (5), which copies the computed right-hand side expression from row (5) into the array destination specified in row (6).
7. Conclusion:
Matching our findings (1) =[] s i, (3) * (0) (2), and (6) []= x i directly corresponds to choice (c).

Explanation:
Let us analyze the logic using the hint provided: • len1 tracks the length of the longest subarray ending at X[i] containing all equal elements (a sequence of the current active element). • len2 tracks the length of the longest subarray ending at X[i] containing at most two distinct elements. At the very end of every iteration, the statement first = X[i]; runs. This means first always holds the element processed in the previous iteration, and second holds the distinct element seen right before that continuous sequence of first broke.
1. Finding Expression (P): • This block executes when X[i] == second.
• Since X[i] matches second, the old continuous sequence of first is broken.
• The new continuous sequence of equal elements now consists of the old second element plus the current X[i].
• Since second was located adjacent to the continuous block of first, the new continuous sequence length becomes the count of the previous continuous block (len1) plus 1 for the current element.
    (P) = len1 + 1
2. Finding Expression (Q): • This block executes when X[i] is completely new (does not match first or second).
• Since it is a third distinct element, we must drop the older distinct element (second) to keep at most two distinct elements.
• The new valid subarray can only consist of the most recent continuous block of equal elements (first) and the current new element X[i].
• Therefore, the new total length len2 becomes the length of the continuous block of first (which is len1) plus 1 for the current element.
    (Q) = len1 + 1
Conclusion: Both (P) and (Q) must be len1 + 1, matching option (c).