Fonctionnement d'un ordinateur/Version imprimable 2

Un livre de Wikilivres.
Aller à la navigation Aller à la recherche
Circuit électronique.

Un ordinateur est un appareil électronique parmi tant d'autres. La conception de ces appareils est un domaine appelé l’électronique et les gens qui conçoivent ces appareils sont appelés des électroniciens. Tous les appareils électroniques contiennent plusieurs composants électroniques simples, qui sont placés sur un support plat, en plastique ou en céramique, appelé la carte électronique. Les composants sont soudés sur la carte, histoire qu’ils ne puisse pas s’en décrocher. Ils sont reliés entre eux par des fils conducteurs, le plus souvent du cuivre ou de l’aluminium, ce qui leur permet de s’échanger des données. Sur les cartes simples, ces fils sont intégrés dans la carte électroniques, dans des creux du plastique. Ils portent le nom de pistes. Évidemment, tous les composants ne sont pas tous reliés entre eux. Par exemple, si je prends un ordinateur, l’écran n’est pas relié au clavier.

Appareils programmables et non-programmables[modifier | modifier le wikicode]

Les appareils simples sont non-programmables, ce qui veut dire qu’ils sont conçus pour une utilisation particulière et qu’ils ne peuvent pas faire autre chose. Par exemple, les circuits électroniques d’un lecteur de DVD ne peuvent pas être transformé en lecteur audio ou en console de jeux... Les circuits non-programmables sont câblés une bonne fois pour toute, et on ne peut pas les modifier. On peut parfois reconfigurer le circuit, pour faire varier certains paramètres, via des interrupteurs ou des boutons, mais cela s’arrête là. Et cela pose un problème : à chaque problème qu'on veut résoudre en utilisant un automate, on doit recréer un nouveau circuit.

À l'inverse, un ordinateur n’est pas conçu pour une utilisation particulière, contrairement aux autres objets techniques. Il est possible de modifier leur fonction du jour au lendemain, on peut lui faire faire ce qu’on veut. On dit qu'ils sont programmables. Pour cela, il suffit d’utiliser un logiciel, une application, un programme (ces termes sont synonymes), qui fait ce que l'on souhaite. La totalité des logiciels présents sur un ordinateur sont des programmes comme les autres, même le système d'exploitation (Windows, Linux, ...) ne fait pas exception.

Les programmes sont donnés au circuit/à l’ordinateur en passant par les périphériques. De nos jours, ils sont gravés sur des CD ou DVD ou téléchargés depuis Internet, et sont ensuite installés sur l’ordinateur. Sur d’anciens ordinateurs, les programmes étaient mis sur des disquettes, de petits supports magnétiques qu’on insérait dans l’ordinateur le temps de leur utilisation. Avant les disquettes, on utilisait d’autres supports, comme des cartes perforées en plastique, sur lesquelles on inscrivait le programme. Sur d’anciens ordinateur personnels, comme l’Amstrad ou le Commodore, on pouvait aussi taper les programmes à exécuter à la main, au clavier, avant d’appuyer une touche pour les exécuter. Sur Arduino, le programme est envoyé via le port USB de la carte, si on se débrouille convenablement.

Les composants d'un ordinateur[modifier | modifier le wikicode]

Éclaté d'un ordinateur de type PC :
1 : Écran ;
2 : Carte mère ;
3 : Processeur ;
4 : Câble Parallel ATA ;
5 : Mémoire vive (RAM) ;
6 : Carte d'extension ;
7 : Alimentation électrique ;
8 : Lecteur de disque optique ;
9 : Disque dur ;
10 : Clavier ;
11 : Souris.

De nombreux appareils sont programmables, mais tous ne sont pas des ordinateurs. Par exemple, certains circuits programmables nommés FPGA n'en sont pas. Pour être qualifié d'ordinateur, un appareil programmable doit avoir d'autres propriétés. L'une d'entre elle est de contenir plusieurs composants séparés, aux fonctions bien distinctes. De l'extérieur, l'ordinateur est composé d'une unité centrale sur laquelle on branche des périphériques.

Les périphériques regroupent l'écran, la souris, le clavier, l'imprimante, et bien d'autres choses. Ils permettent à l'utilisateur d'interagir avec l'ordinateur : un clavier permet de saisir du texte sous dans un fichier, une souris enregistre des déplacements de la main en déplacement du curseur, un écran affiche des données d’images/vidéos, un haut-parleur émet du son, etc. Tout ce qui est branché sur un ordinateur est, formellement un périphérique.

L'unité centrale est là où se trouvent tous les composants importants d'un ordinateur, ceux qui font des calculs, qui exécutent des logiciels, qui mémorisent vos données, etc. Dans les ordinateurs portables, l'unité centrale est bien là, située sous le clavier ou dans l'écran (le plus souvent sous le clavier). À l'intérieur de l'unité centrale, on trouve trois composants principaux : le processeur, la mémoire et les entrée-sorties.

  • Le processeur traite les données, les modifie, les manipule. Pour faire simple, il s’agit d’une grosse calculatrice hyper-puissante. Il comprend à la fois un circuit qui fait des calculs, et un circuit de contrôle qui s'occupe de séquencer les calculs dans l'ordre demandé.
  • La mémoire vive conserve des informations/données temporairement, tant que le processeur en a besoin.
  • Les entrée-sorties permettent à l’ordinateur de communiquer avec l’extérieur. C'est sur celles-ci que l'on branche les périphériques.
  • La carte mère n'est autre que le circuit imprimé, la carte électronique, sur laquelle sont soudés les autres composants.

Outre ces composants dits principaux, un ordinateur peut comprendre plusieurs composants moins importants, surtout présents sur les ordinateurs personnels. Ils sont techniquement facultatifs, mais sont très présents dans les ordinateurs personnels. Cependant, certains ordinateurs spécialisés s'en passent. Les voici :

  • L'alimentation électrique convertit le courant de la prise électrique en un courant plus faible, utilisable par les autres composants.
  • Diverses cartes d'extension sont branchées sur la carte mère. Elles permettent d’accélérer certains calculs ou certaines applications, afin de décharger le processeur. Par exemple, la carte graphique s'occupe des calculs graphiques, qu'il s'agisse de graphismes 3D de jeux vidéos ou de l'affichage en 2D du bureau. Dans un autre registre, la carte son prend en charge le microphone et les haut-parleurs.
  • Les disques durs sont des mémoires de stockage, qui mémorisent vos données de manière permanente.
  • Les lecteurs CD-ROM ou DVD-ROM permettent de lire des CD ou des DVD.
  • Et ainsi de suite.

Résumé[modifier | modifier le wikicode]

Pour résumer, les ordinateurs sont des appareils électroniques qui ont les propriétés suivantes.

  • Ils sont programmables.
  • Ils contiennent un processeur et une mémoire, reliés à des périphériques.
  • et surtout, ils utilisent un codage numérique, chose que nous allons aborder dans le chapitre suivant.

Ces points peuvent paraitre assez abstraits, mais rassurez-vous : nous allons les détailler tout au long de ce cours, au point qu'ils n'auront plus aucun secret pour vous d'ici quelques chapitres. Dans ce chapitre, nous allons détailler le premier point de la liste précédente, les autres étant laissés aux chapitres suivants.


Le codage des informations[modifier | modifier le wikicode]

Vous savez déjà qu'un ordinateur permet de faire plein de choses totalement différentes : écouter de la musique, lire des films/vidéos, afficher ou écrire du texte, retoucher des images, créer des vidéos, jouer à des jeux vidéos, etc. Pour être plus général, on devrait dire qu'un ordinateur manipule des informations, sous la forme de fichier texte, de vidéo, d'image, de morceau de musique, de niveau de jeux vidéos, etc. Dans ce qui suit, nous allons appeler ces informations par le terme données. On pourrait définir les ordinateurs comme des appareils qui manipulent des données et/ou qui traitent de l'information, mais force est de constater que cette définition, oh combien fréquente, n'est pas la bonne. Tous les appareils électroniques manipulent des données, même ceux qui ne sont pas des ordinateurs proprement dit : les exemples des décodeurs TNT et autres lecteurs de DVD sont là pour nous le rappeler. Même si la définition d’ordinateur est assez floue et que plusieurs définitions concurrentes existent, il est évident que les ordinateurs se distinguent des autres appareils électroniques programmables sur plusieurs points. Notamment, ils stockent leurs données d'une certaine manière (le codage numérique que nous allons aborder).

Le codage de l'information[modifier | modifier le wikicode]

Avant d'être traitée, une information doit être transformée en données exploitables par l'ordinateur, sans quoi il ne pourra pas en faire quoi que ce soit. Eh bien, sachez qu'elles sont stockées… avec des nombres. Toute donnée n'est qu'un ensemble de nombres structuré pour être compréhensible par l'ordinateur : on dit que les données sont codées par des nombres. Il suffit d'utiliser une machine à calculer pour manipuler ces nombres, et donc sur les données. Une simple machine à calculer devient une machine à traiter de l'information. Aussi bizarre que cela puisse paraitre, un ordinateur n'est qu'une sorte de grosse calculatrice hyper-performante. Mais comment faire la correspondance entre ces nombres et du son, du texte, ou toute autre forme d'information ? Et comment fait notre ordinateur pour stocker ces nombres et les manipuler ? Nous allons répondre à ces questions dans ce chapitre.

Toute information présente dans un ordinateur est décomposée en petites informations de base, chacune représentée par un nombre. Par exemple, le texte sera décomposé en caractères (des lettres, des chiffres, ou des symboles). Pareil pour les images, qui sont décomposées en pixels, eux-mêmes codés par un nombre. Même chose pour la vidéo, qui n'est rien d'autre qu'une suite d'images affichées à intervalles réguliers. La façon dont un morceau d'information (lettre ou pixel, par exemple) est représenté avec des nombres est définie par ce qu'on appelle un codage, parfois appelé improprement encodage. Ce codage va attribuer un nombre à chaque morceau d'information. Pour montrer à quoi peut ressembler un codage, on va prendre trois exemples : du texte, une image et du son.

Texte : standard ASCII[modifier | modifier le wikicode]

Caractères ASCII imprimables.

Pour coder un texte, il suffit de savoir coder une lettre ou tout autre symbole présent dans un texte normal (on parle de caractères). Pour coder chaque caractère avec un nombre, il existe plusieurs codages : l'ASCII, l'Unicode, etc.

Le codage le plus ancien, appelé l'ASCII, a été inventé pour les communications télégraphiques et a été ensuite réutilisé dans l'informatique et l'électronique à de nombreuses occasions. Il est intégralement défini par une table de correspondance entre une lettre et le nombre associé, appelée la table ASCII. Le standard ASCII originel utilise des nombres codés sur 7 bits (et non 8 comme beaucoup le croient), ce qui permet de coder 128 symboles différents. Les lettres sont stockées dans l'ordre alphabétique, pour simplifier la vie des utilisateurs : des nombres consécutifs correspondent à des lettres consécutives. L'ASCII ne code pas seulement des lettres, mais aussi d'autres symboles, dont certains ne sont même pas affichables ! Cela peut paraitre bizarre, mais s'explique facilement quand on connait les origines du standard. Ces caractères non-affichables servent pour les imprimantes, FAX et autres systèmes de télécopies. Pour faciliter la conception de ces machines, on a placé dans cette table ASCII des symboles qui n'étaient pas destinés à être affichés, mais dont le but était de donner un ordre à l'imprimante/machine à écrire... On trouve ainsi des symboles de retour à la ligne, par exemple.

La table ASCII a cependant des limitations assez problématiques. Par exemple, vous remarquerez que les accents n'y sont pas, ce qui n'est pas étonnant quand on sait qu'il s'agit d'un standard américain. De même, impossible de coder un texte en grec ou en japonais : les idéogrammes et les lettres grecques ne sont pas dans la table ASCII. Pour combler ce manque, de nombreuses autres codages du texte sont apparus. Les premiers codages étendus se sont contentés d'étendre l'ASCII en rajoutant des caractères à la table ASCII de base. De tels codages sont appelés des codages ASCII étendus, ils sont assez nombreux et ne sont pas compatibles entre eux. Le plus connu et le plus utilisé est certainement le codage ISO 8859 et ses dérivés, utilisés par de nombreux systèmes d'exploitation et logiciels en occident. Ce codage code ses caractères sur 8 bits et est rétrocompatible ASCII, ce qui fait qu'il est parfois confondu avec ce dernier alors que les deux sont très différents. Aujourd'hui, le standard de codage de texte le plus connu est certainement l’Unicode. L'Unicode est parfaitement compatible avec la table ASCII : les 128 premiers symboles de l’Unicode sont ceux de la table ASCII, et sont rangés dans le même ordre. Là où l'ASCII ne code que l'alphabet anglais, les codages actuels comme l'Unicode prennent en compte les caractères chinois, japonais, grecs, etc.

Image[modifier | modifier le wikicode]

Image matricielle.

Le même principe peut être appliqué aux images : l'image est décomposée en morceaux de même taille qu'on appelle des pixels. L'image est ainsi vue comme un rectangle de pixels, avec une largeur et une longueur. Le nombre de pixels en largeur et en longueur définit la résolution de l'image : par exemple, une image avec 800 pixels de longueur et 600 en largeur sera une image dont la résolution est de 800*600. Il va de soi que plus cette résolution est grande, plus l'image sera fine et précise. On peut d'ailleurs remarquer que les images en basse résolution ont souvent un aspect dit pixelisé, où les bords des objets sont en marche d'escaliers.

Chaque pixel a une couleur qui est codée par un ou plusieurs nombres entiers. D'ordinaire, la couleur d'un pixel est définie par un mélange des trois couleurs primaires rouge, vert et bleu. Par exemple, la couleur jaune est composée à 50 % de rouge et à 50 % de vert. Pour coder la couleur d'un pixel, il suffit de coder chaque couleur primaire avec un nombre entier : un nombre pour le rouge, un autre pour le vert et un dernier pour le bleu. Ce codage est appelé le codage RGB. Mais il existe d'autres méthodes, qui codent un pixel non pas à partir des couleurs primaires, mais à partir d'autres espaces de couleur.

Pour stocker une image dans l'ordinateur, on a besoin de connaitre sa largeur, sa longueur et la couleur de chaque pixel. Une image peut donc être représentée dans un fichier par une suite d'entiers : un pour la largeur, un pour la longueur, et le reste pour les couleurs des pixels. Ces entiers sont stockés les uns à la suite des autres dans un fichier. Les pixels sont stockés ligne par ligne, en partant du haut, et chaque ligne est codée de gauche à droite. Les fichiers image actuels utilisent des techniques de codage plus élaborées, permettant notamment décrire une image en utilisant moins de nombres, ce qui prend moins de place dans l'ordinateur.

Son[modifier | modifier le wikicode]

Pour mémoriser du son, il suffit de mémoriser l'intensité sonore reçue par un microphone à intervalles réguliers. Cette intensité est codée par un nombre entier : si le son est fort, le nombre sera élevé, tandis qu'un son faible se verra attribuer un entier petit. Ces entiers seront rassemblés dans l'ordre de mesure, et stockés dans un fichier son, comme du wav, du PCM, etc. Généralement, ces fichiers sont compressés afin de prendre moins de place.

Le support physique de l'information codée[modifier | modifier le wikicode]

Pour pouvoir traiter de l'information, la première étape est d'abord de coder celle-ci, c'est à dire de la transformer en nombres. Et peu importe le codage utilisé, celui-ci a besoin d'un support physique, d'une grandeur physique quelconque. Et pour être franc, on peut utiliser tout et n’importe quoi. Par exemple, certains calculateurs assez anciens étaient des calculateurs pneumatiques, qui utilisaient la pression de l'air pour représenter des chiffres ou nombres : soit le nombre encodé était proportionnel à la pression, soit il existait divers intervalles de pression correspondant chacun à un nombre entier bien précis. Il a aussi existé des technologies purement mécaniques pour ce faire, comme les cartes perforées ou d'autres dispositifs encore plus ingénieux. De nos jours, ce stockage se fait soit par l'aimantation d'un support magnétique, soit par un support optique (les CD et DVD), soit par un support électronique. Les supports magnétiques sont réservés aux disques durs magnétiques, destinés à être remplacés par des disques durs entièrement électroniques (les fameux Solid State Drives, que nous verrons dans quelques chapitres).

Pour les supports de stockage électroniques, très courants dans nos ordinateurs, le support en question est une tension électrique. Ces tensions sont ensuite manipulées par des composants électriques/électroniques plus ou moins sophistiqués : résistances, condensateurs, bobines, amplificateurs opérationnels, diodes, transistors, etc. Certains d'entre eux ont besoin d'être alimentés en énergie. Pour cela, chaque circuit est relié à une tension qui l'alimente en énergie : la tension d'alimentation. Après tout, la tension qui code les nombres ne sort pas de nulle part et il faut bien qu'il trouve de quoi fournir une tension de 2, 3, 5 volts. De même, on a besoin d'une tension de référence valant zéro volt, qu'on appelle la masse, qui sert pour le zéro.

Dans les circuits électroniques actuels, ordinateurs inclus, la tension d'alimentation varie généralement entre 0 et 5 volts. Mais de plus en plus, on tend à utiliser des valeurs de plus en plus basses, histoire d'économiser un peu d'énergie. Eh oui, car plus un circuit utilise une tension élevée, plus il consomme d'énergie et plus il chauffe. Pour un processeur, il est rare que les modèles récents utilisent une tension supérieure à 2 volts : la moyenne tournant autour de 1-1.5 volts. Même chose pour les mémoires : la tension d'alimentation de celle-ci diminue au cours du temps. Pour donner des exemples, une mémoire DDR a une tension d'alimentation qui tourne autour de 2,5 volts, les mémoires DDR2 ont une tension d'alimentation qui tombe à 1,8 volts, et les mémoires DDR3 ont une tension d'alimentation qui tombe à 1,5 volts. C'est très peu : les composants qui manipulent ces tensions doivent être très précis.

Les différents codages : analogique, numérique et binaire[modifier | modifier le wikicode]

Codage numérique : exemple du codage d'un chiffre décimal avec une tension.

Le codage, la transformation d’information en nombre, peut être fait de plusieurs façons différentes. Dans les grandes lignes, on peut identifier deux grands types de codages.

  • Le codage analogique utilise des nombres réels : il code l’information avec des grandeurs physiques (quelque chose que l'on peut mesurer par un nombre) comprises dans un intervalle. Par exemple, un thermostat analogique convertit la température en tension électrique pour la manipuler : une température de 0 degré donne une tension de 0 volts, une température de 20 degrés donne une tension de 5 Volts, une température de 40 degrés donnera du 10 Volts, etc. Un codage analogique a une précision théoriquement infinie : on peut par exemple utiliser toutes les valeurs entre 0 et 5 Volts pour coder une information, même des valeurs tordues comme 1, 2.2345646, ou pire…
  • Le codage numérique n'utilise qu'un nombre fini de valeurs, contrairement au codage analogique. Pour être plus précis, il code des informations en utilisant des nombres entiers, représentés par des suites de chiffres. Le codage numérique précise comment coder les chiffres avec une tension. Comme illustré ci-contre, chaque chiffre correspond à un intervalle de tension : la tension code pour ce chiffre si elle est comprise dans cet intervalle. Cela donnera des valeurs de tension du style : 0, 0.12, 0.24, 0.36, 0.48… jusqu'à 2 volts.

Les avantages et désavantages de l'analogique et du numérique : la sensibilité au bruit, la programmabilité[modifier | modifier le wikicode]

Un calculateur analogique (qui utilise le codage analogique) peut en théorie faire ses calculs avec une précision théorique très fine, impossible à atteindre avec un calculateur numérique, notamment pour les opérations comme les dérivées, intégrations et autres calculs similaires. Mais dans les faits, aucune machine analogique n'est parfaite et la précision théorique est rarement atteinte, loin de là. Les imperfections des machines posent beaucoup plus de problèmes sur les machines analogiques que sur les machines numériques.

Obtenir des calculs précis sur un calculateur analogique demande non seulement d'utiliser des composants de très bonne qualité, à la conception quasi-parfaite, mais aussi d'utiliser des techniques de conception particulières. Même les composants de qualité ont des imperfections certes mineures, qui peuvent cependant sévèrement perturber les résultats. Les moyens pour réduire ce genre de problème sont très complexes, ce qui fait que la conception des calculateurs analogiques est diablement complexe, au point d'être une affaire de spécialistes. Concevoir ces machines est non seulement très difficile, mais tester leur bon fonctionnement ou corriger des pannes est encore plus complexe.

De plus, les calculateurs analogiques sont plus sensibles aux perturbations électromagnétiques. On dit aussi qu'ils ont une faible immunité au bruit. En effet, un signal analogique peut facilement subir des perturbations qui vont changer sa valeur, modifiant directement la valeur des nombres stockés ou manipulés. Avec un codage numérique, les perturbations ou parasites vont moins perturber le signal numérique. La raison est qu'une variation de tension qui reste dans un intervalle représentant un chiffre ne changera pas sa valeur. Il faut que la variation de tension fasse sortir la tension de l'intervalle pour changer le chiffre. Cette sensibilité aux perturbations est un désavantage net pour l'analogique et est une des raisons qui font que les calculateurs analogiques sont peu utilisés de nos jours. Elle rend difficile de faire fonctionner un calculateur analogique rapidement et limite donc sa puissance.

Un autre désavantage est que les calculateurs analogiques sont très spécialisés et qu'ils ne sont pas programmables. Un calculateur analogique est forcément conçu pour résoudre un problème bien précis. On peut le reconfigurer, le modifier à la marge, mais guère plus. Typiquement, les calculateurs analogiques sont utilisés pour résoudre des équations différentielles couplées non-linéaires, mais n'ont guère d'utilité pratique au-delà. Mais les ingénieurs ne font cela que pour les problèmes où il est pertinent de concevoir de zéro un calculateur spécialement dédié au problème à résoudre, ce qui est un cas assez rare.

Le choix de la base[modifier | modifier le wikicode]

Au vu des défauts des calculateurs analogiques, on devine que la grosse majorité des circuits électronique actuels sont numériques. Mais il faut savoir que les ordinateurs n'utilisent pas la numération décimale normale, celle à 10 chiffres qui vont de 0 à 9. De nos jours, les ordinateurs n'utilisent que deux chiffres, 0 et 1 (on parle de « bit ») : on dit qu'ils comptent en binaire. On verra dans le chapitre suivant comment coder des nombres avec des bits, ce qui est relativement simple. Pour le moment, nous allons justifier ce choix de n'utiliser que des bits et pas les chiffres décimaux (de 0 à 9). Avec une tension électrique, il y a diverses méthodes pour coder un bit : codage Manchester, NRZ, etc. Ces diverses méthodes ont chacune leurs avantages et leurs défauts.

Autant trancher dans le vif tout de suite : la quasi-intégralité des circuits d'un ordinateur se basent sur le codage NRZ. Pour coder un 0 en NRZ, la tension doit être en dessous d'un seuil donné pour un 0. Et, pour coder un 1, il existe un autre seuil au-dessus duquel la tension représente un 1. Du moins, c'est ainsi dans la majorité des cas : il arrive que ce soit l'inverse sur certains circuits électroniques : en dessous d'un certain seuil, c'est un 1 et si c'est au-dessus d'un autre seuil c'est 0. Tout ce qu'il faut retenir, c'est qu'il y a un intervalle pour le 0 et un autre pour le 1. En dehors de ces intervalles, on considère que le circuit est trop imprécis pour pouvoir conclure sur la valeur de la tension : on ne sait pas trop si c'est un 1 ou un 0. Il y a deux seuils, car les circuits qui manipulent des tensions n'ont pas une précision parfaite, et qu'une petite perturbation électrique pourrait alors transformer un 0 en 1. Pour limiter la casse, on préfère séparer ces deux seuils par une sorte de marge de sécurité.

Codage NRZ

L'avantage du binaire par rapport aux autres codages est qu'il permet de mieux résister aux perturbations électromagnétiques mentionnées dans le chapitre précédent. À tension d'alimentation égale, les intervalles de chaque chiffre sont plus petits pour un codage décimal : toute perturbation de la tension aura plus de chances de changer un chiffre. Mais avec des intervalles plus grands, un parasite aura nettement moins de chance de modifier la valeur du chiffre codé ainsi. La résistance aux perturbations électromagnétiques est donc meilleure avec seulement deux intervalles.

Comparaison entre codage binaire et décimal pour l'immunité au bruit.


Dans le chapitre précédent, nous avons vu que les ordinateurs actuels utilisent un codage binaire. Ce codage binaire ne vous est peut-être pas familier. Aussi, dans ce chapitre, nous allons apprendre comment coder des nombres en binaire. Nous allons commencer par le cas le plus simple : les nombres positifs. Par la suite, nous aborderons les nombres négatifs. Et nous terminerons par les nombres à virgules, appelés aussi nombres flottants.

Le codage des nombres entiers positifs[modifier | modifier le wikicode]

Pour coder des nombres entiers positifs, il existe plusieurs méthodes : le binaire, l’hexadécimal, le code Gray et le décimal codé binaire. La plus connue est certainement le binaire, secondée par l'hexadécimal, les deux autres étant plus anecdotiques. Pour comprendre ce qu'est le binaire, il nous faut faire un rappel sur les nombres entiers tel que vous les avez appris en primaire, à savoir les entiers écrits en décimal. Prenons un nombre écrit en décimal : le chiffre le plus à droite est le chiffre des unités, celui à côté est pour les dizaines, suivi du chiffre des centaines, et ainsi de suite. Dans un tel nombre :

  • on utilise une dizaine de chiffres, de 0 à 9 ;
  • chaque chiffre est multiplié par une puissance de 10 : 1, 10, 100, 1000, etc. ;
  • la position d'un chiffre dans le nombre indique par quelle puissance de 10 il faut le multiplier : le chiffre des unités doit être multiplié par 1, celui des dizaines par 10, celui des centaines par 100, et ainsi de suite.

Exemple avec le nombre 1337 :

Pour résumer, un nombre en décimal s'écrit comme la somme de produits, chaque produit multipliant un chiffre par une puissance de 10. On dit alors que le nombre est en base 10.

Ce qui peut être fait avec des puissances de 10 peut être fait avec des puissances de 2, 3, 4, 125, etc : n'importe quel nombre entier strictement positif peut servir de base. En informatique, on utilise rarement la base 10 à laquelle nous sommes tant habitués. On utilise à la place deux autres bases :

  • La base 2 (système binaire) : les chiffres utilisés sont 0 et 1 ;
  • La base 16 (système hexadécimal) : les chiffres utilisés sont 0, 1, 2, 3, 4, 5, 6, 7, 8 et 9 ; auxquels s'ajoutent les six premières lettres de notre alphabet : A, B, C, D, E et F.

Le système binaire[modifier | modifier le wikicode]

En binaire, on compte en base 2. Cela veut dire qu'au lieu d'utiliser des puissances de 10 comme en décimal, on utilise des puissances de deux : n'importe quel nombre entier peut être écrit sous la forme d'une somme de puissances de 2. Par exemple 6 s'écrira donc 0110 en binaire : . On peut remarquer que le binaire n'autorise que deux chiffres, à savoir 0 ou 1 : ces chiffres binaires sont appelés des bits (abréviation de Binary Digit). Pour simplifier, on peut dire qu'un bit est un truc qui vaut 0 ou 1. Pour résumer, tout nombre en binaire s'écrit sous la forme d'un produit entre bits et puissances de deux de la forme :

Les coefficients sont les bits, l'exposant n qui correspond à un bit est appelé le poids du bit.

La terminologie du binaire[modifier | modifier le wikicode]

En informatique, il est rare que l'on code une information sur un seul bit. Dans la plupart des cas, l'ordinateur manipule des nombres codés sur plusieurs bits. Les informaticiens ont donné des noms aux groupes de bits suivant leur taille. Le plus connu est certainement l'octet, qui désigne un groupe de 8 bits. Moins connu, on parle de nibble pour un groupe de 4 bits (un demi-octet), de doublet pour un groupe de 16 bits (deux octets) et de quadruplet pour un groupe de 32 bits (quatre octets).

Nibbles dans un octet.
Octets et nibbles dans un doublet.

Précisons qu'en anglais, le terme byte n'est pas synonyme d'octet. En réalité, le terme octet marche aussi bien en français qu'en anglais. Quant au terme byte, il désigne un concept complètement différent, que nous aborderons plus tard (c'est la plus petite unité de mémoire que le processeur peut adresser). Il a existé dans le passé des ordinateurs où le byte faisait 4, 7, 9, 16, voire 48 bits, par exemple. Il a même existé des ordinateur où le byte faisait exactement 1 bit ! Mais sur presque tous les ordinateurs modernes, un byte fait effectivement 8 bits, ce qui fait que le terme byte est parfois utilisé en lieu et place d'octet. Mais c'est un abus de langage, attention aux confusions ! Dans ce cours, nous parlerons d'octet pour désigner un groupe de 8 bits, en réservant le terme byte pour sa véritable signification.

À l'intérieur d'un nombre, le bit de poids faible est celui qui est le plus à droite du nombre, alors que le bit de poids fort est celui non nul qui est placé le plus à gauche, comme illustré dans le schéma ci-dessous.

Bit de poids fort.
Bit de poids faible.

Cette terminologie s'applique aussi pour les bits à l'intérieur d'un octet, d'un nibble, d'un doublet ou d'un quadruplet. Pour un nombre codés sur plusieurs octets, on peut aussi parler de l'octet de poids fort et de l'octet de poids faible, du doublet de poids fort ou de poids faible, etc.

Traduction binaire→décimal et décimal→binaire[modifier | modifier le wikicode]

Pour traduire un nombre binaire en décimal, il faut juste se rappeler que la position d'un bit indique par quelle puissance il faut le multiplier. Ainsi, le chiffre le plus à droite est le chiffre des unités : il doit être multiplié par 1 (). Le chiffre situé immédiatement à gauche du chiffre des unités doit être multiplié par 2 (). Le chiffre encore à gauche doit être multiplié par 4 (), et ainsi de suite. Mathématiquement, on peut dire que le énième bit en partant de la droite doit être multiplié par . Par exemple, la valeur du nombre noté 1011 en binaire est de .

Value of digits in the Binary numeral system

La traduction inverse, du décimal au binaire, demande d'effectuer des divisions successives par deux. Les divisions en question sont des divisions euclidiennes, avec un reste et un quotient. En lisant les restes des divisions dans un certain sens, on obtient le nombre en binaire. Voici comment il faut procéder, pour traduire le nombre 34 :

Exemple d'illustration de la méthode de conversion décimal vers binaire.

Le lien entre nombre de bits et valeurs codables[modifier | modifier le wikicode]

Vous vous demandez certainement combien de valeurs différentes on peut coder avec bits. Par exemple, combien de nombres différents peut-on coder avec 4, 8 ou 16 bits ? La réponse est simple : avec bits, on peut coder valeurs différentes, dont le , ce qui fait qu'on peut compter de à . N'oubliez pas cette formule : elle sera assez utile dans la suite de ce tutoriel. Pour exemple, on peut coder 16 valeurs avec 4 bits, qui vont de 0 à 15. De même, on peut coder 256 valeurs avec un octet, qui vont de 0 à 255. Le tableau ci-dessous donne quelques exemples communs.

Nombre de bits Nombre de valeurs codables
4 16
8 256
16 65 536
32 4 294 967 296
64 18 446 744 073 709 551 615

Inversement, on peut se demander combien de bits il faut pour coder une valeur quelconque, que nous noterons N. Pour cela, il faut utiliser la formule précédente, mais à l'envers. On cherche alors tel que . L'opération qui donne est appelée le logarithme, et plus précisément un logarithme en base 2, noté . Le problème est que le résultat du logarithme ne tombe juste que si le nombre X est une puissance de 2. Si ce n'est pas le cas, le résultat est un nombre à virgule, ce qui n'a pas de sens pratique. Par exemple, la formule nous dit que pour coder le nombre 13, on a besoin de 3,70043971814 bits, ce qui est impossible. Pour que le résultat ait un sens, il faut arrondir à l'entier supérieur. Pour l'exemple précédent, les 3,70043971814 bits s'arrondissent en 4 bits.

L'hexadécimal[modifier | modifier le wikicode]

L’hexadécimal est basé sur le même principe que le binaire, sauf qu'il utilise les 16 chiffres suivants :

Chiffre hexadécimal 0 1 2 3 4 5 6 7 8 9 A B C D E F
Nombre décimal correspondant 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Notation binaire 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

Dans les textes, afin de différencier les nombres décimaux des nombres hexadécimaux, les nombres hexadécimaux sont suivis par un petit h, indiqué en indice. Si cette notation n'existait pas, des nombres comme 2546 seraient ambigus : on ne saurait pas dire sans autre indication s'ils sont écrits en décimal ou en hexadécimal. Avec la notation, on sait de suite que 2546 est en décimal et que 2546h est en hexadécimal.

Dans les codes sources des programmes, la notation diffère selon le langage de programmation. Certains supportent le suffixe h pour les nombres hexadécimaux, d'autres utilisent un préfixe 0x ou 0h.

Les traductions hexadécimal↔décimal et hexadécimal↔binaire[modifier | modifier le wikicode]

Pour convertir un nombre hexadécimal en décimal, il suffit de multiplier chaque chiffre par la puissance de 16 qui lui est attribuée. Là encore, la position d'un chiffre indique par quelle puissance celui-ci doit être multiplié : le chiffre le plus à droite est celui des unités, le second chiffre le plus à droite doit être multiplié par 16, le troisième chiffre en partant de la droite doit être multiplié par 256 (16 * 16) et ainsi de suite. La technique pour convertir un nombre décimal vers de l’hexadécimal est similaire à celle utilisée pour traduire un nombre du décimal vers le binaire. On retrouve une suite de divisions successives, mais cette fois-ci les divisions ne sont pas des divisions par 2 : ce sont des divisions par 16.

La conversion inverse, de l'hexadécimal vers le binaire est très simple, nettement plus simple que les autres conversions. Pour passer de l'hexadécimal au binaire, il suffit de traduire chaque chiffre en sa valeur binaire, celle indiquée dans le tableau au tout début du paragraphe nommé « Hexadécimal ». Une fois cela fait, il suffit de faire le remplacement. La traduction inverse est tout aussi simple : il suffit de grouper les bits du nombre par 4, en commençant par la droite (si un groupe est incomplet, on le remplit avec des zéros). Il suffit alors de remplacer le groupe de 4 bits par le chiffre hexadécimal qui correspond.

Le lien entre nombre de chiffres hexadécimaux et valeurs codables[modifier | modifier le wikicode]

Maintenant, voyons combien de valeurs peut-on coder avec chiffres hexadécimaux. La réponse n'est pas très différente de celle obtenue en binaire, si ce n'est qu'il faut remplacer le 2 par un 16 dans la formule précédente. Avec chiffres hexadécimaux, on peut coder valeurs différentes, dont le , ce qui fait qu'on peut compter de à . Le tableau ci-dessous donne quelques exemples communs.

Nombre de chiffres héxadécimaux Nombre de valeurs codables
1 (4 bits) 16
2 (8 bits) 256
4 (16 bits) 65 536
8 (32 bits) 4 294 967 296
16 (64 bits) 18 446 744 073 709 551 615

Inversement, on peut se demander combien faut-il de chiffres hexadécimaux pour coder une valeur quelconque en hexadécimal. La formule est là encore la même qu'en binaire, sauf qu'on remplace le 2 par un 16. Pour trouver le nombre de chiffres hexadécimaux pour encoder un nombre X, il faut calculer . Notons que le logarithme utilisé est un logarithme en base 16, et non un logarithme en base 2, comme pour le binaire. Là encore, le résultat ne tombe juste que si le nombre X est une puissance de 16 et il faut arrondir à l'entier supérieur si ce n'est pas le cas.

Une propriété mathématique des logarithmes nous dit que l'on peut passer d'un logarithme en base X et à un logarithme en base Y avec une simple division, en utilisant la formule suivante :

Dans le cas qui nous intéresse, on a Y = 2 et X = 16, ce qui donne :

Or, est tout simplement égal à 4, car il faut 4 bits pour coder la valeur 16. On a donc :

En clair, il faut quatre moins de chiffres hexadécimaux que de bits, ce qui est assez intuitif vu qu'il faut 4 bits pour coder un chiffre hexadécimal.

Le Binary Coded Decimal[modifier | modifier le wikicode]

Le Binary Coded Decimal, abrévié BCD, est une représentation qui mixe binaire et décimal. Avec cette représentation, les nombres sont écrits en décimal, comme nous en avons l'habitude dans la vie courante, sauf que chaque chiffre décimal est directement traduit en binairen sur 4 bits. Prenons l'exemple du nombre 624 : le 6, le 2 et le 4 sont codés en binaire séparément, ce qui donne 0110 0010 0100.

Codage BCD
Nombre encodé (décimal) BCD
0 0 0 0 0
1 0 0 0 1
2 0 0 1 0
3 0 0 1 1
4 0 1 0 0
5 0 1 0 1
6 0 1 1 0
7 0 1 1 1
8 1 0 0 0
9 1 0 0 1

On peut remarquer que 4 bits permettent de coder 16 valeurs, là où il n'y a que 10 chiffres. Dans le BCD proprement dit, les combinaisons de bits qui correspondent à 10, 11, 12, 13, 14 ou 15 n'ont aucune utilité et ne sont tout simplement pas prises en compte. Mais certaines variantes du BCD les utilisaient pour représenter d'autres symboles, comme un signe + ou - afin de gérer les entiers relatifs, ou une virgule pour gérer les nombres non-entiers. Mais sur d'autres ordinateurs, ces combinaisons servaient à coder des chiffres décimaux en double : certains chiffres pouvaient être codés de deux manières différentes.

Les variantes du BCD sont assez nombreuses. L'une d'entre elle est la représentation Excess-3. Avec elle, la conversion d'un chiffre décimal se fait comme suit : on prend le chiffre décimal, on ajoute 3, puis on traduit en binaire. L'avantage de cette représentation est que l'on peut facilement calculer les soustractions en utilisant une méthode bien précise (celle du complément à 10, je ne détaille pas plus). Le défaut est que le calcul des additions est légèrement plus complexe.

Codage en Excess-3
Nombre encodé (décimal) BCD
0 0 0 1 1
1 0 1 0 0
2 0 1 0 1
3 0 1 1 0
4 0 1 1 1
5 1 0 0 0
6 1 0 0 1
7 1 0 1 0
8 1 0 1 1
9 1 1 0 0

D'autres variantes du BCD visent à réduire le nombre de bits utilisés pour encoder un nombre décimal. Avec certaines variantes, on peut utiliser seulement 7 bits pour coder deux chiffres décimaux, au lieu de 8 bits en BCD normal. Idem pour les nombres à 3 chiffres décimaux, qui prennent 10 bits au lieu de 12. Cette économie est réalisée par une variante du BCD assez compliquée, appelée l'encodage Chen-Ho. Une alternative, appelée le Densely Packed Decimal, arrive à une compression identique, mais avec quelques avantages au niveau de l'encodage. Cse encodage sont cependant assez compliqués à expliquer, surtout à ce niveau du cours, aussi je me contente de simplement mentionner leur existence.

Le BCD et ses variantes étaient utilisés sur les tous premiers ordinateurs pour faciliter le travail des programmeurs, mais aussi sur les premières calculettes. Le BCD est utile dans les applications où on doit manipuler chaque chiffre décimal séparément des autres. Un exemple classique est celui d'une horloge digitale. Il a aussi l'avantage de bien se marier avec les nombres à virgule. Comme nous le verrons plus tard, coder des nombres à virgule en binaire est loin d'être une chose facile et plusieurs représentations existent. Toutes ont le défaut que des arrondis peuvent survenir. Par exemple, la valeur 0,2 est codée comme suit en binaire normal : 0.00110011001100... et ainsi de suite jusqu’à l'infini. Avec le BCD, on n'a pas ce problème, 0,2 étant codé 0000 , 0010.

Le code Gray[modifier | modifier le wikicode]

Avec le code Gray, deux nombres consécutifs n'ont qu'un seul bit de différence. Pour construire ce code Gray, on peut procéder en suivant plusieurs méthodes, les deux plus connues étant la méthode du miroir et la méthode de l'inversion.

Méthode du miroir[modifier | modifier le wikicode]

Construction d'un code gray par la méthode du miroir.

La méthode du miroir est relativement simple. Pour connaître le code Gray des nombres codés sur n bits, il faut :

  • partir du code Gray sur n-1 bits ;
  • symétriser verticalement les nombres déjà obtenus (comme une réflexion dans un miroir) ;
  • rajouter un 0 au début des anciens nombres, et un 1 au début des nouveaux nombres.

Il suffit de connaître le code Gray sur 1 bit pour appliquer la méthode : 0 est codé par le bit 0 et 1 par le bit 1.

Méthode de l'inversion[modifier | modifier le wikicode]

Une autre méthode pour construire la suite des nombres en code Gray sur n bits est la méthode de l'inversion. Celle-ci permet de connaître le codage du nombre n à partir du codage du nombre n-1, comme la méthode du dessus. On part du nombre 0, systématiquement codé avec uniquement des zéros. Par la suite, on décide quel est le bit à inverser pour obtenir le nombre suivant, avec la règle suivante :

  • si le nombre de 1 est pair, il faut inverser le dernier chiffre.
  • si le nombre de 1 est impair, il faut localiser le 1 le plus à droite et inverser le chiffre situé à sa gauche.

Pour vous entraîner, essayez par vous-même avec 2, 3, voire 5.

Interlude propédeutique : les débordements d'entiers[modifier | modifier le wikicode]

Dans la section précédente, nous avons vu comment coder des entiers positifs en binaire ou dans des représentations proches. La logique voudrait que l'on aborde ensuite le codage des entiers négatifs. Mais nous allons déroger à cette logique simple, pour des raisons pédagogiques. Avant de passer aux nombres négatifs, nous allons faire un interlude qui introduira des notions utiles pour la suite. Ces notions permettront d'introduire les notions nécessaires pour comprendre le complément à un et à deux. De plus, ces concepts seront abordés de nombreuses fois dans ce wikilivre et l'introduire ici est de loin une solution idéale. Voyons donc maintenant ce que sont les débordements d'entiers (integer overflow en anglais).

Les débordements d'entier[modifier | modifier le wikicode]

Tout ordinateur manipule des entiers de taille fixe, dont le nombre de bits est toujours le même. Pour les nombres positifs, un ordinateur qui code ses entiers sur n bits pourra coder tous les entiers allant de 0 à . Tout nombre en dehors de cet intervalle ne peut pas être représenté. Mais on peut imaginer d'autres codages pour lesquels les entiers ne commencent pas à zéro ou ne terminent pas à . On peut prendre le cas où l'ordinateur gère les nombres négatifs, par exemple. Dans le cas général, l'ordinateur peut coder les valeurs comprises de à . Si le résultat d'un calcul sort de cet intervalle, il ne peut pas être représenté par l'ordinateur et il se produit ce qu'on appelle un débordement d'entier.

La valeur haute de débordement désigne la première valeur qui est trop grande pour être représentée par l'ordinateur. Par exemple, pour un ordinateur qui peut coder tous les nombres entre 0 et 7, la valeur haute de débordement est égale à 8. On peut aussi définir la valeur basse de débordement, qui est la première valeur trop petite pour être codée par l'ordinateur. Par exemple, pour un ordinateur qui peut coder tous les nombres entre 8 et 250, la valeur basse de débordement est égale à 7. Pour les nombres entiers, la valeur haute de débordement vaut , alors que la valeur basse vaut (avec et respectivement la plus grande et la plus petite valeur codable par l'ordinateur).

La gestion des débordements d'entiers[modifier | modifier le wikicode]

Exemple de débordement d'entier sur un compteur mécanique quelconque. L'image montre clairement que le compteur revient à zéro une fois la valeur maximale dépassée.

Face à un débordement d'entier, l'ordinateur peut utiliser deux méthodes : l'arithmétique saturée ou l'arithmétique modulaire.

  • L'arithmétique saturée consiste à arrondir le résultat au plus grand entier supporté par l'ordinateur si le résultat dépasse la valeur haute de débordement, ou au plus petit entier si la valeur basse est dépassée. La même chose est possible lors d'une soustraction, quand le résultat est inférieur à la plus petite valeur possible : l'ordinateur arrondit au plus petit entier possible.
  • L'arithmétique modulaire est plus compliquée et c'est elle qui va nous intéresser dans ce qui suit. Pour simplifier, imaginons que l'on décompte à partir de zéro. Quand on arrive à la valeur haute de débordement, on recommence à compter à partir de zéro. L'arithmétique modulaire n'est pas si contre-intuitive et vous l'utilisez sans doute au quotidien. Après tout, c'est comme cela que l'on compte les heures, les minutes et les secondes. Quand on compte les minutes, on revient à 0 au bout de 60 minutes. Pareil pour les heures : on revient à zéro quand on arrive à 24 heures. Divers compteurs mécaniques fonctionnent sur le même principe et reviennent à zéro quand ils dépassent la plus grande valeur possible, l'image ci-contre en montrant un exemple.

Mathématiquement, l'arithmétique modulaire implique des divisions euclidiennes, celles qui donnent un quotient et un reste. Lors d'un débordement, le résultat s'obtient comme suit : on divise le nombre qui déborde par la valeur haute de débordement, et que l'on conserve le reste de la division. Au passage, l'opération qui consiste à faire une division et à garder le reste au lieu du quotient est appelée le modulo. Prenons l'exemple où l'ordinateur peut coder tous les nombres entre 0 et 1023, soit une valeur haute de débordement de 1024. Pour coder le nombre 4563, on fait le calcul 4563 / 1024. On obtient : . Le reste de la division est de 467 et c'est lui qui sera utilisé pour coder la valeur de départ, 4563. Le nombre 4563 est donc codé par la valeur 467 dans un tel ordinateur en arithmétique modulaire. Au passage, la valeur haute de débordement est toujours codée par un zéro dans ce genre d'arithmétique.

Les ordinateurs utilisent le plus souvent une valeur haute de débordement de , avec n le nombre de bits utilisé pour coder les nombres entiers positifs. En faisant cela, l'opération modulo devient très simple et revient à éliminer les bits de poids forts au-delà du énième bit. Concrètement, l'ordinateur ne conserve que les n bits de poids faible du résultat : les autres bits sont oubliés. Par exemple, reprenons l'exemple d'un ordinateur qui code ses nombres sur 4 bits. Imaginons qu'il fasse le calcul , soit 1101 + 0011 = 1 0000 en binaire. Le résultat entraîne un débordement d'entier et l'ordinateur ne conserve que les 4 bits de poids faible. Cela donne : 1101 + 0011 = 0000. Comme autre exemple l'addition 1111 + 0010 ne donnera pas 17 (1 0001), mais 1 (0001).

Les nombres entiers négatifs[modifier | modifier le wikicode]

Passons maintenant aux entiers négatifs en binaire : comment représenter le signe moins ("-") avec des 0 et des 1 ? Eh bien, il existe plusieurs méthodes :

  • la représentation en signe-valeur absolue ;
  • la représentation en complément à un ;
  • la représentation en complément à deux;
  • la représentation par excès ;
  • la représentation dans une base négative ;
  • d'autres représentations encore moins utilisées que les autres.

La représentation en signe-valeur absolue[modifier | modifier le wikicode]

Codage des nombres en signe-magnitude sur 4 bits.

La solution la plus simple pour représenter un entier négatif consiste à coder sa valeur absolue en binaire, et rajouter un bit qui précise si c'est un entier positif ou un entier négatif. Par convention, ce bit de signe vaut 0 si le nombre est positif et 1 s'il est négatif. Avec cette technique, l'intervalle des entiers représentables sur N bits est symétrique : pour chaque nombre représentable en représentation signe-valeur absolue, son inverse l'est aussi. Ce qui fait qu'avec cette méthode, le zéro est codé deux fois : on a un -0, et un +0. Cela pose des problèmes lorsqu'on demande à notre ordinateur d'effectuer des calculs ou des comparaisons avec zéro.

Codage sur 4 bits en signe-valeur absolue

La représentation par excès[modifier | modifier le wikicode]

La représentation par excès consiste à ajouter un biais aux nombres à encoder afin de les encoder par un entier positif. Pour encoder tous les nombres compris entre -X et Y en représentation par excès, il suffit de prendre la valeur du nombre à encoder, et de lui ajouter un biais égal à X. Ainsi, la valeur -X sera encodée par zéro, et toutes les autres valeurs le seront par un entier positif. Par exemple, prenons des nombres compris entre -127 et 128. On va devoir ajouter un biais égal à 127, ce qui donne :

Valeur avant encodage Valeur après encodage
-127 0
-126 1
-125 2
0 127
127 254
128 255

Les représentations en complément à un et en complément à deux[modifier | modifier le wikicode]

Les représentations en complément à un et en complément à deux sont deux représentations basées sur le même principe. Leur idée est de remplacer chaque nombre négatif par un nombre positif équivalent, appelé le complément. Par équivalent, on veut dire que les résultats de tout calcul reste le même si on remplace le nombre négatif initial par son complément. Et pour faire cela, elles se basent sur les débordements d'entier pour fonctionner, et plus précisément sur l'arithmétique modulaire abordée plus haut. Si on fait les calculs avec le complément, les résultats du calcul vont entraîner un débordement d'entier, qui sera résolu par un modulo. Et le résultat après modulo sera identique au résultat qu'on aurait obtenu avec le nombre négatif sans modulo. En clair, c'est la gestion des débordements qui permet de corriger le résultat de manière à ce que l'opération avec le complément donne le même résultat qu'avec le nombre négatif voulu. Ainsi, on peut coder un nombre négatif en utilisant son complément positif.

La différence entre complément à un et à deux tient dans la valeur haute de débordement. Pour des nombres codés sur bits, la valeur haute de débordement est égale à en complément à deux, alors qu'elle est de en complément à un. De ce fait, la gestion des débordements est plus simple en complément à deux. Concrètement, lors d'un débordement d'entier, l'ordinateur ne conserve que les bits de poids faible du résultat : les autres bits sont oubliés. Par exemple, reprenons l'addition 13 + 3 vue précédemment. En binaire, cela donne : 1101 + 0011 = 1 0000. En ne gardant que les 4 bits de poids faible, on obtient : 1101 + 0011 = 0000. Comme autre exemple l'addition 1111 + 0010 ne donnera pas 17 (10001), mais 1 (0001).

Le calcul du complément[modifier | modifier le wikicode]

Voyons maintenant comment convertir un nombre décimal en représentation en complément. Précisons que la procédure de conversion est différente suivant que le nombre est positif ou négatif. Pour les nombres positifs, il suffit de les traduire en binaire, sans faire quoi que ce soit de plus. C'est pour les nombres négatifs que la procédure est différente et qu'il faut calculer le complément. La méthode pour déterminer le complément est assez simple. Prenons par exemple un codage sur 4 bits dont la valeur haute de débordement est de 16. Prenons l'addition de 13 + 3 = 16. Avec l'arithmétique modulaire, 16 est équivalent à 0, ce qui donne : 13 + 3 = 0 ! On peut aussi reformuler en disant que 13 = -3, ou encore que 3 = -13. Dit autrement, 3 est le complément de -13 pour ce codage. Et ne croyez pas que ça marche uniquement dans cet exemple : cela se généralise assez rapidement à tout nombre négatif.

Prenons un nombre négatif N et son complément à deux K. Dans ce qui suit, les additions modulo n seront notées comme suit : . La notation se généralise aux autres opérations. Dans le cas général, on a :

Si on fait le calcul sur l'ordinateur, on obtient :

On peut donc calculer le complément d'un nombre comme suit :

Ce qui donne, respectivement en complément à deux et à un :

On se retrouve alors avec des soustractions à faire, mais nous ne sommes pas encore armés pour. On pourrait étudier en détail la soustraction en binaire dans ce chapitre, mais il vaut mieux laisser cela à un chapitre ultérieur. Pour passer outre ce problème, nous allons voir que l'on peut simplifier le calcul dans le cas du complément à un. Puis, nous déduirons le cas du complément à deux à partir de celui du complément à un. Pour le moment, l'on a juste besoin de savoir que la soustraction en binaire se fait comme en décimal, à savoir colonne par colonne et avec une propagation de retenue. La seule différence est que la table de soustraction est différente (en clair, il faut juste savoir soustraire deux bits).

Pour le complément à un, la valeur est par définition un nombre dont tous les bits sont à 1. À cette valeur, on soustrait un nombre dont certains bits sont à 1 et d'autres à 0. En clair, pour chaque colonne, on a deux possibilités : soit on doit faire la soustraction , soit la soustraction Or, les règles de l'arithmétique binaire disent que et . En regardant attentivement, on se rend compte que le bit du résultat est l'inverse du bit de départ. De plus, les deux cas ne donnent pas de retenue : le calcul pour chaque bit n'influence pas les bits voisins. En clair, le complément à un s'obtient en codant la valeur absolue en binaire, puis en inversant tous les bits du résultat (les 0 se transforment en 1 et réciproquement). On a donc :

Pour le complément à deux, on peut utiliser le même raisonnement. Pour cela, reprenons l'équation précédente :

Elle peut se réécrire comme suit :

Or, : n'est autre que le complément à un, ce qui donne :

Pour résumer, on a :

En clair, le complément à deux s'obtient en prenant le complément à un et en ajoutant 1. Dit autrement, il faut prendre le nombre N, en inverser tous les bits et ajouter 1.

Une autre manière équivalente consiste à faire le calcul suivant :

On prend le nombre dont on veut le complément, on soustrait 1 et on inverse les bits.

Comparaison entre complément à un et à deux[modifier | modifier le wikicode]

Avec le complément à un, le zéro est codé deux fois, avec un zéro positif et un zéro négatif. Les calculs sont cependant légèrement plus simples qu'en complément à deux, notamment quand il faut calculer le complément. Remarquez qu'en complément à un, la valeur haute de débordement est le zéro négatif. Traduire en décimal un nombre en complément à un est assez facile : il suffit de le traduire comme on le ferait avec du binaire non-signé, mais en ne tenant pas compte du bit de poids fort. Le signe du résultat est indiqué par le bit de poids fort : 1 pour un nombre négatif et 0 pour un nombre positif.

Codage sur 4 bits en complément à 1.

Avec le complément à deux, le zéro n'est codé que par un seul nombre binaire. Le zéro négatif est remplacé par une valeur négative, par la plus petite valeur négative pour être précis. C'est un avantage suffisant pour que tous les ordinateurs utilisent cette représentation. Pour savoir quelle est la valeur décimale d'un entier en complément à deux, on utilise la même procédure que pour traduire un nombre du binaire vers le décimal, à un détail près : le bit de poids fort (celui le plus à gauche) doit être multiplié par la puissance de deux associée, mais le résultat doit être soustrait au lieu d'être additionné.

Codage sur 4 bits en complément à 2.
Avec les deux représentations, le bit de poids fort vaut 0 pour les nombres positifs et 1 pour les négatifs : il agit comme un bit de signe.

L'extension de signe[modifier | modifier le wikicode]

Dans nos ordinateurs, tous les nombres sont codés sur un nombre fixé et constant de bits. Ainsi, les circuits d'un ordinateur ne peuvent manipuler que des nombres de 4, 8, 12, 16, 32, 48, 64 bits, suivant la machine. Si l'on veut utiliser un entier codé sur 16 bits et que l'ordinateur ne peut manipuler que des nombres de 32 bits, il faut bien trouver un moyen de convertir notre nombre de 16 bits en un nombre de 32 bits, sans changer sa valeur et en conservant son signe. Cette conversion d'un entier en un entier plus grand, qui conserve valeur et signe s'appelle l'extension de signe. L'extension de signe des nombres positifs consiste à remplir les bits de poids fort avec des 0 jusqu’à arriver à la taille voulue : c'est la même chose qu'en décimal, où rajouter des zéros à gauche d'un nombre positif ne changera pas sa valeur. Pour les nombres négatifs, il faut remplir les bits à gauche du nombre à convertir avec des 1, jusqu'à obtenir le bon nombre de bits : par exemple, 1000 0000 (-128 codé sur 8 bits) donnera 1111 1111 1000 000 après extension de signe sur 16 bits. L'extension de signe d'un nombre codé en complément à 2 se résume donc en une phrase : il faut recopier le bit de poids fort de notre nombre à convertir à gauche de celui-ci jusqu’à atteindre le nombre de bits voulu.

La représentation négabinaire[modifier | modifier le wikicode]

Enfin, il existe une dernière méthode, assez simple à comprendre, appelée représentation négabinaire. Dans cette méthode, les nombres sont codés non en base 2, mais en base -2. Oui, vous avez bien lu : la base est un nombre négatif. Dans les faits, la base -2 est similaire à la base 2 : il y a toujours deux chiffres (0 et 1), et la position dans un chiffre indique toujours par quelle puissance de 2 il faut multiplier, sauf qu'il faudra ajouter un signe moins une fois sur 2. Concrètement, les puissances de -2 sont les suivantes : 1, -2, 4, -8, 16, -32, 64, etc. En effet, un nombre négatif multiplié par un nombre négatif donne un nombre positif, ce qui fait qu'une puissance sur deux est négative, alors que les autres sont positives. Ainsi, on peut représenter des nombres négatifs, mais aussi des nombres positifs dans une puissance négative.

Par exemple, la valeur du nombre noté 11011 en base -2 s'obtient comme suit :

-32 16 -8 4 -2 1
1 1 1 0 1 1

Sa valeur est ainsi de (−32×1)+(16×1)+(−8×1)+(4×0)+(−2×1)+(1×1)=−32+16−8−2+1=−25.

Les nombres à virgule[modifier | modifier le wikicode]

On sait donc comment sont stockés nos nombres entiers dans un ordinateur. Néanmoins, les nombres entiers ne sont pas les seuls nombres que l'on utilise au quotidien : il nous arrive d'en utiliser à virgule. Notre ordinateur n'est pas en reste : il est lui aussi capable de manipuler de tels nombres. Dans les grandes lignes, il peut utiliser deux méthodes pour coder des nombres à virgule en binaire : La virgule fixe et la virgule flottante.

Les nombres à virgule fixe[modifier | modifier le wikicode]

La méthode de la virgule fixe consiste à émuler les nombres à virgule à partir de nombres entiers. Un nombre à virgule fixe est codé par un nombre entier proportionnel au nombre à virgule fixe. Pour obtenir la valeur de notre nombre à virgule fixe, il suffit de diviser l'entier servant à le représenter par le facteur de proportionnalité. Par exemple, pour coder 1,23 en virgule fixe, on peut choisir comme « facteur de conversion » 1000, ce qui donne l'entier 1230.

Généralement, les informaticiens utilisent une puissance de deux comme facteur de conversion, pour simplifier les calculs. En faisant cela, on peut écrire les nombres en binaire et les traduire en décimal facilement. Pour l'exemple, cela permet d'écrire des nombres à virgule en binaire comme ceci : 1011101,1011001. Et ces nombres peuvent se traduire en décimal avec la même méthode que des nombres entier, modulo une petite différence. Comme pour les chiffres situés à gauche de la virgule, chaque bit situé à droite de la virgule doit être multiplié par la puissance de deux adéquate. La différence, c'est que les chiffres situés à droite de la virgule sont multipliés par une puissance négative de deux, c'est à dire par , , , , , ...

Cette méthode est assez peu utilisée de nos jours, quoiqu'elle puisse avoir quelques rares applications relativement connue. Un bon exemple est celui des banques : les sommes d'argent déposées sur les comptes ou transférées sont codés en virgule fixe. Les sommes manipulées par les ordinateurs ne sont pas exprimées en euros, mais en centimes d'euros. Et c'est une forme de codage en virgule fixe dont le facteur de conversion est égal à 100. La raison de ce choix est que les autres méthodes de codage des nombres à virgule peuvent donner des résultats imprécis : il se peut que les résultats doivent être tronqués ou arrondis, suivant les opérandes. Cela n'arrive jamais en virgule fixe, du moins quand on se limite aux additions et soustractions.

Les nombres flottants[modifier | modifier le wikicode]

Les nombres à virgule fixe ont aujourd'hui été remplacés par les nombres à virgule flottante, où le nombre de chiffres après la virgule est variable. Le codage d'un nombre flottant est basée sur son écriture scientifique. Pour rappel, en décimal, l’écriture scientifique d'un nombre consiste à écrire celui-ci comme un produit entre un nombre et une puissance de 10. Ce qui donne :

, avec

Le nombre est appelé le significande et il est compris entre 1 (inclus) et 10 (exclu). Cette contrainte garantit que l'écriture scientifique d'un nombre est unique, qu'il n'y a qu'une seule façon d'écrire un nombre en notation scientifique. Pour cela, on impose le nombre de chiffre à gauche de la virgule et le plus simple est que celui-ci soit égal à 1. Mais il faut aussi que celui-ci ne soit pas nul. En effet, si on autorise de mettre un 0 à gauche de la virgule, il y a plusieurs manières équivalentes d'écrire un nombre. Ces deux contraintes font que le significande doit être égal ou plus grand que 1, mais strictement inférieur à 10. Par contre, on peut mettre autant de décimales que l'on veut.

En binaire, c'est la même chose, mais avec une puissance de deux. Cela implique de modifier la puissance utilisée : au lieu d'utiliser une puissance de 10, on utilise une puissance de 2.

, avec

Le significande est aussi altéré, au même titre que la puissance, même si les contraintes sont similaires à celles en base 10. En effet, le nombre ne possède toujours qu'un seul chiffre à gauche de la virgule, comme en base 10. Vu que seuls deux chiffres sont possibles (0 et 1) en binaire, on s'attend à ce que le chiffre situé à gauche de la virgule soit un zéro ou un 1. Mai rappelons que le chiffre à gauche doit être non-nul, pour les mêmes raisons qu'en décimal. En clair, le significande a forcément un bit à 1 à gauche de la virgule. Pour récapituler, l'écriture scientifique binaire d'un nombre consiste à écrire celui-ci sous la forme :

, avec

La partie fractionnaire du nombre , qu'on appelle la mantisse.

Écriture scientifique (anglais).

Traduire un nombre en écriture scientifique binaire[modifier | modifier le wikicode]

Pour déterminer l'écriture scientifique en binaire d'un nombre quelconque, la procédure dépend de la valeur du nombre en question. Tout dépend s'il est dans l'intervalle , au-delà de 2 ou en-dessous de 1.

  • Pour un nombre entre 1 (inclus) et 2 (exclu), il suffit de le traduire en binaire. Son exposant est 0.
  • Pour un nombre au-delà de 2, il faut le diviser par 2 autant de fois qu'il faut pour qu'il rentre dans l’intervalle . L'exposant est alors le nombre de fois qu'il a fallu diviser par 2.
  • Pour un nombre plus petit que 1, il faut le multiplier par 2 autant de fois qu'il faut pour qu'il rentre dans l’intervalle . L'exposant se calcule en prenant le nombre de fois qu'il a fallu multiplier par 2, et en prenant l'opposé (en mettant un signe - devant le résultat).

Le codage des nombres flottants et la norme IEEE 754[modifier | modifier le wikicode]

Pour coder cette écriture scientifique avec des nombres, l'idée la plus simple est d'utiliser trois nombres, pour coder respectivement la mantisse, l'exposant et un bit de signe. Coder la mantisse implique que le bit à gauche de la virgule vaut toujours 1, mais nous verrons qu'il y a quelques rares exceptions à cette règle. Quelques nombres flottants spécialisés, les dénormaux, ne sont pas codés en respectant les règles pour le significande et ont un 0 à gauche de la virgule. Un bon exemple est tout simplement la valeur zéro, que l'on peut coder en virgule flottante, mais seulement en passant outre les règles sur le significande. Toujours est-il que le bit à gauche de la virgule n'est pas codé, que ce soit pour les flottants normaux ou les fameux dénormaux qui font exception. On verra que ce bit peut se déduire en fonction de l'exposant utilisé pour encoder le nombre à virgule, ce qui lui vaut le nom de bit implicite. L'exposant peut être aussi bien positif que négatif (pour permettre de coder des nombres très petits), et est encodé en représentation par excès sur n bits avec un biais égal à .

IEEE754 Format Général

Le standard pour le codage des nombres à virgule flottante est la norme IEEE 754. Cette norme va (entre autres) définir quatre types de flottants différents, qui pourront stocker plus ou moins de valeurs différentes.

Classe de nombre flottant Nombre de bits utilisés pour coder un flottant Nombre de bits de l'exposant Nombre de bits pour la mantisse Décalage
Simple précision 32 8 23 127
Double précision 64 11 52 1023
Double précision étendue 80 ou plus 15 ou plus 64 ou plus 16383 ou plus

IEEE754 impose aussi le support de certains nombres flottants spéciaux qui servent notamment à stocker des valeurs comme l'infini. Commençons notre revue des flottants spéciaux par les dénormaux, aussi appelés flottants dénormalisés. Ces flottants ont une particularité : leur bit implicite vaut 0. Ces dénormaux sont des nombres flottants où l'exposant est le plus petit possible. Le zéro est un dénormal particulier dont la mantisse est nulle. Au fait, remarquez que le zéro est codé deux fois à cause du bit de signe : on se retrouve avec un -0 et un +0.

Bit de signe Exposant Mantisse
0 ou 1 Valeur minimale (0 en binaire) Mantisse différente de zéro (dénormal strict) ou égale à zéro (zéro)

Fait étrange, la norme IEEE754 permet de représenter l'infini, aussi bien en positif qu'en négatif. Celui-ci est codé en mettant l'exposant à sa valeur maximale et la mantisse à zéro. Et le pire, c'est qu'on peut effectuer des calculs sur ces flottants infinis. Mais cela a peu d'utilité.

Bit de signe Exposant Mantisse
0 ou 1 Valeur maximale Mantisse égale à zéro

Mais malheureusement, l'invention des flottants infinis n'a pas réglé tous les problèmes. Par exemple, quel est le résultat de  ? Ou encore  ? Autant prévenir tout de suite : mathématiquement, on ne peut pas savoir quel est le résultat de ces opérations. Pour pouvoir résoudre ces calculs, il a fallu inventer un nombre flottant qui signifie « je ne sais pas quel est le résultat de ton calcul pourri ». Ce nombre, c'est NaN. NaN est l'abréviation de Not A Number, ce qui signifie : n'est pas un nombre. Ce NaN a un exposant dont la valeur est maximale, mais une mantisse différente de zéro. Pour être plus précis, il existe différents types de NaN, qui diffèrent par la valeur de leur mantisse, ainsi que par les effets qu'ils peuvent avoir. Malgré son nom explicite, on peut faire des opérations avec NaN, mais cela ne sert pas vraiment à grand chose : une opération arithmétique appliquée avec un NaN aura un résultat toujours égal à NaN.

Bit de signe Exposant Mantisse
0 ou 1 Valeur maximale Mantisse différente de zéro

Les arrondis et exceptions[modifier | modifier le wikicode]

La norme impose aussi une gestion des arrondis ou erreurs, qui arrivent lors de calculs particuliers. En voici la liste :

Nom de l’exception Description
Invalid operation Opération qui produit un NAN. Elle est levée dans le cas de calculs ayant un résultat qui est un nombre complexe, ou quand le calcul est une forme indéterminée. Pour ceux qui ne savent pas ce que sont les formes indéterminées, voici en exclusivité la liste des calculs qui retournent NaN : , , , , .
Overflow Résultat trop grand pour être stocké dans un flottant. Le plus souvent, on traite l'erreur en arrondissant le résultat vers Image non disponible ;
Underflow Pareil que le précédent, mais avec un résultat trop petit. Le plus souvent, on traite l'erreur en arrondissant le résultat vers 0.
Division par zéro Le nom parle de lui-même. La réponse la plus courante est de répondre + ou - l'infini.
Inexact Le résultat ne peut être représenté par un flottant et on doit l'arrondir.

La gestion des arrondis pose souvent problème. Pour donner un exemple, on va prendre le nombre 0,1. En binaire, ce nombre s'écrit comme ceci : 0,1100110011001100... et ainsi de suite jusqu'à l'infini. Notre nombre utilise une infinité de décimales. Bien évidemment, on ne peut pas utiliser une infinité de bits pour stocker notre nombre et on doit impérativement l'arrondir. Comme vous le voyez avec la dernière exception, le codage des nombres flottants peut parfois poser problème : dans un ordinateur, il se peut qu'une opération sur deux nombres flottants donne un résultat qui ne peut être codé par un flottant. On est alors obligé d'arrondir ou de tronquer le résultat de façon à le faire rentrer dans un flottant. Pour éviter que des ordinateurs différents utilisent des méthodes d'arrondis différentes, on a décidé de normaliser les calculs sur les nombres flottants et les méthodes d'arrondis. Pour cela, la norme impose le support de quatre modes d'arrondis :

  • Arrondir vers + l'infini ;
  • vers - l'infini ;
  • vers zéro ;
  • vers le nombre flottant le plus proche.

Les nombres flottants logarithmiques[modifier | modifier le wikicode]

Les nombres flottants logarithmiques sont une spécialisation des nombres flottants IEEE754, ou tout du moins une spécialisation des flottants écrits en écriture scientifique. Avec ces nombres logarithmiques, la mantisse est totalement implicite : tous les flottants logarithmiques ont la même mantisse, qui vaut 1. Seul reste l'exposant, qui varie suivant le nombre flottant. On peut noter que cet exposant est tout simplement le logarithme en base 2 du nombre encodé, d'où le nombre de codage flottant logarithmique donné à cette méthode. Un nombre logarithmique est donc composé d'un bit de signe et d'un exposant, sans mantisse. Attention toutefois : l'exposant est ici un nombre fractionnaire, ce qui signifie qu'il est codé en virgule fixe. Le choix d'un exposant fractionnaire permet de représenter pas mal de nombres de taille diverses.

Bit de signe Exposant
Représentation binaire 0 01110010101111
Représentation décimale + 1040,13245464

L'utilité de cette représentation est de simplifier certains calculs, comme les multiplications, divisions, puissances, etc. En effet, les mathématiques de base nous disent que le logarithme d'un produit est égal à la somme des logarithmes : . Or, il se trouve que les ordinateurs sont plus rapides pour faire des additions/soustractions que pour faire des multiplications/divisions. On verra dans quelques chapitres que les circuits électroniques d'addition/soustraction sont beaucoup plus simples que les circuits pour multiplier et/ou diviser. Dans ces conditions, la représentation logarithmique permet de remplacer les multiplications/divisions par des opérations additives plus simples et plus rapides pour l'ordinateur. Évidemment, les applications des flottants logarithmiques sont rares, limitées à quelques situations bien précises (traitement d'image, calcul scientifique spécifiques).


Les circuits électroniques[modifier | modifier le wikicode]

Grâce au chapitre précédent, on sait enfin comment sont représentées nos données les plus simples avec des bits. On n'est pas encore allés bien loin : on ne sait pas comment représenter des bits dans notre ordinateur ou les modifier, les manipuler, ni faire quoi que ce soit avec. On sait juste transformer nos données en paquets de bits (et encore, on ne sait vraiment le faire que pour des nombres entiers, des nombres à virgule et du texte...). C'est pas mal, mais il reste du chemin à parcourir ! Rassurez-vous, ce chapitre est là pour corriger ce petit défaut. On va vous expliquer quels traitements élémentaires notre ordinateur va effectuer sur nos bits.

Les portes logiques de base[modifier | modifier le wikicode]

Les portes logiques sont des circuits qui possèdent des sorties et des entrées sur lesquelles on va placer ou récupérer des bits. Les entrées ne sont rien d'autre que des morceaux de « fil » conducteur sur lesquels on envoie un bit (une tension). À partir de là, le circuit électronique va réagir et déduire le bit à placer sur chaque sortie. Tous les composants d'un ordinateur sont fabriqués avec ce genre de circuits.

Sur les schémas qui vont suivre, les entrées des portes logiques seront à gauche et les sorties à droite !

Les portes logiques ont différent symboles selon le pays et l'organisme de normalisation :

  • Commission électrotechnique internationale (CEI) ou International Electrotechnical Commission (IEC),
  • Deutsches Institut für Normung (DIN, Institut allemand de normalisation),
  • American National Standards Institute (ANSI).

La porte NON[modifier | modifier le wikicode]

La première porte fondamentale est la porte NON, qui agit sur un seul bit : la sortie d'une porte NON est exactement le contraire de l'entrée.

Pour simplifier la compréhension, je vais rassembler les états de sortie en fonction des entrées pour chaque porte logique dans un tableau que l'on appelle table de vérité.

Entrée Sortie
0 1
1 0
Symboles d'une porte NON (NOT).
CEI DIN ANSI
NOT IEC Labelled.svg NOT DIN.svg NOT ANSI Labelled.svg

La porte ET[modifier | modifier le wikicode]

La porte ET possède plusieurs entrées, mais une seule sortie. Cette porte logique met sa sortie à 1 quand toutes ses entrées valent 1. Dans le cas le plus simple, une porte ET possède deux entrées.

Entrée 1 Entrée 2 Sortie
0 0 0
0 1 0
1 0 0
1 1 1
Symboles d'une porte ET (AND).
CEI DIN ANSI
AND IEC Labelled.svg AND DIN.svg AND ANSI Labelled.svg


Certaines portes ET ont plus de deux entrées, et peuvent en avoir 3, 4, 5, 6, 7, etc. Là encore, leur sortie ne vaut 1 que si toutes les entrées valent 1 : dans le cas contraire, la sortie de la porte ET vaut 0. Dit autrement, si une seule entrée vaut 0, la sortie de la porte ET vaut 0.

La porte NAND[modifier | modifier le wikicode]

La porte NAND donne l'exact inverse de la sortie d'une porte ET. En clair, sa sortie ne vaut 1 que si au moins une entrée est nulle. Dans le cas contraire, si toutes les entrées sont à 1, la sortie vaut 0. Dans le cas le plus simple, une porte NAND a deux entrées. Certaines portes NAND ont plus de deux entrées : elles peuvent en avoir 3, 4, 5, 6, 7, etc. Là encore, leur sortie ne vaut 1 que si au moins une entrée est nulle : dans le cas contraire, la sortie de la porte NAND vaut 0. Dit autrement, si toutes les entrées sont à 1, la sortie vaut 0.

Entrée 1 Entrée 2 Sortie
0 0 1
0 1 1
1 0 1
1 1 0
Symboles d'une porte NON-ET (NAND).
CEI DIN ANSI
NAND IEC Labelled.svg NAND DIN.svg NAND ANSI Labelled.svg

Au fait, si vous regardez le schéma de la porte NAND, vous verrez que son symbole est presque identique à celui d'une porte ET : seul un petit rond (blanc pour ANSI, noir pour DIN) ou une barre (CEI) sur la sortie de la porte a été rajouté. Il s'agit d'une sorte de raccourci pour schématiser une porte NON.

La porte OU[modifier | modifier le wikicode]

La porte OU est une porte dont la sortie vaut 1 si et seulement si au moins une entrée vaut 1. Dit autrement, sa sortie est à 0 si toutes les entrées sont à 0. Dans le cas le plus simple, la porte OU possède deux entrées, ainsi qu'une seule sortie. Elle met sa sortie à 1 quand au moins une de ses entrées vaut 1. Certaines portes OU ont plus de deux entrées. Là encore, leur sortie est à 0 si et seulement si toutes les entrées sont à 0 : si une seule entrée est à 1, alors la sortie vaut 1.

Entrée 1 Entrée 2 Sortie
0 0 0
0 1 1
1 0 1
1 1 1
Symboles d'une porte OU (OR).
CEI DIN ANSI
OR IEC Labelled.svg OR DIN.svg OR ANSI Labelled.svg

La porte NOR[modifier | modifier le wikicode]

La porte NOR donne l'exact inverse de la sortie d'une porte OU. Là encore, il en existe une version avec deux entrées, et des versions avec plus de deux entrées. Les tableaux et symboles qui suivent sont ceux d'une porte NOR à deux entrées.

Entrée 1 Entrée 2 Sortie
0 0 1
0 1 0
1 0 0
1 1 0
Symboles d'une porte NON-OU (NOR).
CEI DIN ANSI
NOR IEC Labelled.svg NOR DIN.svg NOR ANSI Labelled.svg

La porte XOR[modifier | modifier le wikicode]

Avec une porte OU, deux ET et deux portes NON, on peut créer une porte nommée XOR. Cette porte est souvent appelée porte OU exclusif. Sa sortie est à 1 quand les deux bits placés sur ses entrées sont différents, et vaut 0 sinon.

Entrée 1 Entrée 2 Sortie
0 0 0
0 1 1
1 0 1
1 1 0
Symboles d'une porte OU-exclusif (XOR).
CEI DIN ANSI
XOR IEC Labelled.svg XOR DIN.svg XOR ANSI Labelled.svg

La porte XNOR[modifier | modifier le wikicode]

La porte XOR possède une petite sœur : la XNOR. Sa sortie est à 1 quand les deux entrées sont identiques, et vaut 0 sinon (elle est équivalente à une porte XOR suivie d'une porte NON).

Entrée 1 Entrée 2 Sortie
0 0 1
0 1 0
1 0 0
1 1 1
Symboles d'une porte NON-OU-exclusif (XNOR).
CEI DIN ANSI
XNOR IEC Labelled.svg XNOR DIN.svg XNOR ANSI Labelled.svg

Fabriquer des portes logiques complexes à partir de portes basiques[modifier | modifier le wikicode]

Pour information, il est possible de recréer toutes les portes logiques existantes à partir de seulement quelques portes de base. Par exemple, il est possible de construire toute porte logique, et donc tout circuit numérique, à partir de portes NON, ET et OU. Ces trois portes de base suffisent à créer toutes les autres. La même chose est possible avec uniquement des portes NAND ou seulement des portes NOR. Dans cette section, nous allons voir comment cela est possible.

L'idée est tout simplement qu'on peut obtenir une porte logique en combinant deux autres, parfois plus. La porte ainsi obtenue par combinaison est donc une porte "superflue", elle n'est pas une porte de base. Cela n'a rien d'étonnant et on peut déjà se rendre compte que certaines portes sont l'inverse l'une de l'autre. Par exemple, la porte ET et la porte NAND sont l'inverse l'une de l'autre : il suffit d'en combiner une avec une porte NON pour obtenir l'autre. Même chose pour les portes OU et NOR, ainsi que les portes XOR et NXOR.

Porte ET AND from NAND and NOT
Porte OU OR from NOR and NOT

Une idée serait de retirer les portes NOR, NAND et NXOR, qui peuvent se calculer en combinant une porte NON avec un porte ET ou OU. Mais la question est : faut-il garder les portes ET/OU/XOR ou les portes NOR/NAND/NXOR ? L'un de ces choix est plus pertinent que l'autre, mais nous ne savons pas lequel pour le moment. Intuitivement, on se doute que l'on devrait retirer les portes NOR, NAND et NXOR, mais n'allons pas trop vite en besogne, nous ne sommes pas à l'abri d'une surprise. Dans ce qui suit, nous allons garder les portes NAND, NOR et NXOR.

L'élimination des portes XOR et NXOR[modifier | modifier le wikicode]

Pour commencer, nous allons montrer que les portes XOR/NXOR peuvent se fabriquer à partir de portes NON, ET/NAND et OU/NOR.

Pour la porte XOR, il y a plusieurs possibilités, plusieurs combinaisons de portes logiques faisant l'affaire. La plus simple s'obtient à partir des techniques que l'on verra au chapitre suivant, mais on peut aussi la déduire d'un raisonnement assez simple. Pour cela, partons du tableau vu plus haut :

Entrée 1 Entrée 2 Sortie
0 0 0
0 1 1
1 0 1
1 1 0

On voit que la sortie est à 1 dans deux situations : soit l'entrée n°1 est à 1 et l'entrée 2 à 0, soit c'est l'inverse. L'idée est de créer un circuit qui vérifie si on est dans la première situation, un circuit pour l'autre situation, et de quoi combiner la sortie de ces deux circuits. Les deux circuits de vérification ont une sortie à 1 si les entrées sont adéquates et 0 sinon. Le circuit qui vérifie la première situation est composé d'une porte NON sur l'entrée 2 et d'une porte ET. Le circuit pour la seconde situation est le même, sauf que la porte NON est placée sur l'entrée 2. La sortie des deux circuits est combinée avec une porte OU, car une seule des deux situations rencontrées met la sortie à 1. Le circuit obtenu est le suivant :

Porte XOR fabriquée à partir de portes ET/OU/NON.

Une autre possibilité est la suivante. L'idée est que la sortie d'une porte XOR est à 1 quand au moins une des entrées est à 1, et qu'au moins une des entrées est à zéro. Pour vérifier qu'une des entrées est à 1, il suffit d'une porte OU : par définition sa sortie sera à un si l'une des entrées est à 1. Pour vérifier que au moins l'une des entrées est à zéro, il suffit d'utiliser une porte NAND, qui sort un 1 quand l'une des entrées est à zéro, par définition. Et cette fois, on combine le résultat des deux vérifications avec une porte ET.

Porte XOR fabriquée à partir de portes ET/OU/NON, alternative.

Il est possible de créer une porte NXOR en plaçant une porte NON en sortie d'une porte XOR, mais il est aussi possible de faire plus simple. Par exemple, on peut procéder de la manière suivante. Le circuit suivant est simplement basé sur le fait que la porte NXOR sort un 1 soit quand ses deux entrées sont à 1, soit quand elles sont toutes deux à 0. La porte ET a sa sortie à 1 dans le premier cas, quand les deux entrées sont à 1, alors que la porte NOR (une OU suivie d'un ET) a sa sortie à 1 quand les deux entrées sont à 0. La porte finale combine le résultat de la porte NOR avec celui de la porte ET pour obtenir un résultat valide. Vu que la sortie doit être à 1 dans l'un des deux cas, c'est à dire quand l'une des deux portes ET/NOR est à 1, la porte finale est naturellement une porte OU.

Porte NXOR fabriquée à partir de portes ET/OU/NON, alternative.

L'élimination des portes ET et OU[modifier | modifier le wikicode]

Vu que les portes XOR et NXOR sont superflues, il nous reste les portes NON, ET, OU, NOR et NAND. Dans cette section, nous allons montrer que le ET et le OU peuvent se fabriquer avec d'autres portes, mais sans passer par la solution évidente qui consiste à inverser la sortie d'une NAND ou d'une NOR.

L'élimination de la porte OU[modifier | modifier le wikicode]

Pour montrer que seules les portes NON et ET suffisent, il suffit de créer une porte OU avec seulement des portes NON et ET.

Premièrement, il est possible de créer une porte NOR avec des NON et des ET. Ce qui réalisée avec le circuit ci-dessous.

Porte NOR fabriquée avec des portes NON et ET.

On peut créer une porte OU en ajoutant une porte NON au bout du circuit précédent, pour inverser son résultat.

Porte OU fabriquée avec des portes NON et ET.

L'élimination de la porte ET[modifier | modifier le wikicode]

Pour montrer que seules les portes NON et OU suffisent, il suffit de créer une porte ET avec seulement des portes NON et OU.

Premièrement, il est possible de créer une porte NAND avec des NON et des OU, ou encore avec des NON et des NAND. Ce qui réalisée avec le circuit ci-dessous.

Porte NAND fabriquée avec des portes NON et OU.

On peut aussi créer une porte ET en ajoutant une porte NON au bout du circuit précédent pour inverser son résultat.

Porte ET fabriquée avec des portes NON et OU.

L'élimination de la porte NON[modifier | modifier le wikicode]

Dans la section précédente, nous avons vu qu'il existe deux possibilités : soit on supprime les portes ET/NAND et on garde les portes OU/NOR, soit on fait l'inverse. Les deux possibilités sont équivalentes et permettent chacune de fabriquer toutes les portes logiques restantes. Les deux solutions laissent respectivement les portes logiques suivantes : NON, OU et NOR pour la première solution, NON, ET et NAND pour la seconde. Vu que le NAND est l'inverse du ET et que le NOR est l'inverse du OU, on peut simplifier et ne garder que deux portes logiques. Cela donne alors quatre possibilités : NON et ET, NON et NAND, NON et OU, NON et NOR.

Cependant, il est possible d'éliminer le NON, en utilisant une porte NAND ou une porte NOR. Ce qui permet de fabriquer tout circuit avec seulement un type de porte logique : soit on construit le circuit avec uniquement des NAND, soit avec uniquement des NOR. L'intérêt de n'utiliser qu'un seul type de porte est que les circuits intégrés comportent plusieurs portes d'un même type ; utiliser un seul type de porte évite d'utiliser différents types de circuits intégrés et de gaspiller des portes non utilisées. Pour donner un exemple, sachez que les ordinateurs chargés du pilotage et de la navigation des missions Appollo étaient intégralement conçus avec des portes NOR.

Il est possible de fabriquer toutes les autres portes logiques à partir de portes NAND. Pour cela, il suffit d'envoyer le bit à inverser sur les deux entrées d'une porte NAND. Pour comprendre pourquoi cela marche, il faut imaginer que la porte NAND est composée d'une porte ET suivie par une porte NON. L'idée est que le bit envoyé va subir un ET avec lui-même, avant d'être inversé. Or, on a obligatoirement, pour tout bit a : . En clair, le passage dans le ET/OU ne changera pas le bit, mais la porte NON l'inversera. On peut faire la même chose avec des portes NOR, la porte NAND n'étant pas la seule à avoir ce privilège. Là encore, la porte NON est fabriquée en envoyant le bit à inverser sur les deux entrées d'une porte NOR, afin que le OU entre le bit et lui-même laisse celui-ci inchangé, mais le NON l'inverse.

Porte NON fabriquée avec des portes NAND/NOR
Circuit équivalent avec des NAND Circuit équivalent avec des NOR
Porte NON
NOT from NAND
NOT from NOR

Créer les autres portes logiques est alors un jeu d'enfant avec ce qu'on a appris dans les sections précédentes. Il suffit de remplacer les portes NON et ET par leurs équivalents fabriqués avec des NAND.

Portes logiques fabriquées avec des portes NAND/NOR
Circuit équivalent avec des NAND Circuit équivalent avec des NOR
Porte ET
AND from NAND
AND from NOR
Porte OU
OR from NAND
OR from NOR
Porte NOR
NOR from NAND
Porte NAND
NAND from NOR
Porte XOR
XOR from NAND
XOR from NOR
XOR from NAND
XOR from NOR
Porte NXOR
NXOR from NAND
NXOR from NOR
NXOR from NAND
NXOR from NOR


Dans le chapitre précédent, nous avons abordé les portes logiques. Dans ce chapitre, nous allons voir qu'elles sont fabriquées avec des composants électroniques que l'on appelle des transistors. Ces derniers sont reliés entre eux pour former des circuits plus ou moins compliqués. Pour donner un exemple, sachez que les derniers modèles de processeurs peuvent utiliser près d'un milliard de transistors.

Les transistors[modifier | modifier le wikicode]

Un transistor est un morceau de conducteur, dont la conductivité est contrôlée par sa troisième broche/borne.

Les transistors possèdent trois broches, des pattes métalliques sur lesquelles on connecte des fils électriques. On peut appliquer une tension électrique sur ces broches, qui peut représenter soit 0 soit 1. Sur ces trois broches, il y en a deux entre lesquelles circule un courant, et une troisième qui commande le courant. Le transistor s'utilise le plus souvent comme un interrupteur commandé par sa troisième broche. Le courant qui traverse les deux premières broches passe ou ne passe pas selon ce qu'on met sur la troisième.

Les types de transistors MOS : PMOS et NMOS[modifier | modifier le wikicode]

Les transistors utilisés dans les ordinateurs sont tous des transistors MOS. Chaque broche a un nom, nom qui est indiqué sur le schéma ci-dessous. On l'utilise le plus souvent comme un interrupteur commandé par sa grille. Appliquez la tension adéquate et la liaison entre la source et le drain se comportera comme un interrupteur fermé. Mettez la grille à une autre valeur et cette liaison se comportera comme un interrupteur ouvert.

Il existe deux types de transistors CMOS, qui diffèrent entre autre par le bit qu'il faut mettre sur la grille pour les ouvrir/fermer :

  • les transistors NMOS qui s'ouvrent lorsqu'on envoie un zéro sur la grille et se ferment si la grille est à un ;
  • et les PMOS qui se ferment lorsque la grille est à zéro, et s'ouvrent si la grille est à un.
Illustration du fonctionnement des transistors NMOS et PMOS.

Voici les symboles de chaque transistor.

Transistor CMOS
Transistor MOS à canal N (NMOS).
Transistor MOS à canal P (PMOS).

L'anatomie d'un transistor CMOS[modifier | modifier le wikicode]

À l'intérieur du transistor, on trouve simplement une plaque en métal reliée à la grille appelée l'armature, un bout de semi-conducteur entre la source et le drain, et un morceau d'isolant entre les deux. Pour rappel, un semi-conducteur est un matériau qui se comporte soit comme un isolant, soit comme un conducteur, selon les conditions auxquelles on le soumet. Dans un transistor, son rôle est de laisser passer le courant, ou de ne pas le transmettre, quand il faut. C'est grâce à ce semi-conducteur que le transistor peut fonctionner en interrupteur : interrupteur fermé quand le semi-conducteur conduit, ouvert quand il bloque le courant. La commande de la résistance du semi-conducteur (le fait qu'il laisse passer ou non le courant) est réalisée par la grille, comme nous allons le voir ci-dessous.

Transistor CMOS

Suivant la tension que l'on place sur la grille, celle-ci va se remplir avec des charges négatives ou positives. Cela va entrainer une modification de la répartition des charges dans le semi-conducteur, ce qui modulera la résistance du conducteur. Prenons par exemple le cas d'un transistor NMOS et étudions ce qui se passe selon la tension placée sur la grille. Si on met un zéro, la grille sera vide de charges et le semi-conducteur se comportera comme un isolant : le courant ne passera pas. En clair, le transistor sera équivalent à un interrupteur ouvert. Si on met un 1 sur la grille, celle-ci va se remplir de charges. Le semi-conducteur va réagir et se mettre à conduire le courant. En clair, le transistor se comporte comme un interrupteur fermé.

Transistor NMOS fermé.
Transistor NMOS ouvert.

La loi de Moore[modifier | modifier le wikicode]

Les composants électroniques contiennent un grand nombre de transistors. Par exemple, les derniers modèles de processeurs peuvent utiliser près d'un milliard de transistors. Cette orgie de transistors permet d'ajouter des fonctionnalités aux composants électroniques. C'est notamment ce qui permet aux processeurs récents d'intégrer plusieurs cœurs, une carte graphique, etc. En 1965, le cofondateur de la société Intel, spécialisée dans la conception de mémoires et de processeurs, a affirmé que la quantité de transistors présents dans un processeur doublait tous les 18 mois : c'est la première loi de Moore. En 1975, il réévalua cette affirmation : ce n'est pas tous les 18 mois que le nombre de transistors d'un processeur double, mais tous les 2 ans. Cette nouvelle version, appelée la seconde loi de Moore, est toujours valable de nos jours.

Nombre de transistors en fonction de l'année.

Cela n'aurait pas été possible sans le développement de la miniaturisation, qui permet de rendre les transistors plus petits. Il faut savoir que les circuits imprimés sont fabriqués à partir d'une plaque de silicium pur, un wafer, sur laquelle on vient graver le circuit imprimé. Les transistors sont donc répartis sur une surface plane. Ils ont souvent une largeur et une longueur qui sont très proches. Pour simplifier, la taille des transistors est aussi appelée la finesse de gravure. Celle-ci s'exprime le plus souvent en nanomètres.

La loi de Moore nous donne des indications sur l'évolution de la finesse de gravure dans le temps. Doubler le nombre de transistors signifie qu'on peut mettre deux fois plus de transistors sur une même surface : la surface occupée par un transistor a été divisée par deux. Ainsi, la finesse de gravure est divisée par la racine carrée de deux, environ 1,4, tous les deux ans. Une autre formulation consiste à dire que la finesse de gravure est multipliée par 0,7 tous les deux ans, soit une diminution de 30 % tous les deux ans.

Évolution de la finesse de gravure au cours du temps pour les mémoires FLASH de type NAND.

Néanmoins, la loi de Moore n'est pas vraiment une loi gravée dans le marbre. Si celle-ci a été respectée jusqu'à présent, c'est avant tout grâce aux efforts des fabricants de processeurs, qui ont tenté de la respecter pour des raisons commerciales. Vendre des processeurs toujours plus puissants, avec de plus en plus de transistors est en effet gage de progression technologique autant que de nouvelles ventes.

Il arrivera un moment où les transistors ne pourront plus être miniaturisés, et ce moment approche ! Quand on songe qu'en 2016 certains transistors ont une taille proche d'une vingtaine ou d'une trentaine d'atomes, on se doute que la loi de Moore n'en a plus pour très longtemps. Et la progression de la miniaturisation commence déjà à montrer des signes de faiblesses. Le 23 mars 2016, Intel a annoncé que pour ses prochains processeurs, le doublement du nombre de transistors n'aurait plus lieu tous les deux ans, mais tous les deux ans et demi. Cet acte de décès de la loi de Moore n'a semble-t-il pas fait grand bruit, et les conséquences ne se sont pas encore faites sentir dans l'industrie. Au niveau technique, on peut facilement prédire que la course au nombre de cœurs a ses jours comptés.

On estime que la limite en terme de finesse de gravure sera proche des 5 à 7 nanomètres : à cette échelle, le comportement des électrons suit les lois de la physique quantique et leur mouvement devient aléatoire, perturbant fortement le fonctionnement des transistors au point de les rendre inutilisables. Et cette limite est proche : des finesses de gravure de 10 nanomètres sont déjà disponibles chez certaines fondeurs comme TSMC. Autant dire que si la loi de Moore est respectée, la limite des 5 nanomètres sera atteinte dans quelques années, à peu-près vers l'année 2020. Ainsi, nous pourrons vivre la fin d'une ère technologique, et en voir les conséquences. Les conséquences économiques sur le secteur du matériel promettent d'être assez drastiques, que ce soit en terme de concurrence ou en terme de réduction de l'innovation.

Quant cette limite sera atteinte, l'industrie sera face à une impasse. Le nombre de cœurs ou la micro-architecture des processeurs ne pourra plus profiter d'une augmentation du nombre de transistors. Et les recherches en terme d'amélioration des micro-architectures de processeurs sont au point mort depuis quelques années. La majeure partie des optimisations matérielles récemment introduites dans les processeurs sont en effet connues depuis fort longtemps (par exemple, le premier processeur superscalaire à exécution dans le désordre date des années 1960), et ne sont améliorables qu'à la marge. Quelques équipes de recherche travaillent cependant sur des architectures capables de révolutionner l'informatique. Le calcul quantique ou les réseaux de neurones matériels sont une première piste, mais qui ne donneront certainement de résultats que dans des marchés de niche. Pas de quoi rendre un processeur de PC plus rapide.

Fabriquer des portes logiques avec des transistors[modifier | modifier le wikicode]

Les portes logiques que nous venons de voir sont actuellement fabriquées en utilisant des transistors. Il existe de nombreuses manières pour concevoir des circuits à base de transistors, qui portent les noms de DTL, RTL, TLL, CMOS et bien d'autre.

La technologie CMOS[modifier | modifier le wikicode]

Dans cette section, nous allons montrer comment fabriquer des portes logiques en utilisant la technologie CMOS. Avec celle-ci, chaque porte logique est fabriquée à la fois avec des transistors NMOS et des transistors PMOS. On peut la voir comme un mélange entre la technologie PMOS et NMOS. Tout circuit CMOS est divisé en deux parties : une intégralement composée de transistors PMOS et une autre de transistors NMOS. Chacune relie la sortie du circuit soit à la masse, soit à la tension d'alimentation.

Principe de conception d'une porte logique/d'un circuit en technologie CMOS.

La première partie relie la tension d'alimentation à la sortie, mais uniquement quand la sortie doit être à 1. Si la sortie doit être à 1, des transistors PMOS vont se fermer et connecter tension et sortie. Dans le cas contraire, des transistors s'ouvrent et cela déconnecte la liaison entre sortie et tension d'alimentation. L'autre partie du circuit fonctionne de la même manière que la partie de PMOS, sauf qu'elle relie la sortie à la masse et qu'elle se ferme quand la sortie doit être mise à 0

Fonctionnement d'un circuit en logique CMOS.

La porte NON[modifier | modifier le wikicode]

Cette porte est fabriquée avec seulement deux transistors, comme indiqué ci-dessous.

Porte NON fabriquée avec des transistors CMOS.

Si on met un 1 en entrée de ce circuit, le transistor du haut va fonctionner comme un interrupteur ouvert, et celui du bas comme un interrupteur fermé : la sortie est reliée au zéro volt, et vaut donc 0. Inversement, si on met un 0 en entrée de ce petit montage électronique, le transistor du bas va fonctionner comme un interrupteur ouvert, et celui du haut comme un interrupteur fermé : la sortie est reliée à la tension d'alimentation, et vaut donc 1.

Porte NON fabriquée avec des transistors CMOS - fonctionnement.

La porte NAND[modifier | modifier le wikicode]

Voici en exclusivité comment créer une porte NAND à deux entrées avec des transistors CMOS !

Porte NAND fabriquée avec des transistors.
Porte NAND fabriquée avec des transistors.

La porte NOR[modifier | modifier le wikicode]

Implémenter une porte NOR à deux entrées avec des transistors CMOS ressemble à ce qu'on a fait pour la porte NAND.

Porte NOR fabriquée avec des transistors.
Porte NOR fabriquée avec des transistors.

Portes ET et OU[modifier | modifier le wikicode]

Les autres portes sont construites à partir de ces portes. Par exemple, la porte ET est fabriquée en combinant deux portes logiques : une porte NAND et une porte NON. Voici le circuit d'une porte ET :

Porte ET : circuit à base de transistors CMOS.

Comme pour la porte ET, la porte OU est fabriquée à partie de deux portes plus simples : une porte NON et une porte NOR. Voici le circuit d'une porte OU sans vous l'expliquer.

Porte OU : circuit à base de transistors CMOS.

Portes XOR et NXOR[modifier | modifier le wikicode]

Il est possible de créer une porte XOR en combinant d'autres portes logiques. Il est notamment possible de la concevoir en utilisant uniquement des portes NOR ou des portes NAND.

Circuits équivalents à une porte XOR
Porte XOR à base de transistors CMOS
CmosXORGate CMOS6TrXOR
CMOS XOR Gate Cmos xor

La technologie NMOS[modifier | modifier le wikicode]

Nous allons commencer avec la technologie NMOS, mais les circuits PMOS sont relativement similaires. Ceux-ci sont fabriqués avec des transistors MOS intercalés avec une résistance, qui relie directement la tension d'alimentation à la sortie.

Circuit en logique NMOS.

Leur fonctionnement est assez facile à expliquer. Quand la sortie doit être à 1, tous les transistors sont ouverts. Il n'y a pas de chemin qui relie la sortie à la masse. Par contre, la sortie est connectée à la tension d'alimentation, ce qui fait qu'elle est mise à 1. On place une résistance entre la tension d'alimentation et la sortie pour éviter que le courant qui la traverse soit trop fort dans cette situation. Quand la sortie doit être à 0, il y a au moins un transistor NMOS qui se ferme. Mais si un transistor NMOS se ferme et connecte l'alimentation à la masse, les choses changent. Les lois compliquées de l'électricité nous disent alors que la sortie est connectée à la masse, soit au zéro volts. Elle est donc mise à 0.

Fonctionnement d'un circuit en technologie NMOS.

Voici les circuits obtenus :

Porte NON NMOS. NMOS-NAND-gate NMOS-NOR-gate NMOS AND gate NMOS OR gate

Les portes de base, utilisées pour fabriquer toutes les autres, sont les portes NON, NAND et NOR. Les portes ET et OU sont fabriqués en plaçant une porte NON à la suite d'une porte NAND/NOR.

La porte NON[modifier | modifier le wikicode]

Le circuit d'une porte NON en technologie NMOS est illustré ci-dessous. Le principe de ce circuit est assez simple : l'étude de seulement deux cas permet de le comprendre en détail. Si on envoie un 0 sur la grille du transistor, celui-ci s'ouvre et la sortie est reliée à la tension d'alimentation à travers la résistance. À l'inverse, quand on met un 1 sur la grille, le transistor se ferme et la sortie est reliée à la masse, donc mise à 0. Le résultat est bien un circuit inverseur.

Porte NON NMOS. Porte NON NMOS : fonctionnement.

La porte NOR[modifier | modifier le wikicode]

La porte NOR est similaire à la porte NON, si ce n'est qu'il y a maintenant deux transistors en parallèle. Si l'une des grilles est mise à 1, son transistor se fermera et la sortie sera mise à 0. Par contre, quand les deux entrées sont à 0, les transistors sont tous les deux ouverts, et la sortie est mise à 1. Le comportement obtenu est bien celui d'une porte NOR.

NMOS-NOR-gate Fonctionnement d'une porte NOR NMOS.

La porte NAND[modifier | modifier le wikicode]

La porte NAND fonctionne sur un principe similaire au précédent, si ce n'est qu'il faut que les deux grilles soient à zéro pour obtenir une sortie à 1. Pour mettre la sortie à 0 quand seulement les deux transistors sont ouverts, il suffit de les mettre en série, comme dans le schéma ci-dessous. Le circuit obtenu est bien une porte NAND.

NMOS-NAND-gate
Funktionsprinzip eines NAND-Gatters

La technologie PMOS[modifier | modifier le wikicode]

Les circuits en technologie PMOS ressemblent beaucoup aux circuits en technologie NMOS, mais ils sont inversés. Rien d'étonnant à cela, les deux types de transistors, PMOS et NMOS, ayant un fonctionnement inverse. Là encore, les circuits PMOS sont construits d'une manière assez similaire aux circuits CMOS, si ce n'est que les transistors NMOS sont remplacés par une résistance qui relie ici la masse à la sortie.

PMOS NOT PMOS NAND corr PMOS NOR corr

Les circuits intégrés[modifier | modifier le wikicode]

Broches du processeur MOS6502.

On peut utiliser des portes logiques et/ou des transistors pour créer des circuits plus compliqués, souvent appelés circuits intégrés. Ces circuits ont, comme les portes logiques, des broches métalliques sur lesquelles on envoie des tensions, chaque broche pouvant servir soit d'entrée, soit de sortie (rarement les deux). Certaines de ces broches vont recevoir la tension d'alimentation (broche VCC), d'autres vont être reliées à la masse (broche GND), d'autres vont porter des bits de données ou de contrôle. À l'intérieur de ces circuits intégrés, on trouve un grand nombre de transistors et de portes logiques qui sont reliés entre eux et/ou connectés aux broches d'entrée/sortie.

Les broches[modifier | modifier le wikicode]

La plupart des circuits actuels, processeurs et mémoires, comprennent un grand nombre de broches : plusieurs centaines ! Si on prend l'exemple du processeur MC68000, un vieux processeur inventé en 1979 présent dans les calculatrices TI-89 et TI-92, celui-ci contient 68000 transistors (d'où son nom : MC68000). Il s'agit d'un vieux processeur complètement obsolète et particulièrement simple. Et pourtant, celui-ci contient pas mal de broches : 37 au total ! Pour comparer, sachez que les processeurs actuels utilisent entre 700 et 1300 broches d'entrée et de sortie. À ce jeu là, notre pauvre petit MC68000 passe pour un gringalet !

Pour être plus précis, le nombre de broches (entrées et sorties) d'un processeur dépend du socket de la carte mère. Par exemple, un socket LGA775 est conçu pour les processeurs comportant 775 broches d'entrée et de sortie, tandis qu'un socket AM2 est conçu pour des processeurs de 640 broches. Certains sockets peuvent carrément utiliser 2000 broches (c'est le cas du socket G34 utilisé pour certains processeurs AMD Opteron). Pour la mémoire, le nombre de broches dépend du format utilisé pour la barrette de mémoire (il existe trois formats différents), ainsi que du type de mémoire. Certaines mémoires obsolètes (les mémoires FPM-RAM et EDO-RAM) se contentaient de 30 broches, tandis que la mémoire DDR2 utilise entre 204 et 244 broches.

Les sorties et leurs types[modifier | modifier le wikicode]

Les sorties des circuits intégrés peuvent se classer en plusieurs types, selon leur fonctionnement. On distingue principalement les sorties totem-pole, les sorties à drain ouvert et les sorties trois-état.

Les sorties totem-pole sont les plus communes pour les circuits CMOS. Ce sont des sorties qui sont connectées à deux transistors : un qui relie la sortie à la masse, et un autre qui la relie à la tension d'alimentation. En technologie CMOS, elles sont équivalentes à des sorties connectées à une porte logique.

Sortie à collecteur ouvert, équivalent en technologie TTL d'une sortie à drain ouvert.

Les sorties à drain ouvert sont reliées à un seul transistor, comme indiqué dans le schéma ci-contre. Le transistor relie la sortie à la masse, mais rien ne relie la sortie à la tension d'alimentation. La sortie peut être mise à 0 par le circuit intégré, mais elle ne peut pas être mise à 1 sans intervention extérieure. Pour utiliser une sortie à drain ouvert, il faut relier la sortie à la tension d'alimentation à travers une résistance, appelée résistance de rappel. Dans ce cas, la sortie est mise à 0 ou 1 selon que le transistor est ouvert ou fermé. Si le transistor est ouvert, la sortie n'est pas reliée au circuit. À la place, elle est connectée à la tension d'alimentation, ce qui fait que la sortie est à 1. Si le transistor est fermé, la tension d'alimentation est reliée à la masse et il en est de même pour la sortie. En clair, elle est à 0.

Les sorties à totem-pole ont pour caractéristique de toujours être connectées soit à la masse, soit à la tension d'alimentation. Les sorties à drain ouvert ne sont pas dans ce cas là, du moins sans résistance de rappel. Si on regarde bien, elles peuvent être connectées soit à la masse, soit à rien. Cet état où elles ne sont pas connectées à quoi que ce soit n'est pas utilisé tel quel. Par contre, le troisième type de sortie en fait bon usage. Il s'agit des sorties trois-état. leur caractéristique principale est qu'elles peuvent prendre trois états, comme leur nom l'indique. Soit elles sont connectées à la masse, soit elles sont reliées à la tension d'alimentation, soit elles ne sont connectée ni à l'une ni à l'autre. Si les deux premiers cas correspondent à un 0 et à un 1, l'état déconnecté ne correspond à aucun des deux. Il s'agit d'un état utilisé quand on souhaite déconnecter ou connecter à la demande certains composants dans un circuit. Vous comprendrez en quoi ces sorties sont utiles quand nous parlerons des mémoires et des bus de communication.

Illustration des différents types de sorties d'un circuit intégré et de leur utilisation.


Les circuits combinatoires[modifier | modifier le wikicode]

Dans ce chapitre, nous allons aborder les circuits combinatoires. Ces circuits font comme tous les autres circuits : ils prennent des données sur leurs entrées, et fournissent un résultat en sortie. Le truc, c'est que ce qui est fourni en sortie ne dépend que du résultat sur les entrées, et de rien d'autre (ce n'est pas le cas pour tous les circuits). Pour donner quelques exemples, on peut citer les circuits qui effectuent des additions, des multiplications, ou d'autres opérations arithmétiques du genre.


Quelle que soit la complexité du circuit combinatoire à créer, celui-ci peut être 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 n'est pas un circuit combinatoire, mais appartient à la classe des circuits séquentiels, que nous verrons dans le prochain chapitre.

Dans ce qui va suivre, nous allons voir comment concevoir ce genre de circuits. Il existe des méthodes et procédures assez simples qui permettent à n'importe qui de créer n'importe quel circuit combinatoire. Nous allons voir comment créer des circuits combinatoires à plusieurs entrées, mais à 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 à partir du nombre envoyé en entrée.

Exemple d'un circuit électronique à une seule sortie.

C'est à partir de circuits de ce genre que l'on peut créer des circuits à plusieurs sorties : il suffit d'assembler plusieurs circuits à une sortie. La méthode pour ce faire est très simple : chaque sortie est calculée indépendamment des autres, uniquement à partir des entrées. Ainsi, pour chaque sortie du circuit, on crée un circuit à plusieurs entrées et une sortie : ce circuit déduit quoi mettre sur cette sortie à partir des entrées. En assemblant ces circuits à plusieurs entrées et une sortie, on peut ainsi calculer toutes les sorties.

Comment créer un circuit à plusieurs sorties avec des sous-circuits à une sortie.

Décrire un circuit : tables de vérité et équations logiques[modifier | modifier le wikicode]

Ce schéma montre les trois représentations possibles d'un circuit. Le circuit en question est illustré à gauche (il s'agit d'un circuit nommé décodeur 2 vers 4, mais cela n'a pas d'importance ici). Ses deux autres descriptions, à savoir la table de vérité et ses équations logiques, sont illustrées à droite du schéma.

Dans ce qui va suivre, nous aurons besoin de décrire un circuit électronique, le plus souvent un circuit que l'on souhaite concevoir ou utiliser. Et pour cela, il existe plusieurs grandes méthodes : la table de vérité, les équations logiques et 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 il est câblé. 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.

La table de vérité[modifier | modifier le wikicode]

La table de vérité décrit ce que fait le circuit, mais ne se préoccupe pas de dire comment. Elle ne dit pas quelles sont les portes logiques utilisées pour fabriquer le circuit, ni comment celles-ci sont reliées. Il s'agit d'une description du comportement du circuit, pas du circuit lui-même. En effet, elle se borne à donner la valeur de la sortie pour chaque entrée. Pour l'obtenir, il suffit de lister la valeur de chaque sortie pour toute valeur possible en entrée : on obtient alors la table de vérité du circuit. Pour créer cette table de vérité, il faut commencer par lister toutes les valeurs possibles des entrées dans un tableau, et écrire à côté les valeurs des sorties qui correspondent à ces entrées. Cela peut être assez long : pour un circuit ayant entrées, ce tableau aura lignes. Mais c'est la méthode la plus simple, la plus facile à appliquer.

Un premier exemple[modifier | modifier le wikicode]

Le premier exemple sera très simple. Le circuit que l'on va créer sera un inverseur commandable, qui fonctionnera soit comme une porte NON, soit se contentera de recopier le bit fournit en entrée. Pour faire le choix du mode de fonctionnement (inverseur ou non), un bit de commande dira 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 :

Entrées Sortie
00 0
01 1
10 1
11 0

Un second exemple[modifier | modifier le wikicode]

Pour donner un autre exemple, on va prendre un circuit calculant le bit de parité d'un nombre. Ce bit de parité est un bit qu'on ajoute aux données à stocker afin de détecter des erreurs de transmission ou d’éventuelles corruptions de données. Le but d'un bit de parité est que le nombre de bits à 1 dans le nombre à stocker, bit de parité inclus, soit toujours un nombre pair. Ce bit de parité vaut : zéro si le nombre de bits à 1 dans le nombre à stocker (bit de parité exclu) est pair et 1 si ce nombre est impair. Détecter une erreur demande de compter le nombre de 1 dans le nombre stocké, bit de parité inclus : si ce nombre est impair, on sait qu'un nombre impair de bits a été modifié. Dans notre cas, on va créer un circuit qui calcule le bit de parité d'un nombre de 3 bits.

Entrées Sortie
000 0
001 1
010 1
011 0
100 1
101 0
110 0
111 1

Un troisième exemple[modifier | modifier le wikicode]

Pour le dernier exemple, nous allons prendre en entrée un nombre de 3 bits. Le but du circuit à concevoir sera de déterminer le bit majoritaire dans ce nombre : celui-ci contient-il plus de 1 ou de 0 ? 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.
Entrées Sortie
000 0
001 0
010 0
011 1
100 0
101 1
110 1
111 1

Les équations logiques[modifier | modifier le wikicode]

Il peut être utile d'écrire un circuit non sous forme d'une table de vérité, ou d'un schéma, mais sous forme d'équations logiques. Mais attention : il ne s'agit pas des équations auxquelles vous êtes habitués. Ces équations logiques ne font que travailler avec des 1 et des 0, et n'effectuent pas d'opérations arithmétiques mais seulement des ET, des OU, et des NON. Dans le détail, les variables sont des bits (les entrées du circuit considéré), alors que 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.

Opérateur Notation 1 Notation 2
NON a
a ET b a.b
a OU b a+b
a XOR b

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 : donne un résultat différent de . Avec nos équations logiques, on peut trouver des situations similaires : par exemple, est différent de .

Les formes normales conjonctives et disjonctives[modifier | modifier le wikicode]

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. Il s'agit d'équations qui impliquent uniquement des portes ET, OU et NON. 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 : .
  • Exemple de forme normale disjonctive : .

Il faut savoir que tout circuit combinatoire peut se décrire avec une forme normale conjonctive et avec une forme normale disjonctive. Mais l'équation obtenue n'est pas forcément la manière idéale de concevoir un circuit. Celui-ci peut par exemple être simplifié en utilisant des portes XOR, ou en remaniant le circuit. Mais obtenir une forme normale est très souvent utile, quitte à simplifier celle-ci par la suite. 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 et de traduire le tout en circuit.

Conversions entre équation, circuit et table de vérité[modifier | modifier le wikicode]

Conversion d'un schéma de circuit en équation logique.

Une équation logique se traduit en circuit assez facilement : il suffit de substituer 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. Elles donnent une idée de comment doit être faite cette substitution. Les schémas ci-dessous montrent un exemple d'équation logique et le circuit qui correspond, tout en montrant les différentes substitutions intermédiaires. À ce propos, concevoir un circuit demande simplement d'établir son équation logique : il suffit de traduire l'équation obtenue en circuit, et le tour est joué !

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

Premier exemple. Second exemple.
Troisième exemple.
Quatrième exemple.

Il est aussi intéressant de parler des liens entre tables de vérité et équation logique. Il faut savoir qu'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. On commence par établir la table de vérité, ce qui est assez simple, avant d'établir une équation logique et 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. En réalité, il existe plusieurs équations logiques différentes pour chaque table de vérité. La raison à cela est que des équations différentes peuvent donner des circuits qui se comportent de la même manière. Après tout, on peut concevoir un circuit de différente manières et des circuits câblés différemment peuvent parfaitement faire la même chose. Des équations logiques qui décrivent la même table de vérité sont dites équivalentes. Par équivalente, on veut dire qu'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 faut savoir qu'il est possible de convertir une équation logique en une autre équation équivalente., chose que nous apprendrons à faire dans la suite de ce chapitre.

Concevoir un circuit combinatoire avec la méthode des minterms[modifier | modifier le wikicode]

Comme dit plus haut, 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. Précisons cependant que ces deux méthodes font la même chose : elles traduisent une table de vérité en équation logique. La première étape de ces deux méthodes est donc d'établir la table de vérité. Voyons un peu de quoi il retourne.

La méthode des minterms, expliquée sans formalisme[modifier | modifier le wikicode]

La méthode des minterms est de loin la plus simple à comprendre. Ses principes sont en effet assez intuitifs et elle est assez facile à appliquer, pour qui connaît ses principes sous-jacents. Pour l'expliquer, nous allons commencer par voir 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)[modifier | modifier le wikicode]

Pour commencer, nous allons voir un circuit très simple, qui est utilisé dans la conception des sous-circuits. Ce circuit est appelé le comparateur avec une constante. C'est un circuit qui possède plusieurs entrées et une seule sortie : on lui envoie un nombre codé sur plusieurs bits en entrée, et le circuit vérifie que ce nombre est égal à une certaine constante (2, 3, 5, 8, ou tout autre nombre) qui dépend du circuit. La sortie est alors mise à 1 si le nombre en entrée est égal à cette constante, alors que la sortie est mise à 0 sinon. Ainsi, on peut créer un circuit qui mettra sa sortie à 1 uniquement si on envoie le nombre 5 sur ses entrées. Ou comme autre exemple, créer un circuit qui met sa sortie à 1 uniquement quand l'entrée correspond au nombre 126. Et ainsi de suite : tout nombre peut servir de constante à vérifier.

Tout circuit de ce type est systématiquement composé de deux couches de portes logiques : une couche de portes NON et 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.

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.

Fonctionnement d'un comparateur avec une constante.

Combiner les comparateurs avec une constante[modifier | modifier le wikicode]

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 bits, on peut placer 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.

Conception d'un circuit à partir de minterms

Méthode des minterms, version formalisée[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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.

Entrées Sortie
00 0
01 1
10 1
11 0

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

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[modifier | modifier le wikicode]

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.

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  ;
  • la seconde ligne où l'entrée vaut 010 : son équation logique vaut  ;
  • la troisième ligne où l'entrée vaut 100 : son équation logique vaut  ;
  • la quatrième ligne où l'entrée vaut 111 : son équation logique vaut .

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 :

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 : .
  • Pour la seconde ligne, l'équation obtenue est : .
  • Pour la troisième ligne, l'équation obtenue est : .
  • Pour la quatrième ligne, l'équation obtenue est : .

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

Traduire l'équation en circuit[modifier | modifier le wikicode]

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.

Concevoir un circuit avec la méthode des maxterms[modifier | modifier le wikicode]

La méthode des minterms, vue précédemment, n'est pas la seule qui permet de 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 des équations logiques, et donc des circuits, différents. Les deux commencent par 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[modifier | modifier le wikicode]

La méthode des maxterms fonctionne sur un principe assez tordu, mais qui fonctionne cependant. Avec celle-ci, on effectue trois étapes, chacune correspondant à l'exact inverse de l'étape équivalente avec les minterms. Les 0 sont remplacés par des 1 et les portes ET par des portes OU.

  • 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.

Un exemple d'application[modifier | modifier le wikicode]

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

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 :

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 :

  • pour la première ligne ;
  • pour la seconde ligne ;
  • pour la troisième ligne.

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

Quelle méthode choisir ?[modifier | modifier le wikicode]

On peut se demander quelle méthode choisir entre minterms et maxterms. L'exemple précédent nous donne un indice. Si on applique la méthode des minterms sur l'exemple précédent, vous allez prendre du temps et obtenir une équation logique bien plus compliquée, avec beaucoup de minterms. Alors que c'est plus rapide avec les maxterms, l'équation obtenue étant beaucoup plus simple. Cela vient du fait que 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[modifier | modifier le wikicode]

La méthode des maxterms fonctionne sur un principe un peu différent 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, alors qu'un circuit maxterm vérifie si l'entrée ne met pas la sortie à 0. Dit autrement, ils vérifient soit que l'entrée est un minterm, soit que l'entrée n'est pas un maxterm.

L’aperçu complet de la méthode[modifier | modifier le wikicode]

Pour cela, un circuit conçu avec la méthode des maxterms procède en deux étapes : il 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 avec plusieurs comparateurs avec une constante modifiée : un pour chaque maxterm. Chaque comparateur dit si l'entrée est différente du maxterm associé : 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.
Conception d'un circuit à partir de maxterms.

Le circuit de comparaison[modifier | modifier le wikicode]

Le circuit de comparaison fonctionne sur le principe suivant : il compare l'entrée avec le maxterm bit par bit, chaque bit étant comparé indépendamment des autres, en parallèle. Les résultats des comparaisons sont ensuite combinées pour donner le bit de résultat.

Le circuit de comparaison donne un 1 quand les bits sont différents et un 0 s'ils sont égaux. La comparaison bit à bit est effectuée par une simple porte logique, qui n'est autre que la porte NON en entrée du circuit (ou son absence). Pour comprendre pourquoi, regardons la table de vérité du circuit de comparaison, illustré ci-dessous. On voit que si le bit du maxterm est 0, alors la sortie est égale au bit d'entrée. Mais si le bit du maxterm est à 1, alors la sortie est l'inverse du bit d'entrée.

Bit du maxterm Bit d'entrée Bit de sortie
0 0 0
0 1 1
1 0 1
1 1 0

Maintenant, passons à la combinaison des résultats. Si au moins un bit d'entrée est différent du bit du maxterm, alors l'entrée ne correspond pas au maxterm. On devine donc qu'on doit combiner les résultats avec une porte OU.

Simplifier un circuit[modifier | modifier le wikicode]

Comme on l'a vu, la méthode précédente donne une équation logique qui décrit un circuit. Mais quelle équation : on se retrouve avec un gros paquet de ET et de OU ! heureusement, il est possible de simplifier cette équation. Pour donner un exemple, sachez que cette équation :  ; peut se simplifier en : avec les règles de simplifications que nous allons voir. Dans cet exemple, on passe donc de 17 portes logiques à seulement 3 ! Bien sûr, on peut simplifier cette équation juste pour se simplifier la vie lors de la traduction de cette équation en circuit, mais cela sert aussi à autre chose : cela permet d'obtenir un circuit plus rapide et/ou utilisant moins de portes logiques. Autant vous dire qu'apprendre à simplifier ces équations est quelque chose de crucial, particulièrement si vous voulez concevoir des circuits un tant soit peu rapides.

L'algèbre de Boole[modifier | modifier le wikicode]

Pour simplifier une équation logique, on peut utiliser certaines propriétés mathématiques simples pour factoriser ou développer comme on le ferait avec une équation mathématique normale. Ces propriétés forment ce qu'on appelle l’algèbre de Boole. En utilisant ces règles algébriques, on peut factoriser ou développer certaines expressions, comme on le ferait avec une équation normale, ce qui permet de simplifier une équation logique assez intuitivement. Le tout est de bien faire ces simplifications en appliquant correctement ces règles, ce qui peut demander un peu de réflexion.

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 distributivité et la commutativité des opérateurs logiques[modifier | modifier le wikicode]

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.

Associativité, commutativité et distributivité
Commutativité



Associativité



Distributivité


Les autres règles sont par contre plus importantes.

Les règles de type bit à bit[modifier | modifier le wikicode]

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 :

  • soit on fait un ET/OU/XOR entre un bit et lui-même ;
  • soit on fait un ET/OU/XOR entre un bit et son inverse ;
  • soit on fait un ET/OU/XOR entre un bit et 1 ;
  • soit on fait un ET/OU/XOR entre un bit et 0.

Le premier cas regroupe les trois formules suivantes :

Le second cas regroupe les trois formules suivantes :

,
.

Le troisième cas regroupe les trois formules suivantes :

,
.

Le dernier cas regroupe les trois formules suivantes :

,
.

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

Règles bit à bit
Idempotence


Élément nul


Élément Neutre



Complémentarité





Ces relations permettent de simplifier des équations logiques, mais peuvent avoir des utilisations totalement différentes.

Nous avons déjà utilisé implicitement les formules du premier cas, à savoir et dans le chapitre sur les portes logiques. En effet, nous avions vu qu'il est possible de fabriquer une porte NON à partir d'une porte NAND ou d'une porte NOR. L'idée était d'envoyer le bit à inverser sur les deux entrées d'une NOR/NAND, le ET/OU recopiant le bit sur sa sortie et le NON l'inversant. Pour retrouver ce résultat, il suffit d'ajouter une porte NON dans les formules et , ce qui donne :

Au passage, la formule nous dit pourquoi cela ne marcherait pas du tout avec une porte XOR.

Pour la formule , elle sert dans certaines situations particulières, où l'on veut initialiser un nombre à zéro, peu importe que ce nombre soit une variable, la sortie d'un circuit combinatoire ou un registre. La formule nous dit que le résultat d'un XOR entre un bit et lui-même est toujours zéro. Et cela s'applique aussi à des nombres : si on XOR un nombre avec lui-même, chacun de ses bits est XORé avec lui-même et est donc mis à zéro. Conséquence : un nombre XOR lui-même donnera toujours zéro. Cette propriété est utilisée pour mettre à zéro un registre, pour le calcul des bits de parité ou pour échanger une valeur entre deux registres. Les formules du second cas, à savoir , et , permettent de faire quelque chose de similaire. La première formule dit que faire un ET entre un nombre et son inverse donnera toujours zéro, comme un XOR entre un nombre et lui-même. Pour les deux autres formules, elles disent que le résultat sera toujours un bit à 1. Cela sert cette fois-ci si on veut initialiser une variable, un registre ou une sortie de circuit à une valeur où tous les bits sont à 1.

Les formules du troisième et quatrième cas 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.

Les lois de de Morgan et la double négation[modifier | modifier le wikicode]

Parmi les règles de l’algèbre de Boole, les lois de de Morgan et la double négation sont de loin les plus importantes à retenir. Elles sont les seules à impliquer les négations. Voici ces deux règles :

Règles sur les négations
Double négation
Loi de De Morgan


La première loi de de Morgan nous dit simplement qu'une porte NAND peut se fabriquer avec une porte OU précédée de deux portes NON, comme nous l'avions vu au chapitre précédent.

Porte NAND fabriquée avec des portes NON et OU

La seconde loi, quant à elle, dit qu'une porte NOR peut se fabriquer avec une porte ET précédée de deux portes NON, comme nous l'avions vu au chapitre précédent.

Porte NOR fabriquée avec des portes NON et ET

Les règles de Morgan pour deux entrées sont résumées dans le tableau ci-dessous.

Illustration des lois de De Morgan
1. Theorem.svg
2. Theorem.svg

Les lois de de Morgan peut se généraliser pour plus de deux entrées.

1ère loi de de Morgan :
2nd loi de de Morgan :

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 équation équivalente sous forme normale disjonctive, et réciproquement. 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[modifier | modifier le wikicode]

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. Nous l'avions vu dans le chapitre précédent, et montré quelques exemples de circuits équivalents.

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

XOR :
NXOR :

La formule obtenue avec les minterms pour la porte XOR donne ce circuit :

Porte XOR fabriquée à partir de portes ET/OU/NON.

La formule obtenue avec les minterms pour la porte NXOR donne ce circuit :

Porte NXOR fabriquée à partir de portes ET/OU/NON, alternative.

Il est possible d'obtenir une formule équivalente pour la porte XOR, en utilisant l’algèbre de Boole sur les formules précédentes. Pour cela, partons de l'équation de la porte NXOR obtenue avec la méthode des minterms :

Appliquons une porte NON pour obtenir la porte XOR :

Appliquons la loi de de Morgan entre les parenthèses :

Appliquons la loi de de Morgan dans les parenthèses :

Simplifions les doubles négations :

Porte XOR obtenue avec la méthode des maxterms.

Il est possible de faire la même chose, mais pour la porte NXOR. Pour cela, partons de l'équation de la porte XOR obtenue avec la méthode des minterms :

Une porte NXOR est, par définition, l'inverse d'une porte XOR. En appliquant un NON sur l'équation précédente, on trouve donc :

On applique la loi de de Morgan pour le OU entre les parenthèses :

On applique la loi de de Morgan, mais cette fois-ci à l'intérieur des parenthèses :

On simplifie les doubles inversions :

La formule est similaire à celle d'un XOR, la seule différence étant qu'il faut inverser de place les ET et les OU : le ET est dans les parenthèses pour le XOR et entre pour le NXOR, et inversement pour le OU.

Dans les deux exemples précédents, on voit que l'on a pu passer d'une forme normale conjonctive à une forme normale disjonctive et réciproquement, en utilisant la loi de de Morgan. C'est un principe assez général qui se retrouve souvent dans les démonstrations d'équations logiques.

Exemples complets[modifier | modifier le wikicode]

Comme premier exemple, nous allons travailler sur cette équation : . 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  ;
  • Appliquer la règle de complémentarité sur le terme entre parenthèses , 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 . Cela se fait en suivant les étapes suivantes :

  • Factoriser e0, ce qui donne : ;
  • Utiliser la règle du XOR qui dit que , ce qui donne .

Les tableaux de Karnaugh[modifier | modifier le wikicode]

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. Ces deux méthodes possèdent quelques défauts qui nous empêchent de créer de très gros circuits avec. Pour le dire franchement, elles sont trop longues à utiliser quand le nombre d'entrée du circuit dépasse 5 ou 6. Nous allons cependant aborder la méthode du tableau de Karnaugh, qui peut être assez utile pour des circuits simples. 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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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.

Exemple de regroupement valide.
Exemple de regroupement invalide.
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[modifier | modifier le wikicode]

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.


Dans ce chapitre et les suivants, nous allons voir comment implémenter sous forme de circuits certaines opérations extrêmement courantes dans un ordinateur. Les quelques circuits que nous allons voir seront réutilisés massivement dans les chapitres qui suivront, aussi nous allons passer quelque temps sur ces bases. Le présent chapitre abordera des opérations qui ne sont pas arithmétiques (comprendre des additions, multiplications ou autres), et qui portent le nom d’opérations logiques. Les opérations logiques travaillent sur des suites de bits d'une longueur fixe, l'écriture binaire d'un nombre pour simplifier. Il en existe de deux types, les instructions bit à bit et les instructions de décalage/rotation, mais ce chapitre se concentre sur les opérations bit à bit.

Les opérations bit à bit appliquent un ET, OU, XOR ou NOT sur un ou deux nombres. La plus simple est clairement l'opération NOT, qui inverse tous les bits d'un nombre : les 0 deviennent des 1, et les 1 deviennent des 0. Mais il est aussi possible de prendre deux nombres, de faire un ET/OU/XOR entre les bits de même poids, et de renvoyer le tout en guise de résultat. Le résultat de ces opérations n'est pas vraiment interprétable mathématiquement, la seule exception tient dans l'opération NOT.

  • Pour un entier en complément à 1, le NOT sert à obtenir l'opposé d'un nombre : dit autrement, .
  • Pour un entier en complément à deux, le NOT donne l'opposé d'un nombre auquel on aurait retranché 1 : .
  • Pour un entier non-signé, le NOT va donner la valeur

Le premier point est une définition, c'est comme cela qu'on définit l'inverse d'un nombre en complément à un.

Le second point s'explique par le fait qu'en complément à deux, on a

Le dernier résultat est facile à comprendre quand on sait que la somme donne un nombre de n bits dont tous les bits sont à 1, égal par définition à .

Les circuits de mise à zéro/un/d'inversion[modifier | modifier le wikicode]

Dans ce qui suit, nous allons voir ce qui se passe quand on effectue un ET, un OU, ou un XOR sur tous les bits d'un nombre en même temps. Pour simplifier le tout, nous n’allons pas regarder ce qui se passe quand on fait un ET/OU/XOR entre deux nombres. À la place, nous allons faire un ET/OU/XOR entre une opérande quelconque et un nombre contenant entièrement des 0 ou entièrement des 1. En clair, on va faire un ET/OU/XOR avec un nombre de la forme 00000000...000 ou 11111111...111. Cela peut paraître assez simpliste, mais c'est quelque chose de très utile. De plus, cela permet de comprendre ce qu'il se passe dans le cas général.

Pour comprendre ce que font ces opérations, il faut rappeler les relations suivantes, qui donnent le résultat d'un ET/OU/XOR entre un bit quelconque noté a et un bit qui vaut 0 ou 1.

Opération Interprétation du résultat
Porte ET Mise à zéro du bit d'entrée
Recopie du bit d'entrée
Porte OU Mise à 1 du bit d'entrée
Recopie du bit d'entrée
Porte XOR Recopie du bit d'entrée
Inversion du bit d'entrée

Les circuits qui vont suivre appliquent la même opération entre tous les bits d'une opérande et un bit d'entrée. Le bit d'entrée indique si le nombre est égal à 00000000...000 ou 11111111...111. Il vaut 0 si le nombre est 00000000...000, et vaut 1 pour 11111111...111. En fait, le bit d'entrée est recopié en plusieurs exemplaires pour donner le nombre voulu. Ce qui fait qu'on peut simplement envoyer le bit d'entrée sur les portes ET/OU/XOR. Cela peut paraître compliqué, mais cela deviendra très clair quand nous verrons les schémas ci-dessous.

Le circuit de mise à zéro[modifier | modifier le wikicode]

Dans cette section, nous allons voir un circuit qui prend en entrée un nombre et le met à zéro si une condition est respectée. Pour le dire autrement, le circuit va soit recopier l'entrée telle quelle sur sa sortie, soit la mettre à zéro. Le choix entre les deux situations est réalisé par une entrée Reset de 1 bit : un 0 sur cette entrée met la sortie à zéro, un 1 signifie que l'entrée est recopiée en sortie. La porte ET est toute indiquée pour cela. La mise à zéro d'un bit d'entrée demande de faire un ET de celui-ci avec un 0, alors que recopier un bit d'entrée demande de faire un ET de celui-ci avec un 1. Il suffit d'envoyer le bit d'entrée sur les portes ET, comme illustré ci-dessous.

Circuit de mise à zéro

Le circuit de mise à la valeur maximale[modifier | modifier le wikicode]

Dans cette section, nous allons voir un circuit qui prend en entrée un nombre et met sa sortie à la valeur maximale si une condition est respectée. Pour le dire autrement, le circuit va soit recopier l'entrée telle quelle sur sa sortie, soit la mettre à 11111...111. Le choix entre les deux situations est réalisé par une entrée Set de 1 bit : un 1 sur cette entrée met la sortie à la valeur maximale, un 0 signifie que l'entrée est recopiée en sortie. La porte OU est toute indiquée pour cela. La mise à 1 d'un bit d'entrée demande de faire un OU de celui-ci avec un 1, alors que recopier un bit d'entrée demande de faire un OU de celui-ci avec un 0. Il suffit d'envoyer le bit d'entrée sur les portes ET, comme illustré ci-dessous.

Circuit de mise à 1111111...11

Ce circuit est utilisé pour gérer les débordements d'entier dans les circuits de calculs qui utilise l'arithmétique saturée (voir le chapitre sur le codage des entiers pour plus d'explications). Les circuits de calculs sont souvent suivis par ce circuit de mise à 111111...111, pour gérer le cas où le calcul déborde, afin de mettre la sortie à la valeur maximale. Évidemment, le circuit de calcul doit non seulement faire le calcul, mais aussi détecter les débordements d'entiers, afin de fournir le bit pour l'entrée Set.

L'inverseur commandable[modifier | modifier le wikicode]

Dans cette section, nous allons voir un inverseur commandable, un circuit qui, comme son nom l'indique, inverse les bits d'un nombre passé en entrée. Ce circuit inverse un nombre quand on lui demande et ne fait rien sinon. On précise au circuit s'il doit inverser ou non l'opérande d'entrée avec un bit de commande, souvent nommé Invert. Ce dernier vaut 1 si le circuit doit inverser l'opérande et 0 sinon. La porte XOR est toute indiquée pour, ce qui fait que le circuit d'inversion commandable est composé d'une couche de portes XOR, chaque porte ayant une entrée connectée au bit de commande.

Inverseur commandable par un bit.

Les circuits de masquage total/partiel[modifier | modifier le wikicode]

Les opérations de la section précédente appliquent un ET/OU/XOR entre une opérande et un bit. Maintenant, nous allons voir ce qu'il se passe quand on applique un ET/OU/XOR entre deux nombres. Le premier nombre sera appelé l'opérande et le second le masque. L'opération ET/OU/XOR sur l'opérande va soit recopier certains bits de l’opérande, soit les modifier. L'utilité est de modifier certains bits d'un nombre, en laissant les autres intacts. Les bits à modifier sont indiqués par le masque : chaque bit du masque indique s'il faut modifier ou laisser intact le bit correspondant dans l'opérande.

Le résultat dépend suivant que l'opération est un ET, un OU ou un XOR.

  • Le ET permet soit de recopier le bit d'entrée, soit de le mettre à 0. En clair, faire un ET entre l'opérande et le masque va mettre certains bits de l’opérande à 0 et va recopier les autres. Les bits mis à 0 sont ceux où le bit du masque correspondant est à 0, tandis que les autres sont recopiées tels quels. L'opérande est donc partiellement mise à 0 et les bits à mettre à 0 sont indiqués par le masque.
  • La même chose a lieu avec l'opération OU, sauf que cette fois-ci, les bits de l'opérande sont soit recopiés, soit mis à 1. Les bits mis à 1 sont ceux pour lesquels le bit du masque correspondant est un 1.
  • Dans le cas d'un XOR, les bits sont inversés. Les bits inversés sont ceux pour lesquels le bit du masque correspondant est un 1.
Inverseur commandable par un masque.

Exemples d'utilisation[modifier | modifier le wikicode]

Pour donner un exemple d'utilisation, supposons que j'ai regroupé plusieurs bits, dont chacun a une signification bien précise. Par exemple, je peux regrouper les droits d'accès dans un fichier dans un nombre : un des bits du nombre me dira alors si je peux écrire dans le fichier, un autre me dira si je peux le lire, un autre si… Bref, si jamais je veux modifier mes droits en écriture de mon fichier, je dois mettre un bit bien précis à 1 ou à 0 (suivant la situation). Cela peut se faire facilement en utilisant une instruction bit à bit entre ce nombre et une constante bien choisie.

Un autre cas typique est celui où un développeur compacte plusieurs données dans un seul entier. Par exemple, prenons le cas d'une date, exprimée sous la forme jour/mois/année. Un développeur normal stockera cette date dans trois entiers : un pour le jour, un pour le mois, et un pour la date. Mais un programmeur plus pointilleux sera capable d'utiliser un seul entier pour stocker le jour, le mois, et l'année. Pour cela, il raisonnera comme suit :

  • un mois comporte maximum 31 jours : on doit donc encoder tous les nombres compris entre 1 et 31, ce qui peut se faire en 5 bits ;
  • une année comporte 12 mois, ce qui tient dans 4 bits ;
  • et enfin, en supposant que l'on doive gérer les années depuis la naissance de Jésus jusqu'à l'année 2047, 11 bits peuvent suffire.

Dans ces conditions, notre développeur décidera d'utiliser un entier de 32 bits pour le stockage des dates :

  • les 5 bits de poids forts serviront à stocker le jour ;
  • les 4 bits suivant stockeront le mois ;
  • et les bits qui restent stockeront l'année.

Dans cette situation, le développeur qui souhaite modifier le jour ou le mois d'une date devra modifier une partie des bits, tout en laissant les autres intacts. Encore une fois, cela peut se faire facilement en utilisant une instruction bit à bit entre ce nombre et une constante bien choisie.


Dans les chapitres précédents, nous avons vu comment fabriquer des circuits relativement généraux. Il est maintenant temps de voir quelques circuits relativement simples, très utilisés. Ces circuits simples sont utilisés pour construire des circuits plus complexes, comme des processeurs, des mémoires, et bien d'autres. Les prochains chapitres vont se concentrer exclusivement sur ces circuits simples, mais courants. Nous allons donner quelques exemples de circuits assez fréquents dans un ordinateur et voir comment construire ceux-ci avec des portes logiques. Dans ce chapitre, nous allons nous concentrer sur quelques circuits, que j'ai décidé de regrouper sous le nom de circuits de sélection. Les circuits que nous allons présenter sont utilisés dans les mémoires, ainsi que dans certains circuits de calcul. Il est important de bien mémoriser ces circuits, ainsi que la procédure pour les concevoir : nous en aurons besoin dans la suite du cours. Ils sont au nombre de quatre : le décodeur, l'encodeur, le multiplexeur et le démultiplexeur.

Le décodeur[modifier | modifier le wikicode]

Décodeur à 3 entrées et 8 sorties.

Le premier circuit que nous allons voir est le décodeur, un composant qui contient un grand nombre d'entrées et de sorties, avec des sorties qui sont numérotées. Un décodeur possède une entrée sur laquelle on envoie un nombre codé bits et sorties de 1 bit. Par exemple, un décodeur avec une entrée de 2 bits aura 4 sorties, un décodeur avec une entrée de 3 bits aura 8 sorties, un décodeur avec une entrée de 8 bits aura 256 sorties, etc. Généralement, on précise le nombre de bits d'entrée et de sortie comme suit : on parle d'un décodeur X vers Y pour X bits d'entrée et Y de sortie. Ce qui fait qu'on peut parler de décodeur 3 vers 8 pour un décodeur à 3 bits d'entrée et 8 de sortie, de décodeur 4 vers 16, etc.

Le fonctionnement d'un décodeur est très simple : il prend sur son entrée un nombre entier x codé en binaire, puis il positionne à 1 la sortie numérotée x et met à zéro toutes les autres sorties. Par exemple, si on envoie la valeur 6 sur ses entrées, il mettra la sortie numéro 6 à 1 et les autres à zéro.

Pour résumer, un décodeur est un circuit :

  • avec une entrée de bits ;
  • avec sorties de 1 bit ;
  • où les sorties sont numérotées en partant de zéro ;
  • où on ne peut sélectionner qu'une seule sortie à la fois : une seule sortie devra être placée à 1, et toutes les autres à zéro ;
  • et où deux nombres d'entrée différents devront sélectionner des sorties différentes : la sortie de notre contrôleur qui sera mise à 1 sera différente pour deux nombres différents placés sur son entrée.

La table de vérité d'un décodeur[modifier | modifier le wikicode]

Au vu de ce qui vient d'être dit, on peut facilement écrire la table de vérité d'un décodeur. Pour l'exemple, prenons un décodeur 2 vers 4, pour simplifier la table de vérité. Voici sa table de vérité complète, c’est-à-dire qui contient toutes les sorties regroupées :

E0 E1 S0 S1 S2 S3
0 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 0 0 1

Vous remarquerez que la table de vérité est assez spéciale. Les seuls bits à 1 sont sur la diagonale. Et cela ne vaut pas que dans l'exemple choisit, mais cela se généralise pour tous les décodeurs. Cela se voit aussi quand on prend le tableau de Karnaugh d'un décodeur : il n'y a qu'un seul bit à 1 dans le tableau correspondant à une sortie.

Tableau de Karnaugh d'un décodeur 2 vers 4.

Sur chaque ligne, il n'y a qu'un seul bit à 1, ce qui traduit le fait qu'une entrée ne met qu'une seule sortie est à 1 et met les autres à 0. Si on traduit la table de vérité sous la forme d'équations logiques et de circuit, on obtient ceci :

Equations logiques et circuit d'un décodeur 2 vers 4.

Il y a des choses intéressantes à remarquer sur les équations logiques. Pour rappel, l'équation logique d'une sortie est composée, dans le cas général, soit d'un minterm unique, soit d'un OU entre plusieurs minterms. Chaque minterm est l'équation d'un circuit qui compare l'entrée à un nombre bien précis et dépendant du minterm. Si on regarde bien, l'équation de chaque sortie correspond à un minterm et à rien d'autre, il n'y a pas de OU entre plusieurs minterms. Les minterms sont de plus différents pour chaque sortie et on ne trouve pas deux sorties avec le même minterm. Enfin, chaque minterm possible est présent : X bits d'entrée nous donnent 2^X entrées différentes possibles, donc 2^X minterms possibles. Et il se trouve que tous ces minterms possibles sont représentés dans un décodeur, ils ont tous leur sortie associée. C'est une autre manière de définir un décodeur : toutes ses sorties codent un minterm, deux sorties différentes ont des minterms différents et tous les minterms possibles sur n bits sont représentés.

Ces informations vont nous être utiles pour la suite. En effet, grâce à elles, nous allons en déduire une méthode générale pour fabriquer un décodeur, peu importe son nombre de bits d'entrée et de sortie. Mais elles permettent aussi de montrer que l'on peut créer n'importe quel circuit combinatoire quelconque à partir d'un décodeur et de quelques portes logiques. Dans ce qui suit, on suppose que le circuit combinatoire en question a une entrée de n bits et une seule sortie de 1 bit. Pour rappel, ce genre de circuit se conçoit en utilisant une table de vérité qu'on traduit en équations logiques, puis en circuits. Le circuit obtenu est alors soit un simple minterm, soit un OU entre plusieurs minterms. Or, le décodeur contient tous les minterms possibles pour une entrée de n bits, avec un minterm par sortie. Il suffit donc de prendre une porte OU et de la connecter aux minterms/sorties adéquats.

Conception d'un circuit combinatoire quelconque à partir d'un décodeur.

Ceci étant dit, passons à la conception d'un décodeur avec des portes logiques.

L'intérieur d'un décodeur[modifier | modifier le wikicode]

On vient de voir que chaque sortie d'un décodeur correspond à son propre minterm, et que tous les minterms possibles sont représentés. Rappelons que chaque minterm est associé à un circuit qui compare l'entrée à une constante X, X dépendant du minterm. En combinant ces deux informations, on devine qu'un décodeur est simplement composé de comparateurs avec une constante que de minterms/sorties. Par exemple, si je prends un décodeur 7 vers 128, cela veut dire qu'on peut envoyer en entrée un nombre codé entre 0 et 127 et que chaque nombre aura son propre minterm associé : il y aura un minterm qui vérifie si l'entrée vaut 0, un autre vérifie si elle vaut 1, un autre qui vérifie si elle vaut 2, ... , un minterm qui vérifie si l'entrée vaut 126, et enfin un minterm qui vérifie si l'entrée vaut 127.

Pour reformuler d'une manière bien plus simple, on peut voir les choses comme suit. Si l'entrée du décodeur vaut N, la sortie mise à 1 est la sortie N. Bref, déduire quand mettre à 1 la sortie N est facile : il suffit de comparer l'entrée avec N. Si l'adresse vaut N, on envoie un 1 sur la sortie, et on envoie un zéro sinon. Pour cela, j'ai donc besoin d'un comparateur pour chaque sortie, et le tour est joué. Précisons cependant que cette méthode gaspille beaucoup de circuits et qu'il y a une certaine redondance. En effet, les comparateurs ont souvent des portions de circuits qui sont identiques et ne diffèrent parfois que ce quelques portes logiques. En utilisant des comparateurs séparés, ces portions de circuits sont dupliquées, alors qu'il serait judicieux de partager.

Exemple d'un décodeur à 8 sorties.

Comme autre méthode, plus économe en circuits, on peut créer un décodeur en assemblant plusieurs décodeurs plus simples, nommés sous-décodeurs. Ces sous-décodeurs sont des décodeurs normaux, auxquels on a ajouté une entrée RAZ, qui permet de mettre à zéro toutes les sorties : si on met un 0 sur cette entrée, toutes les sorties passent à 0, alors que le décodeur fonctionne normalement sinon. Construire un décodeur demande suffisamment de sous-décodeurs pour combler toutes les sorties. Si on utilise des sous-décodeurs à n entrées, ceux-ci prendront en entrée les n bits de poids faible de l'entrée du décodeur que l'on souhaite construire (le décodeur final). Dans ces conditions, les n décodeurs auront une de leurs sorties à 1. Pour que le décodeur final se comporte comme il faut, il faut désactiver tous les sous-décodeurs, sauf un avec l'entrée RAZ. Pour commander les n bits RAZ des sous-décodeurs, il suffit d'utiliser un décodeur qui est commandé par les bits de poids fort du décodeur final.

Décodeur 3 vers 8 conçu à partir de décodeurs 2 vers 4.

L'encodeur[modifier | modifier le wikicode]

Encodeur à 8 entrées (et 3 sorties).

Il existe un circuit qui fait exactement l'inverse du décodeur : c'est l'encodeur. Là où les décodeurs ont une entrée de bits et sorties de 1 bit, l'encodeur a à l'inverse entrées de 1 bit avec une sortie de bits. Par exemple, un encodeur avec une entrée de 4 bits aura 2 sorties, un décodeur avec une entrée de 8 bits aura 3 sorties, un décodeur avec une entrée de 256 bits aura 8 sorties, etc. Comme pour les décodeurs, on parle d'un encodeur X vers Y pour X bits d'entrée et Y de sortie. Ce qui fait qu'on peut parler de décodeur 8 vers 3 pour un décodeur à 8 bits d'entrée et 3 de sortie, de décodeur 16 vers 4, etc.

Entrées et sorties d'un encodeur.

De plus, contrairement au décodeur, ce sont les entrées qui sont numérotées de 0 à N et non les sorties. Dans ce qui suit, on va supposer qu'une seule des entrées est à 1. En sortie, l'encodeur donne le numéro de l'entrée qui est à 1. Par exemple, si l'entrée numéro 5 est à 1 et les autres à 0, alors l'encodeur envoie un 5 sur sa sortie.

L'encodeur 4 vers 2[modifier | modifier le wikicode]

Prenons l'exemple d'un encodeur à 4 entrées et 2 sorties. Écrivons sa table de vérité. D'après la description du circuit, on devrait trouver ceci :

Table de vérité d'un encodeur 4 vers 2
E3 E2 E1 E0 S1 S0
0 0 0 1 0 0
0 0 1 0 0 1
0 1 0 0 1 0
1 0 0 0 1 1

Vous voyez que la table de vérité est incomplète. En effet, l'encodeur fonctionne tant qu'une seule de ses entrées est à 1. L'encodeur dit alors quelle est la sortie à 1, mais cela suppose que les autres soient à 0. Si plusieurs entrées sont à 1, le comportement de l'encodeur est à préciser. Mais passons cela sous silence et ne tenons compte que de la table de vérité partielle précédente. On peut traduire cette table de vérité en circuit logique. On obtient alors les équations suivantes :

Le tout donne le circuit suivant :

Exemple d'encodeur à 4 entrées et 2 sorties.

Les encodeurs à plus de deux sorties[modifier | modifier le wikicode]

Il est possible de créer un encodeur complexe en combinant plusieurs encodeurs simples. C'est un peu la même chose qu'avec les décodeurs, pour lesquels on peut créer un décodeur 8 vers 256 à base de deux décodeurs 7 vers 128, ou de quatre décodeurs 6 vers 64. L'idée de découper le nombre d'entrée en morceaux séparés, chaque morceau étant traité par un encodeur à priorité distinct des autres. Les résultats des différents encodeurs sont ensuite combinés pour donner le résultat final.

Pour comprendre l'idée, prenons la table de vérité d'un encodeur 8 vers 3; donnée dans le tableau ci-dessous.

Table de vérité d'un encodeur 8 vers 3
E7 E6 E5 E4 E3 E2 E1 E0 S2 S1 S0
0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0 1
0 0 0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 0 0 0 1 1
0 0 0 1 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 1 0 1
0 1 0 0 0 0 0 0 1 1 0
1 0 0 0 0 0 0 0 1 1 1

En regardant bien, vous verrez que vous pouvez trouver la table de vérité d'un encodeur 4 vers 2 en deux exemplaires, indiquées en rouge.

Table de vérité d'un encodeur 8 vers 3
E7 E6 E5 E4 E3 E2 E1 E0 S2 S1 S0
0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0 1
0 0 0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 0 0 0 1 1
0 0 0 1 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 1 0 1
0 1 0 0 0 0 0 0 1 1 0
1 0 0 0 0 0 0 0 1 1 1

On voit que les deux bits de poids faibles correspondent à la sortie de l'encodeur activé par l'entrée. Si le premier encodeur est activé, c'est lui qui fournit les bits de poids faibles. Inversement, si c'est le second encodeur qui a un résultat non-nul, c'est lui qui fournit les bits de poids faible. Notons que seul un des deux encodeurs a une sortie non-nulle à la fois : soit le premier a une sortie non-nulle, soit c'est le second, mais c'est impossible que ce soit les deux en même temps. Cela permet de déduire quelle opération permet de mixer les deux résultats : un simple OU logique suffit. Car, pour rappel, 0 OU X donne X, quelque que soit le X en question. Les bits de poids faible du résultat se calculent en faisant un OU entre les deux résultats des encodeurs.

Ensuite, il faut déterminer comment fixer le bit de poids fort du résultat. Il vaut 0 si le premier encodeur a une entrée non-nulle, et 1 si c'est le premier encodeur qui a une entrée non-nulle. Pour cela, il suffit de vérifier si les bits de poids forts, associés au premier encodeur, contiennent un 1. Si c'est le cas, alors on met la troisième sortie à 1.

Encodeur fabriqué à partir d'encodeurs plus petits.

Notons que cette procédure, à savoir faire un OU entre les sorties de deux encodeurs simples, puis faire un OU pour calculer le troisième bit, marche pour tout encodeur de taille quelconque. À vrai dire, le circuit obtenu plus haut d'un encodeur 4 vers 2 est conçu ainsi, mais en combinant deux encodeurs 2 vers 1.

La procédure consiste à ajouter trois portes OU à deux encodeurs. Mais ceux-ci sont eux-même composés de portes OU associées à des encodeurs plus petits, et ainsi de suite. On peut poursuivre ainsi jusqu’à tomber sur des encodeurs 4 vers 2, qui sont eux-mêmes composés de deux portes OU. Au final, on se retrouve avec un circuit conçu uniquement à partir de portes OU. Notons qu'il est possible de simplifier le circuit obtenu avec la procédure en fusionnant des portes OU. Si on simplifie vraiment au maximum, le circuit consiste alors en une porte OU à plusieurs entrées par sortie, chacune étant connectée à certaines entrées bien précises. Pour un encodeur 8 vers 3, la simplification du circuit devrait donner ceci :

Encodeur 8 vers 3.

Le multiplexeur[modifier | modifier le wikicode]

Les décodeurs ont des cousins : les multiplexeurs. Ces multiplexeurs sont des composants qui possèdent un nombre variable d'entrées et une sortie. Le rôle d'un multiplexeur est de recopier le contenu d'une des entrées sur sa sortie. Bien sûr, il faut bien choisir l'entrée qu'on veut recopier sur la sortie : pour cela, notre multiplexeur contient une entrée de commande qui permet de spécifier quelle entrée doit être recopiée.

Multiplexeur à 4 entrées.

Le multiplexeur à deux entrées[modifier | modifier le wikicode]

Le multiplexeur le plus simple est le multiplexeur à deux entrées et une sortie. Il est facile de le construire avec des portes logiques, dans les implémentations les plus simples. Sachez toutefois que les multiplexeurs utilisés dans les ordinateurs récents ne sont pas forcément fabriqués avec des portes logiques, mais qu'on peut aussi les fabriquer directement avec des transistors.

Multiplexeur à deux entrées - symbole.

Pour commencer, établissons sa table de vérité. On va supposer qu'un 0 sur l'entrée de commande sélectionne l'entrée a. La table de vérité devrait être la suivante :

Entrée de commande Entrée a Entrée b Sortie
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1

Sélectionnons les lignes qui mettent la sortie à 1 :

Entrée de commande Entrée a Entrée b Sortie
0 1 0 1
0 1 1 1
1 0 1 1
1 1 1 1

On sait maintenant quels comparateurs avec une constante utiliser. On peut, écrire l'équation logique du circuit. La première ligne donne l'équation suivante : , la seconde donne l'équation , la troisième l'équation et la quatrième l'équation . L'équation finale obtenue est donc :

L'équation précédente est assez compliquée, mais il y a moyen de la simplifier assez radicalement. Pour cela, nous allons utiliser les règles de l’algèbre de Boole. Pour commencer, nous allons factoriser et  :

Ensuite, factorisons dans le premier terme et dans le second :

Les termes et valent 1 :

On sait que , ce qui fait que l'équation simplifiée est la suivante :

Le circuit qui correspond est :

Multiplexeur à deux entrées - circuit.

Les multiplexeurs à plus de deux entrées[modifier | modifier le wikicode]

Il est possible de concevoir un multiplexeur quelconque à partir de sa table de vérité. Le résultat est alors un circuit composé d'une porte OU à plusieurs entrées, de plusieurs portes ET, et de quelques portes NON. Un exemple est illustré ci-dessous. Vous remarquerez cependant que ce circuit a un défaut : la porte OU finale a beaucoup d'entrées, ce qui pose de nombreux problèmes techniques. Il est difficile de concevoir des portes logiques avec un très grand nombre d'entrées. Aussi, les applications à haute performance demandent d'utiliser d'autres solutions.

Multiplexeur conçu à partir de sa table de vérité.

Une solution alternative est de concevoir un multiplexeur à plus de deux entrées en combinant des multiplexeurs plus simples. Par exemple, en prenant deux multiplexeurs plus simples, et en ajoutant un multiplexeur 2 vers 1 sur leurs sorties respectives. Le multiplexeur final se contente de sélectionner une sortie parmi les deux sorties des multiplexeurs précédents, qui ont déjà effectué une sorte de présélection.

Multiplexeur conçu à partir de multiplexeurs plus simples.

Il existe toutefois une manière bien plus simple pour créer des multiplexeurs : il suffit d'utiliser un décodeur, quelques portes OU, et quelques portes ET. L'idée est de :

  • sélectionner l'entrée à recopier sur la sortie ;
  • mettre les autres entrées à zéro ;
  • faire un OU entre toutes les entrées : vu que toutes les entrées non-sélectionnées sont à zéro, la sortie de la porte OU aura la même valeur que l'entrée sélectionnée.

Pour sélectionner l'entrée adéquate du multiplexeur, on utilise un décodeur : si la sortie n du décodeur est à 1, alors l'entrée numéro n du multiplexeur sera recopiée sur sa sortie. Dans ces conditions, l'entrée de commande du multiplexeur correspond à l'entrée du décodeur. Pour mettre à zéro les entrées non-sélectionnées, on ajoute une porte ET par entrée : vu que a.0=0 et a.1=a, la porte ET :

  • recopie l'entrée du multiplexeur si le décodeur sort un 1 ;
  • met à zéro l'entrée si le décodeur sort un 0.
Multiplexeur 2 vers 4 conçu à partir d'un décodeur.

Une autre manière d’expliquer le circuit précédent est d'utiliser la notion de masque vue au chapitre précédent. En effet, ce circuit applique un masque à l'entrée, afin de mettre à 0 les entrées non-sélectionnées. Il fait ensuite un OU entre tous les entrées. LE calcul du masque est réalisé par le décodeur.

On peut aussi simplifier le circuit en remplaçant les portes ET en aval du décodeur par des transistors dont la grille est commandée par le décodeur. Ce faisant, seule une entrée sera connectée à la sortie, alors que les autres seront déconnectées.

Le démultiplexeur[modifier | modifier le wikicode]

Après avoir vu le multiplexeur, il est temps de voir de démultiplexeur. Comme le nom l'indique, le démultiplexeur fait l'exact inverse du multiplexeur. Son rôle est de recopier, sur une des sorties, ce qu'il y a sur l'entrée. Évidemment, la sortie sur laquelle on recopie l'entrée est choisie parmi toutes les sorties possibles. Pour cela, le démultiplexeur possède une entrée de commande, sur laquelle on envoie le numéro de la sortie de destination.

Le démultiplexeur à deux sorties[modifier | modifier le wikicode]

Le démultiplexeur le plus simple est le démultiplexeur à deux sorties. Il possède une entrée de donnée, une entrée de commande et deux sorties, toutes de 1 bit. Suivant la valeur du bit sur l'entrée de commande, il recopie le bit d'entrée, soit sur la première sortie, soit sur la seconde. Les deux sorties sont numérotées respectivement 0 et 1.

Démultiplexeur à 2 sorties.

On peut le concevoir facilement en partant de sa table de vérité.

Entrée de commande Select Entrée de donnée Input Sortie 1 Sortie 0
0 0 0 0
0 1 0 1
1 0 0 0
1 1 1 0

Le circuit obtenu est le suivant :

Démultiplexeur à deux sorties.

Les démultiplexeurs à plus de deux sorties[modifier | modifier le wikicode]

Il est parfaitement possible de créer des démultiplexeurs en utilisant les méthodes du chapitre sur les circuits combinatoires, comme ma méthode des minterms ou les tableaux de Karnaugh. On obtient alors un démultiplexeur assez simple, composé de deux couches de portes logiques : une couche de portes NON et une couche de portes ET à plusieurs entrées.

Démultiplexeur fabriqué avec une table de vérité.

Mais cette méthode n'est pas pratique, car elle utilise beaucoup de portes logiques et que les portes logiques avec beaucoup d'entrées sont difficiles à fabriquer. Pour contourner ces problèmes, on peut ruser. Ce qui a été fait pour les multiplexeurs peut aussi s'adapter aux démultiplexeurs : il est possible de créer des démultiplexeurs en assemblant des démultiplexeurs 1 vers 2. Évidemment, le même principe s'applique à des démultiplexeurs plus complexes : il suffit de rajouter des couches.

Circuit d'un démultiplexeur à 4 sorties, conçu à partir de démultiplexeurs à 2 sorties.

Un démultiplexeur peut aussi se fabriquer en utilisant un décodeur et quelques portes ET. Pour comprendre pourquoi, regardons la table de vérité d'un démultiplexeur à quatre sorties. Si vous éliminez le cas où l'entrée de donnée Input vaut 0, et que vous tenez compte uniquement des entrées de commande, vous retombez sur la table de vérité d'un décodeur. Cela correspond aux cases en rouge.

Input E0 E1 S0 S1 S2 S3
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 0 0
0 1 1 0 0 0 0
1 0 0 1 0 0 0
1 0 1 0 1 0 0
1 1 0 0 0 1 0
1 1 1 0 0 0 1

En réalité, Le fonctionnement d'un démultiplexeur peut se résumer comme suit : soit l'entrée Input est à 1 et il fonctionne comme un décodeur dont l'entrée est l'entrée de commande, soit l'entrée Input vaut 0 et sa sortie est mise à 0. On devine donc qu'il faut combiner un décodeur avec le circuit de mise à zéro vu dans le chapitre précédent. On devine rapidement que l'entrée Input commande la mise à zéro de la sortie, ce qui donne le circuit suivant :

Démultiplexeur conçu à partir d'un décodeur.

L'utilisation des circuits de sélection[modifier | modifier le wikicode]

L'utilité des circuits précédents n'est pas évidente, mais les circuits de sélection sont pourtant des circuits basiques, très utilisés. Nous verrons un cas d'utilisation des encodeurs dans le prochain chapitre, ainsi que dans le chapitre sur les mémoires associatives. Pour le décodeur, nous verrons son utilisation dans le chapitre sur les mémoires adressables (les mémoires RAM et ROM, pour anticiper la suite du cours). Pour le démultiplexeur, nous verrons son usage dans le chapitre sur les bus. Bien sur, il ne s'agit pas là des seules utilisations de ces circuits, mais ce seront les principales. Quant au multiplexeur, la suite de ce cours vous montrera que presque tous les circuits importants comprennent des multiplexeurs. On peut notamment citer les circuits pour faire des calculs sur des nombres entiers ou des nombres flottants, les circuits pour faire des décalages ou autres opérations logiques, voire des circuits plus complexes, comme les mémoires. Cependant, je tiens à vous montrer quelques usages intéressants du multiplexeur dans cette section, usages qui n'ont pas leur place ailleurs dans ce cours.

Créer un circuit de calcul bit à bit avec des multiplexeurs[modifier | modifier le wikicode]

Sachez qu'avec un simple multiplexeur, on peut créer un circuit qui effectue toutes les opérations bit à bit possible avec deux bits. Et cela a déjà été utilisé sur de vrais ordinateurs. Pour deux bits, divers théorèmes de l’algèbre de Boole nous disent que ces opérations sont au nombre de 16, ce qui inclus les traditionnels ET, OU, XOR, NAND, NOR et NXOR. Voici la liste complète de ces opérations, avec leur table de vérité ci-dessous (le nom des opérations n'est pas indiqué) :

  • Les opérateurs nommés 0 et 1, qui renvoient systématiquement 0 ou 1 quel que soit l'entrée ;
  • L'opérateur OUI qui recopie l'entrée a ou b, et l'opérateur NON qui l'inverse : , , ,  ;
  • L’opérateur ET, avec éventuellement une négation des opérandes : , , ,  ;
  • La même chose avec l’opérateur OU : , , ,  ;
  • Et enfin les opérateurs XOR et NXOR : , .
a b
0 0 - 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 - 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 - 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 - 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Le circuit à concevoir prend deux bits, que nous noterons a et b, et fournit sur sa sortie : soit a ET b, soit a OU b, soit a XOR b, etc. Pour sélectionner l'opération, une entrée du circuit indique quelle est l'opération à effectuer, chaque opération étant codée par un nombre. On pourrait penser que concevoir ce circuit serait assez complexe, mais il n'en est rien grâce à une astuce particulièrement intelligente. Regardez le tableau ci-dessus : vous voyez que chaque colonne forme une suite de bits, qui peut être interprétée comme un nombre. Il suffit d'attribuer ce nombre à l'opération de la colonne ! En faisant ainsi, le nombre attribué à chaque opération contient tous les résultats de celle-ci. Il suffit de sélectionner le bon bit parmi ce nombre pour obtenir le résultat. Et on peut faire cela avec un simple multiplexeur, comme indiqué dans le schéma ci-dessous !

Unité de calcul bit à bit de 2 bits, capable d'effectuer toute opération bit à bit.

Il faut noter que le raisonnement peut se généraliser avec 3, 4, 5 bits, voire plus ! Par exemple, il est possible d'implémenter toutes les opérations bit à bit possibles entre trois bits en utilisant un multiplexeur 8 vers 3.


Dans ce chapitre, nous allons aborder plusieurs opérations fortement liées entre elles, illustrées dans le schéma ci-dessous. Elles sont très courantes sur la plupart des ordinateurs, surtout dans les ordinateurs embarqués. beaucoup d'ordinateurs, comme les anciens mac avec des processeurs type Power PC et les processeurs MIPS ou RISC ont des instructions pour effectuer ces opérations.

Mais avant de passer aux explications, un peu de terminologie utile. Dans ce qui suit, nous aurons à utiliser des expressions du type "le 1 de poids faible", "les 0 de poids faible" et quelques autres du même genre. Quand nous parlerons du 0 de poids faible, nous voudrons parler du premier 0 que l'on croise dans un nombre en partant de sa droite. Par exemple, dans le nombre 0011 1011, le 0 de poids faible est le troisième bit en partant de la droite. Quand nous parlerons du 1 de poids faible, c'est la même chose, mais pour le premier bit à 1. Par exemple, dans le nombre 0110 1000, le 1 de poids faible est le quatrième bit. Quant aux expressions "le 1 de poids fort" et "les 0 de poids fort" elles sont identiques aux précédentes, sauf qu'on parcourt le nombre à partir de sa gauche. Par contre, les expressions "les 1 de poids faible" ou "les 0 de poids faible" ne parlent pas de la même chose. Quand nous voudrons parler des 1 de poids faible, au pluriel, nous voulons dire : tous les bits situés avant le 0 de poids faible. Par exemple, prenons le nombre 0011 0011 : les 1 de poids faible correspondent ici aux deux premiers bits en partant de la droite. Même chose quand on parle des zéros de poids faible au pluriel. Quant aux expressions "les 1 de poids fort" ou "les 0 de poids fort" elles sont identiques aux précédentes, sauf qu'on parcourt le nombre à partir de sa gauche.

La première opération que nous allons aborder, Find First Set, donne la position du 1 de poids faible. Cette opération est liée à l'opération Count Trailing Zeros, qui donne le nombre de zéros situés à droite de ce 1 de poids faible. L'opération Find First Set est opposée au calcul du Find highest set, qui donne la position du 1 de poids fort. Le nombre de zéros situés à gauche de ce bit à 1 est appelé le Count Leading Zeros. Ces quatre opérations ont leur équivalents en remplaçant les 0 par des 1 et réciproquement. Par exemple, l'opération Find First Zero donne la position du 0 de poids faible (le plus à droite) et l'opération Find Highest Zero donne la position du 0 de poids fort (le plus à gauche). L'opération Count Trailing Ones donnent le nombre de 1 situés à gauche du 0 de poids fort, tandis que l'opération Count Leading Ones donne le nombre de 1 situés à droite du 0 de poids faible.

Opérations Find First Set ; Find First Zero ; Find Highest Set (le logarithme binaire) ; Find Highest Zero ; Count Leading Zeros ; Count Trailing Zeros ; Count Leading Ones et Count Trailing Ones.

La numérotation des bits et l'équivalence de certaines opérations[modifier | modifier le wikicode]

Dans toutes ces opérations, les bits sont numérotés, leur numéro étant appelé leur position ou leur indice. La position d'un bit est donc donnée par ce numéro. Ces opérations varient selon la méthode utilisée pour numéroter les bits. On peut commencer à compter les bits à partir de 0, le 0 étant le numéro du bit de poids faible. Mais on peut aussi compter à partir de 1, le bit de poids faible étant celui de numéro 1. Ces deux conventions ne sont pas équivalentes. Si on choisit la première convention, certaines opérations sont équivalentes. Par exemple, les opérations Count Trailing Zeros et Find First Set donnent toutes les deux le même résultat. Avec l'autre convention, les deux différent de 1 systématiquement.

Avec la première convention, pour un nombre codé sur bits, on a :

On voit que certaines opérations sont équivalentes, ce qui nous arrange bien. De plus, on peut calculer le résultat de l'opération FHS à partir de l'opération CLZ et réciproquement. De même le résultat de FHZ peut se calculer à partir du résultat de CLO et inversement. Il suffit d'effectuer une simple soustraction, avec une constante qui plus est, ce qui est simple à fabriquer. Ce qui revient à ajouter un circuit pour faire le calcul .

De fait, nous n'aurons qu'à aborder quatre calculs :

  • le Find First Set, abréviée FFS ;
  • le Find highest set, abrévié FHS ;
  • le Find First Zero, abréviée FFZ ;
  • le Find highest Zero, abrévié FHZ.

On peut même aller plus loin et éliminer encore plus le nombre d'opérations différentes à effectuer. En effet, les opérations FHS et FHZ peuvent se déduire l'une de l'autre, en changeant le nombre passé en entrée. Pour cela, il suffit d'inverser les bits de l'entrée, avec un inverseur commandable. Avec l'inversion, le 1 de poids fort deviendra le 0 de poids fort et inversement. Idem pour les opérations FFS et FFZ. En inversant l'entrée, le 1 de poids faible deviendra le 0 de poids faible et inversement.

Circuit qui effectue les opérations FHS, FFS, CLZ et autres.

Reste à voir comment effectuer les deux opérations restantes, à savoir Find Highest Set et Find First Set. Et pour cela, nous allons voir un circuit spécialisé dans ces deux calculs : l'encodeur à priorité.

L'encodeur à priorité, généralités[modifier | modifier le wikicode]

L'encodeur à priorité est un dérivé du circuit encodeur, vu dans le chapitre précédent. La différence ne se situe pas dans le nombre d'entrée ou de sortie, ni même dans son interface extérieure. Comme pour l'encodeur normal, l'encodeur à priorité possède entrées numérotées de 0 à et N sorties. Une autre manière plus intuitive de le dire est qu'il possède N entrées et sorties. Pas de changement de ce point de vue.

La différence entre encodeur simple et encodeur à priorité tient dans leur fonctionnement, dans le calcul qu'ils font. Avec un encodeur normal, on a supposé que seul un bit d'entrée pouvait être à 1, les autres étant systématiquement à 0. Si cette condition est naturellement remplie dans certains cas d’utilisation, ce n'est pas le cas dans d'autres. L'encodeur à priorité est un encodeur amélioré dans le sens où il donne un résultat valide même quand plusieurs bits d'entrée sont à 1. Il donne donc un résultat pour n'importe quel nombre passé en entrée. Mais dans cette situation, il peut réagir de plusieurs manières différentes.

Dans le cas le plus fréquent, l'encodeur à priorité prend en entrée un nombre et donne la position du 1 de poids fort. Ces encodeurs à priorité réalisent l'opération Find Highest Set, qui est reliée à l’opération count leading zeros. Ce qui leur vaut le nom anglais de leading zero detector (LZD) ou encore de leading zero counter (LZC). Mais dans d'autres cas, l'encodeur à priorité donne la position du 1 de poids faible, ce qui correspond à l'opération Count Trailing Zeros. Il existe aussi des encodeurs qui donnent la position du zéro de poids faible, voire du zéro de poids fort, ce qui correspond respectivement aux opérations Find First Zero et Find highest Zero.

En clair, pour les quatre opérations précédentes, il existe un encodeur à priorité qui s'en charge. Il existe même des encodeurs à priorité qui peuvent faire plusieurs opérations, voire les quatre opérations suivant comment on les configure. Par exemple, certains encodeurs peuvent faire les quatre opérations précédentes, suivant ce que l'on envoie sur une entrée de configuration qui précise l'opération à effectuer. Dans ce qui va suivre, nous allons nous concentrer sur des encodeurs qui effectuent l'opération Find Highest Set, nous verrons les autres seulement de manière secondaire.

L'encodeur à priorité conçu à partir de sa table de vérité[modifier | modifier le wikicode]

Il est possible de concevoir l'encodeur à priorité à partir de sa table de vérité, mais les méthodes des minterms ou des maxterms ne donnent pas de très bons résultats.

Notons que ces encodeurs ont souvent une nouvelle entrée notée V, qui indique si la sortie est valide, et qui indique qu'au moins une entrée est à 1. Elle vaut 1 si au moins une entrée est à 1, 0 si toutes les entrées sont à 0.

À titre d'exemple, la table de vérité d'un encodeur à priorité 4 vers 2 est illustré ci-dessous. Le signe X signifie que le bit peut prendre la valeur 0 ou 1 sans que cela change quoique ce soit à l'entrée.

E3 E2 E1 E0 S1 S0 V
0 0 0 1 0 0 0
0 0 1 X 0 1 1
0 1 X X 1 0 1
1 X X X 1 1 1

Les équations logiques obtenues sont donc les suivantes :

On voit quelle est la logique de chaque équation. Pour chaque ligne de la table de vérité, il faut vérifier si les bits de poids fort sont à 0, suivi par un 1, les bits de poids faible après le 1 étant oubliées.

Le circuit obtenu est le suivant :

Encodeur à priorité 4 vers 2.

La table de vérité d'un encodeur à priorité 8 vers 3 est illustré ci-dessous. Le signe X signifie que le bit peut prendre la valeur 0 ou 1 sans que cela change quoique ce soit à l'entrée.

Table de vérité d'un encodeur à priorité 8 vers 3.

Utiliser la table de vérité a des défauts. Premièrement, ce n'est pas la meilleure des solutions pour des circuits avec un grand nombre d'entrée. Faire cela donne des tables de vérité rapidement importantes, mêmes pour des encodeurs avec peu de sorties. Deuxièmement, il est difficile de créer un encodeur capable de faire à la fois l'opération Find Highest Set et l’opération Find First Set à partir de sa table de vérité. Le résultat ressemble à ce qu'on obtiendrait en utilisant un encodeur pour l'opération Find Highest Set, un autre pour l’opération Find First Set, et un multiplexeur pour choisir le bon résultat. Le circuit final utilise beaucoup de portes logiques comparé aux autres méthodes. Les solutions alternatives que nous allons voir dans ce qui suit permettent de résoudre ces deux problèmes en même temps.

Les encodeurs à priorité récursifs[modifier | modifier le wikicode]

Une première solution consiste à créer un gros encodeur à base d'encodeurs plus petits.L'idée de découper le nombre d'entrée en morceaux séparés, chaque morceau étant traité par un encodeur à priorité distinct des autres. Les résultats des différents encodeurs sont ensuite combinés pour donner le résultat final. Naturellement, il est préférable d'utiliser plusieurs exemplaires d'un même encodeur, c'est à dire que pour une entrée de 256 bits, il vaut mieux utiliser soit deux décodeurs 7 vers 128, soit quatre décodeurs 6 vers 64, etc. La construction est similaire à celle vue dans le chapitre précédent, dans la section sur les encodeurs. La différence est que le OU entre les sorties des encodeurs est remplacé par un multiplexeur. Une version générale est illustrée ci-dessous. On voit que les encodeurs ont une sortie de résultat de X bits notée idx et une sortie de validité notée vld.

La sortie de validité finale se calcule en combinant les sorties de validité de chaque encodeur. La sortie est par définition à 1 tant qu'un seul encodeur a une sortie non-nulle, donc quand un seul encodeur a un bit de validité à 1. En clair, c'est un simple OU entre les bits de validité. Reste à déterminer la sortie de donnée, celle qui donne la position du 1 de poids fort. On peut dire que si l'on utilise des encodeurs avec N bits de sortie, alors les N bits de poids faible du résultat seront donnés par le premier encodeur avec une sortie non-nulle. Les résultats de chaque encodeur donnent doncles X bits de poids faible, un seul résultat devant être sélectionné. Le résultat à sélectionner est le premier à avoir un résultat non-nul, donc à avoir un bit de validité à 1. En clair, on peut déterminer quel est le bon encodeur, le bon résultat, en analysant les bits de validité. Mieux : d'après ce qui a été dit, on peut deviner que l'analyse réalisée correspond à trouver la position du premier encodeur à avoir un bit de validité à 1. En clair, c'est l'opération réalisée par un encodeur à priorité lui-même.

Tout cela permet de déterminer les N bits de poids faible, amis les autres bits, ceux de poids fort, sont encore à déterminer. Pour cela, on peut remarquer que ceux-ci sont eux-même fournit par l'encodeur à priorité qui commande le MUX.

Construction d'un encodeur à priorité à partir d'encodeur à priorité plus petits.

Notons qu'avec cette méthode, il est possible, mais pas très intuitif, de fabriquer un encodeur configurable, capable de se comporter soit comme un encodeur de type Find Highest Set, soit de type Find First Set. L'implémentation la plus simple demande de modifier le circuit qui combine les résultats pour qu'il soit configurable et puisse faire les deux opérations à la demande.

L'encodeur à priorité avec un circuit d'isolation du 1/0 de poids fort/faible[modifier | modifier le wikicode]

Une autre solution part d'un encodeur normal, auquel on ajoute un circuit qui se charge de sélectionner un seul des bits passé sur son entrée. Le circuit de gestion des priorités a pour fonction de trouver sélectionner un bit et de mettre les autres 1 à 0. Suivant le circuit de priorité considéré, le bit sélectionné est soit le 1 de poids fort, soit le 1 de poids faible, soit le 0 de poids faible, soit le 0 de poids fort. Dans certains cas, le circuit de priorité est configurable et peut trouver l'un ou l'autre suivant ce qu'on lui demande. Dans ce qui va suivre, nous allons partir du principe que l'on souhaite avoir un encodeur de type Find Highest Set, sauf si indication contraire.

Encodeur à priorité.

Implémenter le circuit de gestion des priorités varie grandement selon ce qu'on lui demande de faire. On n'implémente pas pas un circuit qui trouve le 1 de poids fort de la même manière qu'un circuit qui trouve le zéro de poids faible.

La sélection des 0/1 de poids fort : méthode arithmétique[modifier | modifier le wikicode]

Il existe une méthode pour créer un encodeur à priorité qui trouve le 0 ou 1 de poids faible. L'idée est de combiner un encodeur simple avec un circuit de gestion des priorités, sauf que le circuit de gestion des priorité trouve le 0 ou 1 de poids faible. Il est en effet possible d'isoler ceux-ci avec certaines opérations bien précises. Par exemple, l'opération suivante met à 1 le 0 de poids faible et met le reste du nombre à 0. Ce faisant, le zéro de poids faible peut être combiné avec un encodeur simple, afin de donner la position du zéro de poids faible.

Les deux opérations suivantes isolent le 1 de poids faible, ce qui veut dire tous les autres bits du nombre sont mis à 0.

Mais cette méthode demande d'utiliser des opérations arithmétiques, que l'on verra dans un chapitre ultérieur. De plus, le circuit obtenu est assez gros et pas vraiment pratique. Aussi, il n'est jamais utilisé tel quel.

La sélection des 1 de poids fort/faible : méthode par chaine de remise à zéro[modifier | modifier le wikicode]

Une autre méthode bien plus pratique découpe le circuit de gestion des priorité en petites briques de bases, reliées les unes à la suite des autres. L'idée est que les briques de base sont connectées de manière à propager un signal de mise à zéro. Si une brique détecte un 1, elle envoie un signal aux briques précédentes/suivantes, qui leur dit de mettre leur sortie à zéro. Ce faisant, une fois le premier 1 trouvé, on est certain que les autres bits précédents/suivants sont mis à zéro. Suivant les connexions des briques de base, on peut obtenir soit un encodeur qui effectue l'opération Find First Set, soit encodeur de type Find Highest Set et réciproquement. En fait, suivant que les briques soient reliées de droite à gauche ou de gauche à droite, on obtiendra l'un ou l'autre de ces deux encodeurs.

Circuit de gestion des priorités.

Chaque brique de base peut soit recopier le bit en entrée, soit le mettre à zéro. Pour décider quoi faire, elle regarde le signal d'entrée RAZ (Remise A Zéro). Si le bit RAZ vaut 1, la sortie est mise à zéro automatiquement. Dans le cas contraire, le bit passé en entrée est recopié. De plus, chaque brique de base doit fournir un signal de remise à zéro RAZ à destination de la brique suivante. Ce signal RAZ de sortie est mis à 1 dans deux cas : soit si le bit d'entrée vaut, soit quand le signal d'entrée RAZ est à 1. Si vous cherchez à la concevoir à partir d'un table de vérité, vous obtiendrez ceci :

Brique de base du circuit de gestion des priorités d'un encodeur à priorité.
Circuit de gestion des priorité - Circuit de la brique de base.

Le circuit complet d'un encodeur à priorité peut être déduit facilement à partir des raisonnements précédents. Après quelques simplifications, on peut obtenir le circuit suivant. On voit qu'on a ajouté une ligne de briques RAZ à l'encodeur 8 vers 3 vu plus haut.

Encodeur à priorités

Le défaut de cette méthode est que le circuit de gestion des priorité est assez lent. Dans le pire des cas, le signal de remise à zéro traverse toutes les briques de base, soit autant qu'il y a de bits d'entrée. Si chaque brique de base met un certain temps, le temps mis pour que le circuit de priorité fasse son travail est proportionnel au nombre de bits de l'entrée. Cela n'a l'air de rien, mais cela peut prendre un temps rédhibitoire pour les circuits de haute performance, destinés à fonctionner à haute fréquence. Pour ces circuits, on préfère que le temps de calcul soit proportionnel au logarithme du nombre de bits d'entrée, un temps proportionnel étant considéré comme trop lent, surtout pour des opérations simples comme celles étudiées ici.


Les circuits séquentiels[modifier | modifier le wikicode]

La totalité de l'électronique grand public est basée sur des circuits combinatoires auxquels on ajoute des mémoires. Pour le moment, on sait créer des circuits combinatoires, mais on ne sait pas faire des mémoires. Pourtant, on a déjà tout ce qu'il faut. Il est en effet parfaitement possible de créer des mémoires avec des portes logiques. Toutes les mémoires sont conçues à partir de circuits capables de mémoriser un ou plusieurs bits. Ces circuits sont ce qu'on appelle des bascules, ou flip-flops. Pour une question de simplicité, ce chapitre parlera des circuits capables de mémoriser un bit seulement, pas plusieurs. Nous verrons comment combiner ces bits pour former une mémoire ou des compteurs dans le chapitre suivant.

L'interface d'une bascule[modifier | modifier le wikicode]

Avant de voir comment sont fabriquées les bascules, nous allons voir quelles sont leurs entrées et leurs sorties. La raison à cela est que des bascules aux entrées-sorties similaires peuvent être construites sur des principes suffisamment différents pour qu'on les voie à part. Si on ne regarde que les entrées-sorties, on peut grosso-modo classer les bascules en quelques grands types principaux : les bascules RS, les bascules JK et les bascules D. Nous ne parlerons pas des bascules JK dans ce qui va suivre, car elles sont très peu utilisées et que nous n'en ferons pas usage dans le reste du cours.

Les bascules D[modifier | modifier le wikicode]

Interface d'une bascule D.

En premier lieu, on trouve les bascules D, les bascules les plus simples, qui ont deux entrées et deux sorties comme les bascules RS. Les deux entrées sont appelées D et E : D pour Data, E pour Enable. Le bit à mémoriser est envoyé directement sur l'entrée D. L'entrée Enable permet d'autoriser ou d'interdire les écritures dans la bascule. Ainsi, tant que cette entrée Enable reste à 0, le bit mémorisé par la bascule reste le même, peu importe ce qu'on met sur l'entrée D : il faut que l'entrée Enable passe à 1 pour que l'entrée soit recopiée dans la bascule et mémorisée.

Les bascules RS[modifier | modifier le wikicode]

Interface d'une bascule RS.

En second lieu, on trouve les bascules RS, qui possèdent deux entrées et deux sorties. La première sortie permet de lire le bit mémorisé dans la bascule RS, la seconde est simplement l'inverse de ce bit. Les deux sorties sont simplement l'inverse l'une de l'autre. Les deux entrées permettent de placer un 1 ou un 0 dans la bascule. L'entrée R permet de mettre un 1, l'entrée S permet d'y injecter un 0. Pour vous en rappeler, sachez que les entrées de la bascule ne sont nommées ainsi par hasard : R signifie Reset (qui signifie mise à zéro en anglais) et S signifie Set (qui veut dire mise à un en anglais).

Le principe de ces bascules est assez simple :

  • si on met un 1 sur l'entrée R et un 0 sur l'entrée S, la bascule mémorise un zéro ;
  • si on met un 0 sur l'entrée R et un 1 sur l'entrée S, la bascule mémorise un un ;
  • si on met un zéro sur les deux entrées, la sortie Q sera égale à la valeur mémorisée juste avant.
  • Si on met un 1 sur les deux entrées, on ne sait pas ce qui arrivera sur ses sorties. Après tout, quelle idée de mettre la bascule à un en même temps qu'on la met à zéro !
Entrée Reset Entrée Set Sortie Q
0 0 Bit mémorisé par la bascule
0 1 1
1 0 0
1 1 Interdit

Les bascules RS inversées[modifier | modifier le wikicode]

Bascule RS inversée.

Il existe aussi des bascules RS inversées, où les entrées doivent être mises à 0 pour faire ce qu'on leur demande. Ces bascules fonctionnent différemment de la bascule précédente :

  • si on met un 1 sur l'entrée R et un 0 sur l'entrée S, la bascule mémorise un 1 ;
  • si on met un 0 sur l'entrée R et un 1 sur l'entrée S, la bascule mémorise un 0 ;
  • si on met un 1 sur les deux entrées, la sortie Q sera égale à la valeur mémorisée juste avant ;
  • si on met un 0 sur les deux entrées, le résultat est indéterminé.
Entrée /R Entrée /S Sortie Q
0 0 Interdit
0 1 0
1 0 1
1 1 Bit mémorisé par la bascule

Les bascules JK[modifier | modifier le wikicode]

Bascule JK.

Les bascules JK peuvent être vues comme des bascules RS améliorées. La seule différence est ce qui se passe quand on envoie un 1 sur les entrées R et S. Sur une bascule RS, le résultat dépend de la bascule, il est indéterminé. Sur les bascules JK, le contenu de la bascule est inversée.

Entrée J Entrée K Sortie Q
0 0 Bit mémorisé par la bascule
0 1 1
1 0 0
1 1 inversion du bit mémorisé

Les bascules JK, RS et RS inversées à entrée Enable[modifier | modifier le wikicode]

Bascule RS à entrée Enable.

Il est possible de modifier les bascules JK, RS et RS inversées, pour faire permettre d' « activer » ou d' « éteindre » les entrées R et S à volonté. En faisant cela, les entrées R et S ne fonctionnent que si l'on autorise la bascule à prendre en compte ses entrées.

Pour cela, il suffit de rajouter une entrée E à notre circuit. Suivant la valeur de cette entrée, l'écriture dans la bascule sera autorisée ou interdite. Si l'entrée E vaut zéro, alors tout ce qui se passe sur les entrées RS ou JK ne fera rien : la bascule conservera le bit mémorisé, sans le changer. Par contre, si l'entrée E vaut 1, alors les entrées RS ou JK feront ce qu'il faut et la bascule fonctionnera comme une bascule RS/JK normale.

La porte C, une bascule spéciale[modifier | modifier le wikicode]

Porte-C

Enfin, nous allons voir la porte C, une bascule particulière qui sera utilisée quand nous verrons les circuits et les bus asynchrones. Elle a deux entrées A et B, comme les bascules RS et les bascules D, mais seulement une sortie. Quand les deux entrées sont identiques, la sortie de la bascule correspond à la valeur des entrées (cette valeur est mémorisée). Quand les deux entrées différent, la sortie correspond au bit mémorisé.

Entrée A Entrée B Sortie
0 0 0
0 1 Pas de changement
1 0 Pas de changement
1 1 1

L'implémentation des bascules avec des portes logiques[modifier | modifier le wikicode]

Le principe qui se cache derrière toutes ces bascules est le même. Elles sont organisées autour d'un circuit dont on boucle la sortie sur son entrée. Cela veut dire que sa sortie est connectée à une de ses entrées, les autres entrées étant utilisées pour commander la bascule. Nous allons distinguer l'entrée bouclée et la ou les entrées de commande.

Bascule - fonctionnement interne.

Le circuit doit avoir une particularité bien précise : si l'entrée de commande est à la bonne valeur (0 sur certaines bascules, 1 sur d'autres), l'entrée bouclée est recopiée sur la sortie à l'identique. On dit que le circuit a des entrées potentiellement idempotentes. Ainsi, tant que l'entrée de commande est à la bonne valeur, la bascule sera dans un état stable où la sortie et l'entrée de commande restons à la valeur mémorisée. Le circuit en question peut être une porte logique centrale, qui peut être une porte ET, OU, XOR, NAND, NOR, NXOR, ou un multiplexeur.

Bascule - boucle de rétroaction

Toujours est-il qu'un circuit séquentiel contient toujours au moins une entrée reliée sur une sortie, contrairement aux circuits combinatoires, qui ne contiennent jamais la moindre boucle !

La bascule D fabriquée avec un multiplexeur[modifier | modifier le wikicode]

Le cas le plus simple de circuit bouclé est la bascule D conçue à partir d'un multiplexeur. L'idée est très simple. Quand l'entrée Enable est à 0, la sortie du circuit est bouclée sur l'entrée : le bit mémorisé, qui était présent sur la sortie, est alors renvoyé en entrée, formant une boucle. Cette boucle reproduit en permanence le bit mémorisé. Par contre, quand l'entrée Enable vaut 1, la sortie du multiplexeur est reliée à l'entrée D. Ainsi, ce bit est alors renvoyé sur l'autre entrée : les deux entrées du multiplexeur valent le bit envoyé en entrée, mémorisant le bit dans la bascule.

Bascule D créée avec un multiplexeur.

La bascule RS fabriquée avec une porte OU et une porte ET[modifier | modifier le wikicode]

Un autre exemple est la forme la plus basique de bascule RS : la bascule RS de type ET-OU. Dans celle-ci, on trouve entre trois portes : une porte ET, une porte OU, et éventuellement une porte NON. Un exemple de porte RS de ce type est le suivant, d'autres manières de connecter le tout qui donnent le même résultat. On peut par exemple se passer d'inverseur, ou inverser l'ordre des portes logiques ET et OU. L'essentiel est la boucle indiquée en vert, qui fait que le bit de sortie est recopié sur les entrées bouclées des deux portes, l'ensemble formant une boucle qui relie la sortie à elle-même.

Bascule RS de type ET-OU.

Son fonctionnement est assez simple à expliquer. La porte ET a deux entrées, dont une est bouclée et l'autre est une entrée de commande. Les deux portes recopient leur entrée en sortie si on place ce qu'il faut sur l'entrée de commande. Par contre, toute autre valeur modifie le bit inséré dans la bascule.

  • Si on place un 0 sur l'entrée de commande de la porte OU, elle recopiera l'entrée bouclée sur sa sortie. Par contre, y mettre un 1 donnera un 1 en sortie, peu importe le contenu de l'entrée bouclée. En clair, l'entrée de commande de la porte OU sert d'entrée S à la bascule.
  • La porte ET recopie l'entrée bouclée, mais seulement si on place un 1 sur l'entrée de commande. Si on place un 0, elle aura une sortie égale à 0, peu importe l'entrée bouclée. En clair, l'entrée de commande de la porte ET est l'inverse de ce qu'on attend de l'entrée R à la bascule RS.

Pour obtenir une véritable entrée R, il est possible d'ajouter une porte NON sur l'entrée /R, sur l'entrée de la porte ET. En faisant cela, on obtient une vraie bascule RS. Mais ce n'est en rien nécessaire et il est possible d'avoir un circuit hybride, avec une entrée /R et une entrée S.

Si on essaye de concevoir le circuit, on se retrouve alors face à deux choix : ajouter ou non l’inverseur en amont de la porte ET, et l'ordre dans lequel mettre les portes ET et OU. Cela donne en tout quatre possibilités, qui donnent des circuits presque équivalents.

Avec inverseur
Porte ET avant la porte OU, avec inverseur.
Porte OU avant la porte ET, avec inverseur.
Sans inverseur
Porte OU avant la porte ET, sans inverseur.

Les deux portes ET et OU peuvent être mises dans n'importe quel ordre : soit on met la porte ET avant la porte OU, soit on fait l'inverse. La seule différence sera ce qu'il se passe quand on active les deux entrées à la fois. Si la porte ET est située après la porte OU, l'entrée Reset sera prioritaire sur l'entrée Set quand elles sont toutes les deux à 1. Et inversement, si la porte OU est située après, ce sera le signal Set qui sera prioritaire. Voici ci-dessous les tables de vérité correspondantes pour chaque circuit.

Circuit avec la porte ET avant la porte OU
Entrée Reset Entrée Set Sortie Q Circuit
0 0 Bit mémorisé par la bascule Porte OU avant la porte ET.
1 0 0
X (0 ou 1) 1 1
Circuit avec la porte OU avant la porte ET
Entrée Reset Entrée Set Sortie Q Circuit
0 0 Bit mémorisé par la bascule Porte OU avant la porte ET.
0 1 0
1 X (0 ou 1) 1

Une autre manière de voir les choses est que ce circuit possède deux sorties Q éaquivalentes, situées aux deux points entre les portes OU et ET. Cette façon de voir les choses sera très utile dans ce qui va suivre.

Les bascules RS à NOR et à NAND[modifier | modifier le wikicode]

Le circuit précédent a bien une sortie Q, mais pas de sortie /Q. Pour la rajouter, il suffit simplement d'ajouter une porte NON sur la sortie Q. Mais faire ainsi ne permet pas de profiter de certaines simplifications bien appréciables. Il est en effet possible de se débarrasser des deux portes NON, celle en amont de la porte ET, et de celle sur la sortie /Q. Pour cela, nous allons procéder d'une autre manière. Au lieu d'ajouter une seule porte NON, nous allons ajouter deux portes, en amont de la porte OU. En faisant, le circuit devient celui-ci :

Bascule RS à NOR - conception à partir d'une bascule ET-OU - 1

On peut alors regrouper des portes logiques consécutives. Premièrement, on peut regrouper la porte OU avec la porte NON immédiatement à sa suite. Mais on peut aussi regrouper la porte ET et les deux portes NON restantes. En effet, nous avons vu dans le chapitre sur les circuits combinatoires que cette combinaison de portes est équivalente à une porte NOR. Le circuit devient donc :

Bascule RS à NOR - conception à partir d'une bascule ET-OU - 2

Le résultat est ce qu'on appelle une bascule RS à NOR, qui tire son nom du fait qu'elle est fabriquée exclusivement avec des portes logiques NOR. En réorganisant le circuit, on trouve ceci :

Circuit d'une bascule RS à NOR.

Il est possible de faire la même manipulation, mais cette fois-ci sur une bascule RS inversée, de type ET-OU encore une fois. La bascule RS inversée est identique à la bascule ET-OU précédente, si ce n'est que la porte NON est placée sur l'entrée R et non sur l'entrée S. En clair, elle est sur une entrée de la porte OU et non sur la porte ET. Le résultat est une bascule RS à NAND, qui est une bascule inversée à deux sorties (Q et /Q), composée intégralement de portes NAND.

Circuit d'une bascule RS à NAND.

La porte C[modifier | modifier le wikicode]

La porte C est une bascule qui peut être réalisée d'un grand nombre de manière différentes. La plus simple, basée sur des portes logiques, est celle indiquée dans le schéma suivant.

Porte C fabriquée avec des portes logiques.

Il existe aussi une myriade de manières de construire des portes C avec des transistors. LA plus simple est celle illustrée ci-dessous.

Porte C fabriquée avec des transistors et deux inverseurs.

Les bascules peuvent se fabriquer à partir d'autres bascules[modifier | modifier le wikicode]

Il y a quelques chapitres, nous avons vu qu'il est possible de créer une porte logique en combinant d'autres portes logiques. Et bien sachez qu'il est possible de faire la même chose pour des bascules. On peut par exemple fabriquer une bascule RS à partir d'une bascule D, et réciproquement. Ou encore, on peut fabriquer une bascule D à partir d'une bascule JK, et inversement. Les possibilités sont nombreuses. Et pour cela, il suffit juste d'ajouter un circuit combinatoire qui traduit les entrées de la bascule voulue vers les entrées de la bascule utilisée.

Les bascules JK conçues à partir de bascules RS[modifier | modifier le wikicode]

Il est possible de construire une bascule JK à partir d'une bascule RS. Ce qui n'est pas étonnant, vu que les bascules RS et JK sont très ressemblantes. Il suffit d'ajouter un circuit qui déduise quoi mettre sur les entrées R et S suivant la valeur sur les entrées J et K. Le circuit en question est composé de deux portes ET, une par entrée.

Bascule JK obtenue à partir d'une bascule RS.

Il est possible de faire la même chose avec une bascule RS à entrée Enable, qui donne une bascule JK à entrée Enable.

Bascule JK obtenue à partir d'une bascule RS à entrée Enable.

Les bascules RS à entrée Enable conçues à partir de bascules RS[modifier | modifier le wikicode]

Pour fabriquer une bascule RS à entrée Enable, rien de plus simple : il suffit d'ajouter un circuit avant les entrées R et S, qui inactivera celles-ci si l'entrée E vaut zéro. La table de vérité de ce circuit est identique à celle d'une simple porte ET. Le circuit obtenu est donc celui-ci :

Circuit d'une bascule RS à entrée Enable.

Les bascules D conçues à partir de bascules RS à entrée Enable[modifier | modifier le wikicode]

On peut construire une bascule D à partir d'une simple bascule RS. Il suffit d'ajouter un circuit qui déduise quoi mettre sur les entrées R et S suivant la valeur sur D.

Bascule D fabriquée avec une bascule RS, à NOR.

Mais en réfléchissant un peu, on se rend compte qu'il est préférable d'utiliser une bascule RS à entrée Enable. En effet, l'entrée Enable de la bascule D et de la bascule RS sont la même, elle ont exactement le même comportement et la même utilité. Dans ce cas, il suffit de prendre une bascule RS à entrée Enable et d'ajouter un circuit qui convertit l'entrée D en Entrées R et S. On peut alors remarquer que l'entrée R est toujours égale à l'inverse de D, alors que S est toujours strictement égale à D. Il suffit d'ajouter une porte NON avant l'entrée R d'une bascule RS à entrée Enable, pour obtenir une bascule D.

Si on utilise des bascules RS à NOR, on obtient le circuit suivant.

Bascule D à NAND.

On peut aussi faire la même chose, mais avec la bascule RS à NAND.

Bascule D à NAND.


Les bascules sont rarement utilisées seules. Elles sont combinées avec des circuits combinatoires pour former des circuits qui possèdent une capacité de mémorisation, appelés circuits séquentiels. L'ensemble des informations mémorisées dans un circuit séquentiel, le contenu de ses bascules, forme ce qu'on appelle l'état du circuit, aussi appelé la mémoire du circuit séquentiel. Un circuit séquentiel peut ainsi être découpé en deux morceaux : des bascules qui stockent l'état du circuit, et des circuits combinatoires pour mettre à jour l'état du circuit et sa sortie. Suivant la méthode utilisée pour déterminer la sortie, on peut classer les circuits séquentiels en deux catégories :

  • les automates de Moore, où la sortie ne dépend que de l'état mémorisé ;
  • et les automates de Mealy, où la sortie dépend de l'état du circuit et de ses entrées.
Ces derniers ont tendance à utiliser moins de portes logiques que les automates de Moore.
Automate de Moore et de Mealy

Concevoir des circuits séquentiels demande d'utiliser un formalisme assez complexe et des outils comme des machines à état finis (finite state machine). Mais nous ne parlerons pas de cela dans ce cours, car nous n'aurons heureusement pas à les utiliser.

La majorité des circuits séquentiels possèdent plusieurs bascules, dont certaines doivent être synchronisées entre elles. Sauf qu'un léger détail vient mettre son grain de sel : tous les circuits combinatoires ne vont pas à la même vitesse ! Si on change l'entrée d'un circuit combinatoire, cela se répercutera sur ses sorties. Mais toutes les sorties ne sont pas mises en même temps et certaines sorties seront mises à jour avant les autres ! Cela ne pose pas de problèmes avec un circuit combinatoire, mais ce n'est pas le cas si une boucle est impliquée, comme dans les circuits séquentiels. Si les sorties sont renvoyées sur les entrées, alors le résultat sur l'entrée sera un mix entre certaines sorties en avance et certaines sorties non-mises à jour. Le circuit combinatoire donnera alors un résultat erroné en sortie. Certes, la présence de l'entrée Enable permet de limiter ce problème, mais rien ne garantit qu'elle soit mise à jour au bon moment. En conséquence, les bascules d'un composant ne sont pas mis à jour en même temps, ce qui pose quelques problèmes relativement fâcheux si aucune mesure n'est prise.

Le temps de propagation[modifier | modifier le wikicode]

Pour commencer, il nous faut expliquer pourquoi tous les circuits combinatoires ne vont pas à la même vitesse. Tout circuit, quel qu'il soit, va mettre un petit peu de temps avant de réagir. Ce temps mis par le circuit pour propager un changement sur les entrées vers la sortie s'appelle le temps de propagation. Pour faire simple, c'est le temps que met un circuit à faire ce qu'on lui demande : plus ce temps de propagation est élevé, plus le circuit est lent. Ce temps de propagation dépend de pas mal de paramètres, aussi je ne vais citer que les principaux.

Le temps de propagation des portes logiques[modifier | modifier le wikicode]

Une porte logique n'est pas un système parfait et reste soumis aux lois de la physique. Notamment, il n'a pas une évolution instantanée et met toujours un petit peu de temps avant de changer d'état. Quand un bit à l'entrée d'une porte logique change, elle met du temps avant de changer sa sortie. Ce temps de réaction pour propager un changement fait sur les entrées vers la sortie s'appelle le temps de propagation de la porte logique. Pour être plus précis, il existe deux temps de propagation : un temps pour passer la sortie de 0 à 1, et un temps pour la passer de 1 à 0. Les électroniciens utilisent souvent la moyenne entre ces deux temps de propagation, et la nomment le retard de propagation, noté .

Temps de propagation d'une porte logique.

Le chemin critique[modifier | modifier le wikicode]

Délai de propagation dans un circuit simple.

Si le temps de propagation de chaque porte logique a son importance, il faut aussi tenir compte de la manière dont elles sont reliées. La relation entre "temps de propagation d'un circuit" et "temps de propagation de ses portes" n'est pas simple. Deux paramètres vont venir jouer les troubles-fêtes : le chemin critique et la sortance des portes logiques. Commençons par voir le chemin critique, qui n'est autre que le nombre maximal de portes logiques entre une entrée et une sortie de notre circuit. Pour donner un exemple, nous allons prendre le schéma ci-contre. Pour ce circuit, le chemin critique est dessiné en rouge. En suivant ce chemin, on va traverser trois portes logiques, contre deux ou une dans les autres chemins.

Le temps de propagation total, lié au chemin critique, se calcule à partie de plusieurs paramètres. Premièrement, il faut déterminer quel est le temps de propagation pour chaque porte logique du circuit. En effet, chaque porte logique met un certain temps avant de fournir son résultat en sortie : quand les entrées sont modifiées, il faut un peu de temps pour que sa sortie change. Ensuite, pour chaque porte, il faut ajouter le temps de propagation des portes qui précédent. Si plusieurs portes sont reliées sur les entrées, on prend le temps le plus élevé. Enfin, il faut identifier le chemin critique, le plus long : le temps de propagation de ce chemin est le temps qui donne le tempo maximal du circuit.

Temps de propagation par porte logique.
Temps de propagation pour chaque chemin.
Identification du chemin critique.

La sortance des portes logiques[modifier | modifier le wikicode]

Passons maintenant au second paramètre lié à l'interconnexion entre portes logiques : la sortance. Dans les circuits complexes, il n'est pas rare que la sortie d'une porte logique soit reliée à plusieurs entrées (d'autre portes logiques). Le nombre d'entrées connectées à une sortie est appelé la sortance de la sortie. Il se trouve que plus on connecte de portes logiques sur une sortie, (plus sa sortance est élevée), plus il faudra du temps pour que la tension à l'entrée de ces portes passe de 1 à 0 (ou inversement). La raison en est que la porte logique fournit un courant fixe sur sa sortie, qui charge les entrées en tension électrique. Un courant positif assez fort charge les entrées à 1, alors qu'un courant nul ne charge pas les entrées qui retombent à 0. Avec plusieurs entrées, la répartition est approximativement équitable et chaque entrée reçoit seulement une partie du courant de sortie. Elles mettent plus de temps à se remplir de charges, ce qui fait que la tension met plus de temps à monter jusqu'à 1.

Influence de la sortance d'un circuit sur sa fréquence-période

Le temps de latence des fils[modifier | modifier le wikicode]

Enfin, il faut tenir compte du temps de propagation dans les fils, celui mis par notre tension pour se propager dans les fils qui relient les portes logiques entre elles. Ce temps perdu dans les fils devient de plus en plus important au cours du temps, les transistors et portes logiques devenant de plus en plus rapides à force des les miniaturiser. Par exemple, si vous comptez créer un circuit avec des entrées de 256 à 512 bits, il vaut mieux le modifier pour minimiser le temps perdu dans les interconnexions que de diminuer le chemin critique.

Les circuits synchrones et asynchrones[modifier | modifier le wikicode]

Sur les circuits purement combinatoires, le temps de propagation n'est que rarement un souci, à moins de rencontrer des soucis de métastabilité assez compliqués. Par contre, le temps de propagation doit être pris en compte quand on crée un circuit séquentiel : sans ça on ne sait pas quand mettre à jour les bascules du circuit. Si on le fait trop tôt, le circuit combinatoire peut sauter des états : il se peut parfaitement qu'on change le bit placé sur l'entrée avant qu'il ne soit mémorisé. De plus, les différents circuits d'un composant électronique n'ont pas tous le même temps de propagation, et ceux-ci vont fonctionner à des vitesses différentes. Si l'on ne fait rien, on peut se retrouver avec des dysfonctionnements : par exemple, un circuit lent peut rater deux ou trois nombres envoyés par un composant un peu trop rapide.

Pour éviter les ennuis dus à l'existence de ce temps de propagation, il existe deux grandes solutions, qui permettent de faire la différence entre circuits asynchrones et synchrones. Les circuits asynchrones préviennent les bascules quand ils veulent la mettre à jour. Quand le circuit combinatoire et les bascules sont tous les deux prêts, on autorise l'écriture dans les bascules. Mais ce n'est pas cette solution qui est utilisée dans les circuits de nos ordinateurs, qui sont des circuits synchrones. Dans les circuits synchrones, les bascules sont mises à jour en même temps.

Les circuits synchrones[modifier | modifier le wikicode]

Les circuits synchrones mettent à jour leurs bascules à intervalles réguliers. La durée entre deux mises à jour est constante et doit être plus grande que le temps de propagation le plus long du circuit : on se cale donc sur le circuit combinatoire le plus lent. Les concepteurs d'un circuit doivent estimer le pire temps de propagation possible pour le circuit et ajouter une marge de sûreté. Pour mettre à jour les circuits à intervalles réguliers, le signal d'autorisation d'écriture est une tension qui varie de façon cyclique : on parle alors de signal d'horloge. Le temps que met la tension pour effectuer un cycle est ce qu'on appelle la période. Le nombre de périodes par seconde est appelé la fréquence. Elle se mesure en hertz. On voit sur ce schéma que la tension ne peut pas varier instantanément : elle met un certain temps pour passer de 0 à 1 et de 1 à 0. On appelle cela un front. La passage de 0 à 1 est appelé un front montant et le passage de 1 à 0 un front descendant.

Fréquence et période.

En faisant cela, le circuit mettra ses sorties à jour lors d'un front montant (ou descendant) sur son entrée d'horloge. Entre deux fronts montants (ou descendants), le circuit ne réagit pas aux variations des entrées. Rappelons que seuls les circuits séquentiels doivent être synchronisés ainsi, les circuits combinatoires étant épargnés par les problématiques de synchronisation. Pour que les circuits séquentiels soient cadencés par une horloge, les bascules du circuit sont modifiées de manière à réagir aux fronts montants et/ou aux fronts descendants, ce qui fait que la mise à jour de l'état interne du circuit est synchronisée sur l'horloge. Évidemment, l’horloge est envoyée au circuit via une entrée spéciale : l'entrée d'horloge. L'horloge est ensuite distribuée à l'intérieur du composant, jusqu'aux bascules, par un ensemble de connexions qui relient l'entrée d'horloge aux bascules.

Circuit séquentiel synchrone.

En théorie, plus un composant utilise une fréquence élevée, plus il est rapide. C'est assez intuitif : plus un composant peut changer d'état un grand nombre de fois par seconde, plus, il peut faire de calculs, et plus il est performant. Cela n'est toutefois pas un élément déterminant : un processeur de 4 gigahertz peut être bien plus rapide qu'un processeur de 200 gigahertz, pour des raisons techniques qu'on verra plus tard dans ce cours. Mais dans les grandes lignes, une hausse de la fréquence signifie une performances plus élevée. Les processeurs et mémoires ont vu leur fréquence augmenter au fil du temps, ce qui explique en partie pourquoi leur performance a augmenté au cours du temps. Pour donner un ordre de grandeur, le premier microprocesseur avait une fréquence de 740 kilohertz (740 000 hertz), alors que les processeurs actuels montent jusqu'à plusieurs gigahertz : plusieurs milliards de fronts par secondes ! Mais cela a eu pour défaut d'augmenter la consommation d'énergie des processeurs, et la chaleur qu'ils émettent. Car, comme on le verra dans plusieurs chapitres, un composant chauffe d'autant plus qu'il a une fréquence élevée. les premiers processeurs étaient refroidis par un simple radiateur, alors que les processeurs modernes demandent un radiateur, un ventilateur et une pâte thermique de qualité pour dissiper leur chaleur. Pour limiter la catastrophe, les fabricants de processeurs ont inventé diverses techniques permettant de diminuer la consommation énergétique et la dissipation thermique d'un processeur, mais cela est un sujet pour un autre chapitre. Toujours est-il que l'augmentation en fréquence des processeurs modernes est de plus en plus contrainte par la dissipation de chaleur et la consommation d'énergie.

Dans un ordinateur moderne, chaque composant a sa propre horloge, qui peut être plus ou moins rapide que les autres. Par exemple, le processeur fonctionne avec une horloge différente de l'horloge de la mémoire RAM ou des périphériques. La présence de plusieurs horloges vient du fait que certains composants sont plus lents que d'autres. Plutôt que de caler tous les composants d'un ordinateur sur le plus lent en utilisant une seule horloge, il vaut mieux utiliser une horloge différente pour chaque composant : les mises à jour des circuits sont synchronisées à l'intérieur d'un composant (dans un processeur, ou une mémoire), alors que les composants eux-mêmes synchronisent leurs communications avec d'autres mécanismes. Ces multiples signaux d'horloge dérivent d'une horloge de base qui est « transformée » en plusieurs horloges, grâce à des montages électroniques spécialisés (des PLL ou des montages à portes logiques un peu particuliers).

Les circuits asynchrones[modifier | modifier le wikicode]

Les circuits asynchrones n'utilisent pas d'horloge pour synchroniser leurs composants/sous-circuits. L’asynchrone permet à deux circuits/composants de se synchroniser, l'un des deux étant un émetteur, l'autre étant un récepteur. Pour se synchroniser, l’émetteur indique au récepteur qu'il lui a envoyé une donnée. Le récepteur réceptionne alors la donnée et indique qu'il a pris en compte les données envoyées. Cette synchronisation se fait grâce à des fils spécialisés du bus de commande, qui transmettent des bits particuliers.

Communication asynchrone

La transmission des données/requêtes peut se faire de deux manières différentes : la première utilise un signal de requête qui indique que de nouvelles données sont disponibles, la seconde n'envoie que des données dupliquées. Ces deux méthodes portent les noms de Bundled Encoding et de Multi-Rail Encoding. La première est la plus intuitive, car elle correspond à l'encodage des bits que nous utilisons depuis le début de ce cours, alors que la seconde est inédite à ce point du cours.

Le Bundled Encoding[modifier | modifier le wikicode]

Avec la méthode du Bundled Encoding, aussi appelée codage simple-track, la synchronisation utilise deux fils : REQ et ACK (des mots anglais request =demande et acknowledg(e)ment =accusé de réception). Le fil REQ indique au récepteur que l'émetteur lui a envoyé une donnée, tandis que le fil ACK indique que le récepteur a fini son travail et a accepté la donnée entrante. Plus rarement, un seul fil est utilisé à la fois pour la requête et l'acquittement, ce qui limite le nombre de fils.

Signaux de commande d'un bus asynchrone
Protocoles de transmission asynchrone à 2 et 4 phases. les chiffres correspondent au nombre de fronts de la transmission.

Si l'on utilise deux fils séparés, le codage des requêtes et acquittements peut se faire de plusieurs manières. Deux d'entre elles sont très utilisées et sont souvent introduites dans les cours sur les circuits asynchrones. Elles portent les noms de protocole à 4 phases et protocole à 2 phases. Elles ne sont cependant pas les seules et beaucoup de protocoles asynchrones utilisent des méthodes alternatives, mais ces deux méthodes sont très pédagogiques, d'où le fait qu'on les introduise ici.

  • Le tout premier est paradoxalement le plus intuitif. Avec lui, les requêtes d'acquittement sont codées par un bit et/ou un front montant. Les signaux REQ/ACK sont mis à 1 en cas de requête/acquittement et repassent 0 s'il n'y en a pas. Le protocole assure que les deux signaux sont remis à zéro à la fin d'une transmission, ce qui est très important pour le fonctionnement du protocole. Lorsque l'émetteur envoie une donnée au récepteur, il fait passer le fil REQ de 0 à 1. Cela dit au récepteur : « attention, j'ai besoin que tu me fasses quelque chose ». Le récepteur va réagit au front montant et/ou au bit REQ et fait ce qu'on lui a demande. Une fois qu'il a terminé, il positionne le fil ACK à 1 histoire de dire : j'ai terminé ! les deux signaux reviennent ensuite à 0, avant de pouvoir démarrer une nouvelle transaction.
  • Avec le protocole à deux phase, tout changement des signaux REQ et ACK indique une nouvelle transmission, peu importe que le signal passe de 0 à 1 ou de 1 à 0. En clair, les signaux sont codés par des fronts montants et descendants, et non par le niveau des bits ou par un front unique. Il n'y a donc pas de retour à 0 des signaux REQ et ACK à la fin d'une transmission. Une transmission a lieu entre deux fronts de même nature, deux fronts montants ou deux fronts descendants.

Le tout est illustré ci-contre. On voit que le protocole à 4 phases demande 4 fronts pour une transmission : un front montant sur REQ pour le mettre à 1, un autre sur ACk pour indiquer l'acquittement, et deux fronts descendants pour remettre les deux signaux à 0. Avec le protocole à 2 phases, on n'a que deux fronts : deux fronts montants pour la première transmission, deux fronts descendants pour la suivante. D'où le nom des deux protocoles : 4 et 2 phases.

Quand un seul fil est utilisé pour l'acquittement, un 1 sur ce fil signifie qu'une requête est en attente (le second composant est occupé), tandis qu'un 0 indique que le second composant est libre. Ce fil est manipulé aussi bien par l'émetteur que par le récepteur. L'émetteur met ce fil à 1 pour envoyer une donnée, le récepteur le remet à 0 une fois qu'il est libre.

Le Multi-Rail Encoding[modifier | modifier le wikicode]

Les circuits asynchrones précédents, qui le Bundled Encoding, utilisent un fil par bit de données et un fil pour le signal REQ. Mais cette manière de faire a quelques défauts, le principal étant la sensibilité aux délais. Pour faire simple, la conception du circuit doit prendre en compte le temps de propagation dans les fils : il faut garantir que le signal REQ arrive au second circuit après les données, ce qui est loin d'être trivial. Pour éviter cela, d'autres circuits utilisent plusieurs fils pour coder un seul bit, ce qui donne un codage multiple-rails.

Le cas le plus simple utilise deux fils par bit, ce qui lui vaut le nom de codage dual-rail.

Dual-rail protocol

Il en existe plusieurs sous-types, qui différent selon ce qu'on envoie sur les deux fils qui codent un bit.

  • Certains circuits asynchrones utilisent un signal REQ par bit, d'où la présence de deux fils par bit : un pour le bit de données, et l'autre pour le signal REQ.
  • D'autres codent un bit de données sur deux bits, certaines valeurs indiquant un bit invalide.
Protocole 3 états

Les bascules synchrones[modifier | modifier le wikicode]

Utiliser une horloge demande cependant d'adapter les circuits vus précédemment, les bascules devant être modifiées. En effet, les bascules précédentes sont mises à jour quand un signal d'autorisation est mis à 1. Mais avec un signal d'horloge, les bascules doivent être mises à jour lors d'un front, montant ou descendant, peu importe. Pour cela, les bascules ont une entrée d'autorisation d'écriture modifiée, qui réagit au signal d'horloge. Les bascules commandées par une horloge sont appelées des bascules synchrones.

Les bascules synchrones peuvent mettre à jour leur contenu soit lors d'un front montant, soit d'un front descendant, soit les deux, soit lorsque la tension d'horloge est à 1. Suivant le cas, le symbole utilisé pour représenter l'entrée d'horloge est différent, comme illustré ci-dessous.

Symboles des bascules synchrones.
Notons qu'en anglais, le terme bascule se dit flip-flop ou latch. De nos jours, le terme latch étant utilisé pour les bascules non-synchrones, alors que le terme flip-flop est utilisé pour désigner les bascules synchrones.

Les types de bascules synchrones[modifier | modifier le wikicode]

Il existe plusieurs types de bascules synchrones, qu'on peut classer en fonction de leurs entrées-sorties.

Symbole d'une bascule D synchrone.

La plus simple est la bascule D synchrone est une bascule D modifiée de manière à mettre à jour son contenu sur un front (montant). Celle-ci possède deux entrées : une entrée D sur laquelle on envoie la donnée à mémoriser (entrée d'écriture), et une autre pour l'horloge. Elle contient entre une et deux sorties : une pour la donnée mémorisée (sortie de lecture) et éventuellement une autre pour son opposé. Son fonctionnement est simple : son contenu est mis à jour avec ce qu'il y a sur l'entrée D, mais seulement lors d'un front (montant ou descendant suivant la bascule). Plus rares, certaines bascules D contiennent des entrées R et S pour les mettre à zéro ou à 1. La plupart des bascules D ont une entrée R pour les remettre à zéro, tandis que l'entrée S est absente, celle-ci étant peu utile.

Entrée CLK Entrée D Sortie Q
Front montant (ou descendant, suivant la bascule) 0 0
1 1
Pas de front montant 0 ou 1 Pas de changement
Bascule SR synchrone.

Il existe aussi des versions synchrones des bascules RS à entrée Enable. Sur celles-ci, l'entrée Enable est juste remplacée par une entrée pour l’horloge. On les appelle des bascules RS synchrones.

Entrée CLK Entrée R Entrée S Sortie Q
Front montant (ou descendant, suivant la bascule) 0 0 Pas de changement
0 1 Mise à 1
1 0 Mise à 0
1 1 Indéterminé.
Pas de front montant 0 ou 1 0 ou 1 Pas de changement
Bascule synchrone JK.

Les bascules JK ont aussi leur version synchrones, les bascules JK synchrones.

Entrée CLK Entrée R Entrée S Sortie Q
Front montant (ou descendant, suivant la bascule) 0 0 Pas de changement
0 1 Mise à 1
1 0 Mise à 0
1 1 Inversion du bit mémorisé
Pas de front montant 0 ou 1 0 ou 1 Pas de changement
Bascule T.

La bascule T est une bascule qui n'existe que comme bascule synchrone. Elle possède deux entrées : une entrée d'horloge et une entrée nommée T. Cette bascule inverse son contenu quand l'entrée T est à 1, mais à condition qu'il y ait un front sur le signal d'horloge. En clair, l'inversion a lieu quand il y a à la fois un front et un 1 sur l'entrée T. Si l'entrée T est maintenue à 1 pendant longtemps, cette bascule inverse sont contenu à chaque cycle d'horloge. À ce propos, l'entrée T tire son nom du mot anglais Toggle, qui veut dite inverser.

Entrée CLK Entrée T Sortie Q
Front montant (ou descendant, suivant la bascule) 0 Pas de changement
1 Inversion du contenu de la bascule
Pas de front montant 0 ou 1 Pas de changement
Chronogramme qui montre le fonctionnement d'une bascule T. Le chronogramme montre comment évolue la sortie Q en fonction du temps, en fonction de l'entrée d'horloge C et de l'entrée T.
Cette bascule est utilisée pour fabriquer des compteurs, des circuits dans lesquels des bits doivent régulièrement être inversées.
Bascule T simplifiée.

La bascule T simplifiée est une bascule T dont l'entrée T a été retirée. Cette bascule change d'état à chaque cycle d'horloge, sans besoin d'autorisation de la part d'une entrée T.

Entrée CLK Sortie Q
Front montant (ou descendant, suivant la bascule) Inversion du bit mémorisé
Pas de front montant Pas de changement

L'intérieur d'une bascule synchrone[modifier | modifier le wikicode]

Pour fabriquer une bascule synchrone, les solutions sont nombreuses et dépendent de si l'on parle d'une bascule D ou d'une bascule RS. Néanmoins, une méthode assez courante, et assez simple, est de partir d'une bascule RS non-synchrone, puis de la modifier pour la rendre synchrone. Les bascules les plus indiquées pour cela sont les bascules avec une entrée Enable : il suffit de transformer l’entrée Enable en entrée d'horloge. Évidemment, cela demande de faire quelques modifications. Il ne suffit pas d'envoyer le signal d'horloge sur l'entrée Enable pour que cela marche.

La méthode la plus simple consiste à enchaîner deux bascules asynchrones RS ou D l'une à la suite de l'autre, sous réserve que leurs deux entrées Enable subissent un petit traitement. Prenons l'exemple une bascule RS à entrée Enable. À elle seule, elle ne forme pas une bascule synchrone. Par contre, le circuit fonctionne si on enchaîne deux bascules RS à entrée Enable, et que les deux entrées Enable sont connectées à l'entrée d'horloge. De plus, l'entrée Enable de la seconde bascule est précédée d'une porte NON. Avec cette méthode, la première bascule est mise à jour quand l’horloge est à 0, la seconde étant mise à jour avec le contenu de la première quand l'horloge est à 1. Dans ces conditions, la sortie finale de la bascule est mise à jour après un front montant.

Bascule R synchrone basée sur des bascules RS non-synchrones.

On peut faire exactement la même chose pour créer une bascule D synchrone, à savoir placer deux bascules D l'une à la suite de l'autre avec la seconde ayant son entrée Enable inversée. Avec cette méthode, la première bascule est mise à jour quand l’horloge est à 0, la seconde étant mise à jour avec le contenu de la première quand l'horloge est à 1. Dans ces conditions, la sortie finale de la bascule est mise à jour après un front montant.

Negative-edge triggered master slave D flip-flop
Bascule D cadencée par une horloge.

Une autre méthode associe trois bascules RS normales, les deux premières formant une couche d'entrée qui commande la troisième bascule. Ces deux bascules d'entrée vont en quelque sorte traiter le signal à envoyer à la troisième bascule. Quand le signal d'horloge est à 0, les deux bascules d'entrée fournissent un 1 sur leur sortie : la troisième bascule reste donc dans son état précédent, sans aucune modification. Quand l'horloge passe à 1 (front montant), seule une des deux bascules va fournir un 1 en sortie, l'autre voyant sa sortie passer à 0. La bascule en question dépend de la valeur de D : un 0 sur l'entrée D force l'entrée R de la troisième bascule, un 1 forçant l'entrée S. Dit autrement, le contenu de la troisième bascule est mis à jour. Quand l'entrée d'horloge passe à 1, les bascules se figent toutes dans leur état précédent. Ainsi, la troisième bascule reste commandée par les deux bascules précédentes, qui maintiennent son contenu (les entrées R et S restent à leur valeur obtenue lors du front montant).

Il est aussi possible de créer une bascule D synchrone avec des transistors. Nous n'étudierons pas ce cas, qui est franchement compliqué et relève plus de l'état de l'art que d’autre chose. Tout au plus, nous pouvons nous contenter de vous donner le circuit obtenu, pour le plaisir de vos yeux.

True single-phase edge-triggered flip-flop with reset

Fabriquer des bascules synchrones à partir d'autres bascules synchrones[modifier | modifier le wikicode]

Une bascule JK synchrone se fabrique facilement à partir d'une bascule RS synchrones, ce qui n'est pas étonnant quand on sait que leur comportement est presque identique, la seule différence étant ce qui se passe quand les entrées RS sont toutes les deux à 1. Il suffit, comme pour une bascule JK asynchrone, d'ajouter quelques circuits pour convertir les entrées JK en entrées RS.

Bascule JK synchrone, conçue à partir d'une bascule RS synchrone.

La bascule D synchrone peut se fabriquer partir d'une bascule JK ou RS synchrone. Il suffit alors d'ajouter un circuit combinatoire pour traduire les entrées D et E en entrées RS ou JK.

Bascule D fabriquée avec une bascule JK synchrone. Bascule D fabriquée avec une bascule RS synchrone.

La bascule T simplifiée est la version la plus simple de bascule T, celle qui n'a pas d'entrée T et se contente d'inverser son contenu à chaque cycle d'horloge. La fabriquer est assez simple : il suffit de prendre une bascule D synchrone et de relier sa sortie /Q à son entrée D. On peut aussi faire la même chose avec une bascule JK synchrone ou une bascule RS synchrone.

Bascule T simplifiée fabriquée avec une bascule D synchrone. Bascule T simplifiée fabriquée avec une bascule RS synchrone. Bascule T simplifiée fabriquée avec une bascule JK synchrone.

Une bascule T normale peut s’implémenter une bascule T simplifiée, une bascule RS synchrone ou une bascule JK synchrone. Pour le circuit basé sur une bascule T simplifiée, l'idée est de faire un ET entre l'entrée T et le signal d'horloge, ce ET garantissant que le signal d’horloge est mis à 0 si l'entrée T est à zéro.

Bascule T simplifiée, fabriquée avec une bascule T simplifiée. Bascule T simplifiée, fabriquée avec une bascule RS synchrone. Bascule T fabriquée avec une bascule JK.

La distribution de l'horloge dans un circuit complexe[modifier | modifier le wikicode]

L’horloge est distribuée aux bascules et autres circuits à travers un réseau de connexions électriques qu'on appelle l'arbre d'horloge. L'arbre d'horloge le plus simple, illustré dans la première image ci-dessous, relie directement l'horloge à tous les composants à cadencer.

Arbre d’horloge simple.
Arbre d'horloge avec des buffers (les triangles sur le schémas).

Les défauts inhérents aux arbres d’horloge[modifier | modifier le wikicode]

Un problème avec cette approche est la sortance de l'horloge. Cette dernière est connectée à trop de composants, ce qui la ralentit. Pour éviter tout problème, on peut ajouter des buffers, de petits répéteurs de signal. S'ils sont bien placés, ils réduisent la sortance nécessaire et empêchent que le signal de l'horloge s'atténue en parcourant les fils.

Un autre problème très fréquent sur les circuits à haute performance est qu'une bonne partie de la consommation d'énergie a lieu dans l'arbre d'horloge. Ce n'était pas le cas avec les anciens transistors dits bipolaires, ou les anciennes technologies de fabrication de circuits imprimés, mais c'est devenu un problème depuis l'arrivée des transistors CMOS. Nous en reparlerons dans le chapitre sur la consommation énergétique des ordinateurs, mais il est intéressant de mettre quelques chiffres sur ce phénomène. Entre 20 à 30% de la consommation énergétique des processeurs modernes a lieu dans l'arbre d'horloge. En comparaison, les circuits asynchrones se passent de cette consommation d'énergie, sans compter que leurs mécanismes de synchronisations sont moins gourmands en courant. Ils sont donc beaucoup plus économes en énergie et chauffent moins. Malheureusement, leur difficulté de conception les rend peu courants.

Le décalage d’horloge (clock skew)[modifier | modifier le wikicode]

Clock skew lié aux temps de transmission dans les fils.

Un problème courant sur les circuits à haute fréquence est que les fils qui transmettent l’horloge ont chacun des délais de transmission différents. La raison principale à cela est qu'ils n'ont pas la même longueur, ce qui fait que l'électricité met plus de temps à traverser les quelques micromètres de différence entre fils. En conséquence, les composants sont temporellement décalés les uns d'avec les autres, même si ce n'est que légèrement. Ce phénomène est appelé le décalage d'horloge, traduction du terme clock skew utilisé en langue anglaise. Il ne pose pas de problème à faible fréquence et/ou pour des fils assez courts, mais c'est autre chose pour les circuits à haute fréquence. Pour éviter les effets néfastes du clock skew sur les circuits haute-fréquence, on doit concevoir l'arbre d'horloge avec des techniques assez complexes.

Par exemple, on peut jouer sur la forme de l'arbre d'horloge. Dans les schémas du dessus, l'arbre d'horloge part d'un côté du processeur, de là où se trouve la broche pour l'horloge. En faisant cela, un côté du processeur recevra l'horloge avant l'autre, entraînant l'apparition d'un délai entre la gauche du processeur et sa droite. Pour éviter cela, on peut faire partir l'horloge du centre du processeur. Le fil de l'horloge part de la broche d'horloge, va jusqu’au centre du processeur, puis se ramifie de plus en plus en direction des composants. En faisant cela, on garantit que les délais sont équilibrés entre les deux côtés du processeur. Cependant, il existera quand même un délai entre les composants proches du centre et ceux sur les bords du processeur. Mais le délai maximal est minimisé. Entre un délai proportionnel à la largeur du processeur, et un délai proportionnel à la distance maximale centre-bord (environ la moitié de la diagonale), le second est plus faible.

Il arrive que le clock skew soit utilisé volontairement pour compenser d'autres délais de transmission. Pour comprendre pourquoi, imaginons que deux composants soient reliés l'une avec l'autre, le premier envoyant ses données au second. Il y a évidemment un petit délai de transmission entre les deux. Mais sans clock skew, les deux composants recevront l'horloge en même temps : le receveur captera un front montant de l'horloge avant les données de l'émetteur. En théorie, on devrait cadencer l'horloge de manière à ce que ce délai inter-composants ne pose pas de problème. Mais cela n'est pas forcément la meilleure solution si on veut fabriquer un circuit à haute fréquence. Pour éviter cela, on peut ajouter un clock skew, qui retardera l’horloge du receveur. Si le clock skew est supérieur ou égal au temps de transmission inter-composants, alors le receveur réceptionnera bien le signal de l'horloge après les données envoyées par l'émetteur. On peut ainsi conserver un fonctionnement à haute fréquence, sans que les délais de transmission de données ne posent problème. Cette technique porte le nom barbare de source-synchronous clocking.

Interaction entre le clock skew et le délai de transmission entre deux circuits.


Dans les chapitres précédents, nous avons vu comment mémoriser un bit, dans une bascule. Mais les bascules en elles-mêmes sont rarement utiles seules, car les données à mémoriser font généralement plusieurs bits, pas un seul. Stocker plusieurs bits est la raison d'être des registres, des composants qui mémorisent des plusieurs bits, que l'on peut modifier et/ou récupérer plus tard. Il existe plusieurs types de registres, et nous allons faire la distinction entre les registres simples et les registres à décalage. Les registres simples sont capables de mémoriser un nombre, de taille fixe, rien de plus. Les registres à décalage sont des registres simples améliorés, capables de faire quelques petites opérations sur leur contenu.

Les registres simples[modifier | modifier le wikicode]

Les registres simples sont capables de mémoriser un nombre, codé sur une quantité fixe de bits. On peut à tout moment récupérer le nombre mémorisé dans le registre : on dit alors qu'on effectue une lecture. On peut aussi mettre à jour le nombre mémorisé dans le registre, le remplacer par un autre : on dit qu'on effectue une écriture. Les seules opérations possibles sur ces registres sont la lecture (récupérer le nombre mémorisé dans le registre) et l'écriture (mettre à jour le nombre mémorisé dans le registre, le remplacer par un autre).

L'interface d'un registre simple[modifier | modifier le wikicode]

Registre de 4 Bits. On voit que celui-ci contient 4 entrées (à gauche), et 4 sorties (à droite). On peut aussi remarquer une entrée CLK, qui joue le rôle d'entrée d'autorisation.

Niveau entrées et sorties, les registres possèdent des entrées-sorties pour les données mémorisées, mais aussi des entrées-sorties de commande. Les entrées-sorties pour les données permettent de lire le contenu du registre ou d'y écrire. Les entrées de commande permettent de configurer le registre pour lui ordonner de faire une écriture, pour le remettre à zéro, ou toute autre opération.

Les entrées de données sont utilisées pour l'écriture, alors que les sorties de données servent pour la lecture. Le nombre mémorisé dans le registre est disponible sur les sorties du registre. Pour utiliser les entrées d'écriture, on envoie le nombre à mémoriser (celui qui remplacera le contenu du registre) sur les entrées d'écriture et on configure les entrées de commande adéquates.

Les entrées de commande varient suivant le registre, mais on trouve au moins une entrée Enable, qui a le même rôle que pour une bascule, à savoir autoriser une écriture. Si l'entrée Enable est à 1, le registre mémorise ce qu'il y a sur l'entrée de donnée. Mais si l'entrée Enable est à 0, le registre n'est pas mis à jour : on peut mettre n'importe quelle valeur sur les entrées, le registre n'en tiendra pas compte et ne remplacera pas son contenu par ce qu'il y a sur l'entrée. Pour résumer, l'entrée Enable sert donc à indiquer au registre si son contenu doit être mis à jour, quand une écriture a lieu. D'autres entrées de commandes sont parfois présentes, la plus commune étant une entrée permettant de remettre à zéro le registre. La présence d'un 1 sur cette entrée remet à zéro le contenu du registre, à savoir que celui-ci contient la valeur zéro.

L'intérieur d'un registre simple[modifier | modifier le wikicode]

Un registre est composé de plusieurs bascules D qui sont toutes mises à jour en même temps. Pour cela, toutes les entrées E des bascules sont reliées à l'entrée de commande Enable.

Registre.

$

Les registres à décalage[modifier | modifier le wikicode]

Les registres à décalage sont des registres dont le contenu est décalé d'un cran vers la gauche ou la droite sur commande. Nous aurons à les réutiliser plus tard dans ce cours, notamment dans la section sur les circuits de génération de nombres aléatoires, ou dans certains circuits liés au cache. Les registres à décalage sont presque tous synchrones et ce chapitre ne parlera que ce ces derniers. L'animation suivante illustre le fonctionnement d'un registre à décalage qui décale son contenu d'un cran vers la droite à chaque cycle d'horloge.

Registre à décalage.

La classification des registres[modifier | modifier le wikicode]

On peut classer les registres selon le caractère de l'entrée et de la sortie, qui peut être parallèle (entrée de plusieurs bits) ou série (entrée d'un seul bit).

  • Sur les registres simples, les entrées et sorties pour les données sont toujours parallèles. Pour un registre de N bits, il y a une entrée d'écriture de N bits et une sortie de N bits. C'est la raison pour laquelle ils sont appelés des registres à entrées et sorties parallèles.
  • Sur les registres à entrée et sortie série, on peut mettre à jour un bit à la fois, de même qu'on ne peut en récupérer qu'un à la fois. Ces registres servent essentiellement à mettre en attente des bits tout en gardant leur ordre : un bit envoyé en entrée ressortira sur la sortie après plusieurs commandes de mise à jour sur l'entrée Enable.
  • Les registres à décalage à entrée série et sortie parallèle sont similaires aux précédents : on peut ajouter un nouveau bit en commandant l'entrée Enable et les anciens bits sont alors décalés d'un cran. Par contre, on peut récupérer (lire) tous les bits en une seule fois. Ils permettent notamment de reconstituer un nombre qui est envoyé bit par bit sur un fil (un bus série).
  • Enfin, il reste les registres à entrée parallèle et sortie série. Ces registres sont utiles quand on veut transmettre un nombre sur un fil : on peut ainsi envoyer les bits un par un.
Classification des registres à décalage.

Pour résumer, on distingue quatre types de registres (à décalage ou non), qui portent les noms de PIPO, PISO, SIPO et SISO. Les noms peuvent sembler barbares, mais il y a une logique derrière ces termes.La lettre P est pour parallèle, la lettre S est pour série. La lettre I signifie Input, ce qui veut dire entrée en anglais, la lettre O est pour Output, la sortie en anglais.

Classification des registres
Entrée parallèle Entrée série
Sortie parallèle PIPO (registre simple) SIPO
Sortie série PISO SISO

L'intérieur d'un registre à décalage[modifier | modifier le wikicode]

Tous les registres sont conçus en plaçant plusieurs bascules les unes à la suite des autres, que ce soit pour les registres simples ou les registres à décalage. La seule différence tient dans la manière dont les bascules sont reliées. Toutes les bascules sont reliées à l'entrée d'horloge, l'entrée Enable, l'entrée Reset, ou aux autres entrées de commandes. Mais c'est une autre paire de manche pour les entrées/sorties de données.

Dans un registre simple, les bascules sont indépendantes et ne sont pas reliées entre elles.

Registre simple.

À l'inverse, dans les registres à décalage, il existe des connexions entre bascules. Plus précisément, les bascules sont reliées les unes à la suite des autres, elles forment une chaîne de bascules reliées deux à deux. Et les connexions entre bascules sont les mêmes que l'on parle d'un registre à décalage de type SIPO, PISO ou SISO.

Exemple de registre à décalage

Outre le fait que les bascules sont reliées de la même manière, les autres connexions sont les mêmes dans tous les registres. L'entrée d'horloge (non-représentée dans les schémas qui vont suivre) est envoyée à toutes les bascules. Même chose pour l'entrée Enable, qui est reliée aux entrées E de toutes les bascules. La différence entre ces registres tient dans les endroits où se trouvent les entrées et les sorties du registre.

Implémentation des registres avec des bascules.
Registre à entrée et sortie série.
Registre à entrée et sortie parallèle.
Registre à entrée série et sortie parallèle.
Registre à entrée parallèle et sortie série.

Une utilisation des registres : les mémoires SRAM[modifier | modifier le wikicode]

Maintenant que nous avons les registres, il est temps d'en montrer une utilisation assez intéressante. Nous allons combiner les registres avec des multiplexeurs/démultiplexeurs pour former une mémoire adressable. Plus précisément, nous allons voir les mémoires de type SRAM et les mémoires ROM. Une mémoire de ce type peut être vu comme un rassemblement de plusieurs registres. Mais ces registres ne sont pas assemblés pour obtenir un registre plus gros : par exemple, on peut fabriquer un registre de 32 bits à partir de 2 registres de 16 bits, ou de 4 registres de 8 bits. Ce n'est pas ce qui est fait sur les mémoires adressables, où les registres sont regroupés de manière à ce qu'il soit possible de sélectionner le registre qu'on veut consulter ou modifier.

Pour préciser le registre à sélectionner, chacun d'entre eux se voit attribuer un nombre : l'adresse. On peut comparer une adresse à un numéro de téléphone (ou à une adresse d'appartement) : chacun de vos correspondants a un numéro de téléphone et vous savez que pour appeler telle personne, vous devez composer tel numéro. Les adresses mémoires en sont l'équivalent pour les registres d'une mémoire adressable. Il existe des mémoires qui ne fonctionnent pas sur ce principe, mais passons : ce sera pour la suite.

Exemple : on demande à la mémoire de sélectionner le byte d'adresse 1002 et on récupère son contenu (ici, 17).

L'interface d'une mémoire SRAM[modifier | modifier le wikicode]

Interface d'une SRAM.

Niveau entrées et sorties, une mémoire SRAM contient souvent des entrées-sorties dédiées aux transferts de données et plusieurs entrées de commande.

Les entrées de commande permettent de configurer la mémoire pour effectuer une lecture ou écriture, la mettre en veille, ou autre. Parmi les entrées de commande, on trouve une entrée de plusieurs bits, sur laquelle on peut envoyer l'adresse, appelée l'entrée d'adressage. On trouve aussi une entrée R/W d'un bit, qui permet de préciser si on veut faire une lecture ou une écriture. On trouve aussi parfois une entrée Enable Ou Chip Select, qui indique si la RAM est activée ou mise en veille, qui ressemble à l'entrée Enable des bascules.

Pour les données, tout dépend de la mémoire SRAM considérée. Sur certaines mémoires, on trouve une sortie sur laquelle on peut récupérer le registre sélectionné (on dit qu'on lit le registre) et une entrée sur laquelle on peut envoyer une donnée destinée à être écrite dans le registre sélectionné (on dit qu'on écrit le registre). On a donc une sortie pour la lecture et une entrée pour l'écriture. Mais sur d'autres mémoires SRAM, l'entrée et la sortie sont fusionnées en une seule entrée-sortie.

L'intérieur d'une mémoire RAM[modifier | modifier le wikicode]

Une telle mémoire peut se fabriquer assez simplement : il suffit d'un ou de plusieurs multiplexeurs et de registres. Quand on présente l'adresse sur l'entrée de sélection du multiplexeur, celui-ci va connecter le registre demandé à la sortie (ou à l'entrée).

Intérieur d'une RAM fabriquée avec des registres et des multiplexeurs.

Les mémoire mortes et mémoires vives[modifier | modifier le wikicode]

Les mémoires vues plus haut sont fabriquées avec des registres, eux-mêmes fabriqués avec des bascules, elles-mêmes fabriquées avec des portes logiques et/ou des transistors. Elles sont appelées des mémoires SRAM. Elles sont très utilisées, surtout dans les processeurs. Mais les mémoires sont très diverses et les mémoires SRAM ne sont qu'un type de mémoires parmi tant d'autres. Les mémoires SRAM font elles-mêmes partie de la catégorie des mémoires vives, aussi appelées mémoires RAM (bien que ce soit un abus de langage, comme on le verra dans plusieurs chapitres). De telles mémoires sont des mémoires électroniques, qui sont adressables, dans lesquelles on peut lire et écrire.

Il existe deux types de mémoires RAM : les mémoires SRAM vues auparavant, et les mémoires DRAM. La différence est leur caractère statique contre dynamique. Les données d'une mémoire statique ne s'effacent pas tant qu'elles sont alimentées en courant. Par contre, les données des mémoires dynamiques s'effacent en quelques millièmes ou centièmes de secondes si l'on n'y touche pas. Il faut donc réécrire chaque bit de la mémoire régulièrement, ou après chaque lecture, pour éviter qu'il ne s'efface. On dit qu'on doit effectuer régulièrement un rafraîchissement mémoire. Le rafraîchissement prend du temps, et a tendance à légèrement diminuer la rapidité des mémoires dynamiques. Les mémoires SRAM sont des mémoires RAM statiques, alors que les mémoires DRAM sont des mémoires RAM dynamiques. C'est de là que vient le S de SRAM (S pour Statique) et le D de DRAM (D pour Dynamique).

Les mémoires SRAM sont surtout utilisées dans les registres du processeur ou pour des mémoires de petite taille. Par contre, les mémoires DRAM sont utilisées pour des mémoires de plus grande taille, comme la mémoire principale de l'ordinateur. La raison est que les mémoires SRAM sont très gourmandes en transistors et en portes logiques, comparé aux mémoires DRAM. En contrepartie, les mémoires SRAM sont très rapides.

Outre les mémoires RAM, il existe des mémoires qui sont elles aussi électroniques, adressables, mais dans lesquelles on ne peut pas écrire : ce sont les mémoires ROM. Si on ne peut pas écrire dans une ROM, certaines permettent cependant de réécrire intégralement leur contenu : on dit qu'on reprogramme la ROM. Insistons sur la différence entre reprogrammation et écriture : l'écriture permet de modifier un byte sélectionné/adressé, alors que la reprogrammation efface toute la mémoire et la réécrit en totalité. De plus, la reprogrammation est généralement beaucoup plus lente qu'une écriture, sans compter qu'il est plus fréquent d'écrire dans une mémoire que la reprogrammer. Ce terme de programmation vient du fait que les mémoires ROM sont souvent utilisées pour stocker des programmes sur certains ordinateurs assez simples.

Classification des mémoires RAM et ROM.

On peut classer les mémoires ROM en plusieurs types :

  • les mask ROM sont fournies déjà programmées et ne peuvent pas être reprogrammées ;
  • les mémoires PROM sont fournies intégralement vierges, et on peut les programmer une seule fois ;
  • les mémoires RPROM sont reprogrammables, ce qui signifie qu'on peut les effacer pour les programmer plusieurs fois ;
    • les mémoires EPROM s'effacent avec des rayons UV et peuvent être reprogrammées plusieurs fois de suite ;
    • certaines RPROM peuvent être effacées par des moyens électriques : ce sont les mémoires EEPROM.

Les mémoires de type mask ROM sont utilisées dans quelques applications particulières. Par exemple, elles étaient utilisées sur les vieilles consoles de jeux, pour stocker le jeu vidéo dans les cartouches. Elles servent aussi pour les firmware divers et variés, comme le firmware d'une imprimante ou d'une clé USB. Par contre, le BIOS d'un PC (qui est techniquement un firmware) est stocké dans une mémoire EEPROM, ce qui explique qu'on peut le mettre à jour (on dit qu'on flashe le BIOS).

De telles mémoires seront utiles dans les chapitres qui vont suivre. La raison en est que tout circuit combinatoire peut être remplacé par une mémoire adressable ! Imaginons que l'on souhaite créer un circuit combinatoire qui pour toute entrée A fournisse la sortie B. Celui-ci est équivalent à une ROM dont la lecture de l'adresse A renvoie B sur la sortie. Cette logique est notamment utilisée dans certains circuits programmables, les FPGA, comme on le verra plus tard.


Illustration du fonctionnement d'un compteur modulaire binaire de 4 bits, avec un pas de compteur de 1 (le contenu est augmenté de 1 à chaque mise à jour).

Les compteurs/décompteurs sont des circuits électroniques qui mémorisent un nombre qu'ils mettent à jour régulièrement. Cette mise à jour augmente ou diminue le compteur d'une quantité fixe, appelée le pas du compteur. La plupart des compteurs utilisent un pas constant, qui est fixé à la création du compteur, ce qui simplifie la conception du circuit combinatoire. D'autres permettent un pas variable, et ont donc une entrée supplémentaire sur laquelle on peut envoyer le pas du compteur.

Suivant la valeur du pas, on fait la différence entre les compteurs d'un côté et les décompteurs de l'autre. Comme leur nom l'indique, les compteurs comptent alors que les décompteurs décomptent. Les compteurs augmentent le contenu du compteur à chaque mise à jour, alors que les décompteurs le diminuent. Dit autrement, le pas d'un compteur est positif, alors que le pas d'un décompteur est négatif. Les compteurs-décompteurs peuvent faire les deux, suivant ce qu'on leur demande.

Suivant le compteur, la représentation du nombre mémorisé change : certains utilisent le binaire traditionnel, d'autres le BCD, d'autre le code Gray, etc. Mais tous les compteurs que nous allons voir seront des compteurs/décompteurs binaires, à savoir que les nombres qu'ils utilisent sont codés sur bits. Au passage, le nombre de bits du compteur est appelé la taille du compteur, par analogie avec les registres.

Vu que la taille d'un compteur est limitée, il cesse de compter au-delà d'une valeur maximale. La plupart des compteurs comptent de 0 à , avec la taille du compteur. Ils sont appelés des compteurs modulo. D'autres compteurs ne comptent pas jusque-là : leur limite est plus basse que . Par exemple, certains compteurs ne comptent que jusqu'à 10, 150, etc.

Outre la valeur de la limite du compteur, il est aussi intéressant de se pencher sur ce qui se passe quand le compteur atteint cette limite. Certains restent bloqués sur cette valeur maximale tant qu'on ne les remet pas à zéro "manuellement" : ce sont des compteurs à saturation. D'autres recommencent à compter naturellement à partir de zéro : ce sont des compteurs modulaires.

L'interface d'un compteur[modifier | modifier le wikicode]

Compteurs et décompteurs sont presque tous des circuits synchrones, à savoir cadencés par une horloge. Du moins, c'est le cas des compteurs/décompteurs que nous allons voir dans ce chapitre, par souci de simplicité. Un compteur/décompteur est donc relié à une entrée d'horloge.

De plus, certains compteurs ont une entrée Enable qui active/désactive le comptage. Le compteur s'incrémente/décrémente seulement si l'entrée Enable est à 1, mais ne fait rien si elle est à 0. Les compteurs les plus simples sont incrémentés/décrémentés à chaque cycle d'horloge et n'ont pas d'entrée Enable, mais les compteurs plus complexes en ont une. Ce faisant, le compteur/décompteur est incrémenté seulement si deux conditions sont réunies : un front montant sur le signal d'horloge, et une entrée Enable à 1. Dans les schémas qui vont suivre, nous ferons mention soit au signal d'horloge, soit à l'entrée Enable. Si on fait référence à l'entrée Enable, il est sous-entendu que les bascules du registre sont cadencées par une horloge, qui leur dit quand s'actualiser.

En outre, les compteurs ont souvent une entrée Reset qui permet de les remettre à zéro.

Sur les compteurs/décompteurs, il y a une entrée qui décide s'il faut compter ou décompter. Typiquement, elle est à 1 s'il faut compter et 0 s'il faut décompter.

Compteur 4 Bits.
Compteur 4 Bits avec entrée Reset.
Compteur 4 Bits avec entrée pour décider s'il faut compter ou décompter.

Le circuit d'un compteur : généralités[modifier | modifier le wikicode]

Un compteur/décompteur peut être vu comme une sorte de registre (il peuvent stocker un nombre), mais qu'on aurait amélioré de manière à le rendre capable de compter/décompter. Tous les compteurs/décompteurs utilisent un registre pour mémoriser le nombre, ainsi que des circuits combinatoires pour calculer la prochaine valeur du compteur. Ce circuit combinatoire est le plus souvent, mais pas toujours, un circuit capable de réaliser des additions (compteur), des soustractions (décompteurs), voire les deux (compteur-décompteur). Plus rarement, il s'agit de circuits conçus sur mesure, dans le cas où le pas du compteur est fié une bonne fois pour toute.

Comme tout registre, un compteur/décompteur peut être initialisé avec la valeur de notre choix. Pour cela, ils possèdent une entrée d'initialisation sur laquelle on peut placer le nombre initial, couplée à une entrée Reset qui indique si le compteur doit être réinitialisé ou non. Certains compteurs/décompteurs spécifiques n'ont pas d'entrée d'initialisation, mais seulement une entrée de reset, mais il s'agit là d'utilisations assez particulières où le compteur ne peut qu'être réinitialisé à une valeur par défaut. Pour les compteurs/décompteurs, il faut aussi rajouter une entrée qui précise s'il faut compter ou décompter.

Fonctionnement d'un compteur (décompteur), schématique

Comme dit plus haut, certains compteurs ont une valeur maximale qui est plus faible que la valeur maximale du registre. Par exemple, on peut imaginer un compteur qui compte de 0 à 9 : celui-ci est construit à partir d'un registre de 4 bits qui peut donc compter de 0 à 15 ! Ces compteurs sont construits à partir d'un compteur modulo, auquel on rajoute un circuit combinatoire. Ce dernier détecte le dépassement de la valeur maximale et remet à zéro le registre quand c'est nécessaire, via l'entrée de Remise à zéro (entrée Reset).

Compteur modulo N.

L'incrémenteur/décrémenteur[modifier | modifier le wikicode]

Certains compteurs, aussi appelés incrémenteurs comptent de un en un. Les décompteurs analogues sont appelés des décrementeurs. Nous allons voir comment créer ceux-ci dans ce qui va suivre. Il faut savoir qu'il existe deux méthodes pour créer des incrémenteurs/décrémenteurs. La première donne ce qu'on appelle des incrémenteurs asynchrones, et l'autre des incrémenteurs synchrones. Nous allons commencer par voir comment fabriquer un incrémenteur synchrone, avant de passer aux incrémenteurs asynchrones.

L'incrémenteur asynchrone[modifier | modifier le wikicode]

Pour fabriquer un incrémenteur synchrone, la première méthode, il suffit de regarder la séquence des premiers entiers, puis de prendre des paires de colonnes adjacentes :

  • 000 ;
  • 001 ;
  • 010 ;
  • 011 ;
  • 100 ;
  • 101 ;
  • 110 ;
  • 111.

On remarque que le bit sur une colonne change quand le bit de la colonne précédente passe de 1 à 0, en clair, lorsqu'on a un front descendant sur la colonne précédente. Pour la colonne la plus à droite (celle des bits de poids faible), on remarque que celle-ci inverse son contenu à chaque cycle d'horloge. Maintenant que l'on sait cela, on peut facilement créer un compteur avec quelques bascules. Et plus précisément, il est utile d'utiliser des bascules T, éventuellement des bascules T simplifiées. Pour rappel, ces bascules inversent leur contenu à chaque cycle d'horloge. Par simplicité, nous allons utiliser des bascules avec une sortie qui fournit l'inverse du bit stocké.

La première colonne inverse son contenu à chaque cycle, elle correspond donc à une bascule T simplifiée reliée directement à l'horloge. Les autres colonnes s'inversent quand survient un front descendant sur la colonne précédente. le circuit qui correspond est donc celui-ci, avec des bascules T activées sur front descendant :

Compteur asynchrone de 3 bits, basé sur des bascules T simplifiées activées sur front descendant.

Il est aussi possible d'utiliser des bascules T actives sur front montant. En effet, notons qu'un front descendant sur la sortie Q correspond à un front montant sur la sortie /Q. En clair, il suffit de relier la sortie /Q d'une colonne sur l'entrée d'horloge de la suivante. Le circuit est donc le suivant :

Compteur asynchrone de 3 bits, basé sur des bascules T simplifiées activées sur front montant.

Il est aussi possible d'utiliser des bascules JK pour créer un compteur comme les deux précédents. En effet, une bascule T simplifiée est identique à une bascule JK dont les deux entrées J et K sont à 1.

Compteur asynchrone de 3 bits, basé sur des bascules JK activées sur front montant.

Le circuit précédent a cependant un problème : il ne peut pas être réinitialisé. Pour que cela soit possible, il faut que les bascules du compteur aient une entrée de réinitialisation Reset, qui les force à se remettre à zéro, alors on peut l'utiliser. Il suffit d'ajouter une entrée Reset au compteur, et de la connecter aux entrées Reset des bascules. Ce faisant, le compteur peut être remis à zéro sur simple demande.

Compteur réinitialisable.

Cette réinitialisation est utile pour créer des compteurs modulo. Il suffit de créer un circuit qui vérifie si la valeur maximale du comparateur est atteinte et qui met à 1 l'entrée Reset si c'est le cas. Un exemple est illustré ci-dessous.

Compteur modulo 10.

Il est aussi possible d'utiliser des bascules D pour créer un compteur comme les deux précédents. En effet, une bascule T simplifiée est identique à une bascule D dont on boucle la sortie /Q sur l'entrée de données.

Compteur asynchrone, sans initialisation

Cette implémentation peut être modifiée pour facilement réinitialiser le compteur à une valeur non-nulle. Pour cela, il faut ajouter une entrée au compteur, sur laquelle on présente la valeur d’initialisation. Chaque bit de cette entrée est reliée à un multiplexeur, qui choisir quel bit mémoriser dans la bascule : celui fournit par la mise à jour du compteur, ou celui présenté sur l'entrée d'initialisation. On obtient le circuit décrit dans le schéma qui suit. Quand l'entrée Reset est activée, les multiplexeurs connectent les bascules aux bits sur l'entrée d'initialisation. Dans le cas contraire, le compteur fonctionne normalement, les multiplexeurs connectant l'entrée de chaque bascule à sa sortie.

Compteur asynchrone, avec initialisation.

Le décrémenteur asynchrone[modifier | modifier le wikicode]

Un décrémenteur est strictement identique à un incrémenteur auquel on a inversé tous les bits. On peut donc réutiliser le compteur du dessus, à part que les sorties du compteurs sont reliées aux sorties Q des bascules.


Décompteur asynchrone de 3 bits, basé sur des bascules T simplifiées activées sur front descendant.

L'incrémenteur/décrémenteur synchrone[modifier | modifier le wikicode]

Passons maintenant à l'incrémenteur synchrone. Pour le fabriquer, on repart de la séquence des premiers entiers. Dans ce qui va suivre, nous allons créer un circuit qui compte de 1 en 1, sans utiliser d'additionneur. Pour comprendre comment créer un tel compteur, nous allons reprendre la séquence d'un compteur, déjà vue dans le premier extrait :

  • 000
  • 001
  • 010
  • 011
  • 100
  • 101
  • 110
  • 111

On peut remarquer quelque chose dans ce tableau : peu importe la colonne, un bit s'inversera au prochain cycle d’horloge quand tous les bits des colonnes précédentes valent 1. Et c'est vrai quel que soit la taille du compteur ou sa valeur ! Ainsi, prenons le cas où le compteur vaut 110111 :

  • les deux premiers 1 sont respectivement précédés par la séquence 10111 et 0111 : vu qu'il y a un zéro dans ces séquences, ils ne s'inverseront pas au cycle suivant ;
  • le bit qui vaut zéro est précédé de la séquence de bit 111 : il s'inversera au cycle suivant ;
  • le troisième 1 en partant de la gauche est précédé de la séquence de bits 11 : il s'inversera aussi ;
  • même raisonnement pour le quatrième 1 en partant de la gauche ;
  • 1 le plus à droite correspond au bit de poids faible, qui s'inverse tous les cycles.

Pour résumer, un bit s'inverse (à la prochaine mise à jour) quand tous les bits des colonnes précédentes valent 1. Pour implanter cela en circuit, on a besoin de deux circuits par bascules : un qui détermine si les bits des colonnes précédentes sont à 1, et un autre qui inverse le bit de la bascule. Le circuit qui détermine si tous les bits précédents sont à 1 est un simple ET entre les bits en question. L'autre circuit prend en entrée le contenu de la bascule et un bit qui indique s'il faut inverser ou pas. En écrivant sa table de vérité, on s’aperçoit qu'il s'agit d'un simple XOR.

Compteur synchrone à incrémenteur

On peut appliquer la même logique pour un décrémenteur. Avec ce circuit, un bit s'inverse lorsque tous les bits précédents sont à zéro. En utilisant le même raisonnement que celui utilisé pour concevoir un incrémenteur, on obtient un circuit presque identique, si ce n'est que les sorties des bascules doivent être inversées avant d'être envoyée à la porte XOR qui suit.

Les compteurs basés sur des registres à décalage[modifier | modifier le wikicode]

Il existe des compteurs qui sont basés sur un registre à décalage modifiés. Ils regroupent les compteurs en anneau, les compteurs de Johnson et les registres à décalage à rétroaction linéaire. Les plus connus sont basés sur des registres à décalage avec une entrée série, à savoir qu'ils ont une entrée d'un seul bit. Ils peuvent donc insérer un bit dans le registre, à chaque cycle d’horloge. Le bit inséré est calculé soit en fonction du contenu du registre, soit en fonction du bit sortant du registre.

Les compteurs en anneau[modifier | modifier le wikicode]

Les compteurs en anneau sont des registres à décalage dont le bit sortant est renvoyé sur l'entrée. Naturellement, il existe une version qui peut être remise à zéro.

Compteur en anneau de 4 bits


Avec n bits, ce registre peut prendre N valeurs différentes, qui ont toutes un seul bit à 1. La séquence d'un compteur en anneau de 4 bits est illustrée ci-dessous. Elle donne ceci : 1000, 0100, 0010, 0001.

Évolution du contenu d'un compteur en anneau.

Les compteurs de Johnson[modifier | modifier le wikicode]

Sur les compteurs de Johnson, le bit sortant est inversé avant d'être bouclé sur l'entrée. Ce compteur parcours deux fois plus de valeurs différentes, comparé à un compteur en anneau. La séquence d'un tel compteur est :

  • 1000 ;
  • 1100 ;
  • 1110 ;
  • 1111 ;
  • 0111 ;
  • 0011 ;
  • 0001 ;
  • 0000.
Compteur de Johnson de 4 bits

Les registres à décalage à rétroaction linéaire[modifier | modifier le wikicode]

Sur les registres à décalage à rétroaction linéaire de Fibonacci, le bit d'entrée est calculé en fonction du contenu du registre par un circuit combinatoire. La fonction mathématique qui calcule le bit en entrée est assez spéciale. Dans le cas le plus simple, on dit qu'elle est linéaire, ce qui veut dire que le bit de sortie se calcule à partir en multipliant les bits d'entrée par 0 ou 1, et en additionnant le tout. En clair, ce bit de sortie se calcule par une formule du style : :

, où on ne garde que le bit de poids faible du résultat.

Penchons-nous un peu sur cette addition qui ne garde que le bit de poids faible : je ne sais pas si vous avez remarqué, mais il s'agit ni plus ni moins que d'un calcul de parité paire. En effet, si on additionne N bits, le bit de poids faible vaut zéro pour un nombre pair, et 1 pour un nombre impair. Le circuit combinatoire chargé de calculer le bit de résultat est donc un circuit qui calcule la parité de la somme des bits choisis. Pour cela, il suffit d'effectuer une série de XOR entre tous les bits à additionner.

Registre à décalage à rétroaction de Fibonnaci.

Il existe une variante de ce genre de registre, qui modifie légèrement son fonctionnement. Il s'agit des registres à décalages à rétroaction affine. Avec ces registres, la fonction qui calcule le bit de résultat n'est pas linéaire, mais affine. En clair, ce bit de sortie se calcule par une formule du style :

Notez le + 1 à la fin de la formule : c'est la seule différence. Avec ce genre de registre, le bit de résultat est donc calculé en faisant le calcul d'un bit d'imparité de certains (ou de la totalité) des bits du registre. Un tel circuit est donc composé de portes NXOR, comparé à son comparse linéaire, composé à partir de portes XOR. Petite remarque : si je prends un registre à rétroaction linéaire et un registre à rétroaction affine avec les mêmes coefficients sur les mêmes bits, le résultat du premier sera égal à l'inverse de l'autre.


Les registres à décalage à rétroaction de Gallois sont un peu l'inverse des registres à décalages à rétroaction de Fibonacci vus juste avant. Dans ces derniers, on prenait plusieurs bits du registre à décalage pour en déduire un seul bit. Avec les registres à décalage à rétroaction de Gallois, c'est l'inverse : on prend le bit sortant et on en déduit plusieurs bits à partir d'un circuit combinatoire, qui sont chacun insérés dans le registre à décalage à un endroit bien précis. Bien sûr, la fonction qui calcule des différents bits à partir du bit d'entrée conserve les mêmes propriétés que celle utilisée pour les registres à décalages à rétroaction linéaire : elle est affine ou linéaire, et se calcule avec uniquement des portes XOR pour les fonctions linéaires, ou NXOR pour les fonctions affines.

Registre à décalage à rétroaction de Galois.


Dans de nombreuses situations, il peut être utile de pouvoir générer des nombres totalement aléatoires. C'est très utile dans des applications cryptographiques, statistiques, mathématiques, et j'en passe. Ces applications sont le plus souvent logicielles, et cette génération de nombres aléatoire s'effectue avec divers algorithmes plus ou moins efficaces. Mais dans certaines situations, il arrive que l'on veuille créer ces nombres aléatoires de manière matérielle. Cela peut servir pour sélectionner une ligne de cache à remplacer lors d'un cache miss, pour implémenter des circuits cryptographiques, pour calculer la durée d'émission sur un bus Ethernet à la suite d'une collision, et j'en passe. Mais comment créer une suite de nombres aléatoires avec des circuits ? C'est le but de ce tutoriel de vous expliquer comment !

Les registres à décalage à rétroaction[modifier | modifier le wikicode]

La première solution consiste à utiliser des registres à décalages à rétroaction, aussi appelés Feedback Shift Registers, abréviés LSFR. Ce genre de circuit donne un résultat assez proche de l'aléatoire, mais on peut cependant remarquer qu'il ne s'agit pas de vrai aléatoire. En effet, un tel circuit est déterministe : pour le même résultat en entrée, il donnera toujours le même résultat en sortie. De plus, ce registre ne peut contenir qu'un nombre fini de valeurs, ce qui fait qu'il finira donc par repasser par une valeur qu'il aura déjà parcourue. Lors de son fonctionnement, le compteur finira donc par repasser par une valeur qu'il aura déjà parcourue, vu que le nombre de valeurs possibles est fini. Une fois qu'il repassera par cette valeur, son fonctionnement se reproduira à l'identique comparé à son passage antérieur. Un LSFR ne produit donc pas de « vrai » aléatoire, vu que la sortie d'un tel registre finit par faire des cycles. Ceci dit, si la période d'un cycle est assez grande, son contenu semblera varier de manière totalement aléatoire, tant qu'on ne regarde pas durant longtemps. Il s'agit d'une approximation de l'aléatoire particulièrement bonne.

La période N dépend fortement de la fonction utilisée pour calculer le bit de sortie, des bits choisis, etc. Dans le meilleur des cas, le registre à décalage à rétroaction passera par presque toutes les valeurs que le registre peut prendre. Si je dis presque toutes, c'est simplement qu'une valeur n'est pas possible : suivant le registre, le zéro ou sa valeur maximale sont interdits. Si un registre à rétroaction linéaire passe par zéro (ou sa valeur maximale), il y reste bloqué définitivement. La raison à cela est simple : un XOR sur des zéros donnera toujours 0. Le même raisonnement peut être tenu pour les registres à rétroaction affine, sauf que cette fois-ci, le raisonnement ne marche qu'avec la valeur maximale stockable dans le registre. Tout le chalenge consiste donc à trouver quels sont les registres à rétroaction dont la période est maximale : ceux dont la période vaut . Qu'on se rassure, quelle que soit la longueur du registre, il en existe au moins un : cela se prouve mathématiquement, même si nous ne vous donnerons pas la démonstration.

Combinaisons de LSFR[modifier | modifier le wikicode]

Nonlinear-combo-generator

Si les LSFR sont très intéressants, diverses techniques permettent d'améliorer le fonctionnement de ces registres à décalages à rétroaction. Par exemple, on peut décider d'utiliser des LSFR plus compliqués, non linéaires. La fonction appliquée au bit sur l'entrée est alors plus complexe, mais le jeu en vaut la chandelle. Une variante de cette technique consiste à prendre la totalité des bits d'un registre à décalage à rétroaction linéaire (ou affine), et à envoyer ces bits dans un circuit non-linéaire. La différence, c'est que dans ce cas, tous les bits du registre sont pris en compte. Cependant, les techniques les plus efficaces consistent à combiner plusieurs LSFR pour obtenir une meilleure approximation de l'aléatoire. Avec cette technique, plusieurs registres à décalages à rétroaction sont reliés à un circuit combinatoire non-linéaire. Ce circuit prendra en entrée un (ou plusieurs) bit de chaque registre à décalage à rétroaction, et combinera ces bits pour fournir un bit de sortie. Un circuit conçu avec ce genre de méthode va fournir un bit à la fois. Les bits en sortie de ce circuit seront alors accumulés dans un registre à décalage normal, pour former un nombre aléatoire.

Problème : ces circuits ne sont pas totalement fiables : ils peuvent produire plus de bits à 0 que de bits à 1, et des corrections sont nécessaires pour éviter cela. Pour cela, ces circuits de production de nombres aléatoires sont souvent couplés à des circuits qui corrigent le flux de bits accumulé dans le registre pour l'aléatoiriser. Une solution consiste à simplement prendre plusieurs de ces circuits, et d'appliquer un XOR sur les bits fournis par ces circuits : on obtient alors un bit un peu moins biaisé, qu'on peut envoyer dans notre registre à décalage. Pratiquement, des circuits avec trop de bits en entrées sont difficilement concevables.

Pour rendre le tout encore plus aléatoire, il est possible de cadencer nos registres à décalage à rétroaction linéaire à des fréquences différentes. Ainsi, le résultat fourni par notre circuit combinatoire est encore plus aléatoire. Cette technique est utilisée dans les générateurs stop-and-go, alternative step, et à shrinking. Dans le premier, on utilise trois registres à décalages à rétroaction linéaire. Le bit fourni par le premier va servir à choisir lequel de deux restants sera utilisé. Dans le générateur stop-and-go, on utilise deux registres à décalage à rétroaction. Le premier est relié à l'entrée d'horloge du second. Le bit de sortie du second est utilisé comme résultat. Une technique similaire était utilisée dans les processeurs VIA C3, pour l'implémentation de leurs instructions cryptographiques. Dans le shrinking generator, deux registres à décalage à rétroaction sont cadencés à des vitesses différentes. Si le bit de sortie du premier vaut 1, alors le bit de sortie du second est utilisé comme résultat. Par contre, si le bit de sortie du premier vaut 0, aucun bit n'est fourni en sortie, et le bit de sortie du second registre est oublié.

L'aléatoire généré par l'horloge[modifier | modifier le wikicode]

On vient de voir que les registres à décalage à rétroaction ne permettent pas d'obtenir du vrai aléatoire, compte tenu de leur comportement totalement déterministe. Pour obtenir un aléatoire un peu plus crédible, il est possible d'utiliser d'autres moyens qui ne sont pas aussi déterministes et surtout qui ne sont pas cycliques. Parmi ces moyens, certains d'entre eux utilisent le signal d'horloge. Par exemple, une technique très simple utilise un compteur incrémenté à chaque cycle d'horloge. Si on a besoin d'un nombre aléatoire, il suffit de lire le contenu de ce registre et de l'utiliser directement comme nombre aléatoire. Si le délai entre deux demandes est irrégulier, le résultat semblera bien aléatoire. Mais il s'agit là d'une technique assez peu fiable dans le monde réel et seules quelques applications bien spécifiques se satisfont de cette méthode.

Une solution un peu plus fiable utilise ce qu'on appelle la dérive de l'horloge. Il faut savoir qu'un signal d'horloge n'est jamais vraiment très précis. Une horloge censée tourner à 1 Ghz ne tournera pas en permanence à 1Ghz exactement, mais verra sa fréquence varier de quelques Hz ou Khz de manière irrégulière. Ces variations peuvent venir de variations aléatoires de température, des variations de tension, des perturbations électromagnétiques, ou à des phénomènes assez compliqués qui peuvent se produire dans tout circuit électrique (comme le shot noise). L'idée consiste à prendre au moins deux horloges et d'utiliser la dérive des horloges pour les désynchroniser. On peut par exemple prendre deux horloges : une horloge lente et une horloge rapide, dont la fréquence est un multiple de l'autre. Par exemple, on peut choisir une fréquence de 1 Mhz et une autre de 100 Hz : la fréquence la plus grande est égale à 10000 fois l'autre. La dérive d'horloge fera alors son œuvre : les deux horloges se désynchroniseront en permanence, et cette désynchronisation peut être utilisée pour produire des nombres aléatoires. Par exemple, on peut compter le nombre de cycles d'horloge produit par l'horloge rapide durant une période de l'horloge lente. Si ce nombre est pair, on produit un bit aléatoire qui vaut 1 sur la sortie du circuit. Pour information, c'est exactement cette technique qui était utilisée dans l'Intel 82802 Firmware Hub.

L'aléatoire généré par la tension d'alimentation[modifier | modifier le wikicode]

Il existe d'autres solutions matérielles. Dans les solutions électroniques, il arrive souvent qu'on utilise le bruit thermique présent dans tous les circuits électroniques de l'univers. Tous nos circuits sont soumis à de microscopiques variations de température, dues à l'agitation thermique des atomes. Plus la température est élevée, plus les atomes qui composent les fils de nos circuits s'agitent. Vu que les particules d'un métal contiennent des charges électriques, ces vibrations font naître des variations de tensions assez infimes. Il suffit d'amplifier ces variations pour obtenir un résultat capable de représenter un zéro ou un 1. C'est sur ce principe que fonctionne le circuit présent dans les processeurs Intel modernes. Comme vous le savez peut-être déjà, les processeurs Intel Haswell contiennent un circuit capable de générer des nombres aléatoires. Ces processeurs incorporent des instructions capables de fournir des nombres aléatoires, instructions utilisant le fameux circuit que je viens de mentionner.


Les circuits de calcul et de comparaison[modifier | modifier le wikicode]

Les comparateurs sont des circuits qui permettent de comparer deux nombres, à savoir s'ils sont égaux, si l'un est supérieur à l'autre, ou inférieur, ou différent, etc. Dans ce qui va suivre, nous allons voir quatre types de comparateurs. Le premier type de circuit vérifie si un nombre est nul ou différent de zéro. Le second vérifie si deux nombres sont égaux, tandis que le troisième vérifie s'ils sont différent. Enfin, le quatrième vérifie si un nombre est supérieur ou inférieur à un autre. Il faut signaler que nous avons déjà vu comment vérifier qu'un nombre est égal à une constante dans le chapitre sur les circuits combinatoires, aussi nous ne reviendrons pas dessus.

Le comparateur de 1 bit[modifier | modifier le wikicode]

Comparateur 1 bit.

Pour commencer, nous allons voir comment vérifier si deux bits sont égaux/différents, si le premier est inférieur au second ou supérieur. Le but est de créer un circuit qui prend en entrée deux opérandes A et B, et fournit en sortie quatre bits :

  • qui vaut 1 si l'opérande A est supérieure à B et 0 sinon ;
  • qui vaut 1 si l'opérande A est inférieure à B et 0 sinon ;
  • qui vaut 1 si l'opérande A est égale à B et 0 sinon ;
  • qui vaut 1 si l'opérande A est différente de B et 0 sinon.

Notons rapidement que les deux dernières entrées sont l'inverse l'une de l'autre, ce qui n'est pas le cas des deux premières. Nous allons d'abord voir comment calculer les deux premières sorties, à savoir et . La raison à cela est que les deux autres sorties peuvent se calculer à partir de celles-ci.

Peut-être avez-vous remarqué l'absence de sortie qui indique si ou . Mais ces deux sorties peuvent se calculer en combinant la sortie avec les sorties et .

Le comparateur de supériorité/infériorité stricte[modifier | modifier le wikicode]

En premier lieu, nous allons voir comment vérifier qu'un bit A est strictement supérieur ou inférieur à un bit B. Pour cela, le mieux est d'établir la table de vérité des deux comparaisons. La table de vérité est la suivante :

Entrée A Entrée B Sortie < Sortie >
0 0 0 0
0 1 1 0
1 0 0 1
1 1 0 0

On obtient les équations suivantes :

  • Sortie > :
  • Sortie < :

Le comparateur d'inégalité 1 bit[modifier | modifier le wikicode]

La seconde étape est de concevoir un petit circuit qui vérifie si deux bits sont différents, inégaux. Pour cela, on peut combiner les deux signaux précédents. En effet, on sait que si A et B sont différents, alors soit A>B, soit A<B. En conséquence, on a juste à combiner les deux signaux vus précédemment avec une porte OU.

Comparateur d'inégalité 1 bit.

Ce circuit devrait vous dire quelque chose. Pour ceux qui n'ont pas déjà remarqué, le mieux est d'établir la table de vérité du circuit, ce qui donne :

Entrée 1 Entrée 2 Sortie
0 0 0
0 1 1
1 0 1
1 1 0

On voit rapidement qu'il s'agit d'une porte XOR.

Le comparateur d'égalité 1 bit[modifier | modifier le wikicode]

Enfin, nous allons concevoir un petit circuit qui vérifie si deux bits sont égaux. La logique veut que l'égalité est l'inverse de l'inégalité, ce qui fait qu'il suffirait d'ajouter une porte NON en sortie du circuit. Le circuit précédent est alors facile à adapter : il suffit de remplacer la porte OU par une porte NOR. Et si le comparateur d'inégalité 1 bit était une porte XOR, on devine rapidement que le comparateur d'égalité 1 bit est quant à lui une porte NXOR. Ce qui se vérifie quand on regarde la table de vérité du comparateur :

A B A=B
0 0 1
0 1 0
1 0 0
1 1 1

L'interprétation de ce circuit est assez simple. Par définition, deux nombres sont égaux si les deux conditions et sont fausses. C’est pour cela que le circuit calcule d'abord les deux signaux et , puis qu'il les combine avec une porte NOR.

Le circuit complet[modifier | modifier le wikicode]

Fort de ces résultats, nous pouvons fabriquer un comparateur de 1 bit. Celui-ci prend deux bits en entrée, et fournit trois bits en sortie : un pour l'égalité, un autre pour la supériorité et un autre pour l'infériorité. Voici le circuit au complet (sans le bit de différence). On pourrait rajouter le bit de différence assez simplement, en ajoutant une porte OU en sortie des signaux et , mais nous le ferons pas pour ne pas surcharger inutilement les schémas.

Comparateur de magnitude 1 bit.
Comparateur de magnitude 1 bit, alternatif.

Il est aussi possible de reformuler le schéma précédent pour supprimer une redondance invisible dans le circuit, au niveau de la porte NXOR qui calcule le bit d'égalité. À la place, il est possible de prendre les signaux et et de les combiner avec une porte NOR. Ou encore mieux : on utilise une porte OU et une porte NON, la sortie de la porte OU donnant directement le bit d'inégalité, celle de la porte NON donnant le bit d'égalité. Cela économise quelques transistors, mais rallonge un petit peu le circuit.

Comparateur 1 bit complet

Le comparateur avec une constante[modifier | modifier le wikicode]

Voyons maintenant un comparateur qui vérifie si le nombre d'entrée est égal à une certaine constante (2, 3, 5, 8, ou tout autre nombre) qui dépend du circuit 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 comme autre exemple, créer un circuit qui met sa sortie à 1 uniquement quand l'entrée correspondent au nombre 126. Et ainsi de suite : tout nombre peut servir de constante à vérifier. Il possède donc 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.

Introduction : le comparateur avec zéro[modifier | modifier le wikicode]

Le premier circuit que nous allons aborder vérifie si un nombre est nul. Il fonctionne sur un principe simple : un nombre est nul si tous ses bits valent 0.

La solution la plus simple pour créer ce circuit est d'utiliser une porte NOR à plusieurs entrées. Par définition, la sortie d'une NOR vaut zéro si un seul bit de l'entrée est à 1 et 0 sinon, ce qui répond au cahier des charges.

Porte NOR utilisée comme comparateur avec zéro.

Il existe une autre possibilité strictement équivalente, mais qu'il est utile de comprendre pour la suite de ce chapitre. L'idée est d'inverser l'entrée avant de faire la comparaison. Les bits inversés valent tous 1 si l'entrée est nulle, alors qu'une entrée non-nulle donnera au moins un bit à 1. Cette fois-ci, le circuit ne se résume plus à une seule porte logique, mais à deux couches de portes logiques. La première inverse tous les bits, et un autre qui vérifient s'ils valent tous un. Le premier circuit est naturellement composé de portes NON, une par bit. Elle est suivie par une porte ET à plusieurs entrées qui vérifie si tous les bits sont à 1.

Circuit compare si l'opérande d'entrée est nulle.

Notons qu'en peut passer du premier circuit au second, et du second circuit au premier, en utilisant les lois de de Morgan.

Le comparateur avec une constante : cas général[modifier | modifier le wikicode]

Les circuits qui vont suivre sont une amélioration du circuit de comparaison avec zéro. Ou plutôt, les circuits de comparaison avec zéro précédents ne sont que des cas particuliers des circuits qui vont suivre. Dans ce qui va suivre, nous allons voir les comparateurs avec une constante, et 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 second type ressemble beaucoup au comparateur avec zéro, ce qui fait que nous allons le voir en priorité. Tout comparateur avec une constante est systématiquement composé de deux couches de portes logiques

Le comparateur avec une constante de type NON-ET[modifier | modifier le wikicode]

Le comparateur avec une constante de type NON-ET est conçu avec une couche de portes NON et 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.

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.

Fonctionnement d'un comparateur avec une constante.

Le comparateur avec une constante de type NON-NOR[modifier | modifier le wikicode]

Le second type de comparateur avec une constante est fabriqué avec une porte NOR précédée de portes NON. Il se fabrique comme le comparateur précédent, sauf que cette fois-ci, il faut mettre une porte NON pour chaque bit à 1 de l'opérande, et non chaque bit à zéro. En clair, la couche de portes NON est l'exact inverse de celle du circuit précédent. Le tout est suivi par une porte NOR.

Exemples de comparateurs de type NON-NOR.

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 zéro en sortie ;
  • si on envoie un autre nombre, soit certains 1 du nombre en entrée ne seront pas inversés, ou alors des bits à 0 le seront : il y aura au moins un bit à 1 en sortie de la couche de portes NON.

La porte NOR, quant à elle est un comparateur avec zéro, comme on l'a vu plus haut. Pour résumer, la première couche de portes NON transforme l'opérande et que la porte NOR vérifie si l'opérande transformée vaut zéro. La transformation de l'opérande est telle que son résultat est nul seulement si l’opérande est égale à la constante testée.

Fonctionnement des comparateurs de type NON-NOR.

Il est possible de simplifier le circuit en utilisant la loi de de Morgan, afin de supprimer la double négation implicite de certains bits de l'opérande. Après tout, l'inversion de la porte NOR fait doublon avec la couche de portes NON sur certains bits de l'opérande. En faisant cela, on se retrouve avec le comparateur précédent, de type NON-ET.

Le comparateur d'égalité et de différence pour entiers[modifier | modifier le wikicode]

Les circuits qui vérifient si deux nombres sont égaux ou différents sont plus simples que les autres comparateurs. Ceux-ci sont juste composés de deux couches de portes logiques, contrairement aux autres. La vérification de supériorité ou d'infériorité est nettement plus complexe et leur fonctionnement est quelque peu différent. C'est la raison pour laquelle nous allons voir ces deux types de comparateurs ensemble.

Les deux sont cependant basés sur le même modèle et ont une structure similaire. Ils sont composés d'une couche de comparateurs de 1 bits, suivi par une porte logique à plusieurs entrées. La couche de comparateur 1 bits vérifie si les bits de même poids des deux opérandes sont différents ou identiques. La porte logique combine les résultats de ces comparaisons individuelles et en déduit le bit de sortie.

Le comparateur d'égalité[modifier | modifier le wikicode]

Voyons d'abord le circuit qui vérifie si deux nombres sont égaux. Pour cela, il faut prendre les bits de même poids (ceux à la même position dans le nombre, sur la même colonne) et vérifier qu'ils sont égaux. Si tous les bits de même poids sont égaux, alors les deux nombres sont égaux. Par contre, si deux bits de même poids sont différents, quel que soit la colonne, alors les deux nombres sont différents. En clair, la moindre différence entraîne l'inégalité.

On devine que ce circuit est composé de deux couches de portes logiques : une première couche vérifie l'égalité des paires de bits, le second combine les résultats de la couche précédente. Vérifier l'égalité de deux bits se fait avec une porte NXOR, ce qui fait que la première couche est composée de portes NXOR. Reste à combiner les résultats des différentes portes NXOR pour fournit le bit de sortie. La logique dit que la sortie vaut 1 si tous les bits de sortie des NXOR valent 1. La seconde couche est donc, par définition, une porte ET à plusieurs entrées.

Comparateur d'égalité.

Le comparateur de différence[modifier | modifier le wikicode]

Le circuit qui vérifie si deux nombres sont différents peut être construit à partir du circuit précédent. Par définition, deux nombres sont différents s'ils ne sont pas égaux et réciproquement. On pourrait donc ajouter une simple porte NON à la suite d'un circuit d'égalité, ou mieux : changer la porte ET finale par une porte NAND. Mais il existe une autre solution, complétement équivalente, qui permet d'économiser l'utilisation de cette porte NON.

L'idée est de simplifier le circuit précédent de manière, ce qui permet d'éliminer des négations redondantes (la porte NON en sortie du circuit, mais aussi les négations implicites des portes NXOR). Pour cela, on applique la loi de de Morgan, qui veut que