3 ms·
See also https://en.m.wikipedia.org/wiki/Karnaugh_map https://en.m.wikipedia.org/wiki/Karnaugh_map for a human-applicable algorithm to minimize logic expression
by praptak 7y ago
See also https://en.m.wikipedia.org/wiki/Karnaugh_map https://en.m.wikipedia.org/wiki/Karnaugh_map for a human-applicable algorithm to minimize logic expressions.
- yters 7y agoAlso Quine-McCluskey for an automated reduction of Karnaugh maps.
- paypalcust83 7y agoEE/CS here. Kmaps only work for 4-5 variables unless you're some sort of 4D-chess wizard. And they're meant for manual, human pattern-matching rather than automated evaluation. There are numerous, specialized bi/tri/quad boolean logic prime implicant optimization algorithms for combinational logic and expressions like QM and MQM.
- tasty_freeze 7y agoI once did the reverse karnaugh mapping on a set of expressions to minimize their complexity; the input set was 7 bits. Specifically, I created an instruction mapping on a 7b opcode space such that the decode logic for the critical paths was short (eg, branch decode). It took multiple sheets of paper, a few tries, and a couple of days, but it wasn't too bad.
- laszlokorte 7y agoFor my bachelors thesis I built a tool for playing around with and teaching KV diagrams [1] [1]: https://thesis.laszlokorte.de/demo/kvd-editor.html https://thesis.laszlokorte.de/demo/kvd-editor.html
- bear8642 7y agoNice tool! By DNF and KNF do you mean disjunctive and conjuctive normal form?
- laszlokorte 7y agoCorrect. In german it's called "Konjunktive Normalform" and targetted at a german class I decided not to translate it.