Создайте умножающую машину, используя логические элементы NAND

20

Исходя из моего предыдущего вопроса того же типа, « Создайте машину добавления, используя логические элементы 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, необходимых для построения соответствующих вентилей.

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

Джо З.
источник
Я пытаюсь сделать последний пример в Logisim. Это сложно.
Джо З.
Я получил достаточно всего этого в моей школе, нет, спасибо.
Йоханнес Кун
7
У меня есть универсальный оптимизатор для подобных задач. Он, безусловно, находит самую короткую программу для вычисления логической функции с k-выходом. Если бы я дал ему неделю, он мог бы сказать, оптимален ли найденный им множитель 13 gate 2x2. 3x3? Я буду мертв, пока он не закончится.
Boothby
1
Этот множитель 13 вентилей 2x2 является оптимальным (и содержится в ответе Яна). Учитывая это, и еще несколько частей, которые я могу оптимизировать, я очень сильно подозреваю, что 60 будет оптимальным решением для этой проблемы. Я действительно надеюсь, что кто-то докажет, что я не прав.
Boothby
@boothby Не совсем. Наивное применение деревьев сумматора приводит к решению с 18 воротами (4 AND, 2 полумодера), что приводит меня к мысли: я должен быть в состоянии украсть ^ k ^ k ^ k ^ k ^ k, используя 13 ворот Множитель 2х2.
Джон Дворжак

Ответы:

24

60 55 50 48 ворот

Множитель 48 вентилей


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

Умножитель на 60 вентилей

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

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

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

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

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

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

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

Джон дворак
источник
Единственная часть, которая выглядит потенциально оптимизируемой - это средний блок сумматоров. Логическое требование для супер-сумматора (занимает 4 входных бита, имеет два выходных бита переноса) и полного сумматора; Ваша реализация с двумя полными сумматорами и двумя полусуммерами выглядит трудно улучшить.
Питер Тейлор
Вчера вечером я пытался создать именно эту сеть, но, похоже, я недостаточно разбираюсь в логических сетях.
Джо З.
Самый превосходный!
Boothby
9

39 ворот

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

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

Минимальный 3-битный множитель

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

Ким Ойхус

KimOyhus
источник
2
У вас есть доказательства того, что ваш ответ действителен?
Джонатан Фрех
3
Я бы порекомендовал сделать это в Logisim (это бесплатно), чтобы его можно было легко увидеть и протестировать.
mbomb007
Он слишком большой, чтобы быть доказанным как минимальный, за исключением, возможно, будущего квантового компьютера. Поэтому я использую статистические методы для проверки его оптимальности. Это все еще занимает слишком много вычислительного времени.
KimOyhus
2
Джонатон попросил доказательства правильности, а не доказательства оптимальности. Я не думаю, что вам нужно доказывать это. Но было бы неплохо, если бы нам было проще проверить, действительно ли это, а не принять ваше слово за это
H.PWiz
4
Это работает: попробуйте онлайн!
Андерс Касеорг,