欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2020100527087
申请人: 宁波大学
专利类型:发明专利
专利状态:未下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

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。