TPs 1 et 2 (Hiver 2004)
IFT3380/IFT6380
Par groupe de 2 étudiants
Première partie : à remettre jeudi 5 février à 23h59
Exercices 1.1, A1,
A5, A7 de H&P ed 3.
Deuxième partie : à remettre Jeudi 11 mars à 23h59 et Jeudi 18 mars
à 23h59
Exercices 1.3, 3.4,
3.6 de H&P ed 3. (Jeudi 11 mars à 23h59)
Exercice 4 :
(jeudi 18 mars à 23h59)
Théorie :
Toute fonction booléenne peut avoir une
représentation cubique, elle consiste en une table où chaque ligne est appelée
cube. Chaque cube correspond à un produit de la fonction dans la représentation
somme de produits
Ainsi la
fonction: possède la table
suivante :
.
0, 1, x
signifient respectivement : variable complémentée, non
complémentée ou absente du produit (don’t care).
Une
représentation interne utiliserait 2 bits pour chacune des trois valeurs:
Ainsi la fonction
précédente serait représentée sur 8 bits :
Il s’agit
de trouver si un cube est inclus dans un autre dans une table et ainsi réduire
la table. On peut vérifier qu’un cube
est inclus dans un autre par l’opération intersection (qui consiste en un
ET logique) :
Ainsi si on
a :, on remarque que
donc peut être enlevé
On se
limite à des fonction d’au plus 16 variables, et on termine la table par le
cube 0…0 qui représente un cube vide.
Travail demandé :
Écrire en
assembleur MIPS, le programme qui lit une table et la simplifie.