Lecture 1.
Introduction
• What is the course about?
• Logistics
• Questionnaire
Dr. Yao Xie, ECE587, Information Theory, Duke University
What is information?
Dr. Yao Xie, ECE587, Information Theory, Duke University 1
!"#$%&'&($%&$#&'&)*(+$,'#-&*,.$&'&/0'(1&"$023&
%"*("&"'4&"*5"2#&*,6$#7'+$,&0$448&
9&!$7&:$;2#&
Dr. Yao Xie, ECE587, Information Theory, Duke University 2
How to quantify information?
Small information content Large information content
Dr. Yao Xie, ECE587, Information Theory, Duke University 3
What is the fundamental limit of data transfer rate?
!"#"$%&'('%)'(*%+%,-"(./% #"-*)%0123/$%&'('%)'(*%+%4-"(./%
Dr. Yao Xie, ECE587, Information Theory, Duke University 4
Some people think information theory (IT) is about...
Dr. Yao Xie, ECE587, Information Theory, Duke University 5
But IT is also about these...
%&1,-2$
!"#"$%&'()*++,&-$$
%&'(.#"0&-3$4&5'&2&)&6$%&'(5*7,#8$ !"#"$%&''.-,/"0&-$
Dr. Yao Xie, ECE587, Information Theory, Duke University 6
And even these...
!"#$%&'( )*%+,&"--"./(0"1-213(
91:"-#+"1#;(36+<=213(
42%215%&+678-(
Dr. Yao Xie, ECE587, Information Theory, Duke University 7
Where IT all begins...
!"#$%&'())&*+,-&.(/0-&123456)& *065525%&!"!7&8&9::!&
Dr. Yao Xie, ECE587, Information Theory, Duke University 8
Information Theory
• Shannon’s information theory deals with limits on data compression
(source coding) and reliable data transmission (channel coding)
– How much can data can be compressed?
– How fast can data be reliably transmitted over a noisy channel?
• Two basic “point-to-point” communication theorems (Shannon 1948)
– Source coding theorem: the minimum rate at which data can be
compressed losslessly is the entropy rate of the source
– Channel coding theorem: The maximum rate at which data can be
reliably transmitted is the channel capacity of the channel
Dr. Yao Xie, ECE587, Information Theory, Duke University 9
• Since Shannon’s 1948 paper, many extensions
– Rate distortion theory
– Source coding and channel capacity for more complex sources
– Capacity for more complex channels (multiuser networks)
• Information theory was considered (by most) an esoteric theory with no
apparent relation to the “real world”
• Recently, advances in technology (algorithms, hardware, software) today
there are practical schemes for
– data compression
– transmission and modulation
– error correcting coding
– compressed sensing techniques
– information security · · ·
Dr. Yao Xie, ECE587, Information Theory, Duke University 10
IT encompasses many fields
Dr. Yao Xie, ECE587, Information Theory, Duke University 11
In this class we will cover the basics
• Nuts and Bolts
– Entropy: uncertainty of a single random variable
∑
H(X) = − p(x) log2 p(x)(bits)
x
– Conditional Entropy: H(X|Y )
– Mutual information: reduction in uncertainty due to another random
variable
I(X; Y ) = H(X) − H(X|Y )
– Channel capacity C = maxp(x) I(X; Y )
∑
– Relative entropy: D(p||q) = x p(x) log p(x)
q(x)
Dr. Yao Xie, ECE587, Information Theory, Duke University 12
Physical Channel
Source Encoder Transmitter Receiver Decoder
• – Data compression limit (lossless source coding)
– Data transmission limit (channel capacity)
– Tradeoff between rate and distortion (lossy compression)
Data compression Data transmission
limit limit
^
min l (X; X ) max l (X; Y )
Dr. Yao Xie, ECE587, Information Theory, Duke University 13
Important Funcationals
• Upper case X, Y, ... refer to random variables
• X , Y, alphabet of random variables
• p(x) = P(X = x)
• p(x, y) = P(X = x, Y = y)
• Probability density function f (x)
Dr. Yao Xie, ECE587, Information Theory, Duke University 14
∑
• Expectation: µ = E{X} = xp(x)
• Why is this of particular interest? It appears in Law of Large Number
(LLN): If xn independent and identically distributed,
1 ∑
N
xn → E{X}, w.p.1
N n=1
• Variance: σ 2 = E{(X − µ)2} = E{X 2} − µ2
• Why is this of particular interest? It appears in Central Limit Theorem
(CLT):
1 ∑
N
√ (xn − µ) → N (0, 1)
2
N σ n=1
Dr. Yao Xie, ECE587, Information Theory, Duke University 15
Information theory: is it all about theory?
Yes and No.
• Yes, it’s theory. We will see many proofs. But it’s also in preparation
for other subjects
– Coding theory (Prof. R. Calderbank)
– Wireless communications
– Compressed sensing
– Stochastic network
– Many proof ideas come in handy in other areas of research
Dr. Yao Xie, ECE587, Information Theory, Duke University 16
• No. Hopefully you will walk out of this classroom understanding
– Basic concepts people talk on the streets:
entropy, mutual information ...
– Channel capacity - all wireless guys should know
– Huffman code (the optimal lossless code)
– Hamming code (commonly used single error correction code)
– “Water-filling” - power allocation in all communication systems
– Rate-distortion function - if you want to talk with data compression
guy
Dr. Yao Xie, ECE587, Information Theory, Duke University 17
Course Logistics
• Schedule: T, Th, 1:25-2:40pm, Hudson 207
• TA: Miao Liu, Email: miao.liu@duke.edu
• Homework: out Thurs in class, due next Thurs in class
• Grading: homework 30%, two in-class Midterms (each 20%), one Final
30%
• Midterms: 10/4, 11/6 in class
• Final: 11/29 in class
• Prerequisite: basic probability and statistics
Dr. Yao Xie, ECE587, Information Theory, Duke University 18
