What are the best (i.e., highest-rate) explicit binary codes with block length $n$ and minimum distance $d$, in the regime $d = n^{1 - o(1)}$?

The "redundancy" of a code is the difference between the block length and message length. Nonexplicitly, it's easy to show that there exist binary codes with distance $d$, block length $n$, and redundancy $O(d \log(n/d))$. When $d \leq n^{1 - \Omega(1)}$, the nonexplicit bound is $O(d \log n)$, which can be matched explicitly using e.g. Reed-Solomon codes. When $d = \alpha n$ with $\alpha$ a sufficiently small positive constant, the nonexplicit bound is $(1 - \Omega(1)) \cdot n$, which can be matched explicitly using e.g. Justesen codes.

What about in the middle? E.g., what if $d = n / \log n$? The nonexplicit redundancy bound is $o(n)$. Is there an explicit code matching it up to a constant?



Your Answer

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

Browse other questions tagged or ask your own question.