Bagaimana cara memetakan tabel kebenaran ke fungsi logis ternary?

Mohon berbaik hati. Saya punya pertanyaan pelik dan penting dari bidang teknik yang berbeda yang jawabannya mungkin cukup terkenal di bidang teknik listrik. Saya mengajukan pertanyaan serupa di StackOverflow

Misalkan saya memiliki tabel kebenaran 5 input dan 1 output. Saya menggunakan algoritma Espresso (misalnya, Logic Friday) untuk meminimalkan tabel dan menulis beberapa VHDL yang efisien. Semuanya bekerja dengan baik.

Alih-alih meminimalkan dan memetakan tabel kebenaran ke gerbang NAND, saya ingin memetakan ke fungsi logis ternary sewenang-wenang. Saya tidak tertarik pada logika multi-nilai, tetapi pada fungsi logis yang memiliki 3 variabel input. Ada 256 fungsi ini, dan NAND 3-in hanyalah salah satunya. Tidak semua fungsi 256 ini mungkin menarik: beberapa mengurangi ke 2 saudara variabel input mereka.

Pertanyaan : bagaimana Anda bisa memetakan tabel kebenaran (mis., Dengan 7 input) ke salah satu dari fungsi 3-in ini. Alat yang melakukan hal serupa akan bagus, tetapi metode tentang cara menyederhanakan fungsi ternary sewenang-wenang adalah yang terbaik.

Latar Belakang: CPU modern dapat melakukan operasi logika ternary sewenang-wenang pada register 512-bit (mis., Instruksi vpternlog ), tetapi karena kerumitan, kompiler menyerahkannya kepada programmer, yang agak tidak mengerti tentang bagaimana mengoptimalkan ini.

Analisis

Perhatikan bahwa instruksi ini mengkode semua fungsi terner yang mungkin. Jadi, mengingat tiga variabel boolean dan operasi bit-bijaksana pada mereka, kita selalu dapat menemukan byte encoding. Misalnya, jika diberi fungsi

a b c | f
------+--
0 0 0 | 0
0 0 1 | 0
0 1 0 | 0
0 1 1 | 0
1 0 0 | 1
1 0 1 | 1
1 1 0 | 0
1 1 1 | 1

Karena hanya ada 8 input untuk penyandian dan hanya 2 hasil biner, ini dapat dikodekan sebagai angka 8-bit, dalam hal ini 0b10110000 = 0xB0.

Optimalisasi

Dengan fungsi n -ary sembarang dari nilai boolean, yang perlu kita lakukan adalah mengubah fungsi biner menjadi fungsi ternary. Kita dapat melakukan ini, karena kita tahu bahwa kita dapat menghitung kombinasi fungsi apa pun. Mulai dari pohon sintaksis abstrak dari node unary dan binary, kita akan mulai dengan merepresentasikan fungsi unary dan binary dengan cara yang mirip dengan "encoding" di atas.

Jadi, untuk f kami :

f = AND(a, OR(NOT(b), c)) = BIN[1000](a, BIN[1110](UNARY[10](b), c))

Dengan menggunakan logika rekursif, kita dapat menggabungkan BIN dan UNARY menjadi:

f = AND(a, OR(NOT(b), c)) = BIN[1000](a, BIN[1011](b, c))

Yang kemudian dapat dioptimalkan menjadi (aturan konversi mengikuti dengan mudah dari logika boolean):

f = AND(a, OR(NOT(b), c)) = TERN[10110000](a, b, c)

Pengamatan

Ini sangat mirip dengan bagaimana tabel pencarian FPGA (LUT) dihitung. Saya cukup yakin Anda dapat menemukan banyak teks dan algoritma untuk pemetaan logika ke LUT. Misalnya: Flow-map ( http://cadlab.cs.ucla.edu/~cong/papers/tcad94.pdf )

Kutipan dari jawaban saya sendiri .

1. Terjemahkan tabel kebenaran ke dalam formula logis; gunakan mis., Logic Friday.
2. Simpan rumus logis dalam format persamaan Synopsys (.eqn).

Konten BF_Q6.eqn:

INORDER = A B C D E F; 
OUTORDER = F0 F1;
F0 = (!A*!B*!C*!D*!E*F) + (!A*!B*!C*!D*E*!F) + (!A*!B*!C*D*!E*!F) + (!A*!B*C*!D*!E*!F) + (!A*B*!C*!D*!E*!F) + (A*!B*!C*!D*!E*!F);
F1 = (!A*!B*!C*!D*E) + (!A*!B*!C*D*!E) + (!A*!B*C*!D*!E) + (!A*B*!C*!D*!E) + (A*!B*!C*!D*!E);

3. Gunakan "ABC: Sistem untuk Sintesis dan Verifikasi Sekuensial" dari Pusat Penelitian Verifikasi dan Sintesis Berkeley.

Di ABC saya jalankan:

abc 01> read_eqn BF_Q6.eqn
abc 02> choice; if -K 3; ps
abc 03> lutpack -N 3 -S 3; ps
abc 04> show
abc 05> write_bench BF_Q6.bench

Anda mungkin harus berlari choice; if -K 3; ps banyak waktu untuk mendapatkan hasil yang lebih baik.

BF_Q6.bench yang dihasilkan berisi 3-LUT untuk FPGA:

INPUT(A)
INPUT(B)
INPUT(C)
INPUT(D)
INPUT(E)
INPUT(F)
OUTPUT(F0)
OUTPUT(F1)
n11         = LUT 0x01 ( B, C, D )
n12         = LUT 0x1 ( A, E )
n14         = LUT 0x9 ( A, E )
n16         = LUT 0xe9 ( B, C, D )
n18         = LUT 0x2 ( n11, n14 )
F1          = LUT 0xae ( n18, n12, n16 )
n21         = LUT 0xd9 ( F, n11, n14 )
n22         = LUT 0xd9 ( F, n12, n16 )
F0          = LUT 0x95 ( F, n21, n22 )

Ini dapat ditulis ulang (secara mekanis) ke C ++ yang saya cari.