59 56 53 52 51 50 gates
I thought I'd create an actual ALU here, even though it ended up taking more gates than @ovs' answer. Edit: A true ALU would actually use identical lanes for all four bits of the form Result = Input + ((Input & Mask) ^ Flip) + Carry
. This would provide for eight different operations:
Mask Flip Carry Result
0 0 0 Input
0 0 1 Input + 1
0 1 0 Input - 1
0 1 1 Input
1 0 0 Input * 2
1 0 1 Input * 2 + 1 (c.f. Z80 SLL "instruction")
1 1 0 -1
1 1 1 0
Each lane (except the last, as the carry out is not required) would use 15 gates, and then 5 gates are needed to generate the desired carry in for the four operations, making a total of 64 gates. However my first approach actually special-cased the first lane, so that I could choose between the input and 1
as the RHS of the full adder:
00: IIII -> IIII + 0001
01: IIII -> IIII - 0001
10: IIII -> IIII + IIII
11: IIII -> IIII - IIII
To get the RHS takes 8 gates:
R2 = NAND(NOT(I2), I0)
R3 = NOT(NAND(I3, I0))
R4 = NOT(NAND(I4, I0))
R5 = NOT(NAND(I5, I0))
To select between +
and -
, I perform 2's complement on the value. 1's complement takes 16 gates:
S2 = XOR(R2, I1)
S3 = XOR(R3, I1)
S4 = XOR(R4, I1)
S5 = XOR(R5, I1)
To achieve 2's complement we simply add I1
as part of the IIII + SSSS
operation:
C0, O0 = ADD(I2, S2, I1)
C1, O1 = ADD(I3, S3, C0)
C2, O2 = ADD(I4, S4, C1)
C3, O3 = ADD(I5, S5, C2)
This takes 36 gates for a grand total of 60 gates, except we don't need C3
which saves a gate.
Notes:
NOT
takes 1 gate:
NOT(X) = NAND(X, X)
XOR
takes 4 gates:
XOR(X, Y) = _XOR2(X, Y, NAND(X, Y))
_XOR2(X, Y, W) = NAND(NAND(X, W), NAND(Y, W))
ADD
takes 9 gates:
ADD(X, Y, Z) = _ADD2(X, Y, Z, NAND(Y, Z))
_ADD2(X, Y, Z, W) = _ADD3(X, W, _XOR2(Y, Z, W))
_ADD3(X, W, V) = _ADD4(X, W, V, NAND(X, V))
_ADD4(X, W, V, U) = NAND(W, U), _XOR2(X, V, U)
Edit: The LSB's adder's inputs have a lot of redundancy:
S2 = XOR(R2, I1)
C0, O0 = ADD(I2, S2, I1)
But this means that XOR(S2, I1)
is just R2
, so we can write this as:
C0 = NAND(NAND(S2, I1), NAND(I2, XOR(S2, I1)))
= NAND(NAND(S2, I1), NAND(I2, R2))
O0 = XOR(I2, XOR(S2, I1))
= XOR(I2, R2)
= _XOR2(I2, R2, NAND(I2, R2))
This saves three gates.
Edit: Even more redundancy that I overlooked:
C0 = NAND(NAND(S2, I1), NAND(I2, XOR(S2, I1)))
= NAND(NAND(S2, I1), NAND(I2, R2))
= NAND(NAND(XOR(R2, I1), I1), NAND(I2, R2))
= NAND(NAND(NOT(R2), I1), NAND(I2, R2))
Although this costs a gate, it makes S2
unnecessary which saves four gates for an overall saving of three gates.
Edit: Found another redundant gate:
C0 = NAND(NAND(S2, I1), NAND(I2, XOR(S2, I1)))
= NAND(NAND(S2, I1), NAND(I2, R2))
= NAND(NAND(XOR(R2, I1), I1), NAND(I2, R2))
= NAND(NAND(NOT(R2), I1), NAND(I2, R2))
= NAND(NAND(NOT(R2), I1), NAND(I2, NAND(NOT(I2), I0)))
= NAND(NAND(NOT(R2), I1), NOT(I2))
Although this seems to just change a shared NAND
to a shared NOT
, I computed NOT(I2)
as part of the calculation for R2
, so that gate can be shared too, thus saving another gate.
Edit: This applies to O2
as well, then further allowing for a further saving of one gate:
O0 = XOR(I2, XOR(S2, I1))
= XOR(I2, R2)
= _XOR2(I2, R2, NAND(I2, R2))
= _XOR2(I2, R2, NAND(I2, NAND(NOT(I2), I0)))
= _XOR2(I2, R2, NOT(I2))
= NAND(NAND(I2, NOT(I2)), NAND(R2, NOT(I2)))
= NOT(NAND(R2, NOT(I2)))
Edit: One final gate can be saved by eliminating R2
.
C0 = NAND(NAND(NOT(R2), I1), NOT(I2))
= NAND(NAND(NOT(NAND(NOT(I2), I0)), I1), NOT(I2))
= NAND(NAND(AND(NOT(I2), I0), I1), NOT(I2))
= OR(AND(AND(NOT(I2), I0), I1), I2)
= OR(AND(I0, I1), I2)
= NAND(NAND(I0, I1), NOT(I2))
O0 = NOT(NAND(R2, NOT(I2)))
= NOT(NAND(NAND(NOT(I2), I0), NOT(I2)))
= NOT(NAND(OR(I2, NOT(I0)), NOT(I2)))
= NOT(NAND(NOT(I0), NOT(I2)))
10
0011
(should the result be0001
?) \$\endgroup\$