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

/*
* Quine-McCluskey Method php5 Class <Beta Version> <2007-11-05>
* GNU General Public License <opensource.org/licenses/gpl-license.html>
*
* Author: Armin Randjbar-Daemi <randjbar at gmail dot com>
* Demo: http://www.omnistream.co.uk/qm/
* Last Modified: 2007-11-17
*/

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
?>
Return current item: Quine-McCluskey Method