dunkirk.sh
optimizing a gate level bcm to the end of the earth and back
1"""
2Pure Python implementation of Quine-McCluskey algorithm for Boolean minimization.
3
4This implements multi-output prime implicant generation without requiring PyEDA.
5"""
6
7from dataclasses import dataclass, field
8from typing import Optional
9
10
11@dataclass(frozen=False)
12class Implicant:
13 """
14 Represents a prime implicant with output coverage information.
15
16 An implicant is represented by its mask and value:
17 - mask: which bit positions matter (1 = matters, 0 = don't care)
18 - value: the required bit values for positions that matter
19
20 For 4 variables (A, B, C, D):
21 - Bit 3 = A (MSB)
22 - Bit 2 = B
23 - Bit 1 = C
24 - Bit 0 = D (LSB)
25 """
26
27 mask: int # Which bits matter (1 = matters)
28 value: int # Required values for bits that matter
29 output_mask: int = field(default=0, compare=False)
30 covered_minterms: dict[str, set[int]] = field(default_factory=dict, compare=False)
31
32 @property
33 def num_literals(self) -> int:
34 """Count the number of literals (gate inputs) in this implicant."""
35 return bin(self.mask).count('1')
36
37 def covers(self, minterm: int) -> bool:
38 """Check if this implicant covers a given minterm."""
39 return (minterm & self.mask) == (self.value & self.mask)
40
41 def to_expr_str(self, var_names: list[str] = None) -> str:
42 """Convert to a Boolean expression string (product term)."""
43 if var_names is None:
44 var_names = ['A', 'B', 'C', 'D']
45
46 literals = []
47 for i in range(4):
48 bit = 1 << (3 - i)
49 if self.mask & bit:
50 if (self.value >> (3 - i)) & 1:
51 literals.append(var_names[i])
52 else:
53 literals.append(f"{var_names[i]}'")
54
55 return "".join(literals) if literals else "1"
56
57 def __hash__(self):
58 return hash((self.mask, self.value))
59
60 def __eq__(self, other):
61 if not isinstance(other, Implicant):
62 return False
63 return self.mask == other.mask and self.value == other.value
64
65 def __repr__(self):
66 return f"Implicant({self.to_expr_str()})"
67
68
69def try_merge(impl1: Implicant, impl2: Implicant) -> Optional[Implicant]:
70 """
71 Try to merge two implicants differing in exactly one variable.
72
73 Two implicants can merge if:
74 1. They have the same mask
75 2. They differ in exactly one bit position (within the mask)
76
77 Returns new implicant with one less literal, or None if can't merge.
78 """
79 if impl1.mask != impl2.mask:
80 return None
81
82 diff = (impl1.value ^ impl2.value) & impl1.mask
83
84 if bin(diff).count('1') != 1:
85 return None
86
87 new_mask = impl1.mask & ~diff
88 new_value = impl1.value & new_mask
89
90 return Implicant(mask=new_mask, value=new_value)
91
92
93def quine_mccluskey(
94 on_set: set[int],
95 dc_set: set[int] = None,
96 n_vars: int = 4
97) -> list[Implicant]:
98 """
99 Run Quine-McCluskey algorithm to find all prime implicants.
100
101 Args:
102 on_set: Set of minterms where function is 1
103 dc_set: Set of don't-care minterms (can be used for expansion)
104 n_vars: Number of input variables
105
106 Returns:
107 List of prime implicants that cover at least one on-set minterm
108 """
109 if dc_set is None:
110 dc_set = set()
111
112 full_mask = (1 << n_vars) - 1
113
114 # Start with on-set + don't-cares as initial implicants
115 all_minterms = on_set | dc_set
116
117 current = {}
118 for m in all_minterms:
119 impl = Implicant(mask=full_mask, value=m)
120 current[(impl.mask, impl.value)] = impl
121
122 prime_implicants = []
123
124 while current:
125 next_gen = {}
126 used = set()
127
128 impl_list = list(current.values())
129
130 for i, impl1 in enumerate(impl_list):
131 for j in range(i + 1, len(impl_list)):
132 impl2 = impl_list[j]
133 merged = try_merge(impl1, impl2)
134 if merged:
135 key = (merged.mask, merged.value)
136 if key not in next_gen:
137 next_gen[key] = merged
138 used.add((impl1.mask, impl1.value))
139 used.add((impl2.mask, impl2.value))
140
141 for key, impl in current.items():
142 if key not in used:
143 # Only keep if it covers at least one on-set minterm
144 covers_on = any(impl.covers(m) for m in on_set)
145 if covers_on:
146 prime_implicants.append(impl)
147
148 current = next_gen
149
150 return prime_implicants
151
152
153def quine_mccluskey_multi_output(
154 minterms_by_output: dict[str, set[int]],
155 dc_set: set[int] = None,
156 n_vars: int = 4
157) -> list[Implicant]:
158 """
159 Generate prime implicants for multiple outputs with sharing tags.
160
161 Generates primes for each output separately, then deduplicates and tags
162 with output coverage. This correctly handles the case where different
163 outputs have different on-sets.
164
165 Args:
166 minterms_by_output: Dict mapping output name to its on-set minterms
167 dc_set: Set of don't-care minterms (shared across all outputs)
168 n_vars: Number of input variables
169
170 Returns:
171 List of unique prime implicants with output coverage information
172 """
173 if dc_set is None:
174 dc_set = set()
175
176 # Generate prime implicants for each output separately
177 all_primes = {} # (mask, value) -> Implicant
178
179 for output_name, on_set in minterms_by_output.items():
180 primes = quine_mccluskey(on_set, dc_set, n_vars)
181 for impl in primes:
182 key = (impl.mask, impl.value)
183 if key not in all_primes:
184 all_primes[key] = Implicant(mask=impl.mask, value=impl.value)
185
186 # Tag each prime with which outputs it can cover
187 output_names = list(minterms_by_output.keys())
188 result = []
189
190 for impl in all_primes.values():
191 impl.output_mask = 0
192 impl.covered_minterms = {}
193
194 for i, (name, minterms) in enumerate(minterms_by_output.items()):
195 # An implicant can cover an output if:
196 # 1. It covers some minterms in that output's on-set
197 # 2. It doesn't cover any minterms in that output's off-set
198 covered = {m for m in minterms if impl.covers(m)}
199
200 # Check it doesn't cover any off-set minterms (0-9 that are not in on-set)
201 off_set = set(range(10)) - minterms
202 covers_off = any(impl.covers(m) for m in off_set)
203
204 if covered and not covers_off:
205 impl.covered_minterms[name] = covered
206 impl.output_mask |= (1 << i)
207
208 if impl.output_mask > 0:
209 result.append(impl)
210
211 return result
212
213
214def greedy_cover(
215 primes: list[Implicant],
216 minterms_by_output: dict[str, set[int]]
217) -> tuple[list[Implicant], int]:
218 """
219 Greedy set cover to select minimum-cost implicants.
220
221 Returns:
222 Tuple of (selected implicants, total cost)
223 """
224 uncovered = {
225 (out, m)
226 for out, minterms in minterms_by_output.items()
227 for m in minterms
228 }
229
230 selected = []
231 total_cost = 0
232
233 while uncovered:
234 best_impl = None
235 best_ratio = -1
236 best_covers = set()
237
238 for impl in primes:
239 if impl in selected:
240 continue
241
242 covers = set()
243 for out, minterms in impl.covered_minterms.items():
244 for m in minterms:
245 if (out, m) in uncovered:
246 covers.add((out, m))
247
248 if not covers:
249 continue
250
251 cost = impl.num_literals if impl.num_literals > 0 else 1
252 ratio = len(covers) / cost
253
254 if ratio > best_ratio:
255 best_ratio = ratio
256 best_impl = impl
257 best_covers = covers
258
259 if best_impl is None:
260 remaining = [(o, m) for o, m in uncovered]
261 raise RuntimeError(f"Cannot cover: {remaining[:5]}...")
262
263 selected.append(best_impl)
264 total_cost += best_impl.num_literals
265 uncovered -= best_covers
266
267 return selected, total_cost
268
269
270def print_prime_implicants(primes: list[Implicant]):
271 """Debug helper to print all prime implicants."""
272 print(f"Prime implicants ({len(primes)}):")
273 for p in sorted(primes, key=lambda x: (-bin(x.output_mask).count('1'), x.num_literals)):
274 outputs = list(p.covered_minterms.keys())
275 print(f" {p.to_expr_str():8} ({p.num_literals} lit) -> {', '.join(outputs)}")
276
277
278if __name__ == "__main__":
279 from .truth_tables import SEGMENT_MINTERMS, DONT_CARES, SEGMENT_NAMES
280
281 minterms = {s: set(SEGMENT_MINTERMS[s]) for s in SEGMENT_NAMES}
282
283 primes = quine_mccluskey_multi_output(
284 minterms,
285 set(DONT_CARES),
286 n_vars=4
287 )
288
289 print_prime_implicants(primes)
290
291 print("\nGreedy cover:")
292 selected, cost = greedy_cover(primes, minterms)
293 print(f"Selected {len(selected)} implicants, cost = {cost}")
294 for impl in selected:
295 print(f" {impl.to_expr_str()}")