Thursday, December 15, 2011

Error correcting math problem?

Consider a binary symmetric channel with bit error probability p, 0 < p < 1/2. Suppose we encode a binary message (x1, x2, ..., x100) (i.e., there are 100 bits) as n copies of x1, followed by n copies of x2, n copies of x3, ...., n copies of x100. The receiver will look at the first n bits and choose y1 by majority vote from them (and y1 = 0 if there is a tie, say), then look at the next n bits and choose y2 by majority vote of those, and so on. Prove that (y1, y2, ..., y100) = (x1, x2, ..., x100) with probability approaching 1 as n tends to infinity.

No comments:

Post a Comment