论文部分内容阅读
可逆逻辑的研究主要受到低功耗CMOS计算和量子计算的应用推动,不久的将来,电路逻辑上的不可逆操作将成为制约高性能集成电路发展的主因,量子可逆电路可能取代传统不可逆电路解决经典的计算问题。可逆逻辑综合作为量子可逆电路设计中的关键步骤,由于可逆综合问题的复杂度,寻找最优或近优的综合方法仍然是一个开放性问题。基于积之异或和(Exclusive-orSum-of-Products,ESOP)的可逆逻辑综合方法虽然能处理上百个变量以上的大型逻辑函数而受到重点关注,但生成的可逆电路存在较高的量子成本而有较大的优化空间,本文对基于ESOP的可逆逻辑综合与优化方法进行深入研究,取得的主要成果在于:
1.Reed-Muller逻辑的综合
逻辑函数的AND-EXOR式(又称Reed-Muller,RM逻辑)存在多种子类,RM逻辑的复杂程度直接影响可逆逻辑电路的量子成本,可逆逻辑的综合优化问题可在RM域来预先处理。针对ESOP的可扩展综合,将全局空间的最优覆盖搜索简化为多个子空间的最简映射,提出一种基于分层超立方体的ESOP最小化方法;针对规范RM式之间或规范RM式与ESOP之间的快速转换,引入面向立方体的通用改写操作(即转换规则),提出一种基于立方体的快速转换方法。
2.采用MPMCT门的可逆逻辑综合优化
采用混合极性通用Toffoli(Mixed-PolarityMultiple-ControlToffoli,MPMCT)门的可逆级联从功能上与一个ESOP自然对应,但现有综合优化过程存在前、后目标不统一,难以高效地输出更低量子成本的可逆电路。针对单输出函数,通过临时改变逻辑函数的功能获得具有一个更低量子成本的MPMCT网络,提出一种基于预插入CNOT门的综合优化技术;针对多输出函数,利用不同输出函数间存在的结构相似性以及不同立方体之间存在控制线集的相似性来构造MPMCT网络,提出一种基于共享策略的综合优化技术;参考传统多级逻辑综合,引入一种仿射型可逆级联结构,提出一种基于仿射分解的综合技术。
3.可逆逻辑电路的复杂度分析
可逆逻辑电路的复杂度作为一种评价可逆综合方法性能的整体度量,可逆门数的上界有利于理解可逆逻辑电路的复杂度以及量子成本。针对可逆电路级,根据单目标门(Single-Target,ST)的线性上界,采用两种分解方法(函数分解与ESOP乘积项级联)将ST门映射为Toffoli门的级联,由此,给出采用MPMCT门实现的更紧上界;针对映射级,基于Barenco、Nielsen和Miller三种映射技术,由此,给出MPMCT门、ST门和一般可逆电路实现的NCT(NOT-Feynman-Toffoli)复杂度。
4.可逆逻辑电路的功能实现
利用可逆门进行经典功能电路的设计是可逆逻辑电路设计的研究热点之一。针对加法器(所有数字系统中必不可少的算术部件)的可逆电路设计,为了提高计算效率,提出基于标记的BCD加法器结构;为了改善级联深度,提出基于码转换的BCD加法器结构;为了在单个可逆电路中实现BCD加法/减法功能,构造一个通用的n位可逆BCD加/减法器结构;提出的四种可逆逻辑电路设计比现有设计具有更好的性能,即量子成本、辅助线输入、可逆门数和逻辑深度。
本文研究成果在一定程度上提高可逆逻辑综合的效率、降低可逆逻辑电路的量子成本,为可逆逻辑电路的具体功能电路设计以及传统集成电路的可逆改造提供技术基础。
1.Reed-Muller逻辑的综合
逻辑函数的AND-EXOR式(又称Reed-Muller,RM逻辑)存在多种子类,RM逻辑的复杂程度直接影响可逆逻辑电路的量子成本,可逆逻辑的综合优化问题可在RM域来预先处理。针对ESOP的可扩展综合,将全局空间的最优覆盖搜索简化为多个子空间的最简映射,提出一种基于分层超立方体的ESOP最小化方法;针对规范RM式之间或规范RM式与ESOP之间的快速转换,引入面向立方体的通用改写操作(即转换规则),提出一种基于立方体的快速转换方法。
2.采用MPMCT门的可逆逻辑综合优化
采用混合极性通用Toffoli(Mixed-PolarityMultiple-ControlToffoli,MPMCT)门的可逆级联从功能上与一个ESOP自然对应,但现有综合优化过程存在前、后目标不统一,难以高效地输出更低量子成本的可逆电路。针对单输出函数,通过临时改变逻辑函数的功能获得具有一个更低量子成本的MPMCT网络,提出一种基于预插入CNOT门的综合优化技术;针对多输出函数,利用不同输出函数间存在的结构相似性以及不同立方体之间存在控制线集的相似性来构造MPMCT网络,提出一种基于共享策略的综合优化技术;参考传统多级逻辑综合,引入一种仿射型可逆级联结构,提出一种基于仿射分解的综合技术。
3.可逆逻辑电路的复杂度分析
可逆逻辑电路的复杂度作为一种评价可逆综合方法性能的整体度量,可逆门数的上界有利于理解可逆逻辑电路的复杂度以及量子成本。针对可逆电路级,根据单目标门(Single-Target,ST)的线性上界,采用两种分解方法(函数分解与ESOP乘积项级联)将ST门映射为Toffoli门的级联,由此,给出采用MPMCT门实现的更紧上界;针对映射级,基于Barenco、Nielsen和Miller三种映射技术,由此,给出MPMCT门、ST门和一般可逆电路实现的NCT(NOT-Feynman-Toffoli)复杂度。
4.可逆逻辑电路的功能实现
利用可逆门进行经典功能电路的设计是可逆逻辑电路设计的研究热点之一。针对加法器(所有数字系统中必不可少的算术部件)的可逆电路设计,为了提高计算效率,提出基于标记的BCD加法器结构;为了改善级联深度,提出基于码转换的BCD加法器结构;为了在单个可逆电路中实现BCD加法/减法功能,构造一个通用的n位可逆BCD加/减法器结构;提出的四种可逆逻辑电路设计比现有设计具有更好的性能,即量子成本、辅助线输入、可逆门数和逻辑深度。
本文研究成果在一定程度上提高可逆逻辑综合的效率、降低可逆逻辑电路的量子成本,为可逆逻辑电路的具体功能电路设计以及传统集成电路的可逆改造提供技术基础。