Implementarea Algoritmului Quine - Mccluskey

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.