Question

Let C be a linear code with parity-check matrix H. Prove that C corrects single errors if and only if the rows of H are distinct and nonzero.

Short answer

It has been proved that C corrects single errors if and only if the rows of H are distinct and nonzero.

Step-by-step solution

Theorem used

Theorem 16.9: Let C be an$〈n,k〉$code with standard generator matrix G and parity check matrix H. Then an element w in $B\left(n\right)$is a codeword if and only if $wH=0$

Given that

Given that C is a linear code with parity check matrix H.

Proof

Now, C corrects single errors if and only if every nonzero$u\in C$ has $Wt\left(u\right)\ge 3$.

This implies if$u\ne 0$ and$Wt\left(u\right)\le 2$ then $u\notin C$.

According to Theorem 16.9,

If$Wt\left(u\right)=1$ or 2 then $uH\ne 0$.

Let$r_1,\mathrm{...}{r}_n$ be the rows of parity check matrix H.

If $Wt\left(u\right)=1$ then $u=e_i$for some iand thus $uh=r_i$.

If$Wt\left(u\right)=2$ then $u=e_i+e_j$for some indices $i\ne j$.

This implies $uH=r_i+r_j$.

Therefore Ccorrects single errors if and only if$r_i\ne 0$ and $r_i\ne r_j$for every $i\ne j$.

This implies, the rows of Hare nonzero and distinct.

Hence, C corrects single errors if and only if the rows of H are distinct and nonzero.