I know the $n$-bit message ($M$).

I have to send it to the receiver bit by bit.

For each bit I can also send one bit of comment ($C$).

Before receiver gets the bit, he have to guess it($G$).

After all, $M$, $C$ and $G$ should differ only in $k$ places, ie: $$||(M \underline{\vee} C) \vee (M \underline{\vee} G)|| \leq k $$

Receiver and I both know the protocole of sending the message, so he can guess some informations basing on my comments.

What is the maximal length of the message I can send?

the only solution I've found is $n=2k$, which is pretty obvious (eg. in the first $k$ bits of $C$ I send the second half of the message). Is it possible to construct the protocole in the way, that it allow to send messages longer than $2k$?

  • $\begingroup$ Do I understand correctly that the worst case of the "guess" has to satisfy the inequality? So in fact the receiver must be able to deduce a "guess" from the message and comment bits already received such that the inequality is satisfied? $\endgroup$ – joriki Sep 7 '18 at 14:32
  • $\begingroup$ Yes. The receiver have to guess $i+1$st bit basing on the $i$ previous bits. $\endgroup$ – Jaroslaw Matlak Sep 7 '18 at 19:17
  • 1
    $\begingroup$ No, that part was clear. My question was about whether you want a worst-case analysis. $\endgroup$ – joriki Sep 7 '18 at 19:26
  • $\begingroup$ Also yes. I want to be sure, that the inequality is satisfied regardless the message $M$ $\endgroup$ – Jaroslaw Matlak Sep 7 '18 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.