In a Reed-Solomon codeword, why does knowing which symbols are missing double how many can be repaired?
answer
- how much does the decoder already know
- an error hides two things
- a loss hides only the value
- equations spent per damaged symbol
- 2t plus e within n minus k
basics
~20 sAn unknown-position error hides two things, where it is and what it should be, so it consumes two parity symbols. A known-position loss hides only the value, so it consumes one. With n minus k parity symbols the code repairs that many erasures but only half as many errors.
solid answer
~40 sEach parity symbol supplies one independent equation to the decoder. An error in an unknown position presents two unknowns — the location and the correct value — so it eats two of those equations. An erasure, where the system already knows the position is missing, presents one unknown, the value, so it eats one. The whole budget is `2t + e <= n - k` for `t` unknown-position errors and `e` known-position losses. A code with four parity symbols therefore repairs any four erasures, or two errors, or one error plus two erasures. Storage lives on the cheap side of that trade deliberately: a device that is unreachable, or a fragment that fails its own integrity check and is discarded, is a known-position loss, so the same parity buys twice the protection.
go deeper
Remember the distinction itself: a silently corrupted symbol is more expensive to fix than a symbol everyone agrees is missing, because the second one tells the decoder where to look.
Explain the counting. Each parity symbol is one equation, an unknown-position error has two unknowns and a known-position loss has one, so the budget is 2t plus e within n minus k.
Show how a real system engineers itself onto the cheap side, using per-fragment integrity checks to discard bad fragments so the decoder sees located losses, and why a successful decode still needs an end-to-end check.
The trade to own is how much verification to buy: every mechanism that converts silent corruption into a located absence effectively doubles the code you already pay for, often more cheaply than adding parity.
## Two kinds of damage, two different prices The decoder is solving for what the codeword should have been. The `n - k` parity symbols give it that many independent equations, and every piece of damage consumes some of them. How many depends entirely on what the decoder already knows. - An **error** is a symbol that has been silently corrupted. The decoder does not know which position is wrong, nor what the right value there was. That is two unknowns, and it costs **two** parity symbols. - An **erasure** is a symbol known to be missing: the device did not answer, the fragment failed its own integrity check and was discarded, the read timed out. The position is handed to the decoder; only the value is unknown. That is one unknown, and it costs **one** parity symbol. | Damage | What the decoder must find | Parity symbols spent | |---|---|---| | Unknown-position error | the position **and** the value | 2 | | Known-position erasure | the value only | 1 | ## The budget equation Put both together and the code's whole promise fits on one line: ``` 2t + e <= n - k ``` where `t` is the number of unknown-position errors and `e` the number of known-position losses. Work a concrete case. A code with `n = 14` and `k = 10` carries four parity symbols, so it handles: 1. four erasures and no errors (`2*0 + 4 = 4`); 2. two errors and no erasures (`2*2 + 0 = 4`); 3. one error plus two erasures (`2*1 + 2 = 4`). All three sit exactly on the budget. Nothing about the code changes between these cases — the same fourteen symbols, the same four parity symbols. Only the decoder's prior knowledge changes, and that knowledge is worth a factor of two. ## Why storage deliberately lives on the cheap side A distributed store spreads one blob's fragments across independent failure domains, and almost every loss it sees is *located*: a machine is down, a disk is gone, a rack lost power, a request timed out. The store knows precisely which fragment is absent. That is an erasure, and it means a code with four parity fragments protects against four simultaneous absences rather than two. Systems go further and manufacture the cheap case on purpose. Each fragment carries its own independent integrity check. On read, a fragment that fails that check is **discarded rather than passed to the decoder**, which converts a would-be unknown-position error into a known-position erasure before the decoder ever sees it. That single design move doubles what the same parity can repair, which is why the check is worth its storage even though it corrects nothing itself. ## What happens past the budget Exceeding the budget is not always a loud failure, and this is the part candidates miss. The damaged word can land closer to a *different* valid codeword than to the original, and the decoder will happily return that other codeword — a confident, well-formed, wrong answer. Serious systems therefore keep an end-to-end check over the reconstructed object rather than trusting the fact that decoding returned successfully. A second subtlety: the budget is per codeword, not per object. A blob is striped over very many codewords, and a loss that takes out one fragment removes one symbol from every one of them. That uniformity is what makes fragment-level reasoning valid — losing four fragments really does mean four erasures in each codeword, not four somewhere. ## What to watch - Do not quote the erasure count as the error count. Four parity symbols repair four located losses but only two silent corruptions; halving the wrong number here is the classic slip. - Do not assume the two budgets are separate. They draw on the same `n - k` pool, which is why the mixed case has to be checked with the equation rather than guessed. - Do not treat a successful decode as proof of correctness. Past the budget, decoding can succeed onto the wrong codeword. - Do not skip the per-fragment integrity check on the grounds that the code already protects the data. It is what keeps the system on the one-parity-symbol side of the trade.
- How does a system deliberately turn unknown-position errors into known-position losses?By giving every fragment its own independent integrity check. On read, a fragment that fails is discarded and its position reported as missing, so the decoder faces an erasure rather than a silent corruption. That converts a two-parity-symbol problem into a one-parity-symbol problem and doubles what the same code repairs.
- What happens when damage exceeds the parity budget?Decoding either fails loudly or, worse, succeeds onto the wrong codeword: the damaged word can sit closer to some other valid codeword, and the decoder returns that instead. Because a successful decode is therefore not proof of correctness, systems keep an end-to-end check over the reconstructed object.
- Can one codeword mix errors and erasures, and how is the mixture bounded?Yes, because both draw on the same pool. Two parity symbols per unknown-position error plus one per known-position loss must stay within n minus k. With four parity symbols that allows four losses, or two errors, or one error alongside two losses.
saying these in an interview costs you the question
- Says a code with four parity symbols corrects four silent corruptions.
- Treats errors and erasures as drawing on separate independent budgets.
- Claims a missing symbol is replaced with zeros and costs nothing.
- Assumes a successful decode always means the output is correct.
- Thinks knowing the damaged position is a convenience rather than half the problem.