L03 Diagrama VK

Laborator 03 2014/2015

1. MINIMIZAREA FUNCŢIILOR LOGICEFĂRĂ TERMENI REDUNDANŢI

Diagrama VK pentru o funcţie de 4 variabile:

Exerciţii: Să se minimizeze funcţiile: 1.

Utilizarea diagramei VK la minimizarea funcţiilor logice implică parcurgerea următoarelor etape: a). se înscrie valoarea logică a termenilor funcţiei în diagramă (se trece câte un 1 în dreptul celulelor al căror termen apare în dezvoltarea funcţiei). 0 nu se trece niciodată în diagramă. b). se formează grupuri de termeni vecini doi câte doi între ei. Numărul de termeni dintr-un grup trebuie să fie o putere întreagă a lui 2. Pentru a citi direct de pe diagramă valoarea minimă a funcţiei logice se constituie cele mai mari grupuri posibile. c). valoarea minimă a unui grup este dată de produsul variabilelor comune grupului. Dacă s-au format mai multe grupuri, valoarea minimă a funcţiei este suma valorilor minime ale grupurilor constituite.

2. 3.

1

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

B

A

D

C

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

B

A

D

C1 11111sssds11211 11 12111

1 11111 1

DCA

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

B

A

D

C111111 1

111111 1

111111 1

111111 1

CA

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

B

A

111111 1

111111 1

111111 1

111111 1

C

D

CA


4. 5.

6.

Observaţie:Nu se formează toate grupuri posibile!Se formează numai grupurile care au cel

puţin un element propriu.Grupurile fără element propriu nu

se iau în considerare. Ele se numesc grupuri redundante.

7.

Observaţie: Este obligatoriu ca un element să facă parte dintr-un grup, dar dacă e nevoie, el poate să facă parte din mai multe grupuri. Fiecare grup, însă, va trebui să aibă cel puţin un element propriu.

8.

2

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

B

A

D

C

111111 1

111111 1

111111 1

111111 1

BA

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

B

A

D

C

111111 1

111111 1

111111 1

111111 1

CA

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

B

A

D

C111111 1

111111 1

111111 1

111111 1

DCA CBA

DBA

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

B

A

D

C

111111 1

111111 1

111111 1

111111 1

DCA DCB

DBA

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

B

A

D

C111111 1

111111 1

111111 1

111111 1

111111 1

111111 1

111111 1

CA

DB


9.

Exerciţii:1. Se dă funcţia . Se cere:

a.) să se minimizeze cu diagrama VK; b.) să se implementeze utilizând un număr minim de porţi SAU-EXCL şi ŞI-NU cu două intrări; c.) să se implementeze utilizând un număr minim de porţi SAU-EXCL, SAU cu două intrări şi SAU-NU cu două intrări.

a).

Forma minimă este:

b). Se implementează funcţia adusă la forma:

Sunt necesare două porţi SAU-EXCL şi patru porţi ŞI-NU cu două intrări (poarta care realizează inversarea variabilei D poate fi şi de tip SAU-EXCL).

c). Se implementează funcţia adusă la forma:

Sunt necesare două porţi SAU-EXCL cinci porţi SAU-NU şi o poartă SAU cu două intrări (porţile folosite pe post de inversoare se pot realiza şi cu porţi SAU-EXCL).

3

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

D

C

111111 1

111111 1

111111 1

111111 1

111111 1

111111 1

111111 1

111111 1

A

B

C

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

B

A

D

111111 1

111111 1

111111 1

111111 1

DCA

111111 1

111111 1

111111 1

111111 1

C

DCA

DBA

DBA

B

AC

D

CA

D

BA

FCAD

BAD

BA

C

D

BA

D

CA

FBAD

CAD

BA

CA


2. Se dă funcţia . Se cere să se minimizeze cu diagrama VK şi să se implementeze folosind un număr minim de porţi ŞI-NU cu 3 intrări.

a.) Temă Se minimizează şi se implementează ultima formă. b). Se minimizează direct, cu diagrama VK, funcţia scrisă în forma canonică conjuctivă negând fiecare variabilă şi înlocuind funcţiile ŞI şi SAU între ele.

Varianta 1 Varianta 2

Forma minimă este:

Implementarea se realizează cu şapte porţi ŞI-NU cu trei intrări în ambele variante. Spre exemplificare s-a implementat a doua variantă.

Temă: 2.14, 2.15, 2.19, 2.20

4

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

DC

111111 1

111111 1

111111 1

111111 1

111111 1 B

A

CBA

DBA

CBA

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

DC

111111 1

111111 1

111111 1

111111 1

111111 1 B

A

CBA

DCA

CBA

ABAC

D

B

C

ABC

CBA

ACDF


2. MINIMIZAREA FUNCŢIILOR LOGICECU TERMENI REDUNDANŢI

Termenii redundanţi sunt acei termeni care pot exista în principiu ca şi combinaţie liniară între variabile, dar a căror valoare logică nu ne interesează. Ei se notează cu X, se trec în diagrama VK şi ne ajută să formăm grupuri cât mai mari. Nu este obligatoriu să luăm în grupuri toţi termenii redundanţi.

În cazul în care se pot forma grupuri în mai multe moduri, se vor forma acelea care conţin mai mulţi termeni ai funcţiei (mai mulţi de „1”).

1. Se consideră funcţia cu termenii redundanţi P0, P9, P10, P15. Se cere: a.) să se minimizeze cu diagrama VK, folosind atât gruparea de 1 cât şi gruparea de 0; b.) să se implementeze utilizând un număr minim de porţi ŞI-NU cu două intrări; c.) să se implementeze utilizând un număr minim de porţi SAU-NU.

a). A minimiza o funcţie ţinând cont de gruparea de „1” înseamnă a minimiza funcţia F.


Forma minimă obţinută este:

A minimiza o funcţie ţinând cont de gruparea de „0” înseamnă a minimiza pe . conţine toţi termenii care nu aparţin lui F şi nu sunt nici redundanţi:

.

Forma minimă obţinută este:

b.) (8 porţi ŞI-NU cu două intrări)

5

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

B

A

111111 1

X 11111 1

111111 1

111111 1

111111 1

111111 1

111111 1

111111 1

X 11111 1

X 11111 1

X 11111 1

C

D

DB

CA

DC

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

D

C

111111 1

111111 1

111111 1

111111 1

111111 1

X 11111 1

X 11111 1

X 11111 1

X 11111 1

A

B

DC

CB

DA

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

D

C

111111 1

111111 1

111111 1

111111 1

111111 1

X 11111 1

X 11111 1

X 11111 1

X 11111 1

A

B

CB

DA

CA


(7 porţi ŞI-NU cu două intrări)

respectiv: (10 porţi ŞI-NU cu două intrări)

Obs: Numărul de porţi se poate reduce dacă se poate da factor comun o variabilă! (6 porţi ŞI-NU cu două

intrări)

(6 porţi ŞI-NU cu două

intrări)

Se poate implementa oricare din ultimele două variante. Se exemplifică prima variantă:

c.) (7 porţi SAU-NU)

(8 porţi SAU-NU)

(5 porţi SAU-NU)

2. Se consideră funcţia cu termenii redundanţi P10, P11, P12, P13, P14, P15. Se cere:

a.) să se minimizeze cu diagrama VK; b.) să se implementeze utilizând un număr minim de porţi SAU cu două intrări, ŞI cu două intrări şi SAU-EXCL.

a).

Forma minimă obţinută este: b). Implementarea se realizează cu două porţi SAU-EXCL şi două porţi SAU.

6

DA

B

C

B

C CBA

AD

BA F

F

A

D

C

B

C

DB

DC

CA

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

D

C

1

A

B

B

D

CA11

1 11

1 1

X

X X

X X X

CA


3. Se dă funcţia cu termenii redundanţi P1, P4, P8, P14. se cere: a.) să se minimizeze cu diagrama VK; b.) să se implementeze cu un număr minim de porţi ŞI-NU cu 3 intrări.

a). Minimizarea funcţiei F: Minimizarea funcţiei :

Se obţine:

b). Implementarea presupune utilizarea a şapte, respectiv a şase porţi ŞI-NU cu trei intrări. Se preferă ultima variantă.

PROBLEME RECOMANDATE

4. Se consideră funcţia cu termenii redundanţi P0, P4, P7, P10, P15. Se cere:

a.) să se minimizeze cu diagrama VK b.) să se implementeze folosind un nr. minim de porţi SAU EXCLUSIV, porţi ŞI cu 2 intrări şi porţi SAU cu 2 intrări.

a). Se obţine:

7

FDB

CACA

"1"ACBD

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

D

C

1

A

B

1

1

1

1

1

1

X

X

X

1 X

CA

BA

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

1

1

1

1

1X

X

X

X

CAB

C

D

CA

A

B

F

ABC

A

C

CA

CAB

F

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

B

A

D

C

X

X

X

X

X

11

11

1

11

DB DB

CA

CA


b). Se implementează forma:

5. Se consideră funcţia cu termenii redundanţi P4, P5, P8, P10, P14. Se cere: a.) să se minimizeze cu diagrama VK; b.) să se implementeze utilizând un număr minim de porţi SAU cu două intrări, ŞI cu două intrări şi SAU-EXCL.

a).

b). Implementarea este identică cu cea de la problema precedentă.

6. Se consideră funcţia cu termenii redundanţi P10, P11, P12, P13, P14, P15. Se cere:

a.) să se minimizeze cu diagrama VK; b.) să se implementeze utilizând un număr minim de porţi SAU cu două intrări, ŞI-NU cu două intrări, SAU-NU cu două intrări şi SAU-EXCL.


respectiv:

Ambele variante se implementează cu cinci porţi (de exemplu: 1xSAU-NU, 1xSAU-EXCL, 3xŞI-NU).

Temă: 2.25, 2.26, 2.27, 2.28, 2.29, 2.30, 2.32, 2.37, 2.38, 2.41

8

F

AC

BD

CA

DB „1”

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

B

A

D

C

1

X

1

X

1

X1

1X

X

11

DB DB

CA

CA

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

D

C

CB

D

BA

11

1 11

1 1

X

X X

X X X

CB

B

A

8 9 11 10

12 13 15 14

4 5 7 6

0 1 3 2

CB

D

CA

11

1 11

1 1

X

X X

X X X

B

D

ACB

C

L03 Diagrama VK

Documents

Transcript of L03 Diagrama VK