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
- Amin Shokrollahi. Raptor Codes. IEEE TIT 52(6), 2551-2567 (2006), sections III-IV. DOI: 10.1109/TIT.2006.874390.
- RFC 6330 (2011): RaptorQ, sections 5.3.1, 5.8 and 6.
- Hesela: exact synthetic XOR equation, rank and peeling observations
- Hesela: worked decoding example and reproduction instructions
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.