Communication Chapter 2 - proof ideas Flashcards
idea of proof for gibbs lemma. H(P)≤ the sum from i=1 to m of pᵢ log (1/rᵢ).
- multiply result by ln2 (recall log₂x = lnx/ln2)
- replace H(P) by definition, take all sums to one side, combine logs, replace log by lnx ≤ x-1, expand and separate sums, probabilities sum to 1, gets the hypothesis of theorem which we know holds)
Idea of of proof for theorem. 0≤H(P)≤logm.
[lower bound] follows by definition of entropy.
[upperbound] Set rᵢ=1/m. Then by gibbs lemma we get H(P)=log m (sum of probabilities =1)
Idea of proof for Shannons Noiseless Encoding Theorem [lower bound]
- set up random source, prob distru, optimal prefix free encoding, ℓᵢ=|f(sᵢ)|
- set rᵢ=2^-ℓᵢ
- Apply Mcmillans theorem
- Apply Gibbs Lemma
- manipulate and sub in def in ℓᵢ to get expected length
Idea of proof for Shannons Noiseless Encoding Theorem [upper bound]
- We will construct a prefix-free encoding f* of S that satisfies the inequality
- let ℓᵢ be the smallest integer s.t. pᵢ≥2^-ℓᵢ show the condition for krafts theorem holds
- So by Krafts Theorem there exists a prefix free code C={c₁,..,cₘ} s.t. |cᵢ|=ℓᵢ .
- consier the encoding f* of s s.t. f(sᵢ)=cᵢ for all i in [m]. Then |f(sᵢ)|=ℓᵢ .
- By definition of ℓᵢ we have that pᵢ<2^-(ℓᵢ-1). (just swapping inequality)
- Rearrange this and substitute into the definition of H(S) (manipulate to get result)
idea of proof for ℓ₁≤…≤ℓₘ for an optimal prefix free encoding f* of S with ℓᵢ = |f*(sᵢ)|
- Let f₁ be an optimal prefix-free encoding of S.
- We may assume f₁ satisfies the fact that if pᵢ=pⱼ and i is less than j then |f₁(sᵢ)<=|f₁(sⱼ)|
- assume for a contradiction |f₁(sᵢ)|>|f₁(sᵢ₊₁)|. Then pᵢ>pᵢ₊₁
- let f₂ be encoding obtained from f₁ by swapping the codewords of sᵢ and sᵢ₊₁
- Manipulate the expected length equation for f₂ (make in terms of f₁, and collect terms) this contradicts the optimality of f₁
idea of proof for ℓₘ = ℓₘ₋₁ and the codewords differing only in their last bit for an optimal prefix free encoding f* of S with ℓᵢ = |f*(sᵢ)|
- prove claim: the code associated with the encoding of f₁ has two codewords of maximum length which differ only in their last bit.
- for a contradiction suppose only one codeword of maximum length. Since f₁ is prefix free we can truncate this codeword and still have a prefix free encoding => f₁ was not optimal (a contradiction)
- Now assume f₁ has more than 2 codewords of maximum length, but no 2 differ soley in their last bit. Thus we could truncate any two of them and still have a prefix free encoding => f₁ not optimal (a contradiction)
- by claim and part (a) f₁(sᵢ) and f₁(sᵢ₊₁) have maximum length and are the last two codwords. By reassigning codewords we can see the last two differ only in their last bit.
log₂x =
log₂x = lnx/ln2
lnx ≤
lnx≤x-1
sum from i=1 to m of pᵢ
1
rᵢ in the proof of shannons noiseless encoding theorem proof
rᵢ=2^-ℓᵢ
why do you chose rᵢ=2^-ℓᵢ in the proof of shannons noiseless encoding theorem?
So that you can apply mcmillans theorem to get the hypothesis of gibbs lemma
an encoding denoted with a subscript * is
optimal
an encoding denoted with a subscript H is
a Huffman encoding
pᵢ≥2^-ℓᵢ => (Shannon noiseless encoding theorem, upper bound)
pᵢ<2^-(ℓᵢ-1)
Set up of shannons noiseless encoding theorem (upperbound)
we must construct a prefix free encoding f’ of S that satisfies the inequality: 𝔼(ℓ(f))<=𝔼(ℓ(f’))
Set up of shannons noiseless encoding theorem (lowerbound)
Let S be a random source with probability distribution we may assume pᵢ>0 for all i.
Let f be an optimal prefix-free encoding of S.
For all i let lᵢ=|f(sᵢ)| be the length pf the codeword associated to sᵢ.
Set rᵢ = 2^-lᵢ.
claim in proof for ℓₘ = ℓₘ₋₁ and the codewords differing only in their last bit for an optimal prefix free encoding f* of S with ℓᵢ = |f*(sᵢ)|
the code associated with the encoding of f₁ has two codewords of maximum length which differ only in their last bit.
proof of claim the code associated with the encoding of f₁ has two codewords of maximum length which differ only in their last bit.
- for a contradiction suppose only one codeword of maximum length. Since f₁ is prefix free we can truncate this codeword and still have a prefix free encoding => not optimal (a contradiction)
- assume f₁ has more than 2 codewords of maximum length but no 2 differ soley in their last bit. Thus we could truncate any two of them and still have a prefix free encoding => not optimal (a contradiction)
Last part of proof for ℓₘ = ℓₘ₋₁ and the codewords differing only in their last bit for an optimal prefix free encoding f* of S with ℓᵢ = |f*(sᵢ)|
By the claim C(f₁) has at least two codewords sᵢ and sⱼ such that f₁(sᵢ) and f₁(sⱼ) have maximum length and differ only in their last bit. By a) f(sₘ) = f(sₘ₋₁) have maximum length. Thus b) is satisfied. By reassigning the codewords f₁(sᵢ) and f₁(sⱼ) to f(sₘ) = f(sₘ₋₁) respectively we can ensure c) also holds.
Assumption for contradiction in proof of ℓ₁≤…≤ℓₘ
|f₁(sᵢ)|>|f₁(sᵢ₊₁)|
𝔼(ℓ(f₂)) =
proof of ℓ₁≤…≤ℓₘ
= sum over all k∈[m] pₖ|f₂(sₖ)|
= sum over all k∈[m] pₖ|f₁(sₖ)| - pᵢ|f₁(sᵢ)| + pᵢ|f₂(sᵢ)| - pᵢ₊₁|f₁(sᵢ₊₁)| + pᵢ₊₁|f₂(sᵢ₊₁)|
= 𝔼(ℓ(f₁)) - (pᵢ-pᵢ₊₁)(|f₁(sᵢ)| - |f₁(sᵢ₊₁)| )
claim in proof for ℓₘ = ℓₘ₋₁ and the codewords differing only in their last bit for an optimal prefix free encoding f* of S with ℓᵢ = |f*(sᵢ)|
the code associated with the encoding of f₁ has two codewords of maximum length which differ only in their last bit.
ℓᵢ in upperbound of shannons noiseless encoding theorem
let ℓᵢ be the smallest integer s.t. pᵢ≥2^-ℓᵢ
