Factorisation des fonctions logiques
Présentation au sujet: “Factorisation des fonctions logiques”— Transcription de la présentation:
1 Factorisation des fonctions logiques
2 Effet de la factorisation
3 Produit algébrique
4 Division algébrique
5 Division algébrique vs division booléenne
6 Expression libre
7 Noyau
8 Gain associé à un noyau
9 Factorisation d’une fonction simple – Algorithme 1
10 Factorisation d’une fonction simple – Algorithme 1
11 Factorisation d’une fonction simple – Algorithme 2
12 Factorisation des fonctions multiples
13 Recherche de noyaux ou parties de noyaux communs
14 Recherche de noyaux ou parties de noyaux communs
15 Gain associé à un noyau commun ou partie commune
16 Recherche de monômes ou parties de monômes communes
17 Gain associé
18 Algorithme général de factorisation des fonctions multiples
19 Exemple
20 Exemple
21 Exemple 1 – Noyaux de chaque fonction Noyau de F1: Aucun
22 Décomposition technologique – niveau portes
23 Décomposition technologique (Technology Mapping)
24 Equations Optimisées F t4’ F t5’ t3 t1t3 + fgh at2 +c t4h + t2t3 t1 t2
25 Bibliothèque
26 Approche algorithmique
27 Graphe sujet représenté en opérateurs NAND2 et NOT F F
28 Exemple de bibliothèque : graphes formes
29 Approche algorithmique
30 Graphe Sujet f g d F e h b a c t1 = d + e; t2 = b + h; t3 = at2 + c;
31 Couverture du graphe sujet
32 Une autre couverture (meilleure)
33 Une autre couverture (encore meilleure)
34 Technology mapping par couverture
35 Résolution
36 Cas général => problème de satisfiabilité
37 Cas général => problème de satisfiabilité
38 problème de satisfiabilité
39 problème de satisfiabilité
40 Problème de satisfiabilité : entrées/sorties
41 couverture de DAG => problème de statisfiabilité
42 Exemple 1 o1 3 5 2 a b 4 6 c 7 8 o2 d 9
43 Exemple Générer les contraintes de couverture de chaque noeud :
44 Exemple m1 m3 m2 On rajoute la clause : (m3 {m1,m2})
45 Exemple
46 Exemple
47 Complexité de la couverture de DAG
48 Couverture optimale par des arbres
49 Mapping optimisé
50 Mapping optimisé Bibliothèque Fonction
51 Mapping optimisé b c d a
52 Exercice : optimisation vitesse
53 Discussion
54 Inversion Possibilité d’inverser les entrées et/ou la fonction
55 Inversion
56 Partitionnement
57 Partitionnement Autre partitionnement :
58 Décomposition technologique – niveau transistors
59 Portes élémentaires CMOS
60 Portes logiques statiques CMOS
61 Porte complexe CMOS F = a.b’ + c.(d’ + e’) Vdd
62 Décomposition Préparation de la décomposition:
63 Exemple de calcul des couples (S,P)
64 Algorithme de décomposition
65 Expansion d’un nœud de coupure
66 Représentation de la sous-fonction
67 Décomposition – Exemple (1)
68 Décomposition – Exemple (2)
69 Décomposition – Exemple (3)
70 Décomposition – Exemple (4)
71 Décomposition – Exemple (5)
72 Décomposition – Exemple (6)
73 Décomposition – Exemple (7)
74 Exemple (8) SF2 = abc + (a’+b’) (c’+f) SF2′ voulu + + + Vdd SF2 a’ c’
75 Plan Synthèse de contrôleurs (FSM) Spécification de contrôleurs
76 Circuits Logiques Programmables : PLD
77 Circuits Logiques Programmables : PLD
78 PAL : Programmable Array Logic
79 PAL : Programmable Array Logic
80 Implantation sur FPGA Block logique Block logique Block logique Block
81 Architecture des blocks logiques : Actel
82 Architecture des blocks logiques : Quicklogic
83 Architecture des blocks logiques : Xilinx 3000
Factorisation des fonctions logiques pdf.
