npn

NPN: Hitung perwakilan kanonik untuk fungsi Boolean

Paket ini adalah pencocokan Boolean. Ini hanya menghitung perwakilan kanonik, yang unik untuk setiap kelas kesetaraan NPN, untuk fungsi boolean yang diberikan yang diwakili oleh tabel kebenaran.

Backend dari paket ini diimplementasikan oleh C ++ untuk efisiensi.

Saat ini, paket ini mendukung fungsi boolean dengan jumlah input <= 8.

Memasang

pip install npn

Penggunaan

 import npn

# the truth table of f(x_2, x_1, x_0) as [f(0, 0, 0), f(0, 0, 1), f(0, 1, 0), f(0, 1, 1), ...]
tt = [ True , True , True , False , True , True , True , True ]
c = npn . npn_canonical_representative ( tt )    # [True, True, True, True, True, True, True, False]
c_int = npn . tt_to_int ( c )                    # 254 (11111110)
c , phase , perm , output_inv = npn . npn_canonical_representative ( tt , return_details = True , refinement = True )

• Setel parameter return_details ke True untuk mengembalikan informasi transformasi npn ( phase, perm, output_inv ). Misalnya, di sini phase = [False, False, True] , perm = [0, 1, 2] dan output_inv = False mean (x_0, x_1, x_2) harus dipetakan ke (x_0, x_1, x_2) , maka variabel ketiga ( x_2 ) harus dibalik dan hasil akhir tidak boleh dibalik.
• Tetapkan parameter refinement menjadi True untuk mempercepat perhitungan sambil melanggar urutan leksikografi tabel kebenaran. Lihat "Membangun Detektor Pencocokan dan Simetri Boolean yang Lebih Baik" untuk detailnya.

Membangun

Kompilasi perpustakaan bersama libnpn.dll dan libnpn.so melalui cmake di lingkungan windows dan linux, letakkan di folder npn , lalu

python setup.py sdist

Untuk mengunggah ke pypi, jalankan

twine upload . d ist n pn-X.X.tar.gz

Tes

pip install pytest  # if you haven't install it
python -m pytest

Referensi

1. Chai, D., dan A. Kuehlmann. “Membangun Detektor Pencocokan dan Simetri Boolean yang Lebih Baik.” Dalam Prosiding Otomasi & Tes Desain di Konferensi Eropa, 1: 1–6, 2006. https://doi.org/10.1109/date.2006.243959.
2. Debnath, D., dan T. Sasao. "Perhitungan bentuk kanonik yang efisien untuk pencocokan boolean di perpustakaan besar." Dalam ASP-DAC 2004: Asia dan Konferensi Otomasi Desain Pasifik Selatan 2004 (IEEE Cat. No.04ex753), 591–96, 2004. Https://doi.org/10.1109/aspdac.2004.1337660.
3. Hinsberger, U., dan R. Kolla. "Pencocokan boolean untuk perpustakaan besar." Dalam Prosiding Konferensi Desain dan Otomasi 1998. DAC ke -35. (Cat. No.98CH36175), 206–11, 1998. Https://doi.org/10.1145/277044.277100.