Apakah ada algoritma untuk menentukan jumlah minimum gerbang NAND atau NOR
- diberikan sejumlah input
- ketersediaan / tidak tersedianya input yang dilengkapi
diperlukan untuk mewujudkan ekspresi Boolean? Kita bisa mendapatkan bentuk AND-OR sebagai implant utama melalui peta Karnaugh yang minimal (sejauh yang saya tahu, algoritma Quine-McCluskey mendapatkannya secara deterministik). Apakah ada teknik serupa untuk implementasi NAND atau NOR? Setidaknya, teknik seperti itu harus menentukan jumlah minimum yang diperlukan dari gerbang NAND / NOR bahkan tanpa menemukan diagram yang sebenarnya?
Menerapkan hukum De Morgan pada implan utama tampaknya tidak deterministik,
A ⊕ B = A'B + AB' = ((A'B)'(AB')')' [5 NAND gates]
A ⊕ B = (AB + A'B')' = ((ABAB+ABB') + (A'AB+A'B'))' = (AB(AB+B') + A'(AB+B'))' = ((AB+A')(AB+B'))' = (((AB)'A)'((AB)'B)')' [4 NAND gates by reusing (AB)']
logic-gates
boolean-algebra
Samik
sumber
sumber
Jawaban:
Anda hanya dapat menemukan jumlah minimum gerbang di jaringan multi-level dengan menyelesaikan masalah pemrograman bilangan bulat [atau yang setara, lihat di bawah]. Masalah ini NP-lengkap, jadi hanya praktis untuk menyelesaikan hingga selusin gerbang atau lebih.
Ada metode perkiraan yang tidak akan memberi Anda jumlah minimum tetapi lebih mudah ditelusuri dalam hal waktu yang diperlukan ... Ini adalah topik besar dalam diri mereka sendiri, pada dasarnya seluruh bidang optimasi multi-level. Anda dapat membaca ikhtisar [gratis] di sini .
Untuk jaringan kecil NAND (hingga 4 variabel), masalahnya telah sepenuhnya diselesaikan dengan penghitungan lengkap [atau metode yang setara]. Ada tesis PhD [2009] yang cukup baru oleh Elizabeth Ann Ernst yang merangkum hasil kuno dan memperluasnya. Ernst menggunakan cabang-dan-terikat, yang meningkatkan metode lengkap dalam praktek, tetapi tidak asimtotik. Dia juga mencatat bahwa metode enumerasi implisit lainnya seperti pemrograman integer atau CSP (kendala kepuasan, diselesaikan melalui SAT) berkinerja lebih buruk dalam praktiknya.
Dia jelas menulis beberapa perangkat lunak untuk metodenya (disebut BESS), tetapi saya tidak yakin apakah itu tersedia untuk umum. Teks lengkap dari tesisnya tersedia secara bebas di umich . Dan memang Anda menemukan ekspresi minimal untuk 2-input xor (yang ke-2 jelas), yang disorot di bawah:
Dia juga membandingkan hasil yang pasti (untuk NAND) dengan yang dihasilkan oleh pengoptimal heuristik dari ABC .
Di sana (jelas) beberapa jaringan [lebih besar] yang belum selesai oleh BESS, tetapi memungkinkan batas atas dapat ditemukan (pada titik di mana pencarian ditinggalkan). Bagi mereka ABC melakukannya dengan sangat baik [baik sehubungan dengan batas-batas yang ditemukan], seperti yang dapat Anda lihat dari grafik ke-2 di bawah ini.
sumber
resyn2script. Jadi tidak lebih baik dari Logic Friday (yang menggunakan misII).Mungkin ada teknik yang lebih baik di luar sana, tetapi jauh ketika di zaman kegelapan, saya menemukan Karnaugh Maps berfungsi dengan baik
sumber
NAND diikuti oleh NAND sama dengan AND diikuti oleh OR.
NOR diikuti oleh NOR sama dengan OR diikuti oleh AND.
NAND diikuti oleh NOR akan sama dengan AND diikuti oleh AND yang tidak terlalu masuk akal. NOR diikuti oleh NAND juga akan sama dengan OR diikuti oleh OR.
Saya tidak percaya ada dalam kasus umum setiap cara yang layak untuk menemukan solusi minimal untuk masalah dengan sejumlah besar input (jelas untuk jumlah input kecil Anda dapat memaksa). Quine-McClusky hanya melihat dua level soloution (soloution minimal dua level sering bukan soloution minimal keseluruhan) dan dapat menjadi tidak layak secara komputasi dengan tabel kebenaran yang kompleks dan sejumlah besar input.
sumber
Algoritma terbaik adalah algoritma Espresso . Untuk tingkat tertentu ini diterapkan dalam sintesis FPGA
Logic friday adalah perangkat lunak yang dapat Anda gunakan. CATATAN: ini mengurangi XOR menjadi 5 gerbang NAND.
sumber