Processor Architectures and Boolean Algebra: Question 4

Worked solution

Part (a): Half adder

A half adder takes two single-bit inputs, A and B, and produces a Sum bit and a Carry bit.

• Sum is 1 only when exactly one of A, B is 1. This is the XOR relationship.
• Carry is 1 only when both A and B are 1. This is the AND relationship.

Sum = A XOR B (equivalently, (A.NOT B) + (NOT A.B)), and Carry = A.B.

[2 marks: 1 for the fully correct table, 1 for the correct Sum expression]

Part (b): Full adder

A full adder extends the half adder by also taking a carry-in, Cin, so it can be chained with other adders to add multi-bit numbers. Sum is 1 whenever an odd number of the three inputs are 1 (this is a three-input XOR); Cout is 1 whenever at least two of the three inputs are 1 (a “majority” function).

Checking a couple of rows: for A=1, B=0, Cin=1, exactly two of the three inputs are 1 (A and Cin), an even count, so Sum = 0, and since at least two inputs are 1, Cout = 1, matching the table. For A=1, B=1, Cin=1, all three inputs are 1, an odd count, so Sum = 1, and since at least two inputs are 1, Cout = 1, also matching the table.

Cout = A.B + A.Cin + B.Cin (Cout is 1 whenever at least two of the three inputs are 1).

[3 marks: 1 for the correct Sum column, 1 for the correct Cout column, 1 for the correct Cout expression]

Part (c): SR flip-flop

An SR flip-flop holds a single bit, Q, and responds to its S (set) and R (reset) inputs as follows: S = 1, R = 0 sets Q to 1; S = 0, R = 1 resets Q to 0; S = 0, R = 0 holds Q at its previous value (no change); and S = 1, R = 1 is not allowed.

(i) Tracing Q, starting at Q = 0:

• Step 1 (S = 1, R = 0. Set): Q becomes 1.
• Step 2 (S = 0, R = 0. Hold): Q keeps its previous value, so Q stays 1.
• Step 3 (S = 0, R = 1. Reset): Q becomes 0.

[2 marks: 1 mark per correct pair of consecutive values, e.g. 1 for Q = 1 after steps 1–2 and 1 for Q = 0 after step 3]

(ii) Why S = 1, R = 1 is invalid:

Setting S = 1 and R = 1 at the same time asks the flip-flop to set Q to 1 and reset Q to 0 at the same instant. Internally, an SR flip-flop is built so that Q and its complement (NOT Q) are always meant to be opposite to one another; S = R = 1 forces both Q and NOT Q to be driven towards the same value, which is a logical contradiction. This leaves the resulting output undefined (and unpredictable in a real circuit, depending on tiny timing differences between the gates), so this input combination is not allowed. [1 mark]

Part (d): JK flip-flop

A JK flip-flop behaves like an SR flip-flop for J = 0, K = 0 (hold), J = 0, K = 1 (reset), and J = 1, K = 0 (set). The key difference is that J = 1, K = 1 is a valid, defined input: instead of being disallowed, it makes the flip-flop toggle, invert its current output.

Tracing Q, starting at Q = 0:

• Step 1 (J = 1, K = 0. Set): Q becomes 1.
• Step 2 (J = 1, K = 1, toggle): Q inverts from 1 to 0.
• Step 3 (J = 1, K = 1, toggle): Q inverts from 0 to 1.

This is exactly where a JK flip-flop differs from an SR flip-flop: the equivalent input combination on an SR flip-flop (S = 1, R = 1) is invalid and leaves the output undefined, but a JK flip-flop is deliberately designed so that J = K = 1 is a valid, predictable input that simply toggles the stored bit, resolving the SR flip-flop’s invalid-state problem. [2 marks: 1 for the correct traced values (1, 0, 1), 1 for correctly explaining that J = K = 1 gives a defined toggle, unlike the invalid S = R = 1 on an SR flip-flop]

Final answers

• (a) Sum: 0, 1, 1, 0; Carry: 0, 0, 0, 1 (for AB = 00, 01, 10, 11). Sum = A XOR B, Carry = A.B.
• (b) Sum: 0, 1, 1, 0, 1, 0, 0, 1; Cout: 0, 0, 0, 1, 0, 1, 1, 1 (for ABCin = 000…111). Cout = A.B + A.Cin + B.Cin.
• (c)(i) Q = 1, 1, 0 after steps 1, 2, 3. (ii) S = R = 1 forces a contradiction between Q and NOT Q, leaving the output undefined.
• (d) Q = 1, 0, 1 after steps 1, 2, 3; J = K = 1 is a valid toggle input on a JK flip-flop, unlike the invalid S = R = 1 on an SR flip-flop.