一种基于量化布尔公式的逻辑网络乘法复杂度优化方法
本公开涉及电子设计自动化逻辑综合领域，具体涉及一种基于量化布尔公式的逻辑网络乘法复杂度优化方法。
背景技术：
1、在加密和安全应用中函数通常用 (xor-and-graph xag)表示，电路的性能和质量与and门数量呈负相关，and门数量被称为乘积复杂度。在加密安全应用中减少乘法复杂度极其重要，而工艺无关的逻辑优化是逻辑综合中重要的一步。现有的逻辑优化方法包括重写( rewrite)、重替换( resubstitution)、重构( refactor)以及精确综合( exact synthesis)。其中精确综合 ( exact synthesis)是逻辑优化技术中新型的布尔优化方法，它通过对于给定的函数，找到一个节点数最少的逻辑网络，利用切割的原理，从电路中分割小的子电路进行优化。
2、精确综合作为逻辑综合优化网络乘法复杂度的一种新的步骤，求解质量是考量的重要因素。传统的优化方案将网络中的单输出节点进行计算，这降低了网络的乘法复杂度，但由于忽略了网络中的多输出节点，损失了一部分的优化机会，因此得到的结果还有更大的优化空间。同时，传统的优化方案往往只进行局部等价的替换，放弃了因电路的无关项存在导致的局部不等价全局等价的情况，这同样损失了一部分的优化机会。
技术实现思路
1、针对现有技术的不足，本发明提供一种基于量化布尔公式的逻辑网络乘法复杂度优化方法，该优化方法采用精确综合结合窥孔优化的方式，将精确综合中仅仅局限于单输出电路的匹配拓展到多输出，可以降低逻辑网络的乘法复杂度，同时该优化方法有效利用电路中存在的无关项进行优化，允许优化后的子电路与优化前的子电路不等价，只需保证全局电路等价即可。
2、本发明优化方法通过收集待优化节点作为根门，以根门构建子电路以及局部电路，将精确综合中仅仅局限于单输出电路的匹配拓展到多输出，可以降低逻辑网络的乘法复杂度，同时，本发明优化方法有效利用电路中存在的无关项进行优化，量化布尔公式的电路编码方式提供了这些选择的可行性，提高了优化搜索空间。本发明优化方法不仅可以适用于密码学和安全应用的安全性提升，而且适用于逻辑综合中富含异或的网络优化。同时，本发明优化方法可对于一个乘法复杂度已经优化良好的网络，进行进一步的优化，得到更好的求解结果。本发明为逻辑综合乘法复杂度优化提供了一种新的思路，丰富了密码安全学领域乘法复杂度优化的自动设计优化方法，对于逻辑综合的乘法复杂度优化技术有着较强的现实意义和实践意义。
3、本发明解决上述技术问题所采用的技术方案为：一种基于量化布尔公式的逻辑网络乘法复杂度优化方法，包括以下步骤：
4、1）基于加密或安全应用中的函数构建待优化的逻辑网络，解析所述的逻辑网络的拓扑结构，按照重收敛路径查找所述的逻辑网络中的待优化的节点，收集以待优化的节点为根门的子电路 m 1，计算子电路 m 1中and节点数量，在子电路 m 1中and节点数量等于零的情况下，判定子电路 m 1中and节点不是可优化节点，重新查找所述的逻辑网络中的待优化的节点；在子电路 m 1中and节点数量大于零的情况下，记录子电路 m 1中and节点数量 n 1，并以子电路 m 1作为旧的子电路，即将子电路 m 1作为所述的逻辑网络中的待优化区域，进入步骤2）；
5、2）在所述的逻辑网络中收集所述的旧的子电路外的一个局部电路；
6、3）对所述的旧的子电路和所述的局部电路通过量化布尔公式写出约束文件；再对所述的约束文件调用量化布尔公式求解器进行求解，在一定的时间内获取到一个满足约束的解，并将得到的解解析成新的子电路，计算所述的新的子电路中and节点数目 n 2；
7、4）对比所述的新的子电路中and节点数目 n 2和所述的旧的子电路中and节点数目 n 1，保留两者中and节点数目更小的子电路，并将保留的子电路插入回所述的逻辑网络中，得到优化后的逻辑网络，清除优化后的逻辑网络中的悬空节点，得到新的逻辑网络；
8、5）迭代循环上述步骤1）~5）。
9、作为优选，步骤2）的具体过程为：
10、2.1）收集所述的旧的子电路的后续输出节点，收集的上限为层级 k 1，生成部分局部电路集合 n part；
11、2.2）收集所述的部分局部电路集合 n part的输入节点，收集的上限为集合的输入数目不超过 k 2，生成局部电路 n all。
12、作为优选，步骤3）的具体过程为：对所述的旧的子电路和所述的局部电路进行量化布尔公式的编码约束写出约束文件，所述的编码约束包括真值表约束、拓扑连接关系约束和等价性约束；再对所述的约束文件调用开源量化布尔公式求解器qfun进行求解，在一定的时间内获取到一个满足约束的解，并将得到的解解析成新的子电路 m2，计算所述的新的子电路 m2中and节点数目 n 2。
13、与现有技术相比，本发明具有如下优点：本发明优化方法采用精确综合结合窥孔优化的方式，通过收集待优化节点作为根门，以根门构建子电路以及局部电路，将精确综合中仅仅局限于单输出电路的匹配拓展到多输出，可以降低逻辑网络的乘法复杂度，同时，本发明优化方法有效利用电路中存在的无关项进行优化，量化布尔公式的电路编码方式提供了这些选择的可行性，提高了优化搜索空间。本发明优化方法不仅可以适用于密码学和安全应用的安全性提升，而且适用于逻辑综合中富含异或的网络优化。此外，本发明优化方法可对于乘法复杂度已经优化良好的网络，进行进一步的优化，得到更好的求解结果。本发明为逻辑综合乘法复杂度优化提供了一种新的思路，丰富了密码安全学领域乘法复杂度优化的自动设计优化方法，对于逻辑综合的乘法复杂度优化技术有着较强的现实意义和实践意义。
技术特征：
1.一种基于量化布尔公式的逻辑网络乘法复杂度优化方法，其特征在于，包括以下步骤：
2.如权利要求1所述的一种基于量化布尔公式的逻辑网络乘法复杂度优化方法，其特征在于，步骤2）的具体过程为：
3.如权利要求1所述的一种基于量化布尔公式的逻辑网络乘法复杂度优化方法，其特征在于，步骤3）的具体过程为：对所述的旧的子电路和所述的局部电路进行量化布尔公式的编码约束写出约束文件，所述的编码约束包括真值表约束、拓扑连接关系约束和等价性约束；再对所述的约束文件调用开源量化布尔公式求解器qfun进行求解，在一定的时间内获取到一个满足约束的解，并将得到的解解析成新的子电路m2，计算所述的新的子电路m2中and节点数目n2。
技术总结
本发明公开了一种基于量化布尔公式的逻辑网络乘法复杂度优化方法，包括以下步骤：获取待优化的逻辑网络中的待优化区域；构建子电路并计算其AND节点数目n<subgt;1</subgt;；收集局部电路；对子电路和局部电路通过量化布尔公式写出约束文件；对约束文件调用量化布尔公式求解器进行求解，将得到的解解析成新的子电路并计算其AND节点数目n<subgt;2</subgt;；对比n<subgt;2</subgt;和n<subgt;1</subgt;，保留AND节点数目更小的子电路，插入回逻辑网络中，得到优化后的逻辑网络并清除其悬空节点，得到新的逻辑网络；迭代循环上述步骤。本发明方法可以降低逻辑网络的乘法复杂度，有效利用电路中存在的无关项进行优化，不仅可以适用于密码学和安全应用的安全性提升，而且适用于逻辑综合中富含异或的网络优化。
技术研发人员：储著飞,祝军,夏银水,王伦耀
受保护的技术使用者：宁波大学
技术研发日：
技术公布日：2024/12/5