A noisy channel
Assume that you have to transfer a message over a corrupted channel which can randomly flip one of the bits in your message. You are allowed to send bits, and you can use this channel only once. You don't know which bit is going to be corrupted. There are many possible ways to encode your data so there will be no information loss (for example you can transfer a message of the length three times so the receiver will be able to choose the correct value for each bit comparing the values of it from different copies of the message). How many bits can you correctly transfer with the best possible strategy? Solve for
The answer is 8178.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Hint: We can divide the n bits into two parts and denote the parity of longer part using a bit in the end. Dividing the rest of the bits into halves and following an approach similar to binary search we need log(n+1) bits to denote the parity.
The answer is n − l o g ( n + 1 ) .