Internet Engineering Task Force RMT WG
INTERNET-DRAFT M. Luby
draft-luby-rmt-bb-fec-raptor-object-00.txt Digital Fountain
A. Shokrollahi
EPFL
19 October 2004
Expires: April 2005
Raptor Forward Error Correction (FEC) Schemes for Objects
Status of this Document
By submitting this Internet-Draft, I certify that any applicable patent
or other IPR claims of which I am aware have been disclosed, or will be
disclosed, and any of which I become aware will be disclosed, in
accordance with RFC 3668.
Internet-Drafts are working documents of the Internet Engineering Task
Force (IETF), its areas, and its working groups. Note that other groups
may also distribute working documents as Internet-Drafts. Internet-
Drafts are draft documents valid for a maximum of six months and may be
updated, replaced, or obsoleted by other documents at any time. It is
inappropriate to use Internet-Drafts as reference material or to cite
them other than a "work in progress." The list of current Internet-
Drafts can be accessed at http://www.ietf.org/1id-abstracts.html.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This document is a product of the IETF RMT WG. Comments should be
addressed to the authors, or the WG's mailing list at rmt@lbl.gov.
Abstract
This document describes the Raptor code and its application to reliable
delivery of objects. Two Fully-Specified Forward Error Correction (FEC)
schemes are introduced, one for a non-systematic version of Raptor and
one for a systematic version of Raptor, that supplements the FEC schemes
described in RFC 3452.
Luby/Shokrollahi [Page 1]
INTERNET-DRAFT Expires: April 2005 October 2004
Raptor is a fountain code, i.e., as many encoding symbols as needed can
be generated by the encoder on-the-fly from the source symbols of a
source block. The decoder is able to recover the source block from any
set of encoding symbols only slightly more in number than the number of
source symbols.
Luby/Shokrollahi [Page 2]
INTERNET-DRAFT Expires: April 2005 October 2004
Table of Contents
1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2. Gray sequences . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3. Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2. Raptor Encoding of a Source Block . . . . . . . . . . . . . . . . 7
2.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2. Pre-coding . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3. Generators . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3.1. Random Generator. . . . . . . . . . . . . . . . . . . . . . 9
2.3.2. Degree Generator. . . . . . . . . . . . . . . . . . . . . . 9
2.3.3. Encoding Symbol Generator . . . . . . . . . . . . . . . . . 10
2.4. Encoding work. . . . . . . . . . . . . . . . . . . . . . . . . 10
3. Raptor Decoding of a Source Block . . . . . . . . . . . . . . . . 11
3.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2. First Phase. . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3. Second Phase . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.4. Third Phase. . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.5. Fourth Phase . . . . . . . . . . . . . . . . . . . . . . . . . 15
4. Raptor Object Delivery. . . . . . . . . . . . . . . . . . . . . . 15
4.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2. Source blocks and sub-blocks . . . . . . . . . . . . . . . . . 17
4.3. Session and packet information . . . . . . . . . . . . . . . . 17
4.3.1. FEC Object Transmission Information . . . . . . . . . . . . 18
4.3.2. FEC Payload ID. . . . . . . . . . . . . . . . . . . . . . . 19
4.4. Encoding an object . . . . . . . . . . . . . . . . . . . . . . 19
4.4.1. Smaller objects . . . . . . . . . . . . . . . . . . . . . . 20
4.4.2. Larger objects. . . . . . . . . . . . . . . . . . . . . . . 22
4.4.3. Large objects . . . . . . . . . . . . . . . . . . . . . . . 24
4.4.4. Encoding work per object. . . . . . . . . . . . . . . . . . 25
4.5. Decoding an object . . . . . . . . . . . . . . . . . . . . . . 25
4.5.1. Decoding work per object. . . . . . . . . . . . . . . . . . 26
4.5.2. Decoding failure probability. . . . . . . . . . . . . . . . 27
5. Systematic Raptor . . . . . . . . . . . . . . . . . . . . . . . . 27
5.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.2. Systematic information . . . . . . . . . . . . . . . . . . . . 28
5.3. Generating source symbol triples from system-
atic information. . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.4. Calculating the intermediate pre-coding sym-
bols. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.5. Work and decoding failure probability. . . . . . . . . . . . . 30
5.6. Calculating the systematic information . . . . . . . . . . . . 30
6. Raptor Systematic Object Delivery . . . . . . . . . . . . . . . . 32
6.1. Session and packet information . . . . . . . . . . . . . . . . 33
6.1.1. FEC Object Transmission Information . . . . . . . . . . . . 33
6.1.2. FEC Payload ID. . . . . . . . . . . . . . . . . . . . . . . 33
Luby/Shokrollahi [Page 3]
INTERNET-DRAFT Expires: April 2005 October 2004
6.2. Encoding an object . . . . . . . . . . . . . . . . . . . . . . 33
6.2.1. Smaller objects . . . . . . . . . . . . . . . . . . . . . . 33
6.2.2. Larger objects. . . . . . . . . . . . . . . . . . . . . . . 35
6.2.3. Large objects . . . . . . . . . . . . . . . . . . . . . . . 35
6.3. Decoding an object . . . . . . . . . . . . . . . . . . . . . . 35
7. Security Considerations . . . . . . . . . . . . . . . . . . . . . 36
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . . 36
9. Intellectual Property . . . . . . . . . . . . . . . . . . . . . . 37
10. Normative References . . . . . . . . . . . . . . . . . . . . . . 37
11. Informative References . . . . . . . . . . . . . . . . . . . . . 37
12. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 38
13. Full Copyright Statement . . . . . . . . . . . . . . . . . . . . 39
Luby/Shokrollahi [Page 4]
INTERNET-DRAFT Expires: April 2005 October 2004
1. Introduction
This document describes the Raptor code and its application to reliable
delivery of objects. Two Fully-Specified Forward Error Correction (FEC)
schemes are introduced, one for a non-systematic version of Raptor and
one for a systematic version of Raptor, that supplements the FEC schemes
described in RFC 3452.
We first provide a simple and easy to implement description of a non-
systematic Raptor encoder and decoder and then describe how to apply
this version to reliable delivery of objects. We then describe how to
modify the non-systematic Raptor code to make it systematic, and then
describe how to apply the systematic Raptor codes to reliable delivery
of objects. Thus, we introduce two new Fully-Specified FEC Schemes for
reliable object delivery, one for the non-systematic Raptor code and one
for the systematic Raptor code.
Raptor is a fountain code (as for example defined in [10]), i.e., as
many encoding symbols as needed can be generated by the encoder on-the-
fly from the source symbols of a source block. The decoder is able to
recover the source block from any set of encoding symbols only slightly
more in number than the number of source symbols. This fountain
property holds for both the non-systematic and the systematic versions
of Raptor. There are many advantages to using fountain codes versus
other types of FEC codes, some of which are described in [9] and [10].
This document inherits the context, language, declarations and
restrictions of the FEC building block [4]. This document also uses some
of the terminology of the companion document [14] which describes the
use of FEC codes within the context of reliable IP multicast transport
and provides an introduction to some commonly used FEC codes.
Building blocks are defined in RFC 3048 [7]. This document is a product
of the IETF RMT WG and follows the general guidelines provided in RFC
3269 [3].
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [2].
1.1. Notation
We use the following notation hereafter. For a positive value x let
floor(x) be x rounded down to the nearest integer and let ceil(x) be x
rounded up to the nearest integer.
Luby/Shokrollahi Section 1.1. [Page 5]
INTERNET-DRAFT Expires: April 2005 October 2004
For positive integers i and j let i MOD j denote i modulo j. For
example, 11 MOD 3 = 2.
For positive integers i and j let i^j denote i raised to the power j.
For example, 2^16 = 65,536.
Note that 65,521 is the largest prime smaller than 2^16.
For equal-length bit strings X and Y let X XOR Y denote the bit-by-bit
exclusive-or of X and Y. For example, 1010 XOR 1100 = 0110.
1.2. Gray sequences
We use a Gray sequence in the description of the generation of the half
symbols in the pre-coding step, as described below. For all positive
integers i, let g[i] be defined as follows. Let b[i] be the highest
order bit that is different in the binary representation of i-1 and i.
Then, the binary representation of g[i] is obtained by flipping bit b[i]
of g[i-1]. Table 1.2 provides some example values for g[i]. Note that
the sequence defined by g[.] has the property that each pair of
consecutive elements in the sequence differ in exactly one bit position.
i_____g[i]
0000 0000
0001 0001
0010 0011
0011 0010
0100 0110
0101 0111
0110 0101
0111 0100
1000 1100
1001 1101
1010 1111
1011 1110
1100 1010
1101 1011
1110 1001
1111 1000
Table 1.2: Gray sequence g[.]
We also use the function cnt[i], where cnt[i] returns the number of bits
that are set to one in the binary representation of i. For example the
Luby/Shokrollahi Section 1.2. [Page 6]
INTERNET-DRAFT Expires: April 2005 October 2004
binary representation of 25 is 11001, and thus cnt[25] = 3.
For any fixed positive integer j let g[.,j] be the subsequence of g[.]
where for each element in the sequence exactly j bits are set to 1.
Thus, g[.,j] can be defined based on g[.] as follows.
* c = 0, i = 0
* Do forever
o While (cnt(g[c]) not= j) do c = c+1
o g[i,j] = g[c]
o c = c+1
o i = i+1
For example, g[0,2] = g[2], g[1,2] = g[4], g[2,2] = g[6], g[3,2] = g[8],
g[4,2] = g[12], etc. Note that g[.,j] has the property that each pair
of consecutive elements in the sequence differ in exactly two bit
positions. For all i = 1, let Pos1[i,j] be one of the bit positions in
which g[i,j] and g[i-1,j] differ and let Pos2[i,j] be the other bit
position in which they differ. For example, Pos1[2,2] = 0 and Pos2[2,2]
= 1.
1.3. Work
The complexity of encoding and decoding is measured in terms of the
number of bytes of symbols that are exclusive-ored together or copied,
which is defined to be the work. Thus, for example, if a symbol is 64
bytes long, then computing the exclusive-or of two symbols counts as 64
bytes of work, and copying a symbol from one location to another also
counts as 64 bytes of work. The total encoding and decoding times
depend also on the amount of bookkeeping operations that are needed to
determine which symbols are exclusive-ored together or copied. But
since the symbols are typically relatively long, and since when there
are multiple source blocks the bookkeeping operations are done only once
and can be amortized over all the source blocks, the exclusive-or and
copy operations of symbols provide a rough estimate of the relative time
it takes to encode and decode on different CPU/OS platforms.
Furthermore, the efficiency of the bookkeeping operations are
implementation dependent, and in an efficient implementation the
bookkeeping operations take a fraction of the time that the exclusive-or
Luby/Shokrollahi Section 1.3. [Page 7]
INTERNET-DRAFT Expires: April 2005 October 2004
and copy operations take.
2. Raptor Encoding of a Source Block
2.1. Overview
Symbols are the fundamental data units of the encoding and decoding
process, and for each source block all symbols are the same size,
typically a few bytes long. The atomic operation performed on symbols
for both encoding and decoding is the exclusive-or operation.
A pre-coding step is used to produce L-K redundant symbols from the K
source symbols, where L > K, and the combination of the K source symbols
and the L-K redundant symbols form the L pre-coding symbols. Section
2.2 describes how the pre-coding symbols are generated from the source
symbols.
Each encoding packet contains a Encoding Symbol ID (ESI) and encoding
symbols. The ESI is used to generate a (d,a,b)-triple for each encoding
symbol carried in the encoding packet using the generators described in
Section 2.3. Then, each (d,a,b)-triple is used to generate the
corresponding encoding symbol from the pre-coding symbols as described
in Section 2.3.3.
2.2. Pre-coding
The pre-coding step consists of generating redundant symbols from the K
source symbols as follows. The redundant symbols consist of S LDPC
symbols and H half symbols. Let X be the smallest positive integer such
that X*(X-1) = 2*K. The value of S is the smallest positive prime
integer that is at least ceil(0.01*K) + X. The value of H is the
smallest integer such that choose(H,H') >= K + S, where H' = ceil(H/2)
and where choose(i,j) denotes the number of ways j objects can be chosen
from among i objects without repetition. Then L = K+S+H. Let the
positions of the pre-coding symbols range from 0 to L-1, where the first
K are the source symbols, the next S are the LDPC symbols, and the final
H are the half symbols.
For i = 0,...,L-1 let C[i] denote the ith pre-coding symbol. Note that
C[0],..., C[K-1] are the original source symbols. Initialize all the
redundant symbols C[K],...,C[L-1] to all zeroes.
The S LDPC symbols are defined as follows.
Luby/Shokrollahi Section 2.2. [Page 8]
INTERNET-DRAFT Expires: April 2005 October 2004
* For i = 0,...,K-1 do
o a = 1 + (floor(i/S) MOD (S-1))
o b = i MOD S
o C[K + b] = C[K + b] XOR C[i]
o b = (b + a) MOD S
o C[K + b] = C[K + b] XOR C[i]
o b = (b + a) MOD S
o C[K + b] = C[K + b] XOR C[i]
The H half symbols are defined as follows.
* For h = 0,...,H-1 do
o For i = 0,...,K+S-1 do
- If bit h of g[i,H'] is equal to 1 then C[h+K+S] = C[h+K+S]
XOR C[i].
Equivalently, the H half symbols can be defined as follows, which
suggests an efficient implementation:
* T = C[0].
* For i = 1,...,K+S-1 do
o C[Pos1[i,H']+K+S] = C[Pos1[i,H']+K+S] XOR T.
o C[Pos2[i,H']+K+S] = C[Pos2[i,H']+K+S] XOR T.
o T = T XOR C[i].
* For all bit positions h of g[K+S-1,H'] that are equal to 1 do
o C[h+K+S] = C[h+K+S] XOR T.
Luby/Shokrollahi Section 2.2. [Page 9]
INTERNET-DRAFT Expires: April 2005 October 2004
2.3. Generators
All of the generators described in the following subsections are used in
the generation of encoding symbols.
2.3.1. Random Generator
The random number generator Rand[X, i, m] is defined as follows, where X
is a 2-byte unsigned integer, i is an unsigned integer and m is a
positive integer and the value produced is an integer between 0 and m-1.
Let X0 be first byte and let X1 the second byte of X. Let V0 and V1 be
arrays of 256 entries each, where each entry is a random 4-byte unsigned
integer. Then,
Rand[X, i, m] = (V0[(X0 + i) MOD 256] XOR V1[(X1 + i) MOD 256]) MOD m
2.3.2. Degree Generator
The degree generator Deg[v] is defined as follows, where v is an integer
that is at least 0 and less than 2^20 = 1,048,576.
* In Table 2.3.2, find the index j such that f[j-1] <= v < f[j]
* Deg[v] = d[j]
j___________f[j]_______d[j]
0 0 --
1 10,241 1
2 491,582 2
3 712,794 3
4 831,695 4
5 948,446 10
6 1,032,189 11
7 1,048,576 40
Table 2.3.2: Defines the degree distribution for encoding symbols
Luby/Shokrollahi Section 2.3.2. [Page 10]
INTERNET-DRAFT Expires: April 2005 October 2004
2.3.3. Encoding Symbol Generator
Let L be the number of pre-coding symbols of the source block, let L' be
the smallest prime integer greater than or equal to L, and let C[0],...,
C[L-1] be the pre-coding symbols of the source block. The encoding
symbol generator Enc[d, a, b] is defined as follows, where d is a
degree, a is between 1 and L'-1 and b is between 0 and L'-1.
* While (b = L) do b = (b + a) MOD L'
* Enc[d, a, b] = C[b].
* For j = 1,...,d-1 do
o b = (b + a) MOD L'
o While (b = L) do b = (b + a) MOD L'
o Enc[d, a, b] = Enc[d, a, b] XOR C[b]
2.4. Encoding work
The work to produce the LDPC symbols is 3 times the total length in
bytes of the source symbols. The work to produce the half symbols is
essentially 3 times the total length in bytes of the source symbols.
Thus, the total work for generating the pre-coding is 6 times the total
length in bytes of the source symbols.
>From the degree distribution described in Section 2.3.2 via Table 2.3.2,
it is not hard to see that the work on average to generate encoding
symbols is 4.63 times the total length in bytes of the encoding symbols
generated.
3. Raptor Decoding of a Source Block
3.1. Overview
This subsection provides an overview of Raptor decoding of a source
block. It is assumed that the decoder knows the structure of the source
block it is to decode, including the symbol length and the number K of
symbols in the source block.
Luby/Shokrollahi Section 3.1. [Page 11]
INTERNET-DRAFT Expires: April 2005 October 2004
>From the algorithms described in 2.2, the Raptor decoder can calculate
the total number L = K+S+H of pre-coding symbols and determine how they
were generated from the source block to be decoded. It is assumed that
the received encoding symbols for the source block to be decoded are
passed to the decoder. Furthermore, for each such encoding symbol it is
assumed that [d,a,b]-triple that was used to compute the encoding symbol
from the pre-coding symbols is passed to the decoder, and this allows
the decoder to use a portion of the encoding algorithm described in
Section 2.3.3 to compute the number and set of pre-coding symbols used
to generate the encoding symbol.
Let N >= K be the number of received encoding symbols for a source block
and let M = S+H+N. The following M by L bit matrix A can be derived
from the information passed to the decoder for the source block to be
decoded. Let C be the column vector of the L pre-coding symbols, and
let D be the column vector of M symbols with values known to the
receiver, where the first S+H of the M symbols are zero-valued symbols
that correspond to LDPC and half symbols (these are check symbols for
the LDPC and half symbols, and not the LDPC and half symbols
themselves), and the remaining N of the M symbols are the received
encoding symbols for the source block. Then, A is the bit matrix that
satisfies A*C = D, where here * denotes matrix multiplication over
GF[2]. In particular, A[i,j] = 1 if the pre-coding symbol
corresponding to index j is exclusive-or'd into the LDPC, half or
encoding symbol corresponding to index i in the encoding, or if index i
corresponds to a LDPC or half symbol and index j corresponds to the same
LDPC or half symbol. For all other i and j, A[i,j] = 0.
Decoding a source block is equivalent to decoding C from known A and D.
(This is equivalent to recovering the K source symbols since if they can
be recovered then the other L-K pre-coding symbols can be recomputed.)
It is clear that C can be decoded if and only if the rank of A over
GF[2] is L.
The first step in decoding C is to form a decoding schedule. In this
step A is converted, using Gaussian elimination (using row operations
and row and column reorderings) and after discarding M - L rows, into
the L by L identity matrix. The decoding schedule consists of the
sequence of row operations and row and column re-orderings during the
Gaussian elimination process, and only depends on A and not on D. The
decoding of C from D can take place concurrently with the forming of the
decoding schedule, or the decoding can take place afterwards based on
the decoding schedule.
The correspondence between the decoding schedule and the decoding of C
is as follows. Let c[0] = 0, c[1] = 1,...,c[L-1] = L-1 and d[0] = 0,
d[1] = 1,...,d[M-1] = M-1 initially.
Luby/Shokrollahi Section 3.1. [Page 12]
INTERNET-DRAFT Expires: April 2005 October 2004
* Each time row i of A is exclusive-ored into row i' in the decoding
schedule then in the decoding process symbol D[d[i]] is exclusive-
ored into symbol D[d[i']].
* Each time row i is exchanged with row i' in the decoding schedule
then in the decoding process the value of d[i] is exchanged with the
value of d[i'].
* Each time column j is exchanged with column j' in the decoding
schedule then in the decoding process the value of c[j] is exchanged
with the value of c[j'].
>From this correspondence it is clear that the total number of exclusive-
ors of symbols in the decoding of the source block is the number of row
operations (not exchanges) in the Gaussian elimination. Since A is the
L by L identity matrix after the Gaussian elimination and after
discarding the last M - L rows, it is clear at the end of successful
decoding that the L symbols D[d[0]], D[d[1]],..., D[d[L-1]] are the
values of the L symbols C[c[0]], C[c[1]],..., C[c[L-1]].
The order in which Gaussian elimination is performed to form the
decoding schedule has no bearing on whether or not the decoding is
successful. However, the speed of the decoding depends heavily on the
order in which Gaussian elimination is performed. (Furthermore,
maintaining a sparse representation of A is crucial, although this
document does not describe the details of how this is done). The
remainder of this section focuses on the order in which Gaussian
elimination should be performed.
3.2. First Phase
The first phase of the Gaussian elimination the matrix A is conceptually
partitioned into submatrices. The submatrix sizes are parameterized by
non-negative integers i and u which are initialized to 0. The
submatrices of A are:
(1) The submatrix I defined by the intersection of the first i rows
and first i columns. This is the identity matrix at the end of
each step in the phase.
(2) The submatrix defined by the intersection of the first i rows and
all but the first i columns and last u columns. All entries of
this submatrix are zero.
Luby/Shokrollahi Section 3.2. [Page 13]
INTERNET-DRAFT Expires: April 2005 October 2004
(3) The submatrix defined by the intersection of the first i columns
and all but the first i rows. All entries of this submatrix are
zero.
(4) The submatrix U defined by the intersection of all the rows and
the last u columns.
(5) The submatrix X formed by the intersection of all but the first i
columns and the last u columns and all but the first i rows.
Figure 3.2 illustrates the submatrices of A. At the beginning of the
first phase X = A. In each step, a row of A is chosen. The following
graph defined by the structure of X is used in determining which row of
A is chosen. The columns that intersect X are the nodes in the graph,
and the rows that have exactly 2 ones in X are the edges of the graph
that connect the two columns (nodes) in the positions of the two ones.
A component in this graph is a maximal set of nodes (columns) and edges
(rows) such that there is a path between each pair of nodes/edges in the
graph. The size of a component is the number of nodes (columns) in the
component.
I 0 U
0 X U
Figure 3.2: Submatrices of A in the first phase
There are at most L steps in the first phase. The phase ends
successfully when i + u = L, i.e. when X and the all zeroes submatrix
above X have disappeared and A consists of I, the all zeroes submatrix
below I, and U. The phase ends unsuccessfully in decoding failure if at
some step before X disappears there is no non-zero row in X to choose in
that step. In each step, a row of A is chosen as follows:
Row Choice
* If all entries of X are zero then no row is chosen and decoding
fails.
* Let r be the minimum integer such that at least one row of A has
exactly r ones in X.
* If r not= 2 then choose a row with exactly r ones in X with minimum
original degree among all such rows.
* If r = 2 then choose any row with exactly 2 ones in X that is part
of a maximum size component in the graph defined by X.
Luby/Shokrollahi Section 3.2. [Page 14]
INTERNET-DRAFT Expires: April 2005 October 2004
After the row is chosen in the step the first row of A that intersects X
is exchanged with the chosen row so that the chosen row is the first row
that intersects X. The columns of A among those that intersect X are
reordered so that one of the r ones in the chosen row appears in the
first column of X and so that the remaining r-1 ones appear in the last
columns of X. Then, the chosen row is exclusive-ored into all the other
rows of A below the chosen row that have a one in the first column of X.
Finally, i is incremented by 1 and u is incremented by r-1, which
completes the step.
3.3. Second Phase
The submatrix U is further partitioned into the first i rows, UU, and
the remaining M - i rows, UL. Gaussian elimination is performed in the
second phase on UL to either determine that its rank is less than u
(decoding failure) or to convert it into a matrix where the first u rows
is the identity matrix (success of the second phase). Call this u by u
identity matrix UI. The M - L rows of A that intersect UL - UI are
discarded. After this phase A has L rows and L columns.
3.4. Third Phase
After the second phase the only portion of A which needs to be zeroed
out to finish converting A into the L by L identity matrix is UU. The
number of rows i of the submatrix UU is generally much larger than the
number of columns u of UU. To zero out UU efficiently, the following
precomputation matrix UE is computed based on UI in the third phase and
then UE is used in the fourth phase to zero out UU. The u rows of UI
are partitioned into ceil(u/7) groups of 7 rows each. Then, for each
group of 7 rows all non-zero combinations of the 7 rows are computed,
resulting in 2^7- 1 = 127 rows (this can be done with 2^7-7-1 = 120
exclusive-ors of rows per group, since the combinations of Hamming
weight one that appear in UI do not need to be recomputed). Thus, the
resulting precomputation matrix UE has ceil(u/7)*127 rows and u columns.
Note that UE is not formally a part of matrix A, but will be used in the
fourth phase to zero out UU.
3.5. Fourth Phase
For each of the first i rows of A, for each group of 7 columns in the UU
submatrix of this row, if the set of 7 column entries in UU are not all
zero then the row of the precomputation matrix UE that matches the
Luby/Shokrollahi Section 3.5. [Page 15]
INTERNET-DRAFT Expires: April 2005 October 2004
pattern in the 7 columns is exclusive-ored into the row, thus zeroing
out those 7 columns in the row at the cost of exclusive-oring one row of
UE into the row.
After this phase A is the L by L identity matrix and a complete decoding
schedule has been successfully formed. Then, as explained at the
beginning of Section 3.1, the corresponding decoding consisting of
exclusive-oring known encoding symbols can be executed to recover the
source block based on the decoding schedule.
Only rows corresponding to recovering a source symbol need be considered
in this phase if only the source symbols and not all the pre-coding
symbols are to be decoded. However, for the systematic Raptor codes
described in Section 5 all of the pre-coding symbols need be recovered.
4. Raptor Object Delivery
This section specifies how to use the Raptor code specified in Sections
2 and 3 for reliable delivery of an object to many receivers in an IP
multicast network. This could also be used for delivery using other
types of networks, e.g., unicast networks, but this is outside the scope
of this document. This version of Raptor is a non-systematic code.
This section also defines a new Fully-Specified FEC scheme (as defined
in RFC3452 [4]). with a corresponding new FEC Encoding ID (with an as
yet undefined number) and the corresponding FEC Object Transmission
Information and FEC Payload ID format.
4.1. Motivation
The basic properties of Raptor for reliable object delivery are that,
for any packet loss conditions, for delivery of objects of any relevant
size: (a) reception overhead of each individual receiver is minimal; (b)
the total transmission time and bandwidth needed to deliver objects to
any number of receivers is minimal.
In the solution described in this document the amount of working memory
needed for decoding can be much smaller than the object size and still
provide the above properties, and the amount of computation needed to
encode and decode is minimal.
Raptor is a fountain code (as for example defined in [10], called
expandable codes in [14]), i.e., as many encoding packets as needed can
be generated on-the-fly, each containing unique encoding symbols that
Luby/Shokrollahi Section 4.1. [Page 16]
INTERNET-DRAFT Expires: April 2005 October 2004
are equally useful for recovering a object. There are many advantages
to using fountain codes versus other types of FEC codes, some of which
are described in [9], [10] and [11]. One advantage is that, regardless
of packet loss conditions and receiver availability, fountain codes
minimize the number of encoding packets each receiver needs to receive
to reconstruct a object. This is true even under harsh packet loss
conditions and when for example mobile receivers are only intermittently
turned-on or available over a long object delivery session.
One advantage of the fountain property of Raptor is that it makes it
possible to decide during the session how many encoding packets to
generate and send. This can be useful if for example there is feedback
from receivers indicating whether or not they received enough encoding
packets to recover a object. When packet loss conditions are less severe
than expected the transmission can be terminated early. When packet loss
conditions are more severe than expected or receivers are unavailable
more often than expected the transmission can be seamlessly extended.
Alternatively, if a fixed duration object delivery session is used and
after the conclusion of the initial session feedback is received which
indicates that many receivers have not yet received enough packets to
recover the object then it would be advantageous to schedule a repair
session. For example, the scheduled duration of the initial session can
be short, assuming optimistically small losses, and then the duration
can be dynamically extended only if required. This flexibility and
ability to optimize transmission bandwidth usage is simple with a
fountain code.
4.2. Source blocks and sub-blocks
The maximum source block size B in bytes is recommended to be 4 MB in
this document. Thus, objects that are larger than B bytes in size are
partitioned into more than one source block. Limiting the source block
size to at most B bytes in size ensures that the encoding length of a
source block can potentially be many times larger than the source block,
and thus object delivery using this specification can handle very high
packet loss conditions.
The maximum block size W in bytes that can be decoded in working memory
is recommended to be 256 KB in this document. Thus, source blocks that
are larger than W bytes in size are partitioned into N > 1 sub-blocks,
and the Raptor decoder decodes one sub-block at a time. Each sub-block
consists of the same number K of sub-symbols, where each sub-symbol is T
bytes long. Then, each source symbol of the source block is T*N bytes
long, and consists of the concatenation of exactly one sub-symbol from
each of the N sub-blocks. Figure 4.2 shows a source block placed into a
Luby/Shokrollahi Section 4.2. [Page 17]
INTERNET-DRAFT Expires: April 2005 October 2004
two dimensional array, where each entry is a T-byte sub-symbol, each row
is a sub-block and each column is a source symbol. The number shown in
each sub-symbol entry indicates their original order within the source
block. For example, the sub-symbol numbered K contains bytes T*K
through T*(K+1)-1 of the source block. Thus, the first K sub-symbols of
the source block numbered 0 to K-1 form the first sub-block, the next K
sub-symbols of the source block numbered K to 2*K-1 form the second sub-
block, etc. Then, source symbol i is the concatenation of the ith sub-
symbol from each of the sub-blocks, which corresponds to the sub-symbols
of the source block numbered i, K+i, 2*K+i,..., (N-1)*K+i.
0 1 2 ... ... ... ... K-1
K K+1 K+2 ... ... ... ... 2*K-1
2*K 2*K+1 2*K+2 ... ... ... ... 3*K-1
(N-1)*K ... ... ... ... ... ... N*K-1
Figure 4.2: Source symbols from sub-symbols structure
Encoding symbols are generated from the source symbols composed of sub-
symbols,and thus the size of an encoding symbol is T*N bytes consisting
of N encoding sub-symbols each of size T bytes.
4.3. Session and packet information
The overall structure of the FEC Object Transmission Information and the
FEC Payload ID are both defined in [4]. The receiver needs to receive
the specific FEC Object Transmission Information in a session
description (for example, carried in a FLUTE FDT as described in [8])
generally before starting to receive packets for a object to determine
some of the critical parameters needed to decode the object. The FEC
Payload ID is carried in each packet to identify the encoding symbols
carried in that packet.
4.3.1. FEC Object Transmission Information
Besides the FEC Encoding ID, the FEC Object Transmission Information
includes:
* The object size F in bytes
* The payload size P of each packet in bytes
Luby/Shokrollahi Section 4.3.1. [Page 18]
INTERNET-DRAFT Expires: April 2005 October 2004
* The maximum source block size B in bytes
* The maximum working memory size W in bytes that indicates the
largest sub-block that can be decoded in receiver working memory.
A suggested value of P could be for example 512 bytes for object
delivery over multicast cellular networks, or 1024 bytes for other
multicast networks. In general P must be equal to G*N*T, where G is
defined below.
A suggested value of B is 4 MB. This means that objects that are at
most 4 MB will consist of one source block, and that objects larger than
4 MB will be partitioned into more than one source block. The method
used to partition a object larger than 4 MB into source blocks is
described in [8]. In general B must be at least W.
A suggested value of the maximum size W of a sub-block that can be
decoded in working memory is 256 KB for example for delivery of objects
to cellular devices. Other values of W could also be suitable, e.g. W =
512 KB or W = 128 KB. How a source block is partitioned into sub-blocks
depends on whether the source block size is smaller or larger than
working memory W, and is described below for the suggested values of B
and W.
For the suggested values the algorithms described below compute for each
source block:
* The number G of encoding symbols for the source block carried in
each encoding packet
* The number K of source symbols in the source block
* The number N of sub-blocks into which the source block is
partitioned
* The sub-symbol size T in bytes for the sub-blocks.
The symbol size is thus N*T bytes for the source block.
4.3.2. FEC Payload ID
The FEC Payload ID is shown in Figure 4.3.2 and consists of a two-byte
Source Block Number (SBN) and a two-byte Encoding Symbol ID (ESI), and
Luby/Shokrollahi Section 4.3.2. [Page 19]
INTERNET-DRAFT Expires: April 2005 October 2004
thus the overall FEC Payload ID is 4 bytes long. This allows sending of
objects of size up to P*2^32 bytes. The FEC Payload ID is included in
the header of each packet carrying encoding symbols in its payload to
identify how the encoding symbols are generated from the source block.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Block Number (SBN) | Encoding Symbol ID (ESI) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 4.3.2: FEC Payload ID
A longer FEC Payload ID could be used for other services. For example
with an FEC Payload ID that consists of a four-byte SBN and a four-byte
ESI, much larger source blocks can be used and much larger objects can
be sent. would require some minor modifications to how the ESI is used
to generate encoding symbols.
4.4. Encoding an object
All the examples in the subsequent subsections used the suggested
parameter settings of P = 512 bytes, W = 256 KB and B = 4 MB.
4.4.1. Smaller objects
When the object size F <= W the object consists of a single source block
that in turn consists of one sub-block, i.e., Z = N = 1. The number K
of source symbols in the object is computed as ceil(F/T). For P = 512
bytes and W = 256 KB, the number G of encoding symbols placed into each
encoding packet and the symbol size T is determined by Table 4.4.1 based
on the object size F. In general, for other values of P and W, it is
recommended that G and T are set in such a way such that K is at least
1,000 and T is as large as possible.
The SBN is set to 0 in the FEC Payload ID of each packet and the ESI is
set to a two-byte value X, where the value of X should be different in
each encoding packet. The ESI is used to uniquely identify the encoding
symbols generated from the L pre-coding symbols of a source block that
are placed into a single packet, where the value of L and the pre-coding
symbols are generated as described in Section 2. The sequence of ESI
values for the packets sent for the object is generated as follows.
Luby/Shokrollahi Section 4.4.1. [Page 20]
INTERNET-DRAFT Expires: April 2005 October 2004
Generating ESI values
* Let Q be the largest prime integer such that Q = floor(2^16/G)
* Let A be an integer such that 0 < A < Q
* Let B be an integer such that 0 <= B < Q
* Let N be the number of packets to be sent in the session
* X = B
* For i = 0,...,N-1 do
o Use X as the ESI for the next packet
o X = (X + A) MOD Q
If additional packets for the object are to be send at a later time then
the ESI's for the packets sent in that session can be generated using
the above algorithm using the same value for A and using the value of X
at the end of the first session for the value of B. For example,
suppose G = 16 (and thus Q = 4,093), A = 1 and B = 0. If 150 packets
are sent in the first session then their ESI values are 0, 1, ..., 149,
and at the end X = 150. Suppose 50 additional packets are to be sent
in the MBMS repair session. Then A = 1 and B = 150, and the ESI values
are 150, 151, ..., 199 and at the end X = 200.
The values of the encoding symbols placed into the packet with ESI X are
computed as follows:
Generating encoding symbols E0[X],..., EG-1[X]
* v = Rand[X, 0, 2^20]
* Y = (X*G) MOD 2^16
* Repeat the following for i = 0,...,G-1
o d = Deg[v]
o a = 1 + Rand[Y, 1, L'-1]
o b = Rand[Y, 2, L']
Luby/Shokrollahi Section 4.4.1. [Page 21]
INTERNET-DRAFT Expires: April 2005 October 2004
o Ei[X] = Enc[d, a, b]
o v = (v + 2^20/G) MOD 2^20
o Y = (Y + 1) MOD 2^16
Because of the way ESIs are generated for packets in different sessions,
it is easy to see that all of the ESIs in the different sessions are all
distinct and all the Y values used to generate the (d, a, b)-triple for
each encoding symbol are all distinct as long as the total number of
packets generated is at most Q.
F range_________________N_____G_____T___________K range
512 B < F = 64 KB 1 16 32 bytes 16 = K = 2,048
64 KB < F = 128 KB 1 8 64 bytes 1,024 < K = 2,048
128 KB < F = 256 KB 1 4 128 bytes 1,024 < K = 2,048
Table 4.4.1: Source block parameters for small objects when P = 512
bytes and W = 256 KB
EXAMPLE 1
Object size F = 50 KB
Number of object packets = 100
Number of source blocks Z = 1
Number of sub-blocks N = 1
Number of encoding symbols per encoding packet G = 16
Symbol size T = 32 bytes
Number of source symbols K = 1,600
EXAMPLE 2
Object size F = 100 KB bytes
Number of object packets = 200
Number of source blocks Z = 1
Number of sub-blocks N = 1
Number of encoding symbols per encoding packet G = 8
Symbol size T = 64 bytes
Number of source symbols K = 1,600
Luby/Shokrollahi Section 4.4.1. [Page 22]
INTERNET-DRAFT Expires: April 2005 October 2004
EXAMPLE 3
Object size F = 200 KB bytes
Number of object packets = 400
Number of source blocks Z = 1
Number of sub-blocks N = 1
Number of encoding symbols per encoding packet G = 4
Symbol size T = 128 bytes
Number of source symbols K = 1,600
4.4.2. Larger objects
When the object size F is more than W but at most B then the object
consists of a single source block that is partitioned into N sub-blocks,
where the length of each sub-block is greater than W/2 but at most W.
The value of N is the smallest power of two such that N*W >= F. The
size I of each sub-block is computed as ceil(F/N), and the number K of
sub-symbols per sub-block is computed as ceil(I/T). Table 4.4.2 is used
to determine the sub-block parameters based on the object size F when P
= 512 bytes, W = 256 KB and B = 4 MB. In general, for other values of W
and B, it is recommended that G and T are powers of two and set in such
a way such that K is at least 2,000 and T is as large as possible.
The SBN is set to 0 in the FEC Payload ID of each packet and the ESI is
set to a two-byte value X, where the value of X should be different in
each encoding packet. The source block is partitioned into N sub-
blocks, and each encoding packet contains G encoding symbols generated
from the source block consisting of the N sub-blocks, where the values
of N and G are obtained from Table 4.4.2. The ESI values for the packets
and the values of the G encoding symbols E0[X],..., EG-1[X] placed into
the packet with ESI X are computed as described in Section 4.4.1.
F range_________________N_____G_____T___________K range
256 KB < F = 512 KB 2 4 64 bytes 2,048 < K = 4,096
512 KB < F = 1 MB 4 2 64 bytes 2,048 < K = 4,096
1 MB < F = 2 MB 8 1 64 bytes 2,048 < K = 4,096
2 MB < F = 4 MB 16 1 32 bytes 4,096 < K = 8,192
Table 4.4.2: Source block parameters for large objects when P = 512
bytes, W = 256 KB and B = 4 MB
Luby/Shokrollahi Section 4.4.2. [Page 23]
INTERNET-DRAFT Expires: April 2005 October 2004
EXAMPLE 4
Object size F = 400 KB
Number of object packets = 800
Number of source blocks Z = 1
Number of sub-blocks N = 2
Size of a sub-block in bytes I = 200 KB
Number of encoding symbols per encoding packet G = 4
Sub-symbol size T = 64 bytes
Symbol size N*T = 128 bytes
Number of source symbols per source block K = 3,200
EXAMPLE 5
Object size F = 800 KB
Number of object packets = 1,600
Number of source blocks Z = 1
Number of sub-blocks N = 4
Size of a sub-block in bytes I = 200 KB
Number of encoding symbols per encoding packet G = 2
Sub-symbol size T = 64 bytes
Symbol size N*T = 256 bytes
Number of source symbols per source block K = 3,200
EXAMPLE 6
Object size F = 1.6 MB
Number of object packets = 3,200
Number of source blocks Z = 1
Number of sub-blocks N = 8
Size of a sub-block in bytes I = 200 KB
Number of encoding symbols per encoding packet G = 1
Sub-symbol size T = 64 bytes
Symbol size N*T = 512 bytes
Number of source symbols per source block K = 3,200
EXAMPLE 7
Object size F = 3 MB
Number of object packets = 6,144
Number of source blocks Z = 1
Number of sub-blocks N = 16
Size of a sub-block in bytes I = 192 KB
Number of encoding symbols per encoding packet G = 1
Sub-symbol size T = 32 bytes
Symbol size N*T = 512 bytes
Number of source symbols per source block K = 6,144
Luby/Shokrollahi Section 4.4.2. [Page 24]
INTERNET-DRAFT Expires: April 2005 October 2004
4.4.3. Large objects
When the object size F is more than B then the object is partitioned
into more than one source block using the Algorithm for Computing Source
Block Structure described in Section 5.1.2.3 of FLUTE [8]. The inputs to
that algorithm are:
* The maximum number of source symbols per source block. This is set
to the ratio of B/P, since there is one symbol per packet. If B = 4
MB and P = 512 bytes, the maximum number of source symbols per
source block is 8,192.
* The transfer length in bytes. This is set to the object size F.
* The symbol length in bytes. This is set to P since there is one
symbol per packet.
The output of the algorithm is the number Z of source blocks, and the
number and lengths of source symbols in each of the Z source blocks
(with possibly the last symbol of the last source block logically filled
out with zeroes to a full length symbol).
Each encoding packet contains one encoding symbol generated from one of
the Z source blocks. The SBN of each packet is set to the number of the
source block from which the encoding symbol carried in the payload of
the packet is generated, and thus the SBN is between 0 and Z-1. The ESI
values for each source block are generated using the algorithm described
in Section 4.4.1 independently for each source block, and thus the same
ESI values are used for different source blocks of the same object. The
method for generating an encoding symbol from a source block is as
described in Section 4.4.2, where the source block is substituted for
the object in that description.
EXAMPLE 8
Object size F = 9 MB
Number of object packets = 18,432
Number of source blocks Z = 3
Size of source blocks = 3 MB (all equal size in this example)
For each of the 3 source blocks, the rest of the construction is
the same as for Example 6 where the source block is substituted
for the object in that description.
Luby/Shokrollahi Section 4.4.3. [Page 25]
INTERNET-DRAFT Expires: April 2005 October 2004
4.4.4. Encoding work per object
The encoding work per object can be derived from Section 2, i.e., the
work to generate the pre-coding for a object is 6*F and the work on
average to generate packet payloads containing encoding symbols for a
object is 4.63 times the total length in bytes of the generated packet
payloads.
4.5. Decoding an object
Just like for encoding, there are three cases of how to decide how to
recover the object, depending on the object size F. When F <= W then the
object is decoded as a single source block. Each received encoding
packet contains an ESI and one or more encoding symbols. The ESI is
used to reconstruct how each encoding symbol contained in the encoding
packet was generated, and then when enough encoding packets have arrived
the object is decoded.
When B >= F > W then the object consists of a single source block that
is partitioned into multiple sub-blocks that are decoded in a
coordinated way. As each encoding packet arrives, the ESI is saved, and
each encoding sub-symbol corresponding to a sub-block is saved in a
temporary object dedicated to that sub-block. Then, based on the
received ESIs the decoding schedule can be formed based on the
algorithms described in Section 3, and then that decoding schedule is
applied to the encoding sub-symbols for each sub-block in sequence,
decoding each sub-block within the limits of the working memory
resources based on the algorithms described in Section 3, where the sub-
block is substituted for the source block and the encoding sub-symbols
are substituted for the encoding symbols in that description.
When F >= B then the object consists of multiple source blocks that are
in turn partitioned into multiple sub-blocks. Each source block is
handled independently of the other source blocks, i.e., all the ESIs for
a source block are saved in a temporary object dedicated to that source
block, and each encoding sub-symbol corresponding to a sub-block within
the source block are saved in a temporary object dedicated to that sub-
block within the source block. Then, for each source block in turn,
based on the received ESIs for that source block the decoding schedule
can be formed, and then that decoding schedule is applied to the
encoding sub-symbols for each sub-block in sequence, decoding each sub-
block within the limits of the working memory resources.
The decoding memory requirements for Raptor are slightly more than the
sub-block length. For example, a 100 KB object that is encoded and
Luby/Shokrollahi Section 4.5. [Page 26]
INTERNET-DRAFT Expires: April 2005 October 2004
decoded as a single source block takes slightly more than 100 KB of
working memory for the decoding, whereas a 3 MB object is partitioned
into 16 sub-blocks of 192 KB each, and thus the working memory needed to
decode is slightly more than 192 KB. Decoding can be performed in
place, i.e., a sub-block can be recovered in place using the same
working memory that contains the encoding sub-symbols for the sub-block
just before it is decoded.
4.5.1. Decoding work per object
The decoding work per object depends slightly on the reception overhead,
i.e., the more packets received for an object the less the total work it
takes to decode the object. For all object sizes the average decoding
workload per object is around 10 when the reception overhead is 0.02,
and drops to around 8 when the reception overhead is 0.04, where the
decoding workload is the decoding work divided by the number of bytes in
the object, and thus the decoding workload is the number of bytes that
are exclusive-ored on average to decode each byte of the object. The
decoding work per object is independent of the amount of packet loss and
packet loss patterns.
Since the sub-symbols that are exclusive-ored in the decoding generally
are many bytes long (sizes ranging from 32 bytes to 128 bytes depending
on the object size), and since a CPU can generally exclusive-or together
several bytes in a single operation, the exclusive-oring can be
pipelined in such a way that decoding is very efficient.
4.5.2. Decoding failure probability
The decoding failure probability d for a given reception overhead e is
the probability the decoding process fails to recover the source block
when the number of received encoding symbols is (1+e)*K, where K is the
number of source symbols in the source block. For all values of K that
are at least approximately 1,000 the decoding failure probability is at
most around d = 10^-3 when the reception overhead is e = 0.01 and the
decoding failure probability is at most around d = 10^-6 when the
reception overhead is e = 0.02. The decoding failure probability
continues to drop off as the reception overhead increases, but at a much
slower rate.
These results were obtained by running the decoder many times on
different packet sequences until several decoding failures were observed
and then reporting the average number of times decoding failed. In some
cases this required running the decoder tens of millions of times.
Luby/Shokrollahi Section 4.5.2. [Page 27]
INTERNET-DRAFT Expires: April 2005 October 2004
Because each encoding packet is generated at random independently of all
other encoding packets, the received encoding packets are random for any
loss pattern of encoding packets that does not depend on their values.
Since packet loss is independent of packet content, the value of d is
independent of packet loss.
There are other versions of Raptor codes with much smaller failure
probabilities, but this is beyond the scope of this document.
5. Systematic Raptor
5.1. Overview
The Raptor systematic encoder is used to generate repair symbols from a
source block that consists of K source symbols. The overall strategy
for doing this is as follows. A first step is to generate systematic
information associated with K. This systematic information is used to
generate K triples (d[0], a[0], b[0]),..., (d[K-1], a[K-1], b[K-1]) for
the source symbols.
The K source symbol triples are then used to decode L intermediate pre-
coding symbols from the source symbols using the Raptor decoder
described in Section 3. By the way the systematic information is
generated, the K source symbol triples are guaranteed to uniquely decode
the L intermediate pre-coding symbols, i.e., if the K source symbol
triples are used to produce K encoding symbols from the intermediate
pre-coding symbols using the Raptor encoder described in Section 2 then
these encoding symbols are exactly the source symbols. Furthermore, the
K source symbol triples are generated from the same distribution as
other triples generated by the Raptor encoder, and thus the source
symbols can be thought of as random encoding symbols generated from the
intermediate pre-coding symbols. The idea is to then use the Raptor
encoder to produce additional random triples and then use the Raptor
encoder to produce other encoding symbols, called repair symbols, from
the intermediate pre-coding symbols using the additional triples. The
source symbols and the repair symbols are sent to receivers.
If a receiver receives all K of the source symbols then there is no need
for any decoding. If there is at least one missing source symbol then
from the systematic information associated with K the receiver can
generate the K source symbol triples and the additional triples
corresponding to received repair symbols. The Raptor decoder can be
used to recover the intermediate pre-coding symbols from any received
combination of source and repair symbols that is slightly more than K
symbols in total using the corresponding triples for the received
Luby/Shokrollahi Section 5.1. [Page 28]
INTERNET-DRAFT Expires: April 2005 October 2004
symbols, and then the Raptor encoder can be used to recover the missing
source symbols from the intermediate pre-coding symbols using the
triples for the missing source symbols.
5.2. Systematic information
The K triples for the source symbols are generated from the systematic
information as described in Section 5.3. How the systematic information
is generated is described in Section 5.6. The systematic information for
each relevant value of K can either be stored or generated as needed at
each receiver. The systematic information associated with a source
block of K source symbols is:
* An integer T.
* Integers A and B such that 0 < A < 65,521 and 0 <= B < 65,521.
* A list of T integers 0 < M[0] < M[1] < ... < M[T-1] < K+T.
Typically, T can be represented with one byte, while all the other
values can be represented with two bytes. For example, for K = 1,000,
the value of T is at most 10, so that the description of the systematic
information is at most 25 bytes. This representation can be further
shortened, e.g., the sequence M[0], ... , M[T-1] could be stored as
successive differences, and the differences typically take one byte.
5.3. Generating source symbol triples from systematic information
The K source symbol triples (d[0], a[0], b[0]), ... , (d[K-1], a[K-1],
b[K-1]) are generated as follows from the systematic information (T, A,
B, M[0],..., M[T-1]) associated with K. Note that L' is smallest prime
that is at least the number L of intermediate pre-coding symbols.
Generate K triples for source symbols
* Set i = 0, j = 0, t = 0, X = B.
* While i < K do
o If t < T and j = M[t] then t = t+1
Luby/Shokrollahi Section 5.3. [Page 29]
INTERNET-DRAFT Expires: April 2005 October 2004
o Else
- d[i] = Deg[Rand[X,0, 2^20]]
- a[i] = 1 + Rand[X, 1, L'-1]
- b[i] = Rand[X, 2, L']
- i = i+1
o X = (X + A) MOD 65,521
o j = j + 1
Note that it is not necessary to store T explicitly, since it can be
obtained from the other data.
5.4. Calculating the intermediate pre-coding symbols
The L intermediate pre-coding symbols are obtained by applying the
Raptor decoder described in Section 3 to the source symbols C[0], C[1],
..., C[K-1] using the decoding schedule calculated from the K source
symbol triples (d[0], a[0], b[0]),..., (d[K-1], a[K-1], b[K-1]). The
procedure for obtaining the source symbol triples guarantees that the
decoding is successful. The result of this operation is the L
intermediate pre-coding symbols I[0], I[1],..., I[L-1].
5.5. Work and decoding failure probability
At the sender, the intermediate pre-coding symbols can be calculated
with essentially the same work as a decoding step of the Raptor decoder
described in Section 3. From the degree distribution of the Raptor
encoder described in Section 2, it can be seen that the work to generate
repair symbols from intermediate pre-coding symbols is on average 4.63
times the total length in bytes of generated repair symbols.
At the receiver, there is no work to be done if all the source symbols
are received. If there is at least one missing source symbol, then the
average work for decoding the intermediate pre-coding symbols from
received source and repair symbols is essentially the same as the
average work for the Raptor decoder described in Section 3. The
additional work to recreate missing source symbols from the intermediate
pre-coding symbols is on average 4.63 times the length in bytes of
Luby/Shokrollahi Section 5.5. [Page 30]
INTERNET-DRAFT Expires: April 2005 October 2004
missing source symbols.
The decoding failure probability of the Raptor systematic decoder for a
given reception overhead is the same as for Raptor decoder described in
Section 3.
5.6. Calculating the systematic information
In the description below o will denote the chosen reception overhead.
We recall the matrix interpretation of the Raptor decoding process as
described in Section 3, and the four phases of the decoding process. In
that decoding algorithm an elimination process is applied to a matrix A
that is derived from the received symbols, and the pre-coding symbols.
The matrix has N rows corresponding to the N received symbols, and S+H
rows corresponding to the S LDPC and H half symbols. The systematic
information associated with K is computed as follows:
(1) Set A = 53,591, B = 10,267
(2) Compute N = ceil((1 + o)*K)
(3) Repeat the following until the systematic information is
generated:
(a) X = B
(b) Repeat the following for i = 0,...,N-1
(i) Y[i] = Rand[X, 0, 2^16].
(ii) X = (X+A) MOD 65,521
(c) Apply the first phase of the decoding algorithm described in
Section 3 until the number of rows in the matrix I
corresponding to received symbols is K-10, or until the
first phase is finished, whichever is first. Let Y[i1],
Y[i2], ..., Y[im] denote the Y-values corresponding to these
rows.
(d) If the first phase is not yet finished, i.e., if the matrix
X has columns, then replace the matrix U by the matrix
obtained from X and U.
(e) In the second phase of the algorithm (elimination of the
matrix U) use the rows of the matrix corresponding to the
LDPC and the half-symbols as pivot rows.
Luby/Shokrollahi Section 5.6. [Page 31]
INTERNET-DRAFT Expires: April 2005 October 2004
(f) If this is not possible, then
(i) A = (A*10,267) MOD 65,521
(ii) B = X
(iii) Go to Step (3a).
(g) If the pivoting on the LDPC and half symbols is possible in
Step (3e) then
(i) Let Y[im+1],...,Y[iK] denote the Y-values of the pivot
rows of U that do not correspond to the LDPC or half
symbols.
(ii) Set E be the maximum value among i1, i2,..., iK . Set
T = E+1-K and compute the T indices among 0,..., E
missing from i1, i2, ..., iK, and let these indices in
increasing order be M[0], M[1],..., M[T-1].
(h) Return the systematic information (T, A, B, M[0], M[1],...,
M[T-1]).
The systematic information associated for K can be computed for all
relevant values of K once and for all and packaged with the Raptor
decoder software to receivers. Alternatively, receivers may calculate
the systematic information using the algorithm described above for
relevant values of K on an as needed basis. As another alternative, a
mixed strategy can be used, where the systematic information for some
values of K is packaged with the Raptor decoder software and as
systematic information for other values of K is needed the receiver
computes this on the fly, and once computed potentially saved for later
use. Furthermore, the K source symbol triples for a given value of K
can be saved for reuse with other source blocks once they are computed.
6. Raptor Systematic Object Delivery
This section specifies how to use the Raptor systematic code specified
in Section 5 for reliable delivery of an object to many receivers in an
IP multicast network. This could also be used for delivery using other
types of networks, e.g., unicast networks, but this is outside the scope
of this document.
This section also defined a new Fully-Specified FEC scheme (as defined
in RFC3452 [4] and a corresponding new FEC Encoding ID (with an as yet
Luby/Shokrollahi Section 6. [Page 32]
INTERNET-DRAFT Expires: April 2005 October 2004
undefined number) and the corresponding FEC Object Transmission
Information and FEC Payload ID format.
The FEC scheme described in this section is almost identical to the FEC
scheme described in Section 4. As described below, the only difference
in encoding is that the sent encoding symbols for a source block consist
of the source symbols of the source block and the repair symbols
generated from the intermediate pre-coding symbols, whch are in turn
generated from teh source symbols using the systematic information.
There are analogous differences in the decoding algorithm. The overall
properties of this FEC scheme are exactly the same as those for the FEC
scheme defined in Section 4, except that: (a) the encoding and decoding
are both slightly more complex; (b) the original object is sent as part
of the encoding.
6.1. Session and packet information
The overall structure of the FEC Object Transmission Information and the
FEC Payload ID are both defined in [4]. The receiver needs to receive
the specific FEC Object Transmission Information in a session
description (for example, carried in a FLUTE FDT as described in [8])
generally before starting to receive packets for a object to determine
some of the critical parameters needed to decode the object. The FEC
Payload ID is carried in each packet to identify the encoding symbols
carried in that packet.
6.1.1. FEC Object Transmission Information
Besides the FEC Encoding ID, the FEC Object Transmission Information is
the same as for the FEC scheme described in Section 4: the object size F
in bytes; the payload size P of each packet in bytes: the maximum source
block size B in bytes; the maximum working memory size W in bytes that
indicates the largest sub-block that can be decoded in receiver working
memory.
Some suggested values for these parameters, the relationships between
them, and the way parameters G, K, N and T are computed based on them is
all the same as described in Section 4.
Luby/Shokrollahi Section 6.1.1. [Page 33]
INTERNET-DRAFT Expires: April 2005 October 2004
6.1.2. FEC Payload ID
The FEC Payload ID is the same as for the FEC scheme described in
Section 4.
6.2. Encoding an object
All the examples in the subsequent subsections used the suggested
parameter settings of P = 512 bytes, W = 256 KB and B = 4 MB.
6.2.1. Smaller objects
When the object size F <= W the object consists of a single source block
that in turn consists of one sub-block, i.e., Z = N = 1.
Everything is computed exactly the same way as described in Section
4.4.1, except for how the encoding symbols, i.e., source and repair
symbols, and ESIs are generated.
Each packet sent for the object either contains all source symbols
(source packet) or all repair symbols (repair packet).
Each source packet contains G source symbols, except for perhaps the
last source packet which may be either of shorter length or padded out
to the same length as all other source packets if K is not a multiple of
G. The source symbols are placed into source packets sequentially,
i.e., the first source packet contains the first G source symbols, the
second source packet contains the next G source symbols, etc. The ESI
carried in the ith source packet is (i-1)*G, which is the index of the
first source symbol carried in that packet where the indices of the
source symbols are 0,...,K-1.
The K source symbol triples (d[0], a[0], b[0]),..., (d[K-1], a[K-1],
b[K-1]) are generated as described in Section 5.3 from the systematic
information (T, A, B, M[0],..., M[T-1]) associated with K. Then, the
Raptor decoder described in Section 3 is used to recover the L
intermediate pre-coding symbols from the K source symbols using the K
source symbol triples.
The ESI values placed into the R repair RTP packets are K, K+G, K+2*G,
... , K+(R-1)*G, respectively. The G repair symbol triples (d[0], a[0],
b[0]),..., (d[G-1], a[G-1], b[G-1]) for the repair symbols placed into a
repair RTP packet with ESI i are computed as follows, and this depends
on T, A, and B, which is a portion of the systematic information
associated with K.
Luby/Shokrollahi Section 6.2.1. [Page 34]
INTERNET-DRAFT Expires: April 2005 October 2004
Generate G repair symbol triples for repair packet with ESI i
* X = (B + (i+T)*A)) MOD 65,521
* v = Rand[X, 0, 2^20]
* Repeat the following for j = 0,...,G-1
o d[j] = Deg[v]
o a[j] = 1 + Rand[X, 1, L'-1]
o b[j] = Rand[X, 2, L']
o v = (v + ceil(2^20/G)) MOD 2^20
o X = (X + A) MOD 65,521
The Raptor encoder described in Section 2 is used to generate the G
repair symbols from the L intermediate pre-coding symbols using the G
triples associated with the repair packet carrying the repair symbols.
6.2.2. Larger objects
When the object size F is more than W but at most B then the object
consists of a single source block that is partitioned into N sub-blocks,
where the length of each sub-block is greater than W/2 but at most W.
Everything is computed exactly the same way as described in Section
4.4.2, except that Section 6.2.1 is used instead of Section 4.4.1.
6.2.3. Large objects
When the object size F is more than B then the object is partitioned
into more than one source block using the Algorithm for Computing Source
Block Structure described in Section 5.1.2.3 of FLUTE [8]. Everything
is computed exactly the same way as described in Section 4.4.3, except
that Section 6.2.1 is used instead of Section 4.4.1 and Section 6.2.2 is
used instead of Section 4.4.2.
Luby/Shokrollahi Section 6.2.3. [Page 35]
INTERNET-DRAFT Expires: April 2005 October 2004
6.3. Decoding an object
Just like for encoding, there are three cases of how to decide how to
recover the object, depending on the object size F. When F <= W then the
object is decoded as a single source block. Each received encoding
packet contains an ESI and one or more encoding symbols. The ESI is
used to reconstruct how each encoding symbol contained in the encoding
packet was generated, and then when enough encoding packets have arrived
the object is decoded.
Decoding is performed on a sub-block by sub-block basis. A decoding
schedule is created based on received ESIs for a source block, and then
that same decoding schedule can be used to decode all sub-blocks of the
source block. Each sub-block is decoded using the algorithms described
in Section 3, where the sub-block is substituted for the source block
and the encoding sub-symbols are substituted for the encoding symbols in
that description.
Decoding of each source block works as follows. If no source symbols
are missing then no decoding is necessary. If some source symbols are
missing then it is checked to see if enough repair symbols have been
received to recover the missing source symbols. If so, it decodes the
missing source symbols as follows:
* From the systematic information (T, A, B, M[0],..., M[T-1])
associated with K, generate the K source symbol triples using the
algorithm in Section 5.3.
* Determine which source symbols have been received.
* From the ESIs in received repair packets, generate the triples for
the received repair symbols using the algorithm in Section 6.2.1.
* Use the Raptor decoder described in Section 3 to recover the L
intermediate pre-coding symbols from the received source symbols and
repair symbols using their corresponding triples.
* Use the Raptor encoder described in Section 2 and the triples for
the missing source symbols to recover the missing source symbols
from the L intermediate pre-coding symbols.
7. Security Considerations
The security considerations for this document are the same as they are
for RFC 3452 [4].
Luby/Shokrollahi Section 7. [Page 36]
INTERNET-DRAFT Expires: April 2005 October 2004
8. IANA Considerations
Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA
registration. For general guidelines on IANA considerations as they
apply to this document, see RFC 3452 [4]. This document assigns the
Fully-Specified FEC Encoding ID X under the ietf:rmt:fec:encoding name-
space to "Raptor object". The FEC Payload ID format and corresponding
FEC Object Transmission Information associated with FEC Encoding ID X is
described in Section 4.3, and the corresponding FEC scheme is described
in Section 4 of this document.
This document assigns the Fully-Specified FEC Encoding ID Y under the
ietf:rmt:fec:encoding name-space to "Raptor systematic object". The FEC
Payload ID format and corresponding FEC Object Transmission Information
associated with FEC Encoding ID Y is described in Section 6.1, and the
corresponding FEC scheme is described in Section 6 of this document.
9. Intellectual Property
Digital Fountain does have intellectual property rights associated with
the technology described in this document, and intends to provide a full
IPR statement specific to this document to the IETF that will satisfy
the requirements of the IETF.
10. Normative References
[1] Bradner, S., "The Internet Standards Process -- Revision 3", RFC
2026, October 1996.
[2] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", RFC 2119, March 1997.
[3] Kermode, R., Vicisano, L., ``Author Guidelines for Reliable
Multicast Transport (RMT) Building Blocks and Protocol Instantiation
documents'', RFC 3269, April 2002.
[4] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M. and J.
Crowcroft, "Forward Error Correction (FEC) Building Block", RFC 3452,
December 2002.
[5] Luby, M. and Vicisano, L., "Compact Forward Error Correction (FEC)
Schemes", RFC 3695, February 2004.
Luby/Shokrollahi Section 10. [Page 37]
INTERNET-DRAFT Expires: April 2005 October 2004
[6] Mankin, A., Romanow, A., Bradner, S., Paxson V., "IETF Criteria for
Evaluating Reliable Multicast Transport and Application Protocols", RFC
2357, June 1998.
[7] Whetten, B., Vicisano, L., Kermode, R., Handley, M., Floyd, S.,
Luby, M., "Reliable Multicast Transport Building Blocks for One-to-Many
Bulk-Data Transfer", RFC 3048, January 2001.
[8] T. Paila, M. Luby, R. Lehtonen, V. Roca, R. Walsh, ''FLUTE - File
Delivery over Unidirectional Transport'', IETF RMT working group, RFC
3926, October 2004
11. Informative References
[9] M. Luby. ''LT Codes'', Proceedings of The 43rd Annual IEEE Symposium
on Foundations of Computer Science, November 16-19 2002, pp. 271-282.
[10] A. Shokrollahi, ''Raptor Codes'', Digital Fountain Technical
Report, DF2003-06-001
[11] J. Byers, M. Luby, M. Mitzenmacher, ''A Digital Fountain Approach
to Asynchronous Reliable Multicast'', IEEE J. on Selected Areas in
Communications, Special Issue on Network Support for Multicast
Communication, Vol. 20, No. 8, October 2002, pp. 1528 - 1540
[12] Luby, M., Gemmell, J., Vicisano, L., Rizzo, L. and J. Crowcroft,
"Asynchronous Layered Coding (ALC) Protocol Instantiation", RFC 3450
December 2002.
[13] Luby, M., Gemmell, J., Vicisano, L., Rizzo, L., Handley, M. and J.
Crowcroft, "Layered Coding Transport (LCT) Building Block", RFC 3451
December 2002.
[14] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M. and J.
Crowcroft, "The Use of Forward Error Correction (FEC) in Reliable
Multicast", RFC 3453, December 2002.
12. Authors' Addresses
Michael Luby
luby@digitalfountain.com
Digital Fountain, Inc.
39141 Civic Center Drive
Luby/Shokrollahi Section 12. [Page 38]
INTERNET-DRAFT Expires: April 2005 October 2004
Suite 300
Fremont, CA 94538
U.S.A.
M. Amin Shokrollahi
amin.sholrollahi@epfl.ch
Laboratory of Algorithms
Laboratory of Algorithmic Mathematics
EPFL
IC-IIF-ALGO
PSE-A
1015 Lausanne
Switzerland
Luby/Shokrollahi Section 12. [Page 39]
INTERNET-DRAFT Expires: April 2005 October 2004
13. Full Copyright Statement
Copyright (C) The Internet Society (2004).
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors retain
all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR
IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Luby/Shokrollahi Section 13. [Page 40]
INTERNET-DRAFT Expires: April 2005 October 2004
Luby/Shokrollahi Section 13. [Page 41]