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.

60 55 50 48 Tore

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

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.

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.

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