| > |
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\n",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\n",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 ***\n");
break;
end if;
end do; # while not all_done
# Display result
printf("Prime implicants: %s\n",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,{" ","\t","\n"})) 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\n", 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\n",
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\n", externalExpression(e));
end if;
# consensus_printf("Step1 end: %s\n", 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\n", 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\n",
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 ***\n"); return(e);
end if;
end do; # while moreToCheck
if (added > 0) then
consensus_printf("Result: %s\n",externalExpression(e));
end if;
# consensus_printf("Step2 end: %s\n", externalExpression(e));
return e;
end proc: # consensusStep2
end module: # Consensus_Method
with(Consensus_Method);
|
