boolean-logic - 创建逻辑门模拟器

Question

我需要创建一个应用程序来创建逻辑电路并查看结果。这主要用于 A-Level（英国，一般为 16-18 岁）计算机课程。

我从来没有做过这样的应用程序，所以不确定存储电路和评估结果的最佳设计（以可恢复的速度，比如 1.6Ghz 单核计算机上的 100Hz）。

而不是从基本门（和，或，nand等）构建电路，我想让这些门用于制造“芯片”，然后可以在其他电路中使用（例如，您可能想要制作一个8位寄存器芯片，或 16 位加法器）。

问题是这些电路的门数量大量增加，因此如果模拟在每个单独的门上工作，它将有 1000 个门要模拟，所以我需要简化这些可以放置在电路中的组件，以便它们可以被快速模拟。

我考虑为每个组件生成一个真值表，然后模拟可以使用查找表来查找给定输入的输出。尽管这样的表格的大小随着输入的增加而大幅增加，但我遇到了这个问题。如果一个芯片有 32 个输入，那么真值表需要 2^32 行。在许多情况下，这使用了大量的内存，因此对于非平凡的组件来说是不实用的，它也不适用于可以存储其状态的芯片（例如寄存器），因为它们不能简单地表示为输入和输出表。

我知道我可以硬编码诸如寄存器芯片之类的东西，但是由于这是出于教育目的，我想要它，以便人们可以制作自己的组件以及查看和编辑标准组件的实现。我考虑允许使用代码（例如 dll 或脚本语言）创建和编辑此类组件，例如，加法器可以表示为“输出 = 输入 A + 输入 B”，但是假设学生已经完成了足够的编程给定的语言能够理解和编写这样的插件来模仿他们电路的结果，这很可能并非如此......

是否有其他方法可以采用布尔逻辑电路并自动简化它，以便模拟可以快速确定组件的输出？

至于存储组件，我正在考虑存储某种树结构，以便在评估链接到其输入的所有组件后评估每个组件。

例如考虑： AB + C 模拟器将首先评估与门，然后使用与门和 C 的输出评估或门。

但是我突然想到，在输出链接回输入的情况下，将导致死锁，因为输入永远不会全部被评估......我该如何克服这个问题，因为程序只能评估一个门时间？

Answer 1

你看过Richard Bowles 的模拟器吗？

Answer 2

您不是第一个想要构建自己的电路模拟器的人 ;-)。

我的建议是确定一组最小的原语。当我开始我的（我打算在这些日子里恢复……）时，我有两个原语：

• 来源：零输入，一个始终为 1 的输出。
• 晶体管：两个输入A和B，一个输出即A and not B。

显然我有点误用了这个术语，更不用说忽视电子产品的细节了。关于第二点，我建议像我一样抽象成带有 1 和 0 的线。我从中获得了很多有趣的门和加法器图。当您可以将它们组装成电路并在集合周围画一个框（带有输入和输出）时，您可以开始构建更大的东西，例如乘法器。

如果你想要任何带有循环的东西，你需要加入某种延迟——所以每个组件都需要存储其输出的状态。在每个周期中，您都会从上游组件的当前状态更新所有新状态。

编辑关于您对可扩展性的担忧，如何默认使用根据状态和上游邻居模拟每个组件的第一原理方法，但提供优化子电路的方法：

• 如果您有一个S输入A[m]m < 8（例如，最多 256 行）和输出B[n]且没有循环的子电路，请生成真值表S并使用它。这可以针对已识别的子电路自动完成（如果子电路出现不止一次，则可以重复使用）或选择。

• 如果您有一个带有循环的子电路，您仍然可以生成真值表。这里有一些定点查找方法可以提供帮助。

• 如果您的子电路有延迟（并且它们对封闭电路很重要），则真值表可以包含状态列。例如，如果子电路具有输入 A、内部状态 B 和输出 C，其中 C <- A 和 B，B <- A，则真值表可以是：

  AB | 公元前
  0 0 | 0 0
  0 1 | 0 0
  1 0 | 1 0
  1 1 | 1 1

• 如果您有一个用户断言实现特定已知模式（例如“加法器”）的子电路，请提供使用硬编码实现来更新该子电路的选项，而不是通过模拟其内部部分。

Answer 3

当我制作了一个电路仿真器（遗憾的是，也是不完整且未发布的）时，这是我处理循环的方式：

• 每个电路元件存储其布尔值
• 当一个元素“E0”改变它的值时，它会通知（通过观察者模式）所有依赖它的人
• 每个观察元素都会评估其新值，并且也会这样做

当 E0 发生变化时，将保留所有受影响元素的 1 级列表。如果一个元素已经出现在这个列表中，它会被记住在一个新的 2 级列表中，但不会继续通知它的观察者。当 E0 开始的序列停止通知新元素时，处理下一个队列级别。即：按照顺序完成第一个元素添加到 level-2，然后下一个添加到 level-2，依此类推，直到所有 level-x 完成，然后移动到 level-(x+1)

这绝不是完整的。如果您曾经有多个振荡器进行无限循环，那么无论您采用什么顺序，一个都可能阻止另一个轮到它。我的下一个目标是通过使用基于时钟的同步而不是级联组合来限制步骤来缓解这种情况，但我的项目从未走到这一步。

Answer 4

您可能想看看从 Nand 到俄罗斯方块的 12 步课程软件。youtube上有一段视频在谈论它。

课程页面位于：http ://www1.idc.ac.il/tecs/

Answer 5

您可以对所有常见的进行硬编码。然后允许他们从硬编码的（包括低级门）中构建自己的，这将通过评估每个子组件来评估。最后，如果其中一个“芯片”的输入/输出少于 X，您可以将其“优化”到查找表中。也许检测它有多普遍并且只对最常用的 Y 芯片执行此操作？这样你就有了一个很好的速度/空间权衡。

你总是可以即时编译电路......

因为我还没有真正考虑过，所以我不确定我会采取什么方法......但它可能是一种混合方法，我肯定也会硬编码流行的“芯片”。

Answer 6

您可以向他们介绍卡诺图的概念，这将帮助他们为自己简化真值。

Answer 7

如果您可以禁止循环（输出链接回输入），那么您可以显着简化问题。在这种情况下，对于每一个输入，都会有一个明确的输出。然而，循环可以使输出无法确定（或者更确切地说，不断变化）。

评估没有环路的电路应该很容易——只需使用带有“结”（逻辑门之间的连接）的 BFS 算法作为列表中的项目。从处于“未定义”状态的所有门的所有输入开始。一旦门的所有输入“定义”（1 或 0），计算其输出并将其输出连接添加到 BFS 列表。这样，您只需评估每个门和每个结点一次。

如果存在环路，则可以使用相同的算法，但可以以永远不会“静止”的方式构建电路，并且某些连接点总是在 1 和 0 之间变化。

OOps，实际上，这种算法不能在这种情况下使用，因为循环门（以及取决于它们的门）将永远保持为“未定义”。

Answer 8

当我在制作“数字电路”仿真环境时，我将每个定义的电路（一个基本门、一个多路复用器、一个解复用器和几个其他原语）与一个传递函数（即一个计算所有输出，基于当前输入），“议程”结构（基本上是“何时激活特定传递函数的链接列表”），虚拟线和全局时钟。

我任意设置电线以在输出更改时硬修改输入，并更改任何电路上的输入以安排在门延迟后调用的传递函数。有了这个，我可以同时容纳时钟和非时钟电路元件（时钟元件设置为使其传递函数在“下一个时钟转换，加上门延迟”时运行，任何非时钟元件只取决于门延迟）。

从来没有真正开始为它构建一个 GUI，所以我从来没有发布过代码。