Monday, August 11, 2025

Make an ALU using NAND gates

How do you make an ALU using nand gates?

Fun project! The clean way to “make an ALU from NAND gates” is to (1) build the basic gates from NANDs, (2) build slightly bigger blocks (XOR, full adder, multiplexers) from those, then (3) wire a 1‑bit ALU “slice” and replicate it N times.

Here’s a compact blueprint you can follow.

1) Everything from NAND

NAND is functionally complete, so first express the usual gates:

  • NOT: ¬A = NAND(A, A)
  • AND: A ∧ B = ¬NAND(A, B) = NAND(NAND(A, B), NAND(A, B))
  • OR (via De Morgan): A ∨ B = NAND(¬A, ¬B) = NAND(NAND(A, A), NAND(B, B))
  • XOR (minimal 4‑NAND version): t1 = NAND(A, B) t2 = NAND(A, t1) t3 = NAND(B, t1) A ⊕ B = NAND(t2, t3)
  • 2:1 MUX, y = s̄·d0 + s·d1, in NANDs: s̄ = NAND(s, s) u = NAND(d0, s̄) v = NAND(d1, s) y = NAND(u, v)

These five are the only “primitives” you’ll need.

2) Full adder from NANDs

One common approach is “XOR‑XOR‑AND/OR”:

  • p = A ⊕ B (4 NANDs as above)
  • sum = p ⊕ Cin (another 4 NANDs)
  • c1 = A ∧ B (2 NANDs for AND)
  • c2 = A ∧ Cin (2 NANDs)
  • c3 = B ∧ Cin (2 NANDs)
  • Cout = c1 ∨ c2 ∨ c3 (OR = NAND(NOT,NOT); chain two ORs with NANDs)

Gate count isn’t critical unless you’re optimizing, but this maps cleanly and is easy to debug. (There’s also a well‑known 9‑NAND full‑adder topology if you’re chasing minimum count.)

3) One 1‑bit ALU slice

Give the slice two operands (Ai, Bi), a carry‑in (Ci), and control bits op[2:0]. Compute the candidate results in parallel, then use a MUX to pick one:

Common ops (examples; choose what you need):

  • AND: Ai ∧ Bi
  • OR: Ai ∨ Bi
  • XOR: Ai ⊕ Bi
  • ADD: Si = Ai ⊕ Bi ⊕ Ci, Cout from the full adder
  • SUB: do two’s complement: add Ai + (¬Bi) + 1 Implementation trick: feed Bi′ = (bInvert ? ¬Bi : Bi) into the adder and set Ci = bInvert for the LSB. This is exactly how the MIPS/LC‑3 textbook ALUs do it.
  • PASSA / PASSB: route through a MUX
  • SLT (set‑less‑than): in the MSB slice, take the sign of A − B and route it into bit0 via a dedicated path (others output 0). You only need this if you want comparisons.

Inside the slice:

  1. Make Bi′ = MUX(bInvert, Bi, ¬Bi) using the NAND MUX above.

  2. Build the full adder with (Ai, Bi′, Ci) → (Sum, Co).

  3. Compute logic results (AND/OR/XOR) with the NAND recipes.

  4. Select the output with a 4:1 or 8:1 MUX in NANDs, controlled by op[2:0].

    • For example, use two cascaded 2:1 NAND‑MUXes to build a 4:1.

Example encoding (use any you like):

  • 000 → AND
  • 001 → OR
  • 010 → XOR
  • 011 → ADD
  • 100 → SUB (i.e., same data path as ADD, but assert bInvert=1; for LSB, Ci=1)
  • 101 → PASS A
  • 110 → PASS B
  • 111 → SLT (only meaningful in bit0; others drive 0)

Outputs per slice: result bit (Ri) and carry‑out (Ci+1). Chain Ci+1 → next slice’s Ci to form an N‑bit ripple‑carry ALU.

4) Scale to N bits

Replicate the slice N times (4, 8, 16, 32…):

  • Tie all op[2:0] and bInvert lines in parallel across slices.

  • For ADD/SUB:

    • LSB: Ci = bInvert (0 for ADD, 1 for SUB)
    • Middle bits: Ci from previous slice
    • MSB: exposes Cout and (optionally) the signed overflow flag: V = Cout ⊕ Cn−1
  • For SLT: compute A − B in the background (SUB mode), capture the MSB’s sign (or overflow‑corrected less‑than), and route it to bit0 through the 111 MUX selection. Others drive 0 for 111.

5) Practical notes

  • Fan‑in: stick to 2‑input NANDs. If you need wider ORs, tree them (pairwise with NAND‑based OR).
  • Timing: this is a ripple‑carry design; it’s simple but slowish. If you care about speed, add carry‑lookahead later (still doable in NAND‑only logic, just more gates).
  • Reset/flags: you can add Zero flag by NOR‑reducing all result bits (NOR = NOT(OR) using NANDs), Sign from MSB, Carry from last Cout, Overflow as above.

6) Minimal NAND‑only Verilog (illustrative)

If you want to simulate before wiring:

// 1-bit slice, NAND-only style (illustrative subset: AND/OR/XOR/ADD)
module alu1 (
  input  a, b, cin,
  input  op0, op1, op2, // select lines
  input  bInvert,       // 0:add/use b, 1:sub/use ~b
  output result,
  output cout
);
  wire nb, bsel, t1,t2,t3, xor_ab, p1,p2,p3, c1,c2,c3, sum;

  // NOT b
  nand(nb, b, b);
  // bsel = MUX(bInvert ? ~b : b)
  wire ninv; nand(ninv, bInvert, bInvert);
  wire m0, m1;
  nand(m0, nb, ninv);     // ~b & ~bInvert
  nand(m1, b,  bInvert);  //  b &  bInvert
  nand(bsel, m0, m1);     // OR via NAND-NAND → MUX output

  // XOR a ^ bsel (4-NAND)
  nand(t1, a, bsel);
  nand(t2, a, t1);
  nand(t3, bsel, t1);
  nand(xor_ab, t2, t3);

  // SUM = xor_ab ^ cin (4-NAND more)
  wire s1,s2,s3;
  nand(s1, xor_ab, cin);
  nand(s2, xor_ab, s1);
  nand(s3, cin,    s1);
  nand(sum, s2, s3);

  // Carry = (a&bsel) | (a&cin) | (bsel&cin)
  // ANDs in NAND form
  wire ab_n, ac_n, bc_n, ab, ac, bc, c12_n, c12, c_all;
  nand(ab_n, a, bsel); nand(ab, ab_n, ab_n);
  nand(ac_n, a, cin);  nand(ac, ac_n, ac_n);
  nand(bc_n, bsel, cin); nand(bc, bc_n, bc_n);
  // OR three terms: (ab | ac) | bc
  wire abac_n;                  // OR via NAND of NOTs
  // NOT ab / NOT ac
  wire nab, nac; nand(nab, ab, ab); nand(nac, ac, ac);
  nand(abac_n, nab, nac);       // ~(~ab & ~ac) = ab|ac
  wire abac; nand(abac, abac_n, abac_n);
  // (ab|ac)|bc
  wire nabac, nbc; nand(nabac, abac, abac); nand(nbc, bc, bc);
  wire carr_or_n; nand(carr_or_n, nabac, nbc);
  wire carry; nand(carry, carr_or_n, carr_or_n);

  assign cout = carry;

  // Logic ops:
  wire and_n, or_n, a_and_b, a_or_b, a_xor_b;
  // AND
  nand(and_n, a, b); nand(a_and_b, and_n, and_n);
  // OR
  wire na, nb2; nand(na, a, a); nand(nb2, b, b);
  nand(or_n, na, nb2); nand(a_or_b, or_n, or_n);
  // XOR (reuse form with original a,b)
  wire u1,u2,u3; nand(u1, a, b); nand(u2, a, u1); nand(u3, b, u1); nand(a_xor_b, u2, u3);

  // 4:1 MUX (use two 2:1 MUX stages) to choose among AND/OR/XOR/SUM
  // Here: op1:op0 select (ignore op2 in this minimal example)
  function automatic mux2 (input d0, input d1, input s);
    // synthesizable macro in real toolchains; shown behaviorally here
    mux2 = s ? d1 : d0;
  endfunction

  wire mA = mux2(a_and_b, a_or_b, op0);
  wire mB = mux2(a_xor_b, sum,    op0);
  assign result = mux2(mA, mB, op1);
endmodule

(When you build it purely from nand primitives, replace the behavioral mux2 with the 2:1 NAND‑MUX shown earlier.)

7) How to wire a 4‑bit ALU quickly

  • Instantiate 4 slices: bit0..bit3.
  • For ADD: set bInvert=0, bit0.cin=0. For SUB: set bInvert=1, bit0.cin=1.
  • Chain carries: bit0.cout→bit1.cin→bit2.cin→bit3.cin.
  • Use the same op[2:0] for all slices.
  • Optional flags: Z = NOR of all result bits; C = bit3.cout; V = c3_out ⊕ c2_out; N = result[3].

If you want, tell me what bit‑width and exact ops you need and I’ll map the control table and draw you a gate‑level slice with the exact NAND count.

No comments:

Post a Comment