Exercices (énoncés et corrigés) de logique

Sommaire

  1. Décodage (notion de décodeur)
  2. Génération de fonctions
  3. Représentation en complément à 2 (CA2)
  4. Adddition en complément à 2
  5. Soustraction et comparaison
  6. Multiplication
  7. Calcul du maximum entre deux nombres

1. Décodage

Le décodeur est un circuit combinatoire à l'entrée duquel est appliqué un code binaire de n bits. Ce circuit possède N sorties (avec N = 2n, en général). A chaque valeur du code d'entrée, il y a une seule sortie à l'état haut, toutes les autres sont à l'état bas. Les entrées d'un décodeur sont souvent appeléesadresses, car elles expriment en binaire le numéro décimal de la sortie activée. Les décodeurs peuvent être utilisés pour l'adressage de mémoires et la génération de fonctions logiques.

1.1 Décodeur BCD

Le BCD ("binary coded decimal") est un code de 4 bits dont seules les 10 premières combinaisons de 0 à 9 sont employées. Les combinaisons restantes de 10 à 15 ne sont jamais utilisées. Un décodeur BCD est donc un décodeur qui a 4 entrées et 10 sorties.

Question: Réalisez ce décodeur en considérant que si l'une des 6 combinaisons non autorisées est à l'entrée, toutes les sorties sont à l'état inactif "0".

Chaque sortie est active quand le minterme qui lui est associé est actif. Ainsi, en considérant les sorties s0 à s9 et les entrées e0 à e3, les équations des sorties sont :

     __ __ __ __               __    __ __               __                  
s0 = e3.e2.e1.e0          s4 = e3.e2.e1.e0          s7 = e3.e2.e1.e0          
     __ __ __                  __    __                     __ __ __          
s1 = e3.e2.e1.e0          s5 = e3.e2.e1.e0          s8 = e3.e2.e1.e0          
     __ __    __               __       __                  __ __            
s2 = e3.e2.e1.e0          s6 = e3.e2.e1.e0          s9 = e3.e2.e1.e0          
     __ __                
s3 = e3.e2.e1.e0        

1.2 Décodeur de grande capacité

Si le nombre N est très élevé, on peut imaginer réaliser le décodage en cascadant des décodeurs de tailles moins importantes.

Question: Concevez un décodeur binaire 5 entrées/32 sorties à partir de 2 décodeurs binaires 4 entrées/16 sorties. Quelle doit être la modification à apporter au décodeur 4 entrées/16 sorties pour créer facilement le décodeur 5 entrées?

2 décodeurs 4 vers 16 peuvent être pilotés par les 4 bits de faibles poids de l'entrée (e0-3). Le bit de fort poids e4 sert à autoriser les sorties de l'un des 2 décodeur. Un décodeur 1 bit composé d'un simple inverseur est utilisé pour piloter les sorties. Quand e4 est à 0 , les sorties du décodeur de faible poids sont autorisées à sortir par le biais de porte ET; quand e4 est à 1 , ces sont les sorties du décodeur de fort poids qui sont autorisées. Si les décodeur ont une entrée de validation "en" , Il suffit d'utiliser ce décodeur 1 bit sur les entrées "en" des 2 décodeurs comme le montre la figure 3.1.

Figure 3.1

Question: Concevez un décodeur binaire 8 entrées/256 sorties en utilisant le décodeur 4 entrées/16 sorties précédement modifié.

Dans ce cas un décodeur 4 vers 16 sur les bits de forts poids de l'entrée peut générer 16 sorties de sélection "Sel". Ces sorties sont reliées aux entrées "en" de 16 décodeurs 4 bits de faibles poids de façon à en autoriser 1 parmi 16. Il faut donc un total de 17 décodeurs comme le montre la figure 3.2.

Figure 3.2

 

2. Génération de fonctions

Un transcodeur ou convertisseur est un circuit combinatoire à x entrées et y sorties. A chaque code d'entrée de x bits correspond un code de sortie y bits. Les décodeurs que nous avons étudiés dans l'exercice précédent sont donc des cas particuliers de transcodeurs.

Nous désirons réaliser la fonction de transcodage d'un code BCD vers un code "2 parmi 5". Dans le code "2 parmi 5", il y a toujours deux bits à "1" et 3 bits à"0". La table de vérité est indiquée ci-dessous (Table 4.1).

  • i indique la valeur de la combinaison (ou minterme) en décimal
  • Les entrées sont a b c d
  • Les sorties sont F4F3F2F1F0
  • Si i > 9 l'état des sorties est indifférent
Table 4.1
i d c b a F4 F3 F2 F1 F0
0 0 0 0 0 1 1 0 0 0
1 0 0 0 1 0 0 0 1 1
2 0 0 1 0 0 0 1 0 1
3 0 0 1 1 0 0 1 1 0
4 0 1 0 0 0 1 0 0 1
5 0 1 0 1 0 1 0 1 0
6 0 1 1 0 0 1 1 0 0
7 0 1 1 1 1 0 1 0 0
8 1 0 0 0 1 0 0 0 1
9 1 0 0 1 1 0 0 1 0

2.1 Décodeur BCD

Question  Réalisez la fonction à l'aide d'un décodeur et de quelques portes logiques

Un décodeur 4 bits peut fournir les termes Si, comme vu dans l'exercice précédent, A l'aide de ces termes (qui sont les sorties du décodeur) et par analyse de la table de vérité, on obtient :

Le circuit correspondant est celui de la Figure 4.1.

Figure 4.1

2.2 Multiplexeurs

Question: Ecrivez l'équation logique d'un multiplexeur 16 entrées (et donc 4 entrées de sélection) et comparez à l'expression d'une fonction logique quelconque à 4 entrées.

Un multiplexeur à quatre entrées de sélection et 16 données (D0 à D15) fournit une sortie donnée par F = m0D0 + m1D1 + ... + m14D14 +m15D15, où les mi sont les mintermes sur les entrées de sélection.

Une fonction logique de quatre entrées a une équation générique de la forme F = m0F(0,0,0,0) + m1F(0,0,0,1) + ... + m14F(1,1,1,0) +m15F(1,1,1,1), où les misont les mintermes sur les 4 entrées.

En faisant l'analogie entre les 2 équations, il apparait qu'un multiplexeur 16 entrées peut servir à générer n'importe quelle fonction logique de 4 entrées. Les 4 entrées de la fonction correspondent aux entrées de sélection du multiplexeur et les 16 entrées Di du multiplexeur sont forcées à la valeur de la fonction logique pour le minterme i associé.

Par exemple, nous obtenons pour cet exercice :

MUX4 => F4 = m0D0 + m7D7 + m8D8 + m9D9 (D0 = D7 = D8 = D9 = 1)

MUX3 => F3 = m0D0 + m4D4 + m5D5 + m6D6 (D0 = D4 = D5 = D6 = 1)

MUX2 => F2 = m2D2 + m3D3 + m6D6 + m7D7 (D2 = D3 = D6 = D7 = 1)

MUX1 => F1 = m1D1 + m3D3 + m5D5 + m9D9 (D1 = D3 = D5 = D9 = 1)

MUX0 => F0 = m1D1 + m2D2 + m4D4 + m8D8 (D1 = D2 = D4 = D8 = 1)

 

3. Représentation en complément à 2

Question: Donner la représentation en CA2 des nombres suivants : 
-8, +8, -30, -52, +15.

Dans la représentation en complément à 2, le bit de poids le plus fort (MSB) indique le signe du nombre représenté. Il est égal à 0 pour les nombres positifs, à 1 pour les nombres négatifs. Pour les nombres positifs, on obtient donc :

  • +8 : 01000
  • +30 : 011110
  • +52 : 0110100

Pour déterminer la représentation des nombres négatifs, on peut utiliser la relation : -B=NOT(B)+1. Il vient :

  • -8 : 10111+1 = 11000
  • -30 : 100001+1=100010
  • -52 :1001011+1=1001100

On verra dans la question suivante qu'il existe un moyen plus direct de trouver la représentation des nombres négatifs.

Soit B un nombre codé en CA2 sur n bits : (bn-1 bn-2 ... b0).

Question Comment obtient-on la valeur de B à partir de sa représentation lorsqu'il est positif ? lorsqu'il est négatif ?

On peut associer au nombre B, la valeur R positive de sa représentation binaire. Par exemple, le tableau suivant donne pour tous les nombres B compris entre -4 et +3, leur représentation en complément à 2 sur 3 bits, et la valeur R positive associée à cette représentation.

  B     r2 r1 r0     R  
3 011 3
2 010 2
1 001 1
0 000 0
-1 111 7
-2 110 6
-3 101 5
-4 100 4

Pour obtenir la représentation en CA2 des nombres B négatifs, il suffit d'appliquer à ces nombres la translation : R= B+8

Pour les nombres B positifs, on a directement : R=B.

Plaçons nous dans le cas général d'un nombre codé en CA2 sur n bits dont la représentation est : 
rn-1 rn-2 ... r0.

La valeur R associée à cette représentation est :

 

Si rn-1 est nul, B est positif et on a (eq.1) :

 

Si rn-1 est égal à 1, B est négatif et on a (eq.2) :

 

Les expressions 1 et 2 peuvent être mises sous la forme (eq. 3) :

 

On peut appliquer directement cette dernière relation pour déterminer la représentation en CA2 d'un nombre négatif (par ex : -30). Il suffit de rechercher la puissance de 2 immédiatement inférieure au nombre (ex : -32) - elle donne la position du MSB - puis de trouver la quantité positive (+2) à lui ajouter pour obtenir le nombre. Par exemple : 
-30=-32+2 = -25+21soit : 100010 
-8 = -8 + 0 soit : 1000

Par ailleurs, pour déterminer la valeur d'un nombre négatif à partir de sa représentation, on procède de manière inverse. Par exemple : 
101101 : -25+23+22+20= -19

Q.10 Donner la représentation en CA2 des nombres +15, -12 aux formats 5 bits puis 7 bits.

Sur 5 bits :

+ 15 : 01111 
- 12 : = -16 +4 : 10100

Sur 7 bits :

+ 15 : 0001111 
- 12 : = -64 + 32 + 16 + 4 : 1110100

Q.11 D'une façon générale, comment peut-on étendre la représentation d'un nombre codé en CA2 sur n bits, à une représentation sur p bits, avec p plus grand que n ?

On a remarqué dans la question précédente qu'il suffit de répéter le bit de signe jusqu'à atteindre le nombre de bits désirés. On parle d'"extension de signe". On peut montrer ceci dans le cas général. Les cas positifs étant immédiats, nous nous interessons seulement aux cas négatifs.

Soit B un nombre négatif codé sur n bits. Pour étendre la représentation de ce nombre à n+1 bits, il faut faire apparaitre dans l'expression de B (cf eq. 3) la puissance -2n. Or :
-2 n-1 = -2 n + 2 n-1
-2 n-1 bn-1= -2 n bn-1 + 2 n-1 bn-1 (4)

D'où : 

On peut itérer la relation (4) autant de fois que nécessaire pour étendre la représentation au nombre de bits désirés. Par exemple :

-12 = -16 + 4 : 10100 
-12 = -32+16 + 4 : 110100 
-12 = -64 + 32 + 16 + 4 : 1110100 
etc ...

4. Addition en complément à 2

Question: Quel est l'intervalle de variation d'un nombre codé en CA2 sur n bits ?

On déduit aisément de l'équation (3) que l'intervalle de variation d'un nombre B codé sur n bits est :

 

Soient A et B deux nombres codés en CA2 sur n bits et S la somme de ces 2 nombres.

Q.13 Quel est l'intervalle de variation de S ? En déduire le nombre de bits nécessaires à son codage.

L'intervalle de variation de S est : 

L'inégalité précédente montre que la représentation de S doit utiliser n+1 bits

Q.14 Réaliser en binaire les additions suivantes : 30 + 8, 30 + (-8), (-30) + 8, (-30) + (-8).

Les opérandes sont codés sur 6 bits, le résultat sera codé sur 7 bits : 

On peut remarquer que lorsque les opérandes sont de signes opposés (par ex : -30 + 8, -8 + 30), on pourrait se contenter de n bits pour coder le résultat. Cependant en pratique, pour ne pas avoir à distinguer dans quel cas de figure on se place, on réalise l'addition sur n+1 bits. Il est alors impératif d'étendre les opérandes à n+1 bits par des extensions de signe avant de réaliser l'addition, pour obtenir un résultat juste.

 

5. Soustraction, Comparaison

On désire réaliser un opérateur capable d'effectuer la comparaison de 2 nombres positifs A et B codés sur 4 bits. La sortie S de l'opérateur vaut '1' si A est strictement inférieur à B, '0' sinon. 
S=1 si A < B, 
S=0 si A > B ou A = B

Q Proposer une solution à l'aide d'un soustracteur.

La différence R des opérandes A et B s'exprime sur 5 bits. Le bit r(4) indique le signe du résultat : 
r(4)=1 si A < B, 
r(4)=0 si A > B ou A = B

Par conséquent la fonction S à réaliser est directement le MSB de R.

Figure 7.1 : soustracteur

Une autre solution appelée "comparaison MSB en tête" consiste à comparer bit à bit les nombres A et B en commençant par les bits de poids forts. L'algorithme utilisé est le suivant :
S=1
SI  (a3 < b3)
OU ((a3 = b3) ET (a2 < b2))
OU ((a3 = b3) ET (a2 = b2) ET (a1 < b1)
OU ((a3 = b3) ET (a2 = b2) ET (a1 = b1) ET (a0 < b0))

Question Construire l'opérateur élémentaire à 2 entrées aet bdont les sorties ii (inférieur) et ei (égal) vérifient : 
ii=1 si ai<bi , ii=0 sinon. 
ei=1 si ai=bi , ei=0 sinon.

La table 7.1 donne les tables de vérité des fonctions ii et ei.

Table 7.1 : soustracteur
  ai     bi     ei=(ai=bi)     ii=(a<bi)  
0 0 1 0
0 1 0 1
1 0 0 0
1 1 1 0

On déduit de ce tableau les expressions booléennes des fonctions ii et ei :

Le schéma cablé de l'opérateur élémentaire est donné par la figure 7.2.

 

Figure 7.2 : opérateur élémentaire

Question  En utilisant l'opérateur construit précédemment, proposer le schéma complet du comparateur.

Il suffit de reformuler l'algorithme de façon à faire apparaitre dans l'expression de la fonction S, les fonctions élémentaires ii et ei. Il vient : 
S=1
SI  (i3) OU ((e3) ET (i2)) OU ((e3) ET (e2) ET (i1) OU ((e3) ET (e2) ET (e1) ET (i0))

La figure 7.3 donne la structure du comparateur 4 bits.

 

Figure 7.3 : comparateur 4 bits

Question Comment peut-on généraliser simplement ce comparateur à n bits ?

Soient A et B 2 nombres codés sur n bits. On réalise leur comparaison bit à bit comme précédemment, en partant des MSB. A l'étape i, on peut écrire :
   (an-1 an-2 ... an-i   < bn-1 bn-2 ... bn-i )
si (an-1 an-2 ... an-i+1 < bn-1 bn-2 ... bn-i+1)
ou (an-1 an-2 ... an-i+1 = bn-1 bn-2 ... bn-i+1) et (ai < bi)

Notons :
En-i+1= (an-1 an-2 ... an-i +1= bn-1 bn-2 ... bn-i +1)
In-i+1= (an-1 an-2 ... an-i +1 < bn-1 bn-2 ... bn-i +1)

Il vient :
In-i = In-i +1 OU ( En-i+1 ET i i )

On a par ailleurs :
En-i = En-i+1 ET ei

La figure 7.4 donne la structure de l'opérateur réalisant les fonctions Ei et Ii en fonction des résultats Ei+1 et Ii+1 obtenus à l'étape précédente. La figure 7.5 illustre l'utilisation de cet opérateur pour le comparateur 4 bits étudué dans la question précédente. Il est à noté que les cablages des figures 7.3 et 7.5 sont identiques (aux extrémités près). La figure 7.6 donne enfin l'application de cet opérateur à la construction d'un comparateur n bits.

Figure 7.4 : comparateur élémentaire modifié
Figure 7.5 : comparateur 4 bits
Figure 7.6 : comparateur n bits

 

6. Multiplication

Question Réaliser à la main l'opération : 1001 x 1100 (9x12).

On considère dans cette première question les opérandes codés en binaire positif.

La multiplication binaire s'effectue de la même façon qu'en décimal. On effectue la multiplication de l'opérande A par chacun des bits de B. On réalise ensuite la somme de chacun des "produits partiels" ainsi obtenus.

Question Proposer le schéma d'un multiplieur de 2 nombres positifs de 4 bits. On dispose pour cela d'additionneurs 4 bits.

Dans le cas général, B s'écrit :
B = b3 23 + b2 22+ b1 21 + b0 20

D'où :
B x A = ( A x b3 ) x 23 + ( A x b2 ) x 22 + ( A x b1 ) x 21 + ( A x b0 ) x 20
B x A = P3x 23 + P2 x 22 + P1 x 21 + P0 x 20

avec Pi = A x bi

La représentation binaire d'un produit partiel P i est simplement obtenue à l'aide de 4 portes ET : 
Pi : ( a3 ET bi ) ( a2 ET bi) ( a1 ET bi ) ( a0 ET bi )

Il faut ensuite réaliser l'addition des produits partiels Pi , en prenant soin au préalable de les multiplier par 2, ce qui correspond à un décalage de i positions vers la gauche. Cette addition utilise des additionneurs 4 bits. Le schéma du mulitplieur est représenté par la figure 8.1.

Figure 8.1 : multiplieur 4x4

Question Comment faut-il modifier ce schéma pour permettre la multiplication de 2 nombres A et B en complément à 2 ?

Nous allons voir que la multiplication en complément à 2 introduit deux légères modifications. En effet, B s'écrit maintenant :
B = - b3 23 + b2 22+ b1 21 + b0 20

D'où :
B x A = ( - A x b3 ) x 23 + ( A x b2 ) x 22 + ( A x b1 ) x 21 + ( A x b0 ) x 20

  1. Le produit partiel P3 doit maintenant être retranché aux autres produits partiels et non plus ajouté. La relation précédente s'écrit encore :
    B x A = ( ( NOT( A )+1) x b3 ) x 23 + ( A x b2 ) x 22 + ( A x b1 ) x 21 + ( A x b0 ) x 20 
    La figure 8.2 montre que 4 inverseurs sont utilisés pour réaliser la complémentation de l'opérande A. Par ailleurs, le bit b3 est utilisé comme retenue entrante dans le dernier additionneur. Lorsque b3 est égal à 1 ( B négatif), on réalise ainsi l'opération ( NOT ( A ) + 1) x b3.
     
  2. Les produits partiels étant maintenant des nombres signés, il est nécessaire avant de réaliser leur addition de pratiquer des extensions de signe. Ces extensions sont simplement réalisées par cablage. On voit cependant, que la taille des produits partiels augmentant, la taille des additionneurs augmente également.
Figure 8.2 : multiplieur 4x4 signé

 

7 Calcul du maximum deux nombres

Le calcul du maximum entre deux nombres est un problème proche du comparateur (exercice 5) .

Une solution simple consiste à calculer la différence entre les deux nombres et utiliser un multiplexeur piloté par la retenue sortante pour choisir le bon résultat.

Question : peut on construire une structure itérative calculant le résultat bit par bit en partant des poids forts ?

  • Appelons A et B les deux nombres dont on veut trouver le maximum et Ai et Bi les bits de poids i de ces nombres
  • Appelons M le maximum de A et de B , et Mi le bit de poids i de M
  • Supposons A et B entiers positifs codés sur N bits

Les bits de poids fort de A et B sont An-1 et Bn-1 .

Nous pouvons directement trouver Mn-1 le bit de poids fort de M : il vaut 1 si un au moins des bits An-1 et Bn-1  est égal à 1:   An-1 <= An-1 | Bn-1

De manière générale, le bit de poids i de M dépend des décisions prises dans les poids plus élevés.

Supposons que nous disposions pour le calcul du bit de poids i de deux signaux nous informant sur la décision prise au poids i+1 :

  • AsupBi+1 signifie que nous savons que A est supérieur à B
  • BsupAi+1 signifie que nous savons que B est supérieur à A
  • Les signaux AsupBi+1 et  BsupAi+1  ne sont pas égaux à un en même temps.

Nous pouvons calculer les signaux équivalents au poids i.:

AsupBi+1 BsupAi+1 Ai Bi AsupBi BsupAi Mi Commentaire
0 0 0 0 0 0 0 aucune décision n'a été prise dans les poids supérieurs, Ai est égal à Bi, il n'y a pas de décision au niveau i mais on sait que Mi = 0
0 0 0 1 0 1 1 aucune décision n'a été prises dans les poids supérieurs. Bi > Ai donc une décision est prise au poids i : Mi=Bi
0 0 1 0 1 0 1 aucune décision n'a été prises dans les poids supérieurs. Ai > Bi donc une décision est prise au poids i : Mi=Ai
0 0 1 1 0 0 1 aucune décision n'a été prise dans les poids supérieurs, Ai est égal à Bi, il n'y a pas de décision au niveau i mais on sait que Mi = 1
0 1 x x 0 1 Bi La décision au poids i reproduit la décision déjà prise
1 0 x x 1 0 Ai La décision au poids i reproduit la décision déjà prise

 

Sous forme de "pseudo code SystemVerilog" les équations des signaux sont :

AsupBi &lt;= AsupBi+1  | (~BsupAi+1 &amp;  Ai &amp; ~Bi )
BsupAi &lt;= BsupAi+1  | (~AsupBi+1 &amp;  Bi &amp; ~Ai )
Mi &lt;= AsupBi &amp; Ai  | BsupAi &amp; Ai | Ai &amp; Bi

On peut donc construire un bloc de calcul de base, et créer par simple assemblage un calcul de Max allant du poids le plus fort vers le poids le plus faible.

 

Ce calcul de génère bit à bit le résultat du max, alors que le calcul de maximum basé sur l'arithmétique et un multiplexeur génère tout le mot d'un coup après l'arrivée de la retenue sortante du soustracteur.