Verfahren nach Quine und McCluskey (Source)
Bitte geben Sie die Bitkombinationen an, welche die gewünscht Funktion beschreiben.
Die Reihenfolge der eingegebenen Zahlen geht von Xn...X0 (höherwertiges Bit zuerst).
10 (dezimal)
*/
function minterm($str){
$this->marked=false; /*initialize values*/
$this->val=0;
$this->len=strlen($str);
$this->str=$str;
$this->prime=false;
for($i=0;$i<$this->len;$i++){
if($str[$i]=='1')
$this->val=$this->val+pow(2,$this->len-$i-1);
else if($str[$i]!='0'){
$this->val=-1;
echo "Fehler beim Erkennen des MinTerms $str an Position $i:".$str[$i];
break;
}
}
}
/*mark as prime*/
function setprime(){
$this->prime=true;
}
/*returns true if this minterm is a prime*/
function isprime(){
return $this->prime;
}
function ismarked(){
return $this->marked;
}
function mark(){
$this->marked=true;
}
/*unmark*/
function dmark(){
$this->marked=false;
}
/*compare with an other minterm, if equal except 1 bit, then delete this bit*/
function compare($min){
$pos=0;
$diff=0;
for($i=0;$i<$this->len;$i++) {
if (($this->str[$i]!=$min->str[$i]) && ($this->str[$i]!='-')) {
$pos=$i; /*store position of different bit*/
$diff++; /*count differences*/
} else {
if (($this->str[$i]=='-') && ($min->str[$i]!='-')) {
$diff = -1;
break;
}
}
}
if ($diff != 1){ /*difference is one bit, mark this one*/
return -1;
}
return $pos;
}
function dump(){
echo "
".$this->str." Primimplikant: ".(($this->isprime())?"
Ja":"Nein");
if (count($this->impls)>0) {
echo ", Entstanden durch: ".$this->impls[0];
}
for ($cnt=1; $cnt
impls); $cnt++) {
echo ", ".$this->impls[$cnt];
}
echo ".
";
}
}
class quine {
var $minterme; /*array of all minterms*/
var $colhead = array();
/* parse string and fill the minterm array
bsp.:
00010
00011
01001
10011
*/
function initialize($data){
$this->minterme=array();
$lines=split("\n",$data);
while(list(,$val)=each($lines)){
$val=str_replace("\n","",$val); /*Remove linebreaks from input*/
$val=str_replace("\r","",$val);
if ($val!='') {
array_push($this->minterme,new minterm($val));
array_push($this->colhead, $this->BStrToInt($val));
}
}
}
function dump($var){
for($i=0;$idump();
}
/**/
function optimize(){
$i=0;
$j=0;
$res=array();
$minterme=$this->minterme;
$implicants=1;
echo "Berechnung der Primimplikanten
";
$this->dump($minterme);
while($implicants>0) {
$res=array();
$implicants=0;
echo "Terme gefunden: ".count($minterme)."
";
for($i=0;$iisprime()) continue; /* skip primes */
for($j=$i+1;$jisprime()) continue; /* skip primes */
if ($minterme[$i]->str==$minterme[$j]->str) {
$minterme[$j]->mark();
continue;
}
$pos=$minterme[$i]->compare($minterme[$j]);
if ($pos!=-1){
$minterme[$i]->mark();
$minterme[$j]->mark();
array_push($res,$minterme[$i]);
$res[count($res)-1]->str[$pos]='-';
if (count($res[count($res)-1]->impls)==0) {
array_push($res[count($res)-1]->impls, $minterme[$i]->str);
array_push($res[count($res)-1]->impls, $minterme[$j]->str);
} else {
$res[count($res)-1]->impls = array_merge($minterme[$i]->impls, $minterme[$j]->impls);
}
$implicants++;
}
}
}
for($i=0;$iismarked()){
$minterme[$i]->setprime(); /*mark as primiplicant*/
array_push($res,$minterme[$i]);
}
}
for($i=0;$idmark();
}
$minterme=$res;
$this->dump($minterme);
}
echo "Primterme gefunden: ".count($minterme)."
";
$this->minterme = $minterme;
}
/* build a prime term array table */
function primetable() {
$minterme=$this->minterme;
$table = array();
echo "Primtermtabelle
";
$entries = $minterme[0]->impls;
for ($cnt=1; $cntimpls);
}
$entries = array_unique($entries);
asort($entries);
reset($entries);
for ($termcnt=0; $termcntimpls);
$found = 0;
while (list($termkey, $termentrie) = each($minterme[$termcnt]->impls)) {
if ($termentrie == $entrie) {
$found = 1;
break;
}
}
array_push($subary, $found);
$cnt++;
}
array_push($table, $subary);
}
return ($table);
}
/* convert a binary string "000100101..." to an integer */
function BStrToInt($str) {
$retval = 0;
$pos = 0;
for ($cnt=(strlen($str)-1); $cnt>=0; $cnt--) {
if ($str[$cnt] == '1') {
$retval += 1<<$pos;
}
$pos++;
}
return ($retval);
}
function dominance()
{
if (count($this->minterme)==0) {
echo "Minimale Funktion:
";
echo "Y = 0";
return;
}
$prim = $this->primetable();
$xmask = array();
$ymask = array();
$x = count($prim[0]);
$y = count($prim);
/* initialize mask with zeros */
for($cnt=0; $cnt<$x; $cnt++) $xmask[$cnt] = 0;
for($cnt=0; $cnt<$y; $cnt++) $ymask[$cnt] = 0;
/* simplify */
$change = 1;
$dir = 0;
while ($change) {
/* show table */
$this->tabdump($x, $y, $prim, $xmask, $ymask);
/* simplify */
$change = $this->tabdomina($x, $y, $prim, $dir, $xmask, $ymask);
printf ("* %sdominanzpruefung ergab:
", ($dir)?"Zeilen":"Spalten");
$dir = ~$dir;
}
$this->tabdump($x, $y, $prim, $xmask, $ymask);
$this->tabdisj($x, $y, $prim, $xmask, $ymask);
return(0);
}
/* dir = true->horizontally, false->vertically */
function tabconv($x, $y, &$ary, $entry, $dir, &$xmask, &$ymask)
{
$ret = 0;
for ($cnt=0; $cnt<(($dir)?$x:$y); $cnt++) {
if ($dir) {
if ($xmask[$cnt]) continue;
$ret += ($ary[$entry][$cnt])?1<<$cnt:0;
} else {
if ($ymask[$cnt]) continue;
$ret += ($ary[$cnt][$entry])?1<<$cnt:0;
}
}
return($ret);
}
/* check for column and row dominances */
/* dir = true->horizontally, false->vertically */
function tabdomina($x, $y, &$ary, $dir, &$xmask, &$ymask)
{
/* minimize rows */
$max = ($dir)?$y:$x;
$change = 0;
for ($cnt=0; $cnt<$max; $cnt++) {
if ($dir) {
if ($ymask[$cnt]) continue; /* skip already masked rows */
} else {
if ($xmask[$cnt]) continue; /* skip already masked columns */
}
$sum = $this->tabconv($x, $y, $ary, $cnt, $dir, $xmask, $ymask);
printf("- Überprüfe %s %s (%s).
\n", ($dir)?"Zeile":"Spalte", $cnt, $sum);
if ($sum == 0) {
printf ("! %s leer, keine Pruefung notwendig.
\n", ($dir)?"Zeile":"Spalte");
continue;
}
for ($subcnt=0; $subcnt<$max; $subcnt++) {
if ($cnt == $subcnt) continue; /* don't compare to yourself */
if ($dir) {
if ($ymask[$subcnt]) continue; /* skip already masked rows */
if (($sum|$this->tabconv($x, $y, $ary, $subcnt, $dir, $xmask, $ymask))==$sum) {
$ymask[$subcnt] = true;
printf("! Maskiere Zeile %s.
\n", $subcnt);
$change = 1;
}
} else {
if ($xmask[$subcnt]) continue; /* skip already masked columns */
if (($sum&$this->tabconv($x, $y, $ary, $subcnt, $dir, $xmask, $ymask))==$sum) {
$xmask[$subcnt] = true;
printf("! Maskiere Spalte %s.
\n", $subcnt);
$change = 1;
}
}
}
}
printf("\n");
return($change);
}
/* output table */
function tabdump($x, $y, &$ary, &$xmask, &$ymask)
{
echo '| | ';
for ($xcnt=0; $xcnt<$x; $xcnt++) {
if ($xmask[$xcnt]) continue;
printf("%4s | ", $this->colhead[$xcnt]);
}
echo "
|---|
";
for ($ycnt=0; $ycnt<$y; $ycnt++) {
if ($ymask[$ycnt]) continue;
printf("| %4s | ", "P".($ycnt+1));
for ($xcnt=0; $xcnt<$x; $xcnt++) {
if ($xmask[$xcnt]) continue;
printf("%3s | ", $ary[$ycnt][$xcnt]);
}
echo "
";
}
echo "
";
}
/* output disjunctive normal form */
function tabdisj($x, $y, &$ary, &$xmask, &$ymask)
{
$minterme = $this->minterme;
$outstr = "Y = ";
for ($cnt=0; $cnttabcnv($minterme[$cnt]->str)."+ ";
}
$outstr = substr($outstr, 0, strlen($outstr)-strlen(" + "));
echo "Minimale Funktion:
";
echo "$outstr";
}
/* convert primterms to alpha characters */
function tabcnv($str)
{
$cntup = 0;
$res = "";
for ($cnt=strlen($str)-1; $cnt>=0; $cnt--) {
if ($str[$cnt] == "0") {
// $res .= "(!".chr($cntup+97).")";
$res .= "(!x".$cntup.") ";
} elseif ($str[$cnt] == "1") {
// $res .= chr($cntup+97);
$res .= "x".$cntup." ";
}
$cntup++;
}
if (strlen($res)==0) $res = "1 ";
return ($res);
}
}
error_reporting(E_ALL);
if (@$_POST['calc']=='true'){
$quine=new quine();
$quine->initialize($_POST['data']);
$quine->optimize();
$quine->dominance();
}
?>