Information AboutFountain Codes |
|
Fountain codes are also known as rateless erasure codes. A Fountain code is optimal if the original ''k'' source symbols can be recovered from any ''k'' encoding symbols. Fountain codes are known that have efficient encoding and decoding algorithms and that allow the recovery of the original ''k'' source symbols from any ''k’'' of the encoding symbols with high probability, where ''k’'' is just slightly larger than k. PRACTICAL CONSIDERATIONS In practical simulations, for relatively short , say less than , the overhead that is is non trivial. With the short , both LT and Raptor codes by BP algorithm never reach the overhead . It should be emphasized that the advantage of Raptor and Online codes is valid the BP algorithm over a check matrix (or triangularization of a check matrix ) can recover most of input symbols. This is a critical drawback of fountain codes. If a Raptor or Onlice code is going to recover most of the input symbols, say more than 95%, then pre-encoding is not necessary because, transimitting a couple of tens of dense encoding symbols can cover up all the input symbols with an extremely high probability (called Union Bound). The extra dense encoding symbols also contributes to the remained matrix of having its full column rank. And thus, the unrecovered symbols can be solved by Gaussian Elimination via Pivotting Strategy over the remain graph. The check equations of dense encoding symbols can be communicated to receivers by applying the same random degree generators of a sender. EXAMPLES OF FOUNTAIN CODES EXTERNAL LINKS J. Byers, M. Luby, M: Mitzenmacher and A. Rege, " A Digital Fountain Approach to Reliable Distribution of Bulk Data ", Proceedings of ACM Sigcomm '98, Vancouver, Canada, September 1998. |
|
|