fountain-code · shipping · also Rateless erasure code

Fountain code

A fountain code generates additional encoding symbols on demand from a source block, allowing receivers to recover the block from a sufficiently informative received set.

Rateless describes how redundancy is generated, not a guarantee that any k received symbols recover k inputs. LT codes mix selected inputs by XOR; Raptor constructions add a precode before the LT stage. The precode permits recovery of inputs that the LT stage leaves unresolved. Degree distribution, decoding algorithm and reception overhead affect recovery. [1]

RFC 6330 specifies the distinct, systematic RaptorQ scheme. For supported extended block sizes K', its decoder requirements bound average failure by 1/100, 1/10,000 and 1/1,000,000 at K', K'+1 and K'+2 received symbols respectively, with encoding-symbol identifiers sampled independently and uniformly. K' is the supported padded block size, not automatically the original K. These are conditional requirements, not universal disk-loss probabilities. [2]

In Hesela's three-input example, three distinct XOR equations can have rank two. Another three-equation set has full rank but no degree-one equation, so pure peeling stalls. An added singleton starts recovery without increasing rank. Receiving more equations, gaining independent information and enabling a particular decoder are separate events. [3]

Relations

related
Erasure coding, LT code, Maximum distance separable code, Rateless IBLT, Raptor code, RaptorQ

Limitations

  • Erasure recovery does not authenticate symbols or detect every corruption; protect the object and its decoding metadata separately. [2]
  • The linked calculation is a constructed binary-matrix demonstration, not an LT degree-distribution simulation or a RaptorQ implementation. [4]

Citations

  1. Amin Shokrollahi. Raptor Codes. IEEE TIT 52(6), 2551-2567 (2006), sections III-IV. DOI: 10.1109/TIT.2006.874390. (accessed 2026-11-21)
  2. RFC 6330 (2011): RaptorQ, sections 5.3.1, 5.8 and 6. (accessed 2026-11-21)
  3. Hesela: exact synthetic XOR equation, rank and peeling observations (accessed 2026-11-21)
  4. Hesela: worked decoding example and reproduction instructions (accessed 2026-11-21)
Sources & caveats
  • The 2006 paper gives code constructions and mathematical analysis; RFC 6330 gives a later interoperable scheme. Neither is treated as a storage-fleet measurement.
  • The example uses fixed, explicitly listed coefficient rows and known-correct equations from one source block.

JSON: /data/terms/fountain-code.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Fountain code. Hesela. 2026-11-21. https://hesela.dev/terms/fountain-code/