2. circuite logice 2.2. diagrame karnaugh

Copyright Paul GASNERCopyright Paul GASNER 1

2. Circuite logice2. Circuite logice2.2. Diagrame Karnaugh2.2. Diagrame Karnaugh


Diagrame KarnaughDiagrame KarnaughTehnică de simplificare a unei expresii în sumă minimă de produse (minimal sum of products MSP):

Există un număr minim de termeni produs în expresieFiecare termen are un număr minim de variabileImplementarea în circuit impune minimum două nivele


Diagrame KarnaughDiagrame KarnaughO funcţie de două variabile are patru posibili mintermeni. Aceştia se rearanjează într-o diagramă Karnaugh:

Mintermenii de pe coloane conţin y’ şi y respectivMintermenii de pe linii conţin x’ and x respectiv


Simplificările diagramei KarnaughSimplificările diagramei KarnaughPentru o sumă de mintermeni de două variabile:

x’y’ + x’yambii mintermeni apar în prima linie a diagramei, adică ambii

conţin x’

Simplificând expresia algebrică se obţine

x’y’ + x’y = x’(y’ + y) [ Distributivitatea ]= x’ · 1 [ y + y’ = 1 ]= x’ [ x · 1 = x ]


Alte exemple cu două variabileAlte exemple cu două variabileUn alt exemplu de expresie este x’y + xy.

ambii mintermeni apar în dreapta, adică nu sunt complementaţiAstfel, se reduce x’y + xy la y

x’y’ + x’y + xyx’y’ + x’y în prima linie, corespunzător lui x’x’y + xy în partea dreaptă, corespunzător yexpresia se reduce la x’ + y


K-map cu trei variabileK-map cu trei variabileAranjarea mintermenilor la o funcţie cu trei variabile este puţin mai complicată

sau încă o variantă


K-map cu trei variabileK-map cu trei variabileOrice grup de 2, 4 or 8 blocuri adiacente din diagramă conţine variabile comune care pot fi scoase în factor

Adiacenţele se formează “circular”


Exemplu K-map cu trei variabileExemplu K-map cu trei variabilef(x,y,z) = xy + y’z + xz.

Se converteşte expresia într-o sumă de mintermeniCel mai simplu ar fi obţinerea acesteia din tabela de adevăr sau se pot utiliza notaţiile mintermeni

f(x,y,z) = x’y’z + xy’z + xyz’ + xyz= m1 + m5 + m6 + m7


„„Complicarea” unei expresiiComplicarea” unei expresiiSe poate converti expresia într-o sumă de mintermeni utilizând algebra booleană

xy + y’z + xz = (xy · 1) + (y’z · 1) + (xz · 1)= (xy · (z’ + z)) + (y’z · (x’ + x)) + (xz · (y’ + y))= (xyz’ + xyz) + (x’y’z + xy’z) + (xy’z + xyz)= xyz’ + xyz + x’y’z + xy’z

În ambele cazuri expresia se “complică”Rezultatul este mai complex decât originalul!Având toţi mintermenii individuali, aceştia pot fi combinaţi pentru a obţine diagrama Karnaugh


Formarea diagramei KarnaughFormarea diagramei KarnaughPasul următor este desenarea şi completarea diagramei Karnaugh

Se completează cu 1 în diagramă pentru mintermi şi 0 în restSe pot utiliza atât mintermii cât şi notaţiile

În cazul nostru, f(x,y,z) poate fi scrisă în două moduri

Diagrama Karnaugh arată în final

f(x,y,z) = x’y’z + xy’z + xyz’ + xyz f(x,y,z) = m1 + m5 + m6 + m7

Yx’y’z’ x’y’z x’yz x’yz’

X xy’z’ xy’z xyz xyz’Z

Ym0 m1 m3 m2

X m4 m5 m7 m6

Z

Y0 1 0 0

X 0 1 1 1Z


Formarea diagramei Karnaugh din tabela de adevărFormarea diagramei Karnaugh din tabela de adevăr

ieşirea i din tabelă corespunde mintermenului mi în diagramă

x y z f(x,y,z)0 0 0 00 0 1 10 1 0 00 1 1 0

1 0 0 01 0 1 11 1 0 11 1 1 1

Ym0 m1 m3 m2

X m4 m5 m7 m6

Z

Y0 1 0 0

X 0 1 1 1Z


Gruparea mintermenilorGruparea mintermenilorCea mai dificilă operaţie este gruparea 1-rilor din K-map

se încercuiesc grupurile de unu, doi, patru sau opt de 1orice 1 trebuie să fie cuprins în cel puţin un grup0-urile nu se include

Fiecare grup corespunde unui termen produs. Pentru a simplifica rezultatul

trebuie obţinut numărul minim de dreptunghiuri pentru minimizarea numărului de termeni produs în expresia finalăfiecare dreptunghi trebuie să fie cât mai mare posibil pentru minimizarea numărului de litere din termenidreptunghiurile se pot suprapune

Y0 1 0 0

X 0 1 1 1Z


Determinarea MSP din K-mapDeterminarea MSP din K-mapÎn final se găseşte suma minimă de produse MSP:

fiecare dreptunghi corespunde unui termen produsprodusele sunt determinate literele comune din dreptunghi

În exemplul nostru se găseşte în final xy + y’z + xz = y’z + xy (de fapt o teoremă din algebra booleană)

Y0 1 0 0

X 0 1 1 1Z

Yx’y’z’ x’y’z x’yz x’yz’

X xy’z’ xy’z xyz xyz’Z


Exerciţiu K-mapExerciţiu K-mapSimplificaţi suma de mintermeni m1 + m3 + m5 + m6

regiunile se suprapun pentru a fi cât mai largi cu putinţăminitermenul m6 este singur

rezultatul final este x’z + y’z + xyz’

Ym0 m1 m3 m2

X m4 m5 m7 m6

Z

Y0 1 1 0

X 0 1 0 1Z


K-map cu patru variabileK-map cu patru variabileMintermenii din coloanele 3 şi 4 precum şi din liniile 3 şi 4 comută respectivAdiacenţele se formează grupând mintermenii după literele comune

Gruparea mintermenilor se face similar ca la trei variabile, dar:grupurile pot conţine 1, 2, 4, 8 sau 16 mintermiadiacenţele se formează ciclic la toate cele 4 margini

Yw’x’y’z’ w’x’y’z w’x’yz w’x’yz’w’xy’z’ w’xy’z w’xyz w’xyz’

W wxy’z’ wxy’z wxyz wxyz’X

wx’y’z’ wx’y’z wx’yz wx’yz’Z

Ym0 m1 m3 m2

m4 m5 m7 m6

W m12 m13 m15 m14X

m8 m9 m11 m10

Z


Exemplu K-map cu patru variabileExemplu K-map cu patru variabileSă se simplifice m0+m2+m5+m8+m10+m13

Se grupează mintermenii şi se obţine MSP x’z’ + xy’z

Y1 0 0 10 1 0 0

W 0 1 0 0X

1 0 0 1Z

Ym0 m1 m3 m2

m4 m5 m7 m6

W m12 m13 m15 m14X

m8 m9 m11 m10

Z

Y1 0 0 10 1 0 0

W 0 1 0 0X

1 0 0 1Z

Yw’x’y’z’ w’x’y’z w’x’yz w’x’yz’w’xy’z’ w’xy’z w’xyz w’xyz’

W wxy’z’ wxy’z wxyz wxyz’X

wx’y’z’ wx’y’z wx’yz wx’yz’Z


Diagrama Karnaugh nu este unicăDiagrama Karnaugh nu este unicăMPS nu este unică

y’z + yz’ + xy y’z + yz’ + xz

Y0 1 0 1

X 0 1 1 1Z

Y0 1 0 1

X 0 1 1 1Z

Y0 1 0 1

X 0 1 1 1Z


ExcepţiiExcepţiiUneori nu sunt necesare toate cele 2n combinaţii ale intrărilor unei funcţii de n variabile:

dacă există certitudinea că anumite combinaţii nu apar niciodatădacă anumite ieşiri nu sunt utilizate în restul circuitului

Într-o diagramă, un X poate fi interpretat ca 1 sau 0. Se ia în considerare cazul care permite simplificarea cea mai bună

x y z f(x,y,z)0 0 0 00 0 1 10 1 0 X0 1 1 01 0 0 01 0 1 11 1 0 X1 1 1 1


Exemplu: display cu 7 segmenteExemplu: display cu 7 segmenteun digit este codat pe 4 bits: ABCDla intrare avem doar cifrele de la 0 la 9pentru segmentul e avem tabela:

e

b

af

gc

d

XX0110

XXXX11

100001

100100

10110100CDAB

eDCBA

XXXXXX9876543210

X

X

X

X

X

X

01001

10001

01110

10110

01010

00010

01100

10100

01000

10000

CD’ + B’D’


Exemplu: display cu 7 segmenteExemplu: display cu 7 segmentesau pentru segmentul a:

e

b

af

gc

d

aDCBA

XXXXXX9876543210

X

X

X

X

X

X

11001

10001

11110

10110

11010

00010

11100

10100

01000

10000

XX1110

XXXX11

11101

11100

10110100CDAB

A + C + BD + B’D’


Exerciţiu K-mapExerciţiu K-mapSă se găsească MSP pentru:

f(w,x,y,z) = Σm(0,2,4,5,8,14,15), d(w,x,y,z) = Σm(7,10,13)(această notaţie semnifică neutilizarea mintermenilor m7, m10 şi m13,

corespunzători la wxyz = 0111, 1010 şi 1101)

Grupul roşu nu se ia în considerare pentru că mintermenii 'reali' din el apar în alte grupuri – grup redundantMPS este x’z’ + wxy + w’xy’

Y1 0 0 11 1 x 0 X

W 0 x 1 11 0 0 x

Z


K-map. ConcluziiK-map. ConcluziiDiagramele Karnaugh sunt utilizate la simplificarea expresiilor ca alternativă la algebra Bool

Rezultatul este suma minimă de produse MSP, care permite construirea unui circuit cu două niveleSimplitate în utilizareExpresiile cu mulţi termeni devin dificil de simplificat manual

De reţinut:Ordinea corectă a mintermenilor în K-mapLa formarea adiacenţelor se poate trece peste marginile diagramei şi grupurile formate se pot suprapuneSe formează dreptunghiuri cât mai mari posibil şi cât mai puţineExistă mai multe soluţii

2. circuite logice 2.2. diagrame karnaugh

Documents