Skip to content

Costruire una macchina moltiplicatrice utilizzando porte logiche NAND

Il nostro gruppo di specialisti dopo diversi giorni di ricerca e raccolta dati, abbiamo ottenuto la soluzione, speriamo che possa essere molto utile nel tuo piano.

Soluzione:

60 55 50 48 cancelli

Moltiplicatore da 48-gate


L'approccio originale (60 porte) era quello sistematico: moltiplicare ogni cifra per ogni cifra e poi sommarle. Si vedano, ad esempio, gli alberi di Wallace e gli alberi di Dadda.

Moltiplicatore da 60 gate

La metà superiore è la rete di moltiplicazione: moltiplica ogni cifra con ciascuna e raggruppa le cifre in uscita con lo stesso peso. Alcuni bit sono stati lasciati invertiti per risparmiare le porte.

La seconda metà è la rete degli addizionatori. Ogni riquadro rappresenta un singolo sommatore, sia esso un half-adder (5 porte - 1x XOR e un inverter), o un sommatore completo (9 porte - 2x XOR e NAND i bit di riporto invertiti). Gli ingressi in alto, l'uscita in basso è la somma, l'uscita a sinistra è il riporto. vedi la sfida precedente

Il moltiplicatore 2x2 è stato poi ottimizzato a mano con una rete a 13 porte costruita su misura, che è la dimensione ottimale trovata da @boothby. Grazie!

Incollandolo nell'angolo a basso bit e riottimizzando l'albero dell'addizionatore si risparmiano cinque porte (vedi revisione #2). Incollandolo anche nell'angolo ad alto bit, tuttavia, si ottiene una sovrapposizione. Un po' di matematica ci dice, tuttavia, che eliminando il bit basso del moltiplicatore alto si risolve la sovrapposizione e ciò che resta da fare è sommare i due bit rimanenti e fare la somma.

Questa soluzione, purtroppo, non consente di risparmiare, ma permette di ottenere due ottimizzazioni. Innanzitutto, i due moltiplicatori hanno due porte in comune e possono essere fusi insieme. A questo punto, siamo di nuovo a 55. In secondo luogo, nella rete di addizione non abbiamo bisogno di un half-adder perché sappiamo che il suo riporto sarà zero. Possiamo sostituirlo con un OR. Un OR è una NAND con gli ingressi invertiti. In questo modo si ottengono due catene di NOT su ogni ramo, che possono essere rimosse, per un risparmio totale di cinque porte. Sfortunatamente, il semiconduttore in C16 è ancora portante, quindi non possiamo fare lo stesso. In terzo luogo, un sommatore completo ha una proprietà utile: se si invertono i suoi ingressi e le sue uscite, si comporta ancora allo stesso modo. Poiché tutti i suoi ingressi sono già invertiti, possiamo spostare gli invertitori dietro di esso. Due volte. Avremmo potuto fare lo stesso nell'originale, ma... oh beh. Abbiamo ancora una semicella con due ingressi invertiti. Vorrei ottimizzare di più questa parte, ma dubito di riuscirci.

Poiché stiamo estraendo un NOT dall'interno di un componente, dobbiamo segnalarlo in qualche modo. Abbiamo ottenuto un half-adder con carry invertito (AKA tapped XOR) al costo di quattro porte.

Nel frattempo, abbiamo anche ridisegnato il diagramma in modo significativo.

39 porte

Sono certo che non esistono progetti più semplici del mio.
È stato molto difficile da realizzare. Faccio anche altri circuiti minimi.

Il ritardo di trasmissione è indicato dalla posizione verso il basso di ciascun gate NAND sul foglio.

Moltiplicatore minimo a 3 bit

Codice Verilog e test:

// 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:
// https://codegolf.stackexchange.com/questions/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("tttime,tA,tB,tC"); 
    $monitor("%d,t%bt%bt%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

Valutazioni e commenti

Puoi aggiungere valore ai nostri contenuti informativi contribuendo con la tua esperienza nelle spiegazioni.



Utilizzate il nostro motore di ricerca

Ricerca
Generic filters

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.