Subtraction, Multiplication and Division in RTL

Addition is only half of an ALU's arithmetic. This lesson covers the other three operations an interview or a real datapath expects: subtraction with a correct overflow flag, a faster way to generate the partial products behind multiplication, and division — implemented here as this path's first design with a separate datapath and FSM controller, rather than a single combinational expression.

Reading time: about 11 minutes.

10.1 Two's-complement subtraction and overflow

Two's-complement subtraction is addition in disguise: A − B is computed as A + (−B), and negating a two's-complement number is simply inverting every bit and adding 1. An adder that can optionally invert its second operand and inject that same inversion signal as its carry-in computes addition or subtraction from one piece of hardware, with no separate subtractor circuit needed anywhere.

Detecting overflow is a separate question from detecting a carry, and the two are frequently confused. A carry-out only says whether the unsigned result exceeded the available bits; it says nothing about whether a signed result is wrong. Signed overflow has one clean rule, visible directly from the sign bits of the operands and the result: overflow occurs exactly when both operands share the same sign and the result's sign disagrees with them. Two numbers of opposite sign can never overflow when added (their sum's magnitude is no larger than the larger operand's magnitude), so the rule only has to watch same-sign operands.

module addsub8 (
    input  wire [7:0] a,
    input  wire [7:0] b,
    input  wire       sub,       // 0 = a + b, 1 = a - b
    output wire [7:0] result,
    output wire       overflow,  // signed overflow
    output wire       carry_out  // unsigned carry-out; for sub, 1 = no borrow (a >= b)
);
    wire [7:0] b_eff = sub ? ~b : b;
    wire       cin   = sub;
    wire [8:0] sum9  = {1'b0, a} + {1'b0, b_eff} + cin;

    assign result    = sum9[7:0];
    assign carry_out = sum9[8];
    assign overflow  = (a[7] == b_eff[7]) && (result[7] != a[7]);
endmodule

sub does both jobs a subtractor needs from one bit: it inverts b to form its one's complement, and it feeds the same bit in as cin, which supplies the "+1" that turns a one's complement into a two's complement. The overflow equation is the rule above, written directly in terms of a and the effective second operand b_eff — which already accounts for whether this is really an addition or a subtraction, since a subtraction's effective second operand is ~b, not b. For subtraction, carry_out does not mean "borrow": computing a + ~b + 1 produces a carry-out of 1 exactly when no borrow occurred (a ≥ b as unsigned numbers), so borrow = ~carry_out. An exhaustive sweep over all 131,072 combinations of a, b and sub, run silently after the four printed cases, confirms the result, the overflow flag and this carry convention.

PASS: a=80 b=80 sub=0 -> result=-96 ovf=1
PASS: a=5 b=3 sub=1 -> result=2 ovf=0
PASS: a=-100 b=50 sub=1 -> result=106 ovf=1
PASS: a=-10 b=3 sub=0 -> result=-7 ovf=0
ALL ADDSUB8 TESTS PASSED

The first case is the one worth reading twice: 80 + 80 = 160 is far outside signed 8-bit range (−128 to 127), so the hardware correctly reports overflow = 1 and a wrapped, meaningless result of −96 — exactly what the sign-bit rule predicts, since both operands are positive (sign 0) and the result's sign is 1. Yosys's synth and check report zero problems on this design, confirming it is pure combinational logic with no inferred storage.

10.2 Multiplication, and why Booth recoding helps

The Multipliers and Barrel Shifters lesson in the Digital Electronics path already built an array multiplier directly from AND gates and full adders — one partial product per multiplier bit, each one either a full copy of the multiplicand or all zeros, summed together. This lesson does not rebuild that circuit; its job is a genuinely different idea that reduces how many partial products have to be generated and summed in the first place.

Booth recoding (in its common 2-bit, or "radix-4", form) looks at the multiplier three bits at a time — the current pair plus the bit just below it — and replaces each pair with a single signed digit from {−2, −1, 0, +1, +2}, rather than with two separate 0-or-1 decisions. Because each recoded digit now covers two bit positions of the multiplier instead of one, a multiplier that needed n partial-product rows under the plain array-multiplication scheme needs only about n/2 rows under Booth recoding — fewer rows to add together, at the cost of each row now needing a simple shift-and-optionally-negate instead of a plain AND gate.

The pattern behind the table is a run-detection idea: a string of 1s in the multiplier, under plain binary multiplication, forces one partial product per bit in the run. Booth recoding instead treats the start of a run of 1s as "subtract here" and the end of the run as "add here," since a run of k ones is numerically identical to (2^k − 1) — one large addition and one small subtraction replace k separate additions. That run-skipping view is the intuition behind radix-2 Booth, and on its own it does not reduce the row count of a parallel multiplier: an alternating 0101… pattern makes radix-2 Booth produce a nonzero digit at every bit. Radix-4 Booth, the table above, works differently: it scans overlapping 3-bit groups and emits exactly one digit in {−2, …, +2} for every 2 multiplier bits, so an n-bit signed multiplier always yields ⌈n/2⌉ partial products regardless of its bit pattern (plus one extra row for an unsigned multiplier, to supply its zero sign bit). The halving comes from scanning two bits per digit; the ±2M entries are simply what lets every 3-bit pattern map to some digit. This table is the recoding step alone; wiring its output into an actual summation network reuses the full-adder tree the array-multiplier lesson already built, which is why that circuit is not rebuilt here — Booth recoding changes how many rows reach the adder tree, not what the adder tree itself does with them.

10.3 Restoring division as a datapath

Division does not fit a single combinational block well: the long-division method taught by hand — bring down a digit, compare, subtract or not, shift, repeat — is inherently a multi-step process, and building it as RTL means building both a datapath (the registers and arithmetic it actually needs) and a controller (an FSM sequencing those steps), the same project structure this path's capstone, lesson 12, will scale up. Earlier lessons built multi-cycle FSMs and counters, but this is the first design split explicitly into a datapath and the controller that sequences it.

Restoring division is the direct hardware form of binary long division. Held in a combined shift register {A, Q} — A the running partial remainder, Q initially the dividend — each iteration: shift {A, Q} left by one bit, subtract the divisor M from A, and then look at the sign of that subtraction. If the subtraction went negative, the guess was wrong: A must keep its pre-subtraction value, and the quotient bit is 0. If it stayed non-negative, keep the subtracted value and record a 1 quotient bit. The RTL below computes A − M combinationally and simply does not commit it to the register when it is negative (the "non-performing" form); a datapath that wrote A − M into A first would instead restore it by adding M back on the next step, which is where the name comes from. After n iterations (for n-bit operands), Q holds the quotient and A holds the remainder.

// Controller next-state logic
always @* begin
    case (state)
        S_IDLE:    next_state = start ? (divisor == 0 ? S_DONE : S_SHIFT) : S_IDLE;
        S_SHIFT:   next_state = S_RESTORE;
        S_RESTORE: next_state = (count == N - 1) ? S_DONE : S_SHIFT;
        S_DONE:    next_state = S_IDLE;
        default:   next_state = S_IDLE;
    endcase
end

// Datapath: shift, then conditionally subtract-and-restore
wire [N:0] a_shifted  = {a[N-1:0], q[N-1]};
wire [N:0] a_minus_m  = a - {1'b0, m};
// in S_SHIFT:   a <= a_shifted;  q <= {q[N-2:0], 1'b0};
// in S_RESTORE: if (a_minus_m[N])  a <= a;                       // restore, quotient bit 0
//               else               a <= a_minus_m;
//                                  q <= {q[N-1:1], 1'b1};        // quotient bit 1

The guard bit is a similar one-extra-bit trick to the synchronous FIFO's pointers in the common-RTL-blocks lesson, used for a different purpose (there the extra bit tells full from empty as a wrap indicator; here it is a sign): a is declared one bit wider (N+1 bits) than the operand width specifically so a_minus_m[N] can serve as a clean sign bit — if the subtraction's result is genuinely negative, that top bit is 1, and there is no ambiguity between "negative" and "a large positive number that happens to use the same bit pattern."

PASS: 13 / 4 = q3 r1
PASS: 15 / 3 = q5 r0
PASS: 7 / 9 = q0 r7
CASE 9 / 0 -> div_by_zero=1 (quotient=15 remainder=9)
PASS: 0 / 5 = q0 r0
ALL RESTORING_DIV TESTS PASSED

This run exercises the full lifecycle a division controller needs to get right: an ordinary case with both a nonzero quotient and remainder (13/4), an exact division (15/3), a case where the dividend is smaller than the divisor so the quotient is 0 and the remainder is the whole dividend (7/9), a deliberate divide-by-zero that the controller catches in S_IDLE before ever entering the shift/restore loop, and the dividend-is-zero edge case. Yosys's synth and check on this design report only flip-flop cells ($_DFFE_..._ and $_DFF_..._) for every register and zero inferred latches — confirmed by inspecting the cell list directly, not merely trusted from a summary line, which matters because a missing default assignment anywhere in this FSM's datapath block would silently turn a register into a latch instead of failing loudly.

10.4 Interview questions

Why does an adder/subtractor need only one extra control bit, rather than a separate subtractor circuit? Two's-complement negation is invert-and-add-1, and an XOR with the control bit performs the invert (for both polarities of sub) while that same bit, fed into cin, supplies the add-1 — one adder, one bit, both operations.

Why can two numbers of opposite sign never cause signed overflow when added? Their sum's magnitude is no larger than the larger operand's magnitude, which is already representable, so the result can never leave the representable range. Overflow is only possible when both operands share a sign and their magnitudes combine to exceed it.

What problem does Booth recoding actually solve, and what does it not change? Radix-4 Booth reduces how many partial-product rows a multiplier has to generate and sum: it scans overlapping 3-bit groups and emits one digit in {−2..+2} per 2 multiplier bits, giving ⌈n/2⌉ rows for any bit pattern (one more for an unsigned multiplier). Run-skipping, replacing a run of 1s with one addition and one subtraction, is the radix-2 intuition and does not by itself guarantee fewer rows. It does not change how those rows are ultimately summed — that is still the same full-adder tree the array-multiplier lesson builds.

Why does the restoring-division datapath need a guard bit on its remainder register? Without an extra bit beyond the operand width, a genuinely negative subtraction result and a large positive one can share the same bit pattern. The extra bit gives the sign of the subtraction an unambiguous place to live. The synchronous FIFO uses a similar one-extra-bit trick on its pointers, but there the bit is a wrap indicator that separates full from empty, not a sign.