Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Systèmes électroniques numériques

Algèbre de Boole, formes canoniques et tables de Karnaugh

Opérations et théorèmes de l'algèbre de Boole, De Morgan avec démonstration, sommes de produits et produits de sommes, tables de Karnaugh avec un exemple complet, conditions indifférentes.

https://www.electronics-engineering.com/fr/algebre-de-boole-formes-canoniques-tables-de-karnaugh/

Pas encore de vote : soyez le premier à noter cette page.

Les circuits numériques ne travaillent qu’avec deux valeurs, 0 et 1, et leur comportement se décrit par l’algèbre de Boole. Concevoir un réseau logique, c’est écrire la fonction qu’il doit calculer et la simplifier, car une expression plus courte demande moins de portes, moins de surface, moins de puissance et moins de retard. Dans cette leçon, nous traitons les axiomes et les théorèmes de l’algèbre de Boole, les formes canoniques et la méthode des tables de Karnaugh.

Opérations et théorèmes

Les opérations de base sont le produit logique (AND, A\cdot B ou AB), la somme logique (OR, A + B) et la négation (NOT, \overline{A}). Les propriétés commutative, associative et distributive sont valables, avec une surprise : dans l’algèbre de Boole, les deux opérations sont distributives, y compris A + BC = (A + B)(A + C). D’autres identités utiles :

NomForme ORForme AND
identitéA + 0 = AA\cdot 1 = A
élément absorbantA + 1 = 1A\cdot 0 = 0
idempotenceA + A = AA\cdot A = A
complémentA + \overline{A} = 1A\cdot\overline{A} = 0
absorptionA + AB = AA(A + B) = A
De Morgan\overline{A + B} = \overline{A}\,\overline{B}\overline{AB} = \overline{A} + \overline{B}

Chaque identité a un dual, obtenu en échangeant AND et OR, et 0 et 1.

Théorème (De Morgan). \overline{A + B} = \overline{A}\cdot\overline{B}.

Démonstration. Avec deux variables, il n’y a que quatre cas et il suffit de les vérifier tous (démonstration par exhaustion, toujours possible dans une algèbre à un nombre fini de valeurs) : pour A = B = 0, les deux membres valent 1 ; dans les trois autres cas, au moins une variable vaut 1, donc A + B = 1 et le membre de gauche vaut 0, et celui de droite aussi, parce qu’au moins un des deux facteurs niés vaut 0. ∎

De Morgan a une conséquence pratique fondamentale : avec des portes NAND seules (ou NOR seules), on peut réaliser n’importe quelle fonction, et c’est exactement ainsi que sont faites les portes CMOS (leçon de dispositifs électroniques sur la logique CMOS).

Formes canoniques

Toute fonction peut s’écrire à partir de sa table de vérité.

  • Somme de produits (SOP) : pour chaque ligne où la fonction vaut 1, on écrit le produit des variables, niées là où elles valent 0 (un minterme), et on les additionne tous. On l’abrège avec la liste des numéros de ligne : f = \sum m(\dots).
  • Produit de sommes (POS) : le dual, en partant des lignes où la fonction vaut 0.

La forme canonique est correcte mais longue : une fonction de 4 variables avec 8 mintermes demande 8 portes AND à quatre entrées et un OR à huit entrées.

Tables de Karnaugh

L’idée de simplification est le théorème AB + A\overline{B} = A : deux mintermes qui ne diffèrent que d’une variable fusionnent, et cette variable disparaît. La table de Karnaugh dispose la table de vérité sur une grille où les cases adjacentes ne diffèrent que d’une variable : lignes et colonnes suivent le code de Gray (00, 01, 11, 10), et les bords opposés sont aussi adjacents, comme si la table était enroulée sur un tore.

Table de Karnaugh à quatre variables avec deux regroupements
Les lignes correspondent à AB et les colonnes à CD, toutes deux en code de Gray. Les 1 des quatre coins forment un seul groupe, parce que les bords opposés sont adjacents, et donnent le terme B-barre fois D-barre ; le bloc central de quatre 1 donne le terme BD. La fonction simplifiée est la somme des deux termes.

La procédure.

  1. On inscrit les 1 de la fonction dans les cases.
  2. On regroupe les 1 en rectangles de 1, 2, 4, 8… cases adjacentes, les plus grands possible ; un 1 peut appartenir à plusieurs groupes.
  3. Chaque groupe de 2^k cases élimine k variables : celles qui ne changent pas dans le groupe restent.
  4. La fonction est la somme des termes des groupes, choisis en nombre minimal pour couvrir tous les 1.

Exemple. f(A, B, C, D) = \sum m(0, 2, 5, 7, 8, 10, 13, 15). Les mintermes 5, 7, 13, 15 forment un carré au milieu de la table : dans tous, B = 1 et D = 1, tandis que A et C changent, donc le groupe est BD. Les mintermes 0, 2, 8, 10 sont aux quatre coins, qui sont adjacents entre eux : ils ont B = 0 et D = 0, et donnent \overline{B}\,\overline{D}. Donc

    \[ f = \overline{B}\,\overline{D} + BD \]

c’est-à-dire que la fonction vaut 1 quand B et D sont égaux : c’est le complément d’un XOR, \overline{B \oplus D}. Huit mintermes à quatre variables se réduisent à une seule porte XNOR.

Conditions indifférentes. Souvent, certaines combinaisons d’entrée ne peuvent pas se produire (par exemple les codes 10 à 15 dans un circuit qui reçoit des chiffres décimaux BCD). On les marque d’un X sur la table et on peut les traiter comme 1 ou comme 0, selon ce qui aide à former de plus grands groupes.

Au-delà des tables

Les tables fonctionnent bien jusqu’à 4 ou 5 variables. Pour les fonctions plus grandes, on utilise des algorithmes (Quine-McCluskey, Espresso), qui vivent aujourd’hui à l’intérieur des outils de synthèse logique : le concepteur décrit la fonction dans un langage comme VHDL ou Verilog (leçon sur les FPGA) et le programme trouve le réseau de portes, en optimisant surface, retard et puissance.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x