[readonly] markdown buffer
Reed–Solomon Erasure Coding Without the Magic
Suppose I split some data across six drives. Three drives disappear. I can still recover the data.
Reed–Solomon does this without storing three complete copies. It turns the original numbers into extra facts. Any three surviving facts are enough to work backwards.
We will build a small version from beginning to end. Each section introduces one operation, shows it, and explains why it exists.
The assumed maths stops at UK GCSE level: substitution, brackets, multiplication, squares and simple equations. No A-level maths is assumed. Anything beyond that is built here, one small operation at a time, before its formal name appears.
1. Choose the answer we want back
Enter text or a number. The default is 42. Every later visual follows the same value.
Choose the exact value we must recover
The value to protect is “42”. It contains 2 characters.
We start with the answer we expect at the end. Every later step must preserve this exact value.
Convert each character into the numbers a computer actually stores.
Nothing has been encoded yet. We have only written down the answer that recovery must produce.
2. Turn characters into numbers
Computers store text as numbers. UTF-8 is a standard lookup table: 4 maps to 52, and 2 maps to 50.
Replace each character with its UTF-8 number
“42” is now the number list [52, 50].
The coding maths works on numbers. UTF-8 is a standard lookup that we can reverse later; it does not lose the original text.
Split the number list into equally sized blocks.
This lookup is reversible. If we recover [52, 50], the same table takes us back to 42.
3. Work with three numbers at a time
Our toy protects blocks of three numbers. If the final block is short, zeroes fill its unused slots.
Put the bytes into three-number blocks
The first working block is [52, 50, 0].
Our small code protects three numbers at a time. A short final block gets zeroes only so it still has three slots; the decoder removes that padding at the end.
Before mixing those three numbers, practise the small wrap-around arithmetic the code uses.
For 42, [52, 50] becomes [52, 50, 0]. The zero is packaging, not new data. We remember the original length so it can be removed later.
4. Keep answers inside one fixed range
The stored numbers must stay a predictable size. First use a tiny set, 0 to 16, so the whole idea fits on screen.
14 × 8 = 112, but 112 is outside that set. Count around the loop and it lands on 10. This is what 112 mod 17 = 10 means: keep the remainder after dividing by 17.
Keep every answer inside a fixed set of numbers
The result can leave the 0–16 space and keep growing after every operation.
The result is always one of the same 17 values, so it still fits one toy symbol.
14 × 8 became 10 after wrapping around at 17.
Wrapping keeps every result inside one fixed-size symbol instead of letting the numbers grow forever.
Check that this wrapping arithmetic can also be undone.
Our byte example uses a larger loop from 0 to 256. The idea is identical; the larger loop has room for every possible byte.
5. Check that the mixing can be undone
Wrapping is only useful if recovery can reverse the operations. If two starting numbers produce the same answer, we cannot know which one was original.
Make sure the mixing has an undo button
Every input has a different answer. Multiplying by 15 reverses ×8.
For example, 14 × 8 mod 17 = 10, then 10 × 15 mod 17 = 14. No collision means the mixing can be undone.
Use the same idea with 257 positions so every byte value fits.
Using a prime-sized loop—17 in the small visual and 257 in the byte example—means every non-zero multiplication rearranges the values without collisions. That gives it an undo. The formal name is a finite field; remembering “fixed range, no collisions, operations can be reversed” is enough.
6. Give the three source numbers short names
Call the first number a, the second b, and the third c.
Give the three source numbers short names
52, 50, 0 are now called a, b and c.
The letters are only labels. They let us write one short rule while keeping all three original numbers visible.
Give each named value a separate slot in that rule.
For 42, this says a = 52, b = 50, and c = 0. The letters are labels, not extra maths.
7. Put the three numbers into one rule
Use:
p(x) = a + bx + cx²
p(x) just means “the answer this rule makes when we choose an x”. The three source numbers occupy three different slots.
Put the three named values into one reusable rule
becomes the plain number
becomes the amount of x
becomes the amount of x²
The three source values now occupy the three adjustable slots in p(x): 52, 50 and 0.
Later, recovery only needs to rediscover these three slots. A rule gives us a repeatable way to create extra facts about them.
Put one x value into the rule and calculate the first fact.
Why use a rule? We can put several different x values into it. Each produces a new fact about the same three source numbers.
8. Substitute one x value
Choose x = 2. Replace every x in the rule with 2.
Replace every x with the chosen number
p(2) = 52 + 50×2 + 0×2²
The same rule can answer many different x values. A different x will become a different stored fact.
Calculate the square and the two multiplied terms.
This is the same substitution used in school algebra. The chosen x is also the label that tells us which calculation produced the answer.
9. Work out the multiplied parts
Now calculate 2², then b × 2, then c × 2².
Do the square and multiplications
52 + 50×2 + 0×4 = 52 + 100 + 0
All three source slots contribute to the answer, so this shard is not merely a copy of one source value.
Add the three terms and wrap the answer.
Keeping this separate makes it clear that every source slot contributes to the stored answer.
10. Add, wrap, and store the pair
Add the three terms. Wrap the result into 0 to 256. Call the final answer y.
Add, then wrap into the 0–256 loop
a + 2b + 4c = 15252 + 100 + 0 = 152; 152 mod 257 = 152
The stored pair (x=2, y=152) is one equation about the same three source values.
Repeat the same three operations at other x positions.
For the default input, x = 2 produces (2, 152). The pair means “putting 2 into the rule produced 152”.
11. Repeat until there are three facts
Repeat Steps 8–10 with different x values. Every result becomes a different equation about the same a, b, and c.
Collect one equation for each unknown value
x=1 gives: a + b + c = 1021 different equation now describe a, b and c.
There are still three unknowns but only 1 fact, so more than one answer can fit.
Calculate another point to add another independent equation.
One equation cannot tell us three missing numbers. Two still leave choices. Three different equations leave one set of values that makes all three true.
12. See why two facts still allow different answers
This is worth seeing rather than accepting.
See why two points are ambiguous and three are not
Fits both known points.
Fits both known points.
Two different rules produce exactly the same first two stored points.
Two equations cannot solve three unknown values, so guessing would be unsafe.
Adding more points raises the number of erasures we can survive; it does not make the original data larger.
That is the central guarantee: three unknown source numbers need three different facts made by the same rule.
13. Make three replacement facts
We need three facts, but we calculate six by using x = 1 through x = 6.
Store six facts even though recovery needs only three
These three equations are enough to recover a, b and c.
These use new x values, so they can replace any missing equations above.
The same three source values produced six different equations.
Recovery needs any three equations, not these particular first three. Storing six means any three may disappear.
Erase shards and watch three survivors rebuild the source values.
Recovery does not need the first three. It needs any three with different x labels. That is why the extra facts provide protection.
14. Erase some shards
Now lose facts without trying to recover anything yet.
Erase shards without doing any recovery yet
Click a shard to mark it missing. Watch only the survivor count for now.
3 shards are missing; 3 remain.
The source block contains three unknown numbers. We therefore need at least three surviving facts before recovery can even begin.
Write the surviving coordinates back out as equations.
Three survivors are enough for three unknown source numbers. Two survivors are not.
15. Write the surviving facts as equations
Each surviving pair gives an ordinary equation. For example, (3, 202) means:
a + 3b + 9c = 202
Turn each surviving coordinate back into an equation
a + 1b + 1c = 102a + 3b + 9c = 202a + 5b + 25c = 45The three surviving coordinates are now three equations about a, b and c.
A coordinate is not an unexplained magic number. It records which x was used and the y answer produced by the rule.
Build a small selector that can listen to one equation at a time.
The next five sections show how the decoder combines those equations. This is the hardest part, so each section does one small job.
16. Plan a 1-or-0 switch
Start with the first survivor. We want a small rule that produces:
1at this survivor;0at the other two.
Decide what one selector must keep
Decide what this switch must do
Multiplying by 1 keeps a number. Multiplying by 0 removes it.
We want a switch that is 1 at x=1 and 0 at x=3 and x=5.
Multiplying the switch by 102 will keep 102 at its own position and add nothing at the other two.
Create zeroes at the two points this selector must ignore.
Why 1 and 0? Multiplying by 1 keeps a number. Multiplying by 0 removes it.
17. Make zeroes at the ignored positions
The bracket (x − 3) becomes zero when x = 3. Multiplying by a zero makes the whole result zero.
Force that selector to zero at the other points
Make the switch zero at the other two positions
The factors (x−3) and (x−5) force the switch to zero at the other two x positions.
If either factor is zero, their product is zero. This mutes both other survivors.
Adjust the selector so its own point produces exactly one.
Two brackets create two zeroes. The switch now ignores the other two survivors.
18. Make the kept position equal one
At its own x, the switch is not necessarily 1 yet. Use the reversible wrap-around multiplication from Step 5 to scale its answer to 1.
Make the selector equal one at its own point
Make the switch equal 1 at its own position
We got 8, but we need 1. In our 0–256 number loop, 8 × 225 mod 257 = 1. Multiply the whole switch by 225.
At x=1, the two factors produce 8. Multiplying by 225 changes that result to 1 after wrapping.
Now the same switch is 1 at its own point and 0 at both other points: exactly the pattern we asked for.
Multiply the selector by the stored y value.
The switch now gives the pattern [1, 0, 0] across the three survivor positions.
19. Put the stored y value into the switch
Multiply the switch by the survivor’s y value.
Put the survivor’s stored value into the selector
Put this survivor's stored value into the switch
At the three survivor positions: 102 × [1, 0, 0] = [102, 0, 0]
At the survivor positions, 102 × [1, 0, 0] becomes [102, 0, 0].
The kept position now contains 102; the two ignored positions still contain zero.
Expand the brackets so this piece becomes three slot numbers.
The pattern [1, 0, 0] becomes [y, 0, 0]. This restores one survivor without affecting the other two.
20. Turn one bracketed rule into three slot numbers
The previous visual produced a rule with brackets. We still need the three plain, x, and x² slot numbers hidden inside it.
Expand the brackets using ordinary school algebra:
(x − 3)(x − 5) = x² − 8x + 15
Turn the bracketed rule into three slot numbers
Expand the brackets, then read the three slots
wrap at 257 → 127
wrap at 257 → 155
wrap at 257 → 77
Expanding the brackets and collecting the plain, x and x² parts produces [127, 155, 77].
We need the three slot numbers because those are the original values the decoder is trying to rebuild.
Repeat for the other survivors, then add their slot numbers.
This is where each three-number piece comes from. It is not a new trick: the values are the plain, x, and x² slots after expanding, multiplying and wrapping.
21. Add the three restored pieces
Repeat Steps 16–20 for each survivor, then add their three sets of slot numbers.
Add the three selector pieces
Add the three pieces
[127, 155, 77] +[133, 46, 78] +[49, 106, 102]= [52, 50, 0]p(x) = 52 + 50x + 0x² (mod 257)
The three pieces add to [52, 50, 0], which means p(x) = 52 + 50x + 0x² (mod 257).
Each piece restores one survivor without changing the other two. Their sum therefore matches all three survivors at once.
Read the three recovered slot numbers back as the original byte block.
The result is the original three-number block. The formal name for this recovery method is Lagrange interpolation; the name is less important than the six operations above.
22. Turn the recovered numbers back into text
Remove any zero padding, then reverse the UTF-8 lookup from Step 2.
Turn the recovered numbers back into text
These match the numbers placed in a, b and c earlier.
The added zero only filled an unused slot.
The same number table from Step 2 returns the original characters.
The first block [52, 50, 0] decodes to “42”.
Encoding never threw the original numbers away. Recovery rebuilt them, so reversing the UTF-8 lookup gives the same text.
The complete input has now made the full round trip.
For a longer input, the same process runs separately for every three-number block. The decoded pieces are then joined.
23. Missing and secretly wrong are different problems
An erasure means we know exactly which shard is unavailable. An error means a shard supplies a wrong value and pretends it is valid.
Choose the protection you are paying for
Any 3 of the 6 correct stored values are enough.
Finding which stored values lied costs roughly twice as much protection.
The 3 extra stored facts let any 3 known missing shards disappear while 3 useful facts remain.
When a missing position is known, recovery can ignore it immediately. A secretly wrong value must be found before it can be repaired.
Real systems use checksums to identify a bad shard, then treat it as missing.
Known missing positions are easier: the decoder immediately uses the remaining facts. A hidden wrong value must first be located, which consumes more of the extra protection.
The complete automatic run
The final workbench repeats the complete journey using the same input as the detailed explainer.
It now has 24 stages. Each stage shows one operation for five seconds. Pause it or choose a numbered stage when you want more time.
Send your own value through the whole journey
Choose the exact text to protect
Nothing has been encoded yet. This is the value every later step must preserve.
This is the answer the final stage must return without changing a character.
Stage 1 is showing one operation only. The next stage appears after five seconds.
Encoding and recovery are the same small ideas from the earlier toys, repeated once for every three-byte block.
This remains an educational code rather than a production storage format. Real implementations use byte-sized fields, fast arithmetic, many blocks and metadata that identifies every shard. The useful mental model stays the same: turn three source numbers into more than three facts, then use any three surviving facts to rebuild the source numbers.