Comment convertir une logique à plusieurs valeurs en une logique booléenne efficace?

Question

Supposons que j'ai un ensemble S composé de {0₁, ¯1₂, 0₂, 1₂, ¯2₃, ¯1₃, 0₃, 1₃, 2₃, ¯3₄, ¯2₄, ¯1₄, 0₄, 1₄, 2₄, 3₄}. Je veux définir les opérations suivantes sur S:

• S < 0 qui retourne un si et seulement si S est négatif.
• ¯S qui renvoie la négation de S.
• S + 0 qui renvoie S plus zéro, qui est S inchangé.
• S + 1 qui renvoie la valeur absolue de S plus un, modulo l'indice. Par exemple:
  • Les deux ¯1₃ + 1 et 1₃ + 1 évaluent à 2₃.
  • Les deux ¯2₃ + 1 et 2₃ + 1 évaluent à 0₃. L'expression 0₃ + 1 est évaluée à 1₃.
• S ¢ 0 qui renvoie le carry de S + 0, qui est égal à zéro.
• S ¢ 1 qui renvoie le report de S + 1, qui est un si et seulement si S + 1 = 0ₙ pour n > 1.

Ces informations peuvent être capturées sous la forme d'une table de vérité:

S S<0 ¯S S+0 S+1 S¢0 S¢1 
┌───┬───┬───┬───┬───┬───┬───┐ 
│ 0₁│ 0 │ 0₁│ 0₁│ 0₁│ 0 │ 0 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│¯1₂│ 1 │ 1₂│¯1₂│ 0₂│ 0 │ 1 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│ 0₂│ 0 │ 0₂│ 0₂│ 1₂│ 0 │ 0 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│ 1₂│ 0 │¯1₂│ 1₂│ 0₂│ 0 │ 1 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│¯2₃│ 1 │ 2₃│¯2₃│ 0₃│ 0 │ 1 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│¯1₃│ 1 │ 1₃│¯1₃│ 2₃│ 0 │ 0 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│ 0₃│ 0 │ 0₃│ 0₃│ 1₃│ 0 │ 0 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│ 1₃│ 0 │¯1₃│ 1₃│ 2₃│ 0 │ 0 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│ 2₃│ 0 │¯2₃│ 2₃│ 0₃│ 0 │ 1 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│¯3₄│ 1 │ 3₄│¯3₄│ 0₄│ 0 │ 1 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│¯2₄│ 1 │ 2₄│¯2₄│ 3₄│ 0 │ 0 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│¯1₄│ 1 │ 1₄│¯1₄│ 2₄│ 0 │ 0 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│ 0₄│ 0 │ 0₄│ 0₄│ 1₄│ 0 │ 0 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│ 1₄│ 0 │¯1₄│ 1₄│ 2₄│ 0 │ 0 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│ 2₄│ 0 │¯2₄│ 2₄│ 3₄│ 0 │ 0 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│ 3₄│ 0 │¯3₄│ 3₄│ 0₄│ 0 │ 1 │ 
└───┴───┴───┴───┴───┴───┴───┘ 

Ce que je veux faire est de convertir cette table de vérité de valeurs multiples dans une table de vérité booléenne pour que je puisse mettre en œuvre la opérations utilisant des opérateurs au niveau du bit pour la parallélisation. Cela semble assez simple. Attribuez 0000 à 0₁, 0001 à ¯1₂, ..., 1111 à 3₄. Résolvez le résultat Karnaugh map pour obtenir une expression CNF ou DNF et appelez-le un jour. Malheureusement, les expressions CNF ou DNF résultantes peuvent ne pas être efficaces avec ce mappage naïf de S aux valeurs booléennes. Je veux trouver le moyen le plus efficace de représenter cette table de vérité à valeurs multiples comme une table de vérité booléenne. Ici, le moyen efficace consiste à utiliser le moins d'opérateurs pour mettre en œuvre les différentes opérations, en privilégiant l'addition, la négation, le report et la comparaison dans cet ordre. Cependant, le problème est qu'il existe 16! ou 20922789888000 façons de mapper S aux valeurs booléennes. Existe-t-il un meilleur moyen de trouver la solution que la force brute?

Answer 1

Je ne peux pas penser à une solution générale à ce problème, mais voici une solution spécifique à mon problème. Nous commençons par plonger l'ensemble S en deux ensembles disjoints, S₁ et S₂. L'ensemble S₁ contiendrait 0₁ et l'indice ₄ éléments.L'ensemble S₂ contiendrait les ₂ et l'indice ₃ éléments indice:

S₁ = {0₁, ¯3₄, ¯2₄, ¯1₄, 0₄, 1₄, 2₄, 3₄} 
S₂ = {¯1₂, 0₂, 1₂, ¯2₃, ¯1₃, 0₃, 1₃, 2₃} 
S = S₁ ∪ S₂ 

Maintenant, nous pouvons résoudre ce problème séparément pour S₁ et S₂. Cependant, nous voulons le faire de telle sorte que les solutions soient similaires. Ainsi, lorsque nous les combinons, nous pouvons tirer parti de la similarité pour réduire le nombre d'opérations impliquées. Voici la solution que je suis venu avec:

Il y a deux choses à noter au sujet de ma solution:

1. Tous les éléments nuls appartiennent à la colonne C'D'. Par conséquent, il est facile de sélectionner le reste des éléments en utilisant C+D. Cela vous sera utile plus tard.
2. Les éléments négatifs sont toujours dans la ligne B et dans la même colonne que les éléments positifs correspondants. Cela rend la négation et la vérification si négatif facile.

Quoi qu'il en soit, voici les opérations mises en œuvre à l'aide des opérateurs au niveau du bit où (A, B, C, D) ∈ S:

(A, B, C, D) < 0 = B (C + D) 

¯(A, B, C, D) = (A, B^(C + D), C, D) 

(A, B, C, D) + M = 
    E = C D 
    N = M' 
    (A, B N + M E, 
     C N + M (A^C^D^A E), 
     D N + M D' (B + C)) 

(A, B, C, D) ¢ M = M D (A + C) 

Le nombre d'opérations nécessaires pour l'addition, PORTER négation et la comparaison sont 18, 3, 2 et 2 respectivement. Notez que pour la négation, nous avons seulement besoin de modifier B et pour l'addition, nous n'avons pas besoin de modifier A. Common subexpression elimination et les opérations xor sont utilisées pour réduire les opérations.

Je ne sais pas s'il est possible de faire mieux que ça. C'est la meilleure solution que j'ai trouvée.