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.

60 55 50 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

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.

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.

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