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}$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

This is known as the Plotkin bound.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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