Announcements Syllabus Schedule/Downloads
Schedule/Downloads
|
Week |
Lecture |
Topics |
Key Words |
Reading Assignments* |
Handouts (悪税葛闘) /Homeworks |
Exam 2016 Fall | Exam 2015 Spring |
廃厩嬢 悪税 (YouTube) /毒辞 |
HW, Exam 2013 |
Quiz/ Exam 2012 |
Quiz/ Exam 2006 |
Homework/ Exam 2004 |
|
|
1 |
1 |
Introduction |
zero-error data compression, source coding theorem, channel coding theorem, rate-distortion theory |
|
|
|
|||||||
|
2 |
Zero-Error Data Compression |
Problem Formulation |
Encoder, Decoder, Source Code, Expected Length, Uniquely Decodable (UD) Code |
Y 2.5, PDC 2.1, 2.2 |
|
|
|||||||
|
3 |
|
||||||||||||
|
2 |
4 |
Inequalities for UD Codes |
Kraft's Inequality, Fundamental Inequality, Entropy Bound, Some Properties of Entropy |
Y 3.1, PDC 2.3, 2.4 |
|
|
|||||||
|
5 |
Prefix-Free (PF) Codes |
Existence Theorem for PF Codes |
Y 3.2, PDC 2.4 |
|
|
||||||||
|
3 |
6 |
||||||||||||
|
Huffman Codes |
Huffman Procedure, Huffman Code, Optimality of Huffman Codes, Asymptotic Optimality of Huffman Codes |
C 5.6, 5.8, PDC 2.5 |
|
||||||||||
|
|
|||||||||||||
|
Source Coding |
Problem Formulation, Pre-requisites |
Formulation of block source-coding, Chebyshev Inequality, Convergence of a sequence |
S 7.4, 7.5, PDC 2.6 |
||||||||||
|
7 |
Source Coding Theorem |
Convergence in Probability, Weak Law of Large Numbers, Weak Asymptotic Equipartition Property (AEP), Source Coding Theorem |
C 3, Y 4.1-4.4, Y 2.8, 4.3, PDC 2.7 |
|
|
|
|||||||
|
8 |
|
|
|||||||||||
|
4 |
|||||||||||||
|
9 |
|
||||||||||||
|
Shannon's Information Measures |
Entropy, Mutual Information, Relative Entropy |
Entropy, Joint Entropy, Conditional Entropy, Mutual Information |
C 2.1-2.6, 2.8,
|
|
|||||||||
|
|
|||||||||||||
|
|
|||||||||||||
|
5 |
10 |
|
|
||||||||||
|
11 |
Chain Rules, Conditional Mutual Information, Chain Rules, Kullback Leibler Distance, Information Divergence, Fano's Inequality, Markov Chain, Data Processing Theorem |
Exam 01 |
|
||||||||||
|
12 |
|
Exam 01
|
|
||||||||||
|
6 |
Channel Coding for DMC |
Definitions and Problem Formulation |
Channel Coding Problem, Discrete Memoryless Channel (DMC), Code Rate, Error Rate |
C 8.5 |
|
||||||||
|
13 |
|||||||||||||
|
14 |
Sketch of Achievability of max I(X;Y) |
(M,n) code, Channel Encoder, Channel Decoder, Sketch of achievability of max I(X;Y) |
|
|
|
||||||||
|
7 |
15 |
Joint AEP |
Random Coding, Joint AEP, Maximal Probability of Error, Markov inequalities |
C 8.1-8.4, 8.6
|
|
|
|||||||
|
16 |
|
||||||||||||
|
8 |
17 |
Noisy Channel Coding Theorem and Its Weak Converse | Typical Set Decoding, Lower Bound on Maximal Probability, Approximate Necessary Conditions to Achieve Channel Capacity, | C 8.7, 8.9, 8.10 |
|
||||||||
|
18 |
Fano's Inequality and Converse of Channel Coding Theorm |
|
|||||||||||
|
19 |
Mutual Information of a DMC, Convex Set, Convex Functions, Channel Capacity of a DMC |
|
|
||||||||||
|
9 |
20 |
|
|
||||||||||
|
21 |
Feedback Capacity, Joint Source Channel Coding Theorem |
Discrete Memoryless Channel with Feedback, Feedback Capacity, Joint Source/Channel Coding |
C 8.12, 8.13 |
|
|
||||||||
|
|
|||||||||||||
|
10 |
22 |
Channel Coding for Gaussian Noise Channel |
Shannon's Information Measures for Continuous Random Variables |
Differential Entropy, Mutual Information, Relative Entropy, AEP |
C 9.1-9.6 |
|
|
||||||
|
23 |
|
||||||||||||
|
24 |
Capacity of Gaussian CMC |
Gaussian CMC, Capacity of Gaussian CMC |
C 10.1, 10.2 |
Exam 02 |
|
Exam 02 |
|
||||||
|
11 |
NCCT for Gaussian CMC and Its Converse |
|
|
||||||||||
|
25 |
|||||||||||||
|
|
|||||||||||||
|
26 |
Sphere Packing Argument, Parallel Gaussian Channels and Water-Filling |
C 10.3-10.6 |
|
||||||||||
|
27 |
Continuous-Time Band-Limited White/Colored Gaussian Noise Channel, Gaussian Channels with Feedback |
|
|
||||||||||
|
|
|||||||||||||
|
12 |
28 |
Rate Distortion Theory |
Problem Formulation |
Vector Quantization, Operational Rate-Distortion Function |
C 13.1, 13.2 PDC 3, PDCut Lecs.#6-7 |
|
|||||||
|
29 |
Rate Distortion Theorem |
Informational Rate-Distortion Function, Rate-Distortion Theorem, Sphere Covering Argument as Sketch of Direct Part of Rate Distortion Theorem |
C 13.2-13.5 |
|
|
|
|||||||
|
13 |
30 |
Converse of Rate-Distortion Theorem, Distortion Typical Sequences and Set, Distortion Typical Set Encoding, Indicator Function, Direct Part of Rate-Distortion Theorem |
|
|
|
||||||||
|
31 |
|
||||||||||||
|
32 |
AWGN channel and Shannon Bound on BER |
AWGN Channel Revisited |
Gaussian Codebook, DT Complex AWGN channel, Outage, CT bandpass AWGN channel |
|
|
|
|||||||
|
14 |
33 |
Shannon Bound on BER |
Capacity as a function of Eb/N0, Shannon Limit, Bandwidth Efficiency Plane, Joint Source-Channel Coding with Distortion, Shannon bound on Pb vs. Eb/N0 |
|
2016 神嫌舛舛採硲 舘奄悪疎 掻 背雁 採歳 廃厩嬢 悪税 video (Part 1) Shannon's BER bounds (Part2)
|
|
|||||||
|
34 |
|
廃厩嬢 悪税 34-1 (34-1)
毒辞 1 |
|||||||||||
|
|
Miscellaneous |
Entropy Rate, Universal Source Coding, Error Exponent, Occam's Razor, etc. |
|
||||||||||
|
|
Final Exam 19:30-24:00 @LG106 |
|
|
Exam 03 | Exam 03 |
Note_pdf 1
One note 1 |
Exam 03 | ||||||
* References
C2: T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed., John Wiley and Sons, Inc., 2006
C: T. M. Cover and J. A. Thomas, Elements of Information Theory. John Wiley and Sons, Inc., 1991.
G: R. G. Gallager, Information Theory and Reliable Communication. John Wiley and Sons, Inc., 1968
N: A. El Gamal and Y.-H. Kim, Network Information Theory. Cambridge Univ. Press, 2011.
PDC: R. G. Gallager, Principles of Digital Communication. Cambridge Univ. Press, 2008.
S: H. Stark and J. W. Woods, Probability, Random Processes, and Estimation Theory for Engineers, 2nd Ed., Prentice-Hall, Inc., 1994.
Y: R. W. Yeung, A First Course in Information Theory. Kluwer Academic/Plenum Publishers, 2002.
Recommended Papers