<Text-field style="Heading 1" layout="Heading 1"><Font family="Arial">References</Font></Text-field>

<Text-field style="Heading 1" layout="Heading 1"><Font family="Arial">Algorithm Code (Module)</Font></Text-field>

Consensus_Method := module() option package; # interface routines export consensus; # local support routines: local consensus_printf,compressAndUpcase, makeInternalForm, externalTerm, externalExpression, negateVbl, hasVbl, sameTerm, consensusPossible, takeConsensus, termContained, consensusStep1, consensusStep2, consensusList; global verboseMode; # Note: The Internal Format of a boolean expression is a set. # 1. Each term results in a set inside of the expression set. # 2. A variable is stored as its uppercase name. # 3. A negated variable is stored as its lowercase name. # # Eg: "XY + X'Z" is stored as {{"X","Y"},{"x","Z"}}; # Routine: consensus # Abstract: Determine prime implicants for specified boolean expression # Input: boolstr - boolean expression in string form (see "Input Format" section) # Returns: string - prime implicants of specified boolean expression consensus := proc (boolstr::string) local e; # convert input string form of expression to internal form e := makeInternalForm(boolstr); if (type(e,string)) then # error printf("%s\134n",e); return; end if; # verboseMode iff 2nd arg passed, and set true verboseMode := evalb(nargs = 2 and type(args[2],boolean) and args[2]); # perform consensus algorithm on internal-format expression consensusList(e); end proc: # consensus # Routine: consensus_printf # Abstract: printf, but only if in verbose mode # Note: uses args, nargs - to process argument list consensus_printf := proc() global verboseMode; local i; if (verboseMode) then printf(seq(args[i],i=1..nargs)); end if; end proc: # consensus_printf # Routine: consensusList # Abstract: Given expression (list), return simplified form # after applying consensus method to it. # Displays simplified expression in external-form. # Eg: {{"X"}, {"X","Y"}} -> X consensusList := proc(expr::set) local e, saved_e, all_done, loops; e := expr; consensus_printf("Initial: %s\134n",externalExpression(e)); all_done := false; loops := 0; while (not all_done) do; # Step 1. Look for elements contained in other elements. # Eg: AB + ABCDEF --> AB, AB is implicant of ABCDEF e := consensusStep1(e); saved_e := e; # save state, so we can see if step 2 makes any change # Step 2. Looking for removable elements e := consensusStep2(e); # If nothing added in step 2, we are done if evalb(e=saved_e) then all_done := true; break; end if; # Guard against infinite loop loops := loops + 1; if (loops > 1500) then printf("*** Max loops in concensusList reached, terminating ***\134n"); break; end if; end do; # while not all_done # Display result printf("Prime implicants: %s\134n",externalExpression(e)); end proc: # consensusList # Routine: compressAndUpcase # Abstract: Remove whitespace from string, convert to uppercase # Returns: converted string compressAndUpcase := proc (s_in::string) local c,i,n,s,s1; s := ""; s1 := UpperCase(s_in); n := length(s1); for i to n do; # remove blanks, tabs and newlines c := s1[i]; if not (member(c,{" ","\134t","\134n"})) then s := cat(s, c); end if; end do; return s; end proc: # compressAndUpcase # Routine: makeInternalForm # Abstract: Given a sum of products boolean expression string # eg: "XY+Y'Y", convert to internal list form with # single-character variables; lowercase if negated. # (eg: "XY + X'Y" -> {{"X","Y"},{"x","Y"}} # Returns: internal form boolean expression (set) makeInternalForm := proc (s_in::string) local c,e,i,n,s,s1,term,termCount; # remove spaces and tabs, convert to uppercase s1 := compressAndUpcase(s_in); # check for empty expression if (length(s1)=0) then return "*** Empty Expression ***"; end if; s := ""; n := length(s1); e := {}; # output expression term := {}; # next term termCount := 0; for i to n do; c := s1[i]; if (not member(c, {"+", "'", $"A".."Z"})) then return cat("*** Invalid Character: <", c, "> ***"); end if; if (member(c, {$"A".."Z"})) then # lookahead for negation indicator if (i < n) then if (s1[i+1] = "'") then # negated => lowercase i := i + 1; c := LowerCase(c); end if; end if; term := term union {c}; elif (c = "'") then # Only valid after variable (see above) return "*** Invalid negation operation ***"; elif (c = "+") then # Add term if (nops(term) = 0) then return "*** Missing boolean term before + operator ***"; end if; termCount := termCount + 1; e := e union {term}; term := {}; end if; end do; # append trailing term if nops(term) > 0 then termCount := termCount + 1; e := e union {term}; end if; return e; end proc: # makeInternalForm # Routine: externalTerm # Abstract: Given a term in internal format # return an external-format string. # For example: {"A","b","C"} -> AB'C externalTerm := proc(elem::set) local c, i, n, s; s := ""; n := nops(elem); for i to n do; c := elem[i]; s := `if`(not (member(c, {$"a".."z"})), cat(s,c), cat(s,UpperCase(c),"'")); end; return s; end proc: # externalTerm # Routine: externalExpression # Abstract: Given an expression, convert to external format # Example: {{"A","b"},{"C","D"}} --> AB' + CD externalExpression := proc(expr::set) local i,s; s := ""; for i to nops(expr) do; s := `if`(i = 1, externalTerm(expr[i]), cat(s," + ",externalTerm(expr[i]))); end do; return s; end proc: # externalExpression # Routine: negateVbl # Abstract: Given a variable in internal format, return # a variable in internal format that is its # negation. For example: v -> V, V -> v negateVbl := proc (v::string) ASSERT(length(v)=1); return `if`(member(v,{$"a".."z"}),UpperCase(v),LowerCase(v)); end proc: # negateVbl # Routine: hasVbl # Abstract: Determine if variable contained in term. # Returns: boolean result hasVbl := proc (t::set, v::string) ASSERT(length(v)=1); return `subset`({v},t); end proc: # hasVbl # Routine: sameTerm # Abstract: Determine if 2 terms are equal. Eg: XY and YX are equal # Returns: boolean result sameTerm := proc (t1::set, t2::set) return evalb(t1=t2); # could do: `subset`(t1,t2) and `subset`(t2,t1) end proc: # sameTerm # Routine: consensusPossible # Abstract: Determine if consensus of 2 given terms is possible. # This is true if a single variable is in negated form # in comparison of t1's variables and t2's variables. # Eg1: "ABC" and "ABc" -> true. # Eg2: "ABC" and "aBc" -> false (2 vbl flips) # Eg3: "X" and "x" -> false (no consensus of X and X') # Note: Concensus also possible if one term completely contained # within another. This is handled in consensusStep1 # Returns: boolean result consensusPossible := proc (t1::set, t2::set) local i, n, flips; if nops(t1)=1 and nops(t2)=1 then return false; # no concensus of X,X', etc end if; flips := 0; n := nops(t1); for i to n do; if (hasVbl(t2,negateVbl(t1[i]))) then flips := flips + 1; end if; end; return evalb(flips = 1); end proc: # consensusPossible # Routine: takeConsensus # Abstract: Given 2 terms which should be consensus-able; # return the consensus. Eg: "ABC" and "ABc" -> "AB" # Returns: consensus of 2 terms takeConsensus := proc(t1::set, t2::set) local flips, c, cnot, e, i, n, negatedVbl; # Process flipped variables, must be exactly 1 flips := 0; e := {}; n := nops(t1); for i to n do; c := t1[i]; cnot := negateVbl(c); if (hasVbl(t2,cnot)) then flips := flips + 1; negatedVbl := cnot; else e := e union {c}; end if; end do; ASSERT(flips=1,"Bad call to takeConsensus, flips not 1"); # add any vbls from t2 that are not in t1 n := nops(t2); for i to n do; c := t2[i]; if (c <> negatedVbl) then e := e union {c}; end if; end; return e; end proc: # takeConsensus # Routine: termContained # Abstract: Determine if one term contained in another. # Eg: AB and ABC --> true # ABC and ABD --> false # AB and AB --> false # Returns: boolean result termContained := proc(t1::set, t2::set) return (`subset`(t1,t2) or `subset`(t2,t1)) and evalb(t1<>t2); end proc: # termContained # Routine: consensusStep1 # Abstract: Remove superfluous terms which are supersets of # other terms in the expression. # Eg: AB and ABCDE --> AB # Returns: Reduced expression (set) consensusStep1 := proc(expr::set) local e, i, j, k, n, t, dropset, newset, allpairs, pair; e := expr; # consensus_printf("Step1 start: %s\134n", externalExpression(e)); dropset := {}; n := nops(e); allpairs := combinat:-choose(n,2): # all combos of 2 indexes into e for pair in allpairs do; i := pair[1]; j := pair[2]; if termContained(e[i],e[j]) then # Contained term! if (nops(e[i]) < nops(e[j])) then # e[i] contained in e[j] => drop e[j] t := j; k := i; # drop e[j] else # e[j] contained in e[i] => drop e[i] t := i; k := j; # drop e[i] end if; if (not member(t, dropset)) then dropset := dropset union {t}; consensus_printf("Simplify: combine terms %s + %s --> %s\134n", externalTerm(e[i]),externalTerm(e[j]),externalTerm(e[k])); end if; end if; # termContained end do; # for pair in allpairs if (nops(dropset) > 0) then newset := {}; for i to n do; if (not member(i, dropset)) then newset := newset union {e[i]}; end if; end do; e := newset; consensus_printf("Result: %s\134n", externalExpression(e)); end if; # consensus_printf("Step1 end: %s\134n", externalExpression(e)); return e; end proc: # consensusStep1 # Routine: consensusStep2 # Abstract: Given expression (list), perform consensus on # terms which have a single variable changed. # Eg: XY, XY'Z -> XZ # Returns: expression with consensus terms added (set) consensusStep2 := proc(expr::set) local e, t, loops, moreToCheck, allpairs, pair, added; e := expr; # consensus_printf("Step2 start: %s\134n", externalExpression(e)); moreToCheck := true; loops := 0; added := 0; while moreToCheck do; moreToCheck := false; # assume no more consensus terms allpairs := combinat:-choose(e,2): # all combos of 2 terms of e for pair in allpairs do; if (consensusPossible(pair[1],pair[2])) then # May take consensus of terms, useful if consensus is not already a term in e t := takeConsensus(pair[1],pair[2]); if not `subset`({t},e) then moreToCheck := true; consensus_printf("Adding consensus term of %s and %s --> %s\134n", externalTerm(pair[1]),externalTerm(pair[2]),externalTerm(t)); e := e union {t}; # add consensus term - modifies e, breaks indexes into e added := added + 1; break; # added term -- break from while i loop end if; # not subset end if; # consenusPossible end do; # for nextpair # Guard against infinite loop loops := loops + 1; if (loops >= 1500) then printf("*** Max loops in concensusStep2, terminating ***\134n"); return(e); end if; end do; # while moreToCheck if (added > 0) then consensus_printf("Result: %s\134n",externalExpression(e)); end if; # consensus_printf("Step2 end: %s\134n", externalExpression(e)); return e; end proc: # consensusStep2 end module: # Consensus_Method with(Consensus_Method);

NiM3I0kqY29uc2Vuc3VzRzYi