TD 1 5 6 TD 1

TD 1 - C IRCUITS COMBINATOIRES N 00 01 11 10 NW 00 01 11 10 NE 00 01 11 10 C 00 01 11 10
00 1 1 1 00 1 00 1 1 1 1 00 1 1
01 1 1 1 01 1 1 1 01 1 1 01 1 1 1
11 x x x x 11 x x x x 11 x x x x 11 x x x x
Simplification de fonctions booléennes, familiarisation avec l’outil de conception
10 1 1 x x 10 1 1 x x 10 1 1 x x 10 1 1 x x
de circuits, circuits combinatoires, représentation des nombres, arithmétique en com-
plément à 2, arithmétique flottante. SW 00 01 11 10 SE 00 01 11 10 S 00 01 11 10
Page web : [Link] acohen/teach/[Link] 00 1 1 00 1 1 1 00 1 1 1
01 1 01 1 1 1 1 01 1 1
11 x x x x 11 x x x x 11 x x x x
Exercice 1.1 - Afficheur numérique 10 1 x x 10 1 1 x x 10 1 1 x x
Fonctions simplifiées :
On souhaite réaliser l’afficheur numérique décimal décrit sur la figure 1. Il est N = āc̄ + ac + b + d ,
constitué de 7 diodes électro-luminescentes (LEDs) nommées N, NW , NE, C, SW , SE NW = āb̄ + āc + b̄c + d ,
et S. NE = āb̄ + ab + c̄,
C = bc̄ + āb + b̄c + d ,
N SW = āc̄ + āb,
SE = a + b̄ + c
S = ab̄c + bc̄ + āc̄ + āb + d .
NW NE
C Question 1.1.2
Réaliser l’afficheur en DigLog. Pour le circuit, on respectera la représentation des
fonctions logiques sous forme de sommes de produits.
SW SE Support : commencer par récupérer le fichier numeric_mask.lgf, puis lancer Di-
S
gLog par la commande cohen/bin/diglog numeric_mask.lgf.
Réponse
F IG . 1 – Afficheur numérique décimal Voir la figure 2 et le fichier [Link].

Question 1.1.1 Exercice 1.2 - Deux circuits combinatoires importants

Écrire une table de vérité pour chaque LED de l’afficheur, puis simplifier les fonc-
tions algébriques correspondantes à l’aide des tableaux de Karnaugh. Pour ne pas perdre On étudie deux circuits élémentaires fréquemment utilisés dans les composants des
de temps, vous avez la possibilité de ne réaliser que deux tableaux, par exemple ceux processeurs.
du sud ouest (SW ) et du centre (C).
Question 1.2.1
Réponse
Un décodeur n → 2n est un circuit combinatoire comprenant une entrée I sur n bits
Le signal d’entrée est codé sur 4 bits dcba. Les tables suivantes représentent les valeurs de
vérité de chaque LED : ba horizontalement et dc verticalement. 2n
et sorties O0 , . . . , O2n −1 sur 1 bit ; seul le signal Om doit être activé lorsque l’entrée I
vaut m (en binaire sur n bits).
Construire un décodeur 3 → 8. On pourra construire une table de Karnaugh ou
chercher un schéma général pour un décodeur n → 2n .
TD 1 7 8 TD 1

N
"3->8" "MUX8x1_1b"
NW NE I[3:0] O[7:0]
C
hi
SW SE 3->8

S hi

a
b
7
c O[0]
d
A[2:0]
6

N
5
4 0
MUX8x1_1b
I[7:0]
NW 4

5 1
NE
3

C
6 2
2
SW

SE 1
7 3

S
0

F IG . 2 – Circuit de l’afficheur numérique F IG . 3 – Circuits du décodeur et du multiplexeur

Réponse portes ET, recevant le signal Ik correspondant. La porte ET sélectionnée lorsque l’entrée A vaut k
Il suffit de sélectionner une unique combinaison des signaux d’entrée à l’aide de 8 portes ET (sur 3 bits) fournit alors la valeur du signal Ik , les sorties des autres portes ET sont nulles. Il suffit
(à trois entrées). Chaque valeur d’entrée active ainsi un unique signal de sortie du décodeur. donc d’une porte OU à 8 entrées pour produire le signal de sortie du multiplexeur.
Voir la figure 3 et le fichier mux_dec.lgf. Voir la figure 3 et le fichier mux_dec.lgf.

Question 1.2.2
Un multiplexeur 2n × 1 est un circuit combinatoire comprenant une entrée A sur n Exercice 1.3 - Unité arithmétique et logique
bits, 2n entrées I0 , . . . , I2n −1 sur 1 bit, et une sortie O sur 1 bit ; le signal O est égal à
l’entrée Im lorsque A vaut m (en binaire sur n bits). Support : alu_mask.lgf propose une Unité Arithmétique et Logique (ALU) 1-bit
Construire un multiplexeur 8 × 1. On pourra construire une table de Karnaugh, réuti- (comprenant notamment un additionneur 1-bit et un multiplexeur 4 × 1) et un masque
liser le décodeur de la question précédent ou chercher un schéma général. pour une ALU 16-bits.
Réponse L’ALU 1-bit vue en cours propose les opérateurs d’addition, de conjonction et
En suivant le même schéma que le décodeur, on ajoute une quatrième entrée à chacune des 8 de négation ; voir le fichier alu_mask.lgf. On utilise cette « brique de base » pour
TD 1 9 10 TD 1
construire une unité arithmétique et logique 16-bits. On a transformé l’additionneur en a dépassement lorsque les deux entrées sont de signe différent et que le résultat n’a pas le signe
additionneur/soustracteur en lui ajoutant un signal de contrôle ALUKSUB analogue au de ALUSRC1.
signal c vu en cours, et en insérant des XOR pour inverser la deuxième opérande de Le signal V de dépassement ( overflow) est donc défini de la manière suivante :
l’addition.
V = Cout SIGNED ALUKSUB
Question 1.3.1 + Cout SIGNED ALUKSUB
La plupart des unités arithmétiques et logiques génèrent des signaux de condition ; + ALUSRC115 ALUSRC215 ALURES15 SIGNED ALUKSUB
il s’agit de signaux de sortie utilisés par les instructions de branchement conditionnel. + ALUSRC115 ALUSRC215 ALURES15 SIGNED ALUKSUB
Réaliser une ALU 16-bits avec les trois signaux de condition suivants : + ALUSRC115 ALUSRC215 ALURES15 SIGNED ALUKSUB
+ ALUSRC115 ALUSRC215 ALURES15 SIGNED ALUKSUB .
– N vaut 1 lorsque la sortie (16-bits) est strictement négative ;
– Z vaut 1 lorsque la sortie est nulle ; En réalité, le signal de dépassement ne doit être activé que dans le cas d’une addition ou d’une
– P vaut 1 lorsque la sortie est strictement positive. soustraction ; on masque donc le résultat précédent par le NAND des signaux de contrôle de
Réponse l’ALU, ALUK0 et ALUK1 . Voir la figure 4 et le fichier [Link].
Le signal Z est obtenu en calculant le NOR des 16-bits de sortie. Le signal N est égal au
15e bit de sortie de l’ALU (bit de poids fort). Le signal P est facilement obtenu à partir du NOR
de Z et N , puisqu’il est à 1 lorsque la sortie est ni nulle ni négative. Voir le fichier [Link].
Question 1.3.2
Montrer que l’on peut effectuer une soustraction non signée à l’aide d’un opérateur
de soustraction en complément à 2.
Réponse
Pour x, y ∈ {0, . . . , 216 −1}, effectuer la soustraction au sens du complément à 2 est équivalent
à:
x −2 y = x + ȳ + 1 = x + (216 − y) = x − y + 216 mod 216 (1)
Comme l’addition +216 n’influe pas sur les 16 bits de poids faible du résultat, la soustraction
en complément à 2 et de la soustraction sur les entiers naturels conduisent au même résultat. En
revanche, cette addition supplémentaire va modifier la valeur de la retenue : 216 correspond au
bit de la retenue, lui ajouter 1 revient à l’inverser.
Question 1.3.3
On suppose que l’ALU dispose d’un signal SIGNED qui vaut 1 lorsque les calculs
ont lieu en complément à 2 (calculs signés) et 0 sinon (calculs non signés). Définir un
signal V de dépassement de capacité (overflow) pour cette ALU.
Réponse
On appelle V le signal de dépassement de capacité. Supposons que SIGNED = 0. Lorsque
l’on effectue une addition, il y a dépassement (i.e., un résultat supérieur ou égal à 216 ) si la
retenue de sortie vaut 1. Inversement, lorsque l’on effectue une soustraction, on a vu à la question
précédente que le dépassement (i.e., un résultat négatif) correspond à une retenue de sortie à 0.
Supposons désormais que SIGNED = 1. Pour une addition il y a dépassement lorsque les
deux entrées ont le même signe et que le résultat a un signe différent ; pour une soustraction il y
TD 1 11 12 TD 1

ALURES_0
ALURES_1
ALURES_2
ALURES_3
"ALU_1b" ALURES_4
ADD_1b Sum
ALURES_5
ALURES_6
Cin Cout ALUK_SUB ALURES_7
ALURES_8
ALUK_0 ALURES_9
ALUK_1 ALURES_10
ALURES_11
ALURES_12
ALU_1b ALURES_13
ALURES_14
ALURES_15 Z
ALUK_0 ALUK_SUB P
ADD_1b ALUK_1
N
ALUK_SUB ALU_1b ALU_1b ALU_1b ALU_1b ALU_1b ALU_1b ALU_1b ALU_1b ALU_1b ALU_1b ALU_1b ALU_1b ALU_1b ALU_1b ALU_1b ALU_1b
Cout
MUX4x1_1b ADD/SUB V
SIGNED
ALUSRC1_0
ALUSRC1_1 SIGNED=0
ALUSRC1_2
ALUSRC1_3
ALUSRC1_4
ALUSRC1_5
ALUSRC1_6
ALUSRC1_7
ALUSRC1_8 SIGNED=0
ALUSRC1_9
ALUSRC1_10
ALUSRC1_11
ALUSRC1_12
ALUSRC1_13
ALUSRC1_14
ALUSRC1_15 SIGNED=1
ALUSRC2_0
ALUSRC2_1
ALUSRC2_2
ALUSRC2_3
ALUSRC2_4
ALUSRC2_5
ALUSRC2_6 OVERFLOW
ALUSRC2_7
ALUSRC2_8 SIGNED=1
ALUK_0 ALUSRC2_9
ALUSRC2_10
ALUK_1 ALUSRC2_11
ALUSRC2_12
"ADD_1b" ALUSRC2_13
ALUK_SUB ALUSRC2_14
ALUSRC2_15
SIGNED=1
A S
B ALU_1b
Cout
Cin
SIGNED=1

COMPARISON (ALUSRC1<ALUSRC2)
ALUK=0: ADD ALUK_0
hi ALUK=1: AND ALUK_1 SIGNED
0 N LT
1 ALUK=2: NOT
2
MUX4x1_1b V
3 ALUK=3: don’t care ALUK_SUB
3
ALUSRC1_12
ALUSRC1_13 ALUSRC1_8
ALUSRC1_9 ALUSRC1_4
ALUSRC1_5 ALUSRC1_0
ALUSRC1_1 ALURES_12
ALURES_8
ALURES_13 ALURES_4
ALURES_9 ALURES_0
ALURES_5
ALURES_1
SIGNED ALUSRC1_14
ALUSRC1_15 ALUSRC1_10
ALUSRC1_11 ALUSRC1_6
ALUSRC1_7 ALUSRC1_2
ALUSRC1_3 ALURES_14
ALURES_10
ALURES_15 ALURES_6
ALURES_11 ALURES_2
ALURES_7
ALURES_3

N V
Z
"MUX4x1_1b" ALUSRC2_12
ALUSRC2_13 ALUSRC2_8
ALUSRC2_9 ALUSRC2_4
ALUSRC2_5 ALUSRC2_0
ALUSRC2_1 P LT
ALUSRC2_14
ALUSRC2_15 ALUSRC2_10
ALUSRC2_11 ALUSRC2_6
ALUSRC2_7 ALUSRC2_2
ALUSRC2_3

F IG . 4 – Circuit de l’ALU 16-bits

TD 1 13 14 TD 1

Question 1.3.4
En utilisant l’ALU ci-dessus et en minimisant le nombre de modifications, générer
un signal de comparaison : soient a et b les deux entrées de l’ALU, le résultat de la
comparaison est 1 si a < b, et 0 sinon ; le résultat de la comparaison doit être fourni sur A1_0
A1_1
un signal de sortie supplémentaire. A1_2
A1_3
Réponse
A2_0 S=A1+A2+A3
On effectue la soustraction de a et b en choisissant A2_1
A2_2
ALUK1 ALUK0 = 00 et ALUKSUB = 1. A2_3
Le signal LT ( less than) est mis à 1, soit lorsque la différence est négative, soit lorsqu’elle est 0 1 2 3
Cin Cout
positive et qu’il y a dépassement ; voir la figure 4 et le fichier [Link].

Exercice 1.4 (facultatif) - Accélération de l’addition 0 1 2 3 4

0
A3_0
A3_1
Cet exercice compare plusieurs compromis temps-espace pour des circuits d’accé- A3_2
A3_3
lération de l’addition. Il n’est pas nécessaire d’utiliser DigLog dans cet exercice.
On souhaite effectuer l’addition de n nombres a1 , . . . , an sur 4 bits. Pour cela, on S_0
S_1
peut utiliser une ALU pour calculer a1 + a2 puis ajouter le résultat à a3 , etc. S_2
S_3
S_4
S_5
Question 1.4.1
Pour la somme de 3 entiers sur 4 bits, proposer un circuit dont le temps de traversée
vaut 6 fois celui de l’additionneur 1-bit.
Réponse
On « aligne » un additionneur 4 bits calculant la somme partielle des deux premières opé-
randes avec un additionneur 5 bits dont les opérandes sont le résultat du premier additionneur et
F IG . 5 – Circuit de l’additionneur à trois opérandes
la troisième opérande (le résultat comporte 5 bits). Le circuit résultant est décrit sur la figure 5.
VALIDE ; CELA LES MÈNE NATURELLEMENT À LA SOLUTION ( NOTE : UNE UNITÉ DE TEMPS
Question 1.4.2
= PASSAGE À TRAVERS UN ADDITIONNEUR DANS CET EXERCICE ).
Pour la somme de 3 entiers sur 4 bits, proposer un circuit dont le temps de traversée
On sépare le calcul des sommes partielles sans retenue et des retenues pour éviter de propager
ne vaut que 5 fois celui de l’additionneur 1-bit, contre 6 pour le circuit de la question ces dernières. Dans un deuxième temps, les sommes et les retenues sont ajoutées de manière
précédente. Indication : utiliser l’associativité de l’addition pour retarder la propagation classique pour retrouver la somme totale.
des retenues jusqu’à la dernière étape du calcul ; le circuit obtenu est appelé addition- Le cas de l’addition de trois opérandes est décrit sur la figure 6. Par rapport à la solution de
neur carry-save. la question précédente, on remarque qu’un additionneur 1-bit a pu être supprimé alors même que
Proposer une généralisation de ce circuit pour la somme de n opérandes et une le temps de traversée global a été diminué.
estimation de son temps de traversée. Le cas général consiste à grouper les opérandes par 3 et à calculer les sommes partielles
Réponse sans retenue et les retenues en une seule traversée parallèle, puis à recommencer sur les 2/3
I L FAUT SUGGÉRER AUX ÉTUDIANTS DE CONCEVOIR UN ADDITIONNEUR POUR 3 NOMBRES d’opérandes résultant (en tenant compte des alignements respectifs des sommes partielles et des
À PARTIR D ’ ADDITIONNEURS 1- BIT, SANS SE PRÉOCCUPER DES PROBLÈMES DE TEMPS , PUIS
retenues), jusqu’à n’obtenir que deux opérandes que l’on somme de manière classique.
D ’ ÉVALUER , SUR CET ADDITIONNEUR , AU BOUT DE COMBIEN DE TEMPS LE RÉSULTAT EST
Le nombre k d’étages d’additionneurs carry-save 1-bit vérifie n(2/3)k ≤ 2, i.e., k ≤ (lg n −
TD 1 15 16 TD 1

– on ne considérera que des nombres normalisés ;

– lorsqu’une valeur ne peut être représentée par un nombre normalisé, on déclenche
un signal d’erreur ERROR ;
A1_0
A1_1 – le circuit ne pourra effectuer qu’un arrondi par élimination des bits de poids faible
A1_2
A1_3 non représentables.
CS=A1+A2+A3
A2_0
A2_1 Question 1.5.1
A2_2
A2_3 Déterminer les différentes étapes nécessaires à l’opération de multiplication flot-
tante
0 1 2 3 Réponse
A3_0
A3_1
A3_2 Début
A3_3

Multiplication des mantisses

0 1 2 3
Cin Cout On conserve les 25 bits de poids fort
0
CS_0
CS_1
CS_2
CS_3 Normalisation :
CS_4
CS_5 décalage de 1 bit à gauche éventuel,
conservation des 23 bits suivant le bit de poids fort

F IG . 6 – Circuit de l’additionneur carry-save à trois opérandes Addition des exposants

1)/ lg 3. D’autre part, la somme finale séquentielle porte sur ⌈n/2⌉ + 4 bits. Le temps de traversée
global est de l’ordre de n/2 + lg n/ lg 3. Dépassement ?
Cette structure récursive fondée sur l’additionneur carry-save est appelée arbre de Wallace.
Ces arbres sont utilisés pour accélérer les multiplieurs, pour compter le nombre de bits à 1 dans
un registre, etc. Voir Patterson et Hennessy « Computer Organization and Design » pp. 331 et Erreur
332. Mise à jour du signe

Exercice 1.5 (facultatif) - Multiplieur flottant

Fin
On étudie la structure d’un multiplieur pour des nombres à virgule flottante. On
considère une représentation simplifiée, inspirée de la norme IEEE 754 pour les flottants
32 bits :
TD 1 17 18 TD 1
Question 1.5.2
Identifier tous les composants nécessaires à la réalisation du multiplieur (hors contrôle).
Indiquer les jonctions nécessaires entre les différents composants et leur taille.
Réponse
D’une part un registre 48 bits alimenté par un multiplexeur 96 × 48 pour choisir entre les
données initiales — 0 sur les 24 bits de poids fort et l’entrée 1 du multiplieur sur les 24 bits de
poids faible — ou le décalage à gauche. D’autre part, un additionneur 24-bits alimenté par les 24
bits de poids fort du registre et par le produit entre le bit 23 du registre et l’entrée 2 du multiplieur.
La mantisse est obtenue par un décalage à gauche de 1-bit éventuel — lorsque le bit 47 est à
0 — à l’aide d’un multiplexeur 48 × 24.
L’exposant est calculé à l’aide de 3 additions 8 bits enchaînées — pour soustraire le biais
de 127 puis ajouter les exposants et incrémenter éventuellement de 1 si la mantisse n’a pas été
décalée.
Question 1.5.3
Indiquer, pour chaque étape, les valeurs que doivent prendre les différents signaux
d’entrée des composants.
Le circuit de contrôle du multiplieur flottant sera réalisé dans le cadre du prochain
TD.
Réponse
Il y a dépassement de capacité — ERROR = 1 — lorsque la somme modulo 2 des retenues
des trois additionneurs du circuit de calcul de l’exposant vaut 0. En effet, les somme des deux
premières retenues correspond à la négation du bit 8 de l’exposant (il manque le bit 8 de l’expo-
sant de l’entrée 1), et la deuxième somme correspond à la négation du bit 8 de l’exposant final.
On calcule donc ERROR en combinant les trois retenues de sorties avec une porte XNOR et une
porte XOR.
Pour le reste, voir la correction du multiplieur entier et le circuit microprogrammé du multi-
plieur flottant dans le TD suivant.