computer-architecture - 质数蕴涵数和 EPI

Question

我的 TA 解决了这个问题，Prime Implicant (PI) 数

f(a,b,c,d)= Sigma m(0,2,4,5,8,10,11,13,15) 

是 7，基本 PI (EPI) 的数量是 1。这将如何计算？我认为这是错误的。任何想法？

我的解决方案是：

Answer 1

为了给您提供更多的学习机会，我将在与您类似的另一个功能上以图形方式确定 PI 和 EPI 的过程。您可以使用完全相同的方法来求解您在问题中给出的函数的数字。请注意，有多种方法可以确定 PI 和 EPI，但我喜欢 Kmap 方法，因为它很好地说明了这个概念。[注意：在 OP 添加他的解决方案后，我修改了我的答案以包含原始功能]

例子：

假设我们有这个功能：

g(a,b,c,d) = Sigma m(0,4,7,9,10,11,12,13,15)

我们想要确定素蕴涵项 (PI) 和基本素蕴涵项 ( http://en.wikipedia.org/wiki/Imlicant ) 的数量。

第一步是为给定函数生成 Kmap ( http://en.wikipedia.org/wiki/Karnaugh_map )（因为它是作为最小项的总和给出的，用 1 填充 Kmap 中的点，形成给定术语列表的二进制表示）：

现在我们必须为 Kmap 的所有项找到最大的覆盖。这些最大覆盖的数量是 PI 的数量，每个最大的覆盖都是质蕴涵（即蕴涵或偏函数，不能用任何其他蕴涵进一步简化以形成更一般的蕴涵或更大的覆盖）。这样的覆盖是这样的：

现在我们有了覆盖物，我们可以计算这些最大的覆盖物。有 6 个，所以有 6 个 PI，这些覆盖物代表它们。现在，要获得 EPI 的数量，我们需要查看 Kmap 中有多少项被一个且仅一个覆盖覆盖。查看术语，它们是 0（仅被蓝色覆盖）、7（仅被绿色覆盖）、9（仅被橙色覆盖）和 10（仅被青色覆盖）。因此，有 4 个 EPI。

现在，在你的问题上试试这个方法，看看你得到了什么数字！

[更新：这是有关您的解决方案的信息]

你 Kmap 和覆盖对我来说似乎都很好：

从您的覆盖物可以看出，共有 7 个最大尺寸的覆盖物；6 沿对角线和 1 大的覆盖四个角。因此，如上所述，有 7 个 PI。要获得 EPI，我们需要查看这些 PI 中有多少唯一涵盖其中一个术语，即找到由一个且仅一个 PI 涵盖的术语，这些就是 EPI。查看 Kmap，只有具有项 8 和 2 的角仅由一个 PI 覆盖（即，4 个角覆盖）。虽然有两个术语，但它们共享保存覆盖，并记住覆盖是蕴涵项。因此，由于只有一个覆盖范围，包括由一个且只有一个覆盖范围覆盖的术语，因此只有 1 个 EPI。（所以，你的 TA 是正确的；7 个 PI 和 1 个 EPI）。