一种数字电路逻辑函数的最佳蕴含逻辑表示方法与流程

本发明涉及涉及一种蕴含逻辑表示方法，具体是一种数字电路逻辑函数的最佳蕴含逻辑表示方法。

背景技术：

1971年，蔡少棠教授在电路理论及对称性原理的基础上推测一种新型的基本电路元件,并将其称为“忆阻器”，即有记忆性的电阻。随后，hp(惠普公司)实验室在开发替代晶体管开关的分子级产品时开发出纳米忆阻器，并利用双忆阻器的开关特性实现了实质蕴含(materialimplication,imp，逻辑表达式逻辑操作。实质蕴含是两变量基本逻辑运算之一，也可与逻辑常量“0”一起构成逻辑运算的完备基，这意味着利用蕴含操作可以实现任意逻辑运算。若将其与忆阻器的记忆功能相结合，可以构成一种新计算范式，即在同一颗芯片中储存数据时执行计算任务，从而实现存储与计算的动态切换。

先前研究者们通过利用学术逻辑综合工具abc得到电路的蕴含逻辑表示，首先读入一个电路并存储为以“and,inv”为基本运算集的逻辑图形结构(and-invertergraphs,aig)，再通过映射得到仅以“imp”为基本运算集的逻辑图形结构。然而这种方法得到的结果并不是最佳，因为在aig中的反相器一对一映射时需要一个实质蕴含逻辑操作来实现，这种情况会造成冗余。

技术实现要素：

本发明所要解决的技术问题是，针对现有技术的不足，利用基于布尔可满足性(satisfiability,sat)的精确综合算法来求解数字电路逻辑函数的最佳蕴含逻辑表达式，得到一种数字电路逻辑函数的最佳蕴含逻辑表示方法，本发明方法能够有效降低以实质蕴含为基本运算集的逻辑图形结构中结点的数目，当被运用于忆阻器电路中时，可减少忆阻器的数目，降低忆阻器电路的设计成本，同时丰富逻辑综合中实质蕴含逻辑的研究方法。

本发明解决上述技术问题所采用的技术方案为：一种数字电路逻辑函数的最佳蕴含逻辑表示方法，包括以下步骤：

步骤①、定义布尔变量

定义三个布尔变量：xit、ghi和sijk，其中xit表示数字电路中第i个逻辑门xi在数字电路逻辑函数真值表第t行中的取值；如果逻辑门xi的输出为数字电路中第h个原始输出gh，则布尔变量ghi的值为true，否则为false；如果逻辑门xi的两个输入分别是xj和xk，并且逻辑门xi执行实质蕴含逻辑运算，则布尔变量sijk的值为true，否则为false；其中，j和k的取值范围为：1≤j<i,0≤k<i,j≠k；

步骤②、将蕴含逻辑中的约束问题转换成合取范式公式，即cnf公式

以仅含“imp”运算的逻辑图形结构作为逻辑函数表示，即以“imp”为基本运算集的逻辑图形结构中除了原始输入和原始输出外，每个逻辑门均执行实质蕴含逻辑操作，由此得到蕴含逻辑中的主要约束条件为：

式(1)中，符号“→”代表实质蕴含逻辑运算，符号表示严格等值；式(1)表示如果逻辑门xi的两个输入分别是xj和xk，且逻辑门xi执行实质蕴含逻辑运算，即xit＝xjt→xkt，则逻辑门xi的取值xit表示为

利用tseytin变换方法将数字电路中的逻辑门转换为cnf公式的描述形式，得到蕴含逻辑门的cnf公式：

(xit→(xjt→xkt))∧((xjt→xkt)→xit)(2)

式(2)中，符号“∧”代表合取(即逻辑与)，只有蕴含逻辑门真值表中的赋值组合才满足式(2)，结合式(2)和等式其中，布尔变量上方的横线表示逻辑否定，将式(1)扩展为：

将式(3)转换为cnf的形式，利用其中符号“∨”代表逻辑或，得到cnf形式的约束条件：

对于式(4)中含有的nor逻辑门定义一个布尔变量将式(4)改写为：

利用tseytin变换方法将式(4)中含有的nor逻辑门转换成cnf形式：

综上所述，针对实质蕴含逻辑的主要cnf约束条件公式有：

为确保数字电路中的原始输出gh必为逻辑门xi的输出，定义约束条件公式为：

vighi(8)

式(8)中“v”代表逻辑或；

为确保数字电路中的逻辑门xi必有两个输入xj和xk，定义约束条件公式为：

vj,ksijk(9)

式(9)中，j≠k,j≠0；

为将数字电路的原始输出值约束至指定的逻辑门，定义约束条件公式为：

式(10)中代表逻辑异或，(t1,…,tn)2代表数字电路逻辑函数真值表中行号t的二进制编码；

步骤③：在步骤②得到的约束条件的基础上，首先设定需要的实质蕴含逻辑门数为0，编码得到cnf约束文件；将得到的cnf约束文件传送给sat求解器；

步骤④：sat求解器对收到的cnf约束文件中的布尔变量进行赋值，寻找满足式(7)～(10)的值均为true的一组布尔变量赋值；

如果sat求解器找到这样一组布尔变量赋值，则返回的结果为sat，表示找到了最优解；否则，使需要的实质蕴含逻辑门数加1，重新编码和求解，直至sat求解器返回的结果为sat。

与现有技术相比，本发明具有如下优点：

1、本发明公开了一种数字电路逻辑函数的最佳蕴含逻辑表示方法，利用基于布尔可满足性(satisfiability,sat)的精确综合算法来求解数字电路逻辑函数的最佳蕴含逻辑表达式。本发明方法不通过其他逻辑结构变换等中间步骤，而是直接从数字电路逻辑函数中得到最佳的实质蕴含逻辑表达形式。本发明方法首先根据定义的布尔变量来描述蕴含逻辑中的约束条件，得到以合取范式(conjunctionnormalform,cnf)表示的约束文件，设置不同的实质蕴含逻辑操作数，编码得到cnf约束文件，再将cnf约束文件传送给sat求解器，直到sat求解器找到满足约束条件的布尔变量赋值并返回代表最优解的结果sat，从而确保找到数字电路逻辑函数的最佳蕴含逻辑表示形式。

2、本发明方法在整个求解过程中，确保数字电路逻辑函数功能一致的前提下，得到一个数字电路逻辑函数的最佳蕴含逻辑表示形式。本发明方法在所有的三输入数字电路逻辑函数(共个函数)中，优化了74个函数。本发明方法能够有效降低以实质蕴含为基本运算集的逻辑图形结构中结点的数目，当被运用于忆阻器电路中时，可减少忆阻器的数目，降低忆阻器电路的设计成本，同时丰富逻辑综合中实质蕴含逻辑的研究方法。

附图说明

图1为由双忆阻器组成的实质蕴含逻辑电路的结构；

图2为由双忆阻器组成的实质蕴含逻辑电路的逻辑函数真值表；

图3为针对示例的数字电路，现有通过aig一对一映射得到以“imp”为基本运算集的逻辑图形结构示意图；

图4为针对示例的数字电路，本发明方法得到的以“imp”为基本运算集的逻辑图形结构。

具体实施方式

以下结合附图实施例对本发明作进一步详细描述。

图1和图2所示分别为实质蕴含逻辑电路相应的逻辑电路结构和逻辑函数真值表。将一个常规电阻器和两个并联的忆阻器p、q串联，形成一个数字开关电路，该混合电路可以形成实质蕴含操作。忆阻器p、q的初始阻态为逻辑门的输入，忆阻器q同时作为逻辑门的输出，通过电压vset、vcond的共同作用，忆阻器q的阻态改变，作为逻辑门的输出，最后的结果被写入忆阻器q存储起来。

以一个布尔表达式为的简单数字电路为例，其数字电路逻辑函数真值表为(00001011)2。对于该数字电路，图3为现有通过aig一对一映射得到以“imp”为基本运算集的逻辑图形结构示意图，图3中，所有的结点是实质蕴含逻辑门(即imp结点)。图4为本发明方法针对该数字电路得到的以“imp”为基本运算集的逻辑图形结构。本发明方法的优势是在不改变数字电路函数逻辑功能的情况下，通过基于sat的精确综合算法得到数字电路逻辑函数的最佳蕴含逻辑表达式。

对于布尔表达式为的简单数字电路，采用本发明方法求解其数字电路逻辑函数的最佳蕴含逻辑表达式的实施过程包括以下步骤：

步骤①、定义布尔变量

定义三个布尔变量：xit、ghi和sijk，如图4所示，该数字电路的原始输入为x1(即变量a)、x2(即变量b)、x3(即变量c)，中间逻辑门为x4、x5、x6，原始输出为g1；

步骤②、将蕴含逻辑中的约束问题转换成合取范式公式，即cnf公式

得到针对实质蕴含逻辑的约束条件公式有：

其中4≤i≤6,1≤j<i,0≤k<i,h＝1,0≤t≤7；

步骤③：在步骤②得到的约束条件的基础上，首先设定需要的实质蕴含逻辑门数为0，编码得到cnf约束文件；将得到的cnf约束文件传送给sat求解器；

步骤④：sat求解器对收到的cnf约束文件中的布尔变量进行赋值，寻找满足式上述约束条件公式值均为true的一组布尔变量赋值；

如果sat求解器找到这样一组布尔变量赋值，则返回的结果为sat，表示找到了最优解；否则，使需要的实质蕴含逻辑门数加1，重新编码和求解，直至sat求解器返回的结果为sat。最后得到的结果见图4。

以上简单数字电路中，逻辑门x4、x5、x6均为实质蕴含逻辑门，其蕴含逻辑门真值表为：

t＝76543210

x4t＝10111011

x5t＝11110100

x6t＝00001011

在布尔变量ghi中，g16为1，其余的ghi为0；在布尔变量sijk中，s421、s543、s650为1，其余的sijk为0。

对于所有的三输入数字电路逻辑函数(共个函数)，分别采用本发明方法得到数字电路逻辑函数的最佳蕴含逻辑表达式，并与现有aig一对一映射方法进行比较，其比较结果见表1。表1中，nimg(f)表示利用本发明方法得到的数字电路逻辑函数f的以“imp”为基本运算集的逻辑图形结构中的结点个数，naig(f)表示利用先通过转化为aig再映射成以“imp”为基本运算集的逻辑图形结构的结点个数。表1中第二列表示在两种转化方式中得到的结点个数相同的函数个数，第三列表示本方明方法得到的imp结点数优于现有方法的函数个数，本发明方法使256个三输入数字电路逻辑函数中的74个函数得到了最佳的实质蕴含逻辑表达式。

在图3中naig((00001011)2)＝5；图4中nimg((00001011)2)＝3，结点数目减少了两个。因此，本发明方法能有效降低以“imp”为基本运算集的逻辑图形结构中结点的数目，得到数字电路逻辑函数的最佳蕴含逻辑表达式，当被运用于忆阻器电路中时，可为忆阻器电路的设计减少成本，同时丰富逻辑综合中实质蕴含逻辑的研究方法。

表1

技术特征：

1.一种数字电路逻辑函数的最佳蕴含逻辑表示方法，其特征在于，包括以下步骤：

步骤①、定义布尔变量

定义三个布尔变量：xit、ghi和sijk，其中xit表示数字电路中第i个逻辑门xi在数字电路逻辑函数真值表第t行中的取值；如果逻辑门xi的输出为数字电路中第h个原始输出gh，则布尔变量ghi的值为true，否则为false；如果逻辑门xi的两个输入分别是xj和xk，并且逻辑门xi执行实质蕴含逻辑运算，则布尔变量sijk的值为true，否则为false；其中，j和k的取值范围为：1≤j<i,0≤k<i,j≠k；

步骤②、将蕴含逻辑中的约束问题转换成合取范式公式，即cnf公式

以仅含“imp”运算的逻辑图形结构作为逻辑函数表示，即以“imp”为基本运算集的逻辑图形结构中除了原始输入和原始输出外，每个逻辑门均执行实质蕴含逻辑操作，由此得到蕴含逻辑中的主要约束条件为：

式(1)中，符号“→”代表实质蕴含逻辑运算，符号表示严格等值；式(1)表示如果逻辑门xi的两个输入分别是xj和xk，且逻辑门xi执行实质蕴含逻辑运算，即xit＝xjt→xkt，则逻辑门xi的取值xit表示为

利用tseytin变换方法将数字电路中的逻辑门转换为cnf公式的描述形式，得到蕴含逻辑门的cnf公式：

(xit→(xjt→xkt))∧((xjt→xkt)→xit)(2)

式(2)中，符号“∧”代表合取，只有蕴含逻辑门真值表中的赋值组合才满足式(2)，结合式(2)和等式其中，布尔变量上方的横线表示逻辑否定，将式(1)扩展为：

将式(3)转换为cnf的形式，利用其中符号“∨”代表逻辑或，得到cnf形式的约束条件：

对于式(4)中含有的nor逻辑门定义一个布尔变量将式(4)改写为：

利用tseytin变换方法将式(4)中含有的nor逻辑门转换成cnf形式：

综上所述，针对实质蕴含逻辑的主要cnf约束条件公式有：

为确保数字电路中的原始输出gh必为逻辑门xi的输出，定义约束条件公式为：

vighi(8)

式(8)中“v”代表逻辑或；

为确保数字电路中的逻辑门xi必有两个输入xj和xk，定义约束条件公式为：

vj,ksijk(9)

式(9)中，j≠k,j≠0；

为将数字电路的原始输出值约束至指定的逻辑门，定义约束条件公式为：

式(10)中代表逻辑异或，(t1,…,tn)2代表数字电路逻辑函数真值表中行号t的二进制编码；

步骤③：在步骤②得到的约束条件的基础上，首先设定需要的实质蕴含逻辑门数为0，编码得到cnf约束文件；将得到的cnf约束文件传送给sat求解器；

步骤④：sat求解器对收到的cnf约束文件中的布尔变量进行赋值，寻找满足式(7)～(10)的值均为true的一组布尔变量赋值；

如果sat求解器找到这样一组布尔变量赋值，则返回的结果为sat，表示找到了最优解；否则，使需要的实质蕴含逻辑门数加1，重新编码和求解，直至sat求解器返回的结果为sat。

技术总结
本发明公开的数字电路逻辑函数的最佳蕴含逻辑表示方法，首先根据定义的布尔变量来描述蕴含逻辑中的约束条件，得到以合取范式CNF表示的约束文件，设置不同的实质蕴含逻辑操作数，编码得到CNF约束文件，再将CNF约束文件传送给SAT求解器，直到SAT求解器找到满足约束条件的布尔变量赋值并返回代表最优解的结果SAT，从而确保找到数字电路逻辑函数的最佳蕴含逻辑表示形式。本发明方法在所有的三输入数字电路逻辑函数中，优化了74个函数。本发明方法能够有效降低以实质蕴含为基本运算集的逻辑图形结构中结点的数目，当被运用于忆阻器电路中时，可减少忆阻器的数目，降低忆阻器电路的设计成本，同时丰富逻辑综合中实质蕴含逻辑的研究方法。

技术研发人员：储著飞;陈林;夏银水;王伦耀
受保护的技术使用者：宁波大学
技术研发日：2020.01.17
技术公布日：2020.06.09