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
步骤②、将蕴含逻辑中的约束问题转换成合取范式公式,即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。