可逆逻辑函数分类及等价性判定

发布时间：2023-05-28 12:14

　　可逆逻辑综合在量子计算和解决计算机热耗问题中起着关键性的作用，而可逆逻辑综合的规模一直是研究者们关心的重要内容，ω阶的可逆逻辑函数共有2^ω!个，随着阶数的增长，可逆逻辑函数的数目激增，要完全综合这么多的可逆逻辑函数，难度可想而知。由于可逆逻辑函数的分类在可逆逻辑综合中可以使模板重复使用，从而提高综合的效率，所以可逆逻辑函数分类成为解决规模问题的重要方法。 本文正是针对这一主题，把可逆逻辑函数的NP-NP等价作为研究对象，对可逆逻辑函数分类及等价性判定做了探讨。其主要内容为： 1.提出可逆逻辑函数NP-NP等价的定义，该定义是把布尔函数NP-N等价的定义推广到可逆逻辑函数得到的。通过把可逆逻辑函数表示成置换群中的置换，把可逆逻辑函数NP-NP等价分类转化为置换群的双陪集等价分类。 2.研究可逆逻辑非门和交换门对应置换构成的子群的性质，结合可逆逻辑函数NP-NP等价类的特性，对群论中计算双陪集个数的公式进行了改进，完成了可逆逻辑函数NP-NP等价类个数的计算。如果用穷举的方法，在普通计算机上最多只能计算出3阶可逆逻辑函数NP-NP等价类个数，而用该方法在相同的计算机上...

【文章页数】：54 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第一章 绪论
    1.1 课题研究的背景
    1.2 可逆逻辑函数分类的意义
    1.3 可逆逻辑综合及可逆逻辑函数分类的研究现状
    1.4 论文的结构安排
第二章 基础知识和相关理论
    2.1 布尔函数与可逆逻辑函数
        2.1.1 布尔函数及其主要表达式
        2.1.2 可逆逻辑函数与可逆逻辑门
    2.2 等价关系与集合的分类
    2.3 群论基础知识
        2.3.1 群与子群
        2.3.2 置换群
        2.3.3 共轭与陪集
        2.3.4 群的作用
    2.4 本章小结
第三章 可逆逻辑函数 NP-NP 等价类个数的计算
    3.1 可逆逻辑函数的置换表示
    3.2 理论基础
        3.2.1 逻辑非门与交换门的性质
        3.2.2 可逆逻辑函数 NP-NP 等价
    3.3 算法
    3.4 算法实验及其结果
    3.5 本章小结
第四章 可逆逻辑函数 NP-NP 等价判定
    4.1 三阶可逆逻辑函数的 NP-NP 等价判定
        4.1.1 改进的 J.E.Savage 算法
        4.1.2 布尔函数固定极 RM 展开式极性的确定
        4.1.3 辅因子的码值向量
        4.1.4 三阶可逆逻辑函数 NP-NP 等价判定
    4.2 可逆逻辑函数 NP-NP 等价判定的代数方法
    4.3 本章小结
第五章 总结与展望
    5.1 论文总结
    5.2 工作展望
致谢
参考文献
硕期间取得的研究成果



本文编号：3824570