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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
| public class QuinceMcCluskey {
private ArrayList<CriteriaOfEquation> variableArray;
private ArrayList <Integer> MintermsIndicesDecimal;
private int trh_table[][];
private ArrayList < ArrayList <String [][] > > step; //First Step of Minimization
private ArrayList < ArrayList <String [][] > > newStep; //Next Step of Minimization
private ArrayList < String [][] > parameters ; //List each parameters [decimal][binary]
private int stepCount=0; //Count step of minimization
private ArrayList<String> tempStr; //Used to find PI during the minimization
private ArrayList <String[][] > EssentialPrimeImplicant; //List each EPI found by the minimization stored in EPI_lines[][]
private String[][] EPI_lines; //Store EPI (1 line / 3 columns)
private int MintermsOccurences[][]; //List number of minterms occurrences in each EPI (2 lines / X columns)
private int newMintermsOccurences[][]; //??????????????????????????????????
private static String FinalExpression ="";
/**
* Getter
* @return
*/
public String getFinalExpression() {
return FinalExpression;
}
/**
* Constructor
* @param trh_table
* @param variableArray
* @param MintermsIndicesDecimal
*/
public QuinceMcCluskey(int trh_table[][], ArrayList<CriteriaOfEquation> variableArray, ArrayList <Integer> MintermsIndicesDecimal){
this.MintermsIndicesDecimal=MintermsIndicesDecimal;
this.variableArray=variableArray;
this.trh_table=trh_table;
EssentialPrimeImplicant = new ArrayList <String[][] >(); //Headers : [PI][COMBINAISON REDUITE][PI or Not]
MintermsOccurences = new int[2][MintermsIndicesDecimal.size()]; //Headers : [Minterms]
for(int i =0; i<MintermsIndicesDecimal.size(); i++)
MintermsOccurences[0][i]=MintermsIndicesDecimal.get(i);
Minimization();
}
/**
* First step of minimization --> We gather all minterms in function of their numbers of 1
* Each minterms is added in an 2D array : [decimal][binary].
* All minterms having same number of 1 are added in an arrayList called parameters
* According to the number of 1, each arrayList parameter is stored in an item of the ArrayList called step
* @param MintermsIndicesDecimal
*/
private void Minimization(){
ArrayList <Integer> temp = new ArrayList<Integer>();
step = new ArrayList <ArrayList<String [][]>>();
int numberOfTrue=0;
for (int i=0; i<MintermsIndicesDecimal.size(); i++){
for (int j=0; j<variableArray.size(); j++) {
if (trh_table[MintermsIndicesDecimal.get(i)][j] == 1)
numberOfTrue++;
}
if (!temp.contains(numberOfTrue)){
temp.add(numberOfTrue);
Collections.sort(temp);
parameters = new ArrayList < String [][] > () ;
String [][] DecimalxCombination = new String[1][2];
DecimalxCombination[0][0] = MintermsIndicesDecimal.get(i).toString();
DecimalxCombination[0][1] = DecimalToBinary(Integer.toBinaryString(MintermsIndicesDecimal.get(i)));
parameters.add(DecimalxCombination);
//System.out.print("---> temp : "+ temp+ "\n");
//System.out.print("---> step size : "+ step.size() + "\n");
for(int k=0; k<temp.size(); k++){
//System.out.print("\t ~~~ if temp item : "+ temp.get(k) + " = " + numberOfTrue +"\n");
if(temp.get(k)==numberOfTrue){
//System.out.print("\t ~~~ OUI" + "\n");
step.add(k, parameters);
}
}
}else{
for(int k=0; k<temp.size(); k++){
if(temp.get(k)==numberOfTrue){
String [][] DecimalxCombination = new String[1][2];
DecimalxCombination[0][0] = MintermsIndicesDecimal.get(i).toString();
DecimalxCombination[0][1] = DecimalToBinary(Integer.toBinaryString(MintermsIndicesDecimal.get(i)));
step.get(k).add(DecimalxCombination);
}
}
}
numberOfTrue=0;
}
System.out.print(" step 0 : \n");
for(int t=0; t<step.size(); t++){
System.out.print("Column " + t + ": \n");
for(int s=0; s<step.get(t).size();s++){
for (String[] row : step.get(t).get(s) ){System.out.println(Arrays.toString(row));}
}
}
System.out.print(" temp : " + temp +"\n");
NewStep(step);
}
/**
* Method called if there are others steps of minimization after the first
* It calls itself until there are no more step of minimization
* @param step
*/
private void NewStep(ArrayList <ArrayList<String [][]>> step){
newStep = new ArrayList <ArrayList<String [][]>>();
tempStr = new ArrayList<String>();
ArrayList <Integer> temp = new ArrayList<Integer>();
int numberOfTrue=0;
stepCount++;
for(int i=0; i<step.size()-1; i++){
for(int j=0; j<step.get(i).size();j++){
for(int k=0; k<step.get(i+1).size();k++){
if(!(step.get(i).get(j)[0][1].equals(step.get(i+1).get(k)[0][1]))){
//System.out.print("compar " + step.get(i).get(j)[0][0] + " with " + step.get(i+1).get(k)[0][0] + "\n");
String str = StringEquality(step.get(i).get(j)[0][1], step.get(i+1).get(k)[0][1]);
if(!(str==null)){
if(str.equals("PI")){
if(!tempStr.contains(step.get(i).get(j)[0][0]))
tempStr.add(step.get(i).get(j)[0][0]);
if (!tempStr.contains(step.get(i+1).get(k)[0][0]))
tempStr.add(step.get(i+1).get(k)[0][0]);
}else{
numberOfTrue = stringOccur(str, "1");
if (!temp.contains(numberOfTrue)){
parameters = new ArrayList < String [][] > () ;
String [][] DecimalxCombination = new String[1][2];
DecimalxCombination[0][0]= step.get(i).get(j)[0][0] +","+ step.get(i+1).get(k)[0][0];
DecimalxCombination[0][1]= str;
parameters.add(DecimalxCombination);
newStep.add(parameters);
temp.add(numberOfTrue);
Collections.sort(temp);
}else{
Boolean bool = false;
for(int m=0; m<temp.size(); m++){
if(temp.get(m)==numberOfTrue){
outlooper :
for(int n=0; n<newStep.get(m).size();n++){
if(newStep.get(m).get(n)[0][1].contains(str)){
bool = true;
break outlooper;
}
}
if(bool==false){
String [][] DecimalxCombination = new String[1][2];
DecimalxCombination[0][0]= step.get(i).get(j)[0][0] +","+ step.get(i+1).get(k)[0][0];
DecimalxCombination[0][1]= str;
newStep.get(m).add(DecimalxCombination);
}
}
}
}
}
}
}
}
}
}
if(!newStep.isEmpty()){
//Lines only to visualize our results
System.out.print("\n step " + stepCount + ": \n");
for(int t=0; t<newStep.size(); t++){
System.out.print("Column " + t + ": \n");
for(int s=0; s<newStep.get(t).size();s++){
for (String[] row : newStep.get(t).get(s) ){System.out.println(Arrays.toString(row));}
//if(newStep.get(t).get(s)[0][0].equals("1,3,5,7")){
//System.out.print("----------> " + newStep.get(t).get(s)[0][1] + "\n");
//}
}
}
System.out.print("\n\n"+ tempStr+"\n");
int count;
for(String str : tempStr){
count =0;
//System.out.print("\n-- STRING :" + str + "\n");
String[] ArrOfStr = str.split(",");
for(String st : ArrOfStr){
//System.out.print("-- " + st + " size : " + ArrOfStr.length +"\n");
for(int t=0; t<newStep.size(); t++){
for(int s=0; s<newStep.get(t).size();s++){
//System.out.print("------ MINTERMS : " + newStep.get(t).get(s)[0][0]);
String[] ArrOfStr_ = newStep.get(t).get(s)[0][0] .split(",");
for(String strg : ArrOfStr_){
if(Integer.valueOf(strg).equals(Integer.valueOf(st)))
count++;
}
//System.out.print("\t--- COUNT : " + count + "\n");
}
}
}
if(count<=ArrOfStr.length-1){
EPI_lines = new String[1][3];
EPI_lines[0][0]= str;
for(int t=0; t<step.size(); t++)
for(int s=0; s<step.get(t).size();s++){
if(step.get(t).get(s)[0][0].equals(str))
EPI_lines[0][1]= step.get(t).get(s)[0][1];
}
EPI_lines[0][2]= "state";
if (!EssentialPrimeImplicant.contains(EPI_lines))
EssentialPrimeImplicant.add(EPI_lines);
}
}
NewStep(newStep);
}else{
for(int t=0; t<step.size(); t++)
for(int s=0; s<step.get(t).size();s++){
EPI_lines = new String[1][3];
EPI_lines[0][0]= step.get(t).get(s)[0][0];
EPI_lines[0][1]= step.get(t).get(s)[0][1];
EPI_lines[0][2]= "state";
if (!EssentialPrimeImplicant.contains(EPI_lines))
EssentialPrimeImplicant.add(EPI_lines);
}
CountMintermsOccurrences(EssentialPrimeImplicant);
PrimeImplicantChart();
}
}
/**
* Store CountMintermsOccurrences array
* This array store each minterms and their number of occurrences in the list of PI
* @param EssentialPrimeImplicant
*/
public void CountMintermsOccurrences(ArrayList <String[][] > EssentialPrimeImplicant){
int count =0;
for(int k=0; k<MintermsIndicesDecimal.size();k++){
count=0;
for(int i=0; i<EssentialPrimeImplicant.size(); i++){
String[] ArrOfStr = EssentialPrimeImplicant.get(i)[0][0].split(",");
for(String str : ArrOfStr){
if(Integer.valueOf(str).equals(MintermsOccurences[0][k])){
count++;
}
}
}
MintermsOccurences[1][k]=count;
}
}
/**
* Find EPI from PI
*/
public String PrimeImplicantChart(){
System.out.print("\n Count Minterms Occurences : \n");
for (int[] row : MintermsOccurences){System.out.println(Arrays.toString(row));}
int count = 0;
for(int i=0; i<MintermsOccurences[0].length; i++){
if(MintermsOccurences[1][i]==1){
for(int j=0; j<EssentialPrimeImplicant.size(); j++){
String[] ArrOfStr = EssentialPrimeImplicant.get(j)[0][0].split(",");
for(String str : ArrOfStr){
if(Integer.valueOf(str).equals(MintermsOccurences[0][i])){
if(!EssentialPrimeImplicant.get(j)[0][2].contains("EPI")){
EssentialPrimeImplicant.get(j)[0][2]="EPI";
count++;
}
}
}
}
}
}
//Retrouve l'expression de chaque EPI ssi l'expression se simplifie facilement!
String MinimizedExpression ="";
if((EssentialPrimeImplicant.size()-1) == count || EssentialPrimeImplicant.size() == count){
for(int i =0; i<EssentialPrimeImplicant.size();i++){
for(int j =0; j<EssentialPrimeImplicant.get(i).length;j++){
if(EssentialPrimeImplicant.get(i)[j][2]=="EPI"){
MinimizedExpression = "";
String[] ArrOfStr = EssentialPrimeImplicant.get(i)[j][1].split("");
for(int m=0; m<ArrOfStr.length; m++){
if(ArrOfStr[m]!="X"){
if(ArrOfStr[m].equals("1")){
if(MinimizedExpression!=""){
MinimizedExpression =MinimizedExpression +"."+ variableArray.get(m);
EssentialPrimeImplicant.get(i)[j][2]=MinimizedExpression;
}else{
MinimizedExpression = variableArray.get(m).toString();
EssentialPrimeImplicant.get(i)[j][2]=MinimizedExpression;
}
}else if(ArrOfStr[m].equals("0")){
if(MinimizedExpression!=""){
MinimizedExpression = MinimizedExpression + ".!" +variableArray.get(m);
EssentialPrimeImplicant.get(i)[j][2]=MinimizedExpression;
}else{
MinimizedExpression = "!"+variableArray.get(m);
EssentialPrimeImplicant.get(i)[j][2]=MinimizedExpression;
}
}
}
}
//Final expression is the result of the concatenation of each EPI
if(FinalExpression.isEmpty()){
FinalExpression = EssentialPrimeImplicant.get(i)[j][2];
}else{
FinalExpression = FinalExpression + "+(" + EssentialPrimeImplicant.get(i)[j][2] + ")";
}
//
}
}
}
}else{
// REDUIRE LE TABLEAU
System.out.print("Number of state : " + (EssentialPrimeImplicant.size()-count)+ "\n");
updateMintermsOccurencesChart();
// ReducePrimeImplicantChart(EssentialPrimeImplicant.size()-count, MinimizedExpression);
}
System.out.print("\n EssentialPrimeImplicant : ");
System.out.print("\n-----------\n");
for(int i=0; i<EssentialPrimeImplicant.size(); i++)
for (String[] row : EssentialPrimeImplicant.get(i)){System.out.println(Arrays.toString(row));}
System.out.print("\n ***** FINAL EXPRESSION : " + FinalExpression + "\n" );
return FinalExpression;
}
/* public String ReducePrimeImplicantChart(int numOfState, String MinimizedExpression){
outlooper:
for(int i=0; i<MintermsOccurences[0].length; i++){
if(MintermsOccurences[1][i]==numOfState){
for(int j =0; j<EssentialPrimeImplicant.size();j++){
for(int k =0; k<EssentialPrimeImplicant.get(j).length;j++){
if(EssentialPrimeImplicant.get(j)[k][2]=="state"){
String[] ArrOfStr = EssentialPrimeImplicant.get(j)[0][0].split(",");
for(String str : ArrOfStr){
if(Integer.valueOf(str).equals(MintermsOccurences[0][i])){
String[] ArrOfStr1 = EssentialPrimeImplicant.get(j)[k][1].split("");
for(int m=0; m<ArrOfStr1.length; m++){
if(ArrOfStr1[m]!="X"){
if(ArrOfStr1[m].equals("1")){
if(MinimizedExpression!=""){
MinimizedExpression =MinimizedExpression +"."+ variableArray.get(m);
EssentialPrimeImplicant.get(j)[k][2]=MinimizedExpression;
}else{
MinimizedExpression = variableArray.get(m).toString();
EssentialPrimeImplicant.get(j)[k][2]=MinimizedExpression;
}
}else if(ArrOfStr1[m].equals("0")){
if(MinimizedExpression!=""){
MinimizedExpression = MinimizedExpression + ".!" +variableArray.get(m);
EssentialPrimeImplicant.get(j)[k][2]=MinimizedExpression;
}else{
MinimizedExpression = "!"+variableArray.get(m);
EssentialPrimeImplicant.get(j)[k][2]=MinimizedExpression;
}
}
}
}
}
}
}
}
}
break outlooper;
}
}
return null;
}
*/
/**
* delete columns MintermsOccurences array
* @param MintermsOccurences
* @param count
*/
public void deleteColumn(int[][] MintermsOccurences, int count){
if(MintermsOccurences != null && MintermsOccurences.length > 0 && MintermsOccurences[0].length > 0)
{
int newColIdx = 0;
newMintermsOccurences = new int[MintermsOccurences.length][MintermsOccurences[0].length-count];
for(int j=0; j<MintermsOccurences[0].length; j++){
if(MintermsOccurences[0][j]!=0){
newMintermsOccurences[0][newColIdx] = MintermsOccurences[0][j];
newMintermsOccurences[1][newColIdx] = MintermsOccurences[1][j];
newColIdx++;
}
}
}
System.out.print("\n New Count Minterms Occurences : \n");
for (int[] row : newMintermsOccurences){System.out.println(Arrays.toString(row));}
}
/**
* Update MintermsOccurences tab
*/
public void updateMintermsOccurencesChart(){
for(int j=0; j<EssentialPrimeImplicant.size(); j++){
if(EssentialPrimeImplicant.get(j)[0][2].contains("EPI")){
String[] ArrOfStr = EssentialPrimeImplicant.get(j)[0][0].split(",");
for(String str : ArrOfStr){
for(int i=0; i<MintermsOccurences[0].length; i++){
if(Integer.valueOf(str).equals(MintermsOccurences[0][i])){
MintermsOccurences[1][i]=MintermsOccurences[1][i]-1;
}
}
}
}
}
System.out.print("\n Count Minterms Occurences updated : \n");
for (int[] row : MintermsOccurences){System.out.println(Arrays.toString(row));}
}
/**
* Convert decimal value into boolean value
* @param value
* @return
*/
private String DecimalToBinary(String value){
//System.out.print(value + " -- length : " + value.length()+"\n");
while(value.length()!=variableArray.size()){
value = '0'+ value;
//System.out.print("\t"+value + " -- length : " + value.length()+"\n");
}
return value;
}
/**
* Compare 2 String & Replace by 'X' the wrong char
* @param str1
* @param str2
* @return
*/
private String StringEquality(String str1, String str2){
//System.out.print("str1 : " + str1 + "\n");
//System.out.print("str2 : " + str2 + "\n");
char charArray1[] = str1.toCharArray();
char charArray2[] = str2.toCharArray();
String str = "";
int count =0;
for(int i=0; i<charArray1.length; i++){
if(charArray1[i] != charArray2[i]){
charArray2[i] = 'X';
count++;
}else{
charArray2[i] = charArray1[i];
}
}
if(count <= 1){
str = new String(charArray2);
}else if(count > 1 && count <= variableArray.size()){
//System.out.print("\t --> " + count + "compris entre et "+ variableArray.size() + "\n");
str = "PI";
}else{
str = null;
}
return str;
}
/**
* count the number of occurrences
* @param text
* @param string
* @return
*/
public static final int stringOccur(String text, String string) {
return regexOccur(text, Pattern.quote(string));
}
public static final int regexOccur(String text, String regex) {
Matcher matcher = Pattern.compile(regex).matcher(text);
int occur = 0;
while(matcher.find()) {
occur ++;
}
return occur;
}
} |
Comment bien optimiser mon code
Répondre avec citation
Envoyé par Miigui
.
?
Partager