论文部分内容阅读
和传统Boolean逻辑相比,Reed-Muller逻辑运用在运算电路、通信电路、奇偶校验电路等数字电路中时,具备更好的面积、速度、功耗和可验证性等性能。面积优化在Reed-Muller电路设计中扮演重要角色,现有的大多数面积优化方法主要是极性优化,通过搜索最佳极性来优化Reed-Muller逻辑表达式,这类方法属于Reed-Muller电路设计的二级网络优化方法,其优化能力十分有限。对此,本文以面积最小化为主要目标,实施Reed-Muller电路的多级逻辑网络优化,开展了以下几点研究工作:(1)二叉决策图的结点和路径优化。通过对电路二叉决策图结构的分析研究,发现图内普遍存在一种可重构的菱形结构,在规范该菱形结构定义的基础上,提出了借助菱形结构的二叉决策图优化方法。该方法通过搜索二叉决策图内的菱形结构,划分出待优化的结构部分,继而重构该部分的具体结构,完成二叉决策图的结点和路径优化。由于每种菱形结构适用多种优化策略,选择合适的策略可以完成电路面积和延时的同时优化。(2)基于二叉决策图的Reed-Muller多级逻辑优化。优化后的二叉决策图,其结点的控制变量转变为若干单变量的逻辑组合,据此提出了一种Reed-Muller多级逻辑优化方法:利用每个结点的扇出路径均互斥的特点,由根结点至终结点提取出互斥乘积项,然后应用互斥乘积项的极性转换方法得到0极性下的Reed-Muller逻辑函数,最后通过遗传算法进行极性优化,完成了基于二叉决策图的Reed-Muller多级逻辑优化算法。(3)基于kernels的多级逻辑面积优化。从kernels在Boolean逻辑函数中的应用着手,提出了FPRM逻辑函数的kernels、co-kernels等相关术语的定义,并给出了kernels、co-kernels具体的计算方法。由计算后的kernels集合与co-kernels集合构建矩阵,据此提出基于矩形覆盖的多输出FPRM逻辑函数的多级优化方法。该方法给出了Reed-Muller逻辑函数kernels、co-kernels计算过程,并在计算过程中引入的矩阵分块法和贪心策略,提升了本方法的处理速度和通用性。本文提出的方法或算法,均通过C/C++语言编程实现,并使用MCNC benchmarks进行了验证测试,实验结果表明:二叉决策图的优化效果明显,结点和路径的数目大量减少;实现了对二叉决策图映射电路的面积和延时的同步优化,提升了该映射电路的可靠性与有效性;提出的基于二叉决策图的Reed-Muller多级优化方法,其优化结果与并行列表法、不相交乘积项法结果相比,面积均减少了约一半;基于kernels的Reed-Muller多级逻辑优化结果电路的面积,比极性优化所得电路面积减少约65%,比应用onset表得到的多级MPRM电路面积减少约30%,且该方法复杂度对电路输入输出数目不敏感,仅与表达式乘积项数相关。