信息、算法与编码PDF电子书下载

第一部分 信息、算法与编码在数理逻辑中 3

0.1 数理逻辑简介 3

第一章 可计算性函数 8

1.1 算法和能行过程的直观含义（非数学定义） 8

1.2 计算机模型——无界存储机URM 9

1.3 URM-可计算性函数 11

1.4 可判定谓词及可判定问题 13

第二章 生成可计算性函数 15

2.1 生成可计算性函数 15

2.2 原始递归函数 20

第三章 丘奇论题 25

3.1 图灵机 25

3.2 丘奇论题定义及应用 27

第四章 哥德尔编码 32

4.1 URM程序的编码 32

4.2 可计算函数的编码 33

4.3 s-m-n定理 33

4.4 “好”的编码（一） 35

4.5 范式定理 38

第五章 一些重要结果 40

5.1 通用函数及通用计算机 40

5.2 哥德尔不完全性定理（简单化） 40

5.3 P与NP问题 41

5.4 “好”的编码（二） 45

5.5 加速定理（the speed-up theorem，Blum） 46

第六章 可判定问题、递归、规约及度 48

6.1 可判定，不可判定 48

6.2 部分可判定 50

6.3 递归及递归可枚举集 51

6.4 多一规约 53

6.5 图灵（Turing）规约 55

6.6 小结：复杂事物的编码 56

第二部分 信息、算法与编码在可计算分析中 59

第七章 可计算分析的背景、TTE的轮廓 59

7.1 研究背景 59

7.2 TTE体系的轮廓 60

第八章 康托（Cantor）空间上的可计算性 63

8.1 T2-机器及可计算性 63

8.2 可计算串函数是连续的 67

8.3 连续串函数集的标准表示 69

第九章 “好”的命名系统 72

第十章 R上的可计算性 78

第三部分 算法信息 89

第十一章 实数函数的计算复杂性 89

11.1 柯氏（Kolmogorov）复杂性 93

11.2 前缀复杂性 94

11.3 柯氏复杂性与香农熵 96

11.4 算法熵是不可计算的 98

第四部分 信息论 103

第十二章 信息论发展简史和现状 103

第十三章 信息论的基本概念 106

13.1 导论 106

13.2 离散熵的定义 108

13.3 熵的特性 110

13.4 联合熵、条件熵 113

13.5 离散互信息 114

13.6 多个随机变量下的互信息 116

13.7 互信息的性质 119

13.8 熵函数形式的唯一性 120

13.9 连续随机变量下的熵与互信息 123

13.10 鉴别信息 123

第十四章 信源的熵率、冗余度压缩 128

14.1 信源模型与信源编码 128

14.2 离散稳恒信源的熵率、冗余度 129

14.3 渐进等同分割性与定长编码 131

14.4 离散无记忆信源的变长编码 134

14.5 变长编码的最优编码 137

14.6 其他变长编码 140

14.7 离散的马尔可夫信源的熵率 149

第十五章 信道容量及其有效利用 155

15.1 信道模型与分类 155

15.2 离散无记忆信道及信道容量 155

15.3 离散无记忆信道容量的计算 158

15.4 某些简单情况下信道容量的解 160

15.5 可逆矩阵的信道容量 165

15.6 级联信道和并联信道的信道容量 167

15.7 输出字母概率分布唯一性 170

15.8 信道容量的迭代算法 170

第十六章 信道编码 175

16.1 信道编码概述 175

16.2 信道译码准则 176

16.3 联合典型序列和联合渐近等同分割定理 178

16.4 信道编码定理，即香农第二定理 179

第十七章 线性分组码 180

17.1 纠错码分类 180

17.2 线性分组码概述 180

17.3 生成矩阵、一致校验矩阵 180

17.4 线性码的距离、重量和检错、纠错能力 182

17.5 陪集、标准阵列和译码方法 184

17.6 小结：“好”的分组码 186

第十八章 循环码 189

18.1 循环码的定义及特性 189

18.2 循环码的生成矩阵和一致校验矩阵 193

第十九章 卷积码 196

19.1 多项式矩阵法 196

19.2 标量矩阵法 197

19.3 移位寄存器法 198

19.4 状态、格图和Viterbi译码法 200

第二十章 汉明码、BCH码 203

20.1 汉明码和完备码 203

20.2 BCH码 204

第二十一章 有限域基本性质 208

21.1 循环群 208

21.2 环、理想、整环、同构等概念 209

21.3 域的扩张 213

21.4 代数扩域 215

21.5 多项式模与分裂域 218

21.6 有限域的结构 220

21.7 多项式及多项式域（附录） 230

第二十二章 量子信息科学简介 234

22.1 量子 234

22.2 量子比特 235

22.3 量子态叠加与量子态纠缠 235

22.4 量子隐形传态 237

22.5 量子通信 238

22.6 冯·诺依曼熵 239

22.7 最后的一点说明 241

参考文献 243