Information theory

Lecture#1
 Introduction
• IT is the scientific study of the quantification, storage, and communication of
information. IT is a quantitative treatment of what is sent through the
communication system rather than the system itself.

• The field was established by the work of Harry Nyquist and Ralph Hartley, in
1920s, and Claude Shannon in 1940s.

• The field is at the intersection of probability theory, statistics, computer science,

statistical mechanics, communication engineering, and computer networks.
 Schematic diagram of communication system

• Application of information theory include:

• Lossless data compression (e.g., ZIP files)
• Lossy data compression (e.g. MP3s and JPEGs)
• Channel coding (e.g. for DSL)

The theory is interested in:

➢ The rate of information issuing from any source
➢ The information capacity of any channel
➢ The efficiency of codes by means of which this information is sent.
 Source Coding
• Based on characteristics/features of a source,
• Source Encoder-Decoder pair is designate to reduce the source output to a
Minimal Representation.

• [Shannon 1948]
• How to model a signal source? ←Entropy, Random process
• How to measure the content of a source?
• How to represent a source? Code-design
• How to model the behavior of a channel?
• Channel capacity

4
 Source Coding (Cont.)

• Redundancy Reduction →
1. Data Compression
2. Data Compaction
• Modalities of Sources:
1. Text
2. Image
3. Speech/Audio
4. Video
5. Hybrid

5
 Channel coding

Introduction redundancy into the channel encoder and using this redundancy at the
decoder to reconstitute the input sequences as accurately as possible, i.e., channel
coding is designate to minimize the effect of the channel noise.

6
Examples
Examples
What is information?
• Can we measure information?
• Consider the two following sentences:

1. There is a traffic jam on I5

2. There is a traffic jam on I5 near Exit 234

Sentence 2 seems to have more information than that

of sentence 1. So sentence 2 provides more useful
information.

9
What is information?
Consider the following two sentences

1. There is a traffic jam on I5 near Exit 160

2. There is a traffic jam on I5 near Exit 234

It’s not clear whether sentence 1 or 2 would

have more information

10
What is information?

• Let’s attempt at a different definition of information.

• How about counting the number of letters in the two sentences:

1. There is a traffic jam on I5 (22 letters)

2. There is a traffic jam on I5 near Exit 234 (33 letters)

Definitely something we can measure and compare!

11
Uncertainty and Information

• "John passed the Math exam“

• This message carries information that changes our
knowledge state about this event from uncertain
(probable) into certain.

• "The sun moves from east to west“

• This message does not carry information (This is a
physical event which we are always certain that it
must happen).

12
How to measure the information content in a
certain message?

• If we assume that the probability that John passes the Math

exam is 100 % (p=1), then the message information content
equals zero.

• On the contrary, if we receive a message telling that John has

failed, we would be surprised by this message which is against
our expectation, the information content of this message is
high.

• There is a functional relation between the information content

of a message and the probability of occurrence of certain event.

13
What is information?
• First attempt to quantify information by Hartley (1928).

• Every symbol of the message has a choice of S possibilities.

• A message of length l , therefore can have s l distinguishable possibilities.

l
• Information measure is then the logarithm of s

I = log(s l ) = l log(s)

One symbol (letter) has the information of log(s ) then a sentence of length l
should have l times more information, i.e. l log s
14
 Properties of information

• A quantitative measure of information contained in an event, have some properties

such as:

1. Information contained in events ought to be defined in terms of some measure of

the uncertainty of the events.

2. Less certain events ought to contain more information than more certain events.

3. The information of unrelated/independent events taken as a single event should

equal the sum of the information of the unrelated events.

15
• A nature measure of the uncertainty of an event α is the probability of α denoted P(α).
• The properties (2) and (3) will be satisfied if the information in α is defined as
• I (α) = －log P(α)
• The base of the logarithm depends on the unit of information to be used.

• Information (Source)
• S1 S2 ‧‧‧ Sq：Source alphabet
• P1 P2 ‧‧‧ Pq：Probability
• Facts:
1) The information content is inversely related to the probability of occurrence.
2) The information content from two different independent symbols is the sum of the
information content from each separately. Since the probability of two independent
choices are multiplied together to get the probability of the compound event, it is
natural to define the amount of information as

16
Self Information
• Assume a memoryless source with
• alphabet A = (a1, …, an)
• symbol probabilities (p1, …, pn).
• How much information do we get when finding out that the next symbol is ai?
• According to Shannon the self information of ai is

17
Why?
Assume two independent events A and B, with
probabilities P(A) = pA and P(B) = pB.

For both the events to happen, the probability is

pA ¢ pB. However, the amount of information
should be added, not multiplied.

Logarithms satisfy this!

No, we want the information to increase with
decreasing probabilities, so let’s use the negative
logarithm.
18
Self Information
Example 1:

Example 2:

Which logarithm? Pick the one you like! If you pick the natural log,
you’ll measure in nats, if you pick the 10-log, you’ll get Hartleys,
if you pick the 2-log (like everyone else), you’ll get bits.
19
 Measure of Information
1
I ( mk ) 
p ( mk )
I (mk )  0
I ( mk ) = 0 as p (mk ) = pk =1
pk 1→ 0
I (mk ) 0→

I (mk and m j ) = I (mk ) + I (m j )

20
 Measure of Information

I (mk ) = − logb p (mk )

• For natural logarithm base (e),

The unit is nat.
• If the base is 10,
The unit is decit or Hartly.
• When the base is 2,
The unit bit (binary digit).
21
22
 Average Information

 Shannon’s measure of information is the number of bits to

represent the amount of uncertainty (randomness) in a
data source, and is defined as entropy
n
H = − pi log( pi )
i =1

Where there are n symbols 1, 2, … n, each with

probability of occurrence of pi
23
 Shannon’s Entropy
• Consider the following string consisting of symbols a and b:

abaabaababbbaabbabab… ….

• On average, there are equal number of a and b.

• The string can be considered as an output of a below source with equal probability of outputting
symbol a or b:
0.5 a

We want to characterize the average

information generated by the source!
source

0.5 b

24
 Entropy of Symbols in Long Independent
Sequences
• The instantaneous flow of information may fluctuate due to
the randomness involved in the symbol selection.

➢ Hence, we need to talk about average information content of

symbols in a long message.

• The statistical dependence of symbols in a message sequence

will alter the average information content of symbols.

➢ For example, the presence of letter U following Q in an English

word carries less information than the presence of the same
letter U following the letter T.
25
 Entropy of Symbols in Long Independent
Sequences

• Suppose we have a source that emits one of M

possible symbols in an independent sequence
1
s1 with probability p1 I 1 = log 2
p1
1
s2 with probability p2 I 2 = log 2
p2

1
si with probability pi I i = log 2
pi 26
 Entropy of Symbols in Long
Independent Sequences
In a long message containing N symbols

1
s1 occur on average p1 N times I 1 = p1 N log 2
p1
1
s2 occur on average p 2 N times I 2 = p 2 N log 2
p2

1
si occur on average pi N times I i = pi N log 2
pi 27
Entropy of Symbols in Long Independent Sequences

M
1
I tot =  pi N log 2
i =1 pi
M
I tot 1
=  pi log 2
N i =1 pi
M
1
H =  pi log 2
i =1 pi
H (Entropy) is the average information per symbol
28
 Shannon’s Entropy
n
Why H = − pi log( pi )
i =1
Suppose you have a long random string of two binary symbols 0 and 1, and the
probability of symbols 1 and 0 are p
0 and 1 p
Ex: 00100100101101001100001000100110001 ….
If any string is long enough say N, it is likely to contain Np 0 0’s and Np1 1’s.
The probability of this string pattern occurs is equal to

p = p0Np0 p1Np1
− Np0 − Np1
Hence, # of possible patterns is 1 / p = p p1
0
1
# bits to represent all possible patterns is log( p0− Np0 p1− Np1 ) = − Npi log pi
i =0
The average # of bits to represent the symbol is therefore
1
−  pi log pi
i =0
 Entropy (Average Information)

• Entropy: Average information content over the whole alphabet of symbols

• Consider the entropy of the Source can have no meaning unless a model of
the Source is included.
• For a sequence of numbers, we would probably compute the entropy based
on the frequency of occurrence of the individual numbers.
30
31
Entropy
Example: Binary Memoryless Source
BMS 01101000…

Let

Then

1
The uncertainty (information) is greatest when

0 0.5 1
32
Example
Three symbols a, b, c with corresponding probabilities:
P = {0.5, 0.25, 0.25}

What is H(P)?

Three weather conditions : Rain, sunny, cloudy with

corresponding probabilities:
Q = {0.48, 0.32, 0.20}

What is H(Q)?

33
 Properties of Entropy
1. It can be shown that

1. Maximum entropy (H = log N) is reached when all symbols are equiprobable,

i.e., pi = 1/N.

2. The difference log N – H is called the redundancy of the source.

34
 Condition for Maximum Entropy
• Consider a source emitting two symbols with
probabilities p and (1-p). The entropy of that source is
given by

1 1
H = p log 2 ( ) + (1 − p) log 2 ( ) bits symbol
p 1− p

For maximum entropy dH

=0
dp
1− p
log2 ( )=0
p
1− p
(
p
) =1 p= 1 2 H max =1 bit / symbol 35
 Condition for Maximum Entropy

In general, for a source of alphabet of M symbols,

the maximum entropy is attained when, the symbol
probabilities are equal;

p1 = p2 = .......... ........ = pM =1 M
H max = log 2 M bit / symbol
p =0
H =0 if 
p = 1

H max = 1 if p =1 2
36
Variation of entropy with symbol's probability

37
The important properties of the entropy

0  H ( x)  log2 M
H(x) =0, if all probabilities are zero,
except for one that must be unity.

If all probabilities are equal

(messages are called equally-likely)

1
Pi = P ( xi ) = for all i
M

H ( x) = log2 M 38
 Evaluation of Information Source

1- Source Information Rate:

The average number of bits per second

Consider the symbols are emitted at a rate

rs
rs symbols / sec
Each symbol emits on the average H bits/symbol. The
source information rate R bit/sec is the product of
average information content per symbol and symbol
rate

R = rs  H bit / sec 39
 Evaluation of Information Source

2- Source Efficiency:

It is an important parameter to indicate whether the

source is used in an efficient way, or not. It is given by

H(X )
S =  100
H max ( X )

40
Evaluation of Information Source

3- Source Redundancy:
It is the difference between the maximum amount of
information could be get from the source and its
average entropy

RS = [ H max ( X ) − H ( X )] bits / symbol

This means that a discrete information source with

high efficiency has lower redundancy.
41
Evaluation of Information Source

4- Source Capacity:

The maximum information that could be obtained from

the information source in bits per second

CS = rs  H max ( X ) bits / sec

42
 Example
• A discrete source emits one of five symbols once every
millisecond. The symbol probabilities are 1/2, 1/4, 1/8, 1/16, and
1/16, respectively. Find the source entropy and information rate.
Solution

5
H =  pi log2 (1 pi )
i =1

H = (1 2) log2 2 + (1 4) log2 4 + (1 8) log2 8 + (2 16) log2 16

=1.875 bits / symbol

R = rs  H
=1000 1.875 =1875 bit / sec
43
Any Questions ?