Erstellen Sie eine Multiplikationsmaschine mit NAND-Logikgattern

20

Basierend auf meiner vorherigen Frage desselben Typs, Erstellen Sie eine Additionsmaschine mit NAND-Logikgattern . Dieses Mal werden Sie aufgefordert, zu multiplizieren, anstatt zu addieren.

Baue ein Diagramm (zweiadrige) NAND - Logikgatter, die die Eingangsdrähte nehmen A1, A2, A4, B1, B2, B4, , die zwei Binärzahlen Aauf B0-7, und Rückgabewerte an den Ausgangsleitungen C1, C2, C4, C8, C16, und C32, darstellt C, welches das Produkt von Aund ist B.

Ihre Punktzahl richtet sich nach der Anzahl der von Ihnen verwendeten NAND-Gatter (1 Punkt pro Gatter). Zur Vereinfachung können Sie in Ihrem Diagramm AND-, OR-, NOT- und XOR-Gatter mit den folgenden entsprechenden Ergebnissen 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 niedrigste Punktzahl gewinnt.

Joe Z.
quelle
Ich versuche, in Logisim ein letztes Beispiel zu geben. Das Zeug ist schwer.
Joe Z.
Ich habe genug davon in meiner Schule, nein danke.
Johannes Kuhn
7
Ich habe einen universellen Optimierer für solche Aufgaben. Es findet nachweislich das kürzeste Programm zur Berechnung einer booleschen Funktion mit k Ausgängen. Wenn ich es eine Woche geben würde, könnte es mir sagen, ob der gefundene 13-Gate-2x2-Multiplikator optimal ist. 3x3? Ich werde tot sein, bevor es endet.
Stand
1
Dieser Multiplikator mit 13 Gates 2x2 ist optimal (und in Jan's Antwort enthalten). Damit und mit ein paar weiteren Stücken, die ich optimieren kann, vermute ich sehr stark, dass 60 für dieses Problem optimal sind. Ich hoffe wirklich, jemand beweist, dass ich falsch liege.
Stand
@boothby Nicht wirklich. Die naive Anwendung von Addiererbäumen führt zu einer Lösung mit 18 Gattern (4 UNDs, 2 Halbaddierer), was mich zu einer Idee führt: Ich sollte in der Lage sein, das 13-Gate zu stehlen 2x2 Multiplikator.
John Dvorak

Antworten:

24

60 55 50 48 Tore

48-Gate-Multiplikator


Das Original (60 Tore) war der systematische Ansatz - multiplizieren Sie jede Ziffer mit jeder und addieren Sie sie dann. Siehe Wallace-Bäume und Dadda-Bäume

60-Gate-Multiplikator

Die obere Hälfte ist das Multiplikationsnetzwerk - multiplizieren Sie jede Ziffer mit jeder und gruppieren Sie die ausgegebenen Ziffern mit demselben Gewicht. Einige Bits wurden invertiert gelassen, um Tore zu retten.

Die zweite Hälfte ist das Addierernetzwerk. Jedes Kästchen repräsentiert einen einzelnen Addierer - entweder einen Halbaddierer (5 Gatter - 1x XOR und einen Inverter) oder einen Volladdierer (9 Gatter - 2x XOR und NAND die invertierten Übertragsbits). Die oberen sind Eingänge, der untere Ausgang ist die Summe, der linke Ausgang ist die Ausführung. Siehe die vorherige Herausforderung

Der 2x2-Multiplikator wurde dann von Hand für ein maßgeschneidertes 13-Gate-Netzwerk optimiert . Dies entspricht der von @boothby ermittelten optimalen Größe . Vielen Dank!

Durch Einfügen in die Ecke mit dem niedrigen Bit und erneutes Optimieren des Addiererbaums werden fünf Gates gespeichert (siehe Revision 2). Das Einfügen in die Ecke mit dem hohen Bit führt jedoch zu einer Überlappung. Ein bisschen Mathe sagt uns jedoch, dass das Fallenlassen des Low-Bits des High-Multiplikators die Überlappung löst und was zu tun bleibt, ist, die verbleibenden zwei Bits zu addieren und das Zeug zu summieren.

Dies alleine bringt leider keine Einsparungen, eröffnet aber zwei Optimierungen. Erstens haben die beiden Multiplikatoren zwei Gatter gemeinsam und können miteinander verschmolzen werden. Zu diesem Zeitpunkt sind wir wieder bei 55. Zweitens benötigen wir im Additionsnetzwerk keinen Halbaddierer, da wir wissen, dass sein Übertrag Null sein wird. Wir können es durch einen OP ersetzen. Ein ODER ist ein NAND, dessen Eingänge invertiert sind. Dies ergibt zwei 2-Ketten von NOTs auf jedem Zweig, die dann entfernt werden können, um insgesamt fünf Tore einzusparen. Leider trägt der Halbaddierer bei C16 immer noch, daher können wir dort nicht dasselbe tun. Drittens hat ein Volladdierer eine nützliche Eigenschaft: Wenn Sie seine Ein- und Ausgänge invertieren, verhält er sich immer noch gleich. Da alle Eingänge bereits invertiert sind, können wir auch die dahinter liegenden Inverter verschieben. Zweimal. Wir hätten das gleiche im Original tun können, aber ... Naja. Wir haben noch einen Halbaddierer mit zwei invertierten Eingängen. Ich möchte diesen Teil weiter optimieren, aber ich bezweifle, dass ich es kann.

Da wir ein NOT aus einer Komponente herausziehen, müssen wir das irgendwie anzeigen. Wir haben einen Halbaddierer mit invertiertem Übertrag (AKA-getapptes XOR) zu einem Preis von vier Gattern erhalten.

In der Zwischenzeit haben wir auch das Diagramm deutlich neu gezeichnet.

John Dvorak
quelle
Der einzige Teil, der möglicherweise optimisierbar erscheint, ist der mittlere Addiererblock. Die logische Voraussetzung ist ein Super-Volladdierer (benötigt 4 Eingangsbits, hat zwei Übertragsausgangsbits) und ein Volladdierer; Ihre Implementierung mit zwei Volladdierern und zwei Halbaddierern scheint schwer zu verbessern.
Peter Taylor
Ich habe letzte Nacht versucht, genau dieses Netzwerk aufzubauen, aber ich bin anscheinend nicht gut genug mit logischen Netzwerken vertraut.
Joe Z.
Allerbeste!
Stand
9

39 Tore

Ich bin mir ziemlich sicher, dass es hier keine einfacheren Designs gibt als meine. Es war sehr schwer zu machen. Ich mache auch andere Minimalschaltungen.

Die Übertragungsverzögerung wird durch die Abwärtsposition jedes NAND-Gatters auf dem Blatt angezeigt.

Minimaler 3-Bit-Multiplikator

Verilog-Code und Testen:

// MINIMAL 3 BIT MULTIPLICATOR
//
// The simplest 3 bit multiplicator possible, using 39 NAND gates only.
//
// I have also made multiplicators that are faster, more efficient,
// use different gates, and multiply bigger numbers. And I also do
// hard optimization of other circuits. You may contact me at
// [email protected]
// 
// This is my entry to win this hard Programming Puzzle & Code Golf
// at Stack Exchange:
// /codegolf/12261/build-a-multiplying-machine-using-nand-logic-gates/
//
// 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/


module mul3x3 ( in_000, in_001, in_002, in_003, in_004, in_005, out000, out001, out002, out003, out004, out005 );
  input  in_000, in_001, in_002, in_003, in_004, in_005;
  output out000, out001, out002, out003, out004, out005;
  wire   wir000, wir001, wir002, wir003, wir004, wir005, wir006, wir007, wir008, wir009, wir010, wir011, wir012, wir013, wir014, wir015, wir016, wir017, wir018, wir019, wir020, wir021, wir022, wir023, wir024, wir025, wir026, wir027, wir028, wir029, wir030, wir031, wir032;

  nand gate000 ( wir000, in_000, in_005 );
  nand gate001 ( wir001, in_000, in_004 );
  nand gate002 ( wir002, in_000, in_003 );
  nand gate003 ( out000, wir002, wir002 );
  nand gate004 ( wir003, in_004, in_001 );
  nand gate005 ( wir004, wir003, wir003 );
  nand gate006 ( wir005, in_003, in_002 );
  nand gate007 ( wir006, wir000, wir005 );
  nand gate008 ( wir007, in_004, in_002 );
  nand gate009 ( wir008, in_001, in_005 );
  nand gate010 ( wir009, wir008, wir007 );
  nand gate011 ( wir010, in_001, in_003 );
  nand gate012 ( wir011, wir001, wir010 );
  nand gate013 ( wir012, out000, wir004 );
  nand gate014 ( wir013, wir004, wir012 );
  nand gate015 ( wir014, wir011, wir012 );
  nand gate016 ( out001, wir014, wir014 );
  nand gate017 ( wir015, in_002, in_005 );
  nand gate018 ( wir016, wir015, wir015 );
  nand gate019 ( wir017, out000, wir016 );
  nand gate020 ( wir018, wir017, wir013 );
  nand gate021 ( wir019, wir016, wir018 );
  nand gate022 ( wir020, wir019, wir009 );
  nand gate023 ( wir021, wir020, wir017 );
  nand gate024 ( wir022, wir020, wir009 );
  nand gate025 ( wir023, wir022, wir021 );
  nand gate026 ( out005, wir022, wir022 );
  nand gate027 ( wir024, wir016, wir022 );
  nand gate028 ( wir025, wir006, wir018 );
  nand gate029 ( wir026, wir025, wir006 );
  nand gate030 ( wir027, wir025, wir018 );
  nand gate031 ( out002, wir026, wir027 );
  nand gate032 ( wir028, wir004, wir027 );
  nand gate033 ( wir029, wir023, wir028 );
  nand gate034 ( wir030, wir028, wir028 );
  nand gate035 ( wir031, wir030, wir021 );
  nand gate036 ( out004, wir031, wir024 );
  nand gate037 ( wir032, wir029, wir031 );
  nand gate038 ( out003, wir032, wir032 );
endmodule


module mul3x3_test; 
   reg  [5:0] AB; // C=A*B
   wire [5:0] C;

  mul3x3 U1 ( 
  .in_000 (AB[0]), 
  .in_001 (AB[1]), 
  .in_002 (AB[2]), 
  .in_003 (AB[3]), 
  .in_004 (AB[4]), 
  .in_005 (AB[5]), 
  .out000 (C[0]), 
  .out001 (C[1]), 
  .out002 (C[2]), 
  .out003 (C[3]), 
  .out004 (C[4]), 
  .out005 (C[5])
  ); 

  initial  AB=0;
  always  #10  AB = AB+1;
  initial  begin
    $display("\t\ttime,\tA,\tB,\tC"); 
    $monitor("%d,\t%b\t%b\t%b",$time, AB[5:3], AB[2:0],C); 
  end 
  initial  #630  $finish; 
endmodule


// iverilog -o mul3x3_test mul3x3_test.v
// vvp mul3x3_test

Kim Øyhus

KimOyhus
quelle
2
Haben Sie einen Beweis, dass Ihre Antwort gültig ist?
Jonathan Frech
3
Ich würde empfehlen, dies in Logisim (kostenlos) grafisch darzustellen , damit es leicht gesehen und getestet werden kann.
mbomb007
Es ist zu groß, um es als minimal zu beweisen, außer vielleicht von einem zukünftigen Quantencomputer. Deshalb benutze ich statistische Methoden, um die Optimalität zu überprüfen. Es dauert immer noch zu viel Rechenzeit.
KimOyhus
2
Jonathon verlangte eher einen Validitätsnachweis als einen Optimalitätsnachweis. Ich glaube nicht , Sie brauchen es gilt zu beweisen. Aber es wäre schön, wenn wir leichter prüfen
könnten,
4
Das funktioniert: Online ausprobieren!
Anders Kaseorg