Исходя из моего предыдущего вопроса того же типа, « Создайте машину добавления, используя логические элементы NAND , на этот раз вас попросят умножить вместо добавления».

Построить схему (двухпроводные) NAND - логических вентилей , которые будут принимать входные провода A1, A2, A4, B1, B2, B4, представляющие два двоичных чисел Aв Bот 0 до 7, а возвращаемых значений на выходных проводах C1, C2, C4, C8, C16, и C32, представляя C, который является продуктом Aи B.

Ваша оценка определяется количеством используемых вами ворот NAND (1 балл за ворота). Чтобы упростить задачу, вы можете использовать на диаграмме вентили AND, OR, NOT и XOR со следующими соответствующими баллами:

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

Каждый из этих баллов соответствует количеству вентилей NAND, необходимых для построения соответствующих вентилей.

Самый низкий балл побеждает.

60 55 50 48 ворот

Оригинал (60 ворот) был систематическим подходом - умножьте каждую цифру на каждую, а затем сложите их вместе. А именно, увидеть деревья Уоллеса и Дадда

Верхняя половина - это сеть умножения - умножьте каждую цифру на каждую и сгруппируйте выходные цифры с одинаковым весом. Некоторые биты были оставлены инвертированными, чтобы сохранить ворота.

Вторая половина - сеть сумматора. Каждый блок представляет собой один сумматор - либо половинный сумматор (5 вентилей - 1x XOR и инвертор), либо полный сумматор (9 вентилей - 2x XOR и NAND инвертированные биты переноса). Верхняя часть - это входные данные, нижняя часть - это сумма, левая часть - результат. увидеть предыдущий вызов

Затем множитель 2x2 был оптимизирован вручную для специально созданной сети с 13 шлюзами , что является оптимальным размером, найденным @boothby . Благодарность!

Вставка его в младший бит и повторная оптимизация дерева сумматоров экономит пять элементов (см. Редакцию № 2). Однако вставка его в верхний угол приводит к наложению. Немного математики говорит нам, однако, что отбрасывание младшего бита старшего множителя решает наложение, и что остается сделать, это добавить оставшиеся два бита и суммировать вещи.

Одно это, к сожалению, не дает никакой экономии, но открывает две оптимизации. Во-первых, два множителя имеют два общих элемента и могут быть объединены вместе. На данный момент мы вернулись к 55. Во-вторых, в сети дополнений нам не нужен полудейдер, потому что мы знаем, что его перенос будет равен нулю. Мы можем заменить его на ИЛИ. OR - это NAND с инвертированными входами. Это приводит нас к двум 2-цепочкам NOT на каждую ветвь, которые затем могут быть удалены для общей экономии пяти шлюзов. К сожалению, половина сумматора в C16 все еще несет, поэтому мы не можем сделать то же самое там. В-третьих, у полного сумматора есть полезное свойство: если вы инвертируете его входы и выходы, он все равно будет вести себя одинаково. Поскольку все его входы уже инвертированы, мы также можем переместить инверторы за ним. Дважды. Мы могли бы сделать то же самое в оригинале, но ... Ну что ж. У нас еще есть половинный сумматор с двумя инвертированными входами. Я хочу оптимизировать эту часть больше, но я сомневаюсь, что смогу.

Поскольку мы вытягиваем НЕ из компонента, мы должны как-то это обозначить. Мы получили половину сумматора с перевернутым переносом (AKA Tapped XOR) по цене четырех ворот.

Тем временем мы также значительно переработали диаграмму.

39 ворот

Я совершенно уверен, что здесь нет более простых конструкций, чем мой. Это было очень сложно сделать. Я делаю другие минимальные схемы тоже.

Задержка передачи указывается положением вниз каждого элемента NAND на листе.

Verilog код и тестирование:

// 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
// kim.oyhus@gmail.com
// 
// 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

Ким Ойхус