Question

Complete the proof of Theorem 16.2 by showing that if a code corrects errors, then the Hamming distance between any two codewords is at least $2t+1$. [Hint: If u, v are codewords with $d\left(u,v\right)⩽2t$, obtain a contradictionby constructing a word w that differs from u in exactly t coordinates and from v in tor fewer coordinates; see Exercise 14.]

Short answer

It is proved that if a code corrects t errors, then the Hamming distance between any two codewords is at least $2t+1$

Step-by-step solution

Lemma 16.1 and the result of Exercise 14

Lemma 16.1: If$u, v, w\in B\left(n\right)$

Then,

1. $d\left(u,v\right)=Wt\left(u-v\right)$
   
2. $d\left(u,v\right)⩽d\left(u,w\right)+d\left(w,v\right)$
   

Result of Exercise 14:$d\left(u,v\right)⩾t$

Proving that if a code corrects t errors, then the Hamming distance between any two codewords is at least 2t + 1

Let’s assume there exist two codewords such as that $d\left(u,v\right)⩽2t$.

According to Exercise 14$d\left(u,v\right)⩾t$

Let construct the received word W from the code word u and change 1 to 0 and vice versa, at some t coordinates on which u and v differ.

So, $d\left(u,w\right)=t$and according to Lemma 16.1,

$d\left(u,v\right)\le d\left(u,w\right)+d\left(w,v\right)\le 2t$this implies that $d\left(v,w\right)⩽t$

This contradicts that linear code corrects t errors, therefore our assumption is wrong.

Hence it is proved that if a code corrects t errors, then the Hamming distance between any two codewords is at least $2t+1$