2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Yuval Filmus Jan 30 '14 at 14:11
  • $\begingroup$ My case is hamming code (7,4,3) which I know is linear. $\endgroup$ – SuperStamp Jan 30 '14 at 14:17
3
$\begingroup$

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...?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – SuperStamp Jan 30 '14 at 14:30
  • $\begingroup$ No. Please make sure that you understand the concept of minimal distance, that you understand what I wrote, and then you will be able to answer your own question. $\endgroup$ – Yuval Filmus Jan 30 '14 at 14:32
  • $\begingroup$ OK, I get it now. Because of linearity, I need to find the codeword with the smallest weight. the distance from the zero-codeword - is the minimum distance of the code. But now I got a new problem - How to find the codeword with the minimum weight? $\endgroup$ – SuperStamp Jan 30 '14 at 14:43
  • 2
    $\begingroup$ 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.) $\endgroup$ – Yuval Filmus Jan 30 '14 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.