# Compute minimum hamming distance of a code

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?

• If the code is linear then there is no need to look at each pair. It's enough to compute the minimal Hamming weight of a non-zero codeword. Is this your case here? – Yuval Filmus Jan 30 '14 at 14:11
• My case is hamming code (7,4,3) which I know is linear. – SuperStamp Jan 30 '14 at 14:17

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...?
• So, technically I can take any valid codeword and count all $1$-s. In the case of $(7,4,3)$ that would be $d_{min}=4$. – SuperStamp Jan 30 '14 at 14:30
• That's not how this problem is usually attacked, since it is indeed difficult. Instead you use other equivalent characterizations of the minimal distance. For the Hamming code in particular, it is probably possible to prove directly that no codeword has weight $1$ or $2$, and to exhibit a codeword of weight $3$. (This should be equivalent to the generator matrix characterization.) – Yuval Filmus Jan 30 '14 at 17:21