Communication Chapter 3 - ideas of proofs

Question 1

idea of proof for t-error-detecting iff dₕ(C)≥t+1 =>

Answer 1

• Assume C is t-error-detecting
• for a contradiction suppose dₕ(c,c’)≤t
• if c is sent and ≤t errors are made then c’ is recieved and no error is detected (a contradiction)

Question 2

idea of proof for t-error-correcting iff dₕ(C)≥2t+1 =>

Answer 2

• Assume C is t-error-correcting
• Assume for a contradiction dₕ(c,c’)≤2t
• case 1: d is even. define x such that the hamming distance between x and c and x and c’ is the same (d/2). If c is sent but x is received at most t errors have occurred however the minimum distance decoding is ambiguous (contradiction)
• case2:d is odd. define x s.t. that hamming distance between c and x is equal to the hamming distance between c’ and x plus one which is equal to d+1/2. As d is odd and d<=2t we know d<=2t-1 so (d+1)/2<=v. So if c is transmitted and x is recieved then at most t errors have occured but a minimum distance decoding rule would decode x and c’. (a contradiction).

Question 3

idea of proof for t-error-detecting iff dₕ(C)≥t+1 <=

Answer 3

• Assume dₕ(C)≥t+1
• then for all c is c is sent and ≤t errors occurs then what is received is not in c so we can identity an error has been made.

Question 4

idea of proof for t-error-correcting iff dₕ(C)≥2t+1 <=

Answer 4

• Assume dₕ(C)≥2t+1
• suppose at most t errors are made i.e. dₕ(c,x)≤t
• consider any other codeword c’ and look at the hamming distance between c and c’. By the triangle inequality and the two assumptions above we can see c’ is further from x than c is to x => dₕ(c’,x)≥t+1.
• Therefore a minimum distance decoding satisfies h(xc as required.

Question 5

first step in t-error-detecting => dₕ(C)≥t+1

Answer 5

Assume C is t-error-detecting. Suppose for a contradiction that the minimum hamming distance is less than or equal to t.

Question 6

first step in t-error-correcting=> dₕ(C)≥2t+1

Answer 6

Assume C is t-error-correcting. Suppose for a contradiction that the minimum hamming distance is less than or equal to 2t.

Question 7

case 1 in t-error-correcting=> dₕ(C)≥2t+1

Answer 7

d is even

Question 8

case 2 in t-error-correcting=> dₕ(C)≥2t+1

Answer 8

d is odd

Question 9

d in t-error-correcting=> dₕ(C)≥2t+1

Answer 9

d:= dₕ(c,c’)≤2t

Question 10

proof of case 1 in t-error-correcting=> dₕ(C)≥2t+1

Answer 10

d is even.
define x to be the halfway point between c and c’ (i.e. the hamming distance is d/2).
If c is sent but x is received at most t errors have occurred however the minimum distance decoding is ambiguous (contradiction)

Question 11

proof of case 2 in t-error-correcting=> dₕ(C)≥2t+1

Answer 11

d is odd.
There exists and x∈{0,1}ⁿ such that dₕ(c,x)=dₕ(c’,x)+1=(d+1)/2 since d is odd and d≤2t.
if c is sent and x is received then at most t errors have occurred but the minimum distance decoding rule will not decode x into c as dₕ(c,x)>dₕ(c’,x) and c’∈C. A contradiction.

Question 12

What is used in the proof t-error-correcting <= dₕ(C)≥2t+1

Answer 12

Triangle inequality

Question 13

when show t-error-________ => dₕ(C)≥

Answer 13

contradiction

Question 14

when show t-error-________ <= dₕ(C)≥

Answer 14

direct proof