Reed–Solomon Erasure Coding Without the Magic

Suppose I split some data across six drives. Any three drives may disappear. I still want every byte back.

Our small Reed–Solomon encoder will take three original numbers and calculate six new stored numbers. Each stored number keeps a label describing how it was calculated. Any three correctly labelled survivors contain enough information to reconstruct the three originals.

We will build a small version from beginning to end. At every step we will ask four questions: what information do we have, what problem blocks us, why does this particular operation solve it, and what does its result enable next?

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

Before building protection, we need an exact success condition. Enter text or a number; the default is 42. Every later visual follows the same value.

Why do this first? Without recording the original value, seeing some text at the end would not prove that recovery worked. Nothing has been encoded yet; we have only fixed the answer every later operation must preserve exactly.

2. Encode the characters as bytes

We currently have characters, but the mixing rule can only add and multiply numbers. We therefore need a reversible bridge from text to numbers. UTF-8 is that bridge: it turns each character into one or more bytes, where a byte is a number from 0 to 255.

For the default input:

• 4 becomes byte 52;
• 2 becomes byte 50;
• the complete byte sequence is [52, 50].

Why UTF-8 rather than inventing our own numbering? The mapping must be reversible and must support more than the English alphabet. UTF-8 already defines exactly which byte sequence represents each character. If recovery returns the same bytes [52, 50], running that agreed mapping backwards returns 42.

This is not Reed–Solomon yet. It prepares the kind of input the maths accepts without changing the information we need to protect.

Some characters use more than one byte. That does not change the later maths; the encoder protects the resulting byte sequence three numbers at a time.

3. Record where the real bytes end

We now have the real byte sequence [52, 50]. The next step requires groups of exactly three, so we will add a zero to make [52, 50, 0]. That creates a future ambiguity: zero may be padding, but zero is also a valid piece of real data.

Why record the length now? Before padding, we still know which bytes came from the user. After encoding and recovery, the padding zero looks exactly like a real zero. Saving length = 2 now gives the decoder an external boundary it cannot infer later.

For 42, the block will contain [52, 50, 0], but the saved length says only the first two positions belong to the input. Recovery can therefore keep exactly two bytes instead of guessing which zeros to remove.

4. Divide the bytes into blocks of three

The byte sequence could be any length, but one small set of equations can only solve a fixed number of unknown values. We therefore process the input in separate, fixed-size blocks. This article chooses a 3-of-6 code:

• each working block contains 3 original numbers;
• the encoder calculates 6 labelled clues about that block;
• any 3 correctly labelled clues can recover the 3 originals;
• therefore any 3 of the 6 clues may disappear.

Why blocks of three? Each block creates exactly three unknown source values for the decoder to recover. That lets us demonstrate the central rule—three suitable clues recover three unknowns—with equations short enough to solve by hand. A four-slot code would require four surviving equations; an eight-slot code would require eight. Three is a teaching choice, not a limit of Reed–Solomon.

Why split a long input instead of making one enormous rule? Solving and replacing small blocks keeps the amount of work bounded. A damaged shard then removes one clue from every small block, and the same recovery procedure can run independently for each block.

The statement “three originals need three clues” still needs proof. We will build that proof from the simpler case of two originals.

5. Build the smallest rule that can create recoverable clues

We need to understand how several stored answers can preserve values that are no longer stored directly. Start with only two source values, [4, 2], so we can see the complete idea before adding a third.

Merely storing their sum does not work. If every clue were 4 + 2 = 6, making ten clues would only make ten copies of 6. The separate values 4 and 2 would already be lost because many different pairs have the same sum.

We need a clue-making rule with two properties:

1. changing a label must produce a genuinely different clue;
2. two differently labelled clues must let us recover both original values.

Call the first value a and the second b, then use:

y = a + bx

Here x is a label we are free to change, and y is the answer we store. Why give the values these particular jobs?

• a is multiplied by 1, so its contribution stays fixed when x changes;
• b is multiplied by x, so its contribution changes when x changes.

The design is chosen to make one value cancel cleanly during recovery. In two clues, a appears with the same weight 1, while b appears with two different weights. Subtracting the equations will therefore remove a and leave a multiple of b. Once b is known, either clue reveals a.

If both values changed together, ax + bx = (a+b)x, and every clue would reveal only a+b. If neither changed, every clue would be identical. One fixed job plus one changing job is the simplest arrangement that keeps the two values separable.

6. Make two labelled clues

We now have a recipe, but no stored clues. To create clues, choose two different settings for x. We use 1 and 2 because they keep the arithmetic small and their difference is 1; no special Reed–Solomon property belongs to those particular numbers.

Choose x = 1:

y = 4 + 2×1 = 6

Choose x = 2:

y = 4 + 2×2 = 8

Store (1, 6) and (2, 8). From here onwards, labelled clue means exactly this pair (x, y):

• x records which weights were used;
• y records the answer those weights produced.

Why must the settings differ? Using x = 1 twice would recreate the same equation twice. It would look like two stored items but contain only one piece of information. Different settings make b carry a different weight in each equation.

Why store x as well as y? The number 8 alone does not say which weights produced it. The label tells recovery how to turn the stored answer back into an equation. Discarding x would discard the instructions needed to interpret y.

7. Subtract the two equations to recover b

The original pair is now treated as lost. All we have are (1,6) and (2,8). Their labels recreate these equations:

a + b = 6

a + 2b = 8

Subtract the first equation from the second:

(a + 2b) − (a + b) = 8 − 6

Term by term:

• a − a = 0;
• 2b − b = b;
• 8 − 6 = 2.

The result is b = 2.

Why subtract rather than add, divide or guess? Our Step 5 design deliberately put the same amount of a in both clues. Subtraction turns that shared part into a−a=0. Adding would keep both unknowns; dividing whole equations would mix them into fractions; guessing would provide no guarantee. Subtraction exploits the structure we intentionally created.

Because the two x labels differ by 1, the remaining b terms are 2b−b=b. This is the payoff from choosing one fixed job and one changing job.

8. Substitute b to recover a

After Step 7, b is known but a is still missing. The reduced equation no longer contains a, so it cannot recover it. We must return to one of the original clues, which still relates a to b.

Use a + b = 6 and replace b with the recovered value 2:

a + 2 = 6

Subtract 2 from both sides:

a + 2 − 2 = 6 − 2

a = 4

Why substitute? An equation with two unknowns could not identify either value by itself. Replacing the now-known b removes that ambiguity and leaves an ordinary one-unknown equation. Either original clue would work and must give the same a.

Two differently labelled clues have now recovered both source values. This miniature round trip is why the later three-value mixer is plausible rather than magic.

9. Give a third source value a third job

Our real block contains three values, but the rehearsal rule has only two distinguishable jobs. Simply inserting c somewhere in those existing jobs would destroy information:

• adding c to the fixed slot produces (a+c) + bx, so only the sum a+c can be recovered;
• giving c the same changing slot produces a + (b+c)x, so only the sum b+c can be recovered.

Give c a new weight pattern, x²:

p(x) = a + bx + cx²

Now the three slots change as 1, x, and x². Why those three patterns?

We need one recipe that can make as many differently labelled clues as we want. Changing the single label x must produce a new mixture, and any three differently labelled mixtures must contain enough different information to recover the three originals.

The shortest power sequence with three different jobs is:

• 1: this slot stays fixed;
• x: this slot changes once with x;
• x²: this slot changes twice with x.

Using x twice would fail because bx + cx = (b+c)x: the second and third originals would merge into one unknown sum. Using x and 2x would fail for the same reason: both still follow the same x pattern, with one merely twice the other.

In fact, any third pattern made only from “a fixed number plus a multiple of x” would fail. Call that pattern r + sx. The rule would become:

a + bx + c(r + sx)

Multiply out the brackets:

a + bx + cr + csx

Group the fixed parts and the x parts:

(a + cr) + (b + cs)x

The three originals have collapsed back into only two recoverable combinations: a + cr and b + cs. No number of extra clues could separate a, b, and c again.

We therefore need a third pattern that cannot be rewritten as “fixed number plus a multiple of x”. The simplest next operation is to multiply x by itself, giving x². That is the actual reason for choosing it: it creates a third kind of change that cannot be absorbed into the first two jobs.

This does not yet prove that the choice works. Steps 15 and 16 do that by starting with three clues and showing that the arithmetic can always separate all three original slots. The choice is therefore not “because Reed–Solomon says so”; it is the simplest reusable pattern that passes the recovery requirement.

10. See the complete shape before adding bounded arithmetic

We have designed the shape of one recoverable clue, but the next topic—bounded arithmetic—will add unfamiliar wrapping. Before introducing that complication, pause and see where every value will travel.

The encoder does not turn one number into several copies. It turns the whole three-number block into six labelled clues about that block.

If the originals disappear, three surviving clues give three different weighted totals about the same three unknown numbers. The x labels reveal the weights used for each total. Recovery can therefore find the one three-number block that makes all three clues true.

Why show an overview now? It separates the storage design from the number system used to implement it. If we introduced mixing, modular arithmetic, shards and recovery simultaneously, it would be unclear which idea solved which problem.

This overview deliberately uses ordinary arithmetic. It answers what is stored and what survives. Some totals grow beyond a byte; Step 11 separately answers how those totals remain a fixed size without destroying reversibility.

That is the whole shape. The remaining sections make every calculation and its reversal explicit.

11. Keep answers inside one fixed range

The storage shape now works in ordinary arithmetic, but repeatedly multiplying byte values produces ever-larger numbers: 200 × 200 = 40,000. A code whose stored symbols grow without limit is not a usable fixed-size storage format. We need every operation to return to one known set of values.

Why not simply discard high digits or wrap into 0–255? Size is only half the requirement. Recovery must also undo multiplication. Ordinary mod 256 keeps answers small, but some multiplication merges different inputs:

0 × 2 mod 256 = 0

128 × 2 mod 256 = 0

Two possible inputs have become the same answer. Keeping the result byte-sized is not enough; recovery also needs every non-zero multiplication to have an undo. The decoder will eventually undo numbers that multiply the unknown letters. If multiplication merged two inputs, that undo operation would have no single correct answer.

First use a tiny set, 0 to 16, so the safe version of the 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.

Why 17? It is only a teaching choice. We need a prime that is small enough to draw but large enough to show interesting results. A loop of 3 positions would work mathematically but is too cramped to teach much. A loop of 97 would also work but would be absurd to put on a clock. Seventeen is a convenient middle ground, not a magic Reed–Solomon number.

Our educational encoder uses a larger loop from 0 to 256. We use 257 positions because every byte value from 0 to 255 fits, and 257 is the smallest prime larger than 255. The trade-off is that an encoded answer can be 256, so this toy needs 9 binary digits per stored value; a simple implementation would usually place that value in two bytes.

Production Reed–Solomon code usually uses a 256-value arithmetic table called GF(256). Every non-zero multiplication row in that table contains each non-zero byte exactly once, so every result points back to one input and the multiplication can be undone. Building that table uses bit operations rather than ordinary remainders. This article does not use those operations: every calculation below stays in the fully shown 257-position system.

12. Check that the mixing can be undone

Step 11 proposed prime-sized wrapping, but saying it is reversible is not enough. Before entrusting data to it, test the exact failure that would make decoding impossible: two different inputs landing on the same answer.

Why must the loop size be prime? Compare loops of 16 and 17 positions while multiplying by 8:

• with 16 positions, 0 × 8 and 2 × 8 both land on 0, so two possible inputs collide;
• with 17 positions, multiplying by 8 visits every position exactly once.

A composite number such as 16 can be split into smaller whole-number factors. Those shared factors allow different inputs to collapse onto the same remainder:

• the inputs 0 and 2 differ by 2;
• multiplying that difference by 8 gives 2 × 8 = 16;
• 16 is exactly one complete lap of the 16-position loop;
• the two products therefore land on the same position.

Why can that not happen in the 17-position loop? A collision after multiplying inputs u and v by 8 would mean their raw products differ by a whole number of 17-position laps. Their difference is 8 × (u−v). Seventeen is prime and shares no factor with 8, so a complete factor of 17 would have to come from u−v. But u and v are both between 0 and 16; the only way their difference can be a whole multiple of 17 is for the difference to be 0. That means u and v were the same input, not a collision.

Why test multiplication rather than only addition? Adding a known amount can always be undone by subtracting it. Multiplication is the risky operation used throughout the mixer: if multiplying by a non-zero weight creates collisions, the later “divide this weight away” step has no unique answer.

This is why we do not merely pick any range that looks convenient. Once two possibilities have merged, no decoder can separate them again. The formal name for the safe prime-sized number system is a finite field; remembering “fixed range, no collisions, operations can be reversed” is enough.

13. Give the three source numbers short names

We are about to use the same mixer for every three-number block. Writing the current values—such as 52, 50 and 0—directly into the rule would describe only this one block and would make the recovery algebra hard to follow. We need names for the three positions, independent of whichever numbers occupy them.

Call the first position a, the second b, and the third c.

For 42, this says a = 52, b = 50, and c = 0. The letters are labels, not extra maths.

Why letters? During decoding the values themselves are unknown. The letters let us write statements about those missing positions and solve for them. Once solved, they map straight back to the first, second and third byte positions.

14. Build the mixer that makes replacement clues

We have three original numbers but want six stored numbers. Two complete copies would also occupy six positions, but they would not survive every possible set of three losses. If the a position vanished from both copies, plus any third position, neither remaining copy would contain a complete [a,b,c] block.

Reed–Solomon instead makes every stored clue a different mixture of all three originals. No clue belongs only to a, b, or c; any three survivors describe the whole block.

What problem does the mixer solve? It spreads knowledge of every original across every stored position. We are deliberately replacing the original layout—where one lost position means one completely lost value—with a set of overlapping equations. A surviving clue does not reveal one byte directly; it preserves some information about all three.

This rule is the mixing recipe:

p(x) = a + bx + cx²

It says:

• p is merely the name of this mixer;
• p(x) means “the answer from the mixer when its setting is x”;
• bx is shorthand for b × x;
• cx² is shorthand for c × x × x;
• choose a value for x;
• multiply a by 1, b by x, and c by x²;
• add those three contributions;
• call the answer y and store the pair (x, y).

Think of x as the mixer's setting. At x = 1, the weights are [1, 1, 1]. At x = 2, they are [1, 2, 4]. Changing x changes the mixture without changing the original numbers. This is how one fixed block can produce more clues without merely copying itself.

Why choose 1, x and x²?

Start from the job the mixer must perform:

1. it must accept one simple label, x;
2. each new x must make a different mixture;
3. any three different labels must let the decoder separate a, b, and c;
4. the same recipe must keep working when we make a fourth, fifth, or sixth clue.

The powers 1, x, and x² meet those requirements:

• a gets the fixed weight 1, so it contributes the same baseline to every mixture;
• b gets x, so its contribution changes in direct proportion to the label;
• c gets x², so its contribution follows a different curve rather than a resized copy of x.

For example, compare the weights made by x = 1, 2, and 3:

No column is just a fixed multiple or copy of another column. That difference is what allows subtraction to remove one unknown at a time.

Now compare two tempting alternatives:

• [1, x, x] fails because bx + cx = (b+c)x; only the sum b+c survives;
• [1, x, 2x] also fails because bx + 2cx = (b+2c)x; again, only one combined value survives.

Why not choose some other third formula? Anything shaped like r + sx is still only a fixed part plus an x part:

a + bx + c(r + sx) = (a + cr) + (b + cs)x

That would hide three originals inside only two combined values. We choose x² because it is the simplest expression that cannot be folded into the existing 1 and x slots.

Other mixing recipes could work if they gave the same “any three labels can be undone” guarantee. Powers are useful because they extend the same construction without inventing a new rule: with three originals, use 1, x, x²; with four originals, add the next new shape x³; with five, add x⁴. Steps 15 and 16 now prove, rather than merely claim, that the three-slot version can be undone.

15. Prove that three clues identify only one block

The mixer looks plausible, but storage reliability cannot depend on plausibility. We need to rule out the dangerous case: two different source blocks producing the same three surviving clues. If that could happen, the decoder would have no way to choose the original.

Suppose two different blocks somehow produced the same clues at x = 1, 2, and 3. Subtract one block’s slots from the other block’s slots and call the differences A, B, and C.

Because the clue answers supposedly match, the differences must produce zero:

A + B + C = 0

A + 2B + 4C = 0

A + 3B + 9C = 0

Subtracting the first equation from the second gives B + 3C = 0. Subtracting the second from the third gives B + 5C = 0. Subtract those reduced equations and the B terms cancel:

2C = 0

In our reversible number system, multiplication by 2 has an undo, so 2C = 0 forces C = 0.

Put C = 0 into B + 3C = 0:

B + 3×0 = 0

B = 0

Put B = 0 and C = 0 into A + B + C = 0:

A + 0 + 0 = 0

A = 0

Why compare the difference between two possible blocks? Proving uniqueness directly would require listing every possible block. The difference turns the question into a simpler one: can any non-zero change to [a,b,c] leave all three clues unchanged? The calculation shows the only invisible change is [0,0,0], meaning no change at all.

The supposed blocks are therefore the same block. This is the guarantee we need: three correctly labelled clues made with these distinct x values leave one possible answer.

16. Show why any three different labels work

The previous proof only covered the first three labels. That is not yet enough for erasure protection: after arbitrary losses, the survivors might be x = 2, 4, and 6. The code promises any three different labels, so the proof must not depend on receiving 1, 2 and 3.

Call the three surviving labels r, s, and t. Suppose two blocks again produce the same three answers. Their slot differences A, B, and C must satisfy:

A + rB + r²C = 0

A + sB + s²C = 0

A + tB + t²C = 0

Subtract the r equation from the s equation:

(s−r)B + (s²−r²)C = 0

The difference of two squares can be factored:

s²−r² = (s−r)(s+r)

Expand the right-hand side to check it:

(s−r)(s+r) = s² + sr − rs − r²

sr and rs are the same multiplication, so +sr−rs=0. What remains is s²−r².

so:

(s−r)[B + (s+r)C] = 0

The labels s and r are different, so s−r is not zero. Every non-zero field value has an inverse. The notation (s−r)⁻¹ means “the field value that multiplies (s−r) to make 1”. Multiply both sides by it:

(s−r)⁻¹(s−r)[B + (s+r)C] = (s−r)⁻¹×0

The inverse pair on the left becomes 1, and any value multiplied by 0 remains 0:

B + (s+r)C = 0

Repeat the same work with the t and r equations:

B + (t+r)C = 0

Subtract the two reduced equations:

(t−s)C = 0

The labels t and s are also different, so t−s is non-zero and has an inverse. Therefore C = 0. Substitution then gives B = 0 and A = 0, exactly as in Step 15.

Why replace numbers with r, s, and t? They stand for whichever labels happened to survive. If the cancellation works without assigning them particular values, it proves the property for every permitted set rather than one convenient example.

Nothing in that reasoning required the labels to be consecutive. It required only that they were different, so their differences were non-zero and reversible. That proves any three correctly labelled survivors work.

17. Choose one x label

The rule is still only a recipe. To create an actual stored clue, we must select one concrete mixer setting. Use x = 2 for the first detailed calculation.

Why is choosing a label an operation at all? The label determines all three weights [1,x,x²] and is therefore part of the clue's meaning. There is nothing special about 2. We use the small labels 1 through 6 because they are distinct and make the arithmetic readable. Reusing an x within the same block would repeat the same weights and therefore repeat information instead of adding a replacement clue.

18. Substitute the chosen x value

We know which setting this clue will use, but the rule still contains the placeholder x. Replace every x in the rule with 2.

Why substitute before calculating? It converts the general recipe—which can describe many clues—into the one concrete calculation for this clue. Every x in the formula refers to the same setting, so replacing only one occurrence would mix two settings and produce a meaningless answer.

19. Calculate x²

After substitution, the c weight still contains an unfinished operation, 2². Calculate that weight before multiplying it by c:

x² = 2² = 2 × 2 = 4

Why calculate this separately? x² is not a new source value; it is the weight assigned to c at this label. Making the weight explicit as 4 lets the next step show exactly how much of c enters the clue. A computer could evaluate the expression in one line, but separating it prevents the source value, its weight and their product from being confused.

20. Calculate b’s contribution

For the default block, b = 50 and x = 2:

b × x = 50 × 2 = 100

Why multiply b by x? The changing weight is what makes the same b leave a different trace in each clue. If we added the plain value 50 every time, b would behave like the fixed a slot and the two could merge. At x = 2, the rule deliberately puts two copies of b into this total, so b contributes 100.

21. Calculate c’s contribution

For 42, the padded first block is [52, 50, 0], so c = 0. The c weight is x² = 4:

c × x² = 0 × 4 = 0

Why perform a multiplication whose answer is zero? The encoder follows one fixed recipe for every block; it cannot silently omit the third slot merely because this example contains padding. A longer input may put a non-zero byte there, and the decoder interprets every clue as containing all three weighted slots. The result happens to be zero here, but the operation defines what the clue means.

22. Add the three contributions

The a contribution is a × 1 = 52. Add all three:

52 + 100 + 0 = 152

Why combine the contributions into one number? We want each stored position to carry partial knowledge of the whole block, not a separately stored copy of one source value. Addition compresses the three weighted contributions into one field value. One such sum loses detail; several differently weighted sums restore it by providing several equations. Storing the three contributions separately would simply recreate three vulnerable source positions and would not be the code we are building.

23. Wrap the total into the field

The total 152 is already between 0 and 256:

152 = 0 × 257 + 152

152 mod 257 = 152

Why wrap every clue now? The stored symbol must stay inside the agreed 0–256 range. Letting some clues remain as large ordinary integers would give them a different representation and make later field operations inconsistent. For a larger total, subtracting complete groups of 257 gives the same field position. For example, 409 = 1×257 + 152, so 409 and 152 represent the same field value. Encoding and decoding both use this rule.

24. Store the labelled clue

Call the wrapped answer y. We chose x = 2 and calculated y = 152, so store:

(x, y) = (2, 152)

Why store a pair rather than only the answer? Recovery needs both the result and the recipe setting that produced it. The pair means “the mixer produced 152 using the weights belonging to x = 2”. Storing 152 without 2 would preserve a number but lose the information needed to recreate its equation.

25. Repeat until there are three clues

One completed clue gives one equation, but the block contains three unknown source values. Repeat Steps 17–24 with unused x labels until recovery has enough differently weighted equations.

Why stop at three for recovery? One clue is one equation containing three unknowns, so many blocks can fit it. Two clues still leave a free choice. Three clues made with different x labels provide exactly the information Steps 15–16 proved sufficient to isolate a, b, and c. Fewer cannot guarantee one answer; more are useful as replacements rather than as a stricter decoding requirement.

26. Watch two clues accept two different blocks

The previous step used the rule of thumb “two equations cannot fix three unknowns”. Rather than asking the reader to accept that count, construct the failure: two genuinely different blocks that produce the same answers at x = 1 and x = 2.

The alternative changes the slots by [+2, −3, +1]:

• at x = 1, the change in the answer is 2 − 3×1 + 1×1² = 0;
• at x = 2, the change is 2 − 3×2 + 1×2² = 2 − 6 + 4 = 0;
• at x = 3, the change is 2 − 9 + 9 = 2, not zero.

Why show a counterexample? It proves that refusing to decode from two clues is necessary, not conservative programming. The first two clues genuinely cannot distinguish the blocks. The third clue does.

27. Calculate three replacement clues

We now know three clues are enough when all three survive. That alone provides no protection: losing one would leave only two. To tolerate loss, calculate more valid clues than recovery needs, using x = 1 through x = 6.

The first three are not special. Recovery accepts any three with different labels. Six is a policy choice:

• 3 originals and 5 clues tolerate 2 missing clues;
• 3 originals and 6 clues tolerate 3 missing clues;
• 3 originals and 7 clues tolerate 4 missing clues.

Why are the extras mixtures instead of copies? Because any three differently labelled mixtures can replace any missing three. A copied source position would help only when that particular source value was lost. Each extra clue costs storage but increases the number of known losses the whole block can survive.

28. Arrange matching labels into shards

A longer input contains several separate three-number blocks. Each block produces six answers, but a storage system needs six coherent pieces it can place on separate drives or send along separate routes. We therefore organise answers by their shared x label.

A shard is the collection of answers that share one x label:

• shard x = 1 contains the x = 1 answer from every block;
• shard x = 2 contains the x = 2 answer from every block;
• the same pattern continues through x = 6.

Why group by label rather than keep each block together? If one stored piece contained all six clues for a particular source block, losing it would erase that block completely. Grouping one answer from every block into each shard spreads every block across all six storage pieces. Losing one whole shard then removes exactly one correctly labelled clue from every block, leaving the other labels available everywhere.

29. Erase three shards

The code has been designed to tolerate three known losses. Erase three whole shards now so the recovery walkthrough starts from the exact failure the design claims to survive, rather than quietly keeping the originals nearby.

Why erase whole shards rather than three isolated numbers? Real storage failures usually remove an entire device or packet, affecting every block it carried. Each block started with six clues; losing three shards leaves three differently labelled clues for each block. Steps 15–16 proved that any three identify only one block. Losing a fourth shard would leave only two clues per block and reintroduce the ambiguity shown in Step 26.

Decode one block by hand

We have finished encoding and deliberately removed three shards. The remaining task is to turn three labelled totals back into the three source positions.

The real byte values make a paper example needlessly awkward without changing the method. Use the small block [4, 2, 3] in the 17-position rehearsal instead. Its rule is:

p(x) = 4 + 2x + 3x² mod 17

Calculate the three surviving clues:

• at x = 1: 4 + 2×1 + 3×1² = 4 + 2 + 3 = 9, so store (1, 9);
• at x = 2: 4 + 2×2 + 3×2² = 4 + 4 + 12 = 20, and 20 mod 17 = 3, so store (2, 3);
• at x = 3: 4 + 2×3 + 3×3² = 4 + 6 + 27 = 37, and 37 mod 17 = 3, so store (3, 3).

The repeated answer y = 3 is safe because its labels differ. (2,3) and (3,3) describe different equations.

Why switch examples? The purpose of this section is to expose every recovery operation, not to practise large multiplication. The smaller field makes negative values, wrapping and inverses visible on paper. The full automatic component later runs the same structure on the user's real bytes in the 257-position field.

Pretend only those three clues survived. We will now recover [4, 2, 3] while treating its values as unknown.

30. Turn each surviving clue into an equation

The pair (1, 9) says “putting x = 1 into the lost rule produced 9”:

a + b + c = 9

The pair (2, 3) says:

a + 2b + 4c = 3

The pair (3, 3) says:

a + 3b + 9c = 3

Why turn pairs into equations? The stored pairs are not the source bytes; each is a combined total plus the label describing how it was made. Substitution expands that compact record back into a true statement about the missing positions. It turns the vague task “recover the data” into a concrete one: find a, b and c that make all three surviving statements true.

Why use all three now? Each equation still contains all three unknowns. No single one identifies the block. Their value comes from being solved together.

31. Subtract Equation 1 from Equation 2

Write Equation 2 minus Equation 1:

(a + 2b + 4c) − (a + b + c) = 3 − 9

Term by term:

• a − a = 0;
• 2b − b = b;
• 4c − c = 3c;
• 3 − 9 = -6.

The raw result is:

b + 3c = -6

Why this pair, in this order? Any two equations could be combined, but Equations 1 and 2 have small weights and both contain exactly one a. Computing Equation 2 minus Equation 1 creates a−a=0 and removes one unknown without guessing. Reversing the order would also work, but it would negate every remaining term.

32. Wrap -6 to 11

The field uses representatives from 0 to 16. Add one complete lap of 17:

-6 + 17 = 11

Therefore:

b + 3c = 11

Why wrap at this point? -6 is mathematically usable, but every later lookup and inverse in this toy is written using the standard representatives 0–16. Converting now keeps every equation in the same number system and makes later comparisons direct.

Why is adding 17 allowed? In mod 17, numbers separated by a whole lap represent the same position. -6, 11, and 28 all name the same field value. We changed its written representative, not the information in the equation.

33. Subtract Equation 2 from Equation 3

Write:

(a + 3b + 9c) − (a + 2b + 4c) = 3 − 3

Term by term:

• a − a = 0;
• 3b − 2b = b;
• 9c − 4c = 5c;
• 3 − 3 = 0.

The result is:

b + 5c = 0

Why repeat almost the same subtraction? The first reduced equation still contains two unknowns, b and c; many pairs can satisfy it. We need a second, differently weighted relationship between those same two unknowns. Using adjacent original equations removes a again and keeps the remaining numbers small.

34. Subtract the reduced equations to remove b

We now have:

b + 3c = 11

b + 5c = 0

Subtract the first from the second.

Term by term:

• b − b = 0;
• 5c − 3c = 2c;
• 0 − 11 = -11.

The raw result is:

2c = -11

Why subtract again? The two reduced equations were deliberately constructed with the same amount of b: one copy each. Subtraction turns b−b into zero. This is not a generic instruction to keep subtracting; it is a targeted operation chosen because the terms we want to remove match exactly.

35. Wrap -11 to 6

Add one complete lap of 17:

-11 + 17 = 6

Therefore:

2c = 6

Why is this another separate step? The subtraction isolated c, but its right-hand side is outside the agreed 0–16 representation. Wrapping restores the standard field value before we search for an operation that undoes the remaining ×2.

36. Find the operation that undoes ×2

In ordinary arithmetic we would divide both sides by 2. Inside the 17-position loop, division means multiplying by the number that undoes ×2.

That number is 9 because:

2 × 9 = 18

18 mod 17 = 1

We find it by testing the allowed non-zero values. Multiplying 2 by 1 through 8 gives the remainders 2, 4, 6, 8, 10, 12, 14 and 16. None is 1. Multiplying by 9 gives 18, which wraps to 1.

Why can we not use ordinary 6 ÷ 2 = 3 and move on? That happens to produce the same answer in this example, but ordinary division is not defined for every wrapped intermediate in the way we need. The decoder requires one rule that remains inside the field and works for every non-zero multiplier. Multiplying by the field inverse is that rule.

The number 9 is called the multiplicative inverse of 2. Multiplying by it is the field equivalent of dividing by 2 because it changes the number multiplying c from 2 into 1 after wrapping.

37. Multiply both sides by 9 to recover c

Start with:

2c = 6

Multiply both sides by 9:

2c × 9 = 6 × 9

On the left:

2 × 9 = 18

18 mod 17 = 1

so 18c becomes 1c. Another way to see it is 18c = 17c + c: the 17c part is a whole number of 17-position laps, leaving only c.

On the right:

6 × 9 = 54

54 = 3×17 + 3

54 mod 17 = 3

Therefore c = 3.

Why multiply both sides? Our goal is to turn 2c into 1c, but changing only the left side would make the equation false. Applying the inverse to both sides preserves equality while removing the unwanted multiplier from c. This is the same balancing rule used in ordinary school equations, with field multiplication replacing division.

38. Substitute c = 3 into the b equation

Return to:

b + 3c = 11

Replace c with the value we just recovered.

b + 3×3 = 11

Why return to b + 3c = 11? That reduced equation contains only b and c, so inserting the newly known c leaves one unknown immediately. Returning to an original three-unknown equation would also work, but would do unnecessary work.

This is substitution: a solved letter is replaced by its known value. The equation now contains only b.

39. Calculate the known multiplication

3 × 3 = 9

so:

b + 9 = 11

Why calculate 3×3 before moving anything? The term is now entirely known, so reducing it to 9 makes the remaining equation's structure visible: an unknown b plus a known 9 equals 11. We have not changed sides or guessed; we have only evaluated a completed multiplication.

40. Subtract 9 from both sides to recover b

b + 9 − 9 = 11 − 9

On the left, +9−9=0. On the right, 11−9=2. Therefore:

b = 2

Why subtract 9? The operation immediately beside b is +9, so its inverse operation is −9. Applying it to both sides preserves equality. Choosing a different number would not cancel the known term; subtracting only on the left would break the equation.

41. Substitute b and c into the first equation

Return to:

a + b + c = 9

Replace b with 2 and c with 3:

a + 2 + 3 = 9

Why go back to the first equation? We have recovered b and c, and any original clue could now reveal a. The first has the smallest weights—one copy of each value—so it requires the least arithmetic. Substitution turns the stored clue back into an equation with only a unknown.

42. Add the known terms beside a

2 + 3 = 5

so:

a + 5 = 9

Why combine 2 and 3? Both are now known contributions on the same side. Replacing them with their sum does not move anything or alter the equation; it exposes the single operation, +5, that still needs to be undone to isolate a.

43. Subtract 5 from both sides to recover a

a + 5 − 5 = 9 − 5

On the left, +5−5=0. On the right, 9−5=4. Therefore:

a = 4

The recovered block is [a,b,c] = [4,2,3].

Why does this finish recovery? a was the only remaining unknown. Subtracting the known +5 from both sides preserves equality and leaves its unique value. We now have values for all three original positions, in their original order.

44. Re-encode the result to check it

Solving several equations by hand creates opportunities for a sign, multiplication or wrapping mistake. Before trusting the candidate block, put [4, 2, 3] through the encoder again at x = 1, 2 and 3. It reproduces 9, 3 and 3, so the recovered block satisfies every clue we received.

Why does matching the clues matter? The decoder's contract is not “produce three plausible numbers”; it is “produce the unique block described by every survivor”. Re-encoding checks that contract. The uniqueness proof in Steps 15–16 tells us that another different block cannot also pass.

This hand method is equation elimination. Software can rearrange and precompute parts of the same algebra for speed, but it is still solving the same problem.

45. Remove padding and decode the bytes as text

The algebra has recovered numbered block positions, not yet the user's text. Recover every three-number block and join their values in the original order. Then keep exactly the recorded number of real bytes from Step 3; do not guess which zeros are padding.

Why reverse these preparation steps in this order? Encoding first converted text to bytes, recorded the length, and then added padding and blocks. Decoding must undo that packaging in reverse: rebuild blocks, restore byte order, remove positions beyond the saved length, then reverse UTF-8. Decoding UTF-8 before removing padding could introduce an extra null character; stripping every zero could delete real data.

Finally, run the remaining bytes through the UTF-8 decoder. [52,50] returns 42.

46. Distinguish a missing shard from a wrong shard

Everything so far assumed an erasure: we knew exactly which shard was unavailable. A real system may instead receive an error, where a shard supplies a wrong value and pretends it is valid. These are different recovery problems and consume different spare capacity.

Why does one hidden error cost roughly as much as two known erasures? With an erasure, the location is already supplied; the decoder solves only for the missing value. With an error, it must solve two unknown facts: which position is wrong and what value belongs there. The extra clues must identify the liar before they can replace it. That is why correcting one unknown error generally costs the same spare capacity as tolerating two known erasures.

The complete automatic run

The separate lessons deliberately froze one question at a time. The final workbench now reconnects them so the reader can see where each intermediate value goes and why the next operation receives it.

It has 38 stages because substitution, multiplication, wrapping, cancellation and balancing remain separate operations. Each stage stays visible for five seconds. Pause it or choose a numbered stage when you want more time.

Why repeat the whole run? Understanding each operation separately is not the same as understanding the pipeline. The combined view shows that no unexplained value enters and no required information disappears: the user's text becomes bytes, blocks, labelled clues, survivors, equations, recovered bytes and finally the same text.

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 labelled clues, then use any three surviving clues to rebuild the source numbers.

Sources

• Reed and Solomon, “Polynomial Codes Over Certain Finite Fields” (1960)
• RFC 5510: Reed–Solomon Forward Error Correction
• CMU coding theory notes: Reed–Solomon codes and interpolation
• Stanford notes: Introduction to finite fields