1+ def compare_string (string1 , string2 ):
2+ l1 = list (string1 ); l2 = list (string2 )
3+ count = 0
4+ for i in range (len (l1 )):
5+ if l1 [i ] != l2 [i ]:
6+ count += 1
7+ l1 [i ] = '_'
8+ if count > 1 :
9+ return - 1
10+ else :
11+ return ("" .join (l1 ))
12+
13+ def check (binary ):
14+ pi = []
15+ while 1 :
16+ check1 = ['$' ]* len (binary )
17+ temp = []
18+ for i in range (len (binary )):
19+ for j in range (i + 1 , len (binary )):
20+ k = compare_string (binary [i ], binary [j ])
21+ if k != - 1 :
22+ check1 [i ] = '*'
23+ check1 [j ] = '*'
24+ temp .append (k )
25+ for i in range (len (binary )):
26+ if check1 [i ] == '$' :
27+ pi .append (binary [i ])
28+ if len (temp ) == 0 :
29+ return pi
30+ binary = list (set (temp ))
31+
32+ def decimal_to_binary (no_of_variable , minterms ):
33+ temp = []
34+ s = ''
35+ for m in minterms :
36+ for i in range (no_of_variable ):
37+ s = str (m % 2 ) + s
38+ m //= 2
39+ temp .append (s )
40+ s = ''
41+ return temp
42+
43+ def is_for_table (string1 , string2 , count ):
44+ l1 = list (string1 );l2 = list (string2 )
45+ count_n = 0
46+ for i in range (len (l1 )):
47+ if l1 [i ] != l2 [i ]:
48+ count_n += 1
49+ if count_n == count :
50+ return True
51+ else :
52+ return False
53+
54+ def selection (chart , prime_implicants ):
55+ temp = []
56+ select = [0 ]* len (chart )
57+ for i in range (len (chart [0 ])):
58+ count = 0
59+ rem = - 1
60+ for j in range (len (chart )):
61+ if chart [j ][i ] == 1 :
62+ count += 1
63+ rem = j
64+ if count == 1 :
65+ select [rem ] = 1
66+ for i in range (len (select )):
67+ if select [i ] == 1 :
68+ for j in range (len (chart [0 ])):
69+ if chart [i ][j ] == 1 :
70+ for k in range (len (chart )):
71+ chart [k ][j ] = 0
72+ temp .append (prime_implicants [i ])
73+ while 1 :
74+ max_n = 0 ; rem = - 1 ; count_n = 0
75+ for i in range (len (chart )):
76+ count_n = chart [i ].count (1 )
77+ if count_n > max_n :
78+ max_n = count_n
79+ rem = i
80+
81+ if max_n == 0 :
82+ return temp
83+
84+ temp .append (prime_implicants [rem ])
85+
86+ for i in range (len (chart [0 ])):
87+ if chart [rem ][i ] == 1 :
88+ for j in range (len (chart )):
89+ chart [j ][i ] = 0
90+
91+ def prime_implicant_chart (prime_implicants , binary ):
92+ chart = [[0 for x in range (len (binary ))] for x in range (len (prime_implicants ))]
93+ for i in range (len (prime_implicants )):
94+ count = prime_implicants [i ].count ('_' )
95+ for j in range (len (binary )):
96+ if (is_for_table (prime_implicants [i ], binary [j ], count )):
97+ chart [i ][j ] = 1
98+
99+ return chart
100+
101+ def main ():
102+ no_of_variable = int (input ("Enter the no. of variables\n " ))
103+ minterms = [int (x ) for x in input ("Enter the decimal representation of Minterms 'Spaces Seprated'\n " ).split ()]
104+ binary = decimal_to_binary (no_of_variable , minterms )
105+
106+ prime_implicants = check (binary )
107+ print ("Prime Implicants are:" )
108+ print (prime_implicants )
109+ chart = prime_implicant_chart (prime_implicants , binary )
110+
111+ essential_prime_implicants = selection (chart ,prime_implicants )
112+ print ("Essential Prime Implicants are:" )
113+ print (essential_prime_implicants )
114+
115+ if __name__ == '__main__' :
116+ main ()
0 commit comments