Information Theory
Introduction
TS. Lê Nguyên Khôi
Trường Đại học Công nghệ, ĐHQGHN
Lecturer Information
TS. Lê Nguyên Khôi
Bộ môn KHMT, Khoa CNTT, Trường ĐHCN, ĐHQGHN
e-mail: khoi.n.le@vnu.edu.vn
Research Areas
Evolutionary Computation
Federated Learning
Robotics
Lê Nguyên Khôi Information Theory 1
Course Information
Course: INT2044E – Information Theory
Number of credits: 3
Lecture: 3 lectures – 15 weeks
Course webpage: https://portal.uet.vnu.edu.vn/
Grading components
Assignment / class test (40%)
End-of-term written exam (60%)
Textbook
Elements of Information Theory, 2nd edition,
Thomas Cover, Joy Thomas, Wiley, 2006
Lê Nguyên Khôi Information Theory 2
Outline of the Course
Probability and statistics
Entropy, relative entropy
Mutual information
Data compression
Gambling
Channel capacity
Lê Nguyên Khôi Information Theory 3
What is Information Theory?
Information theory studies
quantification of information
representation of information
communication of information
It was originally proposed by Claude Shannon in 1948
Brief explanation: http://y2u.be/d9alWZRzBWk
Lê Nguyên Khôi Information Theory 4
Communication
Lê Nguyên Khôi Information Theory 5
Communication
Lê Nguyên Khôi Information Theory 6
Communication Theory?
In 1948, Claude E. Shannon of Bell Labs (America)
published a paper “The Mathematical Theory of
Communications”, and created this field
Shannon’s work grew out of solving problems of
electrical communication during WWII, but IT applies to
many other fields as well.
Key idea: Communication is sending information from
one place and/or time to another place and/or time over
a channel that might have errors.
Lê Nguyên Khôi Information Theory 7
Main Contributions of the Paper
The first time probability was applied to deal with
communication problems
The innovation idea was that “information” (from any
source) has a digital nature
The concept of “entropy” was invented and used to
measure the “complexity” or the “randomness” of the
source
The paper also set a foundation for data compression,
coding, and decoding with error detection and
correction
Lê Nguyên Khôi Information Theory 8
Shannon’s Communication Model
The paper introduced a model for communication:
encoding, sending signal though a channel, and
decoding
Lê Nguyên Khôi Information Theory 9
Source
Voice
Words
Pictures
Music, art
Human cells about to reproduce
Human parents about to reproduce
Sensory input of biological organism
or any signal at all (any binary data)
Lê Nguyên Khôi Information Theory 10
Channel
Telephone line
High frequency radio link
Storage (disk, tape, internet, TCP/IP, facebook, twitter),
transmission through time rather than space, could be
degradation due to decay
Biological organism (send message from brain to foot,
or from ear to brain)
Lê Nguyên Khôi Information Theory 11
Receiver
The destination of the information transmitted
Person,
Computer
Disk
Analog Radio or TV
Internet streaming audio system
Lê Nguyên Khôi Information Theory 12
Noise
Represents our imperfect understanding of the
universe.
Thus, we treat it as random, often however obeying
some rules, such as that of a probability distribution
Lê Nguyên Khôi Information Theory 13
Lê Nguyên Khôi Information Theory 14
Encoder
Processing done before placing info into channel
First stage: data reduction (keep only important bits or
remove source redundancy), followed by redundancy
insertion catered to channel.
A code = a mechanism for representation of
information of one signal by another.
An encoding = representation of information in another
form
Lê Nguyên Khôi Information Theory 15
Decoder
Exploit and then remove redundancy
Remove and fix any transmission errors
Restore the information in original form
Lê Nguyên Khôi Information Theory 16
Example: Human Speech
Source = human thought, speakers brain
Encoder = Human Vocal Tract
Channel = air, sound pressure waves
Noise = background noise
Decoder = human auditory system
Receiver = human thought, listeners brain
Lê Nguyên Khôi Information Theory 17
Example: Morse Code
Lê Nguyên Khôi Information Theory 18
Morse Code
Morse code, series of dots and
dashes to represent letters
Most frequent letter sent with the
shortest code, 1 dot
Note: codewords might be prefixes
of each other (e.g., “E” and “F”).
Uses only binary data (single
current telegraph, size two
“alphabet”), could use more (three,
double current telegraph), but this
is more susceptible to noise (binary
in computer rather than ternary)
Lê Nguyên Khôi Information Theory 19
On Error
How do we decrease errors in a communications
system?
Physical: use more reliable components in circuitry, broaden
spectral bandwidth, use more precise and expensive
electronics, increase signal power
All of this is more expensive
Question: Given a fixed imperfect analog channel and
transmission equipment, can we achieve perfect
communication over an imperfect communication line?
Yes: Key is to add redundancy to signal
Encoder adds redundancy appropriate for channel
Decoder exploits and then removes redundancy
Lê Nguyên Khôi Information Theory 20
The Meaning of Information
For years, telegraph messages were “compressed” by
leaving certain words out,
or sending key words that stood for longer messages,
since costs were determined by the number of words
Yet people could easily read these abbreviated
messages, since they supplied these predictable
words, such “a” and “the”
Lê Nguyên Khôi Information Theory 21
The Meaning of Information
For Shannon, information is symbols that contain
unpredictable news, like our sentence,
“only infrmatn esentil to understandn mst b tranmitd”
The predictable symbols that we can leave out, which
Shannon calls redundancy, are not really news
Lê Nguyên Khôi Information Theory 22
Hamun Mnid
“Aoccdrnig to a rscheearch at Cmabrigde
Uinervtisy, it deosn’t mttaer in waht oredr
the ltteers in a wrod are, the olny iprmoetnt
tihng is taht the frist and lsat ltteer be at the
rghit pclae. The rset can be a toatl mses
and you can sitll raed it wouthit porbelm.
Tihs is bcuseae the huamn mnid deos not
raed ervey lteter by istlef, but the wrod as a
wlohe.”
Lê Nguyên Khôi Information Theory 23
The Meaning of Information
Another example is coin flipping. Each time we flip a
coin, we can transmit which way it lands, “heads” or
“tails,” by transmitting a code of “zero” or “one.”
But what if the coin has two “heads” and everyone
knows it? Since there is no uncertainty concerning the
outcome of a flip, no message need be sent at all
Lê Nguyên Khôi Information Theory 24
Outline of the Course
Probability and statistics
Entropy, relative entropy
Mutual information
Data compression
Gambling
Channel capacity
Lê Nguyên Khôi Information Theory 25
