消息理論
Information Theory
| 節 | 週五 |
|---|---|
2 09:00–09:50 | 消息理論 SC204 3 節連堂 |
3 10:10–11:00 | |
4 11:10–12:00 |
* 根據陽明交大上課時間表所列
The purpose of this course is to present a concise, yet mathematically rigorous, introduction to the main pillars of information theory. It thus naturally focuses on the foundational concepts and indispensable results of the subject for single-user systems, where a single data source or message needs to be reliably processed and communicated over a noiseless or noisy point-to-point channel. At the first part of this course, six meticulously core chapters with accompanying problems, emphasizing the key topics of information measures, lossless and lossy data compression, channel coding, and joint source-channel coding. Two appendices covering necessary and supplementary material in real analysis and in probability and stochastic processes are included. At the second part of the course, advanced topics concerning the information theoretic limits of discrete-time single-user stochastic systems with arbitrary statistical memory (i.e., systems that are not necessarily stationary, ergodic or information stable) will be covered.
A basic understanding of probability, real analysis and stochastic processes shall be of help for the study of this course. These subjects will be partially coverred in our letctures.
The students can obtain the latest version of the lecture notes from http://shannon.cm.nctu.edu.tw/it18.htm. The following is a list of recommended references: 1. A Student’s Guide to Coding and Information Theory, Stefan M. Moser and Po-Ning Chen, Cambridge University Press, January 2012. 2. Elements of Information Theory, Thomas M. Cover and Joy A. Thomas, 2nd edition, John Wiley & Sons, Inc., July 2006. 3. A First Course in Information Theory (Information Technology: Transmission, Processing, and Storage), Raymond W. Yeung, Plenum Pub Corp., May 2002. 4. Principles and Practices of Information Theory, Richard E. Blahut, Addison Wesley, 1988. 5. Information Theory and Reliable Communication, Robert G. Gallager, 1985. 6. Information Theory, Robert B. Ash, Dover Publications, Inc., 1965. 7. Mathematical Foundations of Information Theory, A. I. Khinchin, Dover Publications, Inc., 1957.
The semester grade will be contributed equally by the midterm exam and the final exam. 1. The first lecture will be given on February 22. 2. There will be no lecture on March 1, April 5 and June 7 because these are holidays. – Since we have lost three 3-hour lectures due to holidays, we shall shorten our second 20-minute break by 10 minutes in order to compensate for the lost of coverage. 3. Midterm will be held on April 26. The coverage of midterm will be decided later (possibly, up to Section 4-3). 4. The last lecture will be given on June 14, 2019. 5. Final exam will be held on June 21, 2019.
| 週次 | 主題 |
|---|---|
| 第 1 週 | A coherent introduction of the primary principles of single-user information theory |
| 第 3 週 | Overview in the subjects of suprema, limits, probability and random processes (e.g., random variables, statistical properties of random processes, Markov chains, convergence of sequences of random variables, ergodicity and laws of large numbers, central limit theorem, concavity and convexity, Jensen’s inequality, Lagrange multipliers, and the Karush–Kuhn–Tucker (KKT) conditions for constrained optimization problems) |
| 第 4 週 | Information measures for discrete systems and their properties (self-information, entropy, mutual information and divergence, data processing theorem, Fano’s inequality, Pinsker’s inequality, simple hypothesis testing, Neyman–Pearson lemma, Chernoff–Stein lemma, and Rényi’s information measures) |
| 第 5 週 | Fundamentals of lossless source coding (i.e., data compression): discrete memoryless sources, fixed-length (block) codes for asymptotically lossless compression, AEP, fixed-length source coding theorems for memoryless and stationary ergodic sources, entropy rate and redundancy, variable-length codes for lossless compression, variable-length source coding theorems for memoryless and stationary sources, prefix codes, Kraft inequality, Huffman codes, Shannon–Fano–Elias codes, and Lempel–Ziv codes |
| 第 6 週 | Fundamentals of lossless source coding (i.e., data compression): discrete memoryless sources, fixed-length (block) codes for asymptotically lossless compression, AEP, fixed-length source coding theorems for memoryless and stationary ergodic sources, entropy rate and redundancy, variable-length codes for lossless compression, variable-length source coding theorems for memoryless and stationary sources, prefix codes, Kraft inequality, Huffman codes, Shannon–Fano–Elias codes, and Lempel–Ziv codes |
| 第 8 週 | Fundamentals of channel coding: discrete memoryless channels, block codes for data transmission, channel capacity, coding theorem for discrete memoryless channels, calculation of channel capacity, channels with symmetric structures, lossless joint source–channel coding, and Shannon’s separation principle |
| 第 9 週 | Fundamentals of channel coding: discrete memoryless channels, block codes for data transmission, channel capacity, coding theorem for discrete memoryless channels, calculation of channel capacity, channels with symmetric structures, lossless joint source–channel coding, and Shannon’s separation principle |
| 第 11 週 | Information measures for continuous alphabet systems and Gaussian channels: differential entropy, mutual information and divergence, AEP for continuous memoryless sources, capacity and channel coding theorem of discrete-time memoryless Gaussian channels, capacity of uncorrelated parallel Gaussian channels and the water-filling principle, capacity of correlated Gaussian channels, non-Gaussian discrete-time memoryless channels, and capacity of band-limited (continuous-time) white Gaussian channels |
| 第 12 週 | Fundamentals of lossy source coding and joint source–channel coding: distortion measures, rate–distortion theorem for memoryless sources, rate–distortion theorem for stationary ergodic sources, rate–distortion function and its properties, rate–distortion function for memoryless Gaussian sources, lossy joint source–channel coding theorem, and Shannon limit of communication systems |
| 第 13 週 | Fundamentals of lossy source coding and joint source–channel coding: distortion measures, rate–distortion theorem for memoryless sources, rate–distortion theorem for stationary ergodic sources, rate–distortion function and its properties, rate–distortion function for memoryless Gaussian sources, lossy joint source–channel coding theorem, and Shannon limit of communication systems |
| 第 14 週 | General information measure: Information spectrum and Quantile and their properties |
| 第 15 週 | Advanced topics of losslesss data compression: Fixed-length lossless data compression theorem for arbitrary channels, variable-length lossless data compression theorem for arbitrary channels |
| 第 17 週 | 1. Measure of randomness and resolvability: Resolvability and source coding, approximation of output statistics for arbitrary channels 2. Advanced topics of channel coding: Channel capacity for arbitrary single- user channel, strong capacity, epsilon-capacity |
Fady Alajaji and Po-Ning Chen, An Introduction to Single-User Information Theory, Springer, July 2018. Additionally, a set of copyrighted class notes for advanced topics will be provided.
- 地點
- ED831 or ED823
- 時間
- If necessary, students can contact the professor or TA for a time to discuss their questions.
- 聯絡方式
- Proefssor: poning@faculty.nctu.edu.tw or TA: bh.chlin@gmail.com