2
$\begingroup$

I recently asked this question and got an answer from Yuval Filmus stating that we can build a solution using error-correcting codes.

More specifically, I'm looking for error correcting codes (for binary alphabet) with constant $R>0$ non-zero relative rate, and as high as possible relative distance $\delta$.

I know that using this theorem, we can achieve any $\delta < \frac{1}{2}$. As pointed out by Yuval Filmus's answer to my last question, this is the best $\delta$ we can hope for.

Where can I find a proof that states there is no binary error-correcting code with a relative distance bigger than $\frac{1}{2}$?

$\endgroup$
2
$\begingroup$

This is known as the Plotkin bound.

$\endgroup$
1
  • $\begingroup$ Thanks! this was really helpful to me :) $\endgroup$
    – nir shahar
    Jun 9 at 21:09

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.