Communication - Chapter 1 - Idea of proofs

Question 1

Idea of proof for instantaneous => prefix free

Answer 1

• suppose C is instantaneous
• suppose for a contradiction C is not prefix free that is there exists c=x₁…xₗ∈C and c’=x₁…xₗy∈C where y∈{0,1}* is a non-empty string.
• if c is received one doesn’t immediately know if it was c that was sent or if one should wait for further bits to decode as c’.
• so c is not instantaneous, a contradiction

Question 2

Idea of proof for prefix free => instantaneous

Answer 2

• suppose C is prefix free
• suppose c=x₁…xₗ is transmitted
• as c is not a prefix of another codeword as soon as the last bit xₗ is received we can identify it as c
• (hence instantaneous)

Question 3

Idea of proof for instantaneous = > uniquely decipherable

Answer 3

• Suppose C is instantaneous, consider any string in {0,1}.
• Since C is instantaneous every time we receive the last bit of a codeword we can unambiguously identify it.
• Thus there is at most one was to decode the string into codewords of C.

Question 4

Idea for proof of code associated to binary tree with m leaves is prefix free and of size m

Answer 4

• Let T be an edge-labelled binary tree with m leaves and root r.
• By definition C has size m
• Suppose for a contradiction C is not prefix-free. Then c is a prefix of c’ (write out full def).
• Let P1 be the path in T obtained by starting at r and following the edge and in the ith step we follow the edge labelled xᵢ. Let P2 be the same for c’.
• P2 must follow P1 precisely but then continues onto other edges. So P1 doesn’t contain a leaf, a contradiction.

Question 5

Idea of proof for tree associated to prefix-free code of size m has m leaves

Answer 5

• T has at most m leaves (since each path contains at most one leaf and there are as many paths as codewords)
• suppose for a contradiction T has at most m-1 leaves
• let the vᵢ’s be the end points of the paths Pᵢ which correspond to the codeword cᵢ
• case 1: the end points of the paths are all leaves. by the pigeonhole principle there exists i,j∈[m] with i≠j such that vᵢ = vⱼ. By the construction of the associated tree, this implies that Pᵢ = Pⱼ. So, cᵢ = cⱼ, a contradiction.
• case 2: vi isn’t a leaf in T. Let vj be the leaf in the subtree of T rooted at vi. Then Pi is a subset of Pj => ci is a prefix of cj (show by definition of prefix), a contradiction.

Question 6

idea of proof for McMillans Theorem

Answer 6

• Define Tₗ to be an edge-labelled binary tree where
  (i) every non-leaf vertex has precisely two children
  (ii) leaves are at a distance l from the root r.
• Consider the associated tree T of C. T is a subtree of Tₗ.
• Let Vᵢ be the set of leaves in Tₗ that live in the subtree of Tₗ rooted at vᵢ
• As vᵢ has depth lᵢ => |Vᵢ|= 2ˡ⁻ˡi
• further if i/=j then Vᵢ∩Vⱼ = ∅ as vᵢ,vⱼ are leaves in T
• so the sum of the size of Vᵢ s are equal to the size of the union of Vᵢs
• as Tₗ has 2ˡ leaves we can rearrange and multiply by 2⁻ˡ we get the result.

Question 7

idea of proof for Krafts theorem

Answer 7

• aⱼ is the number of indices i in 1 to m s.t. lᵢ=j
• first prove aⱼ ≤ 2ʲ - 2ʲ⁻¹a₁ - … - 2aʲ⁻¹
• Now construct aⱼ codewords of length j:
• > assume aₖ codewords of length k∈[j-1] already constructed
• > a string of length k is a prefix of 2ʲ⁻ᵏ strings of length j. Hence there are most a₁2ʲ⁻¹ + a₂2ʲ⁻² + … + aⱼ₋₁2 (**) strings you can’t select in the jth step.
• > so 2ʲ - (**) good choices this is ≥ aⱼ
• > which means that we can select aⱼ codewords of length j and add them to the code we are constructing while preserving the prefix-free property

Question 8

aⱼ in krafts theorem

Answer 8

the number of codewords that will be produced by the theorem that have length j

Question 9

First aim in krafts theorem

Answer 9

prove aⱼ ≤ 2ʲ - 2ʲ⁻¹a₁ - … - 2aⱼ₋₁

(i.e., prove an upper bound on aⱼ

Question 10

Tₗ in proof of mcmillans theorem

Answer 10

An edge labelled binary tree where

(1) Every non-leaf vertex had precisely two children
(2) Leaves are at distance l from the root

Question 11

number of strings of length j you cannot select in the jth step of constructing a prefix free code. (krafts theorem)

Answer 11

2ʲ⁻¹a₁ +… + 2aⱼ₋₁
i.e. 2ʲ⁻ᶦ=number of strings of length i that are a prefix of strings of length j multiplied by the number of codewords of length i for each i.

Question 12

maximum number of strings of length j a string of length k is a prefix of (krafts theorem)

Answer 12

2ʲ⁻ᵏ

Question 13

prove aⱼ ≤ 2ʲ - 2ʲ⁻¹a₁ - … - 2aⱼ₋₁ (krafts theorem)

Answer 13

• write the hypothesis in terms of aⱼs
  the sum from k=1 to l of aₖ2⁻ᵏ ≤ 1
• now given j≤l and by the definition of aₖ we know that the sum from k=1 to j of aₖ2⁻ᵏ ≤ 1
• multiply by 2ʲ to get that the sum from k=1 to j of aₖ2ʲ⁻ᵏ≤2ʲ
• rearrange for aⱼ to get aⱼ ≤ 2ʲ - 2ʲ⁻¹a₁ - … - 2aⱼ₋₁

Question 14

What is the size of the union from i=1 to m of all Vᵢ (Mcmillans Theorem)

Answer 14

As T₁ has 2ˡ leaves we have the size of the union from i=1 to m of all Vᵢ ≤ 2ˡ

Question 15

Vᵢ (Mcmillans theorem)

Answer 15

The set of leaves in Tₗ that live in the subtree of Tₗ rooted at vᵢ where vᵢ is the leaves in T

Question 16

|Vᵢ| (Mcmillans theorem)

Answer 16

As vᵢ has depth lᵢ and each vertex has 2 children => |Vᵢ| = 2ˡ⁻ˡᶦ

Question 17

Set up of krafts proof

Answer 17

Let aⱼ be the number of incidences of lᵢ=j for all i in [m].

Set l:= max over all i in [m] of lᵢ.

Question 18

constructing the code sequentiall step in krafts theorem

Answer 18

We will now construct out desired code sequentially, that is, in the jth step j∈[l], after we have constructed aₖ codewords of length k for each k∈[j-1] we construct aⱼ codewords of length j.
We need to do this so the resulting code is prefix free. Consider the jth step.

Question 19

l in proof of Mcmillans Theorem

Answer 19

Let l=max over all i in [m] of lᵢ be the length of the longest codeword in C.

Question 20

T is a…

Mcmillans proof

Answer 20

subtree of Tₗ with the same root.

Question 21

By a result in the lecture notes we know T has…

Mcmillans Proof

Answer 21

m leaves vₗ,..,vₘ corresponding to the codewords cₗ,..,cₘ in C.