Maîtriser les cartes de Karnaugh à 5 et 6 variables pour une conception logique efficace

À mesure que la logique combinatoire grandit, la taille de la carte de Karnaugh s'étend. Savoir quand une carte à 5 ou 6 variables est appropriée — et comment interpréter et grouper ses cellules — peut réduire dramatiquement l'utilisation logique dans les designs FPGA et ASIC.

Altera (maintenant partie d'Intel) a examiné des milliers de designs clients pour comprendre les tailles typiques de fan-in. La distribution résultante était presque plate de deux à six entrées, avec un pic net à cinq. En pratique, la plupart des circuits n'utilisent pas plus de six entrées, et le design moyen s'inscrit confortablement dans cinq.

Les propres données d'Altera, extraites de sa bibliothèque de designs clients, soutiennent la valeur de l'hétérogénéité. En examinant les cônes logiques, les mappant sur des nœuds basés sur LUT et les triant par le nombre d'entrées optimal à chaque nœud, Altera a trouvé que la distribution des fan-ins était presque plate entre deux et six entrées, avec un joli pic à cinq.

Voici une carte de Karnaugh classique à cinq variables.

Carte K à 5 variables (carte par réflexion)

Le style de réflexion plus ancien étiquette le haut (et, pour une carte à 6 variables, le côté) de la carte avec le code Gray complet. Le code Gray est mis en miroir autour du centre de la carte — une convention trouvée dans de nombreux textes classiques. Une disposition plus récente, préférée, est montrée ensuite.

Version superposée (overlay) de la K-map

La carte superposée consiste en deux sous-cartes identiques à 4 cellules, distinguées seulement par le bit de poids fort de l'adresse 3 bits en haut. La numérotation diffère de la carte par réflexion : si le chiffre de poids fort est ignoré, la séquence 00, 01, 11, 10 apparaît dans les deux sous-cartes. La séquence à 8 bits n'est pas un code Gray, mais le suffixe à 2 bits 01, 10 l'est.

Appliquons la carte à 5 variables à un vrai problème : concevoir un circuit qui accepte une entrée binaire 5 bits (A = MSB, B, C, D, E) et sort un niveau HAUT logique chaque fois que le nombre binaire est premier.

Les nombres premiers dans l'intervalle 5 bits sont (1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31). Marquez un 1 dans chaque cellule correspondante, puis groupez les uns. Terminez en écrivant l'expression simplifiée.

Dans la carte par réflexion, le groupe de 4 cellules A'B'E s'étend sur deux paires miroirs, tandis que le groupe de 2 cellules AB'DE apparaît comme une paire reflétée. En utilisant la carte superposée, cherchez les images miroirs à travers les deux moitiés.

Out = A'B'E + B'C'E + A'CDE + A'CD'E + ABCE + AB'DE + A'B'C'D

Ci-dessous est la version superposée de la même expression.

En comparant les deux cartes, certaines cellules se décalent car le schéma d'adressage diffère. Superposer une moitié sur l'autre révèle les groupes chevauchants qui guident la simplification. Par exemple, le groupe de 4 cellules A'B'E couvre le motif ABCDE = 00xx1, signifiant que A, B et E sont fixés à 0,0,1 respectivement tandis que C et D varient.

Un exemple de carte de Karnaugh à six variables suit. En empilant mentalement les quatre sous-cartes, nous pouvons identifier un groupe de 4 cellules qui implémente Out = C'F'.

Pour illustrer la carte à 6 variables, considérons un comparateur de magnitude 3 bits qui produit trois sorties : égal, supérieur, et inférieur. Le comparateur prend deux entrées 3 bits A₂A₁A₀ et B₂B₁B₀. Pour simplifier, nous ne résoudrons que la sortie A > B.

Carte K à 6 variables

La carte superposée ci-dessous aide à simplifier la logique pour la sortie A > B d'un comparateur 3 bits. Le code d'adresse binaire en haut et sur le côté gauche n'est pas un code Gray 3 bits complet, mais les codes 2 bits de chacune des quatre sous-cartes sont en Gray.

Partout où ABC dépasse XYZ, un 1 est tracé. La carte est remplie en conséquence.

Le groupement suit ces directives :

• Un groupe de 16 cellules
• Deux groupes de 8 cellules
• Quatre groupes de 4 cellules

Le groupe de 16 cellules AX' occupe la sous-carte en bas à droite. Deux groupes de 8 cellules sont formés en superposant des motifs identiques de 4 cellules des sous-cartes supérieures et inférieures. Quatre groupes de 4 cellules apparaissent dans la carte ; chacun donne un terme de produit. La réduction finale Somme-de-Produits contient sept termes.

En comptant les 1, il y a 28 uns. Avant réduction, la SOP contiendrait 28 termes de produit à six entrées chacun. La K-map réduit cela à sept termes de produit à quatre entrées ou moins — une simplification dramatique.

Le diagramme de câblage est omis, mais voici la liste de pièces pour un comparateur de magnitude 3 bits (A > B) utilisant des composants de la famille logique 4-TTL :

• 1 × 7410 triple porte NAND 3 entrées (AX', ABY', BX'Y')
• 2 × 7420 double porte NAND 4 entrées (ABCZ', ACY'Z', BCX'Z', CX'Y'Z')
• 1 × 7430 porte NAND 8 entrées (pour la sortie finale à 7 termes)

Révision

• L'algèbre de Boole, les cartes de Karnaugh et la CAO sont des outils essentiels pour la simplification logique.
• Une solution à coût minimal utilise le moins de portes avec le moins d'entrées.
• Les diagrammes de Venn aident à visualiser les expressions booléennes avant de les traduire en K-maps.
• Les cellules de K-map sont organisées en code Gray, révélant les redondances qui permettent la simplification.
• Les expressions Somme-de-Produits (SOP) sont typiquement implémentées comme des portes ET alimentant une seule porte OU.
• La SOP peut être réalisée en logique NAND-NAND en remplaçant les ET et OU par des NAND.
• Le Produit-de-Sommes (POS) est moins courant mais peut être implémenté avec des portes OU alimentant une seule porte ET, basé sur les 0 de la carte (maxtermes).