Changes between Version 1 and Version 2 of CaoCourseTme6


Ignore:
Timestamp:
Mar 7, 2007, 6:58:28 PM (18 years ago)
Author:
alain
Comment:

--

Legend:

Unmodified
Added
Removed
Modified

  • CaoCourseTme6

    v1 v2  
     1{{{
     2#!html
     3<h1>TME 6 : Représentation des fonctions Boolèennes : ROBDD</h1>
     4}}}
     5[[PageOutline]]
     6
     7= Objectif =
     8
     9L'objectif principal de ce TME est de vous familiariser avec la représentation des fonctions Booléennes sous forme de ROBDD.
    110Les ROBDD (Reduced Ordered Binary Decision Diagram) sont utilisés pour représenter de façon compacte une ou plusieurs fonctions Booléennes, partageant le même support (c’est à dire dépendant d’un même ensemble de variables Booléennes). Pour un ordre donné des variables constituant le support, cette représentation est canonique : A chaque fonction Booléenne est associé un unique graphe orienté acyclique (DAG). Le graphe étant acyclique, chaque noeud BDD définit un sous-graphe dont il est la racine. Par conséquent, chaque noeud BDD correspond à une fonction Booléenne particulière. On utilise le fait que les variables Booléennes constituant le support sont ordonnées pour identifier ces variables par leur index.
    211
     12= A. Structures de données et fonctions de base =
     13
    314La structure C permettant de représenter un noeud du graphe ROBDD est  définie de la façon suivante :
     15{{{
     16typedef struct bdd_t {
     17        unsigned int            INDEX;
     18        struct bdd_t            *HIGH;
     19        struct bdd_t            *LOW;
     20} bdd_t
     21}}}
    422
    5 typedef struct bdd_t {
    6                 unsigned int            INDEX;
    7 struct bdd_t            *HIGH;
    8                 struct bdd_t            *LOW;
    9 } bdd_t
    1023
    11 Pour la gestion des variables, vous utiliserez les mêmes fonctions que celles vues lors du TME5. Vous trouverez ces fonctions dans les fichiers var.h et var.c.
     24Pour construire et visualiser le graphe ROBDD, on disposes des fonctions suivantes
     25{{{
     26extern bdd_t  *create_bdd(unsigned int index, bdd_t *high, bdd_t *low)
     27extern bdd_t  *apply_bdd(unsigned oper, bdd_t *p1, bdd_t *p2)
     28extern bdd_t  *not_bdd(bdd_t *p)
     29extern void   display_bdd(bdd_t *p)
     30}}}
    1231
     32 * La fonction '''create_bdd()''' gère un dictionnaire de tous les noeuds BDD déjà créés et fournit la garantie qu’il n’existera jamais deux noeuds BDD possédant les mêmes valeurs pour les champs INDEX, HIGH et LOW. La fonction create_bdd() recherche le noeud BDD possédant les valeurs définies par les arguments, et renvoie un pointeur sur le noeud BDD correspondant. Si ce noeud n’existe pas, cette fonction crée un nouveau noeud dans le dictionnaire, en affectant la valeur index au champs INDEX, la valeur high au champs HIGH, et la valeur low au champs LOW.
     33 * La fonction '''apply_bdd()''' prend pour arguments un entier définissant un opérateur Booléen (les valeurs possibles sont OR, AND, et XOR), deux pointeurs p1 et p2 sur deux noeuds BDD représentant deux fonctions Booléennes F1 et F2 (notons que les deux fonctions F1 et F2 ne dépendent pas forcément de toutes les variables Booléennes définies dans le support global). La fonction apply_bdd() construit le graphe ROBDD représentant la fonction F = F1 oper F2, et renvoie un pointeur sur le noeud ROBDD racine de ce graphe.
     34 * La fonction '''not_bdd()''' prend pour unique argument un pointeur p sur un noeud BDD représentant une fonction Booléenne F, et renvoie un pointeur sur le noeud BDD représentant la fonction Booléenne NOT( F).
     35 * La fonction '''display_bdd()''' prend pour unique argument un pointeur p sur un noeud BDD représentant une fonction Booléenne F, et affiche sur le terminal standard l’ensemble des noeuds BDD qui interviennent dans le graphe ROBDD représentant F. Il y a un noeud BDD par ligne, et chaque noeud BDD est décrit par quatre entiers :
     36   * N représente un numéro identifiant le noeud BDD
     37   * H représente le numéro du noeud BDD représentant le cofacteur HIGH.
     38   * L représente le numéro du noeud BDD représentant le cofacteur LOW.
     39   * X représente l’INDEX de la variable associée au noeud BDD
     40
     41Pour la représentation des variables, vous utiliserez les mêmes fonctions que celles utilisées lors du TME5.
     42{{{
    1343typedef struct var_t{
    1444                char *NAME;
    … …  
    1747} var_t;
    1848
    19 - extern var_t *cons_var (char *name, unsigned index, unsigned value);
    20         - extern var_t *get_var_index (unsigned index);
    21 - extern var_t *get_var_name (char *name);
     49extern var_t *cons_var (char *name, unsigned index, unsigned value);
     50extern var_t *get_var_index (unsigned index);
     51extern var_t *get_var_name (char *name);
     52}}}
    2253
    23 
    24 Pour la gestion de la structure bdd, vous trouverez la déclaration des types et des fonctions dans les fichiers bdd.h et  bdd.c. En particulier :
    25 
    26 - extern bdd_t  *create_bdd(unsigned int index, bdd_t *high, bdd_t *low)
    27 
    28 Cette fonction gère un dictionnaire de tous les noeuds BDD déjà créés et fournit la garantie qu’il n’existera jamais deux noeuds BDD possédant les mêmes valeurs pour les champs INDEX, HIGH et LOW. La fonction create_bdd() recherche le noeud BDD possédant les valeurs définies par les arguments, et renvoie un pointeur sur le noeud BDD correspondant. Si ce noeud n’existe pas, cette fonction crée un nouveau noeud dans le dictionnaire, en affectant la valeur index au champs INDEX, la valeur high au champs HIGH, et la valeur low au champs LOW.
    29 
    30 - extern bdd_t  *apply_bdd(unsigned oper, bdd_t *p1, bdd_t *p2)
    31 
    32 Cette fonction prend pour arguments un entier définissant un opérateur Booléen (les valeurs possibles sont OR, AND, et XOR), deux pointeurs p1 et p2 sur deux noeuds BDD représentant deux fonctions Booléennes F1 et F2 (notons que les deux fonctions F1 et F2 ne dépendent pas forcément de toutes les variables Booléennes définies dans le support global). La fonction apply_bdd() construit le graphe ROBDD représentant la fonction F = F1 oper F2, et renvoie un pointeur sur le noeud ROBDD racine de ce graphe.
    33 
    34 - extern bdd_t  *not_bdd(bdd_t *p)
    35 
    36 La fonction not_bdd() prend pour unique argument un pointeur p sur un noeud BDD représentant une fonction Booléenne F, et renvoie un pointeur sur le noeud BDD représentant la fonction Booléenne NOT( F).
    37 
    38 - extern void display_bdd(bdd_t *p)
    39 
    40 Cette fonction prend pour unique argument un pointeur p sur un noeud BDD représentant une fonction Booléenne F, et affiche sur le terminal standard l’ensemble dHes noeuds BDD qui interviennent dans le graphe ROBDD représentant F. Il y a un noeud BDD par ligne, et chaque noeud BDD est décrit par quatre entiers :
    41 - N représente un numéro identifiant le noeud BDD
    42 - H représente le numéro du noeud BDD représentant le cofacteur HIGH.
    43 - L représente le numéro du noeud BDD représentant le cofacteur LOW.
    44 - X représente l’INDEX de la variable associée au noeud BDD
    45 
    46 A/  Représentation Graphique
     54= B.  Représentation Graphique =
    4755
    4856Soit la fonction Booléenne F(a,b,c,d,e), définie par l’expression suivante
    4957
    50 E0 = (a’ . (b + c + d’) . e) + c                La notation a’ signifie NOT(a).
     58E0 = (a’ . (b + c + d’) . e) + c               
     59
     60La notation a’ signifie NOT(a).
    5161
    5262E0 peut se re-écrire sous forme préfixée de la façon suivante :
    … …  
    5464E0 = OR( AND (NOT (a) OR (b c NOT (d) e) c)
    5565
    56 A.1) En utilisant la décomposition de Shannon, représentez graphiquement le graphe ROBDD associé à la fonction F(a,b,c,d,e) pour l’ordre a > b > c > d > e , puis pour l’ordre e > d > c > b > a.
     66'''B.1''' En utilisant la décomposition de Shannon, représentez graphiquement le graphe ROBDD associé à la fonction F(a,b,c,d,e) pour l’ordre a > b > c > d > e , puis pour l’ordre e > d > c > b > a.
    5767
    58 A.2) Précisez, pour chaque noeud du ROBDD ainsi construit, quelle est la fonction Booléenne représentée par ce noeud.
     68'''B.2''' Précisez, pour chaque noeud du ROBDD ainsi construit, quelle est la fonction Booléenne représentée par ce noeud.
    5969
    60 
    61 B/ Fonctions notbdd() et applybdd()
     70= C. Fonctions not_bdd() et apply_bdd() =
    6271
    6372Les fonctions apply_bdd() et not_bdd() ont été présentées en cours. Vous trouverez le code de ces fonctions dans le fichier bdd.c.
    6473
    65 B.1) Démontrer la relation de récurrence entre la fonction Booléenne NOT(F) et les fonctions Booléennes NOT(FH) et NOT(FL), où les fonctions Booléennes FH et FL sont les cofacteurs de Shannon de la fonction F, décomposée suivant la variable x : 
     74'''C.1''' Soient F1 et F2 deux fonctions Booléennes, et les fonctions F1H, F1L, F2H, F2L définies par la décomposition de Shannon suivant la variable x :
     75 * F1 = x . F1H + x’ . F1L
     76 * F2 = x . F2H + x’ . F2L [[BR]]
     77La relation de recurrence  (F1 op F2) = x . (F1H op F2H) +  x’. (F1L op F2L)
     78a été démontrée en cours dans le cas des opérateurs OR et AND. Démontrez que cette relation est vraie dans le cas d’un opérateur XOR. Analysez le cas général, ainsi que les cas particuliers où l’une des deux fonctions F1 ou F2 est égale à une des deux fonctions constantes 0 ou 1.
    6679
    67 • F = x . FH + x’ . FL
     80'''C.2''' Soit la fonction F, définie par l’expression E1 =  a . (b + c)
     81Représentez graphiquement le ROBDD représentant la fonction F, pour l’ordre des variables a > b > c. On appelle p0, p1, p2, p3, p4 les pointeurs sur les 5 noeuds BDD contenus dans ce graphe :
     82 * p0 représente la fonction F0 = 0
     83 * p1 représente la fonction F1 = 1
     84 * p2 représente la fonction F2 = c
     85 * p3 représente la fonction F3 = b + c
     86 * p4 représente la fonction F4 = a . (b + c) [[BR]]
     87Représentez graphiquement l’arbre d’appels des fonctions lorsqu’on appelle la fonction not_bdd() avec pour argument le pointeur p4. Quel est le nombre maximum d’appels de fonctions empilés sur la pile d’exécution? Combien de noeuds BDD vont être créés par la fonction create_bdd(), si on suppose que la structure de données ne contient initialement que les 5 noeuds pointés par p0, p1, p2, p3, et p4 au moment de l’appel de la fonction not_bdd(p4)?
    6888
    69 B.2) Soit la fonction F, définie par l’expression E1 =  a . (b + c)
    70 Représentez graphiquement le ROBDD représentant la fonction F, pour l’ordre des variables a > b > c. On appelle p0, p1, p2, p3, p4 les pointeurs sur les 5 noeuds BDD contenus dans ce graphe :
    71 • p0 représente la fonction F0 = 0
    72 • p1 représente la fonction F1 = 1
    73 • p2 représente la fonction F2 = c
    74 • p3 représente la fonction F3 = b + c
    75 • p4 représente la fonction F4 = a . (b + c)
    76 Représentez graphiquement l’arbre d’appels des fonctions lorsqu’on appelle la fonction not_bdd() avec pour argument le pointeur p4. Quel est le nombre maximum d’appels de fonctions empilés sur la pile d’exécution? Combien de noeuds BDD vont être créés par la fonction create_bdd(), si on suppose que la structure de données ne contient initialement que les 5 noeuds pointés par p0, p1, p2, p3, et p4 au moment de l’appel de la fonction not_bdd(p4).
    77 
    78 B.3) Soient F1 et F2 deux fonctions Booléennes, et les fonctions F1H, F1L, F2H, F2L définies par la décomposition de Shannon suivant la variable x :
    79 • F1 = x . F1H + x’ . F1L
    80 • F2 = x . F2H + x’ . F2L
    81 
    82 La relation de recurrence
    83 • (F1 op F2) = x . (F1H op F2H) +  x’. (F1L op F2L)
    84 a été démontrée en cours dans le cas des opérateurs OR et AND. Démontrez que cette relation est vraie dans le cas d’un opérateur XOR. Analysez le cas général, ainsi que les quatre cas particuliers où l’une des deux fonctions F1 ou F2 est égale à une des deux fonctions constantes 0 ou 1.
    85 
    86 C/ Fonction abl2bdd()
     89= D. Fonction abl2bdd() =
    8790
    8891On cherche à écrire la fonction abl2bdd(), qui construit automatiquement le graphe ROBDD représentant une fonction Booléenne F, à partir d’un arbre ABL représentant une expression Booléenne particulière de cette fonction F.
     92{{{
     93bdd_t *abl2bdd(bip_t *p)
     94}}}
     95Cette fonction prend comme unique argument un pointeur sur la racine d’un arbre ABL, et renvoie un pointeur sur le noeud BDD représentant la fonction. Puisque les arbres ABL ne contiennent que des opérateurs OR, AND, XOR et NOT, et qu’on dispose des fonctions apply_bdd() et not_bdd(), il est possible de construire le graphe ROBDD par application récursive de ces deux fonctions.
    8996
    90 - bdd_t *abl2bdd(bip_t *p)
     97'''D.1''' Décrire en français, l’algorithme récursif de cette fonction abl2bdd() dans le cas particulier où tous les opérandes AND, OR ou XOR présents dans l’arbre ABL n’ont que deux opérandes,
    9198
    92 Cette fonction prend comme unique argument un pointeur sur la racine d’un arbre ABL, et renvoie un pointeur sur le noeud BDD représentant la fonction.
    93 Puisque les arbres ABL ne contiennent que des opérateurs OR, AND, XOR et NOT, et qu’on dispose des fonctions apply_bdd() et not_bdd(), il est possible de construire le graphe ROBDD par application récursive de ces deux fonctions.
     99'''D.2''' Ecrire en langage C la fonction abl2bdd() dans le cas particulier de la question  précédente.
     100Pour valider cette fonction, on écrira un programme main(), qui effectue successivement les opérations suivantes :
     101 * déclaration et indexation de toutes les variables Booléennes,
     102 * construction de l’arbre ABL  représentant l’expression E1, avec la fonction parse_abl(),
     103 * affichage de cette expression Booléenne, avec la fonction display_abl(), pour vérifier que l’arbre ABL est correctement construit,
     104 * construction du graphe ROBDD représentant la fonction F, avec la fonction abl2bdd(),
     105 * affichage du graphe ROBDD ainsi construit, en utilisant la fonction display_bdd().
    94106
    95 C1) Décrire en français, l’algorithme récursif de cette fonction abl2bdd() dans le cas particulier où tous les opérandes AND, OR ou XOR présents dans l’arbre ABL n’ont que deux opérandes,
    96 
    97 C.2) Ecrire en langage C la fonction abl2bdd().
    98 Pour valider cette fonction, on écrira un programme main(), qui effectue successivement les opérations suivantes :
    99 • déclaration et indexation de toutes les variables Booléennes (var.h).
    100 • construction explicite de l’arbre ABL  représentant l’expression E1, avec la fonction parse_abl() (parse_abl.h),
    101 • affichage de cette expression Booléenne, avec le fonction display_abl(), pour vérifier que l’arbre ABL est correctement construit (bip.h),
    102 • construction du graphe ROBDD représentant la fonction F, avec la fonction abl2bdd(),
    103 • affichage du graphe ROBDD ainsi construit, en utilisant la fonction display_bdd().
    104 
    105 C.3) Comment faut-il modifier la fonction abl2bdd(), pour traiter le cas général, où les opérateurs OR, AND et XOR peuvent avoir une arité quelconque?
     107'''D.3''' Comment faut-il modifier la fonction abl2bdd(), pour traiter le cas général, où les opérateurs OR, AND et XOR peuvent avoir une arité quelconque?
    106108Modifier le code de la fonction, et validez ces modifications sur l’exemple de l’expression Booléenne E0, ou sur des expressions encore plus complexes.
    107109
    108 D/ Fonction satisfybdd()
     110= E. Fonction satisfybdd() =
    109111
    110 Soit une fonction Booléenne quelconque F(x1, x2, x3, ... xn), dépendant de n variables. Soit la fonction Booléenne G, définie comme un produit (opérateur AND) d’un nombre queconque de variables xi (directes ou complémentées). On dit que G “satisfait” F si G => F. (Autrement dit, si G = 1, alors F = 1). Remarquez que la condition G = 1 impose la valeur de toutes les variables appartenant au support de G (les variables directes doivent prendre la valeur 1, et les variables complémentées doivent prendre la valeur 0). Pour une fonction F donnée, la fonction G n’est évidemment pas unique...
     112Soit une fonction Booléenne quelconque F(x1, x2, x3, ... xn), dépendant de n variables. Soit la fonction Booléenne G, définie comme un produit (opérateur AND) d’un nombre queconque de variables xi (directes ou complémentées). On dit que G “satisfait” F sion a la relation G => F. (Autrement dit, si G = 1, alors F = 1). Remarquez que la condition G = 1 impose la valeur de toutes les variables appartenant au support de G (les variables directes doivent prendre la valeur 1, et les variables complémentées doivent prendre la valeur 0). Pour une fonction F donnée, il existe évidemment plusieurs
     113fonction G qui satisfont F...
    111114
    112115Exemple : F = (a . b) + c
    … …  
    116119ou encore               G = a . b . c’
    117120
    118 Dans la suite de cet exercice, on cherche à écrire une fonction C qui construit automatiquement le ROBDD représentant une fonction G satisfaisant une fronction F quelconque. Comme il existe plusieurs solutions, on choisira la systématiquement la solution qui minimise le nombre de variable xi dans le produit.
    119 
    120 - bdd_t *satisfy_bdd(bdd_t *p)
    121 
     121Dans la suite de cet exercice, on cherche à écrire une fonction C qui construit automatiquement le ROBDD représentant une fonction G satisfaisant une fronction F quelconque. Comme il existe plusieurs solutions, on choisira la systématiquement la solution qui minimise le nombre de variable xi dans le support de G.
     122{{{
     123bdd_t *satisfy_bdd(bdd_t *p)
     124}}}
    122125La fonction satisfy_bdd() prend pour argument un pointeur sur le noeud BDD représentant la fonction F et renvoie un un pointeur sur le noeud BDD représentant la fonction G.
    123126
    124 D.1) La décomposition de Shannon de la fonction F suivant la variable x d’index le plus élévé définit les cofacteurs FH et FL :
    125 
    126 • F = x . FH + x’ . FL
    127 
     127'''E.1''' La décomposition de Shannon de la fonction F suivant la variable x d’index le plus élévé définit les cofacteurs FH et FL : F = x . FH + x’ . FL
    128128Pour alléger les notations, on note sat(F) la fonction Booléenne construite par la fonction satisfy_bdd() pour la fonction F.
    129129Donner la relation de récurrence entre les fonctions  sat(F), sat (FH), et sat(FL). On étudiera successivement le cas général où ni FH et FL ne sont constantes, et les quatre cas particuliers où l’une des deux fonctions FH ou FL sont égales à 0 ou 1.
    130130
    131 D.2) Ecrire, en langage C, le code de la fonction satisfy_bdd(), et appliquez-la sur la fonction Booléenne F définie dans la partie A de l’énoncé, en modifiant le programme main de la fonction précédente.
     131'''E.2''' Ecrire, en langage C, le code de la fonction satisfy_bdd(), et appliquez-la sur la fonction Booléenne F définie dans la partie, en modifiant le programme main de la fonction précédente.
    132132
    133 E/ Fonction bdd2abl()
     133= F. Fonction bdd2abl() =
    134134
    135 On souhaite pour finir écrire la fonction bdd2abl(), qui construit automatiquement l’arbre ABL représentant une expression Booléenne multi-niveaux, pour une fonction Booléenne représentée par un ROBDD.
    136 
    137 - bip_t *bdd2abl(bdd_t *p)
    138 
     135On souhaite pour finir écrire la fonction bdd2abl(), qui construit automatiquement un arbre ABL représentant une expression Booléenne multi-niveaux, à partir d'un ROBDD représentant une fonction Booléenne.
     136{{{
     137bip_t *bdd2abl(bdd_t *p)
     138}}}
    139139Cette fonction prend comme unique argument un pointeur sur un noeud BDD, et renvoie un pointeur sur le bipointeur représentant la racine de l’arbre ABL représentant l’expression Booléenne.
    140140
    141 E.1) Il existe évidemment un grand nombre d’expressions Booléennes équivalentes pour une même fonction Booléenne. Dans un premier temps, nous nous contenterons d’utiliser des opérateurs OR, et AND à deux opérandes, ainsi que l’opérateur NOT.
     141Il existe évidemment un grand nombre d’expressions Booléennes équivalentes pour une même fonction Booléenne. Dans un premier temps, nous nous contenterons d’utiliser des opérateurs OR, et AND à deux opérandes, ainsi que l’opérateur NOT.
    142142Soit un noeud BDD représentant une fonction Booléenne F. Soient x la variable associée à ce noeud BDD, FH et FL les fonctions Booléennes associées aux noeuds BDD pointés par les pointeurs HIGH et LOW (cofacteurs de Shannon).
    143 - Quelle expression Booléenne dépendant de x, FH et FL peut-on associer à la fonction F dans le cas général ou FH et FL sont quelconques ? (aucune des deux fonctions FH ou FL n’est égale à 0 ou à 1)
    144 - Comment cette expression Booléenne se simplifie-t-elle lorsque l’une des deux fonctions FH ou FL est égale à 0 ou à 1. Etudierv un par un les différents cas.
    145143
    146 E.2) En utilisant les résultats de la question E.1, proposez un algorithme de construction de l’arbre ABL
     144'''F.1''' Quelle expression Booléenne dépendant de x, FH et FL peut-on associer à la fonction F dans le cas général ou FH et FL sont quelconques ? (aucune des deux fonctions FH ou FL n’est égale à 0 ou à 1)
    147145
    148 E.3) Ecrire en langage C la fonction bdd2abl(), et validez-la sur différents exemples, en utilisant la fonction display_abl().
     146'''F.2''' Comment cette expression Booléenne se simplifie-t-elle lorsque l’une des deux fonctions FH ou FL est égale à 0 ou à 1. Etudier un par un les 4 cas particuliers.
     147
     148'''F.3''' En utilisant les résultats des questions précédentes, proposez un algorithme de construction de l’arbre ABL
     149
     150'''F.4''' Ecrire en langage C la fonction bdd2abl(), et validez-la sur différents exemples, en utilisant la fonction display_abl().
     151
     152= Compte-Rendu =
     153
     154Il ne vous est pas demandé de compte-rendu écrit pour ce TME, mais vous devrez faire une démonstration
     155de votre code au début du prochain TME.
    149156