W oparciu o moje poprzednie pytanie tego samego typu: Zbuduj maszynę dodającą za pomocą bramek logicznych NAND , tym razem zostaniesz poproszony o pomnożenie zamiast dodania.

Budowanie schemat (dwuprzewodowy) logicznych Bramka NAND, która będzie miała przewody wejściowe A1, A2, A4, B1, B2, B4, reprezentujących dwie liczb binarnych Ana Bod 0 do 7, a wartości powrotne na przewodach wyjściowych C1, C2, C4, C8, C16, i C32, co oznacza C, który jest produktem Ai B.

Twój wynik zależy od liczby bramek NAND, z których korzystasz (1 punkt na bramkę). Aby uprościć rzeczy, możesz użyć bramek AND, OR, NOT i XOR na diagramie z następującymi odpowiednimi wynikami:

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

Każda z tych ocen odpowiada liczbie bramek NAND potrzebnych do zbudowania odpowiedniej bramki.

Najniższy wynik wygrywa.

60 55 50 48 bram

Oryginał (60 bramek) był systematycznym podejściem - pomnóż każdą cyfrę z każdą, a następnie zsumuj je. Mianowicie zobacz drzewa Wallace i Dadda

Górna połowa to sieć mnożenia - pomnóż każdą cyfrę z każdą i zgrupuj cyfry wyjściowe o tej samej wadze. Niektóre bity zostały odwrócone, aby ocalić bramy.

Druga połowa to sieć dodatków. Każde pudełko reprezentuje pojedynczy sumator - albo pół-sumator (5 bramek - 1x XOR i falownik), albo pełny sumator (9 bramek - 2x XOR i NAND odwrócone bity przenoszenia). Górna część to dane wejściowe, dolna wartość wyjściowa to suma, lewe dane wyjściowe to realizacja. zobacz poprzednie wyzwanie

Mnożnik 2x2 został następnie ręcznie zoptymalizowany do niestandardowej sieci 13-bramkowej, która ma optymalny rozmiar znaleziony przez @boothby . Dzięki!

Wklejenie go do dolnego rogu i ponowna optymalizacja drzewa sumatorów powoduje zapisanie pięciu bramek (patrz wersja 2). Jednak wklejenie go również w górnym rogu powoduje nakładanie się. Trochę matematyki mówi nam jednak, że upuszczenie niskiego bitu wysokiego mnożnika rozwiązuje nakładanie się i pozostaje nam dodać dwa pozostałe bity i podsumować rzeczy.

Samo to niestety nie zapewnia żadnych oszczędności, ale otwiera dwie optymalizacje. Po pierwsze, dwa mnożniki mają dwie wspólne bramki i można je ze sobą łączyć. W tym momencie wróciliśmy do 55. Po drugie, w sieci dodatkowej nie potrzebujemy pół-sumatora, ponieważ wiemy, że jego przeniesienie wyniesie zero. Możemy go zastąpić OR. OR jest NAND z odwróconymi wejściami. To daje nam dwa 2 łańcuchy NOT na każdej gałęzi, które można następnie usunąć, co daje całkowitą oszczędność pięciu bramek. Niestety, pół-sumator w C16 nadal ma, więc nie możemy zrobić tego samego. Po trzecie, pełny sumator ma użyteczną właściwość: jeśli odwrócisz jego dane wejściowe i wyjściowe, nadal zachowuje się tak samo. Ponieważ wszystkie jego wejścia są już odwrócone, równie dobrze możemy przesunąć za nim falowniki. Dwa razy. Mogliśmy zrobić to samo w oryginale, ale ... No cóż. Nadal mamy pół sumatora z dwoma odwróconymi wejściami. Chcę bardziej zoptymalizować tę część, ale wątpię, czy potrafię.

Ponieważ wyciągamy NIE z wnętrza komponentu, musimy to jakoś zaznaczyć. Otrzymaliśmy pół-sumator z odwróconym przenoszeniem (AKA z gwintem XOR) kosztem czterech bram.

W międzyczasie znacznie przerysowaliśmy schemat.

39 bram

Jestem pewien, że nie ma tutaj prostszych projektów niż moje. To było bardzo trudne do zrobienia. Robię też inne minimalne obwody.

Opóźnienie transmisji jest wskazywane przez położenie w dół każdej bramki NAND na arkuszu.

Kod Verilog i testy:

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