Question 2.16 of Essential Coding Theory by Guruswami, Rudra and Sudan asks to produce a $[n - d, k - 1, d'\geq\lceil d/q\rceil]_q$ code from an arbitrary $[n, k, d]_q$ code. Here we are working over $\mathbb{F}_q^n$, $k$ is the dimension of our code, and $d$ is the minimum distance between two codewords.
I think I see what to do — the more-or-less obvious thing is to write a generating matrix with two generators that differ in $d$ places, delete the $d$ columns at which they differ, then delete one of the generators (since both will be the same after removing the columns where they differ). It is easy to prove that this can be done (two independent codewords exist with the minumim distance) and that the remaining matrix is a generator matrix (all rows are independent) and that it has the required dimensions.
What is not so easy is proving the $\lceil d/q \rceil$ bound on the minimum distance of the new code. My questions in order are:
- What does this quantity even mean? I don't see the sense in dividing the original distance by the field order, so I have no intuition for this problem.
- Can I prove this bound for the $[n-d,k-1]_q$ code that I constructed, or do I need to start over with another approach? I have created a bunch of example codes and they all seem to have the right distance bound after reducing.