voici le code:
<?
require("./includes/guilfoos.inc" );
/* QMF: SIMPLIFICATION TOOL, BY USING THE QUINE - MCCLUSKY PROCESS,
Copyright (C) 2000 Brian Guilfoos
This program is free software; you can redistribute it and / or
modify it under the terms of the GNU general Public License as
published by the Free software Foundation; either version 2 of
the License, or any later version.
This program is distributed in the hope that it wants be useful,
BUT WITHOUT ANY WARRANTY; WITHOUT EVEN THE IMPLIED WARRANTY OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received at copy of the GNU general Public License
along with this program; if necessary, write to the Free software
Foundation, Inc., 59 Temple Place Suite 330, Boston, MA 02111-1307
*/
top("Quine-McClusky Algorithm","Software: Quine-McClusky Algorithm","quinemcclusky" );
?>
<!-- BEGIN BODY CONTENT -->
<?
function print_array($array) {
if(gettype($array)=="array" ) {
echo "<ul>";
while (list($index, $subarray) = each($array) ) {
echo "<li>$index <code>=></code> ";
print_array($subarray);
echo "</li>";
}
echo "</ul>";
} elseif (gettype($array)=="object" ) {
$array->print_term();
} else echo $array;
}
function print_array_1($array) {
if(gettype($array)=="array" ) {
echo "( ";
while (list($index, $subarray) = each($array) ) {
print_array_1($subarray);
}
echo " )";
} else echo $array." ";
}
class Term {
var $representation;
var $ones;
var $used;
var $minterms;
function Term() {
$this->ones = 0;
$this->used = false;
}
function set_used() {
$this->used = true;
}
function is_used() {
return $this->used;
}
function define($value) {
$this->representation = $value;
$count = array_count_values($value);
$this->ones = $count[1];
}
function value() {
return $this->representation;
}
function ones() {
if ($this->ones == "" )
return 0;
else
return $this->ones;
}
function compare(&$result) {
$diff = 0;
$self = $this->representation;
for ($x=0; $x<count($this->representation); $x++)
{
$one = (string)$self[$x];
$two = (string)$result[$x];
if ($one == 'X')
{
if ($two != 'X')
{
$diff=1000;
}
} elseif ($one == '0')
{
if ($two == '1')
{
$result[$x] = 'X';
$diff++;
} elseif ($two == 'X')
{
$diff=1000;
}
} else
{
if ($two == '0')
{
$result[$x] = 'X';
$diff++;
} elseif ($two == 'X')
{
$diff=1000;
}
}
}
if ($diff == 1)
return true;
else
return false;
}
function ident($result) {
$self = $this->representation;
for ($x=0; $x<count($this->representation); $x++)
{
$one = (string)$self[$x];
$two = (string)$result[$x];
if ($one == 'X')
{
if ($two != 'X')
{
return false;
}
} elseif ($one == '0')
{
if ($two != '0')
{
return false;
}
} else
{
if ($two == '0')
{
return false;
}
}
}
return true;
}
function cover($minterm) {
$diff = 0;
for ($x=0; $x<count($this->representation); $x++) {
$one = (string)$this->representation[$x];
$two = (string)$minterm[$x];
if ($one != $two) {
if ($one != 'X') {
$diff++;
}
}
}
if ($diff>0)
return false;
else
return true;
}
function add_minterm ($minterm) {
$this->minterms[count($this->minterms)]=$minterm;
}
function minterms () {
return $this->minterms;
}
function print_term() {
print_array_1($this->representation);
}
}
function convert_min_to_bin($minterm, $variables) {
$value = $minterm;
$result=array();
while ($value > 0) {
$remainder = $value % 2;
$value = floor($value/2);
array_unshift($result, $remainder);
}
return array_pad($result,0 - $variables, 0);
}
function compare_groups(&$group0, &$group1) {
$k=0;
$group2=array();
for ($i=0;$i<count($group0);$i++) {
//compare each term in group0 with each term group1
$term0 = new Term;
$term0 = $group0[$i];
for($j=0;$j<count($group1);$j++) {
$term1 = new Term;
$term1 = $group1[$j];
$result = $term1->value();
if ($term0->compare($result) == true) {
$term0->set_used();
$term1->set_used();
$term2 = new Term;
$term2->define($result);
$group2[$k] = $term2;
$k++;
$group1[$j] = $term1;
$group0[$i] = $term0;
}
}
}
return $group2;
}
function check_dominance(&$prime_implicants,$minterm) {
$z=count($prime_implicants);
for ($x=0;$x<$z;$x++) {
$term = new Term;
$term = array_shift($prime_implicants);
if ($term->cover($minterm) == true) {
$otherterms = $term->minterms();
$y=count($prime_implicants);
for($i=0;$i<$y;$i++) {
$this_term = new Term();
$this_term = array_shift($prime_implicants);
$this_term_mins = $this_term->minterms();
if ((count($this_term_mins) == 0)) {
//term unused
} else {
$test1 = array_diff($otherterms,$this_term_mins);
$test2 = array_diff($this_term_mins,$otherterms);
if ((count($test1) == 1) and (count($test2) == 0)) {
//this term is dominated by term -> drop it!
} else {
array_push($prime_implicants, $this_term);
}
}
}
}
array_push($prime_implicants,$term);
}
}
function main($minterms, $dont_cares, $variables) {
// get $minterms, $dont_cares and $variables from web page
$minterms = explode(",", $minterms);
$dont_cares = explode(",", $dont_cares);
$terms = array_merge($minterms, $dont_cares);
echo "<p>Minterms: ";
print_array_1($minterms);
echo "</p><p>Don't Cares: ";
print_array_1($dont_cares);
echo "</p>\n";
$groups=array();
$prime_implicants=array();
for($x=0;$x<count($terms);$x++) {
//convert term to binary form
$result = convert_min_to_bin($terms[$x],$variables);
$term = new Term;
$term->define($result);
//put term in group (my # of ones)
$group = $groups[$term->ones()];
$group[count($group)]=$term;
$groups[$term->ones()] = $group;
}
// now we have array "groups" containing arrays of minterms
while (count($groups)>1) {
// create new groups
$newgroups = array();
for($x=0;$x<count($groups)-1;$x++) {
$group0 = $groups[$x];
$group1 = $groups[$x+1];
$newgroup = compare_groups($group0,$group1);
if (is_array($newgroup)) {
$newgroups[count($newgroups)]=$newgroup;
}
$groups[$x] = $group0;
$groups[$x+1] = $group1;
}
// gather current minterms
for($x=0;$x<count($groups);$x++) {
$group = $groups[$x];
for($i=0;$i<count($group);$i++) {
$term = new Term;
$term = $group[$i];
if ($term->is_used() == false) {
$prime_implicants[count($prime_implicants)] = $term;
}
}
}
//trim duplicates
for($x=0;$x<count($newgroups);$x++) {
$group = $newgroups[$x];
$newgroup = array();
while(count($group)>0) {
$term0 = new Term;
$term0 = array_shift($group);
$k=count($group);
for ($i=0;$i<$k;$i++) {
$termi = new Term;
$termi = array_shift($group);
if ($term0->ident($termi->value()) == false) {
array_push($group,$termi);
}
}
array_push($newgroup,$term0);
}
$newgroups[$x]=$newgroup;
}
//prepare for next pass
$groups = $newgroups;
}
echo "<p>List of Prime Implicants:";
print_array($prime_implicants);
echo "</p>\n";
//now have minimal functions... create covering chart
$covering_chart=array();
$minterms_not_covered = array();
for($x=0; $x<count($minterms); $x++) {
$minterm = convert_min_to_bin($minterms[$x],$variables);
for($i=0; $i<count($prime_implicants); $i++) {
$term = new Term;
$term = $prime_implicants[$i];
if ($term->cover($minterm)) {
$covered_by = $covering_chart[$minterms[$x]];
$covered_by[count($covered_by)] = $term->value();
$covering_chart[$minterms[$x]] = $covered_by;
$term->add_minterm($minterms[$x]);
$minterms_not_covered[$minterms[$x]]++;
}
$prime_implicants[$i] = $term;
}
}
// determine necessary terms
asort($minterms_not_covered);
reset($minterms_not_covered);
$covering_function = array();
$essential_terms = array_keys($minterms_not_covered,1);
while(count($essential_terms)>0) {
$covered_by = $covering_chart[$essential_terms[0]];
$termvalue = $covered_by[0];
$k = count($prime_implicants);
for ($x=0;$x<$k;$x++) {
$term = new Term;
$term = array_shift($prime_implicants);
if ($term->ident($termvalue) == true) {
$term->set_used();
array_push($covering_function,$term);
$otherterms = $term->minterms();
for($i=0;$i<count($otherterms);$i++) {
$otherterm = $otherterms[$i];
$minterms_not_covered[$otherterm]=0;
}
break;
} else {
array_push($prime_implicants,$term);
}
}
$temp = array_shift($essential_terms);
}
//remove covered terms
$temp_array = array("-1" => "0" );
$minterms_not_covered = array_diff($minterms_not_covered,$temp_array);
asort($minterms_not_covered);
reset($minterms_not_covered);
while(count($minterms_not_covered)>0) {
$minterm_number = array_keys($minterms_not_covered);
$temp_term=convert_min_to_bin($minterm_number[0],$variables);
check_dominance($prime_implicants,$temp_term);
$covered_by = $covering_chart[$minterm_number[0]];
$termvalue = $covered_by[0];
$k = count($prime_implicants);
for ($x=0;$x<$k;$x++) {
$term = new Term;
$term = array_shift($prime_implicants);
if ($term->cover($temp_term) == true) {
$term->set_used();
array_push($covering_function,$term);
$otherterms = $term->minterms();
for($i=0;$i<count($otherterms);$i++) {
$otherterm = $otherterms[$i];
$minterms_not_covered[$otherterm]=0;
}
break;
} else {
array_push($prime_implicants,$term);
}
}
$minterms_not_covered = array_diff($minterms_not_covered,$temp_array);
asort($minterms_not_covered);
reset($minterms_not_covered);
}
echo "<p>Minimal Covering Function:";
print_array($covering_function);
echo "</p>\n";
}
?>
<p>This is a simple program that takes a set of minterms, don't cares, and a number of variables
(from a Karnaugh Map) and determines the minimum covering function using the Quine-McClusky algorithm.
Not very complicated, but I did it for a grad-level course in logic circuit design during my
undergrad. It works, and is useful if you understand what I'm talking about, so it's been preserved
for posterity. Source available (see link at the bottom of the page).</p>
<form method="post" action="http://www.guilfoos.com/brian/quine_mcclusky/qmf.php">
<p>Minterms:<input type="text" name="minterms" size="40" maxlength="40" /><br />
Don't Cares:<input type="text" name="dont_cares" size="40" maxlength="40" /><br />
Variables:<input type="text" name="variables" size="40" maxlength="40" /><br />
<input type="submit" name="Request" value="Submit This Form" /></p>
</form>
<? import_request_variables("p","p_" ); ?>
<? if ($p_variables != 0) {main($p_minterms, $p_dont_cares, $p_variables);}; ?>
<p><a href="/source.php?page_url=<? echo $_SERVER['PHP_SELF'] ?>">View Source</a></p>
<!-- END BODY CONTENT -->
<? bottom(); ?>
en C/C++ ?
)
);
Merci de nous faire partager tes pensees afbilou
