224:
needed to achieve the initial level of redundancy. In that respect, fountain codes are expected to allow efficient repair process in case of a failure: When a single encoded symbol is lost, it should not require too much communication and computation among other encoded symbols in order to resurrect the lost symbol. In fact, repair latency might sometimes be more important than storage space savings. Repairable fountain codes are projected to address fountain code design objectives for storage systems. A detailed survey about fountain codes and their applications can be found at.
198:
1,000 source symbols, and has a relative reception overhead of less than 2% with probability 99.9999%. The relative reception overhead is defined as the extra encoding data required beyond the length of the source data to recover the original source data, measured as a percentage of the size of the source data. For example, if the relative reception overhead is 0.2%, then this means that source data of size 1
128:: it must successfully receive an encoding symbol which it does not already have. This problem becomes much more apparent when using a traditional short-length erasure code, as the file must be split into several blocks, each being separately encoded: the receiver must now collect the required number of missing encoding symbols for
197:
for delivering commercial TV services over an IP network. This code can be used with up to 8,192 source symbols in a source block, and a total of up to 65,536 encoded symbols generated for a source block. This code has an average relative reception overhead of 0.2% when applied to source blocks with
136:
subset of encoding symbols of size slightly larger than the set of source symbols. (In practice, the broadcast is typically scheduled for a fixed period of time by an operator based on characteristics of the network and receivers and desired delivery reliability, and thus the fountain code is used at
218:
Erasure codes are used in data storage applications due to massive savings on the number of storage units for a given level of redundancy and reliability. The requirements of erasure code design for data storage, particularly for distributed storage applications, might be quite different relative to
223:
enables reading off the message symbols without decoding from a storage unit. In addition, since the bandwidth and communication load between storage nodes can be a bottleneck, codes that allow minimum communication are very beneficial particularly when a node fails and a system reconstruction is
232:
RFC 6330 (which provides significantly better data protection than other systems), using a background repair process (which significantly reduces the repair bandwidth requirements compared to other systems), and using a stream data organization (which allows fast access to data even when not all
209:
RFC 6330. The specified RaptorQ code can be used with up to 56,403 source symbols in a source block, and a total of up to 16,777,216 encoded symbols generated for a source block. This code is able to recover a source block from any set of encoded symbols equal to the number of source
43:
symbols can be generated from a given set of source symbols such that the original source symbols can ideally be recovered from any subset of the encoding symbols of size equal to or only slightly larger than the number of source symbols. The term
210:
symbols in the source block with high probability, and in rare cases from slightly more than the number of source symbols in the source block. The RaptorQ code is an integral part of the ROUTE instantiation specified in ATSC A-331 (ATSC 3.0)
227:
A different approach to distributed storage using fountain codes has been proposed in Liquid Cloud
Storage. Liquid Cloud Storage is based on using a large erasure code such as the RaptorQ code specified in
219:
communication or data streaming scenarios. One of the requirements of coding for data storage systems is the systematic form, i.e., the original message symbols are part of the coded symbols.
359:
T. Stockhammer, A. Shokrollahi, M. Watson, M. Luby, T. Gasiba (March 2008). Furht, B.; Ahson, S. (eds.). "Application Layer
Forward Error Correction for Mobile Multimedia Broadcasting".
321:
124:, where some large file is continuously broadcast to a set of receivers. Using a fixed-rate erasure code, a receiver missing a source symbol (due to a transmission error) faces the
746:
706:
378:
307:
163:
are the most efficient fountain codes at this time, having very efficient linear time encoding and decoding algorithms, and requiring only a small constant number of
67:
successfully received encoding symbols (i.e., excluding those that were erased). Fountain codes are known that have efficient encoding and decoding
325:
117:, or where a fixed code rate cannot be determined a priori, and where efficient encoding and decoding of large amounts of data is required.
769:
665:
577:
205:
A more advanced Raptor code with greater flexibility and improved reception overhead, called RaptorQ, has been specified in
186:
125:
458:
Luby, Michael; Padovani, Roberto; Richardson, Thomas J.; Minder, Lorenz; Aggarwal, Pooja (2019). "Liquid Cloud
Storage".
190:
764:
102:
372:
247:
628:
653:
286:
137:
a code rate that is determined dynamically at the time when the file is scheduled to be broadcast.)
290:
643:
615:
583:
545:
504:
503:
Luby, M.; Padovani, R.; Richardson, T.; Minder, L.; Aggarwal, P. (2017). "Liquid Cloud
Storage".
485:
467:
438:
419:
401:
145:
175:
Raptor code, which has been adopted into multiple standards beyond the IETF, such as within the
740:
700:
661:
573:
301:
727:
719:
687:
679:
647:
607:
595:
565:
537:
477:
411:
148:
scenarios: parity information that is requested by a receiver can potentially be useful for
220:
172:
657:
437:
Arslan, Suayb S. (2014). "Incremental
Redundancy, Fountain Codes and Advanced Topics".
252:
758:
257:
121:
32:
20:
619:
562:
The 43rd Annual IEEE Symposium on
Foundations of Computer Science, 2002. Proceedings
715:
675:
587:
557:
549:
423:
282:
242:
164:
98:
94:
489:
392:
Asteris, Megasthenis; Dimakis, Alexandros G. (2012). "Repairable
Fountain Codes".
160:
569:
141:
415:
611:
364:
114:
101:
were subsequently introduced, and achieve linear time encoding and decoding
68:
53:
199:
194:
90:
40:
36:
541:
732:
692:
509:
132:
block. Using a fountain code, it suffices for a receiver to retrieve
481:
472:
291:"A Digital Fountain Approach to Reliable Distribution of Bulk Data"
443:
406:
183:
361:
Handbook of Mobile
Broadcasting: DVB-H, DMB, ISDB-T and Media FLO
182:
standard for broadcast file delivery and streaming services, the
229:
206:
179:
176:
168:
167:
operations per generated symbol for both encoding and decoding.
530:
202:
can be recovered from 1.002 megabytes of encoding data.
724:
RaptorQ Forward Error
Correction Scheme for Object Delivery
52:
refers to the fact that these codes do not exhibit a fixed
684:
Raptor Forward Error Correction Scheme for Object Delivery
528:
Amin Shokrollahi and Michael Luby (2011). "Raptor Codes".
93:
were the first practical realization of fountain codes.
322:"Qualcomm Raptor Technology - Forward Error Correction"
649:
Information Theory, Inference, and Learning Algorithms
79:
of the encoding symbols with high probability, where
722:, M. Watson, T. Stockhammer, L. Minder (May 2011),
113:Fountain codes are flexibly applicable at a fixed
105:through a pre-coding stage of the input symbols.
394:IEEE Journal on Selected Areas in Communications
35:with the property that a potentially limitless
8:
745:: CS1 maint: multiple names: authors list (
705:: CS1 maint: multiple names: authors list (
682:, M. Watson, T. Stockhammer (October 2007),
377:: CS1 maint: multiple names: authors list (
306:: CS1 maint: multiple names: authors list (
71:and that allow the recovery of the original
346:
59:A fountain code is optimal if the original
731:
691:
508:
471:
442:
405:
189:standard for delivering IP services over
63:source symbols can be recovered from any
600:IEEE Transactions on Information Theory
273:
738:
698:
370:
299:
7:
152:receivers in the multicast group.
14:
536:(3–4). Now Publishers: 213–322.
233:encoded symbols are available).
627:P. Maymounkov (November 2002).
171:RFC 5053 specifies in detail a
140:Another application is that of
16:Class of codes in coding theory
652:. Cambridge University Press.
1:
83:is just slightly larger than
324:. 2014-05-30. Archived from
460:ACM Transactions on Storage
786:
770:Capacity-approaching codes
126:coupon collector's problem
570:10.1109/sfcs.2002.1181950
120:One example is that of a
598:(2006), "Raptor Codes",
416:10.1109/JSAC.2014.140522
75:source symbols from any
612:10.1109/tit.2006.874390
29:rateless erasure codes
248:Linear network coding
564:. pp. 271–282.
560:(2002). "LT codes".
658:2003itil.book.....M
260:, the precursor to
644:David J. C. MacKay
636:(Technical Report)
542:10.1561/0100000060
289:, A. Rege (1998).
146:reliable multicast
31:) are a class of
777:
750:
744:
736:
735:
710:
704:
696:
695:
671:
639:
633:
622:
606:(6): 2551–2567,
591:
553:
515:
514:
512:
500:
494:
493:
475:
455:
449:
448:
446:
434:
428:
427:
409:
400:(5): 1037–1047.
389:
383:
382:
376:
368:
356:
350:
347:Shokrollahi 2006
343:
337:
336:
334:
333:
318:
312:
311:
305:
297:
295:
278:
214:For data storage
785:
784:
780:
779:
778:
776:
775:
774:
755:
754:
737:
714:
697:
674:
668:
642:
631:
626:
594:
580:
556:
527:
524:
519:
518:
502:
501:
497:
482:10.1145/3281276
457:
456:
452:
436:
435:
431:
391:
390:
386:
369:
358:
357:
353:
344:
340:
331:
329:
320:
319:
315:
298:
293:
287:M. Mitzenmacher
280:
279:
275:
270:
239:
221:Systematic form
216:
158:
111:
27:(also known as
17:
12:
11:
5:
783:
781:
773:
772:
767:
757:
756:
753:
752:
720:A. Shokrollahi
712:
680:A. Shokrollahi
672:
666:
640:
629:"Online Codes"
624:
596:A. Shokrollahi
592:
578:
554:
523:
520:
517:
516:
495:
450:
429:
384:
351:
338:
313:
272:
271:
269:
266:
265:
264:
262:fountain codes
255:
253:Secret sharing
250:
245:
238:
235:
215:
212:
193:networks, and
157:
154:
110:
107:
25:fountain codes
15:
13:
10:
9:
6:
4:
3:
2:
782:
771:
768:
766:
765:Coding theory
763:
762:
760:
748:
742:
734:
729:
725:
721:
717:
713:
708:
702:
694:
689:
685:
681:
677:
673:
669:
667:0-521-64298-1
663:
659:
655:
651:
650:
645:
641:
637:
630:
625:
621:
617:
613:
609:
605:
601:
597:
593:
589:
585:
581:
579:0-7695-1822-2
575:
571:
567:
563:
559:
558:Luby, Michael
555:
551:
547:
543:
539:
535:
531:
526:
525:
521:
511:
506:
499:
496:
491:
487:
483:
479:
474:
469:
465:
461:
454:
451:
445:
440:
433:
430:
425:
421:
417:
413:
408:
403:
399:
395:
388:
385:
380:
374:
366:
362:
355:
352:
348:
342:
339:
328:on 2010-12-29
327:
323:
317:
314:
309:
303:
292:
288:
284:
277:
274:
267:
263:
259:
258:Tornado codes
256:
254:
251:
249:
246:
244:
241:
240:
236:
234:
231:
225:
222:
213:
211:
208:
203:
201:
196:
192:
188:
185:
181:
178:
174:
170:
166:
162:
155:
153:
151:
147:
143:
138:
135:
131:
127:
123:
122:data carousel
118:
116:
108:
106:
104:
100:
96:
92:
88:
86:
82:
78:
74:
70:
66:
62:
57:
55:
51:
47:
42:
38:
34:
33:erasure codes
30:
26:
22:
21:coding theory
723:
683:
648:
635:
603:
599:
561:
533:
529:
510:1705.07983v1
498:
463:
459:
453:
432:
397:
393:
387:
373:cite journal
360:
354:
341:
330:. Retrieved
326:the original
316:
276:
261:
243:Online codes
226:
217:
204:
161:Raptor codes
159:
156:In standards
149:
139:
133:
129:
119:
112:
109:Applications
99:online codes
95:Raptor codes
89:
84:
80:
76:
72:
64:
60:
58:
49:
45:
28:
24:
18:
759:Categories
522:References
473:1705.07983
332:2011-06-07
281:J. Byers,
173:systematic
142:hybrid ARQ
103:complexity
69:algorithms
444:1402.6016
407:1401.0734
365:CRC Press
115:code rate
54:code rate
741:citation
701:citation
646:(2003).
620:61814971
466:: 1–49.
302:cite web
237:See also
200:megabyte
195:DVB-IPTV
91:LT codes
50:rateless
46:fountain
41:encoding
37:sequence
716:M. Luby
676:M. Luby
654:Bibcode
588:1861068
550:1731099
424:1300984
283:M. Luby
730:
690:
664:
618:
586:
576:
548:
490:738764
488:
422:
632:(PDF)
616:S2CID
584:S2CID
546:S2CID
505:arXiv
486:S2CID
468:arXiv
439:arXiv
420:S2CID
402:arXiv
294:(PDF)
268:Notes
184:DVB-H
747:link
733:6330
707:link
693:5053
662:ISBN
574:ISBN
379:link
308:link
230:IETF
207:IETF
187:IPDC
180:MBMS
177:3GPP
169:IETF
130:each
97:and
728:RFC
688:RFC
608:doi
566:doi
538:doi
478:doi
412:doi
191:DVB
165:XOR
150:all
144:in
134:any
48:or
39:of
19:In
761::
743:}}
739:{{
726:,
718:,
703:}}
699:{{
686:,
678:,
660:.
634:.
614:,
604:52
602:,
582:.
572:.
544:.
532:.
484:.
476:.
464:15
462:.
418:.
410:.
398:32
396:.
375:}}
371:{{
363:.
304:}}
300:{{
285:,
87:.
81:k’
77:k’
56:.
23:,
751:.
749:)
711:.
709:)
670:.
656::
638:.
623:.
610::
590:.
568::
552:.
540::
534:6
513:.
507::
492:.
480::
470::
447:.
441::
426:.
414::
404::
381:)
367:.
349:)
345:(
335:.
310:)
296:.
85:k
73:k
65:k
61:k
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.