卡诺图最小化器（三变量）

• 下载可执行文件 - 12.73 KB
• 下载源代码 - 6.1 KB

目录

• 引言
• 背景
• 算法
  • 输入项并排序
  • 执行比较
  • 确定素蕴含项
  • 确定必需素蕴含项
  • 构成函数
• 特殊情况
• 实现
  • 步骤 1
  • 第二步
  • 步骤 3
  • 步骤 4
  • 步骤 5
• 参考文献

引言

这个程序提供了一个通用的 C 语言代码（你可以称之为伪代码），可以在其他语言中实现，以解决 3 变量卡诺图问题。

背景

该程序使用了 Quine-McClusky 算法和 Petrick 方法，因为它们易于在编程中实现。

以下是一些使用此程序的技巧

1. 以十进制数字输入最小项，完成后输入 'q' 字符退出。
2. 输入“不关心的项”（如果存在），完成后输入 'q' 字符退出。
3. 选择函数形式（SOP 或 POS）。

算法

我将首先介绍算法，以便代码易于理解。

Quine - McClusky 算法的开发是为了实现卡诺图，这在数字设计或布尔函数简化中非常重要。该算法包含一些我们必须处理的步骤，才能使我们的项目或代码完美运行而没有任何错误。

步骤 1

收集所有最小项和不关心的项（如果存在），并将它们转换为二进制形式，然后将它们分组并列在一个列表中（称为列表 1）。

示例：如果我们有这些项（0,1,2,3,4,7,6），则分组应如下所示

• 组 0 包含二进制 [000]
• 组 1 包含二进制 [001 (十进制 0), 010 (十进制 2), 100 (十进制 4)]
• 组 2 包含二进制 [011 (十进制 3), 110 (十进制 6)]
• 组 3，最后一组，包含二进制 [111 (十进制 7)]

我们可以在这些组中看到，它们是根据每个二进制数中 1 的数量进行排序的。

第二步

比较组 1 与组 2，组 2 与组 3，组 3 与组 4，比较是通过比较第一组中的每个项与下一组中的所有项来完成的。比较的概念是，如果两个项只有一个不同的位，那么这个位必须被替换为 (-)，例如：（000, 001）==>（00-）。

在（列表 1）中完成比较后，进入列表 2 并执行相同的比较，但我们会发现一个新元素，即破折号（-），我们必须在比较中处理它。当我们比较两个带破折号的项时，仅当破折号在两个项中的位置相同时，比较才合法，否则我们无法比较这些项，例如：（00-, 01-）==>（0--），但（00-, 0-1）是非法的。

如果两个项成功比较，则在比较的项旁边会放置一个检查字符（例如，检查字符为 't'），如果不行，我的意思是这两个项有更多不同的位，或者两个项中的破折号位置不相同，那么必须在未比较的项旁边放置一个检查字符（例如，检查字符为 '*'）来指示我们将要在步骤 3 中讨论的内容。

注意：如果两个项无法比较，例如组 2 中的项和组 3 中的项，如果组 3 中的项稍后可以与组 4 中的项比较，则必须将 ('*') 指示符替换或覆盖为 ('t') 指示符。

	列表 1	列表 2	列表 3
组 0	000t	00-t	0--*
		0-0t	--0*
		-00t
组 1	001t	0-1t	-1-*
	010t	01-t
	100t	-10t
		1-0t
组 2	011t	-11t
	110t	11-t
组 3	111t

步骤 3

确定素蕴含项（如果在上面的任何列表中找到）。

注意：素蕴含项是无法进一步比较的项，并用 '*' 表示，例如：（0--, --0, -1-）。

步骤 4

形成覆盖表以确定必需素蕴含项。要形成此表，我们将最小项水平放置，素蕴含项垂直放置，然后我们应该确定一个素蕴含项覆盖哪些项，例如（0--）覆盖 0,1,2,3。并在与素蕴含项及其项对应的单元格中放置一个指示符（例如 'X'）。

	0	1	2	3	4	6	7
0-- (0,1,2,3)	x	x	x	x
--0 (0,2,4,6)	x		x		x	x
-1- (2,3,6,7)			x	x		x	x

现在，在完成表格后，我们可以通过主导具有唯一 'X' 的项的行和列来确定必需素蕴含项，例如：（1, 4, 7）。通过主导这些行，我们可以说与这些行对应的素蕴含项成为必需素蕴含项。

步骤 5

找到简化函数。众所周知，我们的示例给出了这些需要简化的项（0, 1, 2, 3, 4, 6, 7）。这些项如果不简化，应构成此函数

F = A'B'C' + A'B'C + A'BC' + A'BC + AB'C' + ABC' + ABC

其中，A、B、C 是变量，A'、B'、C' 是它们的补变量，它们的补称为文字，代表项的二进制形式。

简化后，函数如下所示

F = A' + C' + B

在（步骤 5）之前还有一步需要处理表格中剩余的素蕴含项，使用 Petrick 方法。我们将在后面的示例中讨论一些我们可能遇到的特殊情况。

特殊情况

1. 缺少一组，如果缺少像组 2 这样的组会怎样？

   在这种情况下，组 0 和组 1 可以进行比较，但组 1 由于缺少组 2 而无法进一步比较，因此组 3 保持原样，组 3 中的项被视为素蕴含项。

2. 重复项，我们在将项与其他项进行比较时，可能会在结果中遇到重复项。

   例如，在之前的示例中，在列表 2 中，项（00-, 01-）可以比较，结果将是项（0--）。项（0-0, 0-1）也可以比较，结果将是（0--），因此项（0--）是重复的，我们不能将其放入列表 3 中两次。

3. 如果我们输入了所有最小项（0, 1, 2, 3, 4, 5, 6, 7），则结果函数可以直接视为值 1（F = 1），而无需使用之前提到的任何步骤。
4. 不关心的项，不关心的项在Quine-McClusky 算法中需要特殊处理，因此如果一个问题或示例有这些项，我们将执行步骤 1,2,3，将这些项视为我们在上一个示例中处理的最小项，但在步骤 4 中，不应将这些项包含在覆盖表中。

示例：如果我们有这个问题，F = m(0,1,2,6) + d(4,5)，所有项，最小项和不关心的项都正常处理步骤 1,2,3，但步骤 4 中不应包含项（4, 5）。

实现

步骤 1

要实现步骤 1，我们应该从用户那里获取输入（最小项和不关心的项）作为数字，将最小项存储在一个数组中，将不关心的项存储在另一个数组中，然后将这些数字转换为其二进制等效值。将十进制数转换为二进制数有许多方法，下面是一个在函数中实现的常用技术。

char *ConvertToBinary(int num, char *bin)
{
int i;
int mask = 1;
int size = BINSIZE; 
 
for (i = size - 1; i >= 0; i--, num >>= 1)
    bin[i] = (mask & num) + '0';

bin[size] = '\0';
return bin; 
}

第二步

当所有输入都转换为二进制数后，我们将使用包含四个二维数组的数据结构将其分组，并通过使用结构数组将这些组划分为三个列表。

// The data structure that contains the groups from 0 ==> 3.
// Each array in this structure represents a group. 

typedef struct q_mc {
 
char ar0[SIZE][ROWSIZE];
char ar1[SIZE][ROWSIZE];
char ar2[SIZE][ROWSIZE];
char ar3[SIZE][ROWSIZE];
 
}Q_MC;

// Array of structures contains the lists from 1 ==> 3.
// Each element in the array represents a list.
 
Q_MC ar[NUMLIST] = {""};

在将用户输入的数据存储到数组ar中的第一个元素（list1）的结构中后，我们现在应该通过使用此函数来比较组（我们刚刚创建的数据结构）。

int CompareTerms(const char *ar1, const char *ar2, int size)
{
int i;
int count = 0;
int temp;
 
for (i = 0; i < size; i++)
{
   if (ar1[i] != ar2[i])
   {
      temp = i;
      count++;
   }
   else
      continue;
}
 

return (count == 1) ? temp : -1;
}

上一个函数接受两个string参数 'ar1' 和 'ar2'，这些string代表项的二进制形式（例如 01-, 11-）。函数接收其参数后，for 循环会检查两个string中的每个字符，如果一个string中的字符与第二个string中的字符不同，则函数返回该字符的位置，否则返回 (-1)。

完成比较后，检查字符（t, *）将附加到比较的项旁边。我们可以通过使用以下代码块来实现这一点。

if (bit_pos != -1)
{
    for (j = 0; j < BINSIZE; j++)
    {
       if (j == bit_pos)
          ar[1].ar0[_rows0][j] = '-';
       else
          ar[1].ar0[_rows0][j] = ar[0].ar1[index][j];
    }
    ar[0].ar0[0][BINSIZE] = 't'; 
    ar[0].ar0[0][BINSIZE+CHKCHAR] = '\0';
    ar[0].ar1[index][BINSIZE] = 't';
    ar[0].ar1[index][BINSIZE+CHKCHAR] = '\0';
    ar[1].ar0[_rows0][BINSIZE+CHKCHAR] = '\0';
   _rows0++;
}
else
{
    if (ar[0].ar0[0][BINSIZE] != 't')
       ar[0].ar0[0][BINSIZE] = '*'; 
    ar[0].ar0[0][BINSIZE+CHKCHAR] = '\0';
 
    if (ar[0].ar1[index][BINSIZE] != 't')
       ar[0].ar1[index][BINSIZE] = '*';
    ar[0].ar1[index][BINSIZE+CHKCHAR] = '\0';
}

我们从条件开始：如果 (bit_pos!= -1)，bit_pos 变量存储CompareTerms 函数的返回值。for 循环跟踪项的二进制形式，直到 j 变量达到不同位的.位置，如果是这样，则该位被替换为破折号 '**-'**，否则，不做任何操作，然后将新的二进制形式放入新列表中。

创建了新的二进制形式后，我们将字符 't' 附加到两个比较的项，并将 '*' 附加到未比较的项，但如果项已经附加了 't' 字符，则不应替换为 '*'，如果它们不能与其他项进行比较。

提示
ar[0] 指的是列表 1。
ar[1] 指的是列表 2。
ar[0].ar0 指的是列表 1 中的组 0。
ar[0].ar1 指的是列表 1 中的组 1。
ar[1].ar0 指的是列表 2 中的组 0。

步骤 3

确定素蕴含项。当我们放置检查字符时，现在确定哪个项是素蕴含项变得非常容易编程，我们唯一要做的就是使用 "strchr" 函数来查找一个string中是否找到 '*' 指示符，记住 '*' 指的是素蕴含项。例如，我将说明如何在列表 2 中的组 0 中捕获素蕴含项，使用以下代码。

for (index = 0; index < _rows0; index++)
{
    if (strchr(ar[1].ar0[index], '*') != NULL)
    {
        for (j = 0; j < BINSIZE; j++)
            prime_imp[k][j] = ar[1].ar0[index][j];
        prime_imp[k++][BINSIZE] = '\0';
    }
}

_rows0 是列表 2 中组 0 中的项数，如果 '*' 字符在组中的任何项中找到，它将被复制到一个保存素蕴含项的新数组中。

步骤 4

查找必需素蕴含项。这部分确定了将构成我们所需的布尔函数的必需素蕴含项。

每个素蕴含项中的破折号首先被转换为二进制状态，然后将二进制数转换为它们所覆盖的项。例如，如果素蕴含项有一个破折号，那么我们得到两种状态（0 或 1），如果有两个破折号，我们得到四种状态（00 或 01 或 10 或 11）。

在完成此替换后，我们将所有生成的二进制数转换为已由它们覆盖的项。

示例：素蕴含项（0--）的处理如下

(-1-) = 替换破折号 ==> (010, 011, 110, 111) 当我们得到这些二进制数时，现在我们可以将它们中的每一个与输入的二进制形式进行比较，以确定与素蕴含项状态相同的项。

如果输入和素蕴含项的状态的二进制数相同，则输入或输入的索引（或输入本身）存储在数组中。此代码可以实现比较部分。

for ( m = 0; m < n; m++)
     if (strcmp(store_inputs[m],prime_imp_bin) == 0)
store_index[l++] = m;

其中，n 是输入的数量。

• store_inputs 是一个（2D）数组，包含输入的二进制数。
• prime_imp_bin 数组包含素蕴含项的状态。
• store_index 数组存储仅与素蕴含项状态相同的每个输入的索引。

在存储了与素蕴含项状态相同的输入索引后，我们将对这些索引进行排序，以按升序排列，从而轻松删除重复的索引。

为什么我们要从覆盖表中删除最小项的重复索引？

答案：为了找出剩余的未重复的最小项索引。由未重复索引引用的最小项将指导我们找到构成我们函数的必需素蕴含项。

提示：未重复的最小项是指其列中只有一个 'X'（粗体）标记的项。

这里是实现排序和删除部分的.代码

qsort(store_index, l, sizeof(int), mycomp);
 

j = 0;
 
for (m = 0; m < l; m++)
{
    if (store_index[m] == store_index[m+1])
        continue;
    else if (store_index[m] != store_index[m+1] && store_index[m] == store_index[m-1])
        continue;
    else
        store_index2[j++] = store_index[m];
}

qsort 函数用于对字母和数字字符进行排序，正如我们所见，它接受一个存储我们要排序的数据的数组，该数组的长度，数组所持数据类型的大小以及 mycomp 函数，该函数被视为该函数的燃料，没有 mycomp 函数，qsort 将什么也不做。

如果我们有两个数字，例如（n1,n2），mycomp 函数如果 n1 < n2 则返回-1，如果 n1 = n2 则返回0，如果 n1 > n2 则返回1。

现在，在我们得到引用素蕴含项的最小项之后，这些项的索引存储在store_index2 数组中，我们将使用这些项来获取我们的必需素项。

我们可以使用以下代码块来达到我们的目标。

for ( m = 0; m < unrepeated_terms; m++)
{
    if (strcmp(store_inputs[store_index2[m]],prime_imp_bin) == 0)
    {
        prime_imp[index][BINSIZE] = '*';
        prime_imp[index][BINSIZE+CHKCHAR] = '\0';
        strncpy(ess_pri_imp[p++], prime_imp[index], BINSIZE);
    }
}

unreapted_terms 变量是未重复项的数量（其列中只有一个 X），strcmp 函数在每个输入（二进制形式）和每个素蕴含项的状态之间进行比较，在任何情况下它们相等时，素蕴含项本身而不是其状态被复制到ess_pri_imp 数组中。请参阅查找必需素蕴含项部分的完整代码，位于3_var.cpp 文件中，从第473行到第730行。

步骤 5

我们的函数有两种形式：SOP 和 POS。SOP 代表积之和 (Sum Of Products)，POS 代表和之积 (Product of Sum)。

要形成SOP 函数，首先将每个必需素蕴含项转换为字母形式。

示例：如果我们有这些必需蕴含项（0-1, 111, --0），这些项的字母形式应该如下

0-1 ===> A|C
111 ===> ABC
--0 ===> C|

在前面的示例中，我们使用了字母 A,B,C。实际上，我们可以使用任何字母，如 X,Y,Z。在任何 SOP 形式中，零位取字母的补（字母+条），因为我们没有条符号，我使用了符号 '|' 来表示字母的补。

第二：在每个项之后放置一个 '+' 运算符。

示例，表示前面这些项的函数是 " F = A|C + ABC + C| "。

让我们看一下可以实现 SOP 形式的代码。

printf("\n\n F = ");
 
for (index2 = 0; index2 < unrepeated_terms2; index2++)
{
    for (j = 0; j < BINSIZE; j++)
    {
        switch (j)
        {
        case 0:
            if (ess_pri_imp2[index2][j] == '0')
                printf("A|");
            else if (ess_pri_imp2[index2][j] == '1')
                putchar('A');
            break;
        case 1:
            if (ess_pri_imp2[index2][j] == '0')
                printf("B|");
            else if (ess_pri_imp2[index2][j] == '1')
                putchar('B');
            break;
        case 2:
            if (ess_pri_imp2[index2][j] == '0')
                printf("C|");
            else if (ess_pri_imp2[index2][j] == '1')
                putchar('C');
            break;
        }
    }
    if (index2 % unrepeated_terms2 == index2 && (unrepeated_terms2 - index2) > 1)
    {
        putchar(' ');putchar('+');putchar(' ');
    }
}

外层循环检查ess_pri_imp2 数组的内容，该数组包含必需素蕴含项。变量unrepeated_terms2 是我们拥有的必需素蕴含项的数量。

内层循环检查每个必需素蕴含项的位。然后我使用switch 将每个蕴含项分为位置（0,1,2）。每个位置都可以根据该蕴含项中的位状态取一个字母或其补。

代码中的最终if 条件控制在每个项之后添加 '+' 运算符，除了函数中的最后一个项。

形成POS 函数，我们使用与 SOP 相同的过程，但在 POS 中，我们将零位转换为字母的补，而一​​位取正常字母，并在代表位的每个字母后面加上 '+' 运算符来分隔文字（代表位的字母），然后我们将每个项放在括号中，使每个项看起来像一个和项，函数看起来像一个积之和。

参考文献

1. http://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm
2. http://en.wikipedia.org/wiki/Petrick%27s_Method
3. Digital Design Fundamentals, 2nd Ed [Kenneth J. Breeding]
4. Digital Fundamentals 9e [Floyd]

帮助

我的朋友总是说“没有人是完美的，但一个团队可以”，所以我希望有人能够完成这个代码，以覆盖超过 3 个变量。