// Copyright (C) Thorsten Thormaehlen, Marburg, 2012-2013, All rights reserved // Contact: www.thormae.de // This software is written for educational (non-commercial) purpose. // There is no warranty or other guarantee of fitness for this software, // it is provided solely "as is". // Version 1.0, 2013 // Version 2.0, 2023 changed how the best solution is selected in Petrick's method function PetrickMethod() { this.problem; this.maxProblemSize = 100; this.solution; this.log = ""; var that = this; this.test = function() { var andArray = new Array(); var orArray; var monomA; var monomB; orArray = new Array(); monomA = new Object(); // using objects ensures that (x and x) = x monomA[1] = 1; orArray.push(monomA); monomB = new Object(); monomB[2] = 2; orArray.push(monomB); andArray.push(orArray); orArray = new Array(); monomA = new Object(); monomA[3] = 3; orArray.push(monomA); monomB = new Object(); monomB[4] = 4; orArray.push(monomB); andArray.push(orArray); orArray = new Array(); monomA = new Object(); monomA[1] = 1; orArray.push(monomA); monomB = new Object(); monomB[3] = 3; orArray.push(monomB); andArray.push(orArray); orArray = new Array(); monomA = new Object(); monomA[5] = 5; orArray.push(monomA); monomB = new Object(); monomB[6] = 6; orArray.push(monomB); andArray.push(orArray); orArray = new Array(); monomA = new Object(); monomA[2] = 2; orArray.push(monomA); monomB = new Object(); monomB[5] = 5; orArray.push(monomB); andArray.push(orArray); orArray = new Array(); monomA = new Object(); monomA[4] = 4; orArray.push(monomA); monomB = new Object(); monomB[6] = 6; orArray.push(monomB); andArray.push(orArray); /*orArray = new Array(); monomA = new Object(); monomA[4] = 4; orArray.push(monomA); monomB = new Object(); monomB[4] = 4; orArray.push(monomB); andArray.push(orArray);*/ this.solve(andArray); }; this.solve = function(eq) { this.problem = eq; this.log = ""; //printEqnArray(eq); printEqnArrayFancy(eq); // multiply out var andArray = eq; var loopCounter = 0; while (andArray.length > 1) { var newAndArray = new Array(); for (var i = 1; i < andArray.length; i += 2) { var orTermA = andArray[i - 1]; var orTermB = andArray[i]; var newOrArray = new Array(); for (var a = 0; a < orTermA.length; a++) { for (var b = 0; b < orTermB.length; b++) { var monom1 = orTermA[a]; var monom2 = orTermB[b]; var resultingMonom = new Object(); for (var m in monom1) { resultingMonom[monom1[m]] = monom1[m]; } for (var n in monom2) { resultingMonom[monom2[n]] = monom2[n]; } newOrArray.push(resultingMonom); } } newAndArray.push(newOrArray); } // if uneven copy last and-term if (andArray.length % 2 === 1) { newAndArray.push(andArray[andArray.length - 1]); } //printEqnArray(newAndArray); printEqnArrayFancy(newAndArray); andArray.length = 0; // simplify or-term for (var i = 0; i < newAndArray.length; i++) { var orTerm = newAndArray[i]; var newOrTerm = simplifyOrTerm(orTerm); if (newOrTerm.length > 0) { andArray.push(newOrTerm); } } var problemSize = eqnArrayProblemSize(andArray); if (problemSize > this.maxProblemSize) { console.log("Error: The cyclic covering problem is too large to be solved with Petrick's method (increase maxProblemSize). Size=" + problemSize); return false; } //printEqnArray(andArray); printEqnArrayFancy(andArray); loopCounter++; } this.solution = andArray; return true; }; function simplifyOrTerm(orTerm) { // find a monom that is the same or simpler than another one var newOrTerm = new Array(); var markedForDeletion = new Object(); for (var a = 0; a < orTerm.length; a++) { var keepA = true; var monomA = orTerm[a]; for (var b = a + 1; b < orTerm.length && keepA; b++) { var monomB = orTerm[b]; var overlapBoverA = 0; var lengthA = 0; for (var m in monomA) { if (monomB[m] in monomA) { overlapBoverA++; } lengthA++; } var overlapAoverB = 0; var lengthB = 0; for (var m in monomB) { if (monomA[m] in monomB) { overlapAoverB++; } lengthB++; } if (overlapBoverA === lengthB) { keepA = false; } if (lengthA < lengthB && overlapAoverB === lengthA) { markedForDeletion[b] = b; } } if (keepA) { if (a in markedForDeletion) { // do nothing } else newOrTerm.push(orTerm[a]); } } return newOrTerm; } function printEqnArrayFancy(andArray) { var str = ""; for (var i = 0; i < andArray.length; i++) { var first = true; str += "("; var orArray = andArray[i]; for (var j = 0; j < orArray.length; j++) { if (!first) str += " ∨ "; var monom = orArray[j]; for (var k in monom) { str += "p"+ monom[k] + ""; } first = false; } str += ")"; } if(that.log.length > 0) { that.log += "
⇔ " + str + "
"; }else{ that.log += ""+ str + "
"; } } function eqnArrayProblemSize(andArray) { var monomCounter = 0; for (var i = 0; i < andArray.length; i++) { var orArray = andArray[i]; monomCounter += orArray.length; } return monomCounter; } function printEqnArray(andArray) { var str = ""; for (var i = 0; i < andArray.length; i++) { var first = true; str += "("; var orArray = andArray[i]; for (var j = 0; j < orArray.length; j++) { if (!first) str += " or "; var monom = orArray[j]; for (var k in monom) { str += monom[k]; } first = false; } str += ")"; } console.log(str); } } function PrimTerm() { this.implicant = -1; this.termString = ""; this.color = [0, 0, 0]; this.coloredTermString = ""; this.used = false; this.neededByVar = new Object; this.varCount = 0; } function Implicant() { this.imp = new Object(); this.isPrim = false; this.isOnlyDontCare = false; this.bitMask = 0; } function ImplicantGroup() { this.group = new Array; this.order = -1; } function PrimTermTable(ord) { this.essentialPrimTerms = new Array(); this.order = ord; this.remainingVars = new Array();; this.remainingPrimTerms = new Array(); this.supersededPrimTerms = new Array(); } function hsvToRgb(h, s, v) { var r, g, b; var i = Math.floor(h * 6); var f = h * 6 - i; var p = v * (1 - s); var q = v * (1 - f * s); var t = v * (1 - (1 - f) * s); switch (i % 6) { case 0: r = v, g = t, b = p; break; case 1: r = q, g = v, b = p; break; case 2: r = p, g = v, b = t; break; case 3: r = p, g = q, b = v; break; case 4: r = t, g = p, b = v; break; case 5: r = v, g = p, b = q; break; } return [ Math.floor(r * 255), Math.floor(g * 255), Math.floor(b * 255) ]; } function QuineMcCluskeyDataCtrl() { this.noOfVars = -1; this.funcdata = new Array; this.primTerms = new Array; this.implicantGroups = new Array; this.minimalTerm = ""; this.coloredMinimalTerm = ""; this.minimalTermPrims = new Array; this.primTermTables = new Array; this.petrickSolver = new PetrickMethod(); this.petrickTermPrims = new Array; this.allowDontCare = false; this.init = function(no) { this.noOfVars = no; this.funcdata.length = 0; this.primTerms.length = 0; this.implicantGroups.length = 0; this.minimalTerm = "0"; this.coloredMinimalTerm = "0"; this.minimalTermPrims.length = 0; this.primTermTables.length = 0; this.petrickTermPrims.length = 0; var noOfFuncData = Math.pow(2, this.noOfVars); for (var i = 0; i < noOfFuncData; i++) { this.funcdata.push(0); } //this.petrickSolver.test(); }; this.setFuncData = function(i, val) { if (i < 0 || i >= this.funcdata.length) return; this.funcdata[i] = val; }; this.activated = function(i) { if (i < 0 || i >= this.funcdata.length) return; this.funcdata[i] += 1; if(this.allowDontCare) { if (this.funcdata[i] > 2) this.funcdata[i] = 0; }else{ if (this.funcdata[i] > 1) this.funcdata[i] = 0; } this.compute(); }; this.random = function() { for (var i = 0; i < this.funcdata.length; i++) { if(this.allowDontCare) { this.funcdata[i] = Math.floor(Math.random() * 3); }else{ this.funcdata[i] = Math.floor(Math.random() * 2); } } this.compute(); }; this.clear = function() { for (var i = 0; i < this.funcdata.length; i++) { this.funcdata[i] = 0; } this.compute(); }; function bitCount(value) { var counter = 0; while (value > 0) { if ((value & 1) === 1) counter++; value >>= 1; } return counter; } this.compute = function() { this.primTerms.length = 0; this.implicantGroups.length = 0; this.minimalTerm = "0"; this.coloredMinimalTerm = "0"; this.minimalTermPrims.length = 0; this.primTermTables.length = 0; this.petrickTermPrims.length = 0; var counter = 0; var lastIg = -1; var continueLoop = true; while(continueLoop) { continueLoop = false; var ig = new ImplicantGroup(); if(counter === 0) { for (var i = 0; i < this.funcdata.length; i++) { if(this.funcdata[i] > 0) { var impl = new Implicant(); impl.imp[i] = i; impl.isPrim = true; ig.group.push(impl); continueLoop = true; } } }else{ for (var i = 0; i < lastIg.group.length; i++) { for (var j = i+1; j < lastIg.group.length; j++) { var imp1 = lastIg.group[i]; var imp2 = lastIg.group[j]; if (imp1.bitMask === imp2.bitMask) { var found = false; var xor = -1; for (var m in imp1.imp) { for (var n in imp2.imp) { var i1 = imp1.imp[m]; var i2 = imp2.imp[n]; //console.log(i1 + "<->" + i2); xor = (i1 ^ i2) & (~imp1.bitMask); if (bitCount(xor) === 1) { //console.log("found merge candidate" + i1 + "<->" + i2); found = true; } break; } break; } if (found) { imp1.isPrim = false; imp2.isPrim = false; var impl = new Implicant(); impl.isPrim = true; impl.bitMask = imp1.bitMask | xor; for (var m in imp1.imp) impl.imp[m] = parseInt(m); for (var n in imp2.imp) impl.imp[n] = parseInt(n); var foundMatch = false; // determine if this combination is already there for(var k=0; k < ig.group.length; k++) { var exist = ig.group[k]; var isTheSame = true; for(var m in impl.imp) { var found = false; for (var n in exist.imp) { if(parseInt(m) === parseInt(n)) { found = true; } } if(!found) { isTheSame = false; break; } } if(isTheSame) { foundMatch = true; break; } } if(!foundMatch) { ig.group.push(impl); continueLoop = true; } } } } } } if(continueLoop) this.implicantGroups.push(ig); lastIg = ig; counter++; } // collect primterms this.primTerms.length = 0; this.minimalTermPrims.length = 0; var color = 0.0; for(var i= this.implicantGroups.length-1; i >=0; i--) { var g = this.implicantGroups[i].group; for(var j=0; j < g.length; j++) { if(g[j].isPrim) { // prim terms introduced by don't cares // must have at least one 1 var containsOne = false; var allFuncPrimTerm = g[j].imp; for(var kk in allFuncPrimTerm) { var k = allFuncPrimTerm[kk]; if(this.funcdata[k] === 1) { containsOne = true; } } if(!containsOne){ g[j].isOnlyDontCare = true; } else { var primTerm = new PrimTerm(); primTerm.implicant = g[j]; // extract minTerm as string for (var thisVal in primTerm.implicant.imp) { var minTerm = ""; var one = 1; var needed = (~primTerm.implicant.bitMask); var varCount = 0; for (var v = 0; v < this.noOfVars; v++) { if ((needed & one) === one) { if ((thisVal & one) === one) { minTerm = "x" + v + "" + minTerm; } else { minTerm = "x̄" + v + "" + minTerm; } varCount++; } one = one << 1; } minTerm = "(" + minTerm + ")"; if (primTerm.implicant.bitMask === Math.pow(2, this.noOfVars) - 1) minTerm = "1"; primTerm.color = hsvToRgb(color, 1.0, 0.5); color += 0.22; color = color % 1.0; primTerm.termString = minTerm; primTerm.varCount = varCount; var colorStr = "rgb(" + primTerm.color[0] + "," + primTerm.color[1] + "," + primTerm.color[2] + ")"; primTerm.coloredTermString = "" + minTerm + ""; break; } this.primTerms.push(primTerm); } } } } // looking for essential prime implicants var remaining = new Object(); for (var i = 0; i < this.funcdata.length; i++) { if(this.funcdata[i] === 1) { remaining[i] = i; } } this.primTermTables.length = 0; var primTableLoop = 0; var primTableFound = (this.primTerms.length > 0); var cyclicCoveringFound = false; var primTermTable; while (primTableFound) { primTableFound = false; primTermTable = new PrimTermTable(primTableLoop); for (var r in remaining) { primTermTable.remainingVars.push(remaining[r]); } if (primTableLoop === 0) { for (var j = 0; j < this.primTerms.length; j++) { primTermTable.remainingPrimTerms.push(this.primTerms[j]); } } else { // remove rows var prevTable = this.primTermTables[primTableLoop-1]; for(var k=0; k" + labels['primChart'] + ":
" +labels['primChartReduced'] + " " + (i-1) + "):"; } resultDiv.setAttribute('class', 'qmcTableResultDiv'); var drawPetrickVars = false; if(this.data.petrickTermPrims.length > 0 && i === this.data.primTermTables.length-1) { drawPetrickVars = true; } this.drawImplicantGroup(this.data.primTerms, resultDiv, true, i, drawPetrickVars); var essPTermsDiv = document.createElement('div'); var essPTermsStr = ""; var primTermTable = this.data.primTermTables[i]; var jj = primTermTable.essentialPrimTerms.length; for(var j=0; j < jj; j++) { essPTermsStr += primTermTable.essentialPrimTerms[j].coloredTermString; if(j !== (jj-1)) essPTermsStr += ", "; } if(jj > 0) { essPTermsDiv.innerHTML = "" + labels['extractedPrims'] +": " + essPTermsStr + "
"; essPTermsDiv.setAttribute('class', 'qmcIndent'); resultDiv.appendChild(essPTermsDiv); } myInnerDiv.appendChild(resultDiv); } if (this.data.petrickTermPrims.length > 0) { var petrickDiv = document.createElement('div'); petrickDiv.innerHTML = "" + labels['petricksM'] + "
"; var petrickInnerDiv = document.createElement('div'); petrickInnerDiv.innerHTML = "" + this.data.petrickSolver.log + ""; petrickInnerDiv.setAttribute('class', 'qmcIndent'); petrickDiv.appendChild(petrickInnerDiv); var petrickEssTermsDiv = document.createElement('div'); var petrickEssTermsStr = ""; var jj = this.data.petrickTermPrims.length; for (var j = 0; j < jj; j++) { petrickEssTermsStr += this.data.petrickTermPrims[j].coloredTermString; if (j !== (jj - 1)) petrickEssTermsStr += ", "; } if (jj > 0) { petrickEssTermsDiv.innerHTML = "" + labels['extractedMPrims'] + " (" + labels['petricksM'] + "): " + petrickEssTermsStr + "
"; petrickEssTermsDiv.setAttribute('class', 'qmcIndent'); petrickDiv.appendChild(petrickEssTermsDiv); } myInnerDiv.appendChild(petrickDiv); } var termDiv = document.createElement('div'); termDiv.innerHTML = "" + labels['minExp']+ ":
y = " + this.data.coloredMinimalTerm; +"
"; myInnerDiv.appendChild(termDiv); myDiv.appendChild(myInnerDiv); }; function myCellMouseDown(e) { var targ; if (e.target) { targ = e.target; } else { // deal with Microsoft if (e.srcElement) targ = e.srcElement; } if (targ.nodeType === 3) { // deal with Safari targ = targ.parentNode; } var i = parseInt(targ.title); that.data.activated(i); that.update(); } }