The ALU on Ben Eater’s original Bentium 8-bit computer has two operations: add (ADD) and subtract (SUB). This gives his design the ability to add and subtract 8-bit numbers. But if you want to add or subtract larger numbers then you need more than 8 bits.
You could do this by expanding to a 16-bit design, but even with this you’d still be limited to the 16-bit size of the bus, registers and ALU. What if you wanted to be able to add and subtract arbitrarily large numbers? For that you need the ability to store numbers across multiple bytes/words, and you need an ALU which can handle those multi-byte numbers.
As you may remember from Ben’s computer if the result of a sum is too large for a single byte then you get a ‘carry’ out. To be able to do multi-byte arithmetic the ALU needs some way to feed that carry into the next calculation.
To be able to do this the ALU needs to have add with carry (ADC) and subtract with carry (SBC) operations1. I also wanted my ALU to have increment (INC) and decrement (DEC) operations. As the names imply those operations either add one or subtract one from the operand and enable faster processing of, for example, loop counters2.
Recap
First, lets have a reminder of how Ben’s ALU works. He has two registers, A and B3, which feed into a pair of 74LS283 4-bit adders. An ADD operation is very simple: feed the two registers in and read the output.
A SUBtraction takes a little more work. We need to do a bitwise invert of the operand to be subtracted (the B register) and then add 1 (watch Ben’s video on two’s complement arithmetic). In other words the operation A – B becomes A + ~B + 1 (where ~ means a bitwise inversion).
Ben’s design does this with a pair of 74LS86 XOR gate ICs to do the inversion when the subtract control signal is high. He also uses the subtract control signal as the carry in to the adder ICs.
ADC (Add With Carry)
Now lets look at how we can extend that design to add our extra functionality.
First up is add with carry (ADC). We can think of this operation as A + B + c (where c is the carry flag).
To do this we simply need to use the current value of the carry flag as the carry in to the adder ICs. So we need a way to select whether the carry in comes from the carry flag or the subtract control signal.
Lets do this by adding an extra control signal which I’ll call ‘use_carry’.
SBC (Subtract With Carry)
Subtract with carry means that if the carry flag is set then we subtract one from the result of the calculation. In other words we’re calculating A – B – c. Rewriting this as an addition we get A + ~B + 1 – c.
Given that we’re already using the carry in for the + 1 section of that equation, how do we perform the – c? Do we have to add lots of extra circuitry or do an additional operation?
Actually no. Look at the 1 – c part of that equation and remember that c is either a 1 or a zero and you’ll see that all we’re doing is inverting c. If c is 1 then 1 – 1 = 0 and if c is 0 then 1 – 0 = 1.
It’s interesting to refer back to the ADD and SUB without carry operations. For ADD we set carry in to 0, for SUB we set carry in to 1. And we’re using the subtract signal for this. But you can also think of this as always passing in a zero but inverting it for a subtraction.
And this inverting if it’s a subtraction is exactly what we’re doing for our ADC/SBC with carry operations.
So, the next thing we need to add to our circuit is something to invert the carry in if we are doing a subtraction.
The use_carry control signal which we introduced above to select between the carry flag and the subtract signal now needs to select between the carry flag or an explicit zero, and whichever value is selected will then be inverted by the subtract signal to become the actual carry in.
INCrement (Add One)
The next operation I want to look at is the increment operation. This simply adds one to the A register.
We could implement this by setting the B register to one and performing an addition but how do we get a one into the B register?
Instead we can ‘hack’ this one. Clearing a register is easy so what if we clear the B register to zero and then use the carry in as the + 1? We’re basically doing an ADC but with the carry in set explicitly to one rather than coming from the carry flag.
Well, that was easy. All we need is to add a control signal to clear the B register and another control signal to send an explicit 1 to the carry in. We can do this with an additional control signal, which I’ll call ‘carry_set’. Our use_carry control signal will now be selecting between the carry flag and the carry_set control signal.
We just need to make sure our control logic sends the correct values for these three signals:
Operations use_carry carry_set ADD/SUB 0 0 ADC/SBC 1 (irrelevant) INC 1 1
DECrement (Subtract One)
And, finally, we get to our DEC operation. Can we do this the same way as our INC operation?
In mathematical terms we’re doing A – 0 – 1. Converted to an addition this becomes A + ~0 + 1 – 1. Simplifying that we get A + ~0 + 0. So we just need to set our carry in to zero. But remember that our carry in gets inverted if we’re doing a subtraction so we actually need to send a one as the carry so it will be inverted to the needed zero.
And, what are we doing for our INC operation above? Why, we’re sending a 1 as carry using the carry_set control signal.
So, in answer to the question, yes, we can do the DEC operation in exactly the same way we do the INC operation.
List of Needed Changes
So we now need:
- A use_carry control signal.
- A carry_set control signal.
- Circuitry to select the carry in based on the above two control signals.
- A way to invert the carry in if we’re doing a subtraction.
- A clear_b control signal to clear the B register if we’re doing an INC or DEC operation.
- To pass in the correct control signals:
Operation use_carry carry_set clear_b4
ADD/SUB 0 0 False
ADC/SBC 1 (irrelevant) False
INC/DEC 1 1 True
Carry Selection Circuitry
We can now start designing some silicon. The most complicated part of that is the circuitry to select which carry signal to use as input so let’s begin with that. We have two possible inputs, the carry flag or the carry_set input signal and we’re using the use_carry signal to select one or the other.
Let’s look at the truth table for an AND gate but we’ll call one of the inputs select and the other data.
select data out 0 0 0 0 1 0 1 0 0 1 1 1
Notice that if the select input is zero then we always get a zero out but if the select signal is one then the output is the same as the data input.
Using this fact gives us the circuit below. The inverter on the use_carry signal means that one or other of the AND gates will have a 1 as input as the select signal. Whichever AND gate has the 1 as the select signal will be outputting the data signal, and the other AND gate will be outputting zero. We then combine the outputs from the AND gates with an OR gate.
However, this circuit would mean using three ICs and I’d like to keep the chip count down if possible. Since any circuit can be built with NAND gates lets using them instead to get the circuit below.
Here I’ve used a NAND gate in place of the inverter and also swapped the AND gates to NAND gates. Now the selected NAND gate will be outputting it’s signal inverted while the unselected gate outputs a 1. If both the NAND gates are outputting a 1 then the final output needs to be a zero. If either is outputting zero (meaning the selected input is one) then the output needs to be zero and this is exactly the function performed by a NAND gate.
Rather conveniently this circuit uses four NAND gates which means that all I needs is a single 74LS00 IC.
Inverting the Carry on Subtraction
The next step is to invert the output from the above circuitry if the subtract control signal is high. This simply needs a XOR gate. Pulling this all together gives us the complete circuitry for the carry in:
The photo above shows the adder circuitry on the Bentium Pro. The topmost breadboard is the flags in input processing, the middle board is the adder ICs, the bottom row is the registers. The highlighted area shows (from left to right): red LED showing carry flag state (illuminated); Orange LED for use_carry (not illuminated); Orange LED for carry_set (illuminated); 74LS00 quad NAND gate IC; 74LS86 quad XOR gate IC. The brown wire from here runs down to the carry input of the 74LS283 adder IC and the associated orange indicator LED (not illuminated). The other brown wire here is the carry output from the first adder IC.
Clearing the B Register and Finishing Off
The only other change we need is the ability to clear the B register on command. We’re using 74LS173 ICs for our registers which have an active high clear input (pin 13) and this input is independent of the clock signal, so all we need is an extra signal from the control logic wired directly to pin 13.
And after running through a tonne of explanation and detail it’s rather pleasing to see that we can get all this extra functionality from just five logic gates, two ICs and three control signals. It’s always nice when the universe is being kind.
UPDATE: I’ve corrected the three circuit diagrams above. In my originals the labels for the carry_flag and use_carry_flag inputs where switched. My apologies.
- Some processors, such as the 6502, have only ADC and SBC operations. ADD and SUB operations require the programmer to explicitly clear the carry flag beforehand.
- Do we need INC and DEC operations with carry input for larger counters? No, we simply finish the calculation if there is no carry out. I.e. INC A;JMP NC, done;INC B;done: …
- The ALU in my Bentium Pro computer uses two special registers, W and Z, which are equivalent to Ben’s A and B respectively.
- I've used True/False for the clear_b signal since this depends on how the registers work. For our circuit (and Ben's) False = 0 and True = 1 (see below) but YMMV.