Construisez une machine multiplicatrice à l'aide de portes logiques NAND

20

Sur la base de ma question précédente du même type, Construisez une machine à ajouter à l'aide de portes logiques NAND , cette fois, vous êtes invité à multiplier au lieu d'ajouter.

Construire un diagramme de (deux fils) portes logiques NON -ET qui prend les fils d'entrée A1, A2, A4, B1, B2, B4, représentant deux nombres binaires Aà Bde 0 à 7, et des valeurs de retour sur les fils de sortie C1, C2, C4, C8, C16, et C32, soit C, qui est le produit de Aet B.

Votre score est déterminé par le nombre de portes NAND que vous utilisez (1 point par porte). Pour simplifier les choses, vous pouvez utiliser les portes ET, OU, NON et XOR dans votre diagramme, avec les scores correspondants suivants:

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

Chacun de ces scores correspond au nombre de portes NAND qu'il faut pour construire la porte correspondante.

Le score le plus bas l'emporte.

Joe Z.
la source
J'essaie de faire un exemple de dernière place dans Logisim. Ce truc est dur.
Joe Z.
J'en ai assez de ce truc dans mon école, non merci.
Johannes Kuhn
7
J'ai un optimiseur universel pour des tâches comme celle-ci. Il trouve de manière probante le programme le plus court pour calculer une fonction booléenne k-output. Si je lui donnais une semaine, il pourrait me dire si le multiplicateur 13 portes 2x2 qu'il a trouvé est optimal. 3x3? Je serai mort avant la fin.
stand
1
Ce multiplicateur 13 portes 2x2 est optimal (et contenu dans la réponse de Jan). Avec cela, et quelques autres pièces que je peux optimiser, je soupçonne très fortement 60 d'être optimal pour ce problème. J'espère vraiment que quelqu'un me prouve le contraire.
boothby
@boothby Pas vraiment. L'application naïve d'arbres additionneurs conduit à une solution à 18 portes (4 ET, 2 demi-additionneurs), ce qui m'amène à une idée: je devrais être capable de voler ^ k ^ k ^ k ^ k ^ k utiliser la porte 13 Multiplicateur 2x2.
John Dvorak

Réponses:

24

60 55 50 48 portes

Multiplicateur à 48 portes


L'original (60 portes) était l'approche systématique - multipliez chaque chiffre par chacun, puis additionnez-les. À savoir, voir les arbres Wallace et les arbres Dadda

Multiplicateur à 60 portes

La moitié supérieure est le réseau de multiplication - multipliez chaque chiffre par chacun et groupez les chiffres de sortie avec le même poids. Certains bits ont été laissés inversés pour sauver les portes.

La seconde moitié est le réseau d'additionneurs. Chaque boîte représente un additionneur unique - soit un demi-additionneur (5 portes - 1x XOR et un onduleur), soit un additionneur complet (9 portes - 2x XOR et NAND les bits de report inversés). Le haut sont des entrées, la sortie du bas est la somme, la sortie de gauche est le report. voir le défi précédent

Le multiplicateur 2x2 a ensuite été optimisé à la main pour un réseau à 13 portes construit sur mesure, qui est la taille optimale trouvée par @boothby . Merci!

Le coller dans le coin des bits bas et réoptimiser l'arbre d'addition permet d'économiser cinq portes (voir révision # 2). Cependant, le coller également dans le coin élevé produit un chevauchement. Un peu de maths nous dit, cependant, que la suppression du bit bas du multiplicateur élevé résout le chevauchement et ce qui reste à faire est d'ajouter les deux bits restants et de résumer les choses.

Cela seul, malheureusement, ne permet pas de réaliser des économies, mais il ouvre deux optimisations. Premièrement, les deux multiplicateurs ont deux portes en commun et peuvent être fusionnés ensemble. À ce stade, nous sommes de retour à 55. Deuxièmement, dans le réseau d'addition, nous n'avons pas besoin d'un demi-additionneur car nous savons que son portage sera nul. Nous pouvons le remplacer par un OU. Un OU est un NAND avec ses entrées inversées. Cela nous produit avec deux chaînes de 2 NOT sur chaque branche, qui peuvent ensuite être supprimées, pour une économie totale de cinq portes. Malheureusement, le demi-additionneur à C16 porte toujours, donc nous ne pouvons pas faire la même chose là-bas. Troisièmement, un additionneur complet a une propriété utile: si vous inversez ses entrées et ses sorties, il se comporte toujours de la même manière. Comme toutes ses entrées sont déjà inversées, on peut tout aussi bien déplacer les onduleurs derrière lui. Deux fois. Nous aurions pu faire la même chose dans l'original, mais ... tant pis. Nous avons encore un demi-additionneur avec deux entrées inversées. Je veux optimiser davantage cette partie, mais je doute que je puisse.

Puisque nous retirons un NOT de l'intérieur d'un composant, nous devons le signifier d'une manière ou d'une autre. Nous avons obtenu un demi-additionneur à portage inversé (AKA taraudé XOR) au prix de quatre portes.

En attendant, nous avons également redessiné le diagramme de manière significative.

John Dvorak
la source
La seule partie qui semble potentiellement optimisable est le bloc central d'additionneurs. L'exigence logique est pour un additionneur superfull (prend 4 bits d'entrée, a deux bits de sortie de report) et un additionneur complet; votre implémentation avec deux ajouteurs complets et deux demi-ajouteurs semble difficile à améliorer.
Peter Taylor
J'ai essayé de faire ce réseau exact hier soir, mais je ne connais pas assez bien les réseaux logiques, semble-t-il.
Joe Z.
Le plus excellent!
stand
9

39 portes

Je suis sûr qu'il n'y a pas de conceptions plus simples que les miennes ici. C'était très difficile à faire. Je fais aussi d'autres circuits minimaux.

Le retard de transmission est indiqué par la position vers le bas de chaque porte NON-ET sur la feuille.

Multiplicateur minimal de 3 bits

Code Verilog et tests:

// 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
la source
2
Avez-vous une preuve que votre réponse est valide?
Jonathan Frech
3
Je recommanderais de schématiser cela dans Logisim (c'est gratuit), afin qu'il puisse être facilement vu et testé.
mbomb007
Il est trop grand pour être prouvé comme minimal, sauf peut-être par un futur ordinateur quantique. J'utilise donc des méthodes statistiques pour vérifier son optimalité. Cela prend toujours un temps de calcul excessif.
KimOyhus
2
Jonathon a demandé une preuve de validité plutôt qu'une preuve d'optimalité. Je ne pense pas que vous ayez besoin de prouver sa validité. Mais ce serait bien s'il était plus facile pour nous de tester si cela est valide, plutôt que de vous
croire
4
Cela fonctionne: essayez-le en ligne!
Anders Kaseorg