npn

NPN: calculer les représentants canoniques pour les fonctions booléennes

Ce package est un correspondant booléen. Il calcule simplement le représentant canonique, qui est unique pour chaque classe d'équivalence NPN, pour une fonction booléenne donnée représentée par la table de vérité.

Le backend de ce package est implémenté par C ++ pour l'efficacité.

Actuellement, ce package prend en charge les fonctions booléennes avec le nombre d'entrées <= 8.

Installer

pip install npn

Usage

 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 )

• Définissez le paramètre return_details sur True pour renvoyer les informations de transformation NPN ( phase, perm, output_inv ). Par exemple, ici phase = [False, False, True] , perm = [0, 1, 2] et output_inv = False signifie (x_0, x_1, x_2) doit être mappé à (x_0, x_1, x_2) , alors la troisième variable ( x_2 ) doit être inversée et le résultat final ne doit pas être inversé.
• Définissez le paramètre refinement sur True à l'accélération du calcul tout en brisant l'ordre lexicographique des tables de vérité. Voir «Construire un meilleur matchur booléen et détecteur de symétrie» pour plus de détails.

Construire

Compilez la bibliothèque partagée libnpn.dll et libnpn.so via Cmake sur Windows et Linux Environment, placez-les dans le dossier npn , puis

python setup.py sdist

Pour télécharger sur PYPI, courez

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

Test

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

Références

1. Chai, D. et A. Kuehlmann. "Construire un meilleur matchur booléen et un détecteur de symétrie." Dans Proceedings of the Design Automation & Test in Europe Conference, 1: 1–6, 2006. https://doi.org/10.1109/date.2006.243959.
2. Debnath, D. et T. Sasao. «Computation efficace de la forme canonique pour la correspondance booléenne dans les grandes bibliothèques.» Dans ASP-DAC 2004: Asia and South Pacific Design Automation Conference 2004 (IEEE Cat. No.04EX753), 591–96, 2004. https://doi.org/10.1109/aspdac.2004.1337660.
3. Hinsberger, U., et R. Kolla. "Booléen Matching pour les grandes bibliothèques." Dans Actes 1998 Conférence de conception et d'automatisation. 35e DAC. (Cat. No.98ch36175), 206–11, 1998. Https://doi.org/10.1145/277044.277100.