跳转至

standardize 库

Caution

还没更新，可能是过期内容，谨慎参考

经过前面的 syntax 库的帮助，我们的程序一定程度上看懂了逻辑表达式，现在我们要开始向实现目标功能前进。得到了语法分析树后，我们要讲它转化成配置 FPGA 芯片用到的逻辑门。对于 FPGA 芯片，当然是希望得到的表达式是规整的，而不是千奇百怪的，所以需要对原来的表达式进行变换到“标准形式”，我称之为“标准化（standardize）”。所谓标准形式：

  1. 表达式只有不多于两层结构
  2. 如果是两层的结构，第一层必须是逻辑与

层是指被同一种运算符连接的表达式。比如说，在表达式 (A & B) | (C & D) | E 中，A、B、C、D都属于第二层，（A & B）、(C & D) 和 E 都属于第一层。所以这是一个两层的表达式，但是第一层是逻辑或，所以不是“标准形式”。为了进一步说明，以下例子都是标准形式：

  • (A | B) & (C | D) & E
  • A | B | C
  • A & B & C
  • A

那么是否所有的逻辑表达式都能被标准化呢？我给出的答案是肯定的，下一节将证明这一点并给出标准化操作的方法。如果你不想看这可能不严谨的证明，可以跳过下一节。

标准化证明

首先，如果表达式的结构少于两层，它已经是标准形式了，无需处理。

其次，如果表达式的结构为两层，那么又有两种情形，一是第一层是逻辑与，那么表达式已经是标准形式了；二是第一层是逻辑或，第二层是逻辑与，下面证明可以使用“两层转换”的操作将它变成标准形式。

两层转换

两层的逻辑表达式的一般形式为 \((A_{11}\&A_{12}\&...\&A_{1n_1}) | (A_{21}\&A_{22}\&...\&A_{2n_2}) | ... | (A_{m1}\&A_{m2}\&...\&A_{mn_m})\)，该表达式第一层是逻辑或，且有 \(m\) 个子表达式，第二层是逻辑与，每 \(k\) 个子表达式中 \(n_k\) 个变量。利用分配率，不难得到 $$ (A_{11}\&A_{12}\&...\&A_{1n_1})\ |\ (A_{21}\&A_{22}\&...\&A_{2n_2})\ | \ ... \ |\ (A_{m1}\&A_{m2}\&...\&A_{mn_m}) \ = AND_{\ 1\le i_1 \le n1,\ 1\le i_2 \le n_2,\ ...\ ,1\le i_m\le n_m}(A_{1i_1}\ |\ A_{2i_2}\ |\ ... \ |\ A_{mi_m}) $$ 其中 \(AND\) 之于 \(\&\) 类比 \(\Sigma\) 之于 \(+\)，即多项的求和。同理，因为与和或运算的优先级是等价的，将上式中的 \(\&\) 和 \(|\) 替换，也是成立的。因此，我们可以将两层结构的逻辑表达式的两层运算顺序转换。在此基础上，下面证明可以将三层的逻辑表达式转换成两层。

三层转两层

对于三层的逻辑表达式，其运算顺序必然是 & | & 或者 | & |。因为这是三层结构，所以必然存在中间层，并且中间层一定有非单个变量的表达式，这些表达式都是两层的。又已知两层结构的运算顺序是可以交换的，所以对三层结构中，所有中间层的子表达式进行两层变换。变换后，三层表达式的顺序变成 & & | 或者 | | &，这样，前两层的运算是一样的，那么实际上就是同一层，所以现在已经是两层的表达式了，运算顺序为 & | 或者 | &。

对于多于三层的表达式，我们总可以找到其仅有三层的表达式，将所有最底层的三层的缩减为两层后，最终就能得到两层的表达式。

小结

所有大于两层的表达式都可以转换成两层的表达式，而两层的表达式又可以通过两层转换变为标准形式。而低于两层的表达式本身已经是标注形式。所以，任意层的表达式都可以转换成标准形式。

实现

为了实现标准化，我定义了两个类 StandardLogicNode 和 StandardLogicTree。

StandardLogicNode

定义和实现在 include/standardize/standard_logic_node.h 和 src/standardize/standard_logic_node.cpp 中。

节点在实际中代表一个子表达式，一个字表达式是由相同运算符连接的表达式或者变量。比如说， A & B & C 构成一个节点，该节点没有子节点但有3个叶节点A、B、C，节点运算符是 & 。而 (A & B) | C，同样构成一个节点，但是该节点有一个子节点 A & B，一个叶节点 C，节点运算符是 |；其子节点没有子节点但有2个叶节点 A 和 B，节点运算符是 &。

同时，节点也是树的基本元素。为了构成树，StandardLogicNode 包含指向父节点的指针 parent_ 和指向子节点的指针向量 branches_，并用std::bitset 来表示叶节点 leaves_。当然还有变量 op_type 表示节点运算符类型。

StandardLogicTree

定义和实现在 include/standardize/standard_logic_tree.h 和 src/standardize/standard_logic_tree.cpp 中。

实际上，一个根节点足以表示树，这里添加 StandardLogicTree 类是方便封装一些函数进去。另一方面，除了表示根节点的变量 tree_root_ 外，因为使用 std::bitset 来表示叶节点即变量（即使用一个序号来表示一个变量），我们需要变量 id_list_ 来给出变量和序号的映射关系。

StandardLogicTree 是在语法分析树的基础上构建的，所以构造函数需要读入表达式的根节点（SLRSyntaxParser::Root）来构建，同时需要辅助函数 ParseE 和 ParseT 来递归解析产生式。读入后将直接构建对应的树，不一定是标准形式，所以需要通过调用 Standardize 来标准化。

Standardize 的方法就是上节标准化证明的小结部分提到的，调用方法 ReduceLayers 减少层数，调用方法 ExchangeOrder 交换两层的运算。

标准化后的树可以调用方法 PrintTree 保留结构地输出，也可以调用方法 Root 获得树的根目录。

优化

现实总是比理想残酷，虽然理论上是对的，但是该方法在面对多层的逻辑表达式时往往需要大量的时间，对于5层及以上的表达式的运行时间无可计数，所以需要进行优化。

去除重复

在转换的过程中，特别是多次进行两层转换后，很容易产生重复的子节点。由于 A | A = A，A & A = A。对于一个节点来说，如果它的两个子节点是相同的，那么可以去掉其中一个。同样的，如果两个叶节点是相同的，也可以去掉一个。当然，因为已经使用了 bitset 来记录叶节点，所以叶节点的重复已经被去掉了。

去除冗余

因为 A | （A & B) = A，A & (A | B) = A，所以上述两个逻辑表达式，A&B 和 A|B 是冗余的。我们可以以此为依据去除冗余枝干。因此我在 StandardLogicNode 中添加了方法 AddBranchNecessary 来检查枝干是否冗余，以避免添加冗余的枝干，或者去除因为新添枝干而变得冗余的枝干。

避免产生重复和冗余

实践中发现，最容易产生重复和冗余的地方是多次调用ExchangeOrder，一般将四层变为两层时，因为至少交换了两次，会产生大量的重复和冗余。消除它们最好的方法是不产生它们。之前提到的方法是用遍历的方法来交换两层结构，只有到了后面才能发现重复和冗余，现在使用一种新的方法，在重复和冗余产生初期就去掉。该方法流程如下：

  1. 读入原节点的第一个子节点，因为是两层结构，该子节点必然只包含叶节点
  2. 将该子节点的所有叶节点移入到公共叶节点集合中
  3. 读入原节点的下一个子节点
  4. 检查公共叶节点集合中是否有叶节点不是该子节点的叶节点中，如果有，将该叶节点移出公共叶节点集合，并添加到新节点中作为叶节点
  5. 检查读入的子节点中是否有叶节点不在公共叶节点集合中，如果有，将该叶节点和新节点的每一个子节点分别组合成新子节点，并和新节点的叶节点也组合出新子节点
  6. 新建节点，命名为新节点，并将第5步产生的所有新子节点作为新节点的子节点
  7. 如果原节点中还有未读入的子节点，回到步骤3
  8. 将公共叶节点集合中的节点作为新节点的叶节点
  9. 读入原节点的叶节点，
  10. 将读入的叶节点添加到所有新子节点中
  11. 将读入的叶节点和新节点的叶节点组合成新子节点

下面举例说明转换两层表达式 (A & B & C) | (A & B & D) | (A & C & E) | (A & F) | B | G 的过程

读入节点 公共叶节点集合 新节点 说明
A & B & C A B C / 步骤1、2
A & B & D A B D 步骤3、4
A & B & D A B C | D 步骤5、6
A & C & E A (C | D) & B 步骤3、4
A & C & E A (C | D) & (B | C) & (B | E) 步骤5、6
A & F A (C | D | F) & (B | C | F) & (B | E | F) 步骤3、4、5、6
/ / (C | D | F) & (B | C | F) & (B | E | F) & A 步骤8
B G / (B | C | F | G) & (B | E | F | G) & (A | B | G) 步骤9、10、11

使用这种新方法可以在重复和冗余产生的初期就将它们去掉，缺点是我还没有从理论上证明这套方法可行的，但在实践中还没有发现错误。

小结

通过剪枝（去除重复和冗余枝叶），将一般复杂（5层）的逻辑表达式的标准化的时间压缩到10ms 量级。

总结

standardize 库能将一般形式的逻辑表达式标准化，即变为仅有两层的结构，且第一层为逻辑与，第二层为逻辑或。如此，可以直接迁移到 FPGA 中，任意的一个表达式只需要一个与门和若干个或门来表达。

如果想要查看逻辑表达式标准化后的形式，可以运行程序 standardize 查看

1
2
3
$ ./bin/standardize
((A|B|C)&(D|E|F)) | ((A|D|G)&H) | ((B|H|I)&(J|K|L))
(B | D | E | F | H | I) & (A | B | C | H | I) & (A | B | C | H | J | K | L) & (D | E | F | H | J | K | L) & (A | B | C | D | G | J | K | L) & (A | D | E | F | G | J | K | L)