Scribd
Upload
18 views7 pages

Information Theory: Entropy & Coding

1. The document discusses discrete memoryless sources and defines entropy as a measure of the average information content per source symbol. 2. Entropy is bounded from 0 to the log base 2 of the number of possible symbols, with 0 representing certainty and the maximum representing total uncertainty. 3. According to Shannon's source coding theorem, the minimum possible average code word length is the entropy, so an efficient source encoder will have an average code word length approaching the entropy.

Uploaded by

Harsha
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
18 views7 pages

Information Theory: Entropy & Coding

1. The document discusses discrete memoryless sources and defines entropy as a measure of the average information content per source symbol. 2. Entropy is bounded from 0 to the log base 2 of the number of possible symbols, with 0 representing certainty and the maximum representing total uncertainty. 3. According to Shannon's source coding theorem, the minimum possible average code word length is the entropy, so an efficient source encoder will have an average code word length approaching the entropy.

Uploaded by

Harsha
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

' $

Uncertainity, Information, and Entropy


Probabilistic experiment involves the observation of the output
emitted by a discrete source during every unit of time. The source
output is modeled as a discrete random variable, S,which takes on
symbols form a fixed finite alphabet.
S = s0 , s1 , s2 , · · · , sk−1
with probabilities
P (S = sk ) = pk , k = 0, 1, · · · , K − 1
We assume that the symbols emitted by teh source during
successive signaling intervals are statistically independent. A source
having the jproperties jist described is called discrete memoryless
source, memoryless in the sense that the symbol emitted at any
time is independent of previous choices.

& %
We can define the amount of information contained in each
' $
symbols.
I(sk ) = log( p1k )
Here, generally use log2 since in digital communications we will be
talking about bits. The above expression also tells us that when
there is more uncertainity(less probability) of the symbol being
occured then it conveys more information. Some properties of
information are summarized here:
1. for certain event i.e, pk = 1 the information it conveys is zero,
I(sk ) = 0.
2. for the events 0 ≤ pk ≤ 1 the information is always I(sk ) ≥ 0.
3. If for two events pk > pi , the information content is always
I(sk ) < I(si ).
4. I(sk si ) = I(sk ) + I(si ) if sk and si are statistically independent.
The amount of information I(sk ) produced by the source during an
& %
' $
arbitrary signalling interval depends on the symbol sk emitted by
the source at that time. Indeed, I(sk ) is a discrete random variable
that takes on the values I(s0 ), I(s1 ), · · · , I(sK−1 ) with probabilites
p0 , p1 , · · · , pK−1 respectively. The mean of I(sk ) over teh source
alphabet S is given by

H(S) = E[I(sk )]
X
K1
= pk I(sk )
k=0

X
K1
1
= pk log2 ( )
pk
k=0

This important quantity is called entropy of a discrete memoryless


source with source alphabet S. It is a measure of average

& %
information content per source symbol.
' $

Some properties of Entropy


The entropy H(S) of a discrete memoryless source is bounded as
follows:
0 ≤ H(S) ≤ log2 (K)
where K is the radix of the alphabet S of the source. Furthermore,
we may make two statements:
1. H(S) = 0, if and only if the probability pk = 1 for some k, and
the remaining probabilities in teh set are all zero; this lower
bound on entropy corresponds to no uncertainity.
1
2. H(S) = log2 (K), if and only if pk = K for all k; this upper
bound on entropy corresponds to maximum uncertainity.

& %
' $

Shannon Source Coding Theorem


An important problem in communication is the efficient
representation of data generated by a discrete source. The process
by which this representation is accomplished is called source
encoding.
Our primary interest is in the development of an efficient source
encoder that satisfies two functional requirements:
1. The code words produced by the encoder are in binary form.
2. The source code is uniquely decodable, so that the original
source sequence can be reconstructed perfectly from the
encoded binary sequence.
We define the average code word length, L̄, of the source encoder
as
& %
' $

X
K−1
L̄ = p k Ik
k=0

In physical terms, the parameter L̄ represents the average number


of bits per source symbol used in the source encoding process. Let
Lm in denote the minimum possible value of L̄. We then define the
coding efficency of the source encoder as
Lm in
η= L̄

The source encoder is said to be efficient when η approaches unity.


According to the source-coding theorem, the entropy H(S)
represents a fundamental limit on the average number of bits per
source symbol necessary to represent a discrete memoryless source
in that it can be made as small as, but no smaller than, the entropy
H(S). Thus with Lm in = H(S), we may rewrite the efficiency of a
source encoder in terms of the entropy H(S) as
& %
' $

H(S)
η= L̄

& %

Common questions

Powered by AI

The efficiency of a source encoder is defined as the ratio of the minimum average code word length to the actual average code word length, denoted as η = Lmin/¯L. An ideal source encoder achieves efficiency when η approaches unity, meaning the average code word length used is as small as the entropy of the source, H(S), without being smaller, which represents the fundamental limit .

According to the Shannon Source Coding Theorem, the entropy H(S) represents a lower bound on the average code word length ¯L required to represent symbols from a discrete memoryless source. The average code word length can be equal to the entropy but cannot be smaller. This relationship defines the efficiency of a source encoding scheme, seeking to achieve the average code word length as close to the entropy as possible for optimal encoding .

The average information content per symbol in a discrete memoryless source is calculated using the formula H(S) = ∑pk log2(1/pk), where the summation is over all symbols in the alphabet, and pk represents the probability of each symbol. This value, known as entropy, represents the average uncertainty or the average amount of information one expects to gain upon observing one symbol from the source .

The entropy value guides the design of an efficient source encoder by setting a fundamental limit on the minimum average code word length required for encoding symbols. An encoder should aim to achieve an average code word length close to this entropy to ensure efficiency, optimizing data compression while maintaining the ability to perfectly reconstruct the original source sequence. This is fundamental in communication systems for minimizing data rate without losing information integrity .

Entropy, denoted as H(S), is a measure of the average information content per source symbol in a discrete memoryless source. It quantifies the uncertainty in the random variable and is bounded by 0 ≤ H(S) ≤ log2(K), where K is the number of symbols in the alphabet. The entropy achieves its maximum value when all symbols are equally likely, indicating maximum uncertainty, and reaches zero when one symbol has a probability of one, implying no uncertainty .

A discrete memoryless source is characterized by the statistical independence of symbols emitted across successive intervals, meaning the selection of any symbol is independent of previous ones. The information content of each symbol is determined by its probability, with less probable symbols carrying more information. This independence implies that each symbol contributes uniquely to the total information, and the collective average information is captured by the entropy of the source .

For a source code to be uniquely decodable according to the Shannon Source Coding Theorem, the encoded binary sequence must allow for the perfect reconstruction of the original source sequence. This means each code word must be distinguishable so that no part of it resembles any other complete code word, ensuring that the original data can be uniquely interpreted from the encoded form .

In a discrete memoryless source, the information conveyed by a symbol is inversely related to its probability of occurring. Specifically, the information content I(sk) of a symbol sk is given by I(sk) = log(1/pk), where pk is the probability of the symbol. This means that a symbol with lower probability conveys more information, as it introduces more uncertainty .

The condition H(S) = log2(K) represents the scenario where a discrete memoryless source achieves maximum entropy, indicating maximum uncertainty about the emitted symbols. This occurs when all symbols in the source alphabet have equal probability, reflecting the highest possible diversity and unpredictability of symbol occurrence. It signifies optimal conditions for encoding from an information-theoretical perspective .

The bounds on the entropy of a discrete memoryless source, 0 ≤ H(S) ≤ log2(K), are important because they signify the range of uncertainty and information content in the source. The lower bound of zero occurs when there is no uncertainty, i.e., one symbol occurs with certainty. The upper bound indicates maximum uncertainty, which occurs when all symbols in the alphabet are equally likely, thereby maximizing the information content per symbol .

You might also like