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}~. \tag*{(1)}\end{align} Error correction can then be applied to each packet.
Protection
Designed to protect against erasures during broadcasting of information by a sender to multiple receivers.Rate
Random linear fountain codes approach the Shannon limit as the file size \(K\) increases. However, they do not have a fixed encoding rate.Decoding
Invert the fragment generator matrix resulting from the continuous encoding process. If exactly \(K\) packets are received, then the probability of decoding correctly is \(0.289\). Extra packets increase this probability exponentially. The decoding runtime is dominated by the matrix inversion step, which takes order \(O(n^3)\) time.Realizations
Designed for servers sending data to many recipients, such as during broadcasting or file distribution [2,3].DNA storage [4].Cousins
- Random code
- Distributed-storage code— There are proposals [8,9] adapting fountain codes to distributed storage systems.
- 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 [2,6].
Primary Hierarchy
References
- [1]
- J. W. Byers, M. Luby, M. Mitzenmacher, and A. Rege, “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]
- E. Baik, A. Pande, and P. Mohapatra, “Cross-layer coordination for efficient contents delivery in LTE eMBMS traffic”, 2012 IEEE 9th International Conference on Mobile Ad-Hoc and Sensor Systems (MASS 2012) 398 (2012) DOI
- [4]
- Y. Erlich and D. Zielinski, “DNA Fountain enables a robust and efficient storage architecture”, Science 355, 950 (2017) DOI
- [5]
- D. J. C. MacKay, “Fountain codes”, IEE Proceedings - Communications 152, 1062 (2005) DOI
- [6]
- Joshi, G., Rhim, J. B., Sun, J., & Wang, D. (2010). Fountain codes. In Global telecommunications conference (GLOBECOM 2010) (pp. 7–12). IEEE.
- [7]
- I. F. Blake, Essays on Coding Theory (Cambridge University Press, 2024) DOI
- [8]
- M. Asteris and A. G. Dimakis, “Repairable Fountain Codes”, (2014) arXiv:1401.0734
- [9]
- M. G. Luby, R. Padovani, T. J. Richardson, L. Minder, and P. Aggarwal, “Liquid Cloud Storage”, (2017) arXiv:1705.07983
Page edit log
- Victor V. Albert (2022-07-15) — most recent
- Noah Berthusen (2022-02-25)
Cite as:
“Fountain code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/fountain