Voir la source de Fonctionnement d'un ordinateur/Les circuits combinatoires

Dans ce chapitre, nous allons aborder les '''circuits combinatoires'''. Ils prennent des données sur leurs entrées et fournissent un résultat en sortie, comme tous les circuits électroniques que nous verrons dans ce cours. Le truc, c'est que le résultat en sortie ne dépend que des entrées et de rien d'autre. Pour donner quelques exemples, on peut citer les circuits qui effectuent des additions, des multiplications, ou d'autres opérations arithmétiques du genre. Ils sont opposés aux circuits dit séquentiels qui ont une capacité de mémorisation, pour lesquels le résultat dépend des entrées et de ce qu'ils ont mémorisés avant. Nous verrons les circuits séquentiels dans un chapitre ultérieur, car ils sont fabriqués en combinant des circuits combinatoires avec des mémoires.

Quelle que soit sa complexité, un circuit combinatoire est construit en reliant des portes logiques entre elles. La conception d'un circuit combinatoire demande cependant de respecter quelques contraintes. La première est qu'il n'y ait pas de boucles dans le circuit : impossible de relier la sortie d'une porte logique sur son entrée, ou de faire la même chose avec un morceau de circuit. Si une boucle est présente dans un circuit, celui-ci est un circuits séquentiel.

Dans ce qui va suivre, nous allons voir comment créer des circuits combinatoires à plusieurs entrées et une seule sortie. Pour simplifier, on peut considérer que les bits envoyés en entrée sont un nombre et que le circuit calcule un bit de résultat.

[[File:Exemple d'un circuit électronique à une seule sortie.jpg|centre|vignette|upright=2|Exemple d'un circuit électronique à une seule sortie.]]

Créer des circuits à plusieurs sorties peut se faire en assemblant plusieurs circuits à une sortie. La méthode pour ce faire est très simple : chaque sortie est calculée indépendamment des autres, avec un circuit à une sortie. En assemblant ces circuits à plusieurs entrées et une sortie, on peut ainsi calculer toutes les sorties. Évidemment, il est possible de faire des simplifications ensuite. Par exemple, en mutualisant des portions de circuit identiques entre deux sous-circuits. Mais laissons cela pour plus tard.

[[File:Comment créer un circuit à plusieurs sorties avec des sous-circuits à une sortie.jpg|centre|vignette|upright=2|Comment créer un circuit à plusieurs sorties avec des sous-circuits à une sortie.]]

==Décrire un circuit : tables de vérité et équations logiques==

Pour commencer, nous avons besoin de décrire le circuit électronique qu'on souhaite concevoir. Et pour cela, il existe plusieurs grandes méthodes : la table de vérité, les équations logiques, un schéma du circuit. Les schémas de circuits électroniques ne sont rien de plus que les schémas avec des portes logiques, que nous avons déjà utilisé dans les chapitres précédents. Reste à voir la table de vérité et les équations logiques.

La différence entre les deux est que la table de vérité décrit ce que fait un circuit, alors qu'une équation logique décrit la manière dont les portes logiques sont reliées. D'un côté la table de vérité considère le circuit comme une boite noire dont elle décrit le fonctionnement, de l'autre les équations décrivent ce qu'il y a à l'intérieur comme le ferait un schéma avec des portes logiques.

===La table de vérité===

La '''table de vérité''' décrit ce que fait le circuit, mais ne dit pas quelles sont les portes logiques utilisées pour fabriquer le circuit, ni comment celles-ci sont reliées. Elle se borne à donner la valeur de la sortie pour chaque entrée. Pour créer cette table de vérité, il faut commencer par lister toutes les valeurs possibles des entrées dans un tableau, puis de lister la valeur de chaque sortie pour toute valeur possible en entrée. Cela peut être assez long : pour un circuit ayant <math>n</math> entrées, ce tableau aura <math>>2^n</math> lignes. Mais c'est la méthode la plus simple, la plus facile à appliquer.

Le premier circuit que l'on va créer est un inverseur commandable, qui fonctionne soit comme une porte NON, soit comme une porte OUI, selon ce qu'on met sur une entrée de commande. Le bit de commande indique s'il faut que le circuit inverse ou non l'autre bit d'entrée :
* quand le bit de commande vaut zéro, l'autre bit est recopié sur la sortie ;
* quand il vaut 1, le bit de sortie est égal à l'inverse du bit d'entrée (pas le bit de commande, l'autre).

La table de vérité obtenue est celle d'une porte XOR :

{|class="wikitable"
|-
!Entrées
!Sortie
|-
||00||0
|-
||01||1
|-
||10||1
|-
||11||0
|}

Pour donner un autre exemple, on va prendre un circuit calculant le bit de parité d'un nombre. Nous avons déjkà vu ce qu'est ce bit de parité dans le chapitre sur les codes correcteurs d'erreur, mais faisons un rappel rapide.. Dans le chapitre sur le binaire, nous avons vu que le nombre de bits à 1 dans un nombre est appelé sa ''population count''. Par exemple, la ''population count'' du nombre 0110 est de 2, celle du nombre 0111 est de 3. Le bit de parité dit cette ''population count'' est un nombre pair ou impair : zéro si elle est paire et 1 si elle est impaire. Le bit de parité et la ''population count'' sont très utilisées dans les codes de détection/correction d'erreur, je ne reviens pas dessus. Dans notre cas, on va créer un circuit qui calcule le bit de parité d'un nombre de 3 bits.

{|class="wikitable"
|-
!Entrées
!Sortie
|-
||000||0
|-
||001||1
|-
||010||1
|-
||011||0
|-
||100||1
|-
||101||0
|-
||110||0
|-
||111||1
|}

Pour le dernier exemple, nous allons créer une porte à majorité de 3 bits. Pour rappel, une porte à majorité prend en entrée un opérande et a pour résultat le bit majoritaire dans ce nombre . Par exemple :
* le nombre 010 contient deux 0 et un seul 1 : le bit majoritaire est 0 ;
* le nombre 011 contient deux 1 et un seul 0 : le bit majoritaire est 1 ;
* le nombre 000 contient trois 0 et aucun 1 : le bit majoritaire est 0 ;
* le nombre 110 contient deux 1 et un seul 0 : le bit majoritaire est 1 ;
* etc.

{|class="wikitable"
|-
!Entrées
!Sortie
|-
||000||0
|-
||001||0
|-
||010||0
|-
||011||1
|-
||100||0
|-
||101||1
|-
||110||1
|-
||111||1
|}

===Les équations logiques===

La table de vérité peut être transformée en '''équations logiques''', qui mettent en œuvre un circuit avec des portes logiques. Il ne s'agit pas des équations auxquelles vous êtes habitués, les équations logiques ne font que des ET/OU/NON sur des bits. Dans le détail, les variables sont des bits (les entrées du circuit considéré), les opérations sont des ET, OU et NON. Voici résumé dans ce tableau les différentes opérations, ainsi que leur notation. a et b sont des bits.

{|class="wikitable"
|-
!Opérateur
!Notation 1
!Notation 2
|-
| NON a || <math>\overline{a}</math> || <math>\lnot a</math>
|-
| a ET b || a.b || <math>a \and b</math>
|-
| a OU b || a+b || <math>a \or b</math>
|-
| a XOR b || <math>a \oplus b</math> || <math>a \veebar b</math>
|}

Avec ce petit tableau, vous savez comment écrire des équations logiques… Enfin presque, il ne faut pas oublier le plus important : les parenthèses, pour éviter quelques ambiguïtés. C'est un peu comme avec des équations normales : <math>(a \times b) + c</math> donne un résultat différent de <math>a \times (b+c)</math>. Avec nos équations logiques, on peut trouver des situations similaires : par exemple, <math>(a.b) + c</math> est différent de <math>a.(b+c)</math>.

Dans la jungle des équations logiques, deux types se démarquent des autres. Ces deux catégories portent les noms barbares de '''formes normales conjonctives''' et de '''formes normales disjonctives'''. Derrière ces termes se cache cependant deux concepts assez simples.

Pour simplifier, ces équations décrivent des circuits composés de trois couches de portes logiques : une couche de portes NON, une couche de portes ET et une couche de portes OU. La couche de portes NON est placée immédiatement à la suite des entrées, dont elle inverse certains bits. Les couches de portes ET et OU sont placées après la couche de portes NON, et deux cas sont alors possibles : soit on met la couche de portes ET avant la couche de OU, soit on fait l'inverse. Le premier cas, avec les portes ET avant les portes OU, donne une forme normale disjonctive. La forme normale conjonctive est l'exact inverse, à savoir celui où la couche de portes OU est placée avant la couche de portes ET.

Les équations obtenues ont une forme similaire aux exemples qui vont suivre. Ces exemples sont donnés pour un circuit à trois entrées nommées a, b et c, et une sortie s. On voit que certaines entrées sont inversées avec une porte NON, et que le résultat de l'inversion est ensuite combiné avec des portes ET et OU.
* Exemple de forme normale conjonctive : <math>( a + b + c ) . ( \overline{a} + b + c ) . ( \overline{a} + \overline{b} + c ) . ( a + b + \overline{c}) . ( \overline{a} + \overline{b} + \overline{c} )</math>.
* Exemple de forme normale disjonctive : <math>( a . b . c ) + ( \overline{a} . b . c ) + ( \overline{a} . \overline{b} . c ) + ( a . b . \overline{c}) + ( \overline{a} . \overline{b} . \overline{c} )</math>.

Il faut savoir que tout circuit combinatoire peut se décrire avec une forme normale conjonctive et avec une forme normale disjonctive. L'équation obtenue n'est pas forcément idéale, mais on peut éventuellement la simplifier par la suite. Elle peut par exemple être simplifié en utilisant des portes XOR. D'ailleurs, les méthodes que nous allons voir plus bas ne font que cela : elles traduisent une table de vérité en forme normale conjonctive ou disjonctive, avant de la simplifier, puis de traduire le tout en circuit.

===Conversions entre équation, circuit et table de vérité===

Une équation logique se traduit en circuit en substituant chaque terme de l'équation avec la porte logique qui correspond. Les parenthèses et priorités opératoires indiquent l'ordre dans lequel relier les différentes portes logiques. Les schémas ci-dessous montrent des équations logiques et les circuits qui correspondent, tout en montrant les différentes substitutions intermédiaires.

[[File:Get logic function from combinational circuit.svg|centre|vignette|upright=2|Conversion d'un schéma de circuit en équation logique.]]

La signification symboles sur les exemples est donnée dans [[#Les équations logiques|la section « Les équations logiques » ci-dessus]].

{|class="wikitable flexible"
|-
|[[File:MFrey Task 1 Solution Normal.svg|300px|class=transparent|Premier exemple.]]
|[[File:MFrey Task 1 Solution NAND.svg|300px|class=transparent|Second exemple.]]
|-
|[[File:MFrey Task 1 Solution NAND 2 Input.svg|300px|class=transparent|Troisième exemple.]]
|[[File:Digitale Kreuzschaltung 8a.svg|centre|300px|class=transparent|Quatrième exemple.]]
|}

Il est possible de trouver l'équation d'un circuit à partir de sa table de vérité, et réciproquement. C'est d'ailleurs ce que font les méthodes de conception de circuit que nous allons voir plus bas : elles traduisent la table de vérité d'un circuit en équation logique, avant de la traduire en circuit.

On pourrait croire qu'à chaque table de vérité correspond une seule équation logique, mais ce n'est pas le cas. Une table de vérité peut être traduite en plusieurs équations logiques différentes. Après tout, on peut concevoir un circuit de différentes manières, des circuits câblés différents peuvent parfaitement faire la même chose. Des équations logiques qui décrivent la même table de vérité sont dites équivalentes. Elles décrivent des circuits différents, mais qui ont la même table de vérité - ils font la même chose. À ce propos, il est possible de convertir une équation logique en une autre équation équivalente, mais plus simple. Une section entière sera dédiée à ce genre de simplifications.

==La méthode des ''minterms''==

Créer un circuit demande d'établir sa table de vérité, avant de la traduire en équation logique, puis en circuit. Nous allons maintenant voir la première étape, celle de la conversion entre table de vérité et équation. Il existe deux grandes méthodes de ce type, pour concevoir un circuit intégré, qui portent les noms de '''méthode des ''minterms''''' et de '''méthode des ''maxterms'''''. La différence entre les deux est que la première donne une forme normale disjonctive, alors que la seconde donne une forme normale conjonctive.

Dans cette section, nous allons voir la méthode des ''minterms'', avant de voir la méthode des ''maxterms''. Pour chaque méthode, nous allons commencer par montrer comment appliquer ces méthodes sans rentrer dans le formalisme, avant de montrer le formalisme en question. La première étape de ces deux méthodes est donc d'établir la table de vérité, voyons comment.

===La méthode des ''minterms'', expliquée sans formalisme===

La méthode des ''minterms'' est de loin la plus simple à comprendre. Pour l'expliquer, nous allons commencer par concevoir un circuit, qui compare son entrée avec une constante, dépendante du circuit. Par la suite, nous allons voir comment combiner ce circuit avec des portes logiques pour obtenir le circuit désiré.

====Les ''minterms'' (comparateurs avec une constante)====

Nous allons maintenant étudier un comparateur qui vérifie si le nombre d'entrée est égal à une certaine constante (2, 3, 5, 8, ou tout autre nombre) et renvoie un 1 seulement si c’est le cas. Ainsi, on peut créer un circuit qui mettra sa sortie à 1 uniquement si on envoie le nombre 5 sur ses entrées. Ou encore, créer un circuit qui met sa sortie à 1 uniquement quand l'entrée vaut 126. Et ainsi de suite : tout nombre peut servir de constante à vérifier.

Le circuit possède plusieurs entrées, sur lesquelles on place les bits du nombre à comparer. Sa sortie est un simple bit, qui vaut 1 si le nombre en entrée est égal à la constante et 0 sinon. Nous allons voir qu'il y en a deux types, qui ressemblent aux deux types de comparateurs avec zéro. Le premier type est basé sur une porte NOR, à laquelle on ajoute des portes NON. Le second est basé sur une porte ET précédée de portes NON.

Le premier circuit de ce type est composé d'une couche de portes NON et d'une porte ET à plusieurs entrées. Créer un tel circuit se fait en trois étapes. En premier lieu, il faut convertir la constante à vérifier en binaire : dans ce qui suit, nous nommerons cette constante k. En second lieu, il faut créer la couche de portes NON. Pour cela, rien de plus simple : on place des portes NON pour les entrées de la constante k qui sont à 0, et on ne met rien pour les bits à 1. Par la suite, on place une porte ET à plusieurs entrées à la suite de la couche de portes NON.

[[File:Exemples de comparateurs (la constante est indiquée au-dessus du circuit).jpg|centre|vignette|upright=2|Exemples de comparateurs (la constante est indiquée au-dessus du circuit).]]

Pour comprendre pourquoi on procède ainsi, il faut simplement regarder ce que l'on trouve en sortie de la couche de portes NON :
* si on envoie la constante, tous les bits à 0 seront inversés alors que les autres resteront à 1 : on se retrouve avec un nombre dont tous les bits sont à 1 ;
* si on envoie un autre nombre, soit certains 0 du nombre en entrée ne seront pas inversés, ou alors des bits à 1 le seront : il y aura au moins un bit à 0 en sortie de la couche de portes NON.

Ainsi, on sait que le nombre envoyé en entrée est égal à la constante k si et seulement si tous les bits sont à 1 en sortie de la couche de portes NON. Dit autrement, la sortie du circuit doit être à 1 si et seulement si tous les bits en sortie des portes NON sont à 1 : il ne reste plus qu'à trouver un circuit qui prenne ces bits en entrée et ne mette sa sortie à 1 que si tous les bits d'entrée sont à 1. Il existe une porte logique qui fonctionne ainsi : il s'agit de la porte ET à plusieurs entrées.

[[File:Fonctionnement d'un comparateur avec une constante.jpg|centre|vignette|upright=2|Fonctionnement d'un comparateur avec une constante.]]

====Combiner les comparateurs avec une constante====

On peut créer n'importe quel circuit à une seule sortie avec ces comparateurs, en les couplant avec une porte OU à plusieurs entrées. Pour comprendre pourquoi, rappelons que les entrées du circuit peuvent prendre plusieurs valeurs : pour une entrée de <math>n</math> bits, on peut placer <math>2^n</math> valeurs différentes sur l'entrée. Mais seules certaines valeurs doivent mettre la sortie à 1, les autres la laissant à 0. Les valeurs d'entrée qui mettent la sortie 1 sont aussi appelées des '''''minterms'''''. Ainsi, pour savoir s’il faut mettre un 1 en sortie, il suffit de vérifier que l'entrée est égale à un ''minterm''. Pour savoir si l'entrée est égale à un ''minterm'', on doit utiliser un comparateur avec une constante pour chaque ''minterm''. Par exemple, pour un circuit dont la sortie est à 1 si son entrée vaut 0000, 0010, 0111 ou 1111, il suffit d'utiliser :
* un comparateur qui vérifie si l'entrée vaut 0000 ;
* un comparateur qui vérifie si l'entrée vaut 0010 ;
* un comparateur qui vérifie si l'entrée vaut 0111 ;
* et un comparateur qui vérifie si l'entrée vaut 1111.

Reste à combiner les sorties de ces comparateurs pour obtenir une seule sortie, ce qui est fait en utilisant un circuit relativement simple. On peut remarquer que la sortie du circuit est à 1 si un seul comparateur a sa sortie à 1. Or, on connaît un circuit qui fonctionne comme cela : la porte OU à plusieurs entrées. En clair, on peut créer tout circuit avec seulement des comparateurs et une porte OU à plusieurs entrées.

[[File:Conception d'un circuit à partir de minterms.jpg|centre|vignette|upright=2.5|Conception d'un circuit à partir de ''minterms'']]

===Méthode des ''minterms'', version formalisée===

On peut formaliser la méthode précédente, ce qui donne la '''méthode des ''minterms'''''. Celle-ci permet d'obtenir un circuit à partir d'une description basique du circuit. Mais le circuit n'est pas vraiment optimisé et peut être fortement simplifié. Nous verrons plus tard comment simplifier des circuits obtenus avec la méthode que nous allons exposer.

====Lister les entrées de la table de vérité qui valident l'entrée====

La première étape demande d'établir la table de vérité du circuit, afin de déterminer ce que fait le circuit voulu. Maintenant que l'on a la table de vérité, il faut lister les valeurs en entrée pour lesquelles la sortie vaut 1. On rappelle que ces valeurs sont appelées des ''minterms''. Il faudra utiliser un comparateur avec une constante pour chaque ''minterm'' afin d'obtenir le circuit final. Pour l'exemple, nous allons reprendre le circuit de calcul d'inverseur commandable, vu plus haut.

{|class="wikitable"
|-
!Entrées
!Sortie
|-
||00||0
|-
||01||1
|-
||10||1
|-
||11||0
|}

Listons les lignes de la table où la sortie vaut 1.

{|class="wikitable"
|-
!Entrées
!Sortie
|-
|01
|1
|-
|10
|1
|}

Pour ce circuit, la sortie vaut 1 si et seulement si l'entrée du circuit vaut 01 ou 10. Dans ce cas, on doit créer deux comparateurs qui vérifient si leur entrée vaut respectivement 01 et 10. Une fois ces deux comparateurs crée, il faut ajouter la porte OU.

====Établir l'équation du circuit====

Les deux étapes précédentes sont les seules réellement nécessaires : quelqu'un qui sait créer un comparateur avec une constante (ce qu'on a vu plus haut), devrait pouvoir s'en sortir. Reste à savoir comment transformer une table de vérité en équations logiques, et enfin en circuit. Pour cela, il n'y a pas trente-six solutions : on va écrire une équation logique qui permettra de calculer la valeur (0 ou 1) d'une sortie en fonction de toutes les entrées du circuit. Et on fera cela pour toutes les sorties du circuit que l'on veut concevoir. Pour ce faire, on peut utiliser ce qu'on appelle la méthode des ''minterms'', qui est strictement équivalente à la méthode vue au-dessus. Elle permet de créer un circuit en quelques étapes simples :
* lister les lignes de la table de vérité pour lesquelles la sortie vaut 1 (comme avant) ;
* écrire l'équation logique pour chacune de ces lignes (qui est celle d'un comparateur) ;
* faire un OU entre toutes ces équations logiques, en n'oubliant pas de les entourer par des parenthèses.

Pour écrire l'équation logique d'une ligne, il faut simplement :
* lister toutes les entrées de la ligne ;
* faire un NON sur chaque entrée à 0 ;
* et faire un ET avec le tout.

Vous remarquerez que la succession d'étapes précédente permet de créer un comparateur qui vérifie que l'entrée est égale à la valeur sur la ligne sélectionnée.

Pour illustrer le tout, on va reprendre notre exemple avec le bit de parité. La première étape consiste donc à lister les lignes de la table de vérité dont la sortie est à 1.

{|class="wikitable"
|-
!Entrées
!Sortie
|-
||001||1
|-
||010||1
|-
||100||1
|-
||111||1
|}

On a alors :
* la première ligne où l'entrée vaut 001 : son équation logique vaut <math>\overline{e2}.\overline{e1}.e0</math> ;
* la seconde ligne où l'entrée vaut 010 : son équation logique vaut <math>\overline{e2}.e1.\overline{e0}</math> ;
* la troisième ligne où l'entrée vaut 100 : son équation logique vaut <math>e2.\overline{e1}.\overline{e0}</math> ;
* la quatrième ligne où l'entrée vaut 111 : son équation logique vaut <math>e2.e1.e0</math>.

On a alors obtenu nos équations logiques. Reste à faire un OU entre toutes ces équations, et le tour est joué !

Nous allons maintenant montrer un deuxième exemple, avec le circuit de calcul du bit majoritaire vu juste au-dessus. Première étape, lister les lignes de la table de vérité dont la sortie vaut 1 :

{|class="wikitable"
|-
!Entrées
!Sortie
|-
||011||1
|-
||101||1
|-
||110||1
|-
||111||1
|}

Seconde étape, écrire les équations de chaque ligne. Essayez par vous-même, avant de voir la solution ci-dessous.
* Pour la première ligne, l'équation obtenue est : <math>\overline{e2}.e1.e0</math>.
* Pour la seconde ligne, l'équation obtenue est : <math>e2.\overline{e1}.e0</math>.
* Pour la troisième ligne, l'équation obtenue est : <math>e1.e2.\overline{e0}</math>.
* Pour la quatrième ligne, l'équation obtenue est : <math>e2.e1.e0</math>.

Il suffit ensuite de faire un OU entre les équations obtenues au-dessus.

====Traduire l'équation en circuit====

Enfin, il est temps de traduire l'équation obtenue en circuit, en remplaçant chaque terme de l'équation par le circuit équivalent. Notons que les parenthèses donnent une idée de comment doit être faite cette substitution.

==La méthode des ''maxterms''==

La méthode des ''minterms'', vue précédemment, n'est pas la seule pour traduire une table de vérité en équation logique. Elle est secondée par une méthode assez similaire : la '''méthode des ''maxterms'''''. Les deux donnent un circuit composé d'une couche de portes NON, suivie par deux couches de portes ET et OU, mais l'ordre des portes ET et OU est inversé. Dit autrement, la méthode des ''minterms'' donne une forme normale disjonctive, alors que celle des ''maxterms'' donnera une forme normale conjonctive.

===La méthode des ''maxterms'' : formalisme===

La méthode des ''maxterms'' fonctionne sur un principe assez tordu. Elle effectue trois étapes, chacune correspondant à l'exact inverse de l'étape équivalente avec les ''minterms''.
* Premièrement on doit lister les lignes de la table de vérité qui mettent la sortie à 0, ce qui est l'exact inverse de l'étape équivalente avec les ''minterms''.
* Ensuite, on traduit chaque ligne en équation logique. La traduction de chaque ligne en équation logique est aussi inversée par rapport à la méthode des ''minterms'' : on doit inverser les bits à 1 avec une porte NON et faire un OU entre chaque bit.
* Et enfin, on doit faire un ET entre tous les résultats précédents.

Par exemple, prenons la table de vérité suivante :

{|class="wikitable"
|-
! Entrée a !! Entrée b !! Entrée c
!
! Sortie S
|-
|0||0||0
|
|0
|-
|0||0||1
|
|1
|-
|0||1||0
|
|0
|-
|0||1||1
|
|1
|-
|1||0||0
|
|1
|-
|1||0||1
|
|1
|-
|1||1||0
|
|1
|-
|1||1||1
|
|0
|}

La première étape est de lister les entrées associées à une sortie à 0. Ce qui donne :

{|class="wikitable"
|-
! Entrée a !! Entrée b !! Entrée c
!
! Sortie S
|-
|0||0||0
|
|0
|-
|0||1||0
|
|0
|-
|1||1||1
|
|0
|}

Vient ensuite la traduction de chaque ligne en équation logique. Cette fois-ci, les bits à 1 dans l'entrée sont ceux qui doivent être inversés, les autres restants tels quels. De plus, on doit faire un OU entre ces bits. On a donc :
* <math>a + b + c</math> pour la première ligne ;
* <math>a + \overline{b} + c</math> pour la seconde ligne ;
* <math>\overline{a} + \overline{b} + \overline{c}</math> pour la troisième ligne.

Et enfin, il faut faire un ET entre ces maxterms. Ce qui donne l'équation suivante :

: <math>( a + b + c ) . ( a + \overline{b} + c ) . ( \overline{a} + \overline{b} + \overline{c} )</math>

On peut se demander quelle méthode choisir entre minterms et maxterms. L'exemple précédent nous donne un indice. Dans l'exemple précédent, il y a beaucoup de lignes associées à une sortie à 1. On a donc plus de minterms que de maxterms, ce qui rend la méthode des minterms plus longue. Par contre, on pourrait trouver des exemples où c'est l'inverse. Si un circuit a plus de lignes où la sortie est à 0, alors la méthode des minterms sera plus rapide. Bref, tout dépend du nombre de minterms/maxterms dans la table de vérité. En comptant le nombre de cas où la sortie est à 1 ou à 0, on peut savoir quelle méthode est la plus rapide : minterm si on a plus de cas avec une sortie à 0, maxterm sinon.

===Le principe caché derrière la méthode des maxterms===

La méthode des maxterms fonctionne sur le principe inverse de la méthode des minterms. Rappelons que chaque valeur d'entrée qui met une sortie à 0 est appelée un maxterm, alors que celles qui la mettent à 1 sont des minterms. Un circuit conçu selon avec des minterms vérifie si l'entrée met la sortie à 1, si l'entrée est un minterm. Alors qu'un circuit maxterm vérifie si l'entrée ne met pas la sortie à 0, si l'entrée n'est pas un maxterm. Pour cela, le circuit compare l'entrée avec chaque maxterm possible, et combine les résultats avec une porte à plusieurs entrées.

Pour commencer, le circuit vérifie si l'entrée est un maxterm un comparateur avec une constante par maxterm. La sortie du comparateur est cependant l'inverse d'avec les minterms : il renvoie un 1 si l'entrée ne correspond pas au maxterm et 0 sinon. La seconde étape combine les résultats de tous les maxterms pour déduire la sortie. Si tous les comparateurs renvoient un 1, cela signifie que l'entrée est différente de tous les maxterms : ce n'en est pas un. La sortie doit alors être mise à 1. Si l'entrée correspond à un maxterm, alors le comparateur associé au maxterm donnera un 0 en sortie : il y aura au moins un comparateur qui donnera un 0. Dans ce cas, la sortie doit être mise à 0. On remarque rapidement que ce comportement est celui d'une porte ET à plusieurs entrées.

[[File:Conception d'un circuit à partir de maxterms.jpg|centre|vignette|upright=2.5|Conception d'un circuit à partir de maxterms.]]

Pour concevoir le circuit de comparaison, la méthode la plus simple reste de prendre un comparateur avec une constante, puis d'inverser sa sortie avec une porte NON. Une méthode équivalente remplace la porte ET à plusieurs entrées dans ce comparateur par une porte NAND. Il est alors possible d'utiliser les lois de De Morgan pour simplifier le circuit : la porte NAND devient une porte OU avec des portes NON sur ses entrées. Les porte NOn sur les entrées sont combinés avec la première couche de porte NON, elles s'annulent, ce qui donne le circuit final, avec une couche de portes NON suivie par une couche porte OU à plusieurs entrées.

==Simplifier un circuit avec l'algèbre de Boole==

La méthode précédente donne une équation logique, en forme disjonctive ou conjonctive, qui est assez complexe. Heureusement, il est possible de la simplifier. Pour donner un exemple, prenez cette équation :

: <math>(\overline{e_2} . \overline{e_1} . e_0) + (\overline{e_2} . e_1 . \overline{e_0}) + (e_2 . \overline{e_1} . \overline{e_0}) + (e_2 . e_1 . e_0)</math> ;

Elle peut se simplifier en :

: <math>e_2 \oplus e_1 \oplus e_0</math>

Dans cet exemple, on passe donc de 17 portes logiques à seulement 3 ! Simplifier une équation logique permet de se faciliter la vie lors de la traduction de l'équation en circuit, mais cela donne un circuit plus rapide et/ou utilisant moins de portes logiques. Autant vous dire qu'apprendre à simplifier ces équations est quelque chose de crucial.

Pour simplifier une équation logique, on doit utiliser certaines propriétés mathématiques simples tirées de ce qu'on appelle l’'''algèbre de Boole''', terme barbare qui regroupe pourtant des manipulations assez basiques. En utilisant ces règles algébriques, on peut factoriser ou développer certaines expressions, comme on le ferait avec une équation normale. Les théorèmes de base de l’algèbre de Boole peuvent se classer en plusieurs types séparés, qui sont les suivantes :
* l'associativité, la commutativité et la distributivité ;
* la double négation et les lois de de Morgan ;
* les autres règles, appelées règles bit à bit.

L'associativité, la commutativité et la distributivité ressemblent beaucoup aux règles arithmétiques usuelles, ce qui fait qu'on ne les détaillera pas ici.

{|class="wikitable"
|+ Associativité, commutativité et distributivité
|-
! Commutativité
|
<math>a+b=b+a</math> </br>
<math>a.b=b.a</math> </br>
<math>a \oplus b = b \oplus a</math>
|-
! Associativité
|
<math>(a+b)+c=a+(b+c)</math> </br>
<math>(a.b).c=a.(b.c)</math> </br>
<math>(a \oplus b) \oplus c = a \oplus (b \oplus c)</math>
|-
! Distributivité
|
<math>(a+b).c=(c.b)+(c.a)</math> </br>
<math>(a.b)+c=(c+b).(c+a)</math>
|}

Les autres règles sont par contre plus importantes.

===Les règles de type bit à bit===

Les règles bit à bit ne sont utiles que dans le cas où certaines entrées d'un circuit sont fixées, ou lors de la simplification de certaines équations logiques. Elles regroupent plusieurs cas distincts.

Le premier cas est celui où on fait un ET/OU/XOR entre un bit et lui-même. Il regroupe les trois formules suivantes :

: <math>a . a = a</math>
: <math>a + a = a</math>
: <math>a \oplus a = 0</math>

Le second cas est celui où on fait un ET/OU/XOR entre un bit et son inverse. Il regroupe les trois formules suivantes :

: <math>a . \overline{a} = 0</math>,
: <math>a + \overline{a} = 1</math>
: <math>a \oplus \overline{a} = 1</math>.

Le troisième cas est celui où on fait un ET/OU/XOR entre un bit et 1. Il regroupe les trois formules suivantes :

: <math>a . 1 = a</math>,
: <math>a + 1 = 1</math>
: <math>a \oplus 1 = \overline{a}</math>.

Le quatrième cas est celui où on fait un ET/OU/XOR entre un bit et 0. Il regroupe les trois formules suivantes :

: <math>a . 0 = 0</math>,
: <math>a + 0 = a</math>
: <math>a \oplus 0 = a</math>.

Voici la liste de ces règles, classées par leur nom mathématique :

{|class="wikitable"
|+ Règles bit à bit
|-
!Idempotence
|
<math>a.a=a</math> </br>
<math>a+a=a</math>
|-
!Élément nul
|
<math>a.0=0</math> </br>
<math>a+1=1</math>
|-
!Élément Neutre
|
<math>a.1=a</math> </br>
<math>a+0=a</math> </br>
<math>a \oplus 0=a</math>
|-
!Complémentarité
|
<math>a \oplus 1=\overline{a}</math> </br>
<math>a+\overline{a}=1</math> </br>
<math>a\oplus \overline{a}=1</math> </br>
<math>a \oplus a=0</math> </br>
<math>a.\overline{a}=0</math>
|}

Nous avons déjà utilisé implicitement les formules du premier cas, à savoir <math>a.a=a</math> et <math>a+a=a</math> dans le chapitre sur les portes logiques. En effet, elles disent comment fabriquer une porte OUI à partir d'une porte ET ou d'une porte OU. Au passage, la formule <math>a \oplus a = 0</math> nous dit pourquoi cela ne marcherait pas du tout avec une porte XOR.

Ces formules seront utilisées dans le chapitre sur les circuits de calcul logique et bit à bit, dans la section sur les masques. C'est dans cette section que nous verrons en quoi ces formules sont utiles en dehors du cas d'une simplification de circuit. Pour le moment, nous ne pouvons pas en dire plus. Mais rassurez-vous, un rappel sera fait dans ce chapitre, vous n'avez pas encore besoin de mémoriser ces formules par cœur, même si c'est toujours bon à prendre.

===Les lois de de Morgan et la double négation===

Les lois de de Morgan et la double négation sont de loin les formules plus importantes à retenir. Les voici :

{|class="wikitable"
|+ Règles sur les négations
|-
! Double négation
| <math>\overline{\overline{a}}=a</math> </br>
|-
!Lois de De Morgan
|
<math>\overline{a.b} = \overline{a} + \overline{b}</math> </br>
<math>\overline{a+b} = \overline{a} . \overline{b}</math>
|}

Les deux loi de De Morghan reformulent quelque chose que nous avons déjà vu dans le chapitre sur les portes logiques :
* la première loi de de Morgan dit qu'une porte NAND peut se fabriquer avec une porte OU précédée de deux portes NON ;
* la seconde loi dit qu'une porte NOR peut se fabriquer avec une porte ET précédée de deux portes NON.

{|class="wikitable"
|+ Illustration des lois de De Morgan
|-
!<math>\overline{a}.\overline{b}=\overline{a+b}</math>
|[[File:1. Theorem.svg|class=transparent|1. Theorem.svg]]
|-
!<math>\overline{a}+\overline{b}=\overline{a.b}</math>
|[[File:2. Theorem.svg|class=transparent|2. Theorem.svg]]
|}

Les lois de de Morgan peuvent se généraliser pour plus de deux entrées, elles marchent pour des portes NAND/NOR à 3/4/5 entrées, voire plus. En les combinant avec la loi de la double négation, les lois de de Morgan permettent de transformer une équation écrite sous forme normale conjonctive en une forme normale disjonctive, et réciproquement. Pour le dire autrement, elles permettent de passer d'une équation obtenue avec les minterms à l'équation obtenue avec les maxterms.

===La formule équivalente de la porte XOR et de la porte NXOR===

Avec les règles précédentes, il est possible de démontrer que les portes XOR et NXOR peuvent se construire avec uniquement des portes ET/OU/NON, comme nous l'avions vu dans le chapitre précédent.

En utilisant la méthode des minterms, on arrive à l'expression suivante pour la porte XOR et la porte NXOR :

: XOR : <math>a \oplus b = ( \overline{a} . b ) + ( a . \overline{b} )</math>
: NXOR : <math>\overline{a \oplus b} = ( a . b ) + ( \overline{a} . \overline{b} )</math>

Les deux formules donnent les deux circuits qu'on avait obtenu dans le chapitre sur les portes logiques.

{|
|[[File:XOR als elementaire poorten.png|centre|vignette|upright=1|Porte XOR fabriquée à partir de portes ET/OU/NON.]]
|[[File:3 gate XNOR.svg|centre|vignette|upright=1|Porte NXOR fabriquée à partir de portes ET/OU/NON, alternative.]]
|}

===Exemples complets===

Comme premier exemple, nous allons travailler sur cette équation : <math>(\overline{e2}.e1.e0)+(e2.e1.e0)</math>. On peut la simplifier en trois étapes :
* Appliquer la règle de distributivité du ET sur le OU pour factoriser le facteur e1.e0, ce qui donne <math>(e2+\overline{e2}).e1.e0</math> ;
* Appliquer la règle de complémentarité sur le terme entre parenthèses <math>(e2+\overline{e2})</math>, ce qui donne 1.e1.e0 ;
* Et enfin, utiliser la règle de l’élément neutre du ET, qui nous dit que a.1=a, ce qui donne : e1.e0.

En guise de second exemple, nous allons simplifier <math>(\overline{e2}.e1.e0)+(e2.\overline{e1}.e0)</math>. Cela se fait en suivant les étapes suivantes :
* Factoriser e0, ce qui donne : <math>e0 . [(\overline{e2}.e1)+(e2.\overline{e1})]</math>;
* Utiliser la règle du XOR qui dit que <math>a \oplus b = ( \overline{a} . b ) + ( a . \overline{b} )</math>, ce qui donne <math>(e2 \oplus e1).e0</math>.

==Annexe facultative : les tableaux de Karnaugh==

Il existe d'autres méthodes pour simplifier nos circuits. Les plus connues étant les '''tableaux de Karnaugh''' et l''''algorithme de Quine Mc Cluskey'''. On ne parlera pas de la dernière méthode, trop complexe pour ce cours. Nous allons cependant aborder la méthode du tableau de Karnaugh. Précisons cependant que cette section est facultative, la plupart des simplifications que permet un tableau de Karnaugh peuvent se faire en utilisant l'algébre de Boole, il faut juste être compétent et parfois bien se creuser le cerveau.

La simplification des équations avec un tableau de Karnaugh demande plusieurs étapes, que nous allons maintenant décrire.

===Première étape : créer le tableau de Karnaugh===

[[File:Karnaugh map KV 4mal4 01.svg|vignette|Tableau de Karnaugh à quatre variables.]]

D'abord, il faut créer une table de vérité pour chaque bit de sortie du circuit à simplifier, qu'on utilise pour construire ce tableau. La première étape consiste à obtenir un tableau plus ou moins carré à partir d'une table de vérité, organisé en lignes et colonnes. Si on a n variables, on crée deux paquets avec le même nombre de variables (à une variable près pour un nombre impair de variables). Par exemple, supposons que j'aie quatre variables : a, b, c et d. Je peux créer deux paquets en regroupant les quatre variables comme ceci : ab et cd. Ou encore comme ceci : ac et bd. Il arrive que le nombre de variables soit impair : dans ce cas, il y a aura un paquet qui aura une variable de plus.

===Seconde étape : remplir ce tableau===

Ensuite, pour le premier paquet, on place les valeurs que peut prendre ce paquet sur la première ligne. Pour faire simple, considérez ce paquet de variables comme un nombre, et écrivez toutes les valeurs que peut prendre ce paquet en binaire. Rien de bien compliqué, mais ces variables doivent être encodées en code Gray : on ne doit changer qu'un seul bit en passant d'une ligne à sa voisine. Pour le second paquet, faites pareil, mais avec les colonnes. Là encore, les valeurs doivent être codées en code Gray.

Pour chaque ligne et chaque colonne, on prend les deux paquets : ces deux paquets sont avant tout des rassemblements de variables, dans lesquels chacune a une valeur bien précise. Ces deux paquets précisent ainsi les valeurs de toutes les entrées, et correspondent donc à une ligne dans la table de vérité. Sur cette ligne, on prend le bit de la sortie, et on le place à l'intersection de la ligne et de la colonne. On fait cela pour chaque case du tableau, et on le remplit totalement.

===Troisième étape : faire des regroupements===

Troisième étape de l'algorithme : faire des regroupements. Par regroupement, on veut dire que les 1 dans le tableau doivent être regroupés en paquets de 1, 2, 4, 8, 16, 32, etc. Le nombre de 1 dans un paquet doit TOUJOURS être une puissance de deux. De plus, ces regroupements doivent obligatoirement former des rectangles dans le tableau de Karnaugh. De manière générale, il vaut mieux faire des paquets les plus gros possible, afin de simplifier l'équation au maximum.

{|
|[[File:Karnaugh map KV 2mal4 Gruppe 9.svg|vignette|Exemple de regroupement valide.]]
|[[File:Karnaugh map KV 2mal4 Gruppe 6.svg|vignette|Exemple de regroupement invalide.]]
|}

[[File:Karnaugh map KV 4mal4 21.svg|vignette|Regroupements par les bords du tableau de Karnaugh, avec recouvrement.]]

Il faut noter que les regroupements peuvent se recouvrir. Non seulement c'est possible, mais c'est même conseillé : cela permet d'obtenir des regroupements plus gros. De plus, ces regroupements peuvent passer au travers des bords du tableau : il suffit de les faire revenir de l'autre côté. Et c'est possible aussi bien pour les bords horizontaux (gauche et droite) que pour les bords verticaux (haut et bas). Le même principe peut s'appliquer aux coins.

===Quatrième étape : convertir chaque regroupement en équation logique===

Trouver l'équation qui correspond à un regroupement est un processus en plusieurs étapes, que nous illustrerons dans ce qui va suivre. Ce processus demande de :
* trouver la variable qui ne varie pas dans les lignes et colonnes attribuées au regroupement ;
* inverser la variable si celle-ci vaut toujours zéro dans le regroupement ;
* faire un ET entre les variables qui ne varient pas.
* faire un OU entre les équations de chaque regroupement, et on obtient l'équation finale de la sortie.

<noinclude>
{{NavChapitre | book=Fonctionnement d'un ordinateur
           | prev=Les portes logiques
           | prevText=Les portes logiques
           | next=Les circuits de masquage
           | nextText=Les circuits de masquage
}}
</noinclude>