Digital Design / Module 2: Combinational building blocks
10. Subtractors, comparators and an ALU
Combine blocks into a datapath.
See it move
The idea
An ALU is a set of operations computed in parallel, with a mux choosing the result. Conceptually, every operation runs each cycle, and the opcode only picks which answer to keep. Sharing one adder between add and subtract saves area.
Subtraction
A - B = A + ~B + 1. Feed B through XOR gates controlled by a sub signal, and use the same signal as the carry in. One small addition turns the adder into an adder-subtractor.
Flags
| Flag | Meaning | How it is computed |
|---|---|---|
| Z | Result is zero | NOR of all result bits |
| N | Result is negative | Top bit of the result |
| C | Unsigned carry out | Carry out of the top bit |
| V | Signed overflow | Carry into top bit XOR carry out of it |
Signed overflow, explained
Adding two positive numbers and getting a negative result can't be right, and neither can adding two negatives and getting a positive. An addition of opposite signs can never overflow. In 8 bits, 127 + 1 produces 10000000, which is fine as unsigned 128 but wrong as signed -128. So V = 1 and C = 0. Each flag answers a different question, and which one to look at depends on how you are reading the bits.
Comparators
Equality is simple: XOR the bits, then NOR the results. Less-than is simplest as a subtraction. For unsigned values, A < B when A - B has no carry out (given the A + ~B + 1 form). For signed values, A < B when N ^ V is 1.
always @(*) begin
case (op)
2'b00: {c, r} = a + b;
2'b01: {c, r} = a + {1'b0, ~b} + 1'b1; // see the note below
2'b10: begin r = a & b; c = 1'b0; end
default: begin r = a ^ b; c = 1'b0; end
endcase
z = (r == 0);
endA width trap in that code
Writing a + ~b + 1 directly would be wrong here. The 9-bit target makes Verilog extend b to 9 bits before inverting it, so the top bit becomes 1 and the carry comes out inverted. Writing {1'b0, ~b} inverts first, then extends.
Common mistake
Using the N flag alone to decide a signed less-than. If the subtraction overflowed, N has the wrong sign. That is why the correct test is N ^ V.
Key ideas
- Subtract with A + ~B + 1.
- Signed overflow occurs when the carries into and out of the sign bit differ.
- Equality is a reduction NOR of a bitwise XOR.
Your exercise
Find the bug
This code has one deliberate bug. Read the symptom, then click the line you think is wrong.
{c, r} is 9 bits wide. At what width does Verilog evaluate ~b, and what happens to its top bit?The fix
{c, r} = a + {1'b0, ~b} + 1'b1;Why it failed
Verilog sizes the whole expression to its widest part, here 9 bits, before it does anything else. So b is extended to 9 bits first and then inverted, which makes bit 8 a 1 instead of a 0. The 8-bit result is unaffected, so simple tests pass while the flag is wrong.
Interview questions
coreHow do you detect signed overflow?
XOR the carry into the MSB with the carry out of it; equivalently, same-sign operands giving an opposite-sign result.
basicCompute 20 - 13 in 8 bits as A + ~B + 1. What is the carry out?
13 is 00001101, so ~B is 11110010, which is 242. Then 20 + 242 + 1 = 263, which is 1_00000111 in nine bits: the result is 7 and the carry out is 1. For unsigned subtraction, a carry out of 1 means no borrow, so A was at least B.
basicHow do you produce a zero flag for an 8-bit result r in Verilog?
Use a reduction NOR: assign z = ~|r;. The reduction OR is 1 if any bit is 1, so its inverse is 1 only when all bits are 0. Writing r == 8'd0 describes the same hardware.
coreIn 8 bits, compute -100 + -100. Give the result and the C, V, N and Z flags.
-100 is 0x9C, and 0x9C + 0x9C = 0x138. The 8-bit result is 0x38 = +56, with a carry out, so C = 1. Two negatives produced a positive, so V = 1. The top result bit is 0, so N = 0, and Z = 0. The true answer, -200, is outside -128 to +127.
coreThe 8-bit patterns A = 50 and B = 200 are compared by computing A - B. Is A less than B? Answer for unsigned and for signed.
The subtraction gives 106 with C = 0, N = 0 and V = 0. Unsigned: no carry out means a borrow, so 50 < 200 is true. Signed: B's pattern is -56, so A - B = 106 fits without overflow, N XOR V = 0, and A is not less than B. Same wires and the same subtraction give opposite answers, and both are correct for their reading.
coreThis adder-subtractor line gives r = 7 but c = 0 for 20 - 13, although the carry out should be 1. Why?
reg [7:0] a, b, r;
reg c;
always @(*) {c, r} = a + ~b + 1'b1;The 9-bit target makes Verilog extend b to 9 bits before applying ~, so its new top bit becomes 1. That extra 1 adds 256 to the sum and flips the carry: 20 + 498 + 1 = 519, whose low nine bits are 0_00000111. Invert first, then extend: a + {1'b0, ~b} + 1'b1 gives c = 1 and r = 7.
coreWhy do ALUs share one adder for addition and subtraction instead of having a separate subtractor?
Subtraction is A + ~B + 1, so one row of XOR gates controlled by a sub signal inverts B on demand, and the same signal feeds the carry in to add the one. That costs N XOR gates rather than a second N-bit adder with its own carry chain. The comparisons then come almost free from the subtraction's flags.
advancedWith signed 8-bit A = -128 and B = 1, compute A - B and the flags. Does N XOR V correctly report A < B?
0x80 + 0xFE + 1 = 0x17F, so the result is 0x7F = +127 with C = 1. The true answer, -129, does not fit, so V = 1, and N = 0 because the top bit is 0. N alone says A is not less than B, which is wrong; N XOR V = 1 correctly says A < B. As unsigned, 128 is not less than 1, and C = 1 agrees.
advancedWrite the signed overflow flag for an 8-bit subtraction d = a - b using only sign bits.
wire [7:0] d = a - b; wire v = (a[7] ^ b[7]) & (d[7] ^ a[7]);
Subtraction can only overflow when the operands have different signs, and then overflow shows up as a result whose sign differs from a. So V = (a[7] ^ b[7]) & (d[7] ^ a[7]). This is equivalent to comparing the carry into and out of the top bit, but it needs only the three sign bits.