Communication - Chapter 5 - ideas of proofs

Question 1

Idea of proof for proposition 5.5. an optimal (n,d)-code always contains (0….0)

Answer 1

• Let C₀ be an optimal (n,d)-code
• Let c₀ϵC₀ and consider the code C := C₀ + c₀
• Then C is also an optimal (n,d)-code (C has the same size as C₀, C has length n, C has minimum distance d)
• Also, (00…0) = c₀ + c₀ ϵC

Question 2

idea of proof for proposition 5.11 (i) dₕ(Cbar) is even.

Answer 2

• for c₁,c₂ϵC note c₁bar,c₂bar have even weight

- by our equation for dₕ we get that dₕ(c₁bar,c₂bar) is a sum of even terms, so we have dₕ(Cbar) is even.

Question 3

idea of proof for proposition 5.11 (ii) If dₕ(C) is odd then dₕ(Cbar) = dₕ(C) + 1.

Answer 3

• suppose dₕ(C) is odd.
• Let c₁, c₂ be in C.
• (one side of inequality) since dₕ(C) is odd then dₕ(Cbar) = dₕ(c₁bar,c₂bar) ≤ dₕ(c₁,c₂) + 1 so dₕ(Cbar)≤ dₕ(C) + 1.
• (other side of inequality) if dₕ(c₁,c₂) = dₕ(Cbar) by (i) we know dₕ(Cbar) is even the parity check only increases the hamming distance so dₕ(c₁bar,c₂bar)≥dₕ(c₁,c₂)+1=dₕ(C)+1
  if dₕ(c₁,c₂) > dₕ(Cbar) then dₕ(c₁bar,c₂bar)≥dₕ(c₁,c₂)≥dₕ(C)+1. So dₕ(Cbar)≥dₕ(C)+1

Question 4

idea of proof of theorem 5.12. If d is odd then A(n,d)=A(n+1,d+1).

Answer 4

• Let C be an optimal (n,d)-code
• If dₕ(d)=d then since d is odd by previous result we have Cbar is an (n+1, d+1)-code. As |Cbar|=|C|=A(n,d) => A(n+1,d+1)≥A(n,d)
• Suppose C is an optimal (n+1,d+1)-code. Consider C(1). dₕ(C(1))≥dₕ(C)-1. Since d+1≥2=>|C*(1)|=|C|=A(n+1,d+1) => A(n,d)≥A(n+1,d+1)

Question 5

idea of proof for sphere packing bound. For 1≤d≤n we have A(n,d)≤2ⁿ/bⁿ⌊ₔ₋₁/₂⌋.

Answer 5

• Let c be an (n,d)-code and let t:=⌊(d-1)/2⌋.
• Given any c₁,c₂ϵC we have dₕ(c₁,c₂)≥d thus the hamming balls are distinct (show true with contradiction for an element in both balls, triangle inequality)
• it follows that 2ⁿ = |{0,1}ⁿ|≥ the sum over all c in C of the size of the hamming balls. Rearrange.

Question 6

idea of proof for plotkins bound. For 1≤d≤n with 2d>n we have A(n,d)≤2d/2d-n

Answer 6

• Let C be an arbitrary (n,d)-code of size m and C={c₁,c₂,..,cₘ}
• Set S = the sum over i,j from 1 to m of dₕ(cᵢ,cⱼ)
• work out a lower bound for S
• work out an upper bound for S (in terms of the indicator function and lₖ)
• Manipulate these bounds and rearrange for m.

Question 7

aim in the sphere packing bound proof.

Answer 7

Show that |C|≤2ⁿ/bⁿₜ

Question 8

aim in the plotkins bound proof

Answer 8

Show that |C|=m≤2d/2d-n

Question 9

indicator function

Answer 9

1(cᵢₖ≠cⱼₖ)= {1 if cᵢₖ≠cⱼₖ, 0 if cᵢₖ=cⱼₖ

i.e. returns 1 if the inputs are not equal and 0 if the inputs are equal

Question 10

Show that the hamming balls of two points in C an (n,d)-code are disjoint (proof of sphere packing bound).

Given and c,c’ϵC we have dₕ(c,c’)≥d we have Bⁿₜ(c)∩Bⁿₜ(c’)=∅

Answer 10

Indeed if not there exists a zϵBⁿₜ(c)∩Bⁿₜ(c’) and since C is an (n,d)-code we have d≤dₕ(c,c’)≤dₕ(c,z)+dₕ(c’,z)≤t+t≤d-1 a contradiction.

Question 11

S in proof of plotkins bound

Answer 11

S = the sum over i,j from 1 to m of dₕ(cᵢ,cⱼ)

Question 12

For c,c’ in C where dₕ(c,c’)≥d then the S in plotkins bound becomes

(LOWER BOUND ON S)

Answer 12

S≥ sum of i,j from 1 to m of d = (m choose 2) d

Question 13

indicator function in words

plotkins

Answer 13

returns 1 if the inputs are not equal and 0 if the inputs are equal

Question 14

First part of the upper bound on S in plotkins bound

Answer 14

We can write dₕ(cᵢ,cⱼ)= sum from k=1 to n of (the indicator function of (cᵢₖ≠cⱼₖ)) where cᵢₖ is the kth bit of cᵢ and 1(cᵢₖ≠cⱼₖ)= {1 if cᵢₖ≠cⱼₖ, 0 if cᵢₖ=cⱼₖ
(then we can substitute this into S)

Question 15

lₖ in plotkins bound

Answer 15

For a given kϵ[n] let lₖ be the number of 0s in the kth bit of the codewords in C.

Question 16

For the upper bounds on S in plotkins bound we write

Answer 16

(after substituting the indicator function in for the hamming distance)
S = sum from k=1 to n of the sum over i,j from 1 to m of the indicator function of (c ≠ c’)
Now where lₖ is the number of 0s in the kth bit on the codewords in C.
= lₖ(m-lₖ)n
= m²n/4 (since lₖ=m/2)

Question 17

maximal

Answer 17

A prefix free code C is maximal if for non-empty x which isn’t in C then CU{x} is not prefix free.

Question 18

prove If d is odd then A(n,d)≤A(n+1,d+1)

Upperbound on A(n,d)

Answer 18

• Let C be an optimal (n,d)-code
• If dₕ(c,c’)>d => Cbar is an (n+1,d+1)-code
• If dₕ(c,c’)=d then since d is odd by previous result we have Cbar is an (n+1, d+1)-code.
• As |Cbar|=|C|=A(n,d) => A(n+1,d+1)≥A(n,d)

Question 19

prove If d is odd then A(n,d)≥A(n+1,d+1)

prove a lower bound on A(n,d)

Answer 19

Suppose C is an optimal (n+1,d+1)-code. Consider C(1) (write def of this => length (n-1)+1). Since d+1≥2=>|C(1)|=|C|=A(n+1,d+1)
Moreover, dₕ(C(1))≥dₕ(C)-1
Since d+1≥2=>|C(1)|=|C|=A(n+1,d+1)
Thus C(1) is an (n,d)-code with |C(1)|=A(n+1,d+1) =>A(n,d)≥A(n+1,d+1)

Question 20

Set up of sphere packing bound proof

Answer 20

Let C be an (n,d)-code and t = floor (d-1/2). Then if x,y in C where x/=y the intersection of their hamming balls is empty.

Question 21

2ⁿ = |{0,1}ⁿ|≥

in sphere packing bound proof

Answer 21

2ⁿ = |{0,1}ⁿ|≥ the sum over all c in C of the size of the hamming balls

Question 22

Set up of plotkins proof

Answer 22

Let C be an arbitrary (n,d)-code of size m and C={c₁,c₂,..,cₘ}.
We must show that m≤2d/2d-n.
We do this by providing a specific quantity and providing upper bounds and lower bounds on the following quantity:
S = the sum over i,j from 1 to m of dₕ(cᵢ,cⱼ)

Question 23

When a code is maximal lₖ=

proof of plotkins proof

Answer 23

lₖ=m/2

Question 24

lₖ in plotkins bound

Answer 24

For a given kϵ[n] let lₖ be the number of 0s in the kth bit of the codewords in C.

Question 25

The number of strings that differ from x in exactly i position is

Answer 25

The number of strings that differ from x in exactly i position is n choose i.

Question 26

dₕ(Cbar)≤ dₕ(C)+1

Answer 26

clearly for all c₁,c₂ϵC then dₕ(c₁bar,c₂bar)≤dₕ(c₁,c₂)+1.

Question 27

dₕ(Cbar)≥dₕ(C)+1

Answer 27

Let c₁,c₂ϵC

• if dₕ(c₁,c₂)=dₕ(C) then dₕ(c₁bar,c₂bar)≥dₕ(c₁,c₂)+1=dₕ(C)+1
• if dₕ(c₁,c₂)≥dₕ(C) then dₕ(c₁bar,c₂bar)≥dₕ(c₁,c₂)≥dₕ(C)+1