Clone this repo:

Branches

  1. 346b6af update repo by Jeff DiCorpo · 3 weeks ago main
  2. a742231 update repo by Jeff DiCorpo · 4 weeks ago
  3. 21e1dca update repo by Jeff DiCorpo · 5 weeks ago
  4. 33ffc1a Add hardened chip by Tamas Hubai · 8 weeks ago
  5. e844cf1 Add documentation by Tamas Hubai · 8 weeks ago

Universal gates

It is quite well known that any logic circuit can be built using only NAND gates. For instance, an XNOR gate is equivalent to the following construction:

XNOR gate composed from 5 NAND gates

Such gates are called universal. Any Boolean function with 2 inputs and 1 output can be built from at most 5 NAND gates.

We can also define a gate U21 that is universal in a stricter sense, such that any Boolean function with 2 inputs and 1 output is realized with just a single copy of U21. This gate would obviously need more than 2 inputs, but it's usually still more economical than the 2k inputs and k outputs used from a set of NAND chips (1≤k≤5).

U21(a,b,c,d)=(a&~b)^c^d

As an example, this is how we get the NAND of p and q and the XNOR of p and q by wiring up U21's four inputs a, b, c and d to a suitable combination of p, q, 0 and 1:

a=p, b=q, c=p, d=1       a=1, b=q, c=p, d=q

⮟   ⮟   ⮟   ⮟   ⮟   ⮟   ⮟   ⮟   ⮟   ⮟   ⮟

NAND gate       XNOR gate

So U21 stands in for any combinatorial logic with 2 inputs and 1 output. And any Boolean function with 3 inputs and 1 output can be built with at most 3 copies of U21. But that doesn‘t stop us from creating a gate U31 that’s even more universal and does so with a single copy when wired correctly:

U31(a,b,c,d,e,f)=(((a^~b)&c)|(d^e))^((d|~a)&b)^f

This repository contains a chip design with four independent gates U21, U31, U41 and U22 where each Uij can be wired to act as an arbitrary function with i inputs and j outputs. It uses the caravel framework and is hardened for the gf180mcuC technology platform.