Location: PHPKode > scripts > Quine-McCluskey Method > quine-mccluskey-method/QM.class.php
```<?php

/*
* Quine-McCluskey Method php5 Class <Beta Version> <2007-11-05>
*
* Author: Armin Randjbar-Daemi <randjbar at gmail dot com>
* Demo: http://www.omnistream.co.uk/qm/
*/

class QM {
//data members
static private \$VAR;
private \$minterm;
private \$dontcare;
//binary matrix-decimal matrix-marks array
private \$QM_matrix;
private \$dec_matrix;
private \$mark;
//after First Algorithm
public \$primary_result;
//for Comparison Double-Loop
private \$x;
private \$y;
//for bit by bit Comparison
private \$difference;
private \$flag="0";
//check_redundancy
private \$recived_minterms;
private \$implicantsBin;
private \$implicantsDec;
//Final Result array
public \$essentialPrimes;

/////////////////////
//Constructor
/////////////////////

public function __construct(\$var_num,\$minterm,\$dontcare)
{
self::\$VAR=\$var_num;
\$this->minterm=\$minterm;
\$this->dontcare=\$dontcare;

//First Algorithm
\$this->create_matrix();
\$this->QM_comparison(0,count(\$this->QM_matrix));
\$this->primary_result();
//Second Algorithm
//1. Pick the column with the least number of "1"s in it. If there is more than one column, pick the first one.
//2. In this column, pick the "1" whose row will get us the greatest number of uncovered minterms.
//3. put "1" into every index of \$mintermsDone that corresponds to a column with a "1" in \$maxChecksRow
//4. add implicant \$maxChecksRow to \$essentialPrimes array
\$this->check_redundancy(
\$this->recived_minterms,
\$this->implicantsDec,
\$this->implicantsBin
);
}

////////////////////
//Public Functions
////////////////////

public function create_matrix()
{
\$this->decimal_matrix();
for (\$a = 0; \$a < count(\$this->minterm); \$a++)
{
\$this->dec_2_bin(\$a);
\$this->more_zero(\$a);
}
\$this->create_mark();
\$this->binary_matrix();
}

public function QM_comparison(\$n,\$m)
{
\$this->flag="0";
for (\$this->x = \$n; \$this->x < \$m; \$this->x++)//select first minterm
for (\$this->y = \$this->x+1; \$this->y < \$m; \$this->y++)//select second minterm
{
\$this->difference="0";
if (count(\$this->QM_matrix[\$this->x])==count(\$this->QM_matrix[\$this->y]))//selected minterms have equal length
for (\$bit = 0; \$bit < count(\$this->QM_matrix[\$this->x]); \$bit++)//Compare minterms bit by bit
\$this->bit_by_bit(\$bit);

if (\$this->difference=="1")//the difference is only 1 bit
{
\$this->combine_minterms();
\$this->unset_repeated(\$m);
}
}
if (\$this->flag=="1")//call the function again
\$this->QM_comparison(\$m,count(\$this->QM_matrix));
}

public function primary_result()
{
for (\$i = 0; \$i < count(\$this->mark); \$i++)
if (\$this->mark[\$i]=="no")
{
\$this->implicantsDec[]=\$this->dec_matrix[\$i];
\$this->implicantsBin[]=implode(\$this->QM_matrix[\$i]);//TEMP binary results
\$temp_dec[]=implode(',',\$this->dec_matrix[\$i]);//TEMP decimal results
}
//save primary result as String so you can show them too
\$this->primary_result=implode('<br />',\$this->implicantsBin).implode('<br />',\$temp_dec);
}

public function check_redundancy(\$minterms,\$implicantsDec,\$implicantsBin)
{
for (\$i = 0; \$i < count(\$minterms); \$i++)
for (\$j = 0; \$j < count(\$implicantsBin); \$j++)
{
\$checkTable[\$j][\$i]="0";
for (\$k = 0; \$k < count(\$implicantsDec[\$j]); \$k++)
{
if (\$implicantsDec[\$j][\$k]==\$minterms[\$i])//\$implicantsBin[\$i] Covers \$minterms[\$j]
\$checkTable[\$j][\$i]="1";//\$checkTable[implicant][minterm]
}
}
\$mintermsDone=array_fill(0,count(\$minterms),0);//to keep track of all minterms, fill the array with "0"
while (in_array(0,\$mintermsDone))//while: not every index in \$mintermsDone contains "1"
{
\$minChecksCol=NULL;
\$maxChecksRow=array();
//1
for (\$col = 0; \$col<count(\$checkTable[0]); \$col++)
{
if (\$mintermsDone[\$col]=="0")
{
\$tempCol=array();
for (\$row = 0; \$row<count(\$implicantsBin); \$row++)
\$tempCol[]=\$checkTable[\$row][\$col];

if (!is_array(\$minChecksCol)||array_sum(\$minChecksCol)>array_sum(\$tempCol))
{
\$minChecksCol=\$tempCol;
\$minColNum=\$col;
}
}
}
//2
for (\$i = 0; \$i<count(\$minChecksCol);\$i++)
if (\$minChecksCol[\$i]=="1")
{
\$tempSum=NULL;
for (\$x = 0; \$x<count(\$checkTable[\$i]); \$x++)
if (\$mintermsDone[\$x]=="0") \$tempSum[]=\$checkTable[\$i][\$x];

if (array_sum(\$maxChecksRow)<=array_sum(\$tempSum))
{
\$maxChecksRow=\$checkTable[\$i];
\$maxRowNum=\$i;
}
}
//3
for (\$w = 0; \$w<count(\$maxChecksRow);\$w++)
if (\$maxChecksRow[\$w]=="1")\$mintermsDone[\$w]="1";
//4
\$this->essentialPrimes[]=\$implicantsBin[\$maxRowNum];//Final Result
}//while End
}

//////////////////////
//Private Functions
//////////////////////

private function decimal_matrix()
{
\$min_dont=\$this->minterm." ".\$this->dontcare;
\$this->minterm=explode(" ",\$this->minterm);
\$this->recived_minterms=\$this->minterm;//only minterms
\$this->minterm=explode(" ",\$min_dont);//minterms + dont cares

for (\$i = 0; \$i < count(\$this->minterm); \$i++)
\$this->dec_matrix[\$i][0]=\$this->minterm[\$i];
}

private function dec_2_bin(\$a)
{
\$this->minterm[\$a]=decbin(\$this->minterm[\$a]);
}

private function more_zero(\$a)
{
\$more_zero="";
if(self::\$VAR-strlen(\$this->minterm[\$a])>"0")
for(\$z = 0; \$z < self::\$VAR-strlen(\$this->minterm[\$a]); \$z++) \$more_zero.="0";
\$this->minterm[\$a]=\$more_zero.\$this->minterm[\$a];
}

private function create_mark()
{
for(\$i = 0; \$i < count(\$this->minterm); \$i++) \$this->mark[\$i]="no";
}

private function binary_matrix()
{
for (\$i = 0; \$i < count(\$this->minterm); \$i++)
for (\$j= 0; \$j < strlen(\$this->minterm[\$i]); \$j++)
{
\$this->QM_matrix[\$i][\$j]=substr(\$this->minterm[\$i],\$j,1);
}
}

private function bit_by_bit(\$bit)
{
if (\$this->QM_matrix[\$this->x][\$bit]!=\$this->QM_matrix[\$this->y][\$bit])
\$this->difference++;
}

private function combine_minterms()
{
\$this->flag="1";
\$new_row=count(\$this->QM_matrix);

\$this->mark[\$new_row]="no";//create new row in mark array
\$this->mark[\$this->x]="yes";//mark the combining minterms
\$this->mark[\$this->y]="yes";

for (\$i = 0; \$i < count(\$this->dec_matrix[\$this->x]); \$i++)//add new decimals
{
\$this->dec_matrix[\$new_row][]=\$this->dec_matrix[\$this->x][\$i];
\$this->dec_matrix[\$new_row][]=\$this->dec_matrix[\$this->y][\$i];
}

for (\$i = 0; \$i < count(\$this->QM_matrix[\$this->y]); \$i++)
{
if (\$this->QM_matrix[\$this->x][\$i]==\$this->QM_matrix[\$this->y][\$i])
\$this->QM_matrix[\$new_row][\$i]=\$this->QM_matrix[\$this->y][\$i];
else
\$this->QM_matrix[\$new_row][\$i]="X";
}
}

private function unset_repeated(\$m)
{
\$matrix_end=count(\$this->QM_matrix);
for (\$x = \$m; \$x < \$matrix_end; \$x++)
for (\$y = \$x+1; \$y < \$matrix_end; \$y++)
if (\$this->QM_matrix[\$x]==\$this->QM_matrix[\$y])//unset one of repeated products
{
unset(\$this->QM_matrix[\$y]);
unset(\$this->dec_matrix[\$y]);
unset(\$this->mark[\$y]);
}
}

}//Class End
?>```