Communication - Chapter 5 - ideas of proofs Flashcards
Idea of proof for proposition 5.5. an optimal (n,d)-code always contains (0….0)
- 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
idea of proof for proposition 5.11 (i) dₕ(Cbar) is even.
- 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.
idea of proof for proposition 5.11 (ii) If dₕ(C) is odd then dₕ(Cbar) = dₕ(C) + 1.
- 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
idea of proof of theorem 5.12. If d is odd then A(n,d)=A(n+1,d+1).
- 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)
idea of proof for sphere packing bound. For 1≤d≤n we have A(n,d)≤2ⁿ/bⁿ⌊ₔ₋₁/₂⌋.
- 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.
idea of proof for plotkins bound. For 1≤d≤n with 2d>n we have A(n,d)≤2d/2d-n
- 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.
aim in the sphere packing bound proof.
Show that |C|≤2ⁿ/bⁿₜ
aim in the plotkins bound proof
Show that |C|=m≤2d/2d-n
indicator function
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
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’)=∅
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.
S in proof of plotkins bound
S = the sum over i,j from 1 to m of dₕ(cᵢ,cⱼ)
For c,c’ in C where dₕ(c,c’)≥d then the S in plotkins bound becomes
(LOWER BOUND ON S)
S≥ sum of i,j from 1 to m of d = (m choose 2) d
indicator function in words
plotkins
returns 1 if the inputs are not equal and 0 if the inputs are equal
First part of the upper bound on S in plotkins bound
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)
lₖ in plotkins bound
For a given kϵ[n] let lₖ be the number of 0s in the kth bit of the codewords in C.
For the upper bounds on S in plotkins bound we write
(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)
maximal
A prefix free code C is maximal if for non-empty x which isn’t in C then CU{x} is not prefix free.
prove If d is odd then A(n,d)≤A(n+1,d+1)
Upperbound on A(n,d)
- 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)
prove If d is odd then A(n,d)≥A(n+1,d+1)
prove a lower bound on A(n,d)
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)
Set up of sphere packing bound proof
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.
2ⁿ = |{0,1}ⁿ|≥
in sphere packing bound proof
2ⁿ = |{0,1}ⁿ|≥ the sum over all c in C of the size of the hamming balls
Set up of plotkins proof
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ⱼ)
When a code is maximal lₖ=
proof of plotkins proof
lₖ=m/2
lₖ in plotkins bound
For a given kϵ[n] let lₖ be the number of 0s in the kth bit of the codewords in C.
The number of strings that differ from x in exactly i position is
The number of strings that differ from x in exactly i position is n choose i.
dₕ(Cbar)≤ dₕ(C)+1
clearly for all c₁,c₂ϵC then dₕ(c₁bar,c₂bar)≤dₕ(c₁,c₂)+1.
dₕ(Cbar)≥dₕ(C)+1
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
