Membangun prosesor logika universal 2 arah menggunakan gerbang logika NAND

8

A 2-arah logika yang universal prosesor (2ULP) adalah jaringan gerbang logika yang mengambil dua kawat masukan Adan B, serta empat input lainnya L_, L_a, L_b, dan L_ab, dan menghasilkan satu output L(a, b)menggunakan empat Linput sebagai fungsi tabel kebenaran:

  • 2ULP mengembalikan L_jika Adan Bkeduanya 0.
  • Ia mengembalikan L_ajika A = 1dan B = 0.
  • Ia mengembalikan L_bjika A = 0dan B = 1.
  • Ia mengembalikan L_abjika Adan Bkeduanya 1.

Sebagai contoh, diberikan masukan L_ = 0, L_a = 1, L_b = 1, dan L_ab = 0, maka output L(a, b)akan sama dengan A xor B.

Tugas Anda adalah membangun 2ULP hanya menggunakan gerbang NAND, menggunakan sesedikit mungkin gerbang NAND. Untuk menyederhanakan hal-hal, Anda dapat menggunakan gerbang AND, ATAU, TIDAK, 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.

Sirkuit logika yang menggunakan gerbang NAND paling sedikit untuk menghasilkan konstruksi yang benar menang.

atomic-code-golf logic-gates Joe Z.
sumber
1
Keahlian desain logika digital saya sangat berkarat sehingga menggelikan, tetapi saya sangat menikmati hasil akhir dari kompetisi ini. +1
ProgrammerDan
Dengan gerbang NAND dua input, tidak ada banyak ruang untuk kreativitas dalam desain ini. Mungkin, alih-alih mengharuskan perangkat mengambil enam input, rancang blok dengan jumlah input dan satu output yang sewenang-wenang, dan mengharuskan diberikan dua input A dan B dan pilihan salah satu dari enam belas fungsi, harus mungkin untuk hubungkan input blok ke beberapa kombinasi A, B, Tinggi, dan Rendah, sehingga output akan menghasilkan fungsi itu. Perangkat seperti itu akan menjadi prosesor logika 2 arah yang universal (cukup tambahkan kabel), tetapi mungkin bisa dilakukan di banyak gerbang kurang dari 11.
supercat
1
Kita harus menciptakan gerbang-golf , tempat Anda menulis di gerbang dengan jumlah terkecil.
TheDoctor
Untuk itulah gerbang atom-kode-golf + logika .
Joe Z.

Jawaban:

10

11 NAND

Tentukan gerbang MUX (biaya 4) sebagai

MUX(P, Q, R) = (P NAND Q) NAND (NOT P NAND R)

dengan tabel kebenaran

P Q R    (P NAND Q)   (NOT P NAND R)    MUX
0 0 0        1               1           0
0 0 1        1               0           1
0 1 0        1               1           0
0 1 1        1               0           1
1 0 0        1               1           0
1 0 1        1               1           0
1 1 0        0               1           1
1 1 1        0               1           1

Maka ini adalah operator ternary yang akrab MUX(P, Q, R) = P ? Q : R

Kami hanya punya

2ULP = MUX(A, MUX(B, L_ab, L_a), MUX(B, L_b, L_))

dengan biaya 12, tetapi ada penghematan satu gerbang sepele dengan menggunakan kembali NOT Bdari dua MUXes dalam .

Peter Taylor
sumber
3
Anda baru saja memberi saya ide tentang sesuatu untuk dicoba dengan redstone di Minecraft, terima kasih
David Wilkins
1
Minimum absolut adalah 11 NAND. Saya mencari dengan seksama. Dan sirkuit tercepat yang saya temukan memiliki kedalaman 5 gerbang. Jadi teka-teki ini dipecahkan oleh Peter Taylor.
KimOyhus
3

biaya: 4 * 4 * 14 + 4 * (13) + 13 * 3 + 3 * 3 + 24 * 1 + 4 = 352

Saya bukan orang boolean, ini adalah yang terbaik dalam mengkode hal-hal ini (saya tahu ini tidak akan memberi saya banyak poin internet immaginary ..).

# l1 is for a=F , b=F
# l2 is for a=F , b=T
# l3 is for a=T , b=F
# l4 is for a=T , b=T

2ULP(l1,l2,l3,l4,a,b) =
 (l1&l2&l3&l4)|             # always true
 (!l1&l2&l3&l4)&(a|b)|      # a=F,b=F->F; ee in T
 (l1&!l2&l3&l4)&(!a&b)|     # a=F,b=T->F; ee in T
 (!l1&!l2&l3&l4)&(a)|       # a=F,b=F->F; a=F,b=T->F; a=T,b=F->T; a=T,b=T->T; 
 (l1&l2&!l3&l4)&(a&!b)|     # a=T,b=F->F, ee in T
 (!l1&l2&!l3&l4)&(b)|       # a=T,b=F->F, ee in T
 (!l1&!l2&!l3&l4)&(a&b)|    # a=T,b=T->T, ee in F
 (l1&l2&l3&!l4)&(!(a|b))|   # a=T,b=T->F, ee in T
 (!l1&l2&l3&!l4)&(!(avb))|  # a=T,b=F->T, a=F,b=T->T, ee in T , note v is the exor.
 (l1&!l2&l3&!l4)&(!b)|      # T when b=T
 (!l1&!l2&l3&!l4)&(a&!b)|   # T when a=T,b=F
 (l1&l2&!l3&!l4)&(!a)|      # T when a=F
 (!l1&l2&!l3&!l4)&(!a&b)|   # T when a=F,B=T
 (l1&!l2&!l3&!l4)&(!(a|b))  # T when a=F,B=F
Antonio Ragagnin
sumber
Jika Anda mengikuti sistem yang digariskan oleh poin-poin dalam pertanyaan maka Anda mendapatkan biaya 29, jadi ini sangat buruk.
Peter Taylor
Maaf Tuan Taylor, saya hanya berharap ini tidak merusak mata Anda.
Antonio Ragagnin
3

Dengan menggunakan bahasa Wolfram saya bisa mendapatkan formula 13 gerbang :

logicfunc = Function[{a, b, Ln, La, Lb, Lab},
                   {a, b, Ln, La, Lb, Lab} -> Switch[{a, b},
                          {0, 0}, Ln, {1, 0}, La, {0, 1}, Lb, {1, 1}, Lab]
                  ];
trueRuleTable = Flatten[Outer[logicfunc, ##]] & @@ ConstantArray[{0, 1}, 6] /. {0 -> False, 1 -> True};
BooleanFunction[trueRuleTable, {a, b, Ln, La, Lb, Lab}] // BooleanMinimize[#, "NAND"] &

yang keluaran:

Rumus NAND

Di sini Ln, La, Lbdan Labadalah L_, L_a, L_bdan L_absecara terpisah di OP.

sidenote: Hasil BooleanMinimizefungsi dalam bahasa Wolfram terbatas pada dua tingkat NANDdan NOTketika dipanggil sebagai BooleanMinimize[(*blabla*), "NAND"], jadi itu tidak sebagus rumus empat tingkat Peter Taylor di atas .

Silvia
sumber