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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.