Journal À quoi sert un tableau de Karnaugh ?

Posté par  (site Web personnel) . Licence CC By‑SA.
Étiquettes : aucune
18
27
jan.
2017

Cher journal,

Ce matin j'ai fait découvrir à mes élèves qu'une table de vérité pouvait être pliée et devenir un objet en 2 dimensions. Et si on utilise un binaire dit réfléchi (voire de Gray), il y a plein de propriétés qui en résultent.

Voir le regard d'un gamin qui comprend une chose et qui sait qu'il l'a comprise.

Être heureux.

Du coup je me suis posé la question bête et je te la transmets, tu penses quoi des tableaux de Karnaugh, cher journal ?

Nota-Bene : je sais que tu ne les utilises jamais

NdM : corrections orthographiques à la demande de l'auteur.

  • # et Quine-McCluskey ?

    Posté par  . Évalué à 5.

    Karnaugh, c'est rigolo, mais c'est difficilement réalisable en informatique.
    A contrario, la méthode de Quine-McCluskey (que tu enseignes aussi, n'est-ce pas ?:-) est un calvaire à faire à la main, mais tellement plus facile à coder…

  • # Ce que j'en pense ? c'est un outil

    Posté par  . Évalué à 9.

    Un outils de compréhension uniquement pour l'apprentissage de la logique câblé (en tout cas je ne l'ai jamais utilisé autrement qu'en phase d'apprentissage).
    Ensuite dans ma vie professionnelle je n'en suis jamais servi, même en 92 des logiciels comme palasm rendait cette étape de factorisation "à la mano" inutile pour faire des pal/gal.
    Avec la démocratisation des fpga qui as suivie je n'en parle même pas.
    Et cela fait longtemps qu'il est plus couteux* de mettre quelques portes logique discrète qu'une logique programmable sur des produits petite-moyenne série

    (*) Par couteux c'est dans le sens évolution dans le temps du produit et ré-utilisation du même pcb validé cem et tout et tout que dans le sens prix du composant.

    Pour les pièces de série importante je comprend qu'une fois la logique mise au point on puisse vouloir passé sur des discrets (si on as de la place disponible), mais encore un fois on peut utilisé le vhdl ou le code intermédiaire de l'outil de synthèse pour réaliser son schéma (encore que les outils évolué de vhdl puisse nous afficher la synthèse vhdl sous forme de schéma directement).

    Voila pour le point de vu d'un électronicien, mais tu le savais déjà c'est marqué dans ton nb ;-)

  • # De l'utilité des termes recouvrement

    Posté par  (site Web personnel) . Évalué à 7.

    Il y a quelque chose que j'aime bien appuyer lorsque j'enseigne les tables de Karnaugh, c'est l'utilité des termes de recouvrement. Car, souvent, on dit qu'il suffit de s'arrêter lorsque tous les '1' sont couverts. Ce qui est juste, et ce qui permet d'exprimer l'équation en forme normale disjonctive (FND).

    Sauf que si les groupes de '1' sont disjoint, le système peut connaître une instabilité lorsqu'on passe de l'un à l'autre de ces groupes. Imaginez que notre implémentation de porte NON ait une légère latence lors du basculement de son entrée, alors l'expression booléenne \overline{a} + a pourrait valoir faux pendant un court instant lorsque a passe de vrai à faux.

    De même la fonction booléenne f(a,b,c)=\overline{a}b+ac pourrait être instable lorsque a passe de vrai à faux. Mais si on rajoute le terme de recouvrement f(a,b,c)=\overline{a}b+ac+bc, la fonction reste vraie, même lorsque a varie. Et ce qui est bien avec Karnaugh, c'est que le recouvrement est très visuel.

    Parfois, je présente ça à mes étudiants en faisant l'analogie avec un assemblage hyperstatique en mécanique (faut dire aussi, que j'enseigne dans une école de mécanique). Pourquoi une chaise a-t-elle généralement quatre pieds, alors bien que trois points suffisent à faire une liaison avec le plan du sol ? Une chaise à trois pieds, c'est certes isostatique, mais dans la pratique, c'est plus casse-gueule ! Donc, il existe des cas dans lesquels on est prêt à payer le coût de l'hyperstaticité (un pied de chaise en plus, c'est pas gratuit), et même de ses inconvénients (ça sera forcément bancal).

    Mais, quand même, on est plus serein quand on s'assoit dessus :-)

    • [^] # Re: De l'utilité des termes recouvrement

      Posté par  (site Web personnel) . Évalué à 0. Dernière modification le 29/01/17 à 04:07.

      Tu notes qu'un trépied est effectivement isostatique, sans prendre en compte le centre de gravité : plus c'est bas, plus c'est mieux, ce en quoi le quadri-pied résiste mieux au centre de gravité plus haut (même si bancale, c'est moins casse-gueule qu'un trépied)

      J'ai beau avoir fait une école d'ingénieur généraliste, j'ai apparemment sans doute passé autant de temps que toi sur le zinc ('fin le coude sur le zinc, une pression patron !) au vu de ton commentaire. En réalité, j'ai passé plus de trois ans derrière le zinc, mais j'en parlerais plutôt IRL que de laisser des traces sur le ternet :-)

      Il n'y a pas que la méca, la RDM, la ruine des matériaux et autres sujets accessoirement fâcheux ou intéressants, il y a aussi le principe de réalité et l'expérience (heureusement accessible à tout le monde, ce qui permet à tout un chacun de tolérer ce genre de commentaire, lisible et compréhensible par tout un chacun) et c'est bien : cela rend abordable le bon sens, que chacun peut comprendre (ceux qui ont essayé des échasses ou les assistances au déplacement : plus le centre de gravité est bas, plus c'est stable, sinon faut être doué ou s'entraîner :D comme pour les déplacements en roue ou skate motorisé, j'ai essayé hein)

      bref : 4 pieds c'est mieux

  • # Qu'est-ce ?

    Posté par  . Évalué à 7.

    Bonjour finss,
    Je ne comprends pas très bien le "une table de vérité pouvait être pliée et devenir un objet en 2 dimensions". Pourrais-tu préciser, ou donner un lien qui explique le concept ?

    • [^] # Re: Qu'est-ce ?

      Posté par  . Évalué à 7.

      Perso je ne capte rien non plus, et le nombre de lien du journal ne me donne pas envie de chercher.

      Qu'est-ce qu'une table de vérité ? Où est-ce qu'on s'en sert en informatique ? Pour des if (a and b) or ((b or c) and (b or c)) and ((a or c) and (b or c)): ?

      Y a vraiment des codes comme ça ? Et du coup qu'est-ce qu'un tableau de Karnaugh ? A quoi cela sert-t-il ? Est-ce que ça se code ou bien on le fait sur un papier lors de la conception de notre boucle if pour minimiser le nombre de caractère de la ligne ?

      C'est frustrant que tu expliques cela à tes élèves mais pas à nous.

      • [^] # Re: Qu'est-ce ?

        Posté par  (site Web personnel) . Évalué à 1.

      • [^] # Re: Qu'est-ce ?

        Posté par  . Évalué à 4.

        Oui les tables de vérités ça sert en informatique, et beaucoup en "informatique matérielle" (programmation de microcontrôleurs) : Fonction logique.
        Par contre je ne comprends pas le concept de plier une table de vérité pour en faire un objet en deux dimensions, vu que c'est déjà un objet en deux dimensions.

        • [^] # Re: Qu'est-ce ?

          Posté par  (site Web personnel) . Évalué à 7.

          Par contre je ne comprends pas le concept de plier une table de vérité pour en faire un objet en deux dimensions, vu que c'est déjà un objet en deux dimensions.

          Une table de vérité classique se représente sous forme de tableau à une entrée (sous forme de colonnes, généralement), une table de Karnaugh est une table à deux entrées (lignes et colonnes). Une ligne dans une table de vérité correspondra à une case dans la table de Karnaugh.

          Exemple : une fonction à quatre atomes f(a,b,c,d) se représente soit sous la forme d'une table de vérité à 2^4=16 lignes, soit sous la forme d'une table de Karnaugh de taille 4\times 4. On retrouve exactement le même nombre d'information. Mais l'organisation des lignes et des colonnes a la propriété suivante : le passage entre deux lignes adjacentes doit produire le changement d'un et un seul atome à la fois. De même pour les colonnes. Et on considère que les lignes extrêmes sont également adjacentes (de même que les colonnes). D'où l'aspect circulaire, ou cylindrique de la représentation.

          Il existe plusieurs manière de disposer les atomes sur les lignes et les colonnes. Une des manière de faire est d'utiliser le binaire réfléchi ou code de Gray : 000, 001, 011, 010, 110, 111, 101, 100, etc. Si on observe bien ces nombres, un seul chiffre varie lorsqu'on passe d'un nombre au suivant. La propriété nécessaire aux tables de Karnaugh est donc bien vérifiée.

          L'avantage de cette disposition, c'est qu'elle permet de visualiser plus simplement l'influence de la variation d'une seule variable à la fois, ce qui peut conduire à des simplifications de l'expression.

  • # Rarement suffisant

    Posté par  (site Web personnel) . Évalué à 6.

    Les tables de Karnaugh, ça permet d'optimiser uniquement avec des "et" et des "ou". Dans la plupart des cas, on a une situation un peu différente:
    - Dans les PAL/GAL et FPGA, on a plutôt des portes AOI (And-Or-Invert).
    - En logique discrète on a tout plein d'outils: XOR, NAND, NOR, et même des trucs vachement plus intégrés. Bien souvent on peut faire plus compact en utilisant un démultiplexeur (un 74xx138, c'est jusqu'à 6 entrées et plusieurs combinaisons possibles pré-décodées en sortie) et éventuellement quelques inverseurs.
    - En informatique, il vaut mieux écrire les conditions dans une forme lisible, que dans une forme optimisée, et laisser le compilateur faire son travail.

    Cela dit, ça n'empêche pas que la table de Karnaugh permet de comprendre un peu comment ça marche, tout ça. Et c'est bien, parce que c'est simple.

    • [^] # Re: Rarement suffisant

      Posté par  (site Web personnel) . Évalué à 7.

      C'est clair que Karnaugh ne donne pas toujours la solution optimale.

      Un exemple que je donne en exercice à mes étudiants est la réalisation d'un circuit comparateur n-bits. Je leur fais d'abord faire un comparateur 2-bits en synthétisant les sorties à l'aide d'une table de Karnaugh. Dans un second temps, je leur fais faire un simple comparateur 1-bit, et on cherche comment fabriquer la version 2-bits en en combinant deux ensemble.

      En comparant les deux solutions, on voit que la deuxième approche est à la fois meilleure pour minimiser le nombre de portes utilisées et en terme de profondeur de circuit (nombre de portes traversées entre l'entrée et la sortie dans le pire cas).

      Moralité : Karnaugh fournit une forme normale disjonctive (en mathématiques du collège on dirait, la forme développée réduite d'une équation). Ça ne garantie en rien qu'il n'existe pas de meilleure solution par ailleurs.

      À vrai dire, le plus difficile dans ce type de cours, c'est de parler de "comparateur deux bits" sans déclencher un rire général dans la classe :-)

  • # C'est cool les tableaux de Karnaugh !

    Posté par  . Évalué à 5.

    Du coup je me suis posé la question bête et je te la transmets, tu penses quoi des tableaux de Karnaugh, cher journal ?

    Je pense que c'est super cool, c'est une parfaite illustration que quand on part d'un système compliqué, si on arrive à y trouver de la structure, on a déjà fait une grande partie du boulot. Si on a un système à N variable booléenne qui en produit une, et où modifier valeur d'une variable modifie (ou pas) la valeur de sortie, sans logique apparente, ça a l'air impossible à traiter.

    Et pourtant… La représentation du comportement de ce système dans un objet en deux dimensions bien choisi (on va pas prendre les entiers ordonnés avec l'ordre naturel) va permettre d'exhiber une sorte de monotonie locale de ce système. Et on va se rendre compte que le système peut être décrit par l'union de ces choses locales.

    Devant un système complexe, le repérage et la compréhension des mécanismes simples et locaux sont indispensables. Dans toutes les sciences. Les tableaux de Karnaugh c'est une version binaire de la recherche des variables indépendantes en statistique par exemple.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.