# Check my proof on distance in a parity-check binary code?

“distance between two parity-check binary codewords must be even.”

Suppose the distance between two codewords A & B of length n is odd. Further, partition {1,...,n} into two sets: P = {i: a_i = b_i} and Q = {i: a_i != b_i}.

Case 1. A has an even number of 1’s in Q.

Since |Q| is odd, there an odd number of 0’s in Q, so B has an odd number of 1’s in Q.

Since the number of 1’s in A must be even, there are an even number of 1’s in P.

So B has an even number of 1’s in P and an odd number of 1’s in Q. But then, B has an odd number of 1’s, since P ∪ Q = {1,2,...,n} (or equivalently, P and Q are disjoint)

Case 2. A has an odd number of 1’s in Q.

Since |Q| is odd, there are an even number of 0’s in Q, so B has an even number of 1’s in Q.

Since the number of 1’s in A must be even, there are an odd number of 1’s in P.

Therefore, B has an odd number of 1’s.

Both of these cases lead to a contradiction, so the distance between two codewords must be even. □

-
Please see here for how to typeset common math expressions with MathJax, and see here for how to use Markdown formatting. – Zev Chonoles Jun 14 '13 at 1:43