Communication - chapter 4 - defs and theorems

Question 1

Hamming ball

Answer 1

Let 0≤k≤n and x∈{0,1}ⁿ. The balls of radius k centered at x is the set of points {0,1}ⁿ at Hamming distance at most k from x. That is,
Bⁿₖ(x) = {y∈{0,1}ⁿ: dₕ(x,y)<=k}

Question 2

Proposition 4.2. Size of hamming ball.

Answer 2

For any 0≤k≤n and any x∈{0,1}ⁿ we have bⁿₖ=bⁿₖ(x) = sun from i=0 to k of n choose i.

Question 3

Proposition 4.3. sums and entropies.

Answer 3

For every λ∈[0,1/2] and every n∈ℕ, we have that

the sum from 0 to λn of n choose i is less than or equal to 2ᴴ⁽λ⁾ⁿ

Question 4

Proposition 4.4. Sphere Covering Bound.

Answer 4

For any 1≤d≤n, there exists a code C of length n with dₕ(C)≥d and |C|≥2ⁿ/bⁿₔ₋₁

Question 5

Theorem 4.5. Sphere Covering Bound Alternative Form.

Answer 5

For every λ∈[0,1/2] and every n∈ℕ, there exists a code C of length n with dₕ(C)≥λn and |C|≥2⁽¹⁻ᴴ⁽λ⁾⁾ⁿ i.e., R(C) ≥ 1 -H(λ)

Question 6

Shannons noisy encoding theorem.

Answer 6

Given any p∈[0,1/2) and ε∈(0,1/2-p], there exists n₀=n₀(p,ε) s.t. if n≥n₀ then there exists a code C of length n, the probability of error is less than epsilon and R(C)>= 1- H(P+ε)

Question 7

Theorem. (looser version of shannons theorem)

Answer 7

Given any p∈[0,1/4) and ε∈(0,1/2-2p], there exists n₀=n₀(p,ε) s.t. if n>n₀ then there exists a code C of length n, with probability of error less than epsilon and R(C)>=1-H(2p+ε)