29:
131:
376:
Two approaches are possible for decoding Raptor codes. In a concatenated approach, the inner code is decoded first, using a belief propagation algorithm, as used for the LT codes. Decoding succeeds if this operation recovers a sufficient number of symbols, such that the outer code can recover the
349:
This distribution, as well as the mechanism for generating pseudo-random numbers for sampling this distribution and for choosing the symbols to be XOR'ed, must be known to both sender and receiver. In one approach, each symbol is accompanied with an identifier which can be used as a seed to a
291:
RFC 6330. The RaptorQ code is a systematic code, can be implemented in a way to achieve linear time encoding and decoding performance, has near-optimal recovery properties, supports up to 56,403 source symbols, and can support an essentially unlimited number of encoding symbols.
345:
of a pseudo-randomly chosen set of symbols from the pre-code output. The number of symbols which are XOR'ed together to form an output symbol is chosen pseudo-randomly for each output symbol according to a specific probability distribution.
322:, usually with a fairly high rate, is applied as a 'pre-code' or 'outer code'. This pre-code may itself be a concatenation of multiple codes, for example in the code standardized by 3GPP a high density parity check code derived from the
303:) standard to enable high quality broadcast video streaming (robust mobile TV) and efficient and reliable broadcast file delivery (datacasting). In particular, the RaptorQ code is specified in A/331 within ATSC 3.0. See
380:
In a combined approach, the relationships between symbols defined by both the inner and outer codes are considered as a single combined set of simultaneous equations which can be solved by the usual means, typically by
426:
encoding symbols are received.) The recovery probability is the probability that the source block is completely recovered upon receiving a given number of random encoding symbols generated from the source block.
233:
or more encoding symbols allows the source block to be recovered with some non-zero probability. The probability that the source block can be recovered increases with the number of encoding symbols received above
417:
of source symbols in the original source block need to be received to completely recover the source block. (Based on elementary information theory considerations, complete recovery of a source block with
257:. In the systematic case, the symbols of the original source block, i.e. the source symbols, are included within the set of encoding symbols. Some examples of a systematic Raptor code is the use by the
360:
output symbols to the source data. Thus, applying the normal encoding operation to the resulting symbols causes the original source symbols to be regenerated as the first
307:
for a list of the ATSC 3.0 standard parts. Next Gen TV (ATSC 3.0) goes well-beyond traditional TV to provide a
Broadcast internet enabling general data delivery services.
356:
In the case of systematic Raptor codes, the input to the pre-coding stage is obtained by first applying the inverse of the encoding operation that generates the first
250:
encoding symbols have been received is less than one in a million. A symbol can be any size, from a single byte to hundreds or thousands of bytes.
214:
in 2000/2001 and were first published in 2004 as an extended abstract. Raptor codes are a significant theoretical and practical improvement over
337:
The inner code takes the result of the pre-coding operation and generates a sequence of encoding symbols. The inner code is a form of
568:
350:
pseudo-random number generator to generate this information, with the same process being followed by both sender and receiver.
496:. The MPEG DASH standard has been deployed by a wide variety of companies, including DASH Industry Forum member companies.
493:
93:
353:
In the case of non-systematic Raptor codes, the source data to be encoded is used as the input to the pre-coding stage.
65:
258:
170:
112:
72:
242:. For example, with the latest generation of Raptor codes, the RaptorQ codes, the chance of decoding failure when
229:
of equal size source symbols into a potentially limitless sequence of encoding symbols such that reception of any
141:
686:
680:
364:
output symbols of the code. It is necessary to ensure that the pseudo-random processes which generate the first
50:
547:
327:
79:
225:
Raptor codes, as with fountain codes in general, encode a given source block of data consisting of a number
46:
238:
becoming very close to 1, once the number of received encoding symbols is only very slightly larger than
492:
RFC 6330. These statements mirror the licensing commitment
Qualcomm, Inc. has made with respect to the
61:
262:
148:
269:
for IP datacast to handheld devices. The Raptor codes used in these standards is also defined in
39:
17:
702:
656:
304:
632:
3GPP Technical
Specification for Multimedia Broadcast/Multicast Service: Protocols and Codecs.
246:
encoding symbols have been received is less than 1%, and the chance of decoding failure when
569:
ATSC Candidate
Standard: Signaling, Delivery, Synchronization, and Error Protection (A/331)
382:
323:
434:
RFC 6330 has the following trade-off between recovery probability and recovery overhead:
8:
86:
587:
Request for
Comments: 6330. RaptorQ Forward Error Correction Scheme for Object Delivery
590:
452:
Greater than 99.9999% recovery probability with overhead of 2 symbols (recovery from
629:
669:
211:
184:
445:
Greater than 99.99% recovery probability with overhead of 1 symbol (recovery from
254:
438:
Greater than 99% recovery probability with overhead of 0 symbols (recovery from
147:
The references used may be made clearer with a different or consistent style of
574:(Report). Advanced Television Systems Committee. 22 March 2017. ATSC S33-174r6.
510:
488:
RFC 5053, and an IPR statement for the more advanced RaptorQ code specified in
484:
Qualcomm, Inc. has published an IPR statement for the Raptor code specified in
266:
219:
207:
152:
16:
This article is about error correction codes. For codebases named raptor, see
696:
641:
594:
520:
673:
505:
331:
319:
276:
203:
377:
remaining symbols using the decoding algorithm appropriate for that code.
585:
Luby M, Shokrollahi A, Watson M, Stockhammer T, Minder L (August 2011).
413:
The overhead is how many additional encoding symbols beyond the number
635:
586:
397:
time to generate an encoding symbol from a source block, and require
28:
611:
300:
287:
The most advanced version of Raptor is the RaptorQ code defined in
215:
515:
338:
584:
541:
210:
with linear time encoding and decoding. They were invented by
489:
485:
473:
465:
431:
315:
Raptor codes are formed by the concatenation of two codes.
296:
288:
270:
638:
Raptor
Forward Error Correction Scheme for Object Delivery
368:
output symbols generate an operation which is invertible.
342:
617:
623:
408:
330:. Another possibility would be a concatenation of a
299:
RFC 6330 is specified as a part of the Next Gen TV (
53:. Unsourced material may be challenged and removed.
655:
279:are an example of a non-systematic fountain code.
694:
539:
460:These statements hold for the entire range of
614:(Advanced Television Standards Committee 3.0)
401:time to recover a source block from at least
422:source symbols is not possible if less than
653:
578:
388:
265:broadcasting and multicasting, and also by
218:, which were the first practical class of
171:Learn how and when to remove this message
113:Learn how and when to remove this message
620:(The 3rd Generation Partnership Project)
689:, with statements by some patent owners
683:, with statements by some patent owners
662:IEEE Transactions on Information Theory
695:
334:with a low density parity check code.
326:is concatenated with a simple regular
540:Amin Shokrollahi (31 January 2011).
124:
51:adding citations to reliable sources
22:
642:DVB-H IP Datacasting specifications
13:
647:
259:3rd Generation Partnership Project
14:
714:
409:Recovery probability and overhead
687:"IPR" Search Result for RFC 6330
681:"IPR" Search Result for RFC 5053
129:
27:
654:Shokrollahi, Amin (June 2006).
543:The Development of Raptor Codes
479:
282:
206:) are the first known class of
38:needs additional citations for
561:
546:(Speech). Invited talk at the
533:
430:The RaptorQ code specified in
341:. Each encoding symbol is the
1:
605:
328:low density parity check code
626:(Digital Video Broadcasting)
295:The RaptorQ code defined in
255:systematic or non-systematic
7:
548:Kungliga Tekniska högskolan
499:
476:RFC 6330 for more details.
456:received encoding symbols).
449:received encoding symbols).
442:received encoding symbols).
371:
310:
10:
719:
15:
526:
389:Computational complexity
263:mobile cellular wireless
674:10.1109/TIT.2006.874390
18:Raptor (disambiguation)
305:List of ATSC standards
393:Raptor codes require
399:O(source block size)
383:Gaussian elimination
324:binary Gray sequence
253:Raptor codes may be
47:improve this article
494:MPEG DASH standard
472:=1,...,56403. See
405:encoding symbols.
181:
180:
173:
123:
122:
115:
97:
710:
677:
659:
599:
598:
582:
576:
575:
573:
565:
559:
558:
556:
554:
537:
468:RFC 6330, i.e.,
212:Amin Shokrollahi
185:computer science
176:
169:
165:
162:
156:
133:
132:
125:
118:
111:
107:
104:
98:
96:
55:
31:
23:
718:
717:
713:
712:
711:
709:
708:
707:
693:
692:
650:
648:Further reading
608:
603:
602:
583:
579:
571:
567:
566:
562:
552:
550:
538:
534:
529:
502:
482:
411:
391:
374:
313:
285:
267:DVB-H standards
177:
166:
160:
157:
146:
140:has an unclear
134:
130:
119:
108:
102:
99:
56:
54:
44:
32:
21:
12:
11:
5:
716:
706:
705:
691:
690:
684:
678:
657:"Raptor Codes"
649:
646:
645:
644:
639:
633:
627:
621:
615:
607:
604:
601:
600:
577:
560:
531:
530:
528:
525:
524:
523:
518:
513:
511:Fountain codes
508:
501:
498:
481:
478:
458:
457:
450:
443:
410:
407:
395:O(symbol size)
390:
387:
373:
370:
312:
309:
284:
281:
220:fountain codes
208:fountain codes
179:
178:
142:citation style
137:
135:
128:
121:
120:
35:
33:
26:
9:
6:
4:
3:
2:
715:
704:
703:Coding theory
701:
700:
698:
688:
685:
682:
679:
675:
671:
668:: 2551–2567.
667:
663:
658:
652:
651:
643:
640:
637:
634:
631:
630:3GPP TS26.346
628:
625:
622:
619:
616:
613:
610:
609:
596:
592:
588:
581:
570:
564:
549:
545:
544:
536:
532:
522:
521:Tornado codes
519:
517:
514:
512:
509:
507:
504:
503:
497:
495:
491:
487:
477:
475:
471:
467:
464:supported in
463:
455:
451:
448:
444:
441:
437:
436:
435:
433:
428:
425:
421:
416:
406:
404:
400:
396:
386:
384:
378:
369:
367:
363:
359:
354:
351:
347:
344:
340:
335:
333:
329:
325:
321:
318:A fixed rate
316:
308:
306:
302:
298:
293:
290:
280:
278:
274:
272:
268:
264:
260:
256:
251:
249:
245:
241:
237:
232:
228:
223:
221:
217:
213:
209:
205:
204:Tornado codes
201:
199:
195:
190:
186:
175:
172:
164:
154:
150:
144:
143:
138:This article
136:
127:
126:
117:
114:
106:
95:
92:
88:
85:
81:
78:
74:
71:
67:
64: –
63:
62:"Raptor code"
59:
58:Find sources:
52:
48:
42:
41:
36:This article
34:
30:
25:
24:
19:
665:
661:
580:
563:
551:. Retrieved
542:
535:
506:Erasure code
483:
480:Legal status
469:
461:
459:
453:
446:
439:
429:
423:
419:
414:
412:
402:
398:
394:
392:
379:
375:
365:
361:
357:
355:
352:
348:
336:
332:Hamming code
320:erasure code
317:
314:
294:
286:
283:RaptorQ code
277:Online codes
275:
252:
247:
243:
239:
235:
230:
226:
224:
197:
193:
192:
189:Raptor codes
188:
182:
167:
161:January 2021
158:
139:
109:
100:
90:
83:
76:
69:
57:
45:Please help
40:verification
37:
553:24 February
606:References
589:(Report).
273:RFC 5053.
153:footnoting
73:newspapers
595:2070-1721
103:June 2024
697:Category
612:ATSC 3.0
500:See also
372:Decoding
339:LT codes
311:Overview
301:ATSC 3.0
216:LT codes
149:citation
636:RFC5053
516:LT code
87:scholar
593:
202:; see
89:
82:
75:
68:
60:
572:(PDF)
527:Notes
94:JSTOR
80:books
618:3GPP
591:ISSN
555:2012
490:IETF
486:IETF
474:IETF
466:IETF
432:IETF
297:IETF
289:IETF
271:IETF
200:nado
151:and
66:news
670:doi
624:DVB
454:k+2
447:k+1
343:XOR
261:in
248:k+2
198:tor
196:id
194:rap
183:In
49:by
699::
666:52
664:.
660:.
385:.
222:.
187:,
676:.
672::
597:.
557:.
470:k
462:k
440:k
424:k
420:k
415:k
403:k
366:k
362:k
358:k
244:k
240:k
236:k
231:k
227:k
191:(
174:)
168:(
163:)
159:(
155:.
145:.
116:)
110:(
105:)
101:(
91:·
84:·
77:·
70:·
43:.
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
