forked from GehadSalemFekry/Boolean-Functions-Simplifier
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathQmAlgo.cpp
200 lines (157 loc) · 6.99 KB
/
QmAlgo.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include "QmAlgo.h"
QmAlgo::QmAlgo(int variables, vector<int>& minterms, vector<int>& dontcares){
this->variables = variables;
for(int min: minterms){
Implicant imp(variables, min);
IMPLICANTS[imp]=false;
TERMS[min]=true;
}
for(int dont: dontcares){
Implicant imp(variables, dont);
IMPLICANTS[imp]=false;
TERMS[dont]=false;
}
}
void QmAlgo::reduce(){
// map to store the minImplicants and don't care values
map<Implicant, bool, comparatorImp> merged = IMPLICANTS;
while (!merged.empty()) {
map<Implicant, bool, comparatorImp> newlyMerged;
for (auto &cur : merged) {
Implicant imp = cur.first; // to change its bits and check its availability in the map
for(int i = 0; i < variables; i++) {
Implicant temp = imp;
if(imp[i] == '0') {
temp.changeBit(i);
// check if the implicant exists
if(merged.count(temp)) {
string newBinary = temp.replace_complements(i);
Implicant found = merged.find(temp)->first; // in need for the key itself to retrieve its values, such as its covered terms
set<int> mergedSet = imp.getCoveredTerms();
set<int> coveredTerms2 = found.getCoveredTerms();
mergedSet.insert(coveredTerms2.begin(), coveredTerms2.end()); // merge the two sets
Implicant mergedB(newBinary, mergedSet);
// Merged
merged[cur.first] = true; // current element that we are iterating over its bits is checked
merged[temp] = true; // implicant to merge with is also done( have to do it through the iterator to change the value in the map itself)
newlyMerged[mergedB] = false;
}
}
}
}
for(auto imp: merged) // Update previous values of implicants
IMPLICANTS[imp.first] = imp.second;
for(auto imp: newlyMerged) // Add new values
IMPLICANTS[imp.first] = imp.second;
merged = newlyMerged;
}
}
void QmAlgo::populatePrimeImplicants(){
for (auto imp: IMPLICANTS){
bool checkAllDontCare = false; // check if the implicant has dontcares only
for(auto term: imp.first.getCoveredTerms()){
if(!checkAllDontCare)
checkAllDontCare=checkAllDontCare||TERMS[term]; // as long as term is a dontcare, keep looping until at least encountering one single minterm
}
if(checkAllDontCare)
if (!imp.second)
PrimeImplicants.push_back(imp.first);
}
}
void QmAlgo::populateEssentialPrimeImplicants() {
map<int, int> numOfCoversPerTerm;
//check all covered terms in all implicants and record the frequency of each term
for (auto imp : PrimeImplicants) {
for (int term : imp.getCoveredTerms()) {
if (COVERSOVERMINTERM.count(term)) COVERSOVERMINTERM[term].push_back(imp);
else COVERSOVERMINTERM[term] = {imp};
numOfCoversPerTerm[term]++;
if (TERMS[term]) isMINTERMCOVERED[term] = false;
}
}
//if the frequenncy of the term is 1 then its cover is an EPI
set<Implicant, comparatorImp> essentialPIs;
for (auto imp : PrimeImplicants)
for (int term : imp.getCoveredTerms())
if (TERMS[term] && numOfCoversPerTerm[term] == 1) essentialPIs.insert(imp);
EssentialPrimeImplicants.assign(essentialPIs.begin(), essentialPIs.end()); // To make sure there is not EPI duplicated
for (auto essential : EssentialPrimeImplicants)
for (int term : essential.getCoveredTerms()) isMINTERMCOVERED[term] = true;
//reduce the Boolean expression
//find the minterm not covered by the EPIs and find the biggest PI that covers these terms
for (auto term : isMINTERMCOVERED) {
if (!term.second) {
int mxNotCovered = 0;
Implicant toInclude;
for (auto imp : COVERSOVERMINTERM[term.first]) {
int curNotCovered = 0;
for (int u : imp.getCoveredTerms()) {
if (TERMS[u] && !isMINTERMCOVERED[u]) curNotCovered++;
}
if (curNotCovered > mxNotCovered) {
mxNotCovered = curNotCovered;
toInclude = imp;
}
}
essentialPIs.insert(toInclude); // these aren't EPIs but to be added to the minimized expression
for (int u : toInclude.getCoveredTerms()) isMINTERMCOVERED[u] = true;
}
}
ReducedExpression.assign(essentialPIs.begin(), essentialPIs.end());
}
void QmAlgo::printPIs(){
cout << "\t\t\t\t\tPrime IMPLICANTS\n\n"; // centered
cout << "Prime Implicant\t\t\t" << "Minterms Covered\t\t" << "Don't Cares Covered\n";
cout << "Binary Representation\t\t" << "Term\n";
for(auto prime: PrimeImplicants){
cout << prime.getBin() << "\t\t\t\t" << prime.getName() << "\t\t";
set<int> coveredTerms = prime.getCoveredTerms();
// minterms
for (auto minterm : coveredTerms)
if (TERMS[minterm])
cout << minterm << ", ";
cout << "\t\t\t\t";
// dontcares
for (auto dontcare : coveredTerms)
if (!TERMS[dontcare])
cout << dontcare << ", ";
cout << "\n";
}
cout << "___________________________________________________________________________________________________\n\n";
}
void QmAlgo::printEPIs(){
cout << "\t\t\t\t Essential Prime IMPLICANTS\n\n"; // centered
cout << "\tEssential Prime Implicant\t\t" << "Minterms Covered\t\t" << "Don't Cares Covered\n";
cout << "Binary Representation\t\t" << "Term\n";
for(auto prime: EssentialPrimeImplicants){
cout << prime.getBin() << "\t\t\t\t" << prime.getName() << "\t\t";
set<int> coveredTerms = prime.getCoveredTerms();
// minterms
for (auto minterm : coveredTerms)
if (TERMS[minterm])
cout << minterm << ", ";
cout << "\t\t\t\t";
// dontcares
for (auto dontcare : coveredTerms)
if (!TERMS[dontcare])
cout << dontcare << ", ";
cout << "\n";
}
cout << "___________________________________________________________________________________________________\n\n";
}
void QmAlgo::generateMinmizedLogicExpression() {
cout << "\t\t\t The Overall Reduced Boolean Expression is:\n"; // centered
for (int i = 0; i < ReducedExpression.size(); i++) {
cout << ReducedExpression[i].name;
if (i != ReducedExpression.size() - 1) cout << " + ";
}
cout << "\n";
}
void QmAlgo::runAlgo() {
reduce();
populatePrimeImplicants();
printPIs();
populateEssentialPrimeImplicants();
printEPIs();
generateMinmizedLogicExpression();
}