Creeaza.com - informatii profesionale despre
Evidentiem nevoile sociale din educatie - Referate profesionale unice



Acasa » referate » matematica
Metode de minimizare a functiilor logice

Metode de minimizare a functiilor logice





Metode de minimizare a functiilor logice

 

            Simplificarea si implicit minimizarea functiilor logice nu este o problema pur teoretica ci depinde in mare si de tehnologia adoptata. Pe de alta parte alegerea circuitului optim din punct de vedere tehnologic este dictata de aspecte tehnice si economice ca:

            - intarzierea maxima impusa semnalelor pentru parcurgerea circuitelor logice;

            - problema hazardului ce reclama renuntarea la forma minimala si adoptarea solutiilor care elimina hazardul;

            - simplificarea constructiei in vederea unei depanari usoare.

 

            Criteriile de minimizare care s-au impus sunt:

 

            - reducerea numarului de variabile;

            - reducerea numarului de termeni;

            - reducerea pe ansamblu a variabilelor si termenilor astfel ca suma lor sa fie minima.

 

            Metode de minimizare pot fi grupate in:

                        - metode grafice;

                        - metode algebrice, dintre care se va prezenta in continuare Metoda diagramei Veitch-Karnaugh.

Metoda diagramei Veitch-Karnaugh

            Aceasta metoda se aplica functiilor logice exprimate sub forma canonica cat si a celor exprimate sub forma elementara. Metoda presupune parcurgerea a doua faze:

            1. Alcatuirea diagramei si introducerea termenilor functiei in casutele diagramei;

            2. Minimizarea propriu-zisa care rezolva doua probleme:

 

- reducerea numarului de termeni;

- reducerea numarului de variabile din termenii functiei.

 

            Prima faza comporta doua etape:

            - Etapa I. Se alcatuieste diagrama sub forma de linii si coloane suplimentate cu o linie si o coloana index. Casutele diagramei sunt in numar de 2n unde n este numarul de variabile. Diagrama Veitch-Karnaugh pentru doua variabile este prezentata in figura 3.1. Fiecare celula reprezinta o combinatie binara a variabilelor de intrare. De exemplu celula aflata pe randul unu coloana unu are valoarea binara 00 ceea ce corespunde expresiei  iar celula aflata in dreapta jos are valoarea 11 corespunzatoare lui AB.

 

   A

BA

 

AAAAAAAAAAAAAAAA

0

1

0

00

01

1

10

11

Figura Error! No text of specified style in document..1. Diagrama Veitch-Karnaugh pentru doua variabile.

Pentru n=3 se obtine diagrama cu 8 celule din figura 3.2. Valorile corespunzatoare variabilei C se gasesc pe coloana din stanga iar valorile corespunzatoare variabilelor A si B se gasesc pe primul rand. In celulele diagramei se inscriu cele 8 combinatii posibile intre variabilele de intrare.

 

 

     BA

  CBC

00

01

11

10

0

000

001

011

010

1

100

101

111

110

Figura Error! No text of specified style in document..2. Diagrama Veitch-Karnaugh pentru trei variabile.

 

Pentru n=4 se obtine diagrama:

 

 

     BA

DCDCDDD

00

01

11

10

00

0000

0001

0011

0010

01

0100

0101

0111

0110

11

1100

1101

1111

1110

10

1000

1001

1011

1010

Figura Error! No text of specified style in document..3. Diagrama Veitch-Karnaugh pentru patru variabile.

            - Etapa II. Termenii functiei canonice  complet determinate se introduc sub forma 1 sau 0 in celulele diagramei pana ce acestea se completeaza. Se introduce un 1 in celula daca termenul produs corespunzator combinatiei care caracterizeaza celula exista in expresia functiei si un 0 daca acesta lipseste. Daca functia este nedeterminata cu o nedeterminare de ordinul “r” adica exista r stari pentru care nu se cunoaste valoarea binara atunci in compartimentele necompletate se introduce variabila X care poate sa fie “1” sau  “0”. Starile nedeterminate sunt numite si stari indiferente, arbitrare sau redundante. Variabilei X i se atribuie valoarea “1” sau “0” dupa cum contribuie sau nu la formarea de grupe cat mai compacte de “1” (pentru termenii SOP) sau de “0” (pentru termenii SOP) si in numar egal cu o putere a lui 2.

            Faza a doua

            Se marcheaza prin linii continue sau intrerupte respectiv se delimiteaza suprafetele care contin celule care contin „1” (pentru forma SOP), intr-un numar egal cu 2x unde x=1n-1 pe principiul compartimentelor adiacente. Aceasta etapa rezolva problema reducerii numarului de termeni prezenti in forma initiala si care vor intra in forma minimala elementara. Se mentioneaza ca acelasi “1” poate fi introdus in mai multe grupe in virtutea legilor de idempotenta.

 

 

 

 

 

            In etapa urmatoare se transforma termenii canonici marcati anterior in termeni elementari cu mai putine variabile. Numarul de variabile dintr-un termen elementar va fi egal cu n-x.

D

C

B

A

F

0

0

0

0

1

0

0

0

1

0

0

0

1

0

1

0

0

1

1

1

0

1

0

0

0

0

1

0

1

1

0

1

1

0

0

0

1

1

1

X

1

0

0

0

X

1

0

0

1

0

1

0

1

0

1

1

0

1

1

X

1

1

0

0

0

1

1

0

1

0

1

1

1

0

0

1

1

1

1

1

Figura Error! No text of specified style in document..4

            Variabila sau variabilele care se suprima se stabilesc astfel: daca in dreptul compartimentelor cu inregistrari de “1” sau “x” grupate pe principiul casutelor adiacente, o variabila sau un grup de variabile isi modifica valoarea, atunci variabila sau grupul de variabile se suprima deoarece valorile functiei nu depind de valoarea acestei variabile. Daca exista mai multe posibilitati de grupare a inregistrarilor de “1” si “x” atunci rezulta mai multe solutii. Dintre solutiile obtinute se retine functia elementara cu numarul cel mai mic de variabile sau solutii in care suma termenilor si a variabilelor este minima. Este indicat ca minimizarea sa se faca atat prin gruparea zonelor de “1” cat si prin gruparea zonelor de “0” si in continuare compararea solutiilor. Daca zonele de “0” sunt in numar mai mic decat zonele de “1” si mai compacte se va opera cu aceste inregistrari.

 

            Daca elementele logice disponibile sunt de tipul SAU-NU (NOR) atunci se opereaza cu zonele de “0” adica se obtine forma conjunctiva elementara. Daca elementele logice disponibile sunt de tipul SI-NU (NAND) se grupeaza inregistrarile de “1” adica se obtine forma disjunctiva elementara.

 

            Exemplu: Fie functia F de 4 variabile A, B, C, D data de tabelul de adevar din figura 3.4 :

cu termenii redundanti: , si

O exprimare alternativa pentru functia de mai sus este data  de folosirea expresiilor termenilor de tip  produs care intra in definirea functiei: F = P0 + P2 + P3 + P5 + P10 + P15, cu termenii redundanti: P7, P8 si P11.  Unde P0 reprezinta termenul , P2 , etc. Implementarea directa a funcției are ca rezultat circuitul din figura 3.5

 

Figura Error! No text of specified style in document..5. Implementarea funcției F neminimizate.

           

            Pentru minimizarea funcției se poate folosi metoda diagramei Veitch-Karnaugh.

 

            Rezolvare: Pentru n=4 rezulta 24 celule astfel:

 

 

     BA

DCxxxxxxxxxxx

00

01

11

10

00

1

0

1

1

01

0

1

X

0

11

0

0

1

0

10

X

0

X

1

Figura Error! No text of specified style in document..6. Diagrama Veitch-Karnaugh pentru functia F.

 

            Se marcheaza termenii “1” in diagrama. Se cauta sa se grupeze locatiile adiacente ce contin “1” in asa fel incat sa fie acoperiti toti termenii de “1”, gruparile sa aiba suprafata cat mai mare pentru ca termenul ce corespunde gruparii sa fie cat mai simplu si sa fie cat mai putine grupari pentru a avea cat mai putini termeni. Fiecare celula ocupata de “1” trebuie sa faca parte cel putin dintr-o grupare dar poate fi inclusa in mai multe. Tipuri de grupari posibile: de o locatie, doua locatii pe o linie sau coloana, patru locatii pe linie, coloana sau patrat, opt locatii in dreptunghiuri 4x2 sau 2x4 locatii. Grupand 2m celule vecine ocupate de unitati se elimina m variabile. Gruparile obtinute sunt prezentate in figura 3.7. Se considera ca fiind celule vecine si cele aflate la extremitati. Astfel sunt vecine celulele de pe coloanele extreme (1 si 4), celulele de pe liniile 1 si 4 precum si celulele aflate in cele 4 colturi.

           

 


BA

DCxxxxxxxxxxx

   00

01

   11

   10

   00

    1

   0

    1

    1

   01

    0

   1

    x

    0

   11

    0

   0

    1

    0

   10

    x

   0

    x

    1

 

Figura Error! No text of specified style in document..7. Gruparile realizate pe principiul vecinatatii.

 

            S-au obtinut 3 grupari deci forma minimizata va contine 3 termeni, iar numarul variabilelor din fiecare termen este n-m. Astfel se obtine forma minimizata:

 

 

Figura Error! No text of specified style in document..8. Implementarea functiei F sub forma SOP.

            Functia F poate fi transformata in continuare in vederea utilizarii unui singur tip de porti prin aplicarea teoremelor lui De Morgan. Astfel se obtine:

Figura Error! No text of specified style in document..9. Implementarea functiei F cu circuite SI-NU.

            Se poate observa ca circuitele inversoare au fost inlocuite cu circuite SI-NU avand intrarile legate impreuna.

            De obicei pentru a reduce numarul de capsule utilizate se prefera utilizarea unui singur tip circuite cu acelasi numar de intrari. Functia F poate fi rescrisa folosind legile de asociativitate:

            Operatia SI dintre cei doi termeni ai primei paranteze poate fi efectuata utilizand un circuit SI-NU urmat de un inversor realizat cu un circuit SI-NU. In mod similar se poate judeca si in cazul celei de a doua paranteze. Astfel functia F devine:

Figura Error! No text of specified style in document..10. Implementarea functiei F cu circuite SI-NU cu doua intrari.

 




loading...


.com Copyright © 2017 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
 PROIECT DE LECTIE Clasa: I Matematica - Adunarea si scaderea numerelor naturale de la 0 la 30, fara trecere peste ordin
 Proiect didactic Grupa: mijlocie - Consolidarea mersului in echilibru pe o linie trasata pe sol (30 cm)
 Redresor electronic automat pentru incarcarea bateriilor auto - proiect atestat
 Proiectarea instalatiilor de alimentare ale motoarelor cu aprindere prin scanteie cu carburator

Lucrari de diploma

vezi toate lucrarile de diploma
 Lucrare de diploma - eritrodermia psoriazica
 ACTIUNEA DIPLOMATICA A ROMANIEI LA CONFERINTA DE PACE DE LA PARIS (1946-1947)
 Proiect diploma Finante Banci - REALIZAREA INSPECTIEI FISCALE LA O SOCIETATE COMERCIALA
 Lucrare de diploma managementul firmei “diagnosticul si evaluarea firmei”

Lucrari licenta

vezi toate lucrarile de licenta
 CONTABILITATEA FINANCIARA TESTE GRILA LICENTA
 LUCRARE DE LICENTA - FACULTATEA DE EDUCATIE FIZICA SI SPORT
 Lucrare de licenta stiintele naturii siecologie - 'surse de poluare a clisurii dunarii”
 LUCRARE DE LICENTA - Gestiunea stocurilor de materii prime si materiale

Lucrari doctorat

vezi toate lucrarile de doctorat
 Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
 Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
 LUCRARE DE DOCTORAT ZOOTEHNIE - AMELIORARE - Estimarea valorii economice a caracterelor din obiectivul ameliorarii intr-o linie materna de porcine

Proiecte de atestat

vezi toate proiectele de atestat
 Proiect atestat informatica- Tehnician operator tehnica de calcul - Unitati de Stocare
 LUCRARE DE ATESTAT ELECTRONIST - TEHNICA DE CALCUL - Placa de baza
 ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
 Proiect atestat tehnician in turism - carnaval la venezia




Formula dreptunghiurilor (metoda mediilor)
Prelucrarea multirata a secventelor sau schimbarea ratei de esantionare
Transformata z
Puncte de vedere in geometrie
Polinom caracteristic
Relatii binare pe o multime
Varianta (fluctuatia) dispersa sau abaterea medie patratica
Teorema limita centrala





Termeni si conditii
Contact
Creeaza si tu