可逆逻辑综合PDF电子书下载

第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