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

8

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.

HJLebbink
la source
Il n'existe même aucun moyen formel de "mapper" une fonction binaire arbitraire . Et toutes les fonctions binaires ne comprennent pas un système fonctionnel complet. Il en va de même pour le ternaire.
Eugene Sh.
1
Je crois que c'est NP difficile pour les fonctions binaires.
user110971
@ user110971 Je ne pense pas. Je pense que vous confondez avec le problème SAT.
Eugene Sh.
1
@EugeneSh. Je pense que le problème se réduit à la minimisation booléenne, qui est NP difficile, car sinon vous pourriez résoudre le problème SAT. C'est du moins ce que je pense que le PO demande.
user110971
2
@ user110971 Les algorithmes standard (que je suis au courant) ne réduisent pas arbitraire ternaires fonctions logiques (qui est la question). Ils se simplifient en NAND 3 pouces et en AND 3 pouces, mais pas toutes les autres fonctions logiques 3 pouces qui permettraient une réduction beaucoup plus compacte.
HJLebbink

Réponses:

4

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

F:Bool×Bool×BoolBool,
alors la valeur de vérité peut être trouvée pour chaque combinaison de valeurs d'entrée et stockée dans une table. Par exemple, si
F(une,b,c)=une&(!b|c),
puis
F(une,b,c)=STERNE101100002(une,b,c),
comme on peut le voir sur une table de vérité.
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 )

Pål-Kristian Engstad
la source
1
Vous dites que "les règles de conversion découlent facilement de la logique booléenne", j'ai donc essayé de construire un système de réécriture de termes (TRS) pour faire exactement cela. <br/> Le premier BF à 4 zones (du type le plus complexe) BF [100010110, 4] a une table de vérité: <br/> 0000 => 1 <br/> 0010 => 1 <br/> 0100 => 1 <br/> 1000 => 1 <br/> A'B'C'D + A'B'CD '+ A'BC'D' + AB'C'D '= BF [0xd1,3] (A, BF [0x16,3] (D, C, B), BF [0x02,3] (C, B, A)) Quelle est la plus petite réduction que j'ai pu trouver par la recherche par force brute. <br/> Ma question: Comment pourriez-vous réécrire cela (de manière inefficace), je ne vois pas comment les règles de conversion de la logique booléenne sont de toute aide ici.
HJLebbink
1
Après 6 minutes de lecture ce que vous ne pouvez pas éliminer même les non-très fonctionnelle <br/>
HJLebbink
1
Vous n'avez pas besoin de le réécrire. Faites simplement une évaluation par force brute pour chaque combinaison de valeurs de vérité.
Pål-Kristian Engstad
@engstad: ah j'ai finalement compris votre remarque: vous voulez dire quelque chose comme: BF [i, K] (a_0, ..., a_K) = BF [0xCA, 3] (a_0, BF [moitié supérieure (i), K-1 ] (a_1, ..., a_K), BF [moitié inférieure (i), K-1] (a_1, ..., a_K))
HJLebbink
2

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);
  1. 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.

HJLebbink
la source
1
Bonne utilisation d'ABC!
Pål-Kristian Engstad