Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

“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. □

share|improve this question
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.