Informatique, option info X MP 2005 : circuits PLA, réduction de formes normales disjonctives et additionneurs
Afficher ou masquer la section
Le sujet porte sur la conception de circuits combinatoires. La première partie construit un algorithme qui réduit le nombre de produits d'une forme normale disjonctive d'une fonction booléenne, en manipulant des listes de produits représentés par des masques de bits, afin de générer un circuit PLA économique. La seconde partie construit des circuits d'addition binaire, d'abord un additionneur série propageant la retenue bit à bit, puis un additionneur plus rapide qui précalcule les deux cas possibles de retenue pour les bits de poids fort.
1Partie I : génération de circuits PLAOn représente les fonctions booléennes et leurs formes normales disjonctives par des entiers et des listes de produits, puis on écrit des fonctions qui réduisent le nombre de produits en éliminant les variables inutiles, avant d'analyser la structure et la surface d'un circuit PLA.
2Partie II : génération de circuits combinatoiresOn construit des circuits représentés par des arbres de portes ET, OU et inverseurs, pour réaliser un additionneur série puis un additionneur plus rapide qui précalcule les retenues sur les bits de poids fort.
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.
Circuits PLA et additionneurs
On attachera une grande importance à la concision, à la clarté, et à la précision de la rédaction. Les deux parties du problème sont quasi indépendantes.
I. Génération de circuits PLA
Dans ce problème, les booléens sont représentés par 0 pour la valeur faux, et 1 pour la valeur vraie. Soit B = {0, 1} l'ensemble des booléens. Si x est un booléen, on notera x¯ = 1 − x le complément de x. On écrira x ⋅ y pour la conjonction (produit) de x et y; x + y pour la disjonction de x et y en posant 0 + ˙0 = 0 et 0 + ˙1 = 1 + ˙0 = 1 + ˙1 = 1; et x ⊕ y pour le ou-exclusif, défini par 0 = 0 ⊕ 0 = 1 ⊕ 1 et 1 = 0 ⊕ 1 = 1 ⊕ 0.
La représentation binaire ( x_0, x_1, …x_(n − 1) ) de l'entier x sur n bits ( 0 ≤ x < 2^n ) est définie par :
x = x_0 2^0 + x_1 2^1 + ⋯ + x_(n − 1)2^(n − 1)
où x_i est un booléen pour tout i(0 ≤ i < n). Dans le problème, on ne considère que des représentations binaires d'entiers x vérifiant x < 2^(30), et donc représentables comme de simples entiers positifs en Pascal ou Caml. On écrira aussi x⃗ pour la représentation binaire de x quand n est clair dans le contexte. Les bits de x sont les booléens x_0, x_1, …x_(n − 1); x_0 est le bit le moins significatif; x_(n − 1) est le bit le plus significatif.
Enfin, on suppose que les deux langages Pascal et Caml possèdent les opérations logiques ∧, ∨, ⊕, ¬ sur les entiers positifs définies par :
x ∧ y = (x_0 ⋅ y_0)2^0 + (x_1 ⋅ y_1)2^1 + ⋯ + (x_(29) ⋅ y_(29))2^(29), si x = x_0 2^0 + x_1 2^1 + ⋯ + x_(29)2^(29); x ∨ y = (x_0 + y_0)2^0 + (x_1 + y_1)2^1 + ⋯ + (x_(29) + y_(29))2^(29), y = y_0 2^0 + y_1 2^1 + ⋯ + y_(29)2^(29); x ⊕ y = (x_0 ⊕ y_0)2^0 + (x_1 ⊕ y_1)2^1 + ⋯ + (x_(29) ⊕ y_(29))2^(29); ¬x = x¯_0 2^0 + x¯_1 2^1 + ⋯ + x¯_(29)2^(29)
qui s'exécutent en temps constant O(1). Ainsi on autorise les expressions arithmétiques de Caml ou Pascal à être de la forme e ∧ e^′, e ∨ e^′, e ⊕ e^′ et ¬e.
Question 1 Montrer que, si 0 < x < 2^(30), alors x est de la forme x = 2^p(p ≥ 0) si et seulement si x ∧ (x − 1) = 0.
La distance de Hamming d(x, y) entre deux entiers x et y est le nombre de bits dont ils diffèrent dans leur décomposition binaire x⃗ et y⃗ sur 30 bits.
x_1
x_0
g(x_0, x_1)
x_2
x_1
x_0
h(x_0, x_1, x_2)
0
0
1
0
0
0
0
0
1
0
0
0
1
1
1
0
1
0
1
0
0
1
1
1
0
1
1
1
1
0
0
1
1
0
1
0
1
1
0
1
1
1
1
0
Fig. 1: Tables de vérité de g et h.
Question 2 Écrire la fonction aDistUn qui prend comme argument deux entiers x et y et retourne, en temps constant, la valeur vrai si et seulement si la distance de Hamming entre x et y vaut 1 .
(∗ Caml ∗), { Pascal }; aDistUn : int − > int − > bool, function aDistUn (x :integer, y :integer) : boolean;
Soit f une fonction booléenne de n arguments booléens; donc f est une fonction de B^n dans B ( n > 0 ). Deux exemples de fonctions booléennes sont g et h définies par: g(x_0, x_1) = x¯_0 + ˙x_0 ⋅ x_1, et h(x_0, x_1, x_2) = x_0 ⊕ x_2. Une fonction booléenne peut être définie par sa table de vérité, comme sur la figure 1. Dans le problème, nous représenterons toute fonction booléenne f par l'ensemble des entiers dont la représentation binaire sur n bits est dans f^(− 1)(1), image inverse de 1 . Ainsi g est définie par l'ensemble {0, 2, 3} et h par {1, 3, 4, 6}.
Un littéral est une variable x ou son complément x¯; on dira que x est un littéral positif et x¯ est un littéral négatif. Toute fonction booléenne f(x_0, x_1, …x_(n − 1)) peut être mise en forme normale disjonctive (f.n.d.) en l'exprimant comme une somme de produits de littéraux formés à partir de x_0, x_1, …x_(n − 1). Ainsi g(x, y) = x¯ ⋅ y¯ + ˙x¯ ⋅ y + ˙x ⋅ y = x¯ + ˙x ⋅ y = x¯ + ˙y s'écrit sous trois f.n.d. distinctes.
Question 3 Exprimer h avec une f.n.d. sous forme de la somme de 4 produits.
Pour réduire le nombre de produits dans la f.n.d. de f, on utilisera principalement l'identité
x ⋅ p + ˙x¯ ⋅ p = (x + ˙x¯) ⋅ p = 1 ⋅ p = p
Ainsi g(x, y) = x¯ ⋅ y¯ + ˙x¯ ⋅ y + ˙x ⋅ y = x¯ ⋅ (y¯ + ˙y) + ˙x ⋅ y = x¯ + ˙x ⋅ y. Remarquons qu'on peut aussi utiliser l'identité p + ˙p = p et obtenir g(x, y) = x¯ ⋅ (y¯ + ˙y) + ˙(x¯ + ˙x) ⋅ y = x¯ + ˙y. Dans cet exemple le nombre de produits n'est pas plus faible, mais en général cette identité supplémentaire permet de le faire baisser. Le but de cette partie est de trouver efficacement parmi toutes les réécritures de la f.n.d. l'une de celles ayant un nombre de produits minimal, ou presque. On appellera f.n.d. réduite le résultat de notre algorithme.
Question 4 Réduire le nombre de produits dans la f.n.d. de h.
Un ensemble {i_0, i_1, …i_(ℓ − 1)} d'indices compris entre 0 et 29(0 ≤ i_k < 30, 0 ≤ k < ℓ) est représentable par l'entier dont la représentation binaire a des bits à 1 aux seules positions i_0, i_1, …i_(ℓ − 1). Un produit de littéraux x_(i_0) ⋅ x_(i_1)⋯x_(i_(ℓ − 1))(0 ≤ i_0 < i_1… < i_(ℓ − 1) < 30) est représenté par un enregistrement contenant deux entiers : une valeur v et un masque m. Le masque m est l'entier désignant l'ensemble E = {i_0, i_1, …i_(ℓ − 1)}; la valeur v correspond au sous-ensemble de E où x_(i_k) est un littéral positif. Ainsi le produit x_0 ⋅ x_2 ⋅ x¯_3 ⋅ x_4 est représenté par les deux entiers v = 21 et m = 29 dont les représentations binaires respectives (sur 30 bits) sont (1, 0, 1, 0, 1, 0, …0) et (1, 0, 1, 1, 1, 0, …0). En abrégé, le produit s'écrira 101-1-- … - ou plus simplement 101-1.
(∗ Caml ∗), { Pascal }; type produit = {v : int; m : int };, type produit = record v, m:integer; end;
Question 5 Écrire les fonctions varEliminable et unifier qui prennent deux produits p et q en arguments; et qui, la première, retourne la valeur vrai si p = p^′ ⋅ x_i ⋅ p^(′′) et q = p^′ ⋅ x¯_i ⋅ p^(′′) ou p = p^′ ⋅ x¯_i ⋅ p^(′′) et q = p^′ ⋅ x_i ⋅ p^(′′); et qui, la seconde, retourne le produit p^′ ⋅ p^(′′) dans le cas où la première fonction vaut vrai.
(* Caml *)
varEliminable : produit -> produit
-> bool
unifier: produit -> produit
-> produit
{ Pascal }
function varEliminable (p:produit, q:produit)
: boolean;
function unifier (p:produit, q:produit)
: produit;
Quelle est la complexité en temps de ces deux fonctions?
Une somme (disjonction) de produits est représentée par une liste de produits :
(* Caml *)
type somme == produit list;;
{Pascal }
type somme = ^cellule;
cellule = record contenu:produit;
suivant:somme; end;
En Pascal, la liste vide est nil et l'on pourra pour construire les listes utiliser la fonction suivante :
function cons(contenu:produit; suivant:somme) : somme;
var r:somme;
begin new(r); r^.contenu := contenu; r^.suivant := suivant; cons := r end;
Cette fonction est applicable pour construire les listes du type somme.
Question 6 Écrire la fonction unique qui prend en argument une somme a; et qui retourne la même somme où chacun des produits n'apparaît qu'une seule fois.
Quelle est la complexité en temps de cette fonction par rapport à la longueur ℓ de la somme a ?
Question 7 Écrire la fonction nouveauxProduits qui prend en argument une somme a; et qui retourne la somme de tous les produits qu'il est possible d'obtenir en éliminant une variable inutile entre deux produits de a.
Quelle est la complexité en temps de cette fonction par rapport à la longueur ℓ de la somme a ?
Pour générer une f.n.d. réduite de la fonction booléenne f de n arguments, on commence par fabriquer la somme a_0 de tous les produits de n variables correspondant à f^(− 1)(1), image inverse de 1 par f (par exemple, 00, 01, 11 pour g ). Puis on applique la fonction nouveauxProduits à a_0, donnant la somme a_1. Et on recommence en rappelant cette fonction sur a_1, donnant une autre somme a_2, etc. On s'arrête quand on ne produit plus de nouveaux produits. Ainsi pour g, on obtient 0 −, − 1 pour a_1, et on s'arrête.
Question 8 Donner la suite des a_i obtenus pour h.
Pour le moment, on garde tous les produits. Il est donc plus simple de manipuler des listes de sommes pour stocker ⟨a_k, …, a_2, a_1, a_0⟩.
(* Caml *)
type fnd == somme list;;
{ Pascal }
type fnd = `celluleS;
celluleS = record contenu:somme;
suivant:fnd; end;
Pour construire ces listes, on utilisera la fonction consFnd analogue de la fonction cons.
Question 9 Écrire la fonction developper qui prend en argument une somme a; et qui retourne la liste ⟨a_k, …a_2, a_1, a_0⟩ des sommes obtenues en itérant la fonction nouveauxProduits à partir de ⟨a⟩.
(∗ Caml ∗), { Pascal }; developper : somme → fnd, function developper (a : somme) : fnd;
Quelle est la complexité de cette fonction par rapport aux longueurs ℓ_0, ℓ_1, …ℓ_k des listes a_0, a_1, …a_k ?
Le résultat de la fonction developper est une liste de listes, ayant beaucoup plus de termes que la somme de départ, et dont on va extraire les produits formant la f.n.d. réduite. Cela se fait en éliminant tous les produits couverts par un autre produit. Ainsi le produit -0 couvre les produits 00 et 10 ; de même 1 - couvre 10 et 11 . Formellement, le produit p^′ ⋅ p^(′′) couvre les produits p^′ ⋅ x_i ⋅ p^(′′) et p^′ ⋅ x¯_i ⋅ p^(′′). En outre, p couvre p^(′′) si p couvre p^′ et p^′ couvre p^(′′).
Question 10 Écrire la fonction couvertPar qui prend en argument deux produits p et q; et qui retourne la valeur vrai si p est couvert par q.
Quelle est la complexité en temps de cette fonction?
Question 11 Écrire la fonction reduire qui prend en argument une f.n.d. s; et qui retourne une f.n.d. calculant la même fonction où il n'y a plus aucun produit couvrant un autre.
Quelle est la complexité de cette fonction par rapport aux longueurs ℓ_0, ℓ_1, …ℓ_k des listes a_0, a_1, …a_k composant la représentation ⟨a_k, …a_2, a_1, a_0⟩ de s ?
Question 12 Donner une borne supérieure de la complexité du calcul du résultat de cette f.n.d. réduite en fonction du nombre n d'arguments de la fonction f.
La partie combinatoire d'un circuit contient une combinaison de portes- ET, portes- OU et inverseurs représentés sur la figure 2 . Les signaux circulant dans les fils des circuits sont assimilés aux booléens 0 et 1 . Une porte- OU à n entrées x_0, x_1, …x_(n − 1) calcule la somme (disjonction) x_0 + ˙x_1 + ˙⋯ + ˙x_(n − 1); de même une porte- ET à n entrées x_0, x_1, …x_(n − 1) calcule le produit x_0 ⋅ x_1⋯x_(n − 1), et l'inverseur à une entrée x calcule x¯.
Cette partie combinatoire des circuits intégrés consiste souvent à calculer une fonction f de B^n dans B^m(0 < n < 30, 0 < m) à l'aide d'un PLA (Programmable Logic Array). Un PLA, à n entrées et m sorties comme indiqué sur la figure 3 , calcule sur chaque sortie la fonction booléenne f_i(x_0, x_1, …x_(n − 1))(0 ≤ i < m) associée à f en s'appuyant sur sa représentation en f.n.d.. Un PLA comporte deux parties : la partie- ET ne contenant que des portes- ET et quelques inverseurs, et la partie- OU ne contenant que des portes-OU.
Fig. 3: Circuit PLA.
Question 13 Pour une fonction f donnée de B^n dans B^m(0 < n < 30, 0 < m)
a) Expliquer le fonctionnement du PLA associé. Dessiner le quand f_0(x_0, x_1, x_2) = g(x_0, x_1) et f_1(x_0, x_1, x_2) = h(x_0, x_1, x_2)
b) Déterminer la largeur k du PLA comme indiqué sur la figure 3 permettant de calculer sa surface. Comment réduire cette surface?
II. Génération de circuits combinatoires
Dans cette partie, nous allons qénérer d'autres exemples de circuits combinatoires calculant des fonctions booléennes. Ces circuits ne seront composés que d'inverseurs, de portes- ET ou portes- OU à 2 entrées (cf. la figure 2), et de bits valant 0 ou 1 . Ils seront représentés par des arbres donnant la valeur de la sortie en fonction des valeurs des entrées, c'est-à-dire des bits figurant à leurs feuilles. Le type de ces arbres est le suivant :
(* Caml *)
type circuit =
Bit of int
| Et of circuit*circuit
| Ou of circuit*circuit
| Non of circuit;;
{Pascal }
type circuit = `porte; porte = record case indicateur of
Bit: (val:integer);
Et: (a1:circuit; a2:circuit) ;
Ou: (a1:circuit; a2:circuit) ;
Non: (a1:circuit) ; end;
On ne se souciera pas du partage possible entre sous-arbres calculant la même valeur. Mais on remarquera que le temps mis par un circuit pour calculer son résultat est proportionnel à la hauteur de cet arbre. Par exemple, on peut calculer en 3 unités de temps le ou-exclusif de x et y comme suit :
let oux x y =
Ou (Et (x, Non y),
Et (Non x, y));;
(* Caml *) \{Pascal \}
function oux (x: circuit; y:circuit): circuit;
begin oux := nouveauOu (nouveauEt(x, nouveauNon (y)),
nouveauEt(nouveauNon(x), y)); end;
En Pascal, pour construire ces circuits, on utilisera les fonctions nouveauEt, nouveauOu et nouveauNon, analogues aux constructeurs cons et consFnd de la partie I.
Question 14 Écrire les fonctions bitAdd et bitRetenue qui prennent en argument trois circuits x, y et r fournissant les valeurs x^′, y^′ et r^′; et qui, la première, retourne le circuit calculant le reste modulo 2 de x^′ + y^′ + r^′; et qui, la seconde, retourne le circuit calculant le quotient de la division par 2 de x^′ + y^′ + r^′.
{ Pascal }
function bitAdd (x:circuit; y:circuit;
r:circuit) : circuit;
function bitRetenue (x:circuit; y:circuit;
r:circuit) : circuit;
La représentation binaire x⃗ de l'entier x sur n bits ( n > 0 ) est à présent décrite par un vecteur (tableau) de n circuits, dont la i-ème entrée vaut le bit x_i, comme indiqué dans la partie I. On appellera mot machine de longueur n ce tableau. Un additionneur série de x⃗ et y⃗ effectue l'addition successive des bits x_i et y_i en partant des bits les moins significatifs vers les bits les plus significatifs en propageant la retenue.
Question 15 Écrire la fonction addSerie qui prend en arguments deux mots machine x et y de longeur n; et qui retourne le circuit calculant le mot machine de longueur n + 1 représentant x + y. Quel est le temps de calcul de ce circuit? Donner un ordre de grandeur du nombre de portes de ce circuit.
(* Caml *) {Pascal }
type mot == circuit vect;
addSerie : mot -> mot -> mot
type mot = array[0..256] of circuit;
procedure addSerie (var z: mot; n:integer;
var x: mot; var y: mot);
En Caml, on supposera que les paramètres x et y ont une même longueur n. En Pascal, la fonction prend la longueur n effective du mot en argument; le résultat est retourné dans le paramètre z passé par référence.
Question 16 Écrire la fonction mux qui prend en arguments un circuit s et deux mots machines x et y; et qui retourne le circuit fournissant la valeur de x si s^′ fourni par s vaut 1 , et celle de y si s^′ vaut 0 .
(* Caml *) {Pascal }
mux: circuit -> mot -> mot -> mot
procedure mux (var z: mot; n:integer;
s: circuit; var x: mot; var y: mot);
On peut calculer l'addition plus rapidement en coupant les mots machine x et y à additionner en deux parties basses x_b, y_b contenant les bits les moins significatifs et deux parties hautes x_h, y_h contenant les bits les plus significatifs. Pour ne pas attendre le résultat de la retenue de x_b + y_b pour calculer x_h + y_h, on peut précalculer les résultats de l'addition de x_h et y_h avec la retenue valant 0 et celle valant 1 . Puis le véritable résultat de la retenue de x_b + y_b permet de donner le résultat voulu pour x_h + y_h + r.
Question 17 Écrire la fonction addPar qui prend en arguments deux mots machine x et y de longeur n et un circuit r fournissant une retenue r^′; et qui retourne le circuit calculant le mot machine de longueur n + 1 représentant x + y + r^′. Quel est le temps de calcul de ce circuit? Donner un ordre de grandeur du nombre de portes de ce circuit.
(∗ Caml ∗), { Pascal }; addPar : mot − > mot − > circuit − > mot, procedure addPar (var z : mot; n : integer;; varx : mot; vary : mot; r : circuit);
Question 18 Pourquoi ne pas utiliser un PLA pour réaliser ces additionneurs? Quels auraient été les avantages/désavantages?
* *
*
Questions fréquentes
4 questions
Sur quels chapitres porte le sujet d'informatique option info X MP 2005 ?
Afficher ou masquer la section
Sur quels chapitres porte le sujet d'informatique option info X MP 2005 ?
+
Il porte sur l'algèbre de Boole, les structures de données de type liste et arbre, l'analyse de complexité en temps des algorithmes, et la conception de circuits combinatoires.
Les deux parties sont-elles indépendantes ?
+
L'énoncé précise qu'elles sont quasi indépendantes : la partie I porte sur la réduction de formes booléennes pour des circuits PLA, la partie II sur la construction directe de circuits additionneurs.
Quel langage de programmation faut-il utiliser ?
+
Le candidat doit choisir entre Caml et Pascal et l'indiquer en tête de copie, les deux langages étant proposés en parallèle dans l'énoncé.
Qu'est-ce qu'un circuit PLA dans ce sujet ?
+
C'est un circuit programmable composé d'une partie de portes ET puis d'une partie de portes OU, qui calcule une fonction booléenne à partir de sa forme normale disjonctive réduite.
Même chapitre : Structures de données : listes et… (+1)Mines Informatique 1 MPI 2023Mines · 2023Corrigé
Même année, CentraleCentrale Option Informatique MP 2005Centrale · 2005Corrigé
Même chapitre : Structures de données : listes et… (+1)X ENS Option Informatique MP MPI 2026X-ENS · 2026Sujet seul
Même année, CCINPCCINP Option Informatique MP 2005CCINP · 2005Sujet seul
.jpg)
