Communication Chapter 6 ideas of proofs

Question 1

idea of proof for lemma 6.2. dₕ(x,y)=w(x+y).

Answer 1

Given any x,y∈𝔽ⁿ₂, x+y has 1 in a position where x and y differ and a 0 in the position where x and y are the same (by definition of addition). So the weight of x+y = # places where x and y differ = dₕ(x,y)

Question 2

idea of proof for minimum hamming distance of C is the minimum weight of a codeword c∈C

Answer 2

For x,y∈C s.t. dₕ(x,y)=dₕ(C) we know x/=y and x+y/=0.
Thus dₕ(C)=dₕ(x,y)=w(x+y)≥ min weight of c∈C (since x+y∈C)
Let c’∈C s.t. w(c’) = min weight of c∈C. Since 0∈C and by dₕ(x,y)=w(x,y) we have
min weight of c∈C = w(c’) = w(c’ + 0) = dₕ(c’,0) ≥ dₕ(C)

Question 3

Idea of proof for theorem 6.18 [upperbound] dₕ(c)≤ r

If r is the smallest integer for which there exists r linearly dependent columns in H, then dₕ(c)=r

Answer 3

• consider a collection of the columns of H that form a linearly dependent set since r is the smallest possible integer we have hᵢ₁+…+ hᵢᵣ = 0 (*)
• Let c be the vector with 1s in positions i₁,…,iᵣ and 0s otherwise. Thus w(c)=r.
• rewrite equation (*) as Hcᵀ=0 which implies c is part of the code C.
• by previous result dₕ(c)= min w(c’) ≤ w(c) = r

Question 4

Idea of proof for prop 6.21 (i) n = 2ʳ-1 (length of codewords) k= 2ʳ-r-1 (dimension of codewords)

Answer 4

By defn of hamming code of order r, its parity check matrix H has r rows and 2ʳ-1 columns. Since H has size (n-k)xn where n is length and k is dimension we can rearrange to get the answer.

Question 5

Idea of proof for prop 6.21 (ii) |C|=2²ʳ⁻ʳ⁻¹ and R(C) = 1 - r/(2ʳ-1)

Answer 5

By applying lemma 6.7 |C|=2ᵏ we get the first part.

Then applying the definition R(C)=log|C|/n we get the second part.

Question 6

Idea of proof for prop 6.21 (iii) dₕ(C)=3

Answer 6

• Indeed H has no all zero columns and no 2 columns are identical.
• On the other hand any two columns in H summed together equals another columns because all possible columns are present.
• So 3 is the smallest size of a linearly dependent set of columns in H. So by previous theorem we compute dₕ(c)

Question 7

idea proof for prop 6.22. There is always a codeword distance at most 1 from the string.

Answer 7

• if the string is in C the the statement holds trivially.
• if the string is not in C then by defn of parity check matrix we have Hxᵀ = s with s not equal to 0.
• Note as H contains all possible non zero vectors of length r there exists an i s.t. s=hᵢ.
• Set c=x+eᵢ. Show c is in C (start with 0=hi+hi) and that dₕ(c,x)=1 (use hamming distance (between c and x) weight).
• Moreover, the choice of c in both cases is unique otherwise contradiction to dₕ(C)=3
• Finally to show the moreover part we note Hxᵀ = H(c+eᵢ)ᵀ= Hcᵀ+Heᵢᵀ = 0+hᵢ

Question 8

idea of proof for theorem 6.27. Minimum distance decoding.
If q(s) is a coset leader of Q(s) then c=x+q(s)∈C and c is the nearest codeword to x

Answer 8

1. since x and q(s) are in the code we know x+q(s) is in the code.
2. Assume for a contradiction there exists a codeword that is closer to x.
3. Use hamming distance/weight result and the definition of x to show that the weight of c’+x is less than the weight of the coset leader.
4. Show c’+x is in Q(s)
5. this is a contradiction since coset leader have smallest possible weight

Question 9

Idea of proof for theorem 6.18. [lowerbound] dₕ(C)≥r

If r is the smallest integer for which there exists r linearly dependent columns in H, then dₕ(c)=r

Answer 9

• Let c’ be in the code C s.t. w(c’)=dₕ(C), which exists by a previous result. we know H(c’)ᵀ=0 as c’ is an element of the code.
• write s=w(c’)
• If j₁,..,jₛ are the positions of c’ that are 1s then note H(c’)ᵀ=0 is precisely saying hⱼ₁+…+ hⱼₛ=0. I.e., these s columns are linearly dependent. Thus dₕ(C) = w(c’)=s≥r

Question 10

Set up of proof for theorem 6.18.

If r is the smallest integer for which there exists r linearly dependent columns in H, then dₕ(c)=r.

Answer 10

Let h₁,…,hₙ be the columns of H

Question 11

eᵢ

Answer 11

Let eᵢ be the vector that is zero everywhere except the ith position.

Question 12

proof of There is always a unique codeword in a hamming code distance at most 1 from the string first line

Answer 12

if x is in the code then we set c=x and triviallt their hamming distance is 0.

Question 13

proof of There is always a unique codeword in a hamming code distance at most 1 from the string. Uniqueness.

Answer 13

The choice of c is always unique else one would obtain a contradiction to the minimum hamming distance of the code being 3.

Question 14

SHow the moreover part in proof of There is always a unique codeword in a hamming code distance at most 1 from the string.

“Moreover is x is not in C and i is the position where x and c differ then Hxᵀ=hᵢ where hᵢ is the ith column in H”

Answer 14

Hxᵀ = H(c+eᵢ)ᵀ= Hcᵀ+Heᵢᵀ = 0+hᵢ

Question 15

If j₁,..,jₛ are the positions of c’ that are 1s then note H(c’)ᵀ=0 is precisely saying….

(proof of dₕ(C)≥r )

Answer 15

hⱼ₁+…+ hⱼₛ=0. I.e., these s columns are linearly dependent.

Question 16

c∈𝔽ⁿ₂ for proving dₕ(C) is at most r

Answer 16

Let c∈𝔽ⁿ₂ be the vector with 1s in positions i₁,…,iᵣ and 0s otherwise.

Question 17

c’∈C for proving dₕ(C) is at least r

Answer 17

Let c’∈C s.t. w(c’)=dₕ(C), which exists by a previous result.

Question 18

Two main things to show contradiction (there exists a codeword c' which is closer to x than c):
If q(s) is a coset leader of Q(s) then c=x+q(s)∈C and c is the nearest codeword to x

Answer 18

• w(c’+x) < w(q(s))

- Show c’+x ∈ Q(s) calculate H(c’+x)ᵀ

Question 19

Show c=x+eᵢ is in C

Proof of There is always a codeword distance at most 1 from the string.

Answer 19

0 = hᵢ + hᵢ = s + hᵢ = Hxᵀ + Heᵢᵀ = H(x+eᵢ)ᵀ => c=x+eᵢ∈C

Question 20

Show c=x+eᵢ has hamming distance 1 from x

Proof of There is always a codeword distance at most 1 from the string.

Answer 20

dₕ(x,c)=dₕ(x,x+eᵢ)=w(x+x+eᵢ)=w(eᵢ)=1

Question 21

if x∉C then…

Answer 21

By the definition of parity check matrix we have Hxᵀ=s∈𝔽ʳ₂. Since H contains all vectors of length r s=hᵢ.