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.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment