Membangun mesin pengganda menggunakan gerbang logika NAND

20

Berdasarkan pertanyaan saya sebelumnya dari jenis yang sama, Bangun mesin tambah menggunakan gerbang logika NAND , kali ini Anda diminta untuk mengalikan bukan menambah.

Membangun diagram gerbang (dua-kawat) NAND logika yang akan membawa kabel masukan A1, A2, A4, B1, B2, B4, yang mewakili dua angka biner Auntuk B0-7, dan kembali nilai-nilai pada kabel keluaran C1, C2, C4, C8, C16, dan C32, yang mewakili C, yang merupakan produk dari Adan B.

Skor Anda ditentukan oleh jumlah gerbang NAND yang Anda gunakan (1 poin per gerbang). Untuk menyederhanakan banyak hal, Anda dapat menggunakan gerbang AND, OR, NOT, dan XOR dalam diagram Anda, dengan skor terkait berikut:

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

Masing-masing skor ini sesuai dengan jumlah gerbang NAND yang diperlukan untuk membangun gerbang yang sesuai.

Skor terendah menang.

Joe Z.
sumber
Saya mencoba membuat contoh tempat terakhir di Logisim. Ini sulit.
Joe Z.
Aku punya cukup banyak barang di sekolah, tidak, terima kasih.
Johannes Kuhn
7
Saya memiliki pengoptimal universal untuk tugas-tugas seperti ini. Itu terbukti menemukan program terpendek untuk menghitung fungsi boolean k-output. Jika saya memberi seminggu, itu bisa memberi tahu saya jika 13 gerbang 2x2 pengganda itu ditemukan optimal. 3x3? Aku akan mati sebelum selesai.
boothby
1
Pengganda 13 gerbang 2x2 itu optimal (dan terkandung dalam jawaban Jan). Dengan itu, dan beberapa bagian lain yang bisa saya optimalkan, saya sangat curiga 60 akan optimal untuk masalah ini. Saya sangat berharap seseorang membuktikan saya salah.
booth
@ bbyby Tidak juga. Penerapan pohon adder yang naif mengarah pada solusi 18-gerbang (4 ANDs, 2 setengah-adders), yang menuntun saya pada sebuah ide: Saya seharusnya bisa mencuri ^ k ^ k ^ k ^ k ^ k memanfaatkan memanfaatkan 13-gate 2x2 pengganda.
John Dvorak

Jawaban:

24

60 55 50 48 gerbang

Pengganda 48 gerbang


Asli (60 gerbang) adalah pendekatan sistematis - gandakan setiap digit dengan masing-masing, dan kemudian jumlahkan semuanya. Yaitu, lihat pohon Wallace dan pohon Dadda

Pengganda 60 gerbang

Bagian atas adalah jaringan perkalian - gandakan setiap digit dengan masing-masing, dan kelompokkan digit keluaran dengan bobot yang sama. Beberapa bit dibiarkan terbalik untuk menyelamatkan gerbang.

Bagian kedua adalah jaringan adder. Setiap kotak mewakili satu penambah - baik penambah setengah (5 gerbang - 1x XOR dan inverter), atau penambah penuh (9 gerbang - 2x XOR dan NAND bit pembawa yang terbalik). Atas adalah input, output bawah adalah jumlah, output kiri adalah pelaksanaan. lihat tantangan sebelumnya

Pengganda 2x2 kemudian dioptimalkan dengan tangan ke jaringan 13-gerbang yang dibuat khusus, yang merupakan ukuran optimal seperti yang ditemukan oleh @boothby . Terima kasih!

Menempelnya ke sudut bit-rendah dan mengoptimalkan kembali pohon penambah menyimpan lima gerbang (lihat revisi # 2). Menempelkannya ke sudut bit tinggi juga menghasilkan tumpang tindih. Sedikit matematika memberi tahu kita, bahwa menjatuhkan bit-rendah dari pengali tinggi memecahkan tumpang tindih dan apa yang tersisa untuk dilakukan adalah menambahkan dua bit yang tersisa dan meringkas hal-hal.

Sayangnya, ini saja, tidak memberikan penghematan apa pun, tetapi membuka dua optimisasi. Pertama, dua pengganda memiliki dua gerbang yang sama, dan dapat digabungkan bersama. Pada titik ini, kita kembali ke 55. Kedua, di jaringan tambahan, kita tidak perlu setengah-penambah karena kita tahu carry-nya akan nol. Kita bisa menggantinya dengan OR. OR adalah NAND dengan inputnya terbalik. Ini menghasilkan kita dengan dua rantai TIDAK pada masing-masing cabang, yang kemudian dapat dihilangkan, untuk penghematan total lima gerbang. Sayangnya, setengah penambah di C16 masih membawa, jadi kita tidak bisa melakukan hal yang sama di sana. Ketiga, penambah lengkap memiliki properti yang berguna: jika Anda membalikkan input dan outputnya, ia tetap berperilaku sama. Karena semua inputnya sudah terbalik, kita bisa juga memindahkan inverter di belakangnya. Dua kali. Kita bisa melakukan hal yang sama di aslinya, tetapi ... Baiklah. Kami masih memiliki setengah penambah dengan dua input terbalik. Saya ingin lebih mengoptimalkan bagian ini, tetapi saya ragu saya bisa.

Karena kita mengeluarkan BUKAN dari dalam suatu komponen, kita harus menandakannya entah bagaimana. Kami telah memperoleh setengah penambah dengan carry terbalik (AKA mengetuk XOR) dengan biaya empat gerbang.

Sementara itu, kami juga telah menggambar ulang diagram secara signifikan.

John Dvorak
sumber
Satu-satunya bagian yang terlihat berpotensi dioptimalkan adalah blok tengah dari adders. Persyaratan logis adalah untuk adder superfull (mengambil 4 bit input, memiliki dua bit output carry) dan adder penuh; implementasi Anda dengan dua penambah penuh dan dua penambah setengah terlihat sulit untuk ditingkatkan.
Peter Taylor
Saya mencoba membuat jaringan yang tepat tadi malam, tapi saya tidak cukup berpengalaman dalam jaringan logis, tampaknya.
Joe Z.
Paling luar biasa!
booth
9

39 gerbang

Saya cukup yakin tidak ada desain yang lebih sederhana dari saya di sini. Sangat sulit dibuat. Saya membuat sirkuit minimal lainnya juga.

Penundaan transmisi ditunjukkan oleh posisi ke bawah dari setiap gerbang NAND pada lembar.

Minimal pengganda 3 bit

Kode dan pengujian 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
// [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
sumber
2
Apakah Anda memiliki bukti bahwa jawaban Anda valid?
Jonathan Frech
3
Saya akan merekomendasikan diagram ini dalam Logisim (gratis), sehingga dapat dengan mudah dilihat dan diuji.
mbomb007
Terlalu besar untuk dibuktikan minimal, kecuali mungkin oleh komputer kuantum masa depan. Jadi saya menggunakan metode statistik untuk memverifikasi optimalitasnya. Masih membutuhkan banyak waktu komputasi.
KimOyhus
2
Jonathon meminta bukti validitas, bukan bukti optimalitas. Saya pikir Anda tidak perlu membuktikannya valid. Tapi alangkah baiknya jika lebih mudah bagi kita untuk menguji apakah ini valid, daripada mengambil kata-kata Anda
H.PWiz
4
Ini berhasil: coba online!
Anders Kaseorg