Biblioteca

Implementarea Algoritmului Quine - Mccluskey

Valoare:

5 puncte *

Marime:

21,68 Kb

Pagini:

12

Nota:
8Implementarea Algoritmului Quine - Mccluskey, 8 out of 10 based on 1 rating
Contine fisiere:

doc


Domenii:

Calculatoare


* de la numai 2.04 Lei, cumparand puncte sau poti obtine puncte daca postezi documente (vezi detalii)
Orice document downloadat sau uploadat este adaugat in Biblioteca Mea
Vezi informatii descarcari anterioare

Din cuprins:
Cuprins
Pagina 3. Descrierea algoritmului
Pagina 4. Implementarea algoritmului
Pagina 6. Codul sursa

Extras din document:

Algoritmul Quine-McCluskey
Acest algoritm este preferat pentru functii ce depind de mai mult de 5 variabile. In cazul formei disjunctive, aceasta metoda presupune parcurgerea etapelor prezentate in continuare.
1) Ordonarea echivalentilor binari ai conjunctiilor corespunzatoare valorilor 1 ale functiei dupa pondere
Ponderea conjunctiei este numarul , unde este suma algebrica.
2) Determinarea implicantilor primi prin comparatii succesive ale echivalentilor binari.
Se numeste implicant prim al unei functii un termen al acesteia care nu se mai poate reduce.
Pentru determinarea implicantilor primi se cupleaza echivalentii binari care difera doar printr-o cifra din acelasi rang. Se obtine astfel primul tabel de comparatii in care disparitia variabilei corespunzatoare cifrei care se modifica se noteaza cu -. In continuare, se pot cupla doua conjunctii din grupe vecine daca simbolul - se afla in acelasi rang si echivalentii binari difera doar printr-o cifra din acelasi rang. Rezulta al doilea tabel de comparare si procedura se repeta. Conjunctia care nu se mai poate cupla cu nici o alta conjunctie din tabel este un implicant prim al functiei date.
3) Determinarea tabelului de acoperire al functiei
Tabelul de acoperire este un tabel rectangular, la care liniile corespund implicantilor primi, iar coloanele corespund echivalentilor zecimali ai conjunctiilor pentru care functia ia valoarea 1. Tabloul se completeaza cu 1 in pozitiile pentru care conjunctiile de pe coloane realizeaza implicantii primi de pe linii.
4) Calculul formal de determinare a tuturor solutiilor functiei
Fiecarui implicant prim X i se ataseaza o variabila logica Fx care ia valoarea 1 cand implicantul prim este realizat (conform tabelului de acoperire). Pentru realizarea functiei este necesar ca in expresia ei sa existe toate conjunctiile corespunzatoare valorilor 1 ale functiei. Pentru determinarea tuturor solutiilor functiei, se exprima aceasta cerinta cu ajutorul variabilelor Fx.
Implementarea algoritmului
Algoritmul a fost implementat in Visual C++ 7. Programul lucreaza in mod asemanator unei persoane care incearca determinarea unei solutii a unei functiei date, utilizand algoritmul Quine-McCluskey.
Programul citeste de la tastatura numarul de variabile ale functiei (care este egal cu numarul de biti folosit in reprezentarea binara a conjunctiilor functiei) si numarul de termeni (conjunctii) ai functiei.
Programul returneaza implicantii primi si o solutie a functiei (in cazul in care sunt mai multe). In formatul solutiei functiei, variabila continuta intre [ ] este negata.
Ex:
Se initializeaza matricea termeni care va contine pe prima coloana, in ordinea introducerii, valorile functiei, iar pe urmatoarele nr_biti coloane reprezentarea binara a valorilor citite.
0 0 0 0 0
1 0 0 0 1
3 0 0 1 1
4 0 1 0 0
7 0 1 1 1
8 1 0 0 0
11 1 0 1 1
12 1 1 0 0
13 1 1 0 1
15 1 1 1 1
termeni
0 0 0 0 0 0
1 0 0 0 0 1
1 0 0 1 0 0
1 0 1 0 0 0
2 0 0 0 1 1
2 0 1 1 0 0
3 0 0 1 1 1
3 0 1 0 1 1
3 0 1 1 0 1
4 0 1 1 1 1
a  pagina 0
Functia dec2bin transforma valorile zecimale in valori binare, ponderea fiecarei valori in format binar (numarul de 1), si completeaza cu ele matricile termeni si a.
Functia sortare efectueaza sortarea matricei a dupa prima coloana (cea a ponderilor).
Functiile verifica_pagina, respectiv verifica_linii lucreaza pe matricea a in felul urmator: se iau, pe rand, toate combinatiile de cate doua linii, a caror pondere difera printr-o unitate, de pe pagina curenta, si se compara. Compararea verifica daca valorile binare difera pe exact o pozitie, caz in care liniile sunt marcate ca nefiind implicanti primi si valoarea corespunzatoarea acestor doua linii (cu _ pe pozitia care contine bitul diferit) este scrisa in pagina urmatoare. In acest caz se indica ciclului do  while din programul principal ca s-a creat o pagina noua in matricea a care trebuie analizata. Dupa ce se epuizeaza toate combinatiile de cate doua linii, se parcurge matricea pentru a vedea ce linii au ramas nemarcate  implicant prim  caz in care valoarea binara de pe acea linie se copie in matricea ip. Ciclul se opreste cand nu mai exista pagini noi.


    Comentarii:

    UNIVERSITATEA POLITEHNICA DIN BUCURESTI
    Facultatea de Automatica si Calculatoare



    Documente similare:
    Preview document similar
    Sistem de Gestiune a unei Librarii Folosind Reguli de Afaceri
    Proiectul contine 101 pagini in format doc cu o marime totala de 1.21 MB.
    Preview document similar
    Proiect - Record MidLet
    Proiectul contine 12 pagini in format doc, java, class, jar, mf, properties, pro, jad cu o marime totala de 1.58 MB.
    Preview document similar
    Studiul Experimental al Dirijarii Pachetelor Utilizand Algoritmul ...
    Proiectul contine 85 pagini in format doc cu o marime totala de 791.71 KB.
    Preview document similar
    Proiect ASDN
    Proiectul contine 21 pagini in format doc cu o marime totala de 585.97 KB.
    Preview document similar
    Structuri de Date si Algoritmi - Managementul unui Magazin de ...
    Cursul contine 27 pagini in format doc cu o marime totala de 55.91 KB.
    Preview document similar
    Preprocesare
    Laboratorul contine 20 pagini in format doc cu o marime totala de 490.14 KB.