Com base na minha pergunta anterior do mesmo tipo, Construa uma máquina de adicionar usando portas lógicas NAND , desta vez você está sendo solicitado a multiplicar em vez de adicionar.

Construir um diagrama de portas (de dois fios) lógicas NAND que vai levar os cabos de entrada A1, A2, A4, B1, B2, B4, representando dois números binários Apara B0-7, e valores de retorno sobre os fios de saída C1, C2, C4, C8, C16, e C32, representando C, qual é o produto de Ae B.

Sua pontuação é determinada pelo número de portões NAND que você usa (1 ponto por portão). Para simplificar, você pode usar as portas AND, OR, NOT e XOR no seu diagrama, com as seguintes pontuações correspondentes:

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

Cada uma dessas pontuações corresponde ao número de portas NAND necessárias para construir o portão correspondente.

Menor pontuação ganha.

60 55 50 48 portões

O original (60 portas) era a abordagem sistemática - multiplique cada dígito por cada um e depois some-os. Ou seja, veja árvores Wallace e árvores Dadda

A metade superior é a rede de multiplicação - multiplique cada dígito por cada e agrupe os dígitos de saída com o mesmo peso. Alguns bits foram deixados invertidos para salvar os portões.

A segunda metade é a rede de somadores. Cada caixa representa um somador único - um meio adicionador (5 portas - 1x XOR e um inversor) ou um adicionador completo (9 portas - 2x XOR e NAND os bits de transporte invertidos). A parte superior são entradas, a saída inferior é a soma, a saída esquerda é a execução. veja o desafio anterior

O multiplicador 2x2 foi então otimizado manualmente para uma rede de 13 portas customizada, que é o tamanho ideal conforme encontrado por @boothby . Obrigado!

Colá-lo no canto mais baixo e otimizar a árvore do somador salva cinco portas (consulte a revisão nº 2). Colá-lo no canto mais alto também produz sobreposição. Um pouco de matemática nos diz, no entanto, que largar o baixo do multiplicador alto resolve a sobreposição e o que resta fazer é adicionar os dois bits restantes e resumir as coisas.

Infelizmente, isso por si só não fornece nenhuma economia, mas abre duas otimizações. Primeiro, os dois multiplicadores têm dois portões em comum e podem ser fundidos. Neste ponto, estamos de volta aos 55 anos. Segundo, na rede de adição, não precisamos de um meio adicionador, porque sabemos que sua carga será zero. Podemos substituí-lo por um OR. Um OR é um NAND com suas entradas invertidas. Isso nos produz duas cadeias de NOTs em cada filial, que podem ser removidas para uma economia total de cinco portões. Infelizmente, o semi-somador em C16 ainda carrega, então não podemos fazer o mesmo lá. Terceiro, um somador completo possui uma propriedade útil: se você inverter suas entradas e saídas, ele ainda se comportará da mesma maneira. Como todas as suas entradas já estão invertidas, também podemos mover os inversores para trás. Duas vezes. Poderíamos ter feito o mesmo no original, mas ... Ah bem. Ainda temos um meio adicionador com duas entradas invertidas. Quero otimizar mais esta parte, mas duvido que possa.

Como estamos retirando um NOT de dentro de um componente, temos que significar isso de alguma forma. Obtivemos um semi-somador com transporte invertido (AKA aproveitado XOR) a um custo de quatro portas.

Enquanto isso, também redesenhamos o diagrama significativamente.

39 portões

Tenho certeza de que não há projetos mais simples do que o meu aqui. Foi muito difícil de fazer. Também faço outros circuitos mínimos.

O atraso da transmissão é indicado pela posição descendente de cada porta NAND na folha.

Código Verilog e testes:

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