Table de Karnaugh

Une table de Karnaugh (prononcé ) est une méthode graphique et simple pour trouver ou simplifier une fonction logique à partir de sa table de vérité. Elle utilise le code de Gray (aussi appelé binaire réfléchi), qui a comme propriété principale de ne faire varier qu'un seul bit entre deux mots successifs (la distance de Hamming de deux mots successifs du code de Gray est égale à 1). Cette méthode a été développée par Maurice Karnaugh en 1953, en perfectionnant un diagramme similaire introduit en 1952 par . Un tableau de Karnaugh peut être vu comme une table de vérité particulière, à deux dimensions, destinées à faire apparaître visuellement les simplifications possibles. Supposons ou variables : on assignera par exemple ou variables au repérage des lignes, les autres variables au repérage des colonnes. Chaque case élémentaire correspond alors à une seule ligne et à une seule colonne, donc à une seule combinaison des variables. Examinons le cas d'une fonction des quatre variables A, B, C, D, les variables A et B étant assignées aux lignes, C et D aux colonnes de la table ci-dessous. Cette table est proche du diagramme de Veitch antérieur. Pour rendre plus évidentes les simplifications cherchées, Karnaugh propose, pour la succession des valeurs données à C et D, ainsi qu'à A et B, d'employer un code de Gray, de sorte que les valeurs de deux repères consécutifs ne diffèrent que par la modification d'une seule variable, et fasse apparaître des symétries utiles. Ainsi : La colonne 1 correspond aux valeurs de S pour et , ou La colonne 2 correspond aux valeurs de S pour et , ou La colonne 3 correspond aux valeurs de S pour et , ou La colonne 4 correspond aux valeurs de S pour et , ou La ligne 1 correspond aux valeurs de S pour et , ou La ligne 2 correspond aux valeurs de S pour et , ou La ligne 3 correspond aux valeurs de S pour et , ou La ligne 4 correspond aux valeurs de S pour et , ou . Alors, on assigne à la case de la ligne 4, colonne 2 la valeur de quand et . Cette valeur peut être trouvée dans la table de vérité ou par une équation à simplifier.