Undergraduate Course
Fundamentals of
I f i Th
Information Theory Xiaojun Hei
Internet Technology and Engineering R&D Center
Department of Electronics and Information Engineering
Email: heixj@https://www.doczj.com/doc/7610794025.html,
Web: https://www.doczj.com/doc/7610794025.html,/heixj
Phone:027-875407451
Phone: 027********
pp
Course support
Office: West Rm324, South Building #1
Office Hours:2:30-3:30pm Wednesday p p j
https://www.doczj.com/doc/7610794025.html,/zh-cn/selfspace/heixj/info10fall/index.html
Course grading g g
Prerequisite courses Probability Theory Stochastic Process
Textbook Thomas M. Cover and Joy A. Thomas, “Elements of y Information Theory”, 2nd, John Wiley & Sons, 2006, 中文版，“信息论基础”，阮吉寿，张华，翻译，机械工业出版社2007业出版社，2007. Lecture notes R f b k Reference books Grading
(30%)
Homework (30%)Final (70%)
Course materials
Landmark paper in information theory:
Claude E Shannon“The Mathematical Theory of
Claude E. Shannon, The Mathematical Theory of
Communications”. Bell System Technical Journal, July
& October 1948.
English textbooks:
English textbooks:
Thomas M. Cover and Joy A. Thomas, “Elements of Information Theory”, 2nd, John Wiley & Sons, 2006
Th M C d J A Th“El t f I f ti Thomas M. Cover and Joy A. Thomas, “Elements of Information Theory”, 2nd, John Wiley & Sons, 2006, 中文版，“信息论基础”，阮吉寿，张华，翻译，机械工业出版社，2007.
David Tse and Pramod Viswanath“Fundamentals of
David Tse and Pramod Viswanath, Fundamentals of
wireless communication”, Cambridge : Cambridge
University Press, 2005
Chinese textbooks:
傅祖芸，“信息论－基础理论与应用”，电子工业出版社，2001.
陈运，周亮，陈新，信息论与编码，电子业出版社， 陈运，周亮，陈新，“信息论与编码”，电子工业出版社，2002.
About myself
y
Current status Research interests
Associate Professor
ITEC, EIE, HUST
Network Measurement
Peer-to-Peer Streaming
I t t b d M i A li ti
Education
Ph.D., HKUST
Internet-based Music Applications
Projects
NSFC:large-scale network Master, HKUST
B.Eng., HUST
NSFC: large scale network
measurement: theory and
techniques
N ti l115t h l t
National 11-5 technology support
program: music digitalization
research and platform
development
National 12-5 technology support
program:network security and
program: network security and
adolescent development
科研训练课题
基于标签的音乐推荐技术研究
基于MATLAB的音乐特征提取
聚类算法或推荐算法的C++程序实现
基于Flash Player 10的P2P流媒体应用
Sk
Skype用户网络追踪技术研究
基于Flash插件方法的RTT时延测量
BitTorrent爬虫软件的设计与实现
Gnutella爬虫软件的设计与实现
迅雷爬虫软件的设计与实现
基于Winpcap的PPLive/PPS流量分析工具的设计与实现 基于BitTorrent的端节点测量技术研究
多媒体资源在线转换和同步工具
分布式资源系统高效NAT穿越技术研究
基于本体的知识发现系统研究
基于Linux的Java Web网站设计与实现
基于Java Web的民间文艺资源管理系统模块设计与实现
Information theory and coding
Lecture 1 --A
Lecture1
Lecture 1
Content
Chapter1. Course Introduction
7
p
Chapter.1 Course Introduction
1.1 What is Information?
1.2 What is Information theory?
12Wh t i I f ti th?
1.3 Information theory in Communication 1.4 Course organization
Essential of information
Although Information has different instances: M k l d i l
Message, knowledge, signal, …
The essential of information is that
When you receive information, uncertainty is eliminated
How to measure information
Uncertainty is eliminated by information
This motivate us to define a quantitative measure of “information”
Mathematical tool:
Uncertainty can be described by probability theory
can be described by probability theory,
stochastic process, …
Modeling steps:
Modeling steps:
(1) investigate the properties of information
(2) model them in probabilities
(2)model them in probabilities
Step1: Information properties p p p
Step1investigate the properties of information Step1. investigate the properties of information
[Property1] Information contained in events ought to be defined in terms of some measure of the of defined in terms of some measure of the uncertainty of the events.
]Less certain events ought to contain more [Property2] Less certain events ought to contain more information than more certain events.
3]The information of [Property 3] The information of unrelated/independent events taken as a single event should equal the sum of the information of the unrelated events.
Step2: information model p
Step2Model the properties of information in probabilities Step2. Model the properties of information in probabilities As to property (1)
A nature measure of uncertainty of event is the A nature measure of uncertainty of event a is the probability of a , P(a)
we will define the information in terms of we will define the information in terms of P(a)As to properties (2)and (3)
As to properties (2) and (3) the properties (2) and (3) will be satisfied if the information in is defined as
information in a is defined as )
a (log )a (P I ?=
Information of event and source
Information of an event
Suppose the event A with probability P(A),its self self--information is defined by:
Information of a source
)
(log )(A P A I ?= Suppose the source as random variable X with a probability mass function p(x),its average information or is defined by:
or entropy is defined by:More details of these concepts in source entropy )
(log )()(x p x p X H ∑?=
More details of these concepts in source entropy
y
1.2 What is information theory?
The chief concern of information theory is to discover mathematical laws in communicating or manipulating th ti l l i i ti i l ti
information.
Information theory sets up quantitative measures of information, and of the capacity of various systems to information and of the capacity of various systems to
transmit, store, and otherwise process information.
Information of an event:I(A)
Information of an event: I(A)
Information of a source: H(X)
Shannon’s information theory y
The classical information theory
is created by the paper of Shannon is created by the paper of Shannon
``A Mathematical Theory of Comm-
unication’’in 1948.
unication in 1948. It origins in analyzing the limits
of communications.
“The fundamental problem of communication is that of reproducing at one point either exactly or p y approximately a message selected at another point ” –E.C. Shannon Q1:What is the ultimate data compression Claude E. Shannon 1916Claude E. Shannon 1916--2001
Q1: What is the ultimate data compression ?Answer: The entropy H Q2: What is the ultimate transmission rate of communication ?Answer:The channel capacity Answer: The channel capacity
C
Applications in communication pp
The main application of Information theory is coding .Th di th i t d b Sh
Three coding theorems invented by Shannon: Source coding theorem Channel coding theorem Channel coding theorem Rate distortion theorem Practical methods have been invented and implemented Practical methods have been invented and implemented after Shannon:
Source coding: Huffman codes (compact), Lempel-Ziv g (p ),p (compress, gzip )
Channel coding: error-correcting codes (Hamming, R d S l l ti l t lli t b Reed-Solomon, convolutional, trellis, turbo ) Rate-distortion coding: vocoders, minidiscs, MP3, JPEG MPEG JPEG, MPEG
Relationship with other fields p
It intersects with many other science subjects
Information Theory
Math
Relationship with other fields (cont.)p ()
Intersection with other fields
Communication theory
Limits of communication theory Probability theory
Limit theorems, Large deviations St ti ti Fi h i f ti H th i t ti Statistics
Fisher information, Hypothesis testing Economics
Portfolio theory, Kelly gambling Mathematics
Inequalities Computer Science
Kolmogorov complexity Thermodynamics
Physics AEP , Thermodynamics
Relationship with other fields (cont.) It intersects with many other science subjects
Limit theorems, Large deviations
Limits of communication theory Fisher information, Hypothesis testing AEP , Thermodynamics
Information g Theory Portfolio theory, Kelly gambling Kolmogorov complexity Relationship
with Math with
other fields Inequalities
Limitation of Shannon’s theory y
Limitation of Shannon’s Information Theory
Th b i d k id i“Al t thi i l t The basic and key idea is “Almost everything is almost provable”. Following this idea, we can model the
information source by a sample space, and describe
information source by a sample space,and describe
the outcomes by probabilities.
How about otherwise? Uncountable space, unknown
probabilities, …
b bili i
Other approaches in information theory
Other approaches in information theory
Noise theory, signal filter and detection, statistical
p,,
detection and prediction, modulation, …
In this course, our scope is only Shannon’s theory.