0
$\begingroup$

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

Suppose that $\rho$ is the covering radius .

I want to show that $\rho \leq n-k$.

Could you give me a hint how we could show this?

The covering radius is defined as follows:

$$\rho=\max_{x \in \mathbb{F}_q^n} d(x,C) \\ d(x,C)=\min_{c \in C} d(x,c)$$

|cite|improve this question|||||
$\endgroup$
  • 1
    $\begingroup$ Please ask only one question per post. $\endgroup$ – Yuval Filmus Mar 23 '16 at 21:12
1
$\begingroup$

You need to show that every vector is at distance at most $n-k$ from a codeword. The code is the collection of all vectors $x$ satisfying $Ax = 0$, where $A$ is an $(n-k) \times n$ matrix, which without loss of generality has the form $A = \begin{bmatrix} I_{n-k} & B \end{bmatrix}$ (use Gaussian elimination, possibly permuting coordinates to avoid zero columns). Let $v$ be a completely arbitrary vector, and suppose that $Av = s$. Extend $s$ to a vector of length $n$ by adding zeroes at the end. Then $A(s + v) = 0$, i.e., $v + s$ is a codeword, which is at distance at most $|s| \leq n-k$ from $v$.

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ With $A$ do you mean the parity matrix? If so , isn't its dimension $(n-k) \times n$ ? @YuvalFilmus $\endgroup$ – Evinda Mar 23 '16 at 20:28
  • $\begingroup$ Also we have $Av-s=0$. How do we deduce from this that $A(s+v)=0$ ? @YuvalFilmus $\endgroup$ – Evinda Mar 23 '16 at 20:36
  • $\begingroup$ Using the fact that $A=\begin{bmatrix} I_{n-k} & B \end{bmatrix}$. Try an example. $\endgroup$ – Yuval Filmus Mar 23 '16 at 20:37
  • $\begingroup$ In this case $|x|$ is the Hamming weight of $x$. Evinda, try to be more resourceful. $\endgroup$ – Yuval Filmus Mar 23 '16 at 21:00
  • $\begingroup$ If you're interested in that, you're welcome to ask a new question. $\endgroup$ – Yuval Filmus Mar 23 '16 at 21:04

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.