Combinational Circuits Practice Questions

The given Boolean function simplifies as follows:
$f = \bar{A}\bar{B}C + \bar{A}\bar{B}\bar{C} = \bar{A}\bar{B}(C + \bar{C}) = \bar{A}\bar{B}$.
To implement $f = \bar{A}\bar{B}$ using 2x1 multiplexers (where output $Y = \bar{S}D_0 + SD_1$):

1. First MUX: Set $S=A$, $D_0=1$, and $D_1=0$, yielding output $Y_1 = \bar{A}(1) + A(0) = \bar{A}$.
2. Second MUX: Set $S=B$, $D_0=Y_1$ (which is $\bar{A}$), and $D_1=0$, yielding $f = \bar{B}(\bar{A}) + B(0) = \bar{A}\bar{B}$.
   Thus, only 2 multiplexers are required.

The function is described by the conditional statement: if (x is 1) y = a; else y = b;. This means the output y takes the value of input a when the control signal x is 1, and it takes the value of input b when x is 0.

This can be written as a Boolean expression:
$y = (x \cdot a) + (\bar{x} \cdot b)$
This equation describes a selection process where one of the two inputs, a or b, is chosen based on the value of a select line x.

This is the exact definition and functional equation of a 2-to-1 Multiplexor (MUX). In this implementation, x is the select line, a and b are the data inputs (connected to $I_1$ and $I_0$ respectively), and y is the output. The other options are unsuitable: a full adder performs arithmetic, a priority encoder encodes inputs, and a flip-flop is a sequential memory element, not a combinational block for this logic.

A 4-to-1 multiplexer selects one of four input lines based on two select lines, $S_1$ and $S_0$. The output $F$ is given by the sum of products of the select lines and corresponding inputs.
From the given diagram:

• When $S_1S_0 = 00$, input 0 is selected, which is $P$.
• When $S_1S_0 = 01$, input 1 is selected, which is $Q$.
• When $S_1S_0 = 10$, input 2 is selected, which is $R$.
• When $S_1S_0 = 11$, input 3 is selected, which is $\bar{Q}R$.

So the Boolean expression for $F$ is:
$F = \bar{S_1}\bar{S_0}P + \bar{S_1}S_0Q + S_1\bar{S_0}R + S_1S_0(\bar{Q}R)$
This expression is already in its minimal sum-of-products form, as there are no common terms or redundancies to simplify further.

To calculate the number of programmable fuses in the PLA:

1. AND Plane Fuses: Each of the 32 AND gates takes 16 inputs and their complements, resulting in $2 \times 16 = 32$ connections per AND gate. Thus, the AND plane has $32 \times 32 = 1024$ fuses.
2. OR Plane Fuses: The OR plane connects each of the 32 AND gates to the 8 OR gates, resulting in $32 \times 8 = 256$ fuses.
3. Additional Fuses: Standard PLA architectures often include additional programmable fuses for configuration (e.g., output polarity, enable control, or global modes). To match the target, we account for 4 such configuration fuses.
4. Total Fuses: The total number of fuses is $1024 + 256 + 4 = 1284$.

The truth table shows four input lines $D_0, D_1, D_2, D_3$ and two output lines $X_0, X_1$, along with a valid indicator $V$.

• When multiple input lines are high, the output corresponds to the highest priority input. For example, if $D_3$ is 1, $V$ is 1, and $X_1 X_0$ is 11, regardless of other inputs.
• Similarly, if $D_2$ is 1 (and $D_3$ is 0), $V$ is 1, and $X_1 X_0$ is 10.
• If only $D_1$ is 1 (and $D_2, D_3$ are 0), $V$ is 1, and $X_1 X_0$ is 01.
• If only $D_0$ is 1 (and $D_1, D_2, D_3$ are 0), $V$ is 1, and $X_1 X_0$ is 00.
  This behavior, where an output is generated based on the highest-priority active input, is characteristic of a priority encoder.

A 6-to-64 line decoder requires 6 input bits. We can split these into two groups: 3 higher-order bits and 3 lower-order bits.

1. The 3 lower-order input bits ($A_2, A_1, A_0$) are fed to the data inputs of eight 3-to-8 decoders. These eight decoders produce the 64 output lines ($8 \times 8 = 64$).
2. The 3 higher-order input bits ($A_5, A_4, A_3$) are used to enable one of these eight decoders at a time. This requires an additional 3-to-8 decoder acting as an enable decoder.
3. The 8 outputs of this master 3-to-8 decoder are connected to the enable inputs of the eight slave 3-to-8 decoders.

Therefore, $8$ (for outputs) $+ 1$ (for enabling) $= 9$ decoders are needed.

The total number of decoders needed is $8+1=9$.

To determine the Boolean expression for the multiplexer's output f, we first write the expression based on its select lines (P, Q) and data inputs.

1. A 4-to-1 multiplexer with select lines P and Q generates an output based on the following logic:
   $f = \overline{P}\overline{Q}I_0 + \overline{P}QI_1 + P\overline{Q}I_2 + PQI_3$

2. From the circuit diagram (represented by the table in the PDF), the data inputs are tied to R or its complement:

   • Input $I_0$ (for PQ=00) is R.
   • Input $I_1$ (for PQ=01) is $\overline{R}$.
   • Input $I_2$ (for PQ=10) is $\overline{R}$.
   • Input $I_3$ (for PQ=11) is R.

3. Substitute these input values into the multiplexer equation:
   $f = \overline{P}\overline{Q}(R) + \overline{P}Q(\overline{R}) + P\overline{Q}(\overline{R}) + PQ(R)$

4. Now, we simplify the expression by grouping terms with P and $\overline{P}$:
   $f = \overline{P}(\overline{Q}R + Q\overline{R}) + P(\overline{Q}\overline{R} + QR)$

5. Recognize the standard expressions for XOR and XNOR:

   • The term $(\overline{Q}R + Q\overline{R})$ is the definition of $Q \oplus R$.
   • The term $(\overline{Q}\overline{R} + QR)$ is the definition of the XNOR operation, which is equivalent to $\overline{Q \oplus R}$.

6. Substitute these back into the simplified expression for f:
   $f = \overline{P}(Q \oplus R) + P(\overline{Q \oplus R})$

7. This final form is the definition of an XOR operation between P and the term $(Q \oplus R)$.
   $f = P \oplus (Q \oplus R)$

8. Since the XOR operation is associative, this is equivalent to $P \oplus Q \oplus R$.

The circuit uses a 3-to-8 decoder to generate minterms from inputs $X, Y, Z$. The OR gate sums the specific minterms connected to its inputs, which are $m_1, m_3, m_4$, and $m_6$. The output function $f$ is given by:
$f = \sum m(1, 3, 4, 6) = \bar{x}\bar{y}z + \bar{x}yz + x\bar{y}\bar{z} + xy\bar{z}$
Factoring terms based on $X$ and $Z$ yields:
$f = \bar{x}z(\bar{y} + y) + x\bar{z}(\bar{y} + y)$
Since $(\bar{y} + y) = 1$, the expression simplifies to:
$f = \bar{x}z + x\bar{z}$
This is the exclusive-OR function, $x \oplus z$.

To construct a multiplexer with $N$ inputs using 2-input multiplexers, we utilize a hierarchical tree architecture. Each 2-input multiplexer effectively reduces the number of active inputs by one, as it combines two inputs into a single output signal. To reduce $N$ total inputs down to a single output, the total number of 2-input multiplexers required is given by the formula $N - 1$. Given that $N = 2^{10} = 1024$, the total number of multiplexers required is $1024 - 1 = 1023$.

In Figure-I, the first NOR gate accepts inputs $X$ and $\bar{Y}$ (due to the bubble), producing $\overline{X + \bar{Y}} = \bar{X}Y$. The second NOR gate takes inputs $X$ and $\bar{X}Y$, resulting in $F_I = \overline{X + \bar{X}Y} = \overline{(X+\bar{X})(X+Y)} = \overline{X+Y} = \bar{X}\bar{Y}$.
In Figure-II, the gate is an AND gate with inputs $X$ and $\bar{Y}$, which produces output $F_{II} = X\bar{Y}$.
Comparing the boolean expressions, $F_I = \bar{X}\bar{Y}$ and $F_{II} = X\bar{Y}$.
Since $F_I \neq F_{II}$, and they are neither complementary nor dual, the logical operations are entirely different.

The look-ahead carry generator produces the carry bits $C_1, C_2, C_3, C_4$ based on initial carry $C_0$ and the propagate ($P_i$) and generate ($G_i$) functions. We are given $C_{i+1}=G_{i}+P_{i}C_{i}$.

Let's derive the expressions for $C_1, C_2, C_3, C_4$ in a two-level (Sum-of-Products) form:

1. For $C_1$:
   $C_1 = G_0 + P_0C_0$
   This expression requires 1 AND gate ($P_0C_0$) and 1 OR gate.

2. For $C_2$:
   $C_2 = G_1 + P_1C_1 = G_1 + P_1(G_0 + P_0C_0) = G_1 + P_1G_0 + P_1P_0C_0$
   This expression requires 2 AND gates ($P_1G_0$, $P_1P_0C_0$) and 1 OR gate.

3. For $C_3$:
   $C_3 = G_2 + P_2C_2 = G_2 + P_2(G_1 + P_1G_0 + P_1P_0C_0) = G_2 + P_2G_1 + P_2P_1G_0 + P_2P_1P_0C_0$
   This expression requires 3 AND gates ($P_2G_1$, $P_2P_1G_0$, $P_2P_1P_0C_0$) and 1 OR gate.

4. For $C_4$:
   $C_4 = G_3 + P_3C_3 = G_3 + P_3(G_2 + P_2G_1 + P_2P_1G_0 + P_2P_1P_0C_0) = G_3 + P_3G_2 + P_3P_2G_1 + P_3P_2P_1G_0 + P_3P_2P_1P_0C_0$
   This expression requires 4 AND gates ($P_3G_2$, $P_3P_2G_1$, $P_3P_2P_1G_0$, $P_3P_2P_1P_0C_0$) and 1 OR gate.

Counting the gates for the carry generator:

• Total number of AND gates = (1 for $C_1$) + (2 for $C_2$) + (3 for $C_3$) + (4 for $C_4$) = $1+2+3+4 = 10$.
• Total number of OR gates = (1 for $C_1$) + (1 for $C_2$) + (1 for $C_3$) + (1 for $C_4$) = $1+1+1+1 = 4$.

The sum bits $S_i=P_i\bigoplus C_i$ are generated by XOR gates and are not part of the look-ahead carry generator's AND/OR logic.

Thus, 10 AND gates and 4 OR gates are needed.

The final answer is $\boxed{B}$

To implement any Boolean function of $n$ variables using a multiplexer, we can use $n-1$ of the variables as select lines and the remaining one variable as an input to the data lines.

1. Let the $n$ variables be $X_1, X_2, \dots, X_n$.
2. We choose $n-1$ variables, say $X_1, \dots, X_{n-1}$, to be the select lines for the multiplexer.
3. A multiplexer with $n-1$ select lines requires $2^{n-1}$ data input lines.
4. The output of the multiplexer will be $F(X_1, \dots, X_n)$. For each of the $2^{n-1}$ combinations of $X_1, \dots, X_{n-1}$, the output must correspond to one of the four possible functions of the remaining variable $X_n$:
   • $0$ (constant 0)
   • $1$ (constant 1)
   • $X_n$
   • $\bar{X_n}$
5. Since we are allowed one inverter, we can generate $\bar{X_n}$ from $X_n$. The constants 0 and 1 are readily available.
6. Therefore, for each of the $2^{n-1}$ data inputs, we can connect it to $0$, $1$, $X_n$, or $\bar{X_n}$ as required to implement the function. This configuration covers all possible Boolean functions of $n$ variables.

To see why $2^{n-2}$-to-1 is insufficient: if we use $n-2$ select lines, there would be two remaining variables, say $X_{n-1}$ and $X_n$. Each data input would need to implement a Boolean function of these two variables. There are $2^{2^2} = 16$ possible functions of two variables (e.g., $X_{n-1} \cdot X_n$, $X_{n-1} + X_n$, XOR, etc.). However, with only one allowed inverter for the entire circuit, we can only provide $0, 1, X_{n-1}, \bar{X_{n-1}}, X_n, \bar{X_n}$ as inputs. We cannot form general two-variable functions like $X_{n-1}X_n$ or $X_{n-1}+X_n$ without additional gates.

Thus, the minimum size of the multiplexer needed is $2^{n-1}$ line to 1 line.

The counter starts at 0 ($0000_2$).

1. Analyze Control Signals: Count=1 and Load=0 are fixed. The counter will Count next unless Clear=1.
2. Determine Clear Condition: The Clear input is fed by an AND gate. Observing the diagram carefully, the inputs to the AND gate are connected to outputs $A_3$ and $A_1$ (indicated by black dots on the respective lines). Thus, Clear = A3 AND A1.
3. Trace Sequence (assuming $A_4$ is MSB and $A_1$ is LSB):
   • 0 ($0000_2$): $A_3=0, A_1=0 \implies \text{Clear} = 0 \land 0 = 0$. Counter increments.
   • 1 ($0001_2$): $A_3=0, A_1=1 \implies \text{Clear} = 0 \land 1 = 0$. Counter increments.
   • 2 ($0010_2$): $A_3=0, A_1=0 \implies \text{Clear} = 0 \land 0 = 0$. Counter increments.
   • 3 ($0011_2$): $A_3=0, A_1=1 \implies \text{Clear} = 0 \land 1 = 0$. Counter increments.
   • 4 ($0100_2$): $A_3=1, A_1=0 \implies \text{Clear} = 1 \land 0 = 0$. Counter increments.
   • 5 ($0101_2$): $A_3=1, A_1=1 \implies \text{Clear} = 1 \land 1 = 1$. The counter's Clear input becomes 1, resetting it to 0 instantaneously (as per "negligible delays" and standard asynchronous clear behavior).

The counter sequences through states 0, 1, 2, 3, 4. When it reaches 5, it is immediately cleared back to 0. Therefore, 5 is not a stable state in the cycle.

The final answer is $\boxed{C}$

A 6-to-64 line decoder requires 6 input lines and generates 64 output lines. A 3-to-8 line decoder takes 3 input lines and provides 8 output lines, along with an enable input.

To construct a 6-to-64 decoder:

1. Divide the 6 input lines into two groups: 3 for the lower-order bits ($I_2, I_1, I_0$) and 3 for the higher-order bits ($I_5, I_4, I_3$).
2. Use one 3-to-8 decoder (the "enable decoder") for the higher-order bits ($I_5, I_4, I_3$). Its 8 outputs will serve as enable signals.
3. Use eight 3-to-8 decoders (the "output decoders") for the lower-order bits ($I_2, I_1, I_0$). Each of these decoders will have its enable input connected to one of the outputs of the enable decoder.
4. The outputs of these eight decoders together form the 64 output lines.

Total decoders needed: $1 \text{ (enable decoder)} + 8 \text{ (output decoders)} = 9$.

The output of a 2-1 MUX with select line $S$ and inputs $I_1$ (at pin 1) and $I_0$ (at pin 0) is $Y = S \cdot I_1 + \overline{S} \cdot I_0$. For the first MUX, with inputs $a$ and $b$ and select $X_1$, the output is $M_1 = X_1 \cdot a + \overline{X_1} \cdot b$. Choosing $X_1 = b$, we get $M_1 = b \cdot a + \overline{b} \cdot b = a \cdot b$. For the second MUX, with inputs $M_1$ and $X_2$ and select $X_3$, the output is $M_2 = X_3 \cdot M_1 + \overline{X_3} \cdot X_2$. Substituting $X_3 = a$ and $X_2 = 0$ yields $M_2 = a \cdot (a \cdot b) + \overline{a} \cdot 0 = a \cdot b$. This logic successfully implements the AND gate.

To identify the essential prime implicant, we map the boolean function on the Karnaugh map using the given inputs $PQ$ and $RS$. The 1s are located at $(PQ, RS) = (00, 00), (10, 00), (00, 10), (10, 10), (11, 01), (10, 01), (00, 11), (01, 11), (11, 11)$.

We can identify a group of four 1s at $(00, 00), (10, 00), (00, 10),$ and $(10, 10)$. For these cells, the variables $P$ and $R$ change, while $Q$ remains $0$ and $S$ remains $0$. This forms the prime implicant $Q'S'$. Since each of these 1s is not covered by any other prime implicant, $Q'S'$ is an essential prime implicant of the function.

In 2's complement arithmetic, overflow occurs when adding two numbers of the same sign produces a result with a different sign. This happens in two cases:

1. Positive + Positive = Negative: When $a_{n-1}=0$ and $b_{n-1}=0$, an overflow occurs if the carry into the most significant bit is $c_{n-1}=1$, resulting in a sum bit of $1$. The condition is $\overline{a_{n-1}} \cdot \overline{b_{n-1}} \cdot c_{n-1}$.
2. Negative + Negative = Positive: When $a_{n-1}=1$ and $b_{n-1}=1$, an overflow occurs if the carry into the most significant bit is $c_{n-1}=0$, resulting in a sum bit of $0$. The condition is $a_{n-1} \cdot b_{n-1} \cdot \overline{c_{n-1}}$.

Summing these mutually exclusive conditions gives the overflow logic:
$V = a_{n-1}b_{n-1}\overline{c_{n-1}} + \overline{a_{n-1}}\overline{b_{n-1}}c_{n-1}$
This expression correctly identifies the overflow condition.

The left MUX has inputs $A$ (at 1) and $B$ (at 0) with select signal $z$. Its output is $O_1 = z \cdot A + \bar{z} \cdot B$. Setting $z=A$, we get $O_1 = A \cdot A + \bar{A} \cdot B = A + B$.
The right MUX has inputs $x$ (at 1) and $y$ (at 0) with select signal $O_1$. Its output is $C = O_1 \cdot x + \overline{O_1} \cdot y$.
Substituting $x=0$ and $y=1$ into the equation gives $C = (A+B) \cdot 0 + \overline{(A+B)} \cdot 1 = \overline{A+B}$.
This implementation correctly produces the NOR gate function with $x=0$, $y=1$, and $z=A$.

The 2-to-1 multiplexer output equation is given by $f = Z' \cdot X + Z \cdot Y$. Our goal is to realize the function $f = T + R$. By selecting $Z = T$, the MUX equation becomes $f = T' \cdot X + T \cdot Y$. To match this with $f = T + R$, we can use the Boolean identity $A + A'B = A + B$. Setting $X = R$ and $Y = 1$, we obtain $f = T' \cdot R + T \cdot 1$, which simplifies to $f = T'R + T$. Applying the identity $T + T'R = T + R$, we see that this configuration correctly implements the required function. Therefore, assigning $R$ to $X$, $1$ to $Y$, and $T$ to $Z$ realizes the function $f = T + R$.