Communication chapter 4 - ideas of proofs

Question 1

idea of proof for proposition. bⁿₖ(x) = sun from i=0 to k of n choose i.

Answer 1

The number of strings that differ from x in exactly i position is n choose i. So the sum of this over all i from 0 to k gives the number of values in the hamming ball by definition.

Question 2

idea of proof for proposition. the sphere covering bound.

Answer 2

• Construct C greedily by choosing codewords.
• Let C₀=∅ and V₀={0,1}ⁿ
• At each step choose and arbitrary codeword add it to C and remove its hamming ball from V.
• repeat until V is empty i.e. repeat S times. Then rearrange the equation for the size of the set V.

Question 3

idea of proof for theorem 4.5. Code of length n with minimum hamming distance λn has size |C|≥2⁽¹⁻ᴴ⁽λ⁾⁾ⁿ

Answer 3

• Let d=⌈λn⌉
• use (bⁿₖ(x) = sum from i=0 to k of n choose i ) and (the sum from i=0 to λn of (n choose i) is less than or equal to 2 to the power of H(λ)n) to get bⁿₔ₋₁≤2ᴴ⁽λ⁾ⁿ
• by sphere covering bound we have the result

Question 4

First step in proof of sphere covering bound

Answer 4

Choose c₁∈C₀ arbitrarily.
Set C₁={c₁} and V₁=V₀\Bⁿₔ₋₁ this means we are no longer able to select something from Bⁿₔ₋₁ to maintain the minimum distance.
|V₁|=2ⁿ-bⁿₔ₋₁

Question 5

second step in sphere covering bound

Answer 5

Choose c₂∈C₁ arbitrarily. Since dₕ(c₁,c₂)≥d then C₂={c₁,c₂} satisfies dₕ(C₂)≥d.
If V₂=V₂\Bⁿₔ₋₁ then |V₂|≥2ⁿ-2bⁿₔ₋₁

Question 6

general step in sphere covering bound

Answer 6

In general on the ith step suppose Cᵢ₋₁={c₁,..,cᵢ₋₁} where dₕ(Cᵢ₋₁)≥d and Vᵢ₋₁⊆{0,1}ⁿ is the set of all strings of distance ≥d from every codeword in Cᵢ₋₁.
Then choose cᵢ∈Vᵢ₋₁ arbitrarily so Cᵢ=ᵢ₋₁U{cᵢ} and dₕ(cᵢ)≥d. Set Vᵢ= Vᵢ₋₁\Bⁿₔ₋₁(cᵢ) so |Vᵢ|≥|Vᵢ₋₁|-bⁿₔ₋₁=2ⁿ-ibⁿₔ₋₁

Question 7

final step in sphere covering bound

Answer 7

repeat the general process until Vᵢ=∅

Then let s be the smallest integer such that Vₛ=∅ and write |Vₛ|=2ⁿ-sbⁿₔ₋₁. Rearrange for s note |Vₛ|=0.

Question 8

set up of proof of sphere covering bound

Answer 8

• Construct C greedily by choosing codewords.

- Let C₀=∅ and V₀={0,1}ⁿ

Question 9

|Vₛ| in proof of sphere covering bound

Answer 9

<= 2ⁿ-sbⁿₔ₋₁

i.e. 2 to the power of n minus s times the size of the hamming ball with radius k (and codeword length n)