minimum distance of a linear codes

Question

My question is about computing the minimum distance (weight) of a linear code. Assume that we have the generating matrix of the code. Then we can easily compute the weights of each row and of course the minimum weight among the set of all rows gives us an upper bound for the minimum weight. My question is, are there any techniques to improve this bound? Also is it possible to find a lower bound for that? Any references will be appreciated.

Answer 1

Of course there are many lower bounds, but for structured choices of $G$.

Bounds such as BCH bound, Hartmann-Tzeng bound apply to cyclic codes, for example. Reed Muller codes have a well known minimum distance, directly obtained from their order, etc.

Answer 2

The problem of the computation of the minimum distance from the generator matrix of a linear code is known to be NP hard, so there won't be any fast algorithms for the general case.

For practical purposes, the best known algorithm is the Brouwer-Zimmermann algorithm. Compared to the naive algorithm checking the weight of every single codeword, the number of enumerated codewords is drastically reduced. In the algorithm, a lower and an upper bound on the minimum distance is gradually improved, until both of them agree.