第一部分 信息、算法与编码在数理逻辑中 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