Demonstration min(LD columns) is minimum distance

35 Views Asked by At

$\newcommand{\code}{\mathcal{C}}$ $\newcommand{\vetor}[1]{\boldsymbol{#1}}$ $\newcommand{\gf}{\mathbb{F}_2}$ $\newcommand{\parityCheckMatrix}{\textsf{H}}$ $\newcommand{\generatorMatrix}{\textsf{G}}$

I am trying to prove the next theorem about linear codes using by own words. Could you help me please to verify if this is correct?

Theorem Let $\code$ be a linear code with parity matrix $\parityCheckMatrix$ and $s$ the minimum number of linearly dependent columns in $ \parityCheckMatrix $, then $s$ is the minimum distance of the code.

Proof

Let $d$ be the minimum distance of $\code$ and let $\vetor{x}= (x_1, \cdots x_s, 0, \cdots, 0)$ $\in \code$ where $x_i \neq 0 $ in the range $1 \leq i \leq s$. Obviously, $s$ can not be less than $d$, because otherwise $s$ must be the minimum distance of the code. It remains to prove that $s$ can not be greater than $d$. Let $\vetor{y} = (y_1, \cdots y_d, 0,0, \cdots, 0) \in C$, with $y_i \neq 0$ in range $ 1 \leq i \leq d$. Since $\vetor{y} \in \code$ then $\parityCheckMatrix\vetor{y}=0$, that is, we have found $d$ linearly dependent columns. Now $s$ can not greater than $d$ because this violates the hypothesis: $s$ is the minimum number of linearly dependent columns in $ \parityCheckMatrix$