2021-2022学年第一学期
信息论与编码（sd04630110）
注意本课程是本科生课程，与研究生课程《信息论与编码》没有关系！
上课时间及地点：周一、三 3-4节，1-12周上课，青岛校区振声苑W302
成绩：
- 本课程会有课后作业，课后作业无需提交，教师会按时公布参考答案。
- 本课程会有两次小测验Q1和Q2，分别定在第5周周三1-2节和第9周周三1-2节，以及一次期末考试T。
- 小测验Q1和Q2的题目将会是课后作业的微小变型，认真完成作业并理解掌握参考答案的同学将会顺利拿到好成绩。
- 最终课业成绩的计算方法为：课程成绩 = max{15% * Q1 + 15% * Q2 + 70% * T, T}。
- 无故缺席任意一次小测验Q1或Q2，其相应测验成绩 = 0，课程成绩计算方式不变。
- 最终解释权归授课教师。
预备知识：微积分、概率论、离散数学
教学日历：
- 2021.09.06 第一讲：熵的定义、基本性质；联合熵与条件熵。课后作业：【CT_zh】习题 2.1，2.4，2.5。
- 2021.09.08 第二讲：熵的链式法则，相对熵与互信息，Jensen不等式。课后作业：【CT_zh】习题 2.6，2.7， 2.12。
- 2021.09.13 第三讲：Jensen不等式及其结果，数据处理不等式。课后作业：【CT_zh】习题 2.14，2.18，2.29。
- 2021.09.15 第四讲：Fano不等式，熵的组合意义，习题2.6讲解。课后作业：【CT_zh】习题 2.23，2.25，2.32。
- 2021.09.18 第五讲：Shearer引理，Markov不等式，Chebyshev不等式，弱大数定律，渐近均分性（AEP）。【CT_zh】习题 3.1，3.4，3.5。
- 2021.09.22 第六讲：习题2.14讲解，数据压缩，信源编码定义，Kraft不等式。【CT_zh】习题5.1。
- 2021.09.27 第七讲：最短描述期望，Huffman码，Shannon-Fano-Elias码。【CT_zh】习题5.12, 5.28。
- 2021.09.29 第八讲：熵的公理化定义。【CT_zh】习题2.27，2.28。进阶：习题2.46（不作要求）。
- 2021.10.04 第九讲：Shannon编码，Fano编码，Shannon-Fano-Elias编码，Huffman码最优性。【CT_zh】习题5.9，5.30.
- 2021.10.06 第十讲：信道容量，信道例子：BSC，BEC，联合典型序列。【CT_zh】习题7.2，7.4.
- 2021.10.11 第十一讲：信道编码定理可达性部分证明。【CT_zh】习题 7.18，7.21，7.26.
- 2021.10.13 第十二讲：信道编码定理的逆定理，Polar码，极化现象。【CT_zh】习题7.13，7.14.
- 2021.10.18 第十三讲：Polar码，极化现象，强极化现象。
- 2021.10.20 第十四讲：强极化，极化码编码复杂度，译码复杂度，汉明码。【CT_zh】习题7.20，7.23.
- 2021.10.25 第十五讲：Parity code, repetition code, Hamming distance, t-error-correction, t-error-detection。【GRS】Exercise 1.1, 1.5, 1.6.
- 2021.10.27 第十六讲：Hamming code, Hamming (sphere packing) bound, linear code。【GRS】Exercise 1.7, 1.8。
- 2021.11.01 第十七讲：Generator matrix, parity-check matrix, generalized Hamming codes, family of codes. 【GRS】Exercise 1.15, 1.17, 2.9.
- 2021.11.03 第十八讲：Asymptotic bounds: Hamming/Sphere-packing bounds, Gilbert-Varshamov bound, q-ary Entropy function. 【GRS】Exercise 2.13, 2.16.
- 2021.11.08 第十九讲：Magic code, probabilistic method. 【GRS】Exercise 2.18, 2.27, 2.31.
- 2021.11.10 第二十讲：Linear codes attaining GV bound, Singleton bound, Plotkin bound. 【GRS】Exercise 4.11, 4.12, 4.13.
- 2021.11.15 第二十一讲：Hadamard matrix, Plotkin bound, Geometric lemma, Polynomials over fields, Reed-Solomon codes, MDS codes. 【GRS】Exercise 5.2, 5.4.
- 2021.11.17 第二十二讲：Welch-Berlekamp algorithm, Boolean functions.
- 2021.11.22 第二十三讲：Exersise 2.18, Reed-Muller codes, (u,u+v) construction.
- 2021.11.24 第二十四讲：Exercise 2.18, majority logic decoing for RM codes.
教材：
- 【H2021】2021-2022第一学期讲义
- 【CT_zh】《信息论基础》，Thomas M.Cover，Joy A.Thomas著；阮吉寿，张华译
- 【CT_en】Elements of Information Theory 2nd Edition by Thomas M. Cover, Joy A. Thomas
- 【GRS】《Essential Coding Theory》，V.Guruswami, A.Rudra, M.Sudan.
- 【H2020】2020-2021第一学期讲义
参考资料及链接：
- Madhu Sudan, Information Theory in Computer Science (Harvard CS 229r, Spring 2019)
- 经典文献：C. E. Shannon, A mathematical theory of communication
- Y. Polyanskiy, Y. Wu, Lecture notes on Information Theory, MIT (6.441), UIUC (ECE 563), Yale (STAT 664), 2012-2017.
- Edward Witten, A Mini-Introduction To Information Theory
- 纪录片：Claude Shannon - Father of the Information Age
- 纪录片：The Bit Player - Who is Claude Shannon
- 网站：Information Theory Society
- 网站：Simons Institute for the Theory of Computing
进阶阅读及后续课程：
- Simons-Berkeley Program on Information Theory
- Network Information Theory by Abbas El Gamal, Young-Han Kim
- Modern Coding Theory by Tom Richardson, Rüdiger Urbanke
信息论部分（【CT_zh】）：
-
绪论与概览
-
熵、相对熵与互信息
-
渐近均分性
-
数据压缩
-
信道容量
-
微分熵
-
高斯信道
编码部分（【GRS】）:
-
The Fundamental Question
-
Linear Codes
-
Probability
-
Bounds
-
Reed-Solomon Codes
-
Shannon’s Theorem
-
List decoding