[Solved]: Compute minimum hamming distance of a code

Problem Detail: 

How do you find the minimum hamming distance of a code?
A naive way is computing the distance of each pair of codewords in our code.

It becomes hard when the code is sufficiently large. Is there a formula for minimum hamming distance?

Asked By : SuperStamp

Answered By : Yuval Filmus

When the code is linear, there is no need to go over all pairs of codewords, due to linearity. Indeed, since $d(x,y) = d(x\oplus y, 0)$ and for any two codewords $x,y \in C$, linearity implies that $x\oplus y \in C$, we see that the minimal distance is the minimal weight of a non-zero codeword. There are other ways characterization of the minimal distance, for example in terms of the generator matrix. See also this question.

By the way, an $(n,k,d)$-code is one with $2^k$ codewords of length $n$ and minimal distance $d$. So if you have a $(7,4,3)$-code, the minimal distance must be...?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/20105