第1章 绪论 1
1.1引言 1
1.2可逆计算 2
1.3可逆计算中的逻辑综合 4
1.3.1可逆逻辑综合的概念 4
1.3.2可逆逻辑综合的意义 4
1.4可逆逻辑综合中的主要问题 5
1.4.1可逆逻辑门的级联 5
1.4.2最小代价问题及其实现 6
1.4.3无用输出信息位 7
1.4.4可逆逻辑综合的规模 7
1.4.5可逆逻辑综合方法 7
1.5本书的主要任务和内容 10
第2章 可逆逻辑与可逆逻辑门 12
2.1关于可逆 12
2.2可逆逻辑中的布尔代数 13
2.3可逆逻辑函数 15
2.3.1问题的提出 15
2.3.2可逆逻辑函数实现 20
2.4可逆逻辑门 21
2.4.1一位可逆逻辑门 22
2.4.2 Feynman门 22
2.4.3简单交换门 24
2.4.4双控制门 25
2.4.5控制交换门 26
2.4.6多位控制反门 27
2.5可逆逻辑门的表示 28
2.6可逆逻辑门的通用性 28
第3章 可逆逻辑门网络 30
3.1可逆逻辑网络结构 30
3.2可逆网络的级联 32
3.3可逆网络的表示 39
3.4可逆逻辑门网络基本元素的产生 40
3.5可逆逻辑门的级联 40
3.6可逆网络门的计数 42
3.6.1 Toffoli门计数 42
3.6.2 Toffoli门网络级联 44
3.6.3实验及结果分析 45
第4章 可逆网络的构造 46
4.1可逆网络结构的表示 46
4.1.1平行线与垂直线编号 46
4.1.2可逆网络的一种结构编码 47
4.1.3一种组合可逆网络的构造 48
4.2一种可逆网络输出向量的序号表示 49
4.2.1序号的定义 49
4.2.2逆序序列与输出向量的一一对应关系 49
4.2.3输出向量序号表示 50
4.3一种可逆网络构造算法 51
4.3.1算法 51
4.3.2实例 52
4.3.3实验结果及分析 54
第5章Toffoli门可逆网络综合 61
5.1基本算法 61
5.1.1基本算法的算法实现 61
5.1.2实例 62
5.2双向算法 63
5.2.1双向算法的算法实现 63
5.2.2实例 63
5.3控制位的优化 64
5.3.1双向最小宽度算法的算法实现 64
5.3.2实例 65
5.4三种方法结果比较 66
5.4.1三种算法之间的比较 66
5.4.2三种算法与Benchmark对比 68
第6章 典型可逆门簇网络组合级联 70
6.1典型可逆门簇网络模型 70
6.2对网络的输入／输出位及垂直线编号 70
6.3典型可逆门簇基本元素库的构造 72
6.4实验结果及分析 74
第7章 正反控制门簇可逆网络级联 76
7.1正／反控制门 76
7.2正／反控制门的可逆逻辑综合 77
7.2.1正反控制门可逆网络级联算法 77
7.2.2正／反控制门级联网络的化简 78
7.2.3实验结果及分析 80
7.3正／反控制门簇的可逆网络级联 85
7.3.1正／反控制门簇的可逆网络级联算法 86
7.3.2实验结果与分析 89
第8章 可逆函数复杂性网络综合 94
8.1基本定义 94
8.2正反控制门的可逆综合 96
8.2.1 PNC门的生成与级联 96
8.2.2实例验证 97
8.2.3化简 101
8.3结果分析 101
第9章 不可逆逻辑函数的可逆构造 104
9.1基本定义 104
9.2可逆逻辑网络的MCMT门描述 106
9.2.1可逆逻辑网络 106
9.2.2 AND/OR运算到AND/OR运算的转换 107
9.3多输出逻辑函数的转换 110
9.3.1积项的表示与运算 110
9.3.2多输出积项的运算 112
9.3.3算法 113
9.3.4结果的正确性验证 115
9.4验证结果分析 117
第10章 置换群与可逆网络级联 119
10.1可逆门与群 119
10.2可逆逻辑门网络与置换 122
10.3真值表的变换 131
10.4综合及优化 132
10.4.1规则优化 132
10.4.2综合 133
10.4.3对换级别的优化 134
10.4.4门级别的优化 135
10.4.5举例 135
10.4.6讨论 137
10.5基于置换群的可逆逻辑网络构造 137
10.5.1置换群与可逆网络 137
10.5.2可逆门的生成 141
10.5.3可逆网络的构造 146
10.5.4实例验证 152
第11章 可逆逻辑网络的优化 154
11.1基本定义 154
11.2模板分类 156
11.3模板的应用 158
11.4实验结果 161
11.5模板的重构 162
11.5.1重构 162
11.5.2优化 162
11.5.3实验结果 165
11.6 Toffoli-Fredkin网络优化 166
11.6.1 Box门 166
11.6.2 Fredkin门与Toffoli门相似性的解释 167
11.6.3算法 168
11.6.4模板化简工具 173
11.6.5讨论 176
第12章 基于PPRM的可逆逻辑综合 178
12.1关于PPRM 178
12.2 PPRM展开式的构造 180
12.2.1 PPRM展开式的构造方法 180
12.2.2 PPRM展开式的展开过程 181
12.3基于PPRM构造可逆逻辑网络 183
12.3.1生成PPRM扩展式 183
12.3.2综合算法 184
12.3.3 PPRM化简 186
12.3.4数据结构 187
12.3.5实例 187
12.3.6实验结果与分析 189
12.3.7算法分析与改进 191
12.4几种基于PPRM的可逆逻辑网络综合 192
12.4.1基于PPRM的可逆逻辑网络综合的快速算法WHH（f） 192
12.4.2深度搜索解空间树的算法DFS（ihigh, irow） 193
12.4.3 BBF算法 194
12.4.4实验结果与分析 195
12.4.5深度优先搜索最优可逆网络的算法DFC（irow） 195
12.4.6调用算法DFC生成可逆逻辑网络的算法DFM（f） 196
12.5小结 198
参考文献 199