Erstellen Sie einen universellen 2-Wege-Logikprozessor mit NAND-Logikgattern

8

Ein 2-Wege - Universallogikprozessor (2ULP) ist ein Netzwerk von Logikgattern , die zwei Eingänge nehmen Drähte Aund B, sowie vier weitere Eingänge L_, L_a, L_b, und L_ab, und erzeugen einen einzelnen Ausgang L(a, b)der vier unter Verwendung LEingänge als Wahrheitstabellenfunktion:

  • Das 2ULP gibt zurück, L_wenn Aund Bbeide sind 0.
  • Es wird zurückgegeben, L_awenn A = 1und B = 0.
  • Es wird zurückgegeben, L_bwenn A = 0und B = 1.
  • Es wird zurückgegeben, L_abwenn Aund Bbeides sind 1.

Beispielsweise sind die Eingänge gegeben L_ = 0, L_a = 1, L_b = 1, und L_ab = 0, dann ist der Ausgang L(a, b)wird gleich sein A xor B.

Ihre Aufgabe ist es, ein 2ULP nur mit NAND-Gattern zu erstellen, wobei möglichst wenige NAND-Gatter verwendet werden. Zur Vereinfachung können Sie in Ihrem Diagramm UND-, ODER-, NICHT- und XOR-Gatter mit den folgenden entsprechenden Bewertungen verwenden:

  • NOT: 1
  • AND: 2
  • OR: 3
  • XOR: 4

Jede dieser Bewertungen entspricht der Anzahl der NAND-Gatter, die zum Aufbau des entsprechenden Gatters erforderlich sind.

Die Logikschaltung, die die wenigsten NAND-Gatter verwendet, um eine korrekte Konstruktion zu erzeugen, gewinnt.

atomic-code-golf logic-gates Joe Z.
quelle
1
Meine Fähigkeiten im Bereich der digitalen Logik sind so verrostet, dass es lächerlich ist, aber ich genieße die Endergebnisse dieser Wettbewerbe sehr. +1
ProgrammerDan
Bei NAND-Gates mit zwei Eingängen gibt es in diesem Design nicht viel Raum für Kreativität. Anstatt dass das Gerät sechs Eingänge benötigt, muss ein Block mit einer beliebigen Anzahl von Eingängen und einem Ausgang entworfen werden, und es muss möglich sein, dass bei zwei Eingängen A und B und einer Auswahl einer der sechzehn Funktionen dies möglich ist Verbinden Sie die Eingänge des Blocks mit einer Kombination aus A, B, High und Low, sodass der Ausgang diese Funktion liefert. Ein solches Gerät wäre ein universeller 2-Wege-Logikprozessor (fügen Sie einfach Drähte hinzu), könnte aber wahrscheinlich in viel weniger als 11 Gattern ausgeführt werden.
Supercat
1
Wir sollten Gate-Golf erfinden , bei dem Sie in der kleinsten Anzahl von Gates schreiben.
TheDoctor
Dafür ist Atomic-Code-Golf + Logic-Gates gedacht.
Joe Z.

Antworten:

10

11 NANDs

Definieren Sie das Gate MUX (Kosten 4) als

MUX(P, Q, R) = (P NAND Q) NAND (NOT P NAND R)

mit Wahrheitstabelle

P Q R    (P NAND Q)   (NOT P NAND R)    MUX
0 0 0        1               1           0
0 0 1        1               0           1
0 1 0        1               1           0
0 1 1        1               0           1
1 0 0        1               1           0
1 0 1        1               1           0
1 1 0        0               1           1
1 1 1        0               1           1

Dann ist dies der bekannte ternäre Operator MUX(P, Q, R) = P ? Q : R

Wir haben einfach

2ULP = MUX(A, MUX(B, L_ab, L_a), MUX(B, L_b, L_))

für einen Preis von 12, aber es gibt eine triviale Ein-Tor-Einsparung durch Wiederverwendung der NOT Bvon den beiden inneren MUXes.

Peter Taylor
quelle
3
Sie haben mir gerade eine Idee gegeben, was ich mit Redstone in Minecraft versuchen kann, danke
David Wilkins
1
Das absolute Minimum beträgt 11 NANDs. Ich habe gründlich gesucht. Und die schnellste Strecke, die ich gefunden habe, hat eine Tiefe von 5 Toren. Dieses Rätsel wird also von Peter Taylor gelöst.
KimOyhus
3

Kosten: 4 * 4 * 14 + 4 * (13) + 13 * 3 + 3 * 3 + 24 * 1 + 4 = 352

Ich bin kein boolescher Mann, dies ist mein Bestes, um diese Dinge zu codieren (ich weiß, das gibt mir nicht viele unvorstellbare Internetpunkte ..).

# l1 is for a=F , b=F
# l2 is for a=F , b=T
# l3 is for a=T , b=F
# l4 is for a=T , b=T

2ULP(l1,l2,l3,l4,a,b) =
 (l1&l2&l3&l4)|             # always true
 (!l1&l2&l3&l4)&(a|b)|      # a=F,b=F->F; ee in T
 (l1&!l2&l3&l4)&(!a&b)|     # a=F,b=T->F; ee in T
 (!l1&!l2&l3&l4)&(a)|       # a=F,b=F->F; a=F,b=T->F; a=T,b=F->T; a=T,b=T->T; 
 (l1&l2&!l3&l4)&(a&!b)|     # a=T,b=F->F, ee in T
 (!l1&l2&!l3&l4)&(b)|       # a=T,b=F->F, ee in T
 (!l1&!l2&!l3&l4)&(a&b)|    # a=T,b=T->T, ee in F
 (l1&l2&l3&!l4)&(!(a|b))|   # a=T,b=T->F, ee in T
 (!l1&l2&l3&!l4)&(!(avb))|  # a=T,b=F->T, a=F,b=T->T, ee in T , note v is the exor.
 (l1&!l2&l3&!l4)&(!b)|      # T when b=T
 (!l1&!l2&l3&!l4)&(a&!b)|   # T when a=T,b=F
 (l1&l2&!l3&!l4)&(!a)|      # T when a=F
 (!l1&l2&!l3&!l4)&(!a&b)|   # T when a=F,B=T
 (l1&!l2&!l3&!l4)&(!(a|b))  # T when a=F,B=F
Antonio Ragagnin
quelle
Wenn Sie dem System folgen, das durch die Aufzählungspunkte in der Frage beschrieben wird, erhalten Sie Kosten von 29, was beeindruckend beeindruckend ist.
Peter Taylor
Es tut mir leid, Mr. Taylor. Ich hoffe nur, dass dies Ihre Augen nicht ruiniert hat.
Antonio Ragagnin
3

Mit der Wolfram-Sprache kann ich eine 13-Tore- Formel erhalten:

logicfunc = Function[{a, b, Ln, La, Lb, Lab},
                   {a, b, Ln, La, Lb, Lab} -> Switch[{a, b},
                          {0, 0}, Ln, {1, 0}, La, {0, 1}, Lb, {1, 1}, Lab]
                  ];
trueRuleTable = Flatten[Outer[logicfunc, ##]] & @@ ConstantArray[{0, 1}, 6] /. {0 -> False, 1 -> True};
BooleanFunction[trueRuleTable, {a, b, Ln, La, Lb, Lab}] // BooleanMinimize[#, "NAND"] &

welche Ausgänge:

NAND-Formel

Hier Ln, La, Lbund Labsind die L_, L_a, L_bund L_abseparat in OP.

Nebenbemerkung: Die Ergebnisse der BooleanMinimizeFunktion in Wolfram-Sprache sind auf zwei Ebenen beschränkt NANDund NOTbeim Aufrufen als BooleanMinimize[(*blabla*), "NAND"], daher ist sie nicht so gut wie die vierstufige Formel von Peter Taylor oben .

Silvia
quelle