linear$ [2k, k, k]$-codes.

Question

Let $[n, k, d]$-codes be defined as a linear code of length $n,$ dimension $k$ and minimal distance $d.$

I'm trying to find the words in the$ [2k, k, k]$-code, but so far I've just been brute forcing it, is there a general way to find such words when you already know the code does exist?

And I don't mean to find if they cannot exist, because I already found that I can use the Griesmer bound for that.

Answer 1

You are off to a good start. Assuming your codes are binary Griesmer bound tells you that you must have $k\le4$ for it to be possible that such a code exists. Other pieces of advice:

• Warning: Even if the parameters of a code are within the Griesmer bound that does not guarantee that a code with such parameters exists. In general figuring out how high the minimum distance of an $[n,k]$-code can be is an open problem. You should keep your mind open to the possibility that tools other the Griesmer bound may prove the non-existence of a certain code. AFAICT that is not the case here though.
• If we didn't already know the parameters of the extended Hamming codes the case $k=4$ woud probably be the most challenging part of this exercise.
• You should be able to construct the codes corresponding to $k=1$ and $k=2$ without much ado. Neither of those is distance optimal, so you will have a lot of elbow room.
• That leaves the case $k=3$. Remember that a linear code has minimum distance $\ge3$ if no two columns of its check matrix are linearly dependent. So just jot down a full rank $3\times6$ parity check matrix with pairwise non-identical and non-zero columns, and solve for the codewords. There are other ways to find such a code as well. But IMHO those don't serve as well as hints, so I'll go with this suggestion.