Comment mapper une table de vérité aux fonctions logiques ternaires?

Veuillez être gentil. J'ai une question épineuse et importante d'un domaine différent de l'ingénierie dont la réponse peut être assez bien connue en génie électrique. J'ai posé une question similaire sur StackOverflow

Supposons que j'ai une table de vérité de 5 entrées et 1 sortie. J'ai utilisé l'algorithme Espresso (par exemple, Logic Friday) pour minimiser la table et écrire du VHDL efficace. Tout fonctionne bien.

Au lieu de minimiser et de mapper la table de vérité aux portes NAND, je voudrais mapper sur une fonction logique ternaire arbitraire. Je ne suis pas intéressé par la logique à valeurs multiples, mais par les fonctions logiques qui ont 3 variables d'entrée. Il existe 256 de ces fonctions, et la NAND 3-in n'est que l'une d'entre elles. Toutes ces 256 fonctions peuvent ne pas être intéressantes: certaines se réduisent à leurs 2 frères et sœurs variables d'entrée.

Question : comment pouvez-vous mapper une table de vérité (par exemple, avec 7 entrées) à l'une de ces fonctions 3-in. Un outil qui fait quelque chose de similaire serait formidable, mais une méthode sur la façon de simplifier les fonctions ternaires arbitraires serait la meilleure.

Contexte: les processeurs modernes peuvent effectuer des opérations logiques ternaires arbitraires sur des registres 512 bits (par exemple, l'instruction vpternlog ), mais en raison de la complexité, les compilateurs laissent le soin au programmeur, qui ne sait pas du tout comment l'optimiser.

Une analyse

Notez que l'instruction code toutes les fonctions ternaires possibles. Donc, étant donné les trois variables booléennes et les opérations binaires sur celles-ci, nous pouvons toujours trouver l'octet de codage. Par exemple, si on lui donne une fonction

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

Puisqu'il n'y a que 8 entrées à coder et seulement 2 résultats binaires, cela peut être codé comme un nombre à 8 bits, dans ce cas 0b10110000 = 0xB0.

Optimisations

Étant donné une fonction n -aire arbitraire de valeurs booléennes, tout ce que nous devons faire est de convertir les fonctions binaires en fonctions ternaires. Nous pouvons le faire, car nous savons que nous pouvons calculer n'importe quelle combinaison de fonctions. En partant d'un arbre de syntaxe abstraite de nœuds unaires et binaires, nous commencerions par représenter les fonctions unaires et binaires de la même manière que le "codage" ci-dessus.

Donc, pour notre f :

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

En utilisant une logique récursive, nous pouvons combiner BIN et UNARY en:

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

Qui peut ensuite être optimisé (les règles de conversion découlent facilement de la logique booléenne):

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

Observation

Ceci est très similaire à la façon dont les tables de recherche FPGA (LUT) sont calculées. Je suis sûr que vous pouvez trouver de nombreux textes et algorithmes pour mapper la logique aux LUT. Par exemple: Flow-map ( http://cadlab.cs.ucla.edu/~cong/papers/tcad94.pdf )

Extrait de ma propre réponse .

1. Traduire la table de vérité en une formule logique; utiliser par exemple, Logic Friday.
2. Stockez la formule logique au format d'équation Synopsys (.eqn).

Contenu de 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. Utilisez "ABC: Un système pour la synthèse séquentielle et la vérification" du Berkeley Verification and Synthesis Research Center.

Dans ABC, je lance:

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

Vous devrez peut-être exécuter choice; if -K 3; ps plusieurs fois pour obtenir de meilleurs résultats.

Le BF_Q6.bench résultant contient les 3-LUT pour un 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 )

Cela peut être réécrit (mécaniquement) dans le C ++ que je cherchais.