If I have a RS code, say [46, 16, 31], then I have a guaranteed error correction up to 15 symbols. I have no idea if it matters, but the code I have in front of me is a shortened code (down from [255, 225, 31])

But what I want to know is the maximum possible number of errors it can correct, if the stars align? Is that 31? Or 30, or lower?

Also, do you have any information of what would constitute a "stars align", in practical terms? Like all the erroneous symbols at the start of the received vector? The end? Or is it more complex than that?


1 Answer 1


An error-correcting code $\mathcal{C}\subset \mathbb{F}_q^n$ comes with the following assumption

If I receive an erroneous message $m \in \mathbb{F}_q^n \setminus \mathcal{C}$ then the original message is the one "closest" to it. I.e., the decoder function is defined as follows $\mathcal{D} = c \iff d(c,m) = \min_{c' \in \mathbb{F}_q^n}\{ d(c',m)\}$.

If you have more errors the $\frac{n-k}{2}$ for a $[n,k,n-k+1]$-RS code then there is no unique $c$ such that $$\mathcal{D} = c \iff d(c,m) = \min_{c' \in \mathbb{F}_q^n}\{ d(c',m)\}$$ so that you can't decode.

However, if we change the previous assumption to the assumption for erasure coding. The error in an erasure channel is the some of the symbols being transmitted get dropped; i.e., a message that is passed through the channel can have some of its symbols changed to a variable $X$.

An erasure channel is one where a massage $m \in \mathbb{F}_q^n$ that is transmitted can be confused for a message $m'$ where $$m'_i = m_i \text{ or } m_i' = X $$.

In this case, a Reed-Solomon code can be applied to correct up to $n-k$ erasures, which is twice as much as before. In other words, knowing the locations of the errors is the "stars-aligning" that you were seeking.

See the article on erasure codes on Wikipedia. For some applications check out my google scholar page or any of the papers in the bibliographies. Erasure coding is a hot topic in distributed computing at the moment.

  • 1
    $\begingroup$ Very interesting, thank you $\endgroup$
    – A. Nilsson
    Sep 28, 2021 at 5:10
  • $\begingroup$ No problem, best of luck! $\endgroup$ Sep 28, 2021 at 5:21

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.