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 l'ensemble des booléens. Si est un booléen, on notera le complément de . On écrira pour la conjonction (produit) de et pour la disjonction de et en posant et ; et pour le ou-exclusif, défini par et .
La représentation binaire ( ) de l'entier sur bits ( ) est définie par :
où est un booléen pour tout . Dans le problème, on ne considère que des représentations binaires d'entiers vérifiant , et donc représentables comme de simples entiers positifs en Pascal ou Caml. On écrira aussi pour la représentation binaire de quand est clair dans le contexte. Les bits de sont les booléens est le bit le moins significatif; 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 :
qui s'exécutent en temps constant . Ainsi on autorise les expressions arithmétiques de Caml ou Pascal à être de la forme et .
Question 1 Montrer que, si , alors est de la forme si et seulement si .
La distance de Hamming entre deux entiers et est le nombre de bits dont ils diffèrent dans leur décomposition binaire et sur 30 bits.
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 et .
Question 2 Écrire la fonction aDistUn qui prend comme argument deux entiers et et retourne, en temps constant, la valeur vrai si et seulement si la distance de Hamming entre et vaut 1 .
Soit une fonction booléenne de arguments booléens; donc est une fonction de dans ( ). Deux exemples de fonctions booléennes sont et définies par: , et . 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 par l'ensemble des entiers dont la représentation binaire sur bits est dans , image inverse de 1 . Ainsi est définie par l'ensemble et par .
Un littéral est une variable ou son complément ; on dira que est un littéral positif et est un littéral négatif. Toute fonction booléenne 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 . Ainsi s'écrit sous trois f.n.d. distinctes.
Question 3 Exprimer 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 , on utilisera principalement l'identité
Ainsi . Remarquons qu'on peut aussi utiliser l'identité et obtenir . 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 .
Un ensemble d'indices compris entre 0 et est représentable par l'entier dont la représentation binaire a des bits à 1 aux seules positions . Un produit de littéraux est représenté par un enregistrement contenant deux entiers : une valeur et un masque . Le masque est l'entier désignant l'ensemble ; la valeur correspond au sous-ensemble de où est un littéral positif. Ainsi le produit est représenté par les deux entiers et dont les représentations binaires respectives (sur 30 bits) sont et . En abrégé, le produit s'écrira 101-1-- - ou plus simplement 101-1.
Question 5 Écrire les fonctions varEliminable et unifier qui prennent deux produits et en arguments; et qui, la première, retourne la valeur vrai si et ou et ; et qui, la seconde, retourne le produit 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 ; 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 ?
Question 7 Écrire la fonction nouveauxProduits qui prend en argument une somme ; et qui retourne la somme de tous les produits qu'il est possible d'obtenir en éliminant une variable inutile entre deux produits de .
Quelle est la complexité en temps de cette fonction par rapport à la longueur de la somme ?
Pour générer une f.n.d. réduite de la fonction booléenne de arguments, on commence par fabriquer la somme de tous les produits de variables correspondant à , image inverse de 1 par (par exemple, pour ). Puis on applique la fonction nouveauxProduits à , donnant la somme . Et on recommence en rappelant cette fonction sur , donnant une autre somme , etc. On s'arrête quand on ne produit plus de nouveaux produits. Ainsi pour , on obtient pour , et on s'arrête.
Question 8 Donner la suite des obtenus pour .
Pour le moment, on garde tous les produits. Il est donc plus simple de manipuler des listes de sommes pour stocker .
(* 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 ; et qui retourne la liste des sommes obtenues en itérant la fonction nouveauxProduits à partir de .
Quelle est la complexité de cette fonction par rapport aux longueurs des listes ?
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 couvre les produits et . En outre, couvre si couvre et couvre .
Question 10 Écrire la fonction couvertPar qui prend en argument deux produits et ; et qui retourne la valeur vrai si est couvert par .
Quelle est la complexité en temps de cette fonction?
Question 11 Écrire la fonction reduire qui prend en argument une f.n.d. ; 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 des listes composant la représentation de ?
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 d'arguments de la fonction .
La partie combinatoire d'un circuit contient une combinaison de portes- , portes- 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- à entrées calcule la somme (disjonction) ; de même une porte- à entrées calcule le produit , et l'inverseur à une entrée calcule .
Cette partie combinatoire des circuits intégrés consiste souvent à calculer une fonction de dans à l'aide d'un PLA (Programmable Logic Array). Un PLA, à entrées et sorties comme indiqué sur la figure 3 , calcule sur chaque sortie la fonction booléenne associée à en s'appuyant sur sa représentation en f.n.d.. Un PLA comporte deux parties : la partie- ne contenant que des portes- et quelques inverseurs, et la partie- ne contenant que des portes-OU.
Fig. 3: Circuit PLA.
Question 13 Pour une fonction donnée de dans
a) Expliquer le fonctionnement du PLA associé. Dessiner le quand et
b) Déterminer la largeur 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- ou portes- à 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 et 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 et fournissant les valeurs et ; et qui, la première, retourne le circuit calculant le reste modulo 2 de ; et qui, la seconde, retourne le circuit calculant le quotient de la division par 2 de .
{ Pascal }
function bitAdd (x:circuit; y:circuit;
r:circuit) : circuit;
function bitRetenue (x:circuit; y:circuit;
r:circuit) : circuit;
La représentation binaire de l'entier sur bits ( ) est à présent décrite par un vecteur (tableau) de circuits, dont la -ème entrée vaut le bit , comme indiqué dans la partie I. On appellera mot machine de longueur ce tableau. Un additionneur série de et effectue l'addition successive des bits et 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 et de longeur ; et qui retourne le circuit calculant le mot machine de longueur représentant . 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 et ont une même longueur . En Pascal, la fonction prend la longueur effective du mot en argument; le résultat est retourné dans le paramètre passé par référence.
Question 16 Écrire la fonction mux qui prend en arguments un circuit et deux mots machines et ; et qui retourne le circuit fournissant la valeur de si fourni par vaut 1 , et celle de si 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 et à additionner en deux parties basses contenant les bits les moins significatifs et deux parties hautes contenant les bits les plus significatifs. Pour ne pas attendre le résultat de la retenue de pour calculer , on peut précalculer les résultats de l'addition de et avec la retenue valant 0 et celle valant 1 . Puis le véritable résultat de la retenue de permet de donner le résultat voulu pour .
Question 17 Écrire la fonction addPar qui prend en arguments deux mots machine et de longeur et un circuit fournissant une retenue ; et qui retourne le circuit calculant le mot machine de longueur représentant . Quel est le temps de calcul de ce circuit? Donner un ordre de grandeur du nombre de portes de ce circuit.
Question 18 Pourquoi ne pas utiliser un PLA pour réaliser ces additionneurs? Quels auraient été les avantages/désavantages?
* *
*
Polytechnique Option Informatique MP 2005 - Version Web LaTeX | WikiPrépa | WikiPrépa
