La logique numérique : portes logiques et circuits combinatoires

Dans un circuit CMOS, chaque porte comporte deux réseaux d'interrupteurs. Les transistors P, en haut, conduisent quand leur grille est à 0 et relient la sortie à l'alimentation (1). Les transistors N, en bas, conduisent quand leur grille est à 1 et relient la sortie à la masse (0). Les deux réseaux sont construits pour être complémentaires : pour toute combinaison d'entrées, exactement l'un des deux conduit. Il n'y a donc jamais de court-circuit ni de sortie flottante, et la porte ne consomme presque rien au repos. Le NON-ET met ses transistors N en série et ses P en parallèle ; le NON-OU fait l'inverse. Le ET et le OU s'obtiennent en ajoutant un inverseur : ils sont plus coûteux que leurs versions inversées.

Le NON-ET est universel : avec lui seul, on fabrique n'importe quelle fonction logique. Relier ses deux entrées en fait un inverseur ; un NON-ET suivi d'un inverseur donne un ET ; d'après les lois de De Morgan, un NON-ET dont on a inversé les entrées donne un OU, car le complément de A·B vaut A + B. Comme le NON-ET est aussi la porte CMOS la plus simple, des circuits entiers ont été construits avec ce seul modèle de porte : l'ordinateur de guidage des missions Apollo comptait environ 5 600 portes NON-OU à trois entrées, toutes identiques ; le NON-OU est universel lui aussi.

Toute fonction s'écrit comme une somme de mintermes : un ET des quatre variables pour chaque ligne de la table qui vaut 1. C'est juste, mais coûteux. Deux mintermes qui ne diffèrent que par une variable se fondent en un seul terme sans cette variable, car X·A + X·A = X. Le tableau de Karnaugh (1953) range les 16 cases de sorte que deux cases voisines ne diffèrent que d'une variable, y compris d'un bord à l'autre : il suffit de regrouper les 1 voisins par blocs de 2, 4 ou 8. Les cases marquées × sont indifférentes (combinaisons qui n'arrivent jamais) : on peut les inclure dans un groupe si cela l'agrandit. Ici, le regroupement est calculé par la méthode de Quine et McCluskey, qui trouve tous les groupes maximaux puis choisit le plus petit ensemble qui couvre tous les 1.

L'addition binaire se pose comme à l'école : on additionne les deux bits et la retenue venue de la droite, on écrit le bit de somme et on propage une retenue vers la gauche. L'additionneur complet le fait avec cinq portes : P = A ⊕ B indique si la retenue doit être propagée, G = A·B si une retenue est générée ; la somme vaut P ⊕ C_e et la retenue sortante G + P·C_e. En chaînant n additionneurs complets, on additionne deux nombres de n bits. Mais chaque porte met un peu de temps à réagir, un délai de porte, et la retenue doit parfois traverser toute la chaîne : le résultat n'est juste qu'au bout de 2n délais dans le pire cas. Avant, les sorties peuvent changer plusieurs fois : ce sont des aléas. La simulation ci-dessous calcule chaque porte, délai après délai.

Un décodeur qui allume les segments d'un afficheur, un multiplexeur qui choisit une entrée parmi plusieurs et peut réaliser n'importe quelle fonction, et un piège que tout concepteur doit connaître : l'aléa, cette brève impulsion parasite qui naît quand deux chemins d'un même signal n'ont pas la même longueur.