0
$\begingroup$

Let $C$ be a $[n,k]$ linear Code over $\mathbb{F}_q$ .

I want to show that each vector of $\mathbb{F}_q^{n-k} $ is written as a linear combination of $m$ columns of $H$ iff $\rho \leq m$.

I have thought the following:

$$ d(C)=\min \{ d \in \mathbb{N} | \text{ there are d linearly dependent columns of H}\} $$

So $H$ has $ d-1 $ linearly independent columns , so each vector of $\mathbb{F}_q^n$ can be written as a linear combination of these columns.

But what can we say about the vectors of $ \mathbb{F}_q^{n-k}$?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Evinda, you're asking a lot of questions. Try to solve some of them yourself. $\endgroup$
    – Yuval Filmus
    Mar 23 '16 at 21:57
  • $\begingroup$ Also, what is $H$? The parity check matrix? $\endgroup$
    – Yuval Filmus
    Mar 23 '16 at 21:57
  • 2
    $\begingroup$ Are you going over an exercise sheet? Exercises are meant to help you grasp the material. If you don't grapple with them on your own, you'll have trouble later on. $\endgroup$
    – Yuval Filmus
    Mar 23 '16 at 21:58
  • 1
    $\begingroup$ However, so far all the exercises have been very standard, and covered in any textbook on the subject, so I don't feel too bad for answering them. $\endgroup$
    – Yuval Filmus
    Mar 23 '16 at 22:02
  • 2
    $\begingroup$ My professor always said: "start from the beginning, read book, read more books, read about every concept you do not know, then try to solve the question. And if you cannot give it one more day, revisit steps once more (maybe you overlooked something), and if this did not helped - solve easier questions or trace solutions to easier questions until you understand, and only if all failed ask question", another one was about books - not everyone likes particular book - try various resources. $\endgroup$
    – Evil
    Mar 23 '16 at 23:14
1
$\begingroup$

Here is the idea. Suppose that $C$ has covering radius $\rho$. Pick a vector $s \in \mathbb{F}^{n-k}$. Since $H$ is full rank, there is a vector $x$ such that $Hx = s$. There is a vector $y \in C$ with $|x-y| \leq \rho$ (here $|\cdot|$ is Hamming distance). Then $H(x-y) = s$, and so $s$ is a sum of at most $\rho$ columns of $H$. The opposite direction is very similar.

Improve this answer
$\endgroup$
1
  • $\begingroup$ With "$H$ is full rank" do you mean that all the columns are linearly independent? If, so? Why does it hold? Don't we know that there are $d$ linearly dependent columns? @YuvalFilmus $\endgroup$
    – Evinda
    Mar 23 '16 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.