Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Ecole Nationale Supérieure d’Informatique et de Mathématiques Appliquées Archit

Ecole Nationale Supérieure d’Informatique et de Mathématiques Appliquées Architecture : Circuits numériques et éléments d’architecture 1ère année Année scolaire 2014–2015 Les exercices de ce recueil sont classés en 4 catégories : – Les exercices avec la mention "Préparation" sont proposés pour vous aider à pré- parer les séances de TDs ; il est recommandé de résoudre ces exercices avant les séances de TD. – Les exercices avec la mention "Pour aller plus loin..." sont proposés pour vous aider à consolider les notions vues pendant les séances de TD ; il est recommandé de résoudre ces exercices après la séance de TD. – Les exercices avec la mention "Méthodologie" sont étudiés en séance. Leur correc- tion est fournie dans l’enoncé. – Les exercices sans mention sont ceux qui seront étudiés pendant les séances ; il est recommandé de préparer ces exercices avant la séance de TD. Toutes les questions traitées en séance disposent d’une correction à la ﬁn du fascicule. L’enseignant vous donnera le numéro correspondant à chaque question. Consignes TD 1 Portes de base et minimisations de fonctions booléennes Préparation Ex. 1 : Codage des entiers naturels Question 1 Remplir un tableau contenant les valeurs en base 2, en base 10 et en base 16 des entiers naturels entre 0 et 15 (inclus). Question 2 Comment peut-on calculer facilement une valeur en hexadécimal à partir de sa valeur en binaire ? Convertir en hexadécimal la valeur binaire 1011010111002. Question 3 Faire les additions suivantes en binaire : 44+21 et 200+100 sur 8 bits 1. Que constatez- vous pour le résultat de la 2e addition ? Comment peut-on détecter ce phénomène ? Question 4 Quel intervalle d’entiers naturels peut-on coder sur n bits ? Combien de bits faut-il pour coder m valeurs diﬀérentes (avec m ≥2) ? Préparation Ex. 2 : Circuit comparateur d’entiers Dans cet exercice, on travaille sur des entiers A et B codés sur 4 bits, ce qu’on notera A = a3a2a1a0 et B = b3b2b1b0. Pour construire les circuits demandés, on suppose qu’on dispose de portes avec au maximum 4 entrées. Question 1 Quelle porte élémentaire produit 1 en sortie ssi ses deux entrées sont égales ? Question 2 Construire un circuit prenant en entrée 2 entiers A et B et produisant une sortie eg valant 1 ssi ces 2 entiers sont égaux. Question 3 Etendre ce circuit pour ajouter une sortie z valant 1 ssi A vaut 0. Question 4 Ajouter une sortie imp valant 1 ssi le nombre de bits composant B et valant 1 est impair. Par exemple, si B = 510 = 01012 alors imp = 0 et si B = 1410 = 11102 alors imp = 1. Méthodologie Ex. 3 : Conception et minimisation de circuits combinatoires sur un exemple élémentaire On travaille sur la fonction majorité de trois variables valant "vrai" ssi la majorité des paramètres de la fonction valent 1. Table de vérité de la fonction Majorité 1. C’est à dire que les opérandes et le résultat de l’opération sont codés sur 8 bits. a b c Maj(a, b, c) termes canoniques 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 a.b.c 1 0 0 0 1 0 1 1 a.b.c 1 1 0 1 a.b.c 1 1 1 1 a.b.c N.B : un "terme canonique" est le produit (AND) de toutes les variables de la fonction sous forme normale (a) ou complémentée (a). On recherche une expression somme de produits donc on ne s’intéresse qu’aux termes correspondants aux 1 de la fonction. Expression booléenne canonique de la fonction Maj(a, b, c) C’est l’expression de la fonction Maj(a, b, c) en fonction des paramètres a, b et c, sans chercher à minimiser cette expression. C’est donc la somme des termes canoniques déduits de la table de vérité : Maj(a, b, c) = a.b.c + a.b.c + a.b.c + a.b.c. Circuit implantant cette fonction Pour dessiner le circuit implantant cette fonction, on n’utilisera ici que des portes de bases AND, OR à 2 entrées ainsi que des portes INV. a Maj(a, b, c) b c Minimisation de l’expression de la fonction On montre ici comment on peut minimiser l’expression d’une fonction en utilisant le calcul booléen. On part de : Maj(a, b, c) = a.b.c + a.b.c + a.b.c + a.b.c On remarque que les simpliﬁcations suivantes sont possibles, grâce à la règle x.y + x.y = y : a.b.c + a.b.c = b.c a.b.c + a.b.c = a.c a.b.c + a.b.c = a.b Faut-il choisir une (et une seule) de ces simpliﬁcations ? non, car on a aussi la règle x + x = x. On peut donc réécrire l’expression de la fonction Majorité comme ci-dessous : Maj(a, b, c) = a.b.c + a.b.c + a.b.c + a.b.c + a.b.c + a.b.c = a.b.c + a.b.c + a.b.c + a.b.c + a.b.c + a.b.c = b.c + a.c + a.b Tableaux de Karnaugh : Une technique graphique pour la minimisation d’expressions booléennes Un tableau de Karnaugh est une table de vérité, présentée de façon à ce que les adjacences du type x.y + x.y = y soient mises en évidence. Le tableau de Karnaugh de la fonction Maj(a, b, c) est donné ci-dessous. Remarquez que l’ordre de l’énumération des variables b et c n’est pas quelconque : une seule des variables change de valeur entre deux colonnes (y compris quand on rapproche la dernière colonne de la première : adjacence circulaire). Remplir un tableau de Karnaugh revient à remplir une table de vérité. Par exemple, la troisième case de la première ligne correspond à a = 0 et b = 1 et c = 1 : Maj(0, 1, 1) = 1 donc la case est remplie avec un 1. 1 0 00 01 11 10 a bc 0 0 1 0 0 1 1 1 Les groupements de points à 1 mettent en évidence les simpliﬁcations possibles. Il suﬃt alors de choisir un nombre minimal de regroupements qui couvrent tous les points à 1 de la fonction. Pour chaque groupe de cases à 1, on extrait un terme construit à partir des variables qui ne changent pas de valeur pour l’ensemble des points regroupés. Par exemple, pour le groupement vertical de la troisième colonne : on remarque que la valeur de a change entre les deux cases regroupées, a n’apparaitra donc pas dans le terme correspondant à ce groupe. Ce qui est commun dans ce groupe ce sont les valeurs de b et c : on extrait donc le terme b.c Sur cet exemple, il y a donc 3 termes qui correspondent aux trois groupements, on retrouve l’expression : Maj(a, b, c) = b.c + a.c + a.b. N.B : Les groupements ne peuvent être que de 2, 4 ou 8 cases (puissances de 2). Par la suite, on utilisera souvent des tableaux avec 4 variables en entrées donc 16 cases. Le nombre de variables dans un terme correspond à la taille du groupement. Par exemple, dans un tableau de 16 cases (4 variables), un groupe de 8 cases correspond à un terme d’une variable, un groupe de 4 à un terme de 2 variables, un groupe de 2 à un terme de 3 variables et si il reste un 1 isolé le terme correspondant utilise les 4 variables. Circuit minimisé A partir de l’expression minimisée, on peut dessiner le circuit suivant : a Maj(a, b, c) b c Pourquoi a t on besoin de minimiser ? On remarque que le circuit obtenu à partir de la forme minimisée a deux avantages : moins de portes au total (5 au lieu de 12) et moins de portes traversées (entre l’entrée et la sortie, au plus 3 portes au lieu de 4). Ce circuit minimisé est donc moins couteux en porte et plus rapide. N.B : Chaque porte a un temps de propagation (diﬀérent suivant la technologie). Le temps de propagation à travers un circuit est déterminé par le nombre maximal de couches de portes à traverser entre une entrée et une sortie. Remarque : dans la suite du semestre, nous n’utiliserons que les minimisations de fonctions boo- léennes à base de tableaux de Karnaugh. Ex. 4 : Reste de la division entière Soit un entier naturel E dans l’intervalle [0 .. 15], donc codé sur 4 bits e3, e2, e1, e0 ; on veut réaliser un circuit qui calcule le reste S de la division entière de E par 7. Question 1 Sur combien de bits doit être codé S ? Question 2 Représenter les fonctions de sortie du circuit à l’aide de tableaux de Karnaugh. Question 3 Proposer des expressions minimisées des fonctions de sortie du circuit. On considère maintenant que l’entier E en entrée est dans l’intervalle [0 .. 9]. Les fonctions en sortie sont donc des fonctions Φ - booléennes. Méthodologie : Pour toutes les cases qui correspondent à une valeur d’entrées non utilisée (ici, les cases correspondant aux valeurs de 10 à 15), la valeur de la sortie est uploads/s3/ archi1-recueil.pdf