Errors up to Gilbert - Varshamov bound

Question

The Gilbert-Varshamov distance $GV(n,k)$ for binary linear code is given by the smallest integer $d$ such that $\sum_{i=0}^{d-1} \tbinom{n}{i} \geq 2^{n-k}$. Reference.

1. If the weight of error $w$ reach to the Gilbert-Varshamov distance, is it possible to decode correctly (high probability is also acceptable)?

2. The covering radius of a code is defined as the smallest radius such that the union of the spheres of codewords cover the $F_q^n$. In my understanding, for a linear code $[n,k]$ with Gilbert-Varshamov distance, its covering radius is $d-1$. The book Fundamentals of Error-Correcting Codes(Chapter 11) said and I quoted

When decoding C, if $t$ or fewer errors are made, the received vector can be uniquely decoded. If the number of errors is more than $t$ but no more than the covering radius, sometimes these errors can still be uniquely corrected.

Thus, the answer of question 1 may be positive. I want to know the detailed reason.

Answer 1

What GV bound says is that spheres of radius $d-1$ around codewords of a maximal code must cover $\mathbb{F}_q^n.$ If they don't you can add an uncovered vector to the code.

If the code is linear, the number of codewords is then $M=q^k$ which results in the equation you gave.

However, a point at distance $d-1$ from a specific codeword $c,$ can be as near as distance $1$ to another codeword $c'$, thus an error $e$ of weight $w=d-1$ moves the received word $c+e$ too far from $c$ and too near to $c'$ for minimum distance decoding to work.

And high probability of correction is in general not present either since as you increase the radius, the number of points on the surface of the sphere get larger and larger, and in general there is substantial intersection between the spheres around codewords when the radius approaches the Gilbert-Varshamov distance.

If the goal was only error detection not correction, this answer would change.

It is not the covering radius but the packing radius that ensures unique error correction to the nearest codeword. For distance $d,$ this is $t=\lfloor (d-1)/2 \rfloor.$