Fountain code[1]
Description
Code based on the idea of generating an endless stream of custom encoded packets for the receiver. The code is designed so that the receiver can recover the original transmission of size \(Kl\) bits after receiving at least \(K\) packets each of \(l\) bits.
The simplest example of a fountain code is the random linear fountain code. Take some message of size \(Kl\) and split into \(K\) packets, \(p_0, p_1, ..., p_K\). For each packet \(\hat{p}_n\) to be transmitted do the following: Generate \(K\) random bits \(G_{nk}\) and let \(\hat{p}_n\) be the bitwise sum of the source packets when \(G_{nk}\) is 1, \begin{align} \hat{p}_n = \sum_{k=1}^K p_k G_{kn}~. \end{align} Error correction can then be applied to each packet.
Protection
Rate
Decoding
Realizations
Notes
Parent
Child
Cousins
- Random code
- Tornado code — Tornado codes, the precursor to fountain codes, are much slower to encode and decode in the low-rate regime applicable to scalable data transmission [4][2].
Zoo code information
References
- [1]
- J. W. Byers et al., “A digital fountain approach to reliable distribution of bulk data”, ACM SIGCOMM Computer Communication Review 28, 56 (1998). DOI
- [2]
- A. Shokrollahi, “Raptor codes”, IEEE Transactions on Information Theory 52, 2551 (2006). DOI
- [3]
- D. J. C. MacKay, “Fountain codes”, IEE Proceedings - Communications 152, 1062 (2005). DOI
- [4]
- Joshi, G., Rhim, J. B., Sun, J., & Wang, D. (2010). Fountain codes. In Global telecommunications conference (GLOBECOM 2010) (pp. 7–12). IEEE.
Cite as:
“Fountain code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/fountain
Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/bits/fountain.yml.