<p>An error-correcting code <span class="math-container">$\mathcal{C}\subset \mathbb{F}_q^n$</span> comes with the following assumption</p>
<blockquote>
<p>If I receive an erroneous message <span class="math-container">$m \in \mathbb{F}_q^n \setminus \mathcal{C}$</span> then the original message is the one &quot;closest&quot; to it. <em>I.e.,</em> the decoder function is defined as follows <span class="math-container">$\mathcal{D} = c \iff d(c,m) = \min_{c' \in  \mathbb{F}_q^n}\{ d(c',m)\}$</span>.</p>
</blockquote>
<p>If you have more errors the <span class="math-container">$\frac{n-k}{2}$</span> for a <span class="math-container">$[n,k,n-k+1]$</span>-RS code then there is no unique <span class="math-container">$c$</span> such that <span class="math-container">$$\mathcal{D} = c \iff d(c,m) = \min_{c' \in  \mathbb{F}_q^n}\{ d(c',m)\}$$</span> so that you can't decode.</p>
<p><strong>However,</strong> <em>if we change the previous assumption to the assumption for</em> erasure coding. The error in an erasure channel is the some of the symbols being transmitted get dropped; <em>i.e.,</em> a message that is passed through the channel can have some of its symbols changed to a variable <span class="math-container">$X$</span>.</p>
<blockquote>
<p>An erasure channel is one where a massage <span class="math-container">$m \in \mathbb{F}_q^n$</span> that is transmitted can be confused for a message <span class="math-container">$m'$</span> where
<span class="math-container">$$m'_i = m_i \text{ or } m_i' = X $$</span>.</p>
</blockquote>
<p><em><strong>In this case, a Reed-Solomon code can be applied to correct up to <span class="math-container">$n-k$</span> erasures</strong></em>, which is twice as much as before. In other words, knowing the locations of the errors is the &quot;stars-aligning&quot; that you were seeking.</p>
<p>See <a href="https://en.wikipedia.org/wiki/Erasure_code" rel="nofollow noreferrer">the article on erasure codes on Wikipedia.</a> For some applications <a href="https://scholar.google.com/citations?user=0huMa6oAAAAJ&amp;hl=en." rel="nofollow noreferrer">check out my google scholar page or any of the papers in the bibliographies.</a> Erasure coding is a hot topic in distributed computing at the moment.</p>

CC BY-SA 4.0
2021-09-28T05:10:43.680Z
Very interesting, thank you
A. Nilsson
CC BY-SA 4.0
2021-09-28T05:21:45.400Z
No problem, best of luck!
Pedro Juan Soto
CC BY-SA 4.0
2021-09-28T00:44:45.633Z
2021-09-28T00:44:45.633Z
Pedro Juan Soto
<p>If I have a RS code, say <code>[46, 16, 31]</code>, 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 <code>[255, 225, 31]</code>)</p>
<p>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?</p>
<p>Also, do you have any information of what would constitute a &quot;stars align&quot;, in practical terms? Like all the erroneous symbols at the start of the received vector? The end? Or is it more complex than that?</p>

<coding-theory>
Non-random errors with a Reed Solomon code
A. Nilsson
# Non-random errors with a Reed Solomon code

(Asked by: username_0 on 2021-09-23)

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?

**Tags:** coding-theory


---

## 1 answers

### Answer by username_1 on 2021-09-28. Score: 0 | Accepted answer

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.](https://en.wikipedia.org/wiki/Erasure_code) For some applications [check out my google scholar page or any of the papers in the bibliographies.](https://scholar.google.com/citations?user=0huMa6oAAAAJ&hl=en.) Erasure coding is a hot topic in distributed computing at the moment.

> **Comments:**
> **username_0**: Very interesting, thank you  
> **username_1**: No problem, best of luck!  

---

