Communication Chapter 2 - proof ideas

Question 1

idea of proof for gibbs lemma. H(P)≤ the sum from i=1 to m of pᵢ log (1/rᵢ).

Answer 1

• 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)

Question 2

Idea of of proof for theorem. 0≤H(P)≤logm.

Answer 2

[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)

Question 3

Idea of proof for Shannons Noiseless Encoding Theorem [lower bound]

Answer 3

• 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

Question 4

Idea of proof for Shannons Noiseless Encoding Theorem [upper bound]

Answer 4

• 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)

Question 5

idea of proof for ℓ₁≤…≤ℓₘ for an optimal prefix free encoding f* of S with ℓᵢ = |f*(sᵢ)|

Answer 5

• 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₁

Question 6

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ᵢ)|

Answer 6

• 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.

Question 7

log₂x =

Answer 7

log₂x = lnx/ln2

Question 8

lnx ≤

Answer 8

lnx≤x-1

Question 9

sum from i=1 to m of pᵢ

Answer 9

1

Question 10

rᵢ in the proof of shannons noiseless encoding theorem proof

Answer 10

rᵢ=2^-ℓᵢ

Question 11

why do you chose rᵢ=2^-ℓᵢ in the proof of shannons noiseless encoding theorem?

Answer 11

So that you can apply mcmillans theorem to get the hypothesis of gibbs lemma

Question 12

an encoding denoted with a subscript * is

Answer 12

optimal

Question 13

an encoding denoted with a subscript H is

Answer 13

a Huffman encoding

Question 14

pᵢ≥2^-ℓᵢ => (Shannon noiseless encoding theorem, upper bound)

Answer 14

pᵢ<2^-(ℓᵢ-1)

Question 15

Set up of shannons noiseless encoding theorem (upperbound)

Answer 15

we must construct a prefix free encoding f’ of S that satisfies the inequality: 𝔼(ℓ(f))<=𝔼(ℓ(f’))

Question 16

Set up of shannons noiseless encoding theorem (lowerbound)

Answer 16

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ᵢ.

Question 17

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ᵢ)|

Answer 17

the code associated with the encoding of f₁ has two codewords of maximum length which differ only in their last bit.

Question 18

proof of claim the code associated with the encoding of f₁ has two codewords of maximum length which differ only in their last bit.

Answer 18

• 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)

Question 19

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ᵢ)|

Answer 19

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.

Question 20

Assumption for contradiction in proof of ℓ₁≤…≤ℓₘ

Answer 20

|f₁(sᵢ)|>|f₁(sᵢ₊₁)|

Question 21

𝔼(ℓ(f₂)) =

proof of ℓ₁≤…≤ℓₘ

Answer 21

= 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ᵢ₊₁)| )

Question 22

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ᵢ)|

Answer 22

the code associated with the encoding of f₁ has two codewords of maximum length which differ only in their last bit.

Question 23

ℓᵢ in upperbound of shannons noiseless encoding theorem

Answer 23

let ℓᵢ be the smallest integer s.t. pᵢ≥2^-ℓᵢ