Digital Logic

\(X\) is the majority function. Two quick rules: \(X(p, p, r) = p\), and if two arguments differ, \(X\) equals the remaining one.

• (A) False: with \(a = b = 1\), \(c = d = e = 0\), the left side is \(X(1, 1, 0) = 1\) but the right side is \(X(1, 0, 0) = 0\).
• (B) True: if \(a = b\), both sides equal \(a\); if \(a \ne b\), the left side equals its third argument, \(X(a, b, c)\).
• (C) False: the right side is \(a \cdot c\); with \(a = b = 1\), \(c = d = 0\), the left side is \(X(1, 1, 0) = 1\) but the right side is 0.
• (D) True: \(X(a, c, c) = c\), so the right side is \(X(a, X(a, b, c), c)\); if \(a = c\) it equals \(a = X(a, b, c)\), and if \(a \ne c\) it equals the middle argument \(X(a, b, c)\).

Answer: B, D

To widen a 2’s complement number, copy its sign bit into every new position (sign extension). The sign bit of 1010 is 1, so \(-6\) is 1111 1010 in 8 bits and 1111 1111 1111 1010 in 16 bits.

• (A) False: 1000 1010 is \(-128 + 10 = -118\).
• (B) True: 1111 1010 is \(-128 + 122 = -6\).
• (C) False: 1000 0000 0000 1010 is \(-32768 + 10 = -32758\).
• (D) True: it is 1010 sign-extended to 16 bits, value \(-6\).

Answer: B, D

Write the minterms as \(b_3 b_2 b_1 b_0\): 0 = 0000, 2 = 0010, 4 = 0100, 8 = 1000, 10 = 1010, 11 = 1011, 12 = 1100. Group them on a K-map:

• \(\{0, 4, 8, 12\}\) all have \(b_1 = b_0 = 0\), giving \(\bar{b}_1 \bar{b}_0\).
• \(\{0, 2, 8, 10\}\) all have \(b_2 = b_0 = 0\), giving \(\bar{b}_2 \bar{b}_0\).
• 11 (1011) has only one neighbouring 1, namely 10 (1010), so it needs the pair \(\{10, 11\}\), giving \(b_3 \bar{b}_2 b_1\).

All three groups are essential and together cover exactly the seven minterms, so \(F = \bar{b}_1 \bar{b}_0 + \bar{b}_2 \bar{b}_0 + b_1 \bar{b}_2 b_3\). Option B misses minterm 11, C covers 14 and 15 (not in \(F\)), and D covers 1, 3, 5, 6 and 7.

Answer: A

From the circuit, \(D_1 = Q_0\), \(D_2 = Q_1\), \(D_3 = Q_2\) and \(D_0 = \overline{Q_3}\). Each clock shifts the bits one place and feeds the complement of the last bit back to the first: a 4-bit Johnson (twisted-ring) counter.

With the state written as \(Q_0Q_1Q_2Q_3\): 0000 → 1000 → 1100 → 1110 → 1111 → 0111 → 0011 → 0001 → 0000. The other 8 states form a second cycle of the same length (0100 → 1010 → 1101 → 0110 → 1011 → 0101 → 0010 → 1001 → 0100), so from any initial state the circuit comes back after 8 clocks.

That is 8 distinct states counting the initial one, or 7 besides it, so the official key accepts 7 to 8.

Answer: 8 (7 is also accepted)

Reading the three gates that feed the OR gate:

• the NAND gate gives \(\overline{XY}\);
• the NOT gate on \(X\) gives \(\overline{X}\);
• the AND gate gives \(X\overline{Y}\).

So \(F = \overline{XY} + \overline{X} + X\overline{Y}\), which is option C as written. By De Morgan's law \(\overline{XY} = \overline{X} + \overline{Y}\); the term \(\overline{X}\) repeats part of this and \(X\overline{Y}\) is absorbed by \(\overline{Y}\), so \(F = \overline{X} + \overline{Y} = \overline{XY}\). That is option A, and option B reduces to it the same way.

D is wrong: at \(X = Y = 1\), \(F = 0\) but \(X + \overline{Y} = 1\).

Answer: A, B, C

Each flip-flop in a ripple counter toggles on every active edge it receives, so its output completes one cycle for every two input cycles: each stage halves the frequency. The output of the 4th (last) flip-flop therefore runs at \(f_{clk}/2^{4} = f_{clk}/16\), and its period is 16 clock periods.

\(16\,T_{clk} = 64\ \mu\text{s} \Rightarrow T_{clk} = 4\ \mu\text{s} \Rightarrow f_{clk} = \frac{1}{4\ \mu\text{s}} = 250\ \text{kHz}\).

The counter’s frequency is its input clock frequency. Taking the last stage’s own frequency, \(1/64\ \mu\text{s} \approx 15.6\) kHz, is the usual slip.

Answer: 250

Read the map with the usual Gray-code order (00, 01, 11, 10) for \(wx\) and \(yz\). The four corner 1s are the cells with \(x = 0, z = 0\), and the central block of four 1s has \(x = 1, z = 1\). So \(F = \overline{x}\,\overline{z} + xz\), which is option D.

• A: its four 4-literal terms are exactly the four corner cells, and \(\overline{x}\,\overline{z}(\overline{w}\,\overline{y} + w\overline{y} + \overline{w}y + wy) = \overline{x}\,\overline{z}\), so A equals D.
• B: \(w\overline{x}yz\) has \(x = 0, z = 1\), a 0 cell, and two corner cells are missing.
• C: \(w\overline{x}\,\overline{y}z\) is also a 0 cell, and two corner cells are missing.

Answer: A, D

Read each word as sign (1 bit), biased exponent (8 bits) and fraction (23 bits); the value is \((-1)^{s} \times 1.f \times 2^{e - 127}\).

• 0xC1100000: sign 1, exponent 10000010 = 130, fraction 001000…, so \(X = -1.125 \times 2^{3} = -9\).
• 0x40C00000: sign 0, exponent 10000001 = 129, fraction 100000…, so \(Y = 1.5 \times 2^{2} = 6\).
• 0x41400000: sign 0, exponent 10000010 = 130, fraction 100000…, so \(Z = 1.5 \times 2^{3} = 12\).

Now check each option: (A) \(4(-9 + 6) + 12 = 0\); (B) \(12 - 12 = 0\); (C) \(-36 + 36 = 0\). (D) fails because \(-9 + 6 + 12 = 9\).

Answer: A, B, C

• (A) is wrong. The left side is \(\sum m(0, 3, 4, 5, 7)\) over \(ABC\). On the right, \(B\,C\) gives \(m_3, m_7\), \(\overline{B}\,\overline{C}\) gives \(m_0, m_4\) and \(\overline{A}\,\overline{B}\) gives \(m_0, m_1\): it contains 001 and misses 101. With \(A\,\overline{B}\) as the last term it would hold.
• (B) is the consensus theorem: \(BC = ABC + \overline{A}BC\), and these two terms are absorbed by \(AB\) and \(\overline{A}C\).
• (C) Expanding gives \(A\overline{A} + AB + \overline{A}C + BC = AB + \overline{A}C + BC\), which reduces to \(AB + \overline{A}C\) by (B).
• (D) By De Morgan, the complement of the product is the sum of the complemented factors: \(\overline{A}BD + \overline{C}\,\overline{D} + A\overline{C}\,\overline{D} + \overline{A}\,\overline{B}D\). The first and last terms combine to \(\overline{A}D\), and \(A\overline{C}\,\overline{D}\) is absorbed by \(\overline{C}\,\overline{D}\).

Answer: B, C, D

With 5 bits, 2’s complement covers \(-16\) to \(+15\). Decode the operands: \(A = 01010 = +10\), and \(B = 11010 = -6\) (invert and add 1 to get \(00110 = 6\)).

• \(A + B = 4\): in range.
• \(A - B = 10 + 6 = 16\): above \(+15\), so it overflows; the 5-bit result 10000 would read as \(-16\).
• \(B - A = -16\): exactly the most negative value, so it fits.
• \(2 * B = -12\): in range.

Only \(A - B\) leaves the representable range.

Answer: B