Règles de regroupement dans un tableau de Karnaugh

[KFSHU]

Bonsoir,

Je m'intéresse aux motivations des règles de regroupement dans un tableau de Karnaugh, certaines sont assez évidentes d'autres un peu moins même si on sent en pratiquant que les choses ne se passent pas bien si on les respecte pas. J'ai longuement cherché sur internet mais toutes les pages exposent les règles sans en donner les motivations.

Voici une règle en particulier sur laquelle j'aimerais si possible avoir une explication :
-le nombre de case dans un groupe est une puissance de 2.



(j'ai hésité entre les sections "Logique" et "Électronique" pour poster ce message, je ne sais pas si je suis au bon endroit.)
-----

[albanxiii]

Bonjour,

La rubrique "Logique" est consacrée à la logique mathématique (théorie des ensembles, ZFC, théorie des modèles, etc.). Je déplace votre fil en électronique.

[GBo]

Bonjour,
Je ne sais pas si ça répond à la question précise, mais je peux témoigner de l'utilité de la méthode dans l'industrie.
La motivation est d'ailleurs bien explicitée dans l'article de Wikipédia:
https://fr.wikipedia.org/wiki/Table_...gh#Utilisation

"Les tables/tableaux de Karnaugh sont surtout utilisé(e)s en électronique. En effet, la simplification de l'expression algébrique booléenne permet d'économiser des opérateurs logiques (portes logiques) et donc des circuits. Elle engendre aussi une économie de temps de conception et de fonds, tout en augmentant la fiabilité de l'ensemble.

En programmation, l'utilisation des tables de Karnaugh permet de réduire les séquences de conditions de test complexes en les regroupant en des conditions non intuitives au premier abord, mais qui réduisent la complexité effective du code (volume du source), ainsi que son temps d'exécution en réduisant le nombre des évaluations nécessaires."

cdlt,
GBo

[Jack]

Je ne sais pas si ça répond à la question précise, mais je peux témoigner de l'utilité de la méthode dans l'industrie.

Salut,
tu entends quoi par "dans l'industrie"?
Karnaugh était intéressant lorsqu'on utilisait massivement des portes logiques, mais est-ce encore très utilisé?
C'est le monde de la logique programmée il me semble, basée sur du microprocesseur si la vitesse le permet, sinon du CPLD ou FPGA programmé avec les langages idoines.

[A voir en vidéo sur Futura]

[GBo]

Bonjour Jack,
Coté soft je l'ai utilisé plusieurs fois dans mon premier job de développeur logiciel pour simplifier le contenu de if() (dans du code embarqué dans des stations de base GSM d'opérateurs public comme Orange ou Chunghwa Telecom). C'est donc un témoignage personnel, je l'admets, je ne suis pas toute l'industrie, juste une infime partie .
Coté hard (FPGA), je pense que quelqu'un comme jiherve pourra sûrement mieux en parler ?

[Black Jack 2]

Bonjour,

Le nombre de "portes" dans les CPLD et FPGA est grand ... mais pas infini.

Dans des applications pointues, les circuits peuvent être utilisés près du max de leurs possibilités et donc simplifier les équations logiques (quelle qu'en soit la méthode) reste souvent très important.

[Jack]

Bonjour Jack,
Coté soft je l'ai utilisé plusieurs fois dans mon premier job de développeur logiciel pour simplifier le contenu de if() (dans du code embarqué dans des stations de base GSM d'opérateurs public comme Orange ou Chunghwa Telecom). C'est donc un témoignage personnel, je l'admets, je ne suis pas toute l'industrie, juste une infime partie .
Coté hard (FPGA), je pense que quelqu'un comme jiherve pourra sûrement mieux en parler ?

Pour simplifier un if, il m'arrive d'utiliser "de Morgan" parfois, mais pas Karnaugh. L'intérêt d'avoir une forme simplifiée dans une expression logique n'est pas aussi primordiale qu'avec une solution câblée.

[Jack]

Bonjour,

Le nombre de "portes" dans les CPLD et FPGA est grand ... mais pas infini.

Dans des applications pointues, les circuits peuvent être utilisés près du max de leurs possibilités et donc simplifier les équations logiques (quelle qu'en soit la méthode) reste souvent très important.

Les optimiseurs des compilateurs doivent faire ça très bien, non?

[GBo]

Si tu as admets que c'est utile au moins en câblé et en logique programmable contemporaine, c'est l'essentiel, mon message est passé. Ca permet en plus de dire aux étudiants que ce qu'on apprend à l'école peut être utile ensuite

EDIT : ah non, croisement, je vois que le message n'est pas passé...

[Jack]

Si tu as admets que c'est utile au moins en câblé et en logique programmable contemporaine, c'est l'essentiel, mon message est passé. Ca permet en plus de dire aux étudiants que ce qu'on apprend à l'école peut être utile ensuite

EDIT : ah non, croisement, je vois que le message n'est pas passé...

C'était utile en câblé.
En logique programmable, ça ne me semble guère utile aujourd'hui.

Ca permet en plus de dire aux étudiants que ce qu'on apprend à l'école peut être utile ensuite

Karnaugh a de vertus pédagogiques, car il est toujours bon de connaitre les principes mis en oeuvre pour la simplification d'équation, voire même le fait que des équations puissent être simplifiées

Je pense que jiherve pourra donner sa vision des choses, lui qui a connu tout ça en long, en large et en travers.

[GBo]

Pas en travers j'espère, vu sa spécialité

[jiherve]

bonsoir,
Si l'on fait de la logique câblée asynchrone c'est indispensable, en logique synchrone c'est moins vrai sauf si l'on explose les capacités de la cible et qu'il faudra y pallier.
Mais je suis un mauvais exemple car en général derrière moi le compilo VHDL ne faisait pas grand chose car ayant débuté avec des 74XX je suis resté câblé simplification au maximum et je comptais le nombre d'entrées nécessaire pour chaque fonction afin d'optimiser le "fit" sur la cible; Ce qui m'a permit de detecter qqs faiblesses dans le compilo AHDL Altera.
Aujourd'hui les développeurs FPGA écrivent à tellement haut niveau qu'ils ne perçoivent même plus le hard situé derrière mais chance pour eux les performances des FPGA ont cru de façon quasi exponentielle, avec toutefois une grosse limitation des qu'il s'agit de tirer le max de composants externes(ex DDRx), c'est la même chose en soft là ou je devais programmer en assembleur un 6809 pour assurer un minimum de performances il est aujourd'hui possible de programmer(cochon) un I7 en haut niveau et çà passe quand même.
Donc pour résumer oui il faut apprendre Karnaugh car un jour ou l'autre on sera coincé, rarement par un "no fit" mais par un composant transformé en brouette!
JR

[GBo]

Tiens, quand on parle du loup... Merci de ton témoignage jiherve !
cdlt,
GBo

[jiherve]

bonjour,
une précision la méthode Karnaugh minimise mais en évitant les glitch/aleas cela repose sur la philosophie du code Gray, ce qui explique qu'en logique synchrone elle ne soit pas indispensable car on est censé échantillonner en dehors des transitions; Le piège se trouve cependant dans les entrées de fonctions intrinsèquement asynchrones comme le sont les reset de bascules et là je ne compte plus le nombre de bugs dormants ou pas que j'ai du corriger.

JR