Construye una máquina multiplicadora usando puertas lógicas NAND

20

Basado en mi pregunta anterior del mismo tipo, Construya una máquina sumadora usando compuertas lógicas NAND , esta vez se le pide que multiplique en lugar de sumar.

Construir un diagrama de las puertas (dos hilos) de lógica NAND que se llevará a los cables de entrada A1, A2, A4, B1, B2, B4, lo que representa dos números binarios Aa Bde 0 a 7, y los valores de retorno de los cables de salida C1, C2, C4, C8, C16, y C32, lo que representa C, cuál es el producto de Ay B.

Su puntaje está determinado por la cantidad de compuertas NAND que usa (1 punto por compuerta). Para simplificar las cosas, puede usar las compuertas AND, OR, NOT y XOR en su diagrama, con los siguientes puntajes correspondientes:

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

Cada una de estas puntuaciones corresponde al número de puertas NAND que se necesitan para construir la puerta correspondiente.

La puntuación más baja gana.

Joe Z.
fuente
Estoy tratando de hacer un ejemplo de último lugar en Logisim. Esto es dificil.
Joe Z.
Tengo suficiente de estas cosas en mi escuela, no, gracias.
Johannes Kuhn
77
Tengo un optimizador universal para tareas como esta. Probablemente encuentra el programa más corto para calcular una función booleana de salida k. Si le diera una semana, podría decirme si el multiplicador 13x 2x2 que encontró es óptimo. 3x3? Estaré muerto antes de que termine.
stand el
1
Ese multiplicador de 13 puertas 2x2 es óptimo (y figura en la respuesta de Jan). Con eso, y otras pocas piezas que puedo optimizar, sospecho que 60 es óptimo para este problema. Realmente espero que alguien demuestre que estoy equivocado.
stand
@Boothby No realmente. La aplicación ingenua de árboles sumadores conduce a una solución de 18 puertas (4 AND, 2 medios sumadores), lo que me lleva a una idea: debería poder robar ^ k ^ k ^ k ^ k ^ k utilizar las 13 puertas Multiplicador 2x2.
John Dvorak

Respuestas:

24

60 55 50 48 puertas

Multiplicador de 48 puertas


El original (60 puertas) fue el enfoque sistemático: multiplique cada dígito con cada uno y luego sume los dos. A saber, ver árboles Wallace y árboles Dadda

Multiplicador de 60 puertas

La mitad superior es la red de multiplicación: multiplique cada dígito con cada uno y agrupe los dígitos de salida con el mismo peso. Se han invertido algunos bits para salvar las puertas.

La segunda mitad es la red de sumadores. Cada cuadro representa un sumador único, ya sea un medio sumador (5 puertas - 1x XOR y un inversor), o un sumador completo (9 puertas - 2x XOR y NAND los bits de transporte invertidos). La parte superior son entradas, la salida inferior es la suma, la salida izquierda es la ejecución. ver el desafío anterior

El multiplicador 2x2 se ha optimizado manualmente para una red personalizada de 13 puertas, que es el tamaño óptimo que encontró @boothby . ¡Gracias!

Pegarlo en la esquina de bits bajos y volver a optimizar el árbol sumador ahorra cinco puertas (vea la revisión # 2). Pegarlo también en la esquina de bits altos, sin embargo, produce superposición. Sin embargo, un poco de matemática nos dice que soltar el bit bajo del multiplicador alto resuelve la superposición y lo que queda por hacer es agregar los dos bits restantes y resumir cosas.

Esto solo, desafortunadamente, no proporciona ningún ahorro, pero abre dos optimizaciones. Primero, los dos multiplicadores tienen dos puertas en común, y pueden fusionarse. En este punto, estamos de vuelta en 55. Segundo, en la red de suma, no necesitamos un medio sumador porque sabemos que su acarreo será cero. Podemos reemplazarlo con un OR. Un OR es una NAND con sus entradas invertidas. Esto nos produce dos cadenas 2 de NOT en cada rama, que luego se pueden quitar, para un ahorro total de cinco puertas. Desafortunadamente, el medio sumador en C16 todavía lleva, por lo que no podemos hacer lo mismo allí. Tercero, un sumador completo tiene una propiedad útil: si invierte sus entradas y sus salidas, todavía se comporta igual. Como todas sus entradas ya están invertidas, también podemos mover los inversores detrás de él. Dos veces. Podríamos haber hecho lo mismo en el original, pero ... Oh bien. Todavía tenemos un medio sumador con dos entradas invertidas. Quiero optimizar esta parte más, pero dudo que pueda.

Como sacamos un NOT del interior de un componente, tenemos que indicarlo de alguna manera. Hemos obtenido un medio sumador con transporte invertido (también conocido como XOR roscado) a un costo de cuatro puertas.

Mientras tanto, también hemos redibujado significativamente el diagrama.

John Dvorak
fuente
La única parte que parece potencialmente optimizable es el bloque medio de sumadores. El requisito lógico es un sumador super lleno (toma 4 bits de entrada, tiene dos bits de salida de transporte) y un sumador completo; su implementación con dos sumadores completos y dos sumadores medios parece difícil de mejorar.
Peter Taylor
Intenté hacer esta red exacta anoche, pero parece que no estoy lo suficientemente versado en redes lógicas.
Joe Z.
¡El mas excelente!
Boothby
9

39 puertas

Estoy bastante seguro de que no hay diseños más simples que los míos aquí. Fue muy difícil de hacer. También hago otros circuitos mínimos.

El retraso de la transmisión se indica mediante la posición hacia abajo de cada compuerta NAND en la hoja.

Multiplicador mínimo de 3 bits

Código Verilog y pruebas:

// 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
fuente
2
¿Tiene una prueba de que su respuesta es válida?
Jonathan Frech
3
Recomendaría diagramar esto en Logisim (es gratis), para que pueda verse y probarse fácilmente.
mbomb007
Es demasiado grande para ser probado como mínimo, excepto quizás por una futura computadora cuántica. Así que uso métodos estadísticos para verificar su optimización. Todavía lleva una cantidad excesiva de tiempo de computación.
KimOyhus
2
Jonathon solicitó una prueba de validez, en lugar de una prueba de optimización. No creo que necesites demostrar que es válido. Pero sería bueno si fuera más fácil para nosotros comprobar si esto es válido, en lugar de tomar su palabra al respecto
H.PWiz
44
Esto funciona: ¡ pruébelo en línea!
Anders Kaseorg el