Build a 4-vertex Connectedness Tester using NAND gates
19 NANDs
There is no simpler circuit than this.
There is code for testing it below the picture. As for understanding it, that's difficult. There are a couple of IF gates there, and the inputs are kinda grouped into a triangle with the free corner lines added for analysis one by one, but not in a simple way. If anyone manages to understand it, I will be impressed.
Verilog code with testing:
// 4-vertex Connectedness Tester
// Minimal at 19 NANDs
//
// By Kim Øyhus 2018 (c) into (CC BY-SA 3.0)
// This work is licensed under the Creative Commons Attribution 3.0
// Unported License. To view a copy of this license, visit
// https://creativecommons.org/licenses/by-sa/3.0/
//
// This is my entry to win this Programming Puzzle & Code Golf
// at Stack Exchange:
// https://codegolf.stackexchange.com/questions/69912/build-a-4-vertex-connectedness-tester-using-nand-gates/
//
// I am sure there are no simpler solutions to this problem.
// It has a logical depth of 11, which is deeper than
// circuits using a few more NANDs.
module counting6 ( in_000, in_001, in_002, in_003, in_004, in_005, in_006, out000 );
input in_000, in_001, in_002, in_003, in_004, in_005, in_006;
output out000;
wire wir000, wir001, wir002, wir003, wir004, wir005, wir006, wir007, wir008, wir009, wir010, wir011, wir012, wir013, wir014, wir015, wir016, wir017;
nand gate000 ( wir000, in_000, in_000 );
nand gate001 ( wir001, in_001, in_003 );
nand gate002 ( wir002, wir001, wir000 );
nand gate003 ( wir003, in_002, wir002 );
nand gate004 ( wir004, wir002, wir002 );
nand gate005 ( wir005, wir004, in_002 );
nand gate006 ( wir006, wir005, wir004 );
nand gate007 ( wir007, in_005, wir006 );
nand gate008 ( wir008, in_003, wir006 );
nand gate009 ( wir009, in_004, wir003 );
nand gate010 ( wir010, wir003, wir009 );
nand gate011 ( wir011, wir009, wir000 );
nand gate012 ( wir012, wir011, in_001 );
nand gate013 ( wir013, wir008, wir012 );
nand gate014 ( wir014, wir013, in_005 );
nand gate015 ( wir015, wir006, wir013 );
nand gate016 ( wir016, wir015, wir007 );
nand gate017 ( wir017, wir016, wir010 );
nand gate018 ( out000, wir014, wir017 );
endmodule
module connecting6_test;
reg [5:0] X;
wire a;
counting6 U1 (
.in_000 (X[0]),
.in_001 (X[1]),
.in_002 (X[2]),
.in_003 (X[3]),
.in_004 (X[4]),
.in_005 (X[5]),
.in_006 (X[6]),
.out000 (a )
);
initial begin
X = 0;
end
always
#10 X = X+1;
initial begin
$display("\t\t \t_");
$display("\t\ttime,\t \\db/_,\tconnected");
$monitor("%d,\t%b,\t%d",$time, X, a );
end
initial
#630 $finish;
endmodule
// iverilog -o hello hello.v
// vvp hello
Kim Øyhus
30 NANDS
Instead of asking when do we get a 1, I asked the question when do we get a 0. It's better to ask it this way round because there are less 0's than 1's.
Here's the distribution according to number of edges (6th row of pascal's triangle)
Edges 0 1 2 3 4 5 6
Frequency 1 6 15 20 15 6 1 (total 64)
Output 0 0 0 * 1 1 1
* = 0 if triangle (4 possibilities) 1 if claw (4 possibilities)
1 if two opposite edges and one other (12 possibilities)
Asking the question this way round, we get the following diagram and expression
___D___
|\ /|
| E F |
| \ / |
A X C
| / \ |
| / \ |
|/__B__\|
(A|C|D|B)&(A|D|E)&(D|B|E|F)&(C|B|E)&(A|C|E|F)&(D|F|C)&(A|F|B)
We assume the output will default to 1, but will change to 0 under any of the following conditions
1.A 0 for three adjacent edges (test 3 inputs)
2.A 0 for two opposing pairs of edges (test 4 inputs)
The terms above are already ordered in the manner that will enable them to be grouped as below. (Incidentally, this version of the expression is rotationally symmetrical abouth the AFB vertex.)
((A|D)|((C|B)&E))&((B|E)|((D|F)&C))&((C|F)|((A|E)&D))&(A|F|B) =6 inverters
1 1 1 1 1 1 1 1 1 1 =10 (7 OR with both inputs inverted, 3 NAND)
2 2 2 2 =8 (4 OR with one input inverted)
2 2 2 =6 (3 AND)
Total =30
The score for each & or | is placed below the symbol and justified as follows:
Level 0: We invest in an inverter for each input: 6 NANDS
Level 1: We can build an OR from a NAND gate by putting an inverter at the input (total 3 NANDS) but as we already invested in 6 NANDS in the previous step we can make 7 OR gates from 7 NAND gates. We also need 3 AND gates. For these, we will just use NANDs and leave the output inverted. 10 NANDS
Level 2: Again we build 4 OR gates from NAND gates. In each case we have 1 input from an OR gate, so we have to invert that. But the other input is already inverted (coming from one of the NANDs in the previous step that corresponds to a & symbol in three cases, and from an inverter in the last one) so we only need 2 gates for each OR functionality. 4 * 2 =8
Level 3: We now need to AND the four outputs together. This requires 3 AND gates, each built from 2 NANDs, 3 * 2 = 6
That's a total of 30 NAND gates, with a max depth of 2+2+4=8 NANDs for branches with an | at level 1 or 3+1+4=8 NANDs for branches with an & at level 1.
The following Ruby script confirms visually that the above expression is valid.
64.times{|i|
a=i%2
b=i/2%2
c=i/4%2
d=i/8%2
e=i/16%2
f=i/32%2
puts i, ((a|d)|((c|b)&e))&((b|e)|((d|f)&c))&((c|f)|((a|e)&d))&(a|f|b)
puts " ___#{d}___
|\\ /|
| #{e} #{f} |
| \\ / |
#{a} X #{c}
| / \\ |
| / \\ |
|/__#{b}__\\|
"
}