Let $\mathcal C$ be a $[n,k,d]$ linear binary code such that $\mathcal C$ has a systematic generator matrix $G=[I_k\mid A]$.
(i) Prove that $u\in (\mathbb F_2)^k$ is coded by $c=(u\mid uA)\in \mathcal C$. $(u\mid uA)$ is concatenation.
(ii) Suppose that $\mathcal C$ can correct $t$ errors and when transmitting $c\in \mathcal C$, an error $e$ with weight $w_H(e)\leq t$ happens, so the received message is $v=c+e$. Set $e=(e'\mid e'')$ where $e'\in \mathbb (F_2)^k$ and $e''\in (F_2)^{n-k}$. Let $s=Sd(v)$ be $v$'s syndrome.
a) Prove that if $w_h(s)\leq t$, then $e'=0, e''=s$ and $c=v-(0\mid s)$.
b) Prove that if $e'=0$, then $w_H(s)\leq t$.
I already proved (i) and (ii), b). I'm missing (ii), a).
What I have so far is this
- $d\ge 2t+1$ because $\mathcal C$ corrects $t$ errors.
- let $H=[A^T\mid I_{n-k}]$ be parity check matrix. Then $Sd(v)=vH^T=[c+e]H^T=[u+e'\mid uA+e'']\begin{bmatrix} A\\ I_{n-k}\end{bmatrix}=uA+e'A+uA+e''=e'A+e''+2uA=e'A+e''$
- since $d\ge 2t+1$, any $2t$ columns of $H$ are linearly independent
- I guess that somehow I first need to prove that $e'A=0$ and then $e'=0$ should follow. But does $e'A=0$ imply $e'=0$ here?
what I showed above are just some facts that I think might be useful, although I don't see how. I just need to prove that $e'=0$, the rest is an easy consequence.
Can someone tell me how to prove this?
let $p=(0\mid s)$. since $pH^T=s$, then $Sd(p)=Sd(v)$, so $p-v\in \mathcal C$. Since $\mathcal C$ detects $2t$ errors, then $B_{2t}(c)\cap \mathcal C=\{c\}$. But $d_H(c,v-p)=d_H(v-e, v-p)=d_H(e,p)\leq d_H(e,0)+d_H(0,p)=w_H(e)+w_H(p)\leq 2t$, so $v-p\in B_{2t}(c)\cap \mathcal C=\{c\}$. so $v-p=v-e$ and every thing follows.