Méthode de Quine-Mc Cluskey

L'algorithme se déroule en deux étapes. Pour faciliter la mise en œuvre de la méthode, la fonction logique doit être exprimée soit sous forme tabulaire (table de vérité, tableau de Karnaugh), soit sous la forme suivante :

${\displaystyle f(A_{0},...,A_{N-1})=R(N_{0},...,N_{k-1})+\Phi (M_{0},...,M_{p-1})}$

où ${\displaystyle (N_{0},...,N_{k-1})}$ sont ${\displaystyle k}$ valeurs (exprimées en binaire ou plus souvent en décimal) correspondant aux ${\displaystyle k}$ cas où ${\displaystyle f(A_{0},...,A_{N-1})}$, avec le nombre ${\displaystyle (A_{N-1}...A_{0})=N_{k}}$, vaut 1 et ${\displaystyle (M_{0},...,M_{p-1})}$ sont ${\displaystyle p}$ valeurs correspondant aux ${\displaystyle p}$ cas où ${\displaystyle f(A_{0},...,A_{N-1})}$, avec le nombre ${\displaystyle (A_{N-1}...A_{0})=M_{p}}$ est indéterminé. Par exemple, l'expression d'une porte NAND sous cette forme serait : ${\displaystyle f_{NAND}(a,b)=R(0,1,2)}$.

La première étape de l'algorithme correspond à la recherche de l'ensemble des termes générateurs. Un terme est générateur s'il ne peut être combiné avec aucun autre terme pour donner un terme plus simple.

Par exemple, dans le cas de la porte NAND, la fonction vaut 1 lorsque ${\displaystyle (ab)}$ vaut ${\displaystyle 00}$, ${\displaystyle 01}$ ou ${\displaystyle 10}$. Le terme ${\displaystyle 00}$ n'est pas un terme générateur car combiné avec ${\displaystyle 01}$, il donne naissance à un terme plus simple ${\displaystyle 0x}$. En revanche, ${\displaystyle 0x}$ ne peut être combiné avec un autre terme, c'est donc un terme générateur. De la même manière ${\displaystyle x0}$ est un autre terme générateur.

Pour trouver les termes générateurs, on utilise les valeurs ${\displaystyle (N_{0},...,N_{k-1})}$ et ${\displaystyle (M_{0},...,M_{p-1})}$ car, comme dans un tableau de Karnaugh, les termes indéterminés peuvent conduire à des simplifications.

La deuxième étape de l'algorithme correspond à l'élimination, parmi les termes générateurs, des termes redondants. Pour cela, on identifie les termes générateurs à partir desquels chaque ${\displaystyle (n_{0},...,n_{k-1})}$ peut-être écrit et on élimine ceux qui sont en trop.

Par exemple, dans le cas de la porte NAND, le terme ${\displaystyle 00}$ et ${\displaystyle 01}$ peuvent être écrit avec le terme générateur ${\displaystyle 0x}$ mais celui-ci n'est pas utilisable pour écrire ${\displaystyle 10}$. L'utilisation du second générateur ${\displaystyle x0}$ est indispensable. Il n'y a pas de terme redondant.

Pour cette étape de simplification, on ne cherche à coder que les valeurs ${\displaystyle (N_{0},...,N_{k-1})}$. Les valeurs indéterminés nous sont ici inutiles.

• Portail de la logique
• Portail de l'informatique théorique