Information Theory
Dr. Ranjay Hazra
At the end you will know
What is information and how its important.
What is data compression its aspect;
entropy.
Some coding techniques.
Data transmission through channel and its
reception our goal to achieve.
Information Theory
Invented by C.E. Shannon in late 1940s.
Information theory deals with mathematical
modeling and analysis of a communication system
rather than physical sources and channels.
In particular it helps us to find
The amount of information contained in the signal.
The irreducible complexity below which the signal cant
be compressed.
The ultimate transmission rate for reliable
communication over a noisy channel.
Information Theory
Information theory answers two fundamental questions:
What is the ultimate data compression?
Answer: The Entropy H.
What is the ultimate transmission rate?
Answer: Channel Capacity C.
The concept that increasing transmission rate over a channel
increases the error rate. Shannon showed that this is not true
as long as rate is below Channel Capacity.
Shannon has further shown that random processes have an
irreducible complexity below which they can not be
compressed.
INFORMATION THEORY 5
We assume a discrete memory less source ,
memory less in the sense that the symbol emitted
at any point of time is independent of previous
choices.
The source output as emitted during every signaling
interval is modeled as a discrete random variable, S,
which takes on symbols
{s0 , s1 , sfrom a fixed finite alphabet
2 ...s K 1}
with probabilities
P(S=sk) = pk k =0,1,2,3..
K 1
and pk 1
k 0
Information
For an event S = sk with the symbol sk emitted by the
source with probability pk. Then if pk=1 and pi = 0 and
for all i k , then there is no information because we
know what the message is going to be from the source.
But if pk is low, then there is more surprise and so the
information when sk is emitted by the source than the
symbol si which is having the higher probability to be
emitted.
The amount of information is related to the inverse of
the probability of occurrence as given by
1
I ( sk ) log( ) log( pk )
pk
Information
So, I ( sk ) I ( si )
for
pk pi
When pk=1/2, we have I(sk)=1, i.e., one bit
of information that we gain when one of two
possible and equally likely events occur.
And I ( sk ) 0;0 pk 1
Entropy
The amount of potential information contained is a signal is termed the
entropy, usually denoted by H, which is defined as follows:
We can essentially think of this as a weighted average of log 1/P(X) . The
quantity 1/P(X) expresses the amount of surprise in an event Xi.e., if the
probability is low, then there is a lot of surprise, and consequently a lot of
information is conveyed by telling you that X happened.
Its a measure of the average information content per source symbol.
The reason we are taking the log of the surprise is so that the total amount of
surprise from independent events is additive. Logs convert multiplication to
addition, so
.
Entropy
Thus, entropy essentially measures the average
surprise or average uncertainty of a random
variable.
If the distribution P(X) is highly peaked around one
value, then we will rarely be surprised by this variable,
hence it would be incapable of conveying much
information.
If on the other hand P(X) is uniformly distributed, then
we will be most surprised on average by this variable,
hence it could potentially convey a lot of information.
Properties of Entropy
(P1) H(x) 0
0 p(x) 1 log [ 1/p(x)] 0
[E] x=1 p
0 1-p
H(x) = - p log p (1-p) log(1-p)
= H(p) the entropy function.
INFORMATION THEORY 11
Entropy
Limiting factor:
Entropy is 0, if and only if pk=1 for some k and
remaining probabilities in the set are all 0 this
means there is no uncertainty in the
information.
Entropy is log2 K, if and only if pk=1/K for all k
i.e., all the symbols in the alphabet are equi-
probable; this upper bound on entropy
corresponds to maximum information.
Entropy . extended
We often use blocks rather than individual
symbols, with each block consisting of n
successive source symbols.
This block could be viewed as an extended source
with a source alphabet n that hasK n distinct
blocks, where K is the no of distinct symbols in
the source alphabet of the original source.
In case of a discrete memory less source, the
source symbols are statistically independent.
Entropy . extended
Hence the probability of the source symbol n
in is equal to the product of the
probabilities of the n source symbol in
consisting of the n particular source symbol in
. We may thus expect that the entropy of
the Hextended
( ). source is equal to n times the
or
H ( n ) nH ( )
Example
Consider a discrete memory less source
with source alphabet
{s , s , s } with
0 1 2
respective probabilities p0= ; p1= & p2
= .
The entropy
H ( ) pof
log the
0 ( ) source
1
2 p log ( ) p becomes
1
1 2
1
log ( ) 2 2
p0 p1 p2
1 1 1
log 2 (4) log 2 (4) log 2 (2)
4 4 2
3
2
Example
For the second order extension of the
source with the original source consisting 3
symbols the extended second order source
will consists of 9 symbols as given by
0 s0 s0 ; 1 s0 s1 ; 2 s0 s2 ; 3 s1s0 ; 4 s1s1 ; 5 s1s2 ;
6 s2 s0 ; 7 s2 s1 ; 8 s2 s2 ;
with their probabilities given as
1 1 1 1 1
0 ; 1 ; 2 ; 3 ; 4
16 16 8 16 16
1 1 1 1
5 ; 6 ; 7 ; 8
8 8 8 4
Example
So the entropy of the extended source is
8
1
H ( ) p ( i ) log 2
2
i 0 p ( i )
1 1 1 1 1
log 2 (16) log 2 (16) log 2 (8) log 2 (16) log 2 (16)
16 16 8 16 16
1 1 1 1
log 2 (8) log 2 (8) log 2 (8) log 2 (4)
8 8 8 4
3
so,
H ( 2 ) 2 H ( ).
Information Rate
If a source of message generates messages
at the rate r messages per second then
information rate is defined as
R= rH = average no of bits of information
/ second.
where, H stand for entropy of the source.
Source Coding
From a transmitters point of view data of
the source is compressed in a source
encoder.
For efficient compression we need the
knowledge of entropy or the statistics of the
source.
For an example, we can assign short code
to frequent source codes and longer code to
infrequent one this is called variable
length code.
Requirement of Efficient Source
Coding
The primary requirement for a efficient
source encoder is that
The code words produced by the encoder is in
binary form.
The source code is uniquely decodable, so that
the original source sequence can be
reconstructed perfectly from the encoded binary
sequence.
Coding Efficiency
We have the following source encoder
Discrete Source
Memory less Sk Encoder bk
Binary sequenceSource
the above source is having an alphabet
with K different symbols and k th symbol sk
occures with probability pk, k=0,1,2,3K-1.
let the binary codeword assigned to
symbol sk by the encoder have length lk,
measured in bits.
Coding Efficiency
So the average codeword
K 1
length L of the source
encoder as L
k 0
pl k k
in physical terms it represents the average no of bits
per source symbol. L
if Lmin the minimum possible value for , then coding
efficiency of the source
Lmin encoder is given by-
L
L Lmin 1
with we have . encoder is said to be
efficient when efficiency approaches unity.
Shannons First Theorem
Shannons first theorem on coding efficiency gives
the idea to calculate Lmin .It is stated as
H ( )
Given a discrete memory less source of entropy
, the average codeword Llength for any distortion
less source coding scheme is bounded as
L H ( )
So, according to the source coding theorem, the entropy
represents a fundamental limit on the average no of
bits per source symbol necessary to represent a
discrete memory less source in that it can be made as
small as, but no smaller that the entropy, Lmin so
Hwith
( )
,
H ( )
L
Data Compaction
For efficient transmission redundant data should be removed
from the signal prior to transmission.
This operation with no loss of information is performed in
digital form and is called as data compaction or lossless
data compression.
This operation provides the source output with average no
of bits/symbol and also original data could be
reconstructed from these data with no loss of information.
So short descriptions are provided to the most
frequent outcomes and longer for the less frequent
ones.
Prefix Coding
Any sequence made up of the initial part of
the code is called the prefix of the code and
A Prefix Code is defined as a code in
which no code word is the prefix of any
other code word.
Example ofSourc
PrefixProba
Code:Code I Code Code
e bility II III
Symb
ol
s0 0.5 0 0 0
s1 0.25 1 10 01
s2 0.125 00 110 011
s3 0.125 11 111 0111
example
Code I : its not a prefix code since the bit 0,
the codeword for s0, is a prefix of 00 (s2).
Again the bit 1, the codeword for s1 is the
prefix of 11 (s3).
Code III: its also not a prefix code. Justify
Code II: its a prefix code for the given
condition that no code is the prefix of any
other.
Decoding
The important property of this code is that its
uniquely decodable.
To decode a sequence of code words generated
from a prefix source code, the source decoder
starts at the beginning of the sequence
and decodes one code word at a time.
This way it sets up a decision tree which is a
graphical portrayal of code words in the
particular code.
The first received bit moves the decoder to the terminal state
s0, if its 0, or else to a second decision point if its 1.
In the latter case, the second bit moves the decoder one step
further down the tree, i.e., either to s1 if its 0 or to a third
decision point if its 1. and so on..
Once each terminal state emits its symbol the decoder goes
back to its initial state.
The end of the prefix code is always recognizable. Hence,
decoding could be accomplished as soon as the binary
sequence representing the source symbol is fully
received. So its also called the instantaneous code.
Decoding Tree
s0
0 s1
initial state
1 0
s2
1
1
s3
Problem
Decode the sequence 1011111000 and
verify it will produce s1s3s2s0s0
we can prove 1
lim n Ln H ( )
n
So, by making the order n of an extended prefix source
encoder large enough, we can make the code faithfully
represent the discrete memory less source as close as
desired.
In other words the average code word length of an
extended prefix code can be made as small as the
entropy of the source provided the extended code has a high
enough order.
But the disadvantage of extended code is increased decoding
complexity.
Huffman Coding
Its one important class of prefix code.
The basic idea behind the Hoffman coding is to
assign to each of an alphabet a sequence
of bits roughly equal to the amount of
information conveyed by it.
The end result is a source code whose average
code word length approaches the fundamental
limit set by the entropy of the memory less
source namely entropy.
For given set of symbols with different
probabilities there is a reduction process
applied here to generate the code.
The reduction process is continued in a step by
step manner until we are left with a final set of
two source symbols and they are assigned with
0 and 1.
From this trivial last stage we then go back to
the original symbol to find its code word.
Huffman Encoding process
The source symbols are listed in order of decreasing
probability. The two source symbols of lowest probability are
assigned a 0 and a 1 this is the splitting phase.
These two source symbols are regarded as being combined to
form a new source symbol with probability equal to the
sum of two original probabilities (thus it in effect reduces
the no of source symbols by one).
This probability value of the new symbol is placed in the list
according to its value.
This process is continued until we are left with a final list
of source symbols of only two for which we assign 0 and 1.
Huffman Coding process
symbol Stage I Stage II Stage III Stage IV
S0 0.4 0.4 0.4 0.6 --- 0
S1 0.2 0.2 0.4 --0 0.4 ---- 1
S2 0.2 0.2 -- ---0 0.2 -- 1
S3 0.1 ------- 0 0.2 ------ 1
S4 0.1 -------- 1
Contd
Symbol Probability Code word
s0 0.4 00
s1 0.2 10
s2 0.2 11
s3 0.1 010
s4 0.1 011
average codeword length is therefore
L 0.4(2) 0.2(2) 0.2(2) 0.1(3) 0.1(3)
2.2
1 1 1
and entropy H ( ) 0.4 log 2 (
0.4
) 0.2 log 2 ( ) 0.2 log 2 ( )
0.2 0.2
1 1
0.1log 2 ( ) 0.1 log 2 ( )
0.1 0.1
0.52877 0.46439 0.46439 0.33219 0.33219
2.12193
H ( )
efficiency - 2.1293 / 2.2 0.9678
L
Limitations of Huffman Coding
At each splitting level, there is arbitrariness
in the way a 1 or a 0 is assigned to the last
two source symbols.
Ambiguity arises when the probability of a
combined source is found to be equal of
another probability in the list. We may place
the new symbol as high as possible
alternatively, it could be as low as possible.