Lecture 07 Summary (Information Theory)

Lecture07 Summary

Asymptotic Equipartition Property (AEP) is given by

$AEP is defined as limit as n tends to infinity of (-log p(x sup n)). And AEP tends to H(X)$

where X is the DMS with statistically independent symbols x_i fed into a symbol register xⁿ = (x₀, x₁, …, x_n-1)
Practical consequence of AEP $limit as n tends to infinity of (-log p(x sup n)) over n$ is that it makes lossless data compression possible (data compaction).
In general

$H(X sub R) is lessthan H(X) and H(X sub R) = H(X) iff X is DMS$
If X is an Ergodic source, then

$limit as n tends to infinity of (-log p(x sup n)) over n tends to H(X sub R)$

This is called Shannon-McMillan-Breiman Theorem (S-M-B Th.)
Ergodic source are source whose
- Probabilities don't change with time, i.e., stationary.
- For any and all of its statistics,
  
  Time average = Ensemble average

In the communication system

The typical set ⁿA_ε ⊂ ⁿX_C such that

$sup n A sub epsilon = set of elements x sup n belonging to sup n X sub C given p(x sup n) is greaterthanequal to 2 index (-n times (H(X) + epsilon)) and p(x sup n) is lessthanequal to 2 index (-n times (H(X) - epsilon))$

where ε > 0 is an arbitrarily small constant.
The set ⁿA_ε is typical enough that

$P (x sup n belongs to sup n A sub epsilon) is greaterthan (1 - epsilon)$

for sufficiently large n.
The size of a typical set is given by

$(1 - epsilon) times 2 index (n times (H(X) - epsilon)) is lessthanequal to |sup n A sub epsilon| is lessthanequal to 2 index (n times (H(X) + epsilon))$

where |ⁿA_ε| is the cardinality of ⁿA_ε.
The number of data–bits (l) required to form a typical set $sup n A sub epsilon is subset of sup n X sub C$ is

$log base 2 |sup n A sub epsilon| + 1 + 1 is lessthanequal to n times H(X) + n times epsilon + 1 + 1$

and

$l over n is lessthanequal to H(X) + epsilon + 2 over n$

l ∕ n is the number of $bits over characters (x belongs to X)$ .

✪

♻
After this lecture you may take a mini EXAM
♻

Lectures on Information Theory