PorteLogique_Boole

  • Published on
    25-Nov-2015

  • View
    12

  • Download
    3

Transcript

  • Unit: Base de systmes logiques (BSL)

    Portes logiques et algbre de Boole,

    Portes logiqueset algbre de Boole

    Etienne Messerli& collgues REDS

    10 septembre 2013

    Copyright 2013 EMI, REDS@HEIG-VD p 1

    Portes logiques et algbre de Boole,

    Polycopi : Electronique numrique

    Portes logiques et algbre de Boolechapitre 4, pages 35 54

    Circuits logiques combinatoires Simplification, tables de Karnaugh

    chapitres 5-1 5-6, pages 55 64 Symboles utiliss

    chapitre 4-9, pages 46 et 47

    Copyright 2013 EMI, REDS@HEIG-VD p 2

  • Portes logiques et algbre de Boole,

    Principe de la logique (postulat)

    tre logique, cest avoir une rponse unique sans contradiction : Pas dAffirmation et de Ngation en mme temps !!! Pas de Vrai et de Faux en mme temps !!!

    Une lampe ne peut jamais tre Allume (ON) et Eteinte (OFF)en mme temps

    0OFF

    Copyright 2013 EMI, REDS@HEIG-VD p 3

    Portes logiques et algbre de Boole,

    principe de la logique (postulat)

    1ON

    tre logique, cest avoir une rponse unique sans contradiction : Pas dAffirmation et de Ngation en mme temps !!! Pas de Vrai et de Faux en mme temps !!!

    Une lampe ne peut jamais tre Allume (ON) et Eteinte (OFF)en mme temps

    Copyright 2013 EMI, REDS@HEIG-VD p 4

  • Portes logiques et algbre de Boole,

    principe de la logique (postulat)

    On voit clairement une Variable binaire :

    1ON

    1 ON

    0OFF

    0 OFF

    Copyright 2013 EMI, REDS@HEIG-VD p 5

    Portes logiques et algbre de Boole,

    Systme logique

    C'est un systme qui traite l'information de faon logique

    Pour tudier un systme logique, il faut connatre les fonctions de base (les composants) et le langage mathmatique qui permet de dcrire un comportement sous forme dquations

    Pour un additionneur: X Y Z0 0 00 1 1 1 0 11 1 0

    Z = (X, Y)

    Copyright 2013 EMI, REDS@HEIG-VD p 6

  • Portes logiques et algbre de Boole,

    Systme binaire

    Systme logique qui emploie des informations lmentaires (signaux) deux valeurs

    Avantages : on peut utiliser des interrupteurs comme lments

    de base du systme un signal binaire est plus fiable qu'un autre plus

    d'tats les dcisions prises dans un systme digital sont trs

    souvent binaires En gnral, les 2 valeurs sont reprsentes par

    les chiffres 0 et 1 (facilite le calcul arithmtique)Copyright 2013 EMI, REDS@HEIG-VD p 7

    Portes logiques et algbre de Boole,

    Dfinitions

    Etat logique : chacune des 2 valeurs que peut prendre une variable

    logique Variable logique :

    grandeur qui ne peut prendre que les 2 tats logiques Variable dentre (ou simplement entre) :

    information 2 tats reue par un systme logique Variable de sortie (ou simplement sortie) :

    information 2 tats gnre par un systme logique Fonction logique :

    relation logique entre une sortie et une ou plusieurs entres

    Copyright 2013 EMI, REDS@HEIG-VD p 8

  • Portes logiques et algbre de Boole,

    Types de systmes logiques

    Systme combinatoire : la valeur des sorties un moment donn dpend

    uniquement des valeurs des entres cet instant le comportement est entirement spcifi par une table,

    nomme table de vrit, qui pour chaque combinaison des entres donne la valeur des sorties

    pour n entres, la table de vrit comporte 2n lignes la sortie est immdiate

    Systme squentiel : la valeur des sorties dpend de la valeur des entres au

    cours du temps: il faut une mmoire l'obtention d'un rsultat peut demander plusieurs tapes,

    avec mmorisation de rsultats intermdiaires

    Copyright 2013 EMI, REDS@HEIG-VD p 9

    Portes logiques et algbre de Boole,

    Additionneur combinatoire

    X1X0Y1Y0

    Z2Z1Z0

    +

    X1 X0 Y1 Y0 Z2 Z1 Z00 0 0 0 0 0 00 0 0 1 0 0 10 0 1 0 0 1 00 0 1 1 0 1 10 1 0 0 0 0 10 1 0 1 0 1 00 1 1 0 0 1 10 1 1 1 1 0 01 0 0 0 0 1 01 0 0 1 0 1 11 0 1 0 1 0 01 0 1 1 1 0 11 1 0 0 0 1 11 1 0 1 1 0 01 1 1 0 1 0 11 1 1 1 1 1 0

    Y

    X

    Copyright 2013 EMI, REDS@HEIG-VD p 10

  • Portes logiques et algbre de Boole,

    Additionneur squentiel

    XiYi

    mmoire

    Zi

    retenue

    +

    Pour effectuer laddition, il faudra acheminer les bits des oprandes vers les entres Xi et Yi, dans le bon ordre

    Copyright 2013 EMI, REDS@HEIG-VD p 11

    Portes logiques et algbre de Boole,

    Dcomposition sortie par sortie

    Chaque bit de sortie peut tre exprim en fonction des entres indpendamment des autres

    sorties Z2 vaut 1 lorsque (X1=0 et X0=1 et Y1=1 et Y0=1)

    ou (X1=1 et X0=0 et Y1=1 et Y0=0)ou (X1=1 et X0=0 et Y1=1 et Y0=1)ou (X1=1 et X0=1 et Y1=0 et Y0=1)ou (X1=1 et X0=1 et Y1=1 et Y0=0)ou (X1=1 et X0=1 et Y1=1 et Y0=1)

    Un systme combinatoire N sorties peut tre dcompos en N systmes combinatoires une seule sortie

    X1 X0 Y1 Y0 Z2 Z1 Z00 0 0 0 0 0 00 0 0 1 0 0 10 0 1 0 0 1 00 0 1 1 0 1 10 1 0 0 0 0 10 1 0 1 0 1 00 1 1 0 0 1 10 1 1 1 1 0 01 0 0 0 0 1 01 0 0 1 0 1 11 0 1 0 1 0 01 0 1 1 1 0 11 1 0 0 0 1 11 1 0 1 1 0 01 1 1 0 1 0 11 1 1 1 1 1 0

    Copyright 2013 EMI, REDS@HEIG-VD p 12

  • Portes logiques et algbre de Boole,

    Conventions : quations logiques

    Pour abrger lcriture : Z vaut 1 lorsque remplac par Z = Y vaut 1 remplac par Y Y vaut 0 remplac par / Y linverse de remplac par / et remplac par ou remplac par + ordre de priorit : / +

    Ainsi, la sortie Z2 peut tre dcrite par lquation logique : Z2 = /X1 X0 Y1 Y0 + X1 /X0 Y1 /Y0 +

    X1 /X0 Y1 Y0 + X1 X0 /Y1 Y0 +X1 X0 Y1 /Y0 + X1 X0 Y1 Y0

    Copyright 2013 EMI, REDS@HEIG-VD p 13

    Portes logiques et algbre de Boole,

    Les portes logiques de bases

    Etude des fonctions d'une variableNous verrons la porte logique de base : NON

    Etude des fonctions de deux variablesNous verrons les portes logiques de base : ET, OUnous verrons ensuite des combinaisons : NON-ET, NON-OU OU-Exclusif

    Copyright 2013 EMI, REDS@HEIG-VD p 14

  • Portes logiques et algbre de Boole,

    4 fonctions d'une variable

    F1.0 = 0 constanteF1.1 = A transmissionF1.2 = not A = /AF1.3 = 1 constante

    VariableA01

    Fonctions F1.0 00

    F1.1 01

    F1.2 10

    F1.3 11

    Seule fonction non triviale dune seule variable :

    le NON (inversion logique)Copyright 2013 EMI, REDS@HEIG-VD p 15

    Portes logiques et algbre de Boole,

    Inverseur NON NOT

    Symbolis par un triangle pointant vers la sortie, suivi ou prcd dun petit cercle ou dune demi-flche

    La sortie du circuit est ltat logique inverse de son entre

    0 1

    Copyright 2013 EMI, REDS@HEIG-VD p 16

  • Portes logiques et algbre de Boole,

    Inverseur NON NOT

    1 0

    Symbolis par un triangle pointant vers la sortie, suivi ou prcd dun petit cercle ou dune demi-flche

    La sortie du circuit est ltat logique inverse de son entre

    Copyright 2013 EMI, REDS@HEIG-VD p 17

    Portes logiques et algbre de Boole,

    16 fonctions de deux variables ...

    F2.0 = 0 F2.4 = not A and B = /A BF2.1 = A and B = A B F2.5 = BF2.2 = A and not B = A /B F2.6 = A xor B = A BF2.3 = A F2.7 = A or B = A + B

    Copyright 2013 EMI, REDS@HEIG-VD p 18

  • Portes logiques et algbre de Boole,

    16 fonctions de deux variables

    Nous pouvons reprer les fonctions : ET (AND, intersection) = F2.1 OU (OR, runion) = F2.7

    Autre fonction logique intressante : OU-EXCLUSIF (XOR) = F2.6

    Copyright 2013 EMI, REDS@HEIG-VD p 19

    Portes logiques et algbre de Boole,

    16 fonctions de deux variables

    F2.8 = /F2.7 = /(A + B) F2.C = /F2.3 = /AF2.9 = /F2.6 = /(A B) F2.D = /F2.2 F2.A = /F2.5 = /B F2.E = /F2.1 = /(A B)F2.B = /F2.4 F2.F = /F2.0 = 1

    Copyright 2013 EMI, REDS@HEIG-VD p 20

  • Portes logiques et algbre de Boole,

    .16 fonctions de deux variables

    Les fonctions F2.8 F2.F sont respectivement les inverses des fonctions F2.7 F2.0

    3 de ces fonctions sont intressantes : NON-ET (NAND) : fonction universelle NON-OU (NOR) : fonction universelle NON-OU-EXCLUSIF (XNOR) : fonction galit

    Copyright 2013 EMI, REDS@HEIG-VD p 21

    Portes logiques et algbre de Boole,

    Porte logique ET AND

    La sortie de la porte ET est 1 si toutes les entres sont 1 . sortie ET a 1 si : a ET b ET c ET d sont 1

    a

    bc

    d

    S

    Copyright 2013 EMI, REDS@HEIG-VD p 22

  • Portes logiques et algbre de Boole,

    porte logique ET AND

    La sortie de la porte ET est 1 si toutes les entres sont 1. Il y a un seul cas :

    1

    1

    1

    1

    1

    Copyright 2013 EMI, REDS@HEIG-VD p 23

    Portes logiques et algbre de Boole,

    porte logique ET AND

    Dans les autres cas la sortie est '0'

    0000

    0

    01

    1

    1

    0

    Copyright 2013 EMI, REDS@HEIG-VD p 24

  • Portes logiques et algbre de Boole,

    Porte logique OU OR

    La sortie du circuit OU est 1 si une entre est 1. sortie OU a 1 si : a OU b OU c OU d est 1

    a

    bc

    d

    S

    Copyright 2013 EMI, REDS@HEIG-VD p 25

    Portes logiques et algbre de Boole,

    porte logique OU OR

    Si une entre est 1, la sortie est 1.

    1000

    1

    1111

    1

    Copyright 2013 EMI, REDS@HEIG-VD p 26

  • Portes logiques et algbre de Boole,

    porte logique OU OR

    Si tous les entres sont 0 alors la sortie est 0. Il y a un seul cas :

    0000

    0

    Copyright 2013 EMI, REDS@HEIG-VD p 27

    Portes logiques et algbre de Boole,

    Porte logique NON-ET NAND

    La sortie de la porte NON-ET est 1 si une entre est 0 . sortie NON-ET a 1 si : a OU b OU c OU d est 0

    a

    bc

    d

    S

    Copyright 2013 EMI, REDS@HEIG-VD p 28

  • Portes logiques et algbre de Boole,

    Porte logique NON-OU NOR

    La sortie du circuit NON-OU est 1 si toutes les entres sont 0. sortie NON-OU a 1 si : a ET b ET c ET d sont 0

    a

    bc

    d

    S

    Copyright 2013 EMI, REDS@HEIG-VD p 29

    Fonctions de base

    NON (NOT): inversion ou complment logique

    ET (AND): produit ou intersection logique

    a /a0 11 0

    a b ab0 0 00 1 01 0 01 1 1

    Copyright 2013 EMI, REDS@HEIG-VD Portes logiques et algbre de Boole, p 30

  • OU (OR): somme ou union logiquea b a#b0 0 00 1 11 0 11 1 1

    a b ab0 0 00 1 11 0 11 1 0

    Impossible dafficher limage.

    fonctions de base

    OU-exclusif (XOR) : pas une fonction de base, mais proprits intressantes

    Copyright 2013 EMI, REDS@HEIG-VD Portes logiques et algbre de Boole, p 31

    Portes logiques et algbre de Boole,

    fonctions de base

    Les fonctions ET, OU et OU-EXCLUSIF plus de 2 entres peuvent tre ralises laide des fonctions correspondantes 2 entres seulement

    3 formes : Parallle (non dcompose) Dcomposition pyramidale Dcomposition en cascade

    Copyright 2013 EMI, REDS@HEIG-VD p 32

  • Portes logiques et algbre de Boole,

    ABCD

    F

    AB

    CD

    F

    AB

    CD

    F

    Parallle

    Pyramidale

    Cascade

    fonctions de base

    Exemple : fonction ET 4 entres

    Copyright 2013 EMI, REDS@HEIG-VD p 33

    Portes logiques et algbre de Boole,

    fonctions de base

    Nous pouvons dcrire tout systme combinatoire, quel que soit son nombre dentres, avec seulement les 3 fonctions de base : inversion ET 2 entres OU 2 entres

    ou seulement avec la fonction universelle NAND 2 entres

    ou seulement avec la fonction universelle NOR 2 entres

    Copyright 2013 EMI, REDS@HEIG-VD p 34

  • Portes logiques et algbre de Boole,

    Fonctions universelles

    Un fonction est universelle lorsquelle permet la ralisation des trois fonctions logiques de base (NON, ET, OU)

    NAND

    NOR

    Copyright 2013 EMI, REDS@HEIG-VD p 35

    Portes logiques et algbre de Boole,

    Logigramme

    Logigramme = schma logique Utilise les symboles graphiques des

    fonctions usuelles (ET, OU, ) Montre les liaisons entre les entres, les

    fonctions utilises et les sorties Par convention, les signaux vont de gauche

    droite (entres gauche, sorties droite)

    Copyright 2013 EMI, REDS@HEIG-VD p 36

  • Portes logiques et algbre de Boole,

    Conventions

    A lintrieur dune fonction : logique positive (tat actif = 1)

    A lextrieur : logique mixte (tat actif indiqu)

    UNIQUEMENTen logique positive

    Bouton_Press

    nContactnAllume

    Ferme

    Logique mixte : ltat actif est prcis dans le nom

    Copyright 2013 EMI, REDS@HEIG-VD p 37

    Portes logiques et algbre de Boole,

    Exercices

    Ecrivez lquation logique des sorties Z1 et Z0 de ladditionneur 2 bits de la page 10.

    Exprimez la fonction OU-EXCLUSIF 2 entres laide des fonctions de base uniquement, dessiney le logigramme.

    Pourquoi la fonction XNOR est-elle appele galit ?

    Faites une dcomposition en pyramide dune fonction OU 4 entres, en utilisant des fonctions OU 2 entres.

    Ralisez la fonction impair 3 entres, en utilisant des fonctions OU-EXCLUSIF 2 entres.

    Dmontrez que les fonctions NAND et NOR sont universelles.

    Copyright 2013 EMI, REDS@HEIG-VD p 38

  • Portes logiques et algbre de Boole,

    Exercices

    Dessinez un schma de la fonction Z2 (pages 12 et 13), en nutilisant que des fonctions ET et OU 2 entres, ainsi que des inversions (voir symboles pages 30 et 31).

    Dessinez le schma de la fonction S2 = X1 Y1 + X1 X0 Y0 + X0 Y1 Y0en nutilisant que des fonctions ET et OU 2 entres, ainsi que des inversions.

    Dmontrez que les fonctions S2 et Z2 ci-dessus sont identiques (ont exactement le mme comportement logique)

    Copyright 2013 EMI, REDS@HEIG-VD p 39

    Portes logiques et algbre de Boole,

    Algbre de Boole : postulats

    Postulats de l'algbre de BooleA + /A = 1 (A or /A = 1)A /A = 0 (A and /A = 0)

    dcoulent de l'hypothse :l'inverse d'une variable ne peut jamais avoir la mme valeur que la variable

    Les postulats seront viols dans les circuits rels !

    Copyright 2013 EMI, REDS@HEIG-VD p 40

  • Portes logiques et algbre de Boole,

    Algbre de Boole : thormes

    I /(/A) = A thorme de linvolution not(notA) = AII A + 0 = AIII A 0 = 0IV A + 1 = 1V A 1 = AVI A + A = A idempotence de loprateur OUVII A A = A idempotence de loprateur ET

    Copyright 2013 EMI, REDS@HEIG-VD p 41

    Portes logiques et algbre de Boole,

    thormes

    VIII A + B = B + A commutativit

    IX A B = B A commutativit

    X A + (B + C) = (A + B) + C = A + B + C associativitXI A (B C) = (A B) C = A B C associativitXII A + B C = (A + B) (A + C) distributivitXIII A (B + C) = (A B) + (A C) distributivit

    Copyright 2013 EMI, REDS@HEIG-VD p 42

  • Portes logiques et algbre de Boole,

    thormes

    Thormes de De Morgan (1806-1871)XIV /(A + B) = /A /BXV /(A B) = /A + /B

    ConsensusXVI (A B) + (/A C) + (B C) = (A B) + (/A C)XVII (A + B) (/A + C) (B + C) = (A + B) (/A + C)

    Copyright 2013 EMI, REDS@HEIG-VD p 43

    Portes logiques et algbre de Boole,

    Table de vrit (TDV)

    Liste des valeurs de sortie en fonction des combinaisons des entres

    Permet de spcifier touts les tats d'une fonction logique => cahier des charges

    A

    B S

    Copyright 2013 EMI, REDS@HEIG-VD p 44

  • Portes logiques et algbre de Boole,

    Construction TDV

    Lister les combinaisons des entres N entres => 2N lignes dans la table

    Copyright 2013 EMI, REDS@HEIG-VD p 45

    Portes logiques et algbre de Boole,

    Mintermes

    On appellee minterme, ou function unit de deux variables chacun des quatre monmes de ces deux variables:

    Ceci se gnralise n variables

    Copyright 2013 EMI, REDS@HEIG-VD p 46

    F2.8 = /A /BF2.4 = /A BF2.2 = A /BF2.1 = A B

  • Portes logiques et algbre de Boole,

    Liste des mintermes d'une fonction

    Soit la TDV d'une fonction :

    Nous pouvons rsumer la TDV en donnant la liste des mintermes :

    F (C,B,A) = 0, 3, 5, 7

    0 0 0 0 1 1 0 0 1 0 2 0 1 0 0 3 0 1 1 1 4 1 0 0 0 5 1 0 1 1 6 1 1 0 0 7 1 1 1 1

    No C B A F

    Copyright 2013 EMI, REDS@HEIG-VD p 47

    Forme canonique dcimale

    Portes logiques et algbre de Boole,

    Notion de Systme

    Un systme est une collection organise d'objets qui interagissent pour former un tout

    Objets = composants du systme Interconnexions = liens entre les objets

    ncessaires pour les interactions Structure = organisation du systme

    (composants, interconnexions) Comportement = fonctionnement du systme

    (entres, sorties)Copyright 2013 EMI, REDS@HEIG-VD p 48

  • Portes logiques et algbre de Boole,

    entres sorties

    composant

    interconnexion

    Vue d'un systme

    Copyright 2013 EMI, REDS@HEIG-VD p 49

    Portes logiques et algbre de Boole,

    Analyse: Dterminer le comportement d'un systme

    partir dune description textuelle

    Conception: Dterminer la structure ncessaire qui produit

    un comportement donn. Plusieurs structures sont possibles pour obtenir

    un mme comportement (entres sorties)

    Ralisation d'un systme

    Copyright 2013 EMI, REDS@HEIG-VD p 50

  • Portes logiques et algbre de Boole,

    Solution logicielle ou matrielle

    Tout traitement ralis par un programme peut tre ralis par un composant matriel

    Solution logicielle souplesse grande capacit de traitement (beaucoup de

    donnes) lent

    Solution matrielle rapide ncessite beaucoup de matriel (composants

    logiques) temps de dveloppement important

    Copyright 2013 EMI, REDS@HEIG-VD p 51

    Portes logiques et algbre de Boole,

    Les niveaux d'abstraction

    L'abstraction se rfre la distinction entre les proprits externes d'un systme et les dtails de sa composition interne

    L'abstraction d'un systme comprend: la suppression de certains dtails pour montrer

    seulement l'essence du sujet (pour chaque niveau d'abstraction il faut pouvoir diffrencier ce qui est essentiel des dtails superflus)

    une structure une division en sous-systmes (composants)

    Copyright 2013 EMI, REDS@HEIG-VD p 52

  • Portes logiques et algbre de Boole,

    Ralit versus Abstraction

    L'abstraction est utile et ncessaire, mais il ne faut pas oublier la ralit

    Les abstractions possdent toujours des limites qu'il faut connatre

    Copyright 2013 EMI, REDS@HEIG-VD p 53

    Portes logiques et algbre de Boole,

    Exemples

    Les int (integer) ne sont pas des entiers et les float ne sont pas des rels

    Est-ce que x2 0 est toujours vrai? pour les float, oui pour les int (32 bits sign), pas toujours:

    40'000 * 40'000 1'600'000'000 50'000 * 50'000 ??

    Est-ce que (x+y)+z = x+(y+z) est toujours vrai? pour les integer, oui pour les float, pas toujours:

    (1e20 + -1e20) + 3.14 3.14 1e20 + (-1e20 + 3.14) ??

    Copyright 2013 EMI, REDS@HEIG-VD p 54

  • Portes logiques et algbre de Boole,

    Conception de systmes logiques combinatoires

    plusieurs quationssont possibles

    plusieurs logigrammessont possibles

    Cahier des charges(souvent textuelle)

    Table de vrit

    Logigramme

    Equations logiques(simplification)

    Copyright 2013 EMI, REDS@HEIG-VD p 55

    Portes logiques et algbre de Boole,

    Equation canonique dcoule directement de la TDV. Mais il peut exister des solutions quivalentes.

    Exemple: la fonction OU

    Comment simplifi la fonction => deux mthodes: algbrique (algbre de Boole) graphique (table de Karnaugh)

    B A Z

    0 0 00 1 11 0 11 1 1

    Equation logique

    solution canonique:

    Z(B,A) = BA + BA + BA

    solution simplifie:

    Z(B,A) = B + A

    Copyright 2013 EMI, REDS@HEIG-VD p 56

  • Portes logiques et algbre de Boole,

    Diagramme de Venn

    Reprsentation graphique dune fonction logiqueET: intersection OU: runion

    ETA B

    OUA B

    Copyright 2013 EMI, REDS@HEIG-VD p 57

    Portes logiques et algbre de Boole,

    Table de Karnaugh

    Forme stylise dun diagramme de Venn Chaque case correspond

    une combinaison des valeurs des entres donc un minterme donc une ligne de la table de vrit

    N entres 2N cases Dans chaque case on indique la valeur de la

    fonction 0 1 - ou => tat indiffrent

    Copyright 2013 EMI, REDS@HEIG-VD p 58

  • Portes logiques et algbre de Boole,

    table de Karnaugh

    Variables dentre indpendantes : chaque variable a une intersection avec toutes les autres variables et avec toutes les intersections des autres variables

    Fonction de 3 variables : 23 cases = 8

    A

    B CA

    C B00 01 11 10

    0

    1

    Copyright 2013 EMI, REDS@HEIG-VD p 59

    Portes logiques et algbre de Boole,

    table de Karnaugh

    Autre notation de la table

    A

    B

    C

    Copyright 2013 EMI, REDS@HEIG-VD p 60

  • Portes logiques et algbre de Boole,

    Table de Karnaugh 4 variables

    D C00 01 11 10

    00

    01

    B A

    11

    10

    Copyright 2013 EMI, REDS@HEIG-VD p 61

    Portes logiques et algbre de Boole,

    Structure de la table de Karnaugh

    Une table de Karnaugh est similaire une table de vrit:tat des sorties pour toutes les combinaisons des entres

    Dans la table de vrit, chaque combinaison des entres correspond une ligne; dans la table de Karnaugh chaque combinaison des entres correspond une case.

    Le nombre de cases table de Karnaugh d'une fonction n variables est donc gal 2n

    Les cases de la table de Karnaugh sont arranges de telle faon qu'une seule variable change entre deux cases contigus

    Toute case d'une table de Karnaugh n variables est contigu n autres cases

    Copyright 2013 EMI, REDS@HEIG-VD p 62

  • Portes logiques et algbre de Boole,

    Voici les 4 cases contigus pour la combinaison des entres DCBA

    D

    C

    B

    A

    Exemple table de Karnaugh 4 variables

    Copyright 2013 EMI, REDS@HEIG-VD p 63

    Portes logiques et algbre de Boole,

    0

    1

    2

    3

    0

    1

    2

    3

    6

    7

    4

    5

    D

    B

    A

    0

    1

    3

    2

    4

    5

    7

    6

    12

    13

    15

    14

    8

    9

    11

    10

    B

    A

    C

    A

    B

    C

    f(B,A)

    f(D,C,B,A)

    f(C,B,A)

    00 01 11 10

    00

    01

    11

    10

    DC

    BA

    Copyright 2013 EMI, REDS@HEIG-VD p 64

  • Portes logiques et algbre de Boole,

    D

    B

    A

    0

    1

    3

    2

    4

    5

    7

    6

    12

    13

    15

    14

    8

    9

    11

    10

    C

    f(E,D,C,B,A)

    D

    24

    25

    27

    26

    28

    29

    31

    30

    20

    21

    23

    22

    16

    17

    19

    18

    C

    E

    Copyright 2013 EMI, REDS@HEIG-VD p 65

    Portes logiques et algbre de Boole,

    0 4 12 8

    1 5 13 9

    3 7 15 11

    2 6 14 10

    32 36 44 40

    33 37 45 41

    35 39 47 43

    34 38 46 42

    16 20 28 24

    17 21 29 25

    19 23 31 27

    18 22 30 26

    48 52 60 56

    49 53 61 57

    51 55 63 59

    50 54 62 58

    F

    D D

    E

    B

    B

    A

    A

    C C

    f(F,E,D,C,B,A)

    Ordre D inverser!

    Ordre B inverser!

    Copyright 2013 EMI, REDS@HEIG-VD p 66

  • Portes logiques et algbre de Boole,

    Reprsentation d'une fonction

    Une fonction est reprsente l'aide d'une table de Karnaugh en mettant la valeur de la fonction l'intrieur de chaque case

    Exemple: Z(D,C,B,A) = (3,4,5,6,7,11,12,13,14,15)

    C

    D

    B

    A

    0 1 1 0

    0 1 1 0

    1 1 1 1

    0 1 1 0

    0

    1

    3

    2

    4

    5

    7

    6

    12

    13

    15

    14

    8

    9

    11

    10

    Copyright 2013 EMI, REDS@HEIG-VD p 67

    Portes logiques et algbre de Boole,

    Exemple partir d'une table de vrit:

    0

    1

    2

    3

    6

    7

    4

    5

    C

    A

    00 01 11 10

    0

    1

    B

    C B A f0 0 0 10 0 1 00 1 0 00 1 1 01 0 0 11 0 1 01 1 0 11 1 1 1

    f(C,B,A)

    1 1 1

    1

    reprsentation d'une fonction

    Copyright 2013 EMI, REDS@HEIG-VD p 68

  • Portes logiques et algbre de Boole,

    Simplification par Karnaugh

    Simplification base sur lapplication graphique de lalgbre de Boole

    AC B

    00 01 11 10

    0

    1

    1

    1

    terme /C B /A

    terme /C B A

    somme des 2 termes:

    /C B /A + /C B A =

    /C B ( /A + A ) = /C B

    groupe /C B

    Copyright 2013 EMI, REDS@HEIG-VD p 69

    Portes logiques et algbre de Boole,

    simplification par Karnaugh

    Un groupe de deux '1' adjacents (ayant une frontire commune non rduite un point) sexprime sous la forme dun produit comportant N-1 variables

    Par analogie : le groupement de deux groupes adjacents de

    deux '1' sexprime sous la forme dun produit comportant N-2 variables, etc

    Copyright 2013 EMI, REDS@HEIG-VD p 70

  • Portes logiques et algbre de Boole,

    AC B

    00 01 11 10

    0

    1

    Lexpression d'un groupe donne ses caractristiques

    Le groupe ci-dessous est caractris par le fait quil est contenu dans A mais lextrieur de C. Donc il sexprime par

    /C A

    simplification par Karnaugh

    1 1

    Copyright 2013 EMI, REDS@HEIG-VD p 71

    Portes logiques et algbre de Boole,

    D C00 01 11 10

    00

    01

    B A

    11

    10

    simplification par Karnaugh

    Expression : groupe de quatre '1'

    produit de N-2 variables

    (4-2=2) caractristiques :

    dans A et lextrieur de D /D A

    1 1

    1 1

    Copyright 2013 EMI, REDS@HEIG-VD p 72

  • Portes logiques et algbre de Boole,

    simplification par Karnaugh

    Rsum : groupe de deux '1' => produit de N - 1 variables groupe de quatre '1' => produit de N - 2 variables groupe de huit '1' => produit de N - 3 variablesfinalement : groupe de 2N '1' => 1

    un groupe est nomm: Impliquant dune fonction il s'agit du produit des variables de la fonction.

    Chaque impliquant est reprsent dans la table de Karnaugh par un groupe de cases contigus, en un nombre gal une puissance de deux

    Copyright 2013 EMI, REDS@HEIG-VD p 73

    Portes logiques et algbre de Boole,

    La table de Karnaugh permet l'obtention de l'quation minimale d'une fonction logique, sous la forme d'une somme de produits

    En effet, tout produit logique correspond un ensemble de cases contigus dont le nombre est une puissance de 2

    Si le nombre de variables de la fonction est gal n et le nombre de cases contigus est gal 2m, le produit correspondant aura seulement n-m variables

    La somme de produits minimale d'une fonction correspond donc l'ensemble minimal de groupes de cases de la table de Karnaugh o la fonction est gale 1. Le nombre de cases de chaque groupe doit tre une puissance de 2

    simplification par Karnaugh

    Copyright 2013 EMI, REDS@HEIG-VD p 74

  • Portes logiques et algbre de Boole,

    Impliquant premier:impliquant qui n'est pas inclus dans un autre impliquant plus grand.La solution minimale d'une fonction est forme seulement d'impliquants premiers. Mais tous les impliquants premiers ne font ncessairement pas partie de la solution minimale.

    Impliquant premier essentiel:impliquant premier qui contient au moins un mintermequi n'est pas inclus dans un autre impliquant premier. Un impliquant premier essentiel fait toujours partie de la solution minimale.

    Marche suivre avec Karnaugh

    Copyright 2013 EMI, REDS@HEIG-VD p 75

    Portes logiques et algbre de Boole,

    Mthode de minimisation Dresser la liste de tous les impliquants

    premiers de la fonction Dresser la liste de tous les impliquants

    premiers essentiels Tous les impliquants premiers essentiels

    font partie de la solution minimale Couvrir les mintermes restants avec un

    nombre minimal dimpliquants premiers

    marche suivre avec Karnaugh

    Copyright 2013 EMI, REDS@HEIG-VD p 76

  • Portes logiques et algbre de Boole,

    Marche suivre avec Karnaugh

    Pour trouver lexpression en somme de produits la plus simple rechercher les plus grands groupes possibles commencer par les groupes contenant des '1' isols

    '1' isol = '1' qui nentre que dans un seul groupe ajouter les groupes les plus grands qui incluent des

    '1' nayant pas encore t pris ajouter les '1' ne pouvant pas tre groups

    (= mintermes) jusqu ce que tous les '1' aient t pris un '1' peut faire partie de plusieurs groupes (1 ou 1

    = 1), mais il suffit quil soit pris une seule fois

    Rsum

    Copyright 2013 EMI, REDS@HEIG-VD p 77

    Portes logiques et algbre de Boole,

    Exercices

    Ecrivez la table de vrit, cherchez lexpression simplifie en somme de produits puis dessinez le logigramme de la fonction majorit 3 entres.MAJ = 1 si la majorit des 3 entres est 1.

    Dessinez le logigramme ci-dessus en utilisant un nombre minimum de NAND 2 entres ( lexclusion de toute autre fonction).

    Dessinez le logigramme ci-dessus en utilisant un nombre minimum de NOR 2 entres ( lexclusion de toute autre fonction).

    Copyright 2013 EMI, REDS@HEIG-VD p 78

  • Portes logiques et algbre de Boole,

    exercices

    Dessinez le logigramme le plus simple dun encodeur de priorit 4 entres, In3, In2, In1, In0. Les 4 entres sont classes par ordre de priorit de 3 (la plus prioritaire) 0 (la moins prioritaire). Une sortie 2 bits donne le numro de lentre 1 la plus prioritaire. Une sortie supplmentaire indique si une des entres au moins est 1.

    Copyright 2013 EMI, REDS@HEIG-VD p 79

    Portes logiques et algbre de Boole,

    exercices

    Donner l'quation la plus simple pour la fonction Z donne dans la table de Karnaugh ci-dessous:

    D C00 01 11 10

    00

    01

    B A

    11

    10

    0

    0

    1

    0

    1 0

    0 1 0

    1

    1 1 0

    10 1Z

    Copyright 2013 EMI, REDS@HEIG-VD p 80

  • Portes logiques et algbre de Boole,

    exercices

    Donner l'quation la plus simple pour la fonction Z donne dans la table de Karnaugh ci-dessous:

    D C00 01 11 10

    00

    01

    B A

    11

    10

    0

    0

    0

    0

    1 0

    0 1 1

    1

    1 1 1

    11 1Z

    Copyright 2013 EMI, REDS@HEIG-VD p 81

    Portes logiques et algbre de Boole,

    exercices

    Donner l'quation la plus simple pour la fonction Z donne dans la table de Karnaugh ci-dessous:

    D C00 01 11 10

    00

    01

    B A

    11

    10

    1

    1

    1

    1

    1 0

    1 0 0

    1

    0 1 0

    11 1Z

    Copyright 2013 EMI, REDS@HEIG-VD p 82

  • Portes logiques et algbre de Boole,

    Fonction incompltement dfinie

    Frquemment, il y a des combinaisons d'entrs qui ne sont pas utilises (inexistantes)

    Nous pouvons alors choisir l'tat de sortie de la fonction pour la combinaison d'entres correspondante

    Nous l'indiquerons par : - ou (tat indiffrent) Dans la table de Karnaugh, ltat indiffrent

    pourra tre considr comme 0 ou 1 Sert crer des impliquants les plus grands

    possibles

    Copyright 2013 EMI, REDS@HEIG-VD p 83

    Portes logiques et algbre de Boole,

    Valeur impaire d'un nombre BCD

    La fonction de sortie Impaire nest dfinie que pour les combinaisons BCD

    Il y a 6 combinaisons o la fonction n'est pas spcifie=> choix tat de sortie => -

    Dterminer l'quation simplifie de la fonction Impaire

    Nombre BCD Impaire0 0 0 0 00 0 0 1 10 0 1 0 00 0 1 1 10 1 0 0 00 1 0 1 10 1 1 0 00 1 1 1 11 0 0 0 01 0 0 1 11 0 1 0 -1 0 1 1 -1 1 0 0 -1 1 0 1 -1 1 1 0 -1 1 1 1 -

    Copyright 2013 EMI, REDS@HEIG-VD p 84

  • Portes logiques et algbre de Boole,

    3, 200 01 11 10

    00

    01

    1, 0

    11

    10

    Nbr_BCD

    valeur impaire d'un nombre BCD

    Copyright 2013 EMI, REDS@HEIG-VD p 85

    Portes logiques et algbre de Boole,

    Exercices

    Donner l'quation la plus simple pour la fonction P donne dans la table de Karnaugh ci-dessous:

    D C00 01 11 10

    00

    01

    B A

    11

    10

    1

    -

    0

    0

    1 0

    1 - -

    0

    - 1 0

    11 0P

    Copyright 2013 EMI, REDS@HEIG-VD p 86

  • Portes logiques et algbre de Boole,

    exercices

    Donner l'quation la plus simple pour la fonction F donne dans la table de Karnaugh ci-dessous:

    D C00 01 11 10

    00

    01

    B A

    11

    10

    0

    0

    0

    -

    1 0

    0 0 -

    1

    - 1 1

    11 -F

    Copyright 2013 EMI, REDS@HEIG-VD p 87