Ein verbundener Graph ist ein Graph, der einen Pfad zwischen zwei beliebigen Eckpunkten enthält.

Herausforderung

Bauen Sie eine [2-Input NAND-Gate] -Schaltung auf, die bestimmt, ob ein 4-Vertex-Graph angeschlossen ist.
(Die 2 Eingänge eines Gatters können dasselbe Eingangsbit oder ein anderes Gatter sein.)
Ausgang Wahr, wenn der Graph verbunden ist, und Falsch, wenn nicht.

Eingang

Die sechs möglichen Kanten eines einfachen Graphen mit 4 Eckpunkten:

[ ₀ e ₁ , ₀ e ₂ , ₁ e ₂ , ₀ e ₃ , ₁ e ₃ , ₂ e ₃ ]

wobei _a e _b darstellt, ob es eine Kante zwischen den Eckpunkten a und b gibt

Verbundenheit entspricht den folgenden Bedingungen:

• Wenn weniger als 3 Eingaben wahr sind, wird falsch ausgegeben.

• Wenn mehr als 3 Eingaben wahr sind, wird wahr ausgegeben.

• Wenn genau 3 Eingaben True sind und ein Dreieck bilden, wird False ausgegeben.

• Andernfalls geben Sie True aus.

Die Antwort mit den wenigsten Toren gewinnt. Die Verbindungen werden durch
die niedrigste Schaltkreistiefe (Länge der längsten Pfade vom Eingang zum Ausgang) getrennt.

30 NANDS

Anstatt zu fragen, wann wir eine 1 bekommen, habe ich die Frage gestellt, wann wir eine 0 bekommen. Es ist besser, es so zu stellen, weil es weniger Nullen als Einsen gibt.

Hier ist die Verteilung nach der Anzahl der Kanten (6. Reihe des Pascal-Dreiecks)

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)

Wenn wir die Frage auf diese Weise stellen, erhalten wir das folgende Diagramm und den folgenden Ausdruck

 ___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) 

Wir gehen davon aus, dass die Ausgabe standardmäßig 1 ist, sich jedoch unter den folgenden Bedingungen auf 0 ändert

1.A 0 für drei benachbarte Kanten (Test 3 Eingänge)

2.A 0 für zwei gegenüberliegende Kantenpaare (4 Eingänge testen)

Die obigen Begriffe sind bereits so angeordnet, dass sie wie folgt gruppiert werden können. (Diese Version des Ausdrucks ist übrigens rotationssymmetrisch um den AFB-Eckpunkt.)

((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

Die Punktzahl für jedes &oder |wird unter das Symbol gesetzt und wie folgt begründet:

Stufe 0: Wir investieren in einen Wechselrichter für jeden Eingang: 6 NANDS

Stufe 1: Wir können ein ODER aus einem NAND-Gatter bauen, indem wir einen Inverter an den Eingang legen (insgesamt 3 NANDS). Da wir jedoch bereits im vorherigen Schritt in 6 NANDS investiert haben, können wir aus 7 NAND-Gattern 7 ODER-Gatter erstellen. Wir brauchen auch 3 UND-Tore. Für diese verwenden wir nur NANDs und lassen den Ausgang invertiert. 10 NANDS

Level 2: Wieder bauen wir 4 ODER-Gatter aus NAND-Gattern. In jedem Fall haben wir 1 Eingang von einem ODER-Gatter, also müssen wir das invertieren. Der andere Eingang ist jedoch bereits invertiert (von einem der NANDs im vorherigen Schritt, der &in drei Fällen einem Symbol entspricht , und von einem Inverter im letzten), sodass wir nur 2 Gatter für jede OR-Funktionalität benötigen. 4 * 2 = 8

Level 3: Wir müssen jetzt die vier Ausgänge UND-verknüpfen. Dies erfordert 3 UND-Gatter, die jeweils aus 2 NANDs aufgebaut sind, 3 · 2 = 6

Das sind insgesamt 30 NAND-Gatter mit einer maximalen Tiefe von 2 + 2 + 4 = 8 NANDs für Zweige mit einer |Stufe 1 oder 3 + 1 + 4 = 8 NANDs für Zweige mit einer &Stufe 1.

Das folgende Ruby-Skript bestätigt visuell, dass der obige Ausdruck gültig ist.

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}__\\|


"
}

19 NANDs

Es gibt keine einfachere Schaltung als diese.

Unter dem Bild befindet sich ein Code zum Testen. Was das Verständnis angeht, ist das schwierig. Dort gibt es ein paar IF-Gatter, und die Eingänge sind zu einem Dreieck gruppiert, wobei die freien Ecklinien zur Analyse einzeln hinzugefügt werden, jedoch nicht auf einfache Weise. Wenn es jemand schafft, es zu verstehen, werde ich beeindruckt sein.

Verilog-Code mit Test:

// 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:                                                                             
// /codegolf/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

Mathematica, 17 Tore

Wir listen einfach alle Regeln auf, konstruieren die Boolesche Funktion und minimieren sie in der NANDForm.

#->If[Total@#<3||
       MemberQ[{{1,1,1,0,0,0},{1,0,0,1,1,0},{0,1,0,1,0,1},{0,0,1,0,1,1}},#]
       ,0,1] /.{1->True,0->False}& /@
     Tuples[{0,1},6];
BooleanMinimize[BooleanFunction[rule], "NAND"]

Ergebnis :

(#1⊼#2⊼#4)⊼(#1⊼#2⊼#5)⊼(#1⊼#2⊼#6)⊼(#1⊼#3⊼#4)⊼ \
(#1⊼#3⊼#5)⊼(#1⊼#3⊼#6)⊼(#1⊼#4⊼#6)⊼(#1⊼#5⊼#6)⊼ \
(#2⊼#3⊼#4)⊼(#2⊼#3⊼#5)⊼(#2⊼#3⊼#6)⊼(#2⊼#4⊼#5)⊼ \
(#2⊼#5⊼#6)⊼(#3⊼#4⊼#5)⊼(#3⊼#4⊼#6)⊼(#4⊼#5⊼#6)&

, wo #1...#6sind 6 Plätze für Argumente.

Testfälle :

f=%; (* assign the function to symbol f *)

f[True, True, True, True, False, False]
(* True *)

f[True, True, False, True, False, False]
(* True *) (*, three Trues do not form a triangle *)

f[True, True, True, False, False, False]
(* False *) (*, three Trues form a triangle *)

64 NANDs

Die sechs Kanten können in drei Paare gegenüberliegender Kanten aufgeteilt werden. Damit ein Graph verbunden werden kann, müssen entweder zwei gegenüberliegende Kanten sowie eine dritte Kante vorhanden sein oder drei Kanten, die mit demselben Scheitelpunkt verbunden sind.

       •
       U

   Z   •   Y  
    V     W 
 •     X     •

Die entgegengesetzten Paare sind UX, VY, WZ, also:

A = U+V   ;3 gates
B = W+X
C = Y+Z

D = UV(B+C)  ;2+2+3=7 gates
E = WX(A+C)
F = YZ(C+A)

Result = D+E+F+UVW+UYZ+XVZ+XWY ; 18 + 16 = 34 gates

Wenn Sie UND- und ODER-Tore auf die übliche Weise erstellen, beträgt die Gesamtanzahl der verwendeten Tore 3*3+7*3+34= 64.