EN102 : Logique combinatoire et séquentielle - Introduction

Introduction Représentation des nombres dans une base b Fonctions logiques et Algèbre de Boole Les circuits combinatoires Les circuits séquentiels synchrones

EN102 : Logique combinatoire et séquentielleIntroduction

Camille Leroux

Camille LEROUX [email protected]

EN102 : Logique combinatoire et séquentielle 1 / 142


Objectif final

Vidéo projet final



./fig/IMG_8723.MOV


1 Introduction

2 Représentation des nombres dans une base b

3 Fonctions logiques et Algèbre de Boole

4 Les circuits combinatoires

5 Les circuits séquentiels synchrones




Objectifs

Plan

1 IntroductionObjectifsOrganisation et évaluation




Objectifs

Quelques notions abordées

• Représentation des nombres en bases 2, 8, 10 et 16

• Complément à 2

• Arithmétique binaire (addition, soustraction, comparaison, multiplication)

• Algèbre de Boole (théorème de De Morgan, formes canoniques, formes simplifiées,Tableau de Karnaugh, ...)

• Logique combinatoire (portes logiques, multiplexage, décodage, ...)

• Le principe de la mémorisation de l’information (bascule, registres)

• Logique séquentielle (compteur, machine d’états)

• Circuits FPGA

• ...




Objectifs

Quelques objectifs pédagogiques

• Maîtriser la représentation de l’information dans les basesbinaires, octales et hexadécimales.• Maîtriser l’arithmétique binaire élémentaire : complément à 2,

addition, soustraction, multiplication.• Concevoir des circuits numériques intégrant à la fois de la logique

combinatoire et de la logique séquentielle synchrone.• Analyser un circuit numérique et en déduire son comportement

dans le temps (chronogramme).• Décrire le comportement d’architectusres de circuits numériques

en utilisant le langage VHDL.• Simuler le comportement d’architectures de circuits numériques.• Synthétiser et implémenter sur circuit FPGA des ciruits

numériques.• ...




Organisation et évaluation

Plan

1 IntroductionObjectifsOrganisation et évaluation





Organisation

Les enseignements se déroulent en plusieurs phases.• 5 Cours d’1h20 (6h40)• 1 QCM d’1h20 (algèbre de Boole et arithmétique binaire)• 6 séances de TD + TP de 4h (24h00)• 4 séances de Projet de 4h (16h00)





Evaluation

• L’évaluation inclut• un QCM,• un rapport de projet,• un examen écrit de 2h.

• Une partie des concepts vus en cours sont évalués lors d’un QCM(Algèbre de Boole, arithmétique binaire).• L’autre partie des concepts est utilisée en TD, TP et projet

(circuits numériques).• Les TP servent à introduire les principes de conception

numériques nécessaires pour la réalisation du projet.• Le projet est évalué par un rapport écrit.• L’ensemble des concepts vus dans les enseignements font

également l’objet d’un examen écrit de 2h.Camille LEROUX [email protected]



Plan

1 Introduction








Représentation

Plan

2 Représentation des nombres dans une base bReprésentationConversionL’addition en base 2Les nombres signésLa soustraction en base 2Dynamique et précisionExercicesAutres bases utiles




Représentation

Représentation polynômiale de l’information

Tout nombre N exprimé dans une base b peut se décomposer sous laforme polynômiale :

N(b) = S(anbn + an−1b

n−1 + ...+ a0b0 + a−1b−1 + ...+ a−mb

−m)

avec {ai,b,n,m} ∈ N+, 0 6 ai < b, S = ±1

Exemples en base 10 :

1337(10) = 1× 103 + 3× 102 + 3× 101 + 7× 100

42, 83(10) = 4× 101 + 2× 100 + 8× 10−1 + 3× 10−2


1011(2) = ...010, 11(2) = ...




Représentation

Représentation polynômiale de l’information

Tout nombre N exprimé dans une base b peut se décomposer sous laforme polynômiale :


n−1 + ...+ a0b0 + a−1b−1 + ...+ a−mb

−m)

avec {ai,b,n,m} ∈ N+, 0 6 ai < b, S = ±1


1337(10) = 1× 103 + 3× 102 + 3× 101 + 7× 100

42, 83(10) = 4× 101 + 2× 100 + 8× 10−1 + 3× 10−2


1011(2) = 1× 23 + 0× 22 + 1× 21 + 1× 20 = 9(10)010, 11(2) = 0× 22 + 1× 21 + 0× 20 + 1× 2−1 + 1× 2−2 = 2, 75(10)Camille LEROUX [email protected]



Représentation

La base binaire en électronique numérique

• Électronique numérique : deux niveaux logiques• Mot binaire est un groupe ordonné d’éléments binaires• Élément binaire : nommé bit (= binary digit)• Mot de W bits → 2W combinaisons distinctes.

Plusieurs tailles de mots binaire sont normalisées :

W Nombre de combinaisons

8 25616 65 53624 16 777 21632 4 294 967 29664 18× 1018




Conversion

Plan





Conversion

Conversion d’une base à une autre

1 Soit un nombre X(b), faire une division par b de ce nombre revient àappliquer un décalage de la virgule vers la droite sur la représentation dunombre.Exemples : 432(10)/10(10) = 43, 2(10), 110101(2)/10(2) = 11010, 1(2)

2 Dans le cas où X(b) est un nombre entier, le chiffre qui apparait après lavirgule correspond au symbole d’ordre 0 (a0).

3 Après troncature du résultat, appliquer une nouvelle division par b permetde faire apparaître le coefficient a1.

=> En effectuant des divisions successives d’un nombre entier dans une base b,on peut obtenir les coefficients de sa représentation dans la base b.Exemple : Convertir le nombre 17(10) en base 2




Conversion

Conversion d’une base à une autre

1 Soit un nombre X(b), faire une multiplication par b de ce nombre revient àappliquer un décalage vers la gauche sur la représentation du nombre.Exemples : 0, 135(10) × 10(10) = 1, 35(10), 0, 110101(2) × 10(2) = 1, 10101(2)

2 Dans le cas où X(b) ne contient pas de partie entière, le chiffre quiapparait avant la virgule correspond au symbole d’ordre -1 (a−1).

3 Après suppression de la partie entière du résultat, appliquer une nouvellemultiplication par b permet de faire apparaître le coefficient a−2.

=> En effectuant des multiplications successives d’un nombre n’ayant pas departie entière, dans une base b, on peut obtenir les coefficients de sareprésentation dans la base b.Exemple : Convertir le nombre 0, 625(10) en base 2. Même chose pour le nombre0, 1(10)




Conversion

Exercices

1 Convertir les nombres binaires suivants en décimal1 101012 11,1013 1011,14 111,11

2 Convertir les nombres décimaux suivants en binaire sur 8 bits1 612 933 1,254 0,186




L’addition en base 2

Plan





L’addition en base 2

Addition binaire, sur 8 bits

Même principe qu’en décimal :

1 1 1 1

52 → 0 0 1 1 0 1 0 0+ 45 → 0 0 1 0 1 1 0 1

= 97 → 0 1 1 0 0 0 0 1Attention au dépassement de capacité !




Les nombres signés

Plan





Les nombres signés

Représentations des entiers signés

2 représentations possibles :

• Signe + magnitude

• x = (−1)S.W−2∑i=0

ai2i

• 1 bit de signe (poids fort), (W − 1) bits pour le module• 2 représentations pour 0• Additionneurs différents suivant le signe

• Complément à deux (CA2)

• x = −2SS+W−2∑i=0

ai2i =⇒ x > 0, x = x+ 1

• 2W−1 − 1 valeurs positives et 2W−1 valeurs négatives• Une seule représentation pour 0• Additionneur unique




Les nombres signés

Complément à 10

Constat : En base 10 : 427 = 00427 = ...00427Problème : Trouver une représentation de X telle que :

...X4 X3 X2 X1 X0

+ ...0 0 4 2 7

= ...0 0 0 0 0→ X = ..99573

• X = ..99573 est une représentation de l’opposé de 427 car427+ X = 0• L’opposé d’un nombre Y en base 10 se représente comme le

complément à 9 de Y auquel on ajoute 1.• Exemple : Calculez 7-15 en utilisant le complément à 10• De manière encore plus générale, l’opposé d’un nombre Y en baseb se représente comme le complément à (b− 1) de Y auquel onajoute 1




Les nombres signés

Complément à 2

Constat : En base 2 : 110 = 00110 = ...00110Problème : Trouver une représentation de X telle que :

...X4 X3 X2 X1 X0

+ ...0 0 1 1 0

= ...0 0 0 0 0→ X = ..11010

• L’opposé d’un nombre Y en base 2 se représente comme lecomplément à 1 de Y auquel on ajoute 1.• le MSB d’un nombre positif est toujours 0• le MSB d’un nombre négatif est toujours 1• On peut calculer (−Y) à partir du complément de Y, ce dernier

s’obtenant par une simple inversion des bits de Y : (−Y) : Y + 1




Les nombres signés

Exemples CA2, sur 4 bits

7→ 0111• On complémente : 1000• On ajoute 1 : 1001→ −7

1→ 0001• On complémente : 1110• On ajoute 1 : 1111→ −1




La soustraction en base 2

Plan






Addition binaire signée, sur 8 bits

Même principe grâce à la représentation CA2 :

52 → 0 0 1 1 0 1 0 0+ -45 → 1 1 0 1 0 0 1 1

= 7 → 0 0 0 0 0 1 1 145 → 0 0 1 0 1 1 0 1

+ -52 → 1 1 0 0 1 1 0 0

= -7 → 1 1 1 1 1 0 0 1

Attention au dépassement de capacité !





CA2 et extension du nombre de bits

7 01116 01105 01014 01003 00112 00101 00010 0000-1 1111-2 1110-3 1101-4 1100-5 1011-6 1010-7 1001-8 1000

Extension sur 8 bits :

7 000001116 000001105 000001014 000001003 000000112 000000101 000000010 00000000-1 11111111-2 11111110-3 11111101-4 11111100-5 11111011-6 11111010-7 11111001-8 11111000





Exercice

Soit deux opérandes X = 192 et Y = 78 que l’on souhaite représenteren CA2.

1 Combien de bits faut-il pour représenter ces deux nombressachant qu’il seront codés au même format ?

2 Réaliser les opérations suivantes :1 A = X + Y2 B = X - Y3 C = -X + Y4 D = -X - Y

3 Quelles sont les précautions à prendre pour que les résultat soientcorrects ?




Dynamique et précision

Plan






Codage des données réelles à valeur dans R

2 formats sont possibles :• Virgule fixe

• Virgule flottante





Virgule fixe

Pour pouvoir effectuer des opérations arithmétiques, dans le cas de lavirgule fixe, il faut savoir où est placée la virgule.Représentation Qm :

• m bits pour la partie fractionnaire,• Résolution : q = 2−m

Nous avons donc une dynamique limitée par la précision et le nombrede bits total





Dynamique et précision en virgule fixe


n−1 + ...+ a0b0 + a−1b−1 + ...+ a−mb

−m)

avec {ai,b,n,m} ∈ N+, 0 6 ai < b, S = ±1La dynamique ∆ d’un format de représentation, est la différence entre

la plus grande et la plus petite valeur représentable dans ce format.La résolution δ est la différence entre deux valeurs consécutivesreprésentées dans ce format.Pour les nombres non-signés au format (b,n,m) :∆ = bn+1 − b−m et δ = b−m

Exemple : Quelle est la dynamique et la résolution offerte par leformat (10,1,1) ? (2,1,2) ?Camille LEROUX [email protected]




Dynamique et précision en virgule fixe

Format (10,1,1) :b = 10,n = 1,m = 1 => ∆ = 99.9 et δ = 0.1Format (2,1,2) :b = 2,n = 1,m = 2 => ∆ = 3.75 et δ = 0.25





Virgule flottante

Permet d’augmenter la dynamique mais utilisation plus complexe

N =M× 2E

M : Mantisse, E : ExposantSur 32 bits, 1 bit de signe, 8 bits pour l’exposant et 23 pour la

mantisse (Norme IEEE).




Exercices

Plan





Exercices

Exercices

(1030)10 = ( )2

(1030)10 = ( )8

(1030)10 = ( )16

(ABDE, 1F)16 = ( )8

(ABDE, 1F)16 = ( )10

(31, 35)10 = ( )2 (sur 8 bits)

(34, 703125)10 = ( )2 (sans approximation)




Exercices

Exercices

(10001001)Q1 = ( )10

(10001001)Q2 = ( )10

(10001001)Q3 = ( )10

(10001001)Q4 = ( )10

(10001001)Q6 = ( )10

(21, 25)10 = ( )Q3

(21, 20)10 = ( )Q5




Exercices

Exercices

(10001001)Q1 = (68.5)10

(10001001)Q2 = (34.25)10

(10001001)Q3 = (17.125)10

(10001001)Q4 = (8.5625)10

(10001001)Q6 = (2, 140625)10

(21, 25)10 = (10101010)Q3

(21, 20)10 ≈ (1010100110)Q5




Autres bases utiles

Plan





Autres bases utiles

Bases de numération courantes

Les bases usuelles :• La base décimale : b = 10 (0→ 9)• La base binaire : b = 2 (0→ 1)• La base octale : b = 8 (0→ 7)• La base hexadécimale : b = 16 (0→ F)

Les conversions les plus utilisées :• base 10↔ base b• base 2↔ base 8, 10, 16




Autres bases utiles

Tableau de correspondance

Base 10 Base 2 Base 8 Base 16

0 0 0 01 1 1 12 10 2 23 11 3 34 100 4 45 101 5 56 110 6 67 111 7 78 1000 10 89 1001 11 910 1010 12 A11 1011 13 B12 1100 14 C13 1101 15 D14 1110 16 E15 1111 17 F16 10000 20 10




Autres bases utiles

Les bases octales et hexadécimales

Permettent de condenser la représentation binaire par unetransformation rapide :

• Un chiffre en base octale = 3 bits,

• Un chiffre en base hexadécimale = 4 bits.




Autres bases utiles

La base octale

Soit le mot binaire

X(2) = a6.26 + a5.25 + a4.24 + a3.23 + a2.22 + a1.21 + a0.20

on peut le factoriser comme étant

X(2) = (a6.20)82+(a5.22+a4.21+a3.20)81+(a2.22+a1.21+a0.20)80

soit en base 8 :X(8) = A282 +A181 +A080

Les Ai sont la représentation en base 8 des nombres binairesfactorisés et Ai = {0, 1, ..., 7}




Autres bases utiles

La base hexadécimale

Soit le mot binaire

X(2) = a6.26 + a5.25 + a4.24 + a3.23 + a2.22 + a1.21 + a0.20

on peut le factoriser comme étant

X(2) = (a6.22+a5.21+a4.20).161+(a3.23+a2.22+a1.21+a0.20)160

soit en base 16 :X(16) = A1161 +A0160

Les Ai sont la représentation en base 16 des nombres binairesfactorisés et Ai = {0, 1, ..., F}.




Autres bases utiles

Exemples

1 Convertir les mots binaires suivants en base 8 et 16 :• 100110101(2)• 1110101(2)• 100, 001(2)• 11111111, 1(2)

2 Convertir les mots suivants en base 2 :• 123, 7(8)• 100, 1(8)• 100, 1(16)• FE, 1A(16)

3 Convertir les 2 premiers mots en base 16 et les deux autres enbase 8

4 Convertir les 8 nombres en base 10




Autres bases utiles

Méthodes de conversion

• b→ 10 : Addition des coefficients du polynôme,

• 10→ 2 : Divisions successives par 2,

• 8 ou 16→ 2 : Décomposition de chaque chiffre en 3 ou 4 bits,

• 2→ 8 ou 16 : Groupements des bits par 3 ou 4,

• 8 ou 10→ 16 : Passage par la base 2,

• 10 ou 16→ 8 : Passage par la base 2.




Plan

1 Introduction








Fonctions logiques de bases

Plan

3 Fonctions logiques et Algèbre de BooleFonctions logiques de basesAlgèbre de BooleSimplification des équations logiques





Table de vérité à 2 variables

Table donnant l’état logique de la fonction pour chacune descombinaisons des états des variables.Une fonction logique à N entrées sera représenté par une table à 2N

lignes.

E1 E2 S

0 0 x0 1 x1 0 x1 1 x





Inversion

NON / NOT : S(a) = a

a S(a)

0 11 0

a s





Et

ET / AND : S(a,b) = a · b

a b S(a,b)

0 0 00 1 01 0 01 1 1

ab

s





Ou

OU / OR : S(a,b) = a+ b

a b S(a,b)

0 0 00 1 11 0 11 1 1

ab

s





NAND

NON ET / NAND : S(a,b) = a · b

a b S(a,b)

0 0 10 1 11 0 11 1 0

ab

s





NOR

NON OU / NOR : S(a,b) = a+ b

a b S(a,b)

0 0 10 1 01 0 01 1 0

ab

s





XOR

OU EXCLUSIF / XOR : S(a,b) = a⊕ b = a · b+ a · b

a b S(a,b)

0 0 00 1 11 0 11 1 0

ab

s





XNOR

XNOR : S(a,b) = a⊕ b = a · b+ a · b

a b S(a,b)

0 0 10 1 01 0 01 1 1

ab

s





Exercice

Représentez sous forme de logigramme (schéma de symboles logiquesinterconnectées) la fonction :

S = (A+ B) · (A+ C)

A

B

C

S





Exercice

Représentez sous forme de logigramme (schéma de symboles logiquesinterconnectées) la fonction :

S = (A+ B) · (A+ C)

A

B

C

S




Algèbre de Boole

Plan





Algèbre de Boole

Définition

L’algèbre de Boole définit les outils nécessaires à la description etl’établissement des relations entrées-sorties d’un système logique.Initiée en 1854 par George Boole

Approche algébrique de la logique.

Variable binaire ou booléenne : 2 états : 0 ou 1

Proposition Vraie => 1, Proposition Fausse => 0




Algèbre de Boole

Propriétés des opérateurs de l’algèbre de Boole (1/3)

Involution

a = a

Éléments neutresa+ 0 = aa · 1 = a

Éléments absorbantsa+ 1 = 1a · 0 = 0

Complémentaritéa+ a = 1a · a = 0




Algèbre de Boole


AssociativitéComme avec les opérations habituelles, certaines parenthèses sont inutiles :(a+ b) + c = a+ (b+ c) = a+ b+ c(a · b) · c = a · (b · c) = a · b · c

CommutativitéL’ordre est sans importance :a+ b = b+ aa · b = b · a

Distributivitéa · (b+ c) = a · b+ a · ca+ (b · c) = (a+ b) · (a+ c)




Algèbre de Boole


Idempotencea+ a+ . . .+ a = aa · a · . . . · a = a

Simplificationa+ a · b = a+ ba · (a+ b) = a · b

Redondance (Théorème du consensus)a · b+ a · c+ b · c = a · b+ a · c

(a+ b) · (a+ c) · (b+ c) = (a+ b) · (a+ c)




Algèbre de Boole

Démonstration du théorème du consensus

a · b+ a · c+ b · c = a · b+ a · c+ (a+ a) · b · c= a · b+ a · c+ a · b · c+ a · b · c= a · b · (1+ c) + a · c · (1+ b)= a · b+ a · c

(a+ b) · (a+ c) · (b+ c) = (a+ b) · (a+ c) · (b+ c+ a · a)= (a+ b) · (a+ c) · (b+ c+ a) · (b+ c+ a)= (a+ b) · (1+ c) · (a+ c) · (1+ b)= (a+ b) · (a+ c)




Algèbre de Boole

Théorème de De Morgan

Complément d’une somme

a+ b = a · b

Complément de l’intersection

a · b = a+ b




Algèbre de Boole

Théorème de De Morgan - Démonstration

Démonstration avec tables de vérité

a b a+ b a+ b a b a · b0 0 0 1 1 1 10 1 1 0 1 0 01 0 1 0 0 1 01 1 1 0 0 0 0

a b a · b a · b a b a+ b

0 0 0 1 1 1 10 1 0 1 1 0 11 0 0 1 0 1 11 1 1 0 0 0 0




Algèbre de Boole

Théorème de De Morgan - Démonstration

Démonstration avec tables de vérité

a b a+ b a+ b a b a · b0 0 0 1 1 1 10 1 1 0 1 0 01 0 1 0 0 1 01 1 1 0 0 0 0

a b a · b a · b a b a+ b

0 0 0 1 1 1 10 1 0 1 1 0 11 0 0 1 0 1 11 1 1 0 0 0 0




Algèbre de Boole

Formes canoniques - Définitions

Deux formes :• Première forme canonique : union (+) de mintermes• Seconde forme canonique : intersection (·) de maxtermes

Exemple fonction de 3 variables• Mintermes : a · b · c,a · b · c,a · b · c, . . .• Maxtermes : a+ b+ c,a+ b+ c,a+ b+ c, . . .




Algèbre de Boole

Formes canoniques - Obtention

• Méthode algébrique• Première forme canonique : grâce à (x+ x = 1), on rajoute les

termes manquants.• Seconde forme canonique : utilisation de l’involution,

développement et ajout des termes manquants.• Méthode table de vérité

• Première forme canonique : union des mintermes tels quef(x) = 1.

• Seconde forme canonique : union des mintermes tels quef(x) = 0 puis complémentation.




Algèbre de Boole

Formes canoniques - Exemple

Obtenez les deux formes canoniques, selon les deux méthodes de

f(a,b, c) = a · b+ b · c+ a · c




Algèbre de Boole



f(a,b, c) = a · b+ b · c+ a · c

Première forme :

f(a,b, c) = (a · b)(c+ c) + (b · c)(a+ a) + (a · c)(b+ b)= abc+ abc+ abc+ abc+ abc




Algèbre de Boole



f(a,b, c) = a · b+ b · c+ a · c

Seconde forme :

f(a,b, c) = ab+ bc+ ac

= (a+ b)(b+ c)(a+ c)

= ab+ abc+ ac+ abc

= abc+ abc+ abc

f(a,b, c) = (a+ b+ c)(a+ b+ c)(a+ b+ c)




Algèbre de Boole



f(a,b, c) = a · b+ b · c+ a · c

Table de vérité :

a b c f(a,b,c)

0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1




Algèbre de Boole



f(a,b, c) = a · b+ b · c+ a · c

Table de vérité :

a b c f(a,b,c)

0 0 0 00 0 1 10 1 0 00 1 1 01 0 0 11 0 1 11 1 0 11 1 1 1




Algèbre de Boole

Formes canoniques - Exercice 1

Établir les tables de vérité des fonctions suivantes, puis les écrire sousles formes canoniques :• f1(x,y, z) = x.y+ y.z+ x.z• f2(x,y, z, t) = x+ y.z+ y.z.t• f3(x,y, z) = (x+ y)(x+ y+ z)




Algèbre de Boole

Formes canoniques - Exercice 2

Exprimer sous la première forme canonique les propositions suivantes :• f1(x,y, z) = 1 ssi aucune des variables x,y, z ne prend la valeur

1.• f2(x,y, z) = 1 ssi au plus une des variables x,y, z prend la valeur

0.• f3(x,y, z) = 1 ssi exactement une des variables x,y, z prend la

valeur 1




Simplification des équations logiques

Plan






Principe

• Les formes canoniques peuvent être simplifiées.• On cherche la forme minimale d’une fonction :

• Nombre minimal de monômes,• nombre minimal de variables par monômes

• Possibilité de plusieurs formes minimales : formes équivalentes• But : Fabriquer un système

• à moindre coût,• rapide,• fiable,• peu consommateur

• 2 méthodes :• Algébrique• Graphique





Méthode algébrique (algèbre de Boole)

Applications des principes et propriétés de l’algèbre de Boole :• Identités remarquables

• a.b+ a.b = b• a+ a.b = a• a+ a.b = a+ b

• (a+ b).(a+ b) = b• a.(a+ b) = a• a.(a+ b) = a.b

• Il en découle :• 2 mintermes adjacents → il reste l’intersection commune

a.b.c+ a.b.c = a.b

• 2 maxtermes adjacents → il reste l’union commune

(a+ b+ c).(a+ b+ c) = a+ b





Méthode algébrique (algèbre de Boole)

• Factorisation• Théorème du consensus• Simplification de la forme canonique avec le moins de terme

RemarqueLa méthode algébrique est toujours possible mais est une démarcheintuitive dépendant de l’expérience...





Méthode algébrique - Exemples

1 f1 = (a+ b)(a+ b)

2 f2 = (a+ b)(a+ c)(c+ b)

3 f3 = a+ a.b

4 f4 = abc+ abc+ abc+ abc+ abc





Méthode graphique (tableau de Karnaugh)

Principe :• Mettre en évidence les termes adjacents (qui ne différent que par

une variable)

abc+ abc = ac(b+ b) = ac

• Méthode : Tableau de Karnaugh• 2 termes adjacents logiquement sont adjacents géométriquement• Regrouper 2n cases revient à factoriser et à faire disparaître n

variables de l’équation logique• Tableau rempli à la manière d’une table de vérité





Tableau de Karnaugh - Exemples

Depuis la table de vérité :

a b c f

0 0 0 00 0 1 10 1 0 10 1 1 11 0 0 01 0 1 01 1 0 01 1 1 0

bca 00 01 11 10

0

1

0 1 11

0 0 00

f(a,b, c) = ac+ ab






Depuis la première forme canonique :

f(a,b, c) = a.b.c+ a.b.c+ a.b.c

bca 00 01 11 10

0

1

1 1

1






Depuis la deuxième forme canonique :

f(a,b, c) = (a+ b+ c).(a+ b+ c).(a+ b+ c)

bca 00 01 11 10

0

1

0

0 0






Exemple de simplification. A partir des 1 :

bca 00 01 11 10

0

1

0 1 01

1 1 01

bca 00 01 11 10

0

1

0 1 01

1 1 01

f(a,b, c) = a.b+ a.c+ a.c







bca 00 01 11 10

0

1

0 1 01

1 1 01

bca 00 01 11 10

0

1

0 1 01

1 1 01

f(a,b, c) = a.b+ c







bca 00 01 11 10

0

1

0 1 01

1 1 01

bca 00 01 11 10

0

1

0 1 01

1 1 01

f(a,b, c) = (a+ c).(b+ c)





Tableau de Karnaugh - Exercices

1 f(a,b, c) = a.b.c+ a.b.c+ a.b.c+ a.b.c+ a.b.c+ a.b.c

2 f(a,b, c) = a.b.c+ a.b.c+ a.b.c

3 f(a,b, c) = a.b.c+ a.b.c+ a.b.c+ a.b.c

4 f(a,b, c) = (a+b+c)(a+ b+ c)(a+ b+c)(a+ b+ c)(a+b+c)





Tableau de Karnaugh - Exercices

1 f(a,b, c,d) = a.b.c.d+ a.b.c.d+ a.b.c.d+ a.b.c.d

2 f(a,b, c,d) = a.b.c.d+ a.b.c.d+ a.b.c.d+ a.b.c.d

3 f(a,b, c,d) = a.b.c.d+ a.b.c.d+ a.b.c.d+ a.b.c.d+a.b.c.d+ a.b.c.d+ a.b.c.d+ a.b.c.d

4 f(a,b, c,d) = (a+ b+ c+ d)(a+ b+ c+ d)(a+ b+ c+d)(a+ b+ c+ d)(a+ b+ c+ d)(a+ b+ c+ d)




Plan

1 Introduction








Définition

Plan

4 Les circuits combinatoiresDéfinitionLes portes élémentairesLes multiplexeursLes transcodeursLes additionneurs / soustracteursLes comparateursLes unités arithmétiques et logiques




Définition

Circuit combinatoire• C’est l’abscence de

mémoire qui lesdéfinissent,• Les sorties sont une

fonction combinatoire desentrées S = f(E),• A une des configuration

des entrées correspond uneunique configuration dessorties.

Circuit séquentiel• Les sorties sont fonction

des entrées mais aussi del’état interne du système,• A une des configuration

des entréespeutcorrespondre plusieursconfigurations des sorties• L’état interne est une

trace du passé du systèmenumérique




Les portes élémentaires

Plan






Porte NOT

x y

x y

0 11 0

x y

entity my_not isPort ( x : in STD_LOGIC;y : out STD_LOGIC);end my_not;

architecture Behavioral of my_not isy <= not(x);end Behavioral;





Porte OR

yab

a b y

0 0 00 1 11 0 11 1 1

a

y

b

entity my_or isPort ( a : in STD_LOGIC;b : in STD_LOGIC;y : out STD_LOGIC);end my_or;

architecture Behavioral of my_or isy <= a or b;end Behavioral;





Porte AND

yab

a b y

0 0 00 1 01 0 01 1 1

a

y

b

entity my_and isPort ( a : in STD_LOGIC;b : in STD_LOGIC;y : out STD_LOGIC);end my_and;

architecture Behavioral of my_and isy <= a and b;end Behavioral;





Porte NOR

yab

a b y

0 0 10 1 01 0 01 1 0

a

b

y

entity my_nor isPort ( a : in STD_LOGIC;b : in STD_LOGIC;y : out STD_LOGIC);end my_nor;

architecture Behavioral of my_nor isy <= a nor b;end Behavioral;





Porte NAND

ab

y

a b y

0 0 10 1 11 0 11 1 0

y

a

b

entity my_nand isPort ( a : in STD_LOGIC;b : in STD_LOGIC;y : out STD_LOGIC);end my_nand;

architecture Behavioral of my_nand isy <= a nand b;end Behavioral;





Porte XOR

yab

a b y

0 0 00 1 11 0 11 1 0

y

a

a

a

b b

a

b

b

entity my_xor isPort ( a : in STD_LOGIC;b : in STD_LOGIC;y : out STD_LOGIC);end my_xor;

architecture Behavioral of my_xor isy <= a xor b;end Behavioral;





Porte XNOR

yab

a b y

0 0 10 1 01 0 01 1 1

y

a

a

a

b b

a

b

b

entity my_xnor isPort ( a : in STD_LOGIC;b : in STD_LOGIC;y : out STD_LOGIC);end my_xnor;

architecture Behavioral of my_xnor isy <= a xnor b;end Behavioral;




Les multiplexeurs

Plan





Les multiplexeurs

Opérations d’aiguillage

Multiplexeur

Aiguille un signal d’entrée parmi2n vers une sortie grâce à n bits

d’adresse

Démultiplexeur

Aiguille un signal d’entrée versune des 2n sorties grâce à n bits

d’adresse




Les multiplexeurs

Application des multiplexeurs

• Conversion parallèle/série• Réalisations des fonctions combinatoires : toute fonction logique

de N variables est réalisable avec un multiplexeur de 2N vers 1 :




Les transcodeurs

Plan





Les transcodeurs

Opération de transcodage

DéfinitionUn opérateur de transcodage est un circuit transformant uneinformation présente en entrée sous une forme donnée (code 1) en lamême information en sortie mais sous une autre forme (code 2)

Il en existe 3 types :




Les transcodeurs

Transcodeur - Exemple

Le transcodeur BCD / 7 segments




Les transcodeurs


Le transcodeur BCD / 7 segments1 Dressez la table de vérité de ce transcodeur

2 Grâce à des tableaux de Karnaugh, exprimez chacune des sortiesen fonction des entrées

3 Dessinez le logigramme du transcodeur




Les transcodeurs


Le transcodeur BCD / 7 segments




Les additionneurs / soustracteurs

Plan






Le demi-additionneur

Il prend en entrée 2 bits Ak et Bk et délivre leur somme Sk et laretenue Ck

Ak Bk Sk Ck

0 0 0 00 1 1 01 0 1 01 1 0 1

Sk = Ak ⊕ Bk

Ck = Ak · Bk





L’additionneur complet

Il permet de prendre en compte un retenue entrante Ck−1

Écrivez alors

1 sa table de vérité,

2 ses équations logiques,

3 son logigramme.






Ak Bk Ck−1 Sk Ck

0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 0 1






Sk = Ak ⊕ Bk ⊕ Ck−1

Ck = Ak · Bk + (Ak ⊕ Bk) · Ck−1

A

B

Cin

Cout

S





L’additionneur à retenue propagée

cin

s

cout

ba

cin

s

cout

ba

a0 b0 a1 b1

c0

s0 s1





Débordement (overflow) et détection du zéro

0 1 1 10 1 1 1 (7)

+ 0 0 1 1 (3)

= 1 0 1 0 (-6)

1 0 0 01 1 0 0 (-4)

+ 1 0 1 1 (-5)

= 0 1 1 1 (7)

• Un débordement arrive si le résultat est trop grand (en valeur absolue)• L’addition de deux opérandes de signes différents ne génère pas d’overflow

• Un débordement se produit lorsqu’on additionne :• 2 nombres positifs et la somme générée est négative• 2 nombres négatifs et la somme générée est positive

• En utilisant une table de vérité, on peut facilement montrer qu’undébordement se produit quand les retenues entrantes et sortantes du MSBsont différentes.




Les comparateurs

Plan





Les comparateurs

Comparateur élémentaire

Être capable de détecter l’égalité et de comparer deux nombres

A B E S I

0 0 1 0 00 1 0 0 11 0 0 1 01 1 1 0 0




Les comparateurs

Concaténation

Dessinez le logigramme d’un comparateur opérant sur 2 bits grâce à 2comparateurs élémentaires et des portes logiques




Les unités arithmétiques et logiques

Plan






L’unité arithmétique et logique

ALU

S

flagsselect

BA

/f

/s

/n/n

/ n





UAL

Synthèse de l’UAL :• 2 entrées A et B codées sur 4 bits,• 1 sortie S codée sur 4 bits,• 1 sortie zero qui vaut 1 si S = 0,• 1 sortie of qui vaut 1 si un débordement est détecté sur S• 1 entré sel sur 2 bits permettant de sélectionner l’opération à

effectuer :

• sel = 00⇒ S = A+ B• sel = 01⇒ S = A− B

• sel = 10⇒ S = A OU SB• sel = 11⇒ S = A ET B




Plan

1 Introduction








La bascule D-Latch (Verrou)

Plan

5 Les circuits séquentiels synchronesLa bascule D-Latch (Verrou)La bascule D-Flip-flopLes registresLes compteurs synchrones





Limitations de la logique combinatoire

SystemeBouton Lampe

Quand le bouton poussoir estenfoncé :• Allumer la lampe si elle est

éteinte• Eteindre la lampe si elle est

alluméeLa lampe doit changer d’étatlorsque le bouton reste enfoncépendant une seconde.

En quoi ce cuircuit est-il différent de ceux étudiés précédemment ?• La notion d’état, i.e. le circuit a une mémoire.• La sortie change de valeur sur une entrée de type événement.• La notion de temps.





Vers un système séquentiel

Logique

Combinatoire Element

Memoire

Bouton Lampe

EtatCourant

EtatSuivant

• La logique séquentielle permet de stocker l’état courant.• La logique combinatoire permet de calculer l’état futur et les

sorties à partir de l’état présent et des entrées.• Bascules asynchrones

• Bascule RS• Bascules synchrones

• Bascule D Latch• Bascule D Flip Flop• Bascule T• Bascule JK





Point mémoire

Q∗Q Q∗ = Q

Nombre pair d’inversions => 2 états stables : bistable• Q = 1 et Q∗ = 0• Q = 0 et Q∗ = 1

Problème : Ecriture d’une valeur dans le bistable ?





D latch

Bascule D latch(verrou)• E = 0 : mode acquisition• E = 1 : mode mémorisation

Synchronisation sur niveauDifférenciation des entrées :• D (data) : entrée de donnée• E (enable) : entrée de validation

E D Q+ Q∗+

0 0 Q Q

0 1 Q Q

1 0 0 11 1 1 0

D

Q*E

Q

Symbole logique

D Q*

Q

E E*

E*

E*

E

E





Fonctionnement

D Q*

Q

E E*

E*

E*

E

E

D Q*

Q

D Q*

Q

D Q*

Q

E E*

E*

E*

E

E

E = 1 : mode acquisition E = 0 : mode memorisation

E

D

Q




La bascule D-Flip-flop

Plan






Fonctionnement

• Structure "maître/esclave" : 2latches à commandesopposées• CLK = 0 : L1 en acquisition,L2 vérrouillé (mémorisation)• CLK = 1 : L1 vérrouillé

(mémorisation), L2 enacquisition• La donnée D est "recopiée"

sur la sortie Q sur un frontmontant d’horloge

L1

D1

Q∗1E1

Q1

L2

D2

E2

Q2

D

CLK

Q

Q∗

CLKCLK

D

Q∗2

M

M

Q

L1

L2

ACQUIS. MEMO. ACQUIS. MEMO.

MEMO. ACQUIS. MEMO. ACQUIS.





d q

qclk

clk q+

0 q

1 q

↓ q

↑ d

entity my_DFF isPort( d : in STD_LOGIC;

clk : in STD_LOGIC;q : out STD_LOGIC);

end my_DFF;

d q

qclk

d q

qclk

d q

qclk

esclavemaître d

clk

q





d q

qclk

clk q+

0 q

1 q

↓ q

↑ d

architecture Behavioral of my_DFF isbegin

DFF_pr : process(clk)begin

if (clk'event and clk = '1') thenq <= d;

end if;end process DFF_pr;

end Behavioral;

d q

clk

clk clk

clk

clkclk

clk

clk

q

d

clk

tpcqdown tpcqup





d q

qclk

rst

rst clk q+

0 X 01 0 q

1 1 q

1 ↓ q

1 ↑ d

d q

clk

clk clk

clk

clkclk

clk

clk

rst

rst


clk : in STD_LOGIC;rst : in STD_LOGIC;q : out STD_LOGIC);

end my_DFF;

architecture Behavioral of my_DFF isbegin

DFF_pr : process(clk,rst)begin

if (rst = '0') thenq <= '0';

elsif (clk'event and clk = '1') thenq <= d;


end Behavioral;





d q

qclk

rst

rst clk q+

1 X 01 0 q

1 1 q

1 ↓ q

1 ↑ d

d q

clk

clk clk

clk

clkclk

clk

clk

rst

rst


clk : in STD_LOGIC;rst : in STD_LOGIC;q : out STD_LOGIC);

end my_DFF;

architecture Behavioral of my_DFF isbeginDFF_pr : process(clk,rst)begin

if (rst = '1') thenq <= '0';

elsif (clk'event and clk = '1') thenq <= d;


end Behavioral;




Les registres

Plan





Les registres

Registre N bits

• N bascules D Flip-Flops• Toutes commandées par une

même horloge CLK• Mémorisation d’un vecteur

binaire de N bits• Registre "tampon" / "buffer"

D Q

D Q

D Q

...

D0

D1

DN−1

Q0

Q1

QN−1

CLK




Les registres

Registre à décalage

D QD QD Q

CLK

E S

• La donnée présente sur l’entrée E sera disponible en sortie 3cycles d’horloge plus tard• La donnée est "retardée" de 3 cycles d’horloges• Ligne à retard• Multiplication par 23 = 8




Les registres

Registre à décalage avec chargement parallèle

D QD QD Q

CLK

E S1

0

LOAD

1

0

LOAD

1

0

LOAD

Q2 Q1 Q0

V2 V1 V0

• Des multiplexeurs permettent de charger une valeur V• La donnée est "retardée" de 3 cycles d’horloges• Chargement (LOAD=1) + décalage (LOAD=0)




Les registres

Intilialisation asynchrone

D QD QD Q

CLK

E S1

0

LOAD

1

0

LOAD

1

0

LOAD

Q2 Q1 Q0

V2 V1 V0

SET

RST

SET

RST

SET

RST

A_INIT

1 1

1

• On utilise les entrée de SET/RST asynchrone pour forcer lavaleur du registre• Ici, entrées SET/RST actives à 0• Si A_INIT=0 : reg. initialisé à 101 sinon, fonctionnement normal• Initialisation indépendante de CLK et prioritaire sur CLK




Les compteurs synchrones

Plan




Documents

EN102 : Logique combinatoire et séquentielle - Introduction