Proove that hamming distance is three for Hamming(7,4)

Question

I'm trying to proof that the minimal Hamming distance for any Hamming(7,4) code is exactly three. My idea was to show that it is bounded above by three and then eliminating 2,1 as possibilities. I'm not sure how to show that analytically.

Answer 1

What is your definition of a $(7,4)$ Hamming code? The minimal definition is a set of $2^4 = 16$ binary vectors of length $7$ such that any two vectors differ in three or more places. So, what you are looking for is a proof that a given collection of $16$ binary vectors has the specified property. This can be done by checking the $\binom{16}{2} = 120$ pairs of codewords to see every pair differs in at least three places.

If you are given a more specific description, e.g. you are told that the code is a linear code with specified generator matrix or parity check matrix, then the above brute-force method can be simplified to checking just the minimum weight of the code since, as @JyrkiLahtonen's comment says, the minimum distance of a linear code equals the minimum weight. More simply, if the $7$ columns (more generally $2^n-1$ columns) of the parity check matrix are the $7$ (more generally $2^n-1$) nonzero binary vectors of length $3$ (more generally, length $n$), then the code is a linear Hamming code; that is, we need not make a list of all the codewords to find the minimum weight. But, a Hamming code need not be a linear code at all. For example, each coset of a linear Hamming code has the property that any two vectors differ in at least three places. So, if you are given a list of the vectors in a coset of a linear Hamming code (without being informed that it is a coset) and asked whether this set of vectors constitutes a Hamming code, then the brute-force checking of all $120$ pairs (more generally, $\binom{2^n-1}{2}$ pairs) is what you need to do.