Reliable Multicast Transport M. Luby
Internet-Draft Qualcomm, Inc.
Intended status: Standards Track A. Shokrollahi
Expires: May 14, 2010 EPFL
M. Watson
Qualcomm, Inc.
T. Stockhammer
Nomor Research
November 10, 2009
RaptorG Forward Error Correction Scheme for Object Delivery
draft-luby-rmt-bb-fec-raptorg-object-01
Abstract
This document describes a Fully-Specified FEC scheme, corresponding
to FEC Encoding ID XXX, for the RaptorG forward error correction code
and its application to reliable delivery of data objects.
RaptorG codes are a new family of codes to provide superior
flexibility, larger source block sizes and better coding efficiency
than Raptor codes in RFC5053. RaptorG is also 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 of data. The
decoder is able to recover the source block from any set of encoding
symbols for most cases equal to the number of source symbols and in
rare cases with slightly more than the number of source symbols.
The RaptorG code described here is a systematic code, meaning that
all the source symbols are among the encoding symbols that can be
generated.
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79.
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 as "work in progress."
Luby, et al. Expires May 14, 2010 [Page 1]
Internet-Draft RaptorG FEC Scheme November 2009
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on May 14, 2010.
Copyright Notice
Copyright (c) 2009 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents in effect on the date of
publication of this document (http://trustee.ietf.org/license-info).
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document.
Luby, et al. Expires May 14, 2010 [Page 2]
Internet-Draft RaptorG FEC Scheme November 2009
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Requirements notation . . . . . . . . . . . . . . . . . . . . . 4
3. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . . 5
3.1. FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . . 5
3.2. FEC Object Transmission Information . . . . . . . . . . . . 5
4. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.1. Content Delivery Protocol Requirements . . . . . . . . . . 8
4.2. Example parameter derivation algorithm . . . . . . . . . . 8
4.3. Object delivery . . . . . . . . . . . . . . . . . . . . . 10
5. RaptorG FEC code specification . . . . . . . . . . . . . . . 13
5.1. Definitions, Symbols and abbreviations . . . . . . . . . 13
5.2. Overview . . . . . . . . . . . . . . . . . . . . . . . . 16
5.3. Systematic RaptorG encoder . . . . . . . . . . . . . . . 18
5.4. Example FEC decoder . . . . . . . . . . . . . . . . . . . 31
5.5. Random Numbers . . . . . . . . . . . . . . . . . . . . . 37
5.6. Systematic indices and other parameters . . . . . . . . . 41
5.7. Arithmetic in GF(256) . . . . . . . . . . . . . . . . . . 45
6. Security Considerations . . . . . . . . . . . . . . . . . . . 47
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 48
8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 49
9. References . . . . . . . . . . . . . . . . . . . . . . . . . 50
9.1. Normative references . . . . . . . . . . . . . . . . . . 50
9.2. Informative references . . . . . . . . . . . . . . . . . 50
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 51
Luby, et al. Expires May 14, 2010 [Page 3]
Internet-Draft RaptorG FEC Scheme November 2009
1. Introduction
This document specifies an FEC Scheme for the RaptorG forward error
correction code for object delivery applications. The concept of an
FEC Scheme is defined in RFC5052 [RFC5052] and this document follows
the format prescribed there and uses the terminology of that
document. An initial version of a Raptor code was introduced in
RFC5053 [RFC5053]. The RaptorG code described herein is a next
generation of Raptor code with superior reliability, better coding
efficiency, and support for larger source block sizes than the Raptor
code of RFC5053 [RFC5053]. These improvements simplify the usage of
the RaptorG code in an object delivery Content Delivery Protocol
compared to RFC5053 [RFC5053].
The RaptorG FEC Scheme is a Fully-Specified FEC Scheme corresponding
to FEC Encoding ID XXX.
RaptorG 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 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.
The code described in this document is a systematic code, that is,
the original source symbols can be sent unmodified from sender to
receiver, as well as a number of repair symbols. For more backgound
on the use of Forward Error Correction codes in reliable multicast,
see [RFC3453].
Luby, et al. Expires May 14, 2010 [Page 4]
Internet-Draft RaptorG FEC Scheme November 2009
2. Requirements notation
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 [RFC2119].
Luby, et al. Expires May 14, 2010 [Page 5]
Internet-Draft RaptorG FEC Scheme November 2009
3. Formats and Codes
3.1. FEC Payload IDs
The FEC Payload ID MUST be a 4 octet field defined as follows:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| SBN | Encoding Symbol ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 1: FEC Payload ID format
Source Block Number (SBN), (8 bits): An integer identifier for the
source block that the encoding symbols within the packet relate
to.
Encoding Symbol ID (ESI), (24 bits): An integer identifier for the
encoding symbols within the packet.
The interpretation of the Source Block Number and Encoding Symbol
Identifier is defined in Section 5.
3.2. FEC Object Transmission Information
3.2.1. Mandatory
The value of the FEC Encoding ID MUST be XXX, as assigned by IANA
(see Section 7).
3.2.2. Common
The Common FEC Object Transmission Information elements used by this
FEC Scheme are:
- Transfer Length (F)
- Symbol Size (T)
The Transfer Length is a non-negative integer that is at most
946287651840, which can be represented by 40 bits. The Symbol Size
is a non-negative integer less than 2^^16.
The Transfer Length is a field of 40 bits in its definition, and the
Symbol Size field is 16 bits, and both length units are bytes.
The encoded Common FEC Object Transmission Information format is
Luby, et al. Expires May 14, 2010 [Page 6]
Internet-Draft RaptorG FEC Scheme November 2009
shown in Figure 2.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Transfer Length (F) |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | Reserved | Symbol Size (T) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 2: Encoded Common FEC OTI for RaptorG FEC Scheme
NOTE 1: The limit of 946287651840 on the transfer length is a
consequence of the limitation on the symbol size to 2^^16-1, the
limitation on the number of symbols in a source block to 56404 and
the limitation on the number of source blocks to 2^^8.
3.2.3. Scheme-Specific
The following parameters are carried in the Scheme-Specific FEC
Object Transmission Information element for this FEC Scheme:
o The number of source blocks (Z)
o The number of sub-blocks (N)
o A symbol alignment parameter (Al)
These parameters are all non-negative integers. The encoded Scheme-
specific Object Transmission Information is a 4-octet field
consisting of the parameters Z (12 bits), N (12 bits) and Al (8 bits)
as shown in Figure 3.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Z | N | Al |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 3: Encoded Scheme-specific FEC Object Transmission Information
The encoded FEC Object Transmission Information is a 14 octet field
consisting of the concatenation of the encoded Common FEC Object
Transmission Information and the encoded Scheme-specific FEC Object
Transmission Information.
These three parameters define the source block partitioning as
Luby, et al. Expires May 14, 2010 [Page 7]
Internet-Draft RaptorG FEC Scheme November 2009
described in Section 4.3.1.2
Luby, et al. Expires May 14, 2010 [Page 8]
Internet-Draft RaptorG FEC Scheme November 2009
4. Procedures
4.1. Content Delivery Protocol Requirements
This section describes the information exchange between the RaptorG
FEC Scheme and any Content Delivery Protocol (CDP) that makes use of
the RaptorG FEC Scheme for object delivery.
The RaptorG encoder scheme and RaptorG decoder scheme for object
delivery require the following information from the CDP:
o The transfer length of the object, F, in bytes
o A symbol alignment parameter, Al
o The symbol size, T, in bytes, which MUST be a multiple of Al
o The number of source blocks, Z
o The number of sub-blocks in each source block, N
The RaptorG encoder scheme for object delivery additionally requires:
- the object to be encoded, F bytes
The RaptorG encoder scheme supplies the CDP with the following
information for each packet to be sent:
o Source Block Number (SBN)
o Encoding Symbol ID (ESI)
o Encoding symbol(s)
The CDP MUST communicate this information to the receiver.
4.2. Example parameter derivation algorithm
This section provides recommendations for the derivation of the three
transport parameters, T, Z and N. This recommendation is based on the
following input parameters:
o F the transfer length of the object, in bytes
o WS the maximum size block that is decodable in working memory, in
bytes
Luby, et al. Expires May 14, 2010 [Page 9]
Internet-Draft RaptorG FEC Scheme November 2009
o P' the maximum payload size in bytes, which is assumed to be a
multiple of Al
o Al the symbol alignment parameter, in bytes
o SS a parameter where the desired lower bound on the sub-symbol
size is SS*Al
o K'_max the maximum number of source symbols per source block.
Note: Section 5.1.2 defines K'_max to be 56404
Based on the above inputs, the transport parameters T, Z and N are
calculated as follows:
Let,
o T = P'
o Kt = ceil(F/T)
o N_max = floor(T/(SS*Al))
o for all n=1, ..., N_max
* KL(n) is the maximum K' value in Table 2 in Section 5.6 such
that
K' <= floor (WS/(Al*(ceil(T/(Al*n)))))
o Z = ceil(Kt/KL(N_max))
o N is the minimum n=1, ..., N_max such that ceil (Kt/Z) <= KL(n)
It is RECOMMENDED that each packet contains exactly one symbol.
However, receivers SHALL support the reception of packets that
contain multiple symbols.
The value Kt is the total number of symbols required to represent the
source data of the object.
The algorithm above and that defined in Section 4.3.1.2 ensure that
the sub-symbol sizes are a multiple of the symbol alignment
parameter, Al. This is useful because the XOR operations used for
encoding and decoding are generally performed several bytes at a
time, for example at least 4 bytes at a time on a 32 bit processor.
Thus the encoding and decoding can be performed faster if the sub-
symbol sizes are a multiple of this number of bytes.
Luby, et al. Expires May 14, 2010 [Page 10]
Internet-Draft RaptorG FEC Scheme November 2009
The recommended settings for the input parameter Al is 4.
The parameter WS can be used to generate encoded data which can be
decoded efficiently with limited working memory at the decoder. Note
that the actual maximum decoder memory requirement for a given value
of WS depends on the implementation, but it is possible to implement
decoding using working memory only slightly larger than WS.
4.3. Object delivery
4.3.1. Source block construction
4.3.1.1. General
In order to apply the RaptorG encoder to a source object, the object
may be broken into Z >= 1 blocks, known as source blocks. The
RaptorG encoder is applied independently to each source block. Each
source block is identified by a unique integer Source Block Number
(SBN), where the first source block has SBN zero, the second has SBN
one, etc. Each source block is divided into a number, K, of source
symbols of size T bytes each. Each source symbol is identified by a
unique integer Encoding Symbol Identifier (ESI), where the first
source symbol of a source block has ESI zero, the second has ESI one,
etc.
Each source block with K source symbols is divided into N >= 1 sub-
blocks, which are small enough to be decoded in the working memory.
Each sub-block is divided into K sub-symbols of size T'.
Note that the value of K is not necessarily the same for each source
block of a object and the value of T' may not necessarily be the same
for each sub-block of a source block. However, the symbol size T is
the same for all source blocks of an object and the number of
symbols, K is the same for every sub-block of a source block. Exact
partitioning of the object into source blocks and sub-blocks is
described in Section 4.3.1.2 below.
4.3.1.2. Source block and sub-block partitioning
The construction of source blocks and sub-blocks is determined based
on five input parameters, F, Al, T, Z and N and a function
Partition[]. The five input parameters are defined as follows:
o F the transfer length of the object, in bytes
o Al a symbol alignment parameter, in bytes
Luby, et al. Expires May 14, 2010 [Page 11]
Internet-Draft RaptorG FEC Scheme November 2009
o T the symbol size, in bytes, which MUST be a multiple of Al
o Z the number of source blocks
o N the number of sub-blocks in each source block
These parameters MUST be set so that ceil(ceil(F/T)/Z) <= K'_max.
Recommendations for derivation of these parameters are provided in
Section 4.2.
The function Partition[] takes a pair of integers (I, J) as input and
derives four integers (IL, IS, JL, JS) as output. Specifically, the
value of Partition[I, J] is a sequence of four integers (IL, IS, JL,
JS), where IL = ceil(I/J), IS = floor(I/J), JL = I - IS * J and JS =
J - JL. Partition[] derives parameters for partitioning a block of
size I into J approximately equal sized blocks. Specifically, JL
blocks of length IL and JS blocks of length IS.
The source object MUST be partitioned into source blocks and sub-
blocks as follows:
Let,
o Kt = ceil(F/T)
o (KL, KS, ZL, ZS) = Partition[Kt, Z]
o (TL, TS, NL, NS) = Partition[T/Al, N]
Then, the object MUST be partitioned into Z = ZL + ZS contiguous
source blocks, the first ZL source blocks each having KL*T bytes,
i.e. KL source symbols of T bytes each, and the remaining ZS source
blocks each having KS*T bytes, i.e. KS source symbols of T bytes
each.
If Kt*T > F then for encoding purposes, the last symbol of the last
source block MUST be padded at the end with Kt*T-F zero bytes.
Next, each source block with K source symbols MUST be divided into N
= NL + NS contiguous sub-blocks, the first NL sub-blocks each
consisting of K contiguous sub-symbols of size of TL*Al bytes and the
remaining NS sub-blocks each consisting of K contiguous sub-symbols
of size of TS*Al bytes. The symbol alignment parameter Al ensures
that sub-symbols are always a multiple of Al bytes.
Finally, the m-th symbol of a source block consists of the
concatenation of the m-th sub-symbol from each of the N sub-blocks.
Note that this implies that when N > 1 then a symbol is NOT a
Luby, et al. Expires May 14, 2010 [Page 12]
Internet-Draft RaptorG FEC Scheme November 2009
contiguous portion of the object.
4.3.2. Encoding packet construction
Each encoding packet contains the following information:
o Source Block Number (SBN)
o Encoding Symbol ID (ESI)
o encoding symbol(s)
Each source block is encoded independently of the others. Source
blocks are numbered consecutively from zero.
Encoding Symbol ID values from 0 to K-1 identify the source symbols
of a source block in sequential order, where K is the number of
source symbols in the source block. Encoding Symbol IDs K onwards
identify repair symbols generated from the source symbols using the
RaptorG encoder.
Each encoding packet either consists entirely of source symbols
(source packet) or entirely of repair symbols (repair packet). A
packet may contain any number of symbols from the same source block.
In the case that the last source symbol in a source packet includes
padding bytes added for FEC encoding purposes then these bytes need
not be included in the packet. Otherwise, only whole symbols MUST be
included.
The Encoding Symbol ID, X, carried in each source packet is the
Encoding Symbol ID of the first source symbol carried in that packet.
The subsequent source symbols in the packet have Encoding Symbol IDs,
X+1 to X+G-1, in sequential order, where G is the number of symbols
in the packet.
Similarly, the Encoding Symbol ID, X, placed into a repair packet is
the Encoding Symbol ID of the first repair symbol in the repair
packet and the subsequent repair symbols in the packet have Encoding
Symbol IDs X+1 to X+G-1 in sequential order, where G is the number of
symbols in the packet.
Note that it is not necessary for the receiver to know the total
number of repair packets.
Luby, et al. Expires May 14, 2010 [Page 13]
Internet-Draft RaptorG FEC Scheme November 2009
5. RaptorG FEC code specification
5.1. Definitions, Symbols and abbreviations
For the purpose of the RaptorG FEC code specification in this
section, the following definitions, symbols and abbreviations apply.
5.1.1. Definitions
o Source block: a block of K source symbols which are considered
together for RaptorG encoding and decoding purposes.
o Extended Source Block: a block of K' source symbols, where K' >= K
constructed from a source block and zero or more padding symbols.
o Symbol: a unit of data. The size, in bytes, of a symbol is known
as the symbol size. The symbol size is always an integer.
o Source symbol: the smallest unit of data used during the encoding
process. All source symbols within a source block have the same
size.
o Padding symbol: a symbol with all zero bits that is added to the
source block to form the extended source block.
o Encoding symbol: a symbol that can be sent as part of the encoding
of a source block. The encoding symbols of a source block consist
of the source symbols of the source block and the repair symbols
generated from the source block. Repair symbols generated from a
source block have the same size as the source symbols of that
source block.
o Repair symbol: the encoding symbols of a source block that are not
source symbols. The repair symbols are generated based on the
source symbols of a source block.
o Intermediate symbols: symbols generated from the source symbols
using an inverse encoding process. The repair symbols are then
generated directly from the intermediate symbols. The encoding
symbols do not include the intermediate symbols, i.e.,
intermediate symbols are not sent as part of the encoding of a
source block. The intermediate symbols are partitioned into LT
symbols and PI symbols.
o LT symbols: The subset of the intermediate symbols that can be LT
neighbors of an encoding symbol.
Luby, et al. Expires May 14, 2010 [Page 14]
Internet-Draft RaptorG FEC Scheme November 2009
o PI symbols: The subset of the intermediate symbols that can be PI
neighbors of an encoding symbol.
o Systematic code: a code in which all source symbols are included
as part of the encoding symbols of a source block. The RaptorG
code as described herein is a systematic code.
o Encoding Symbol ID: information that uniquely identifies each
encoding symbol associated with a source block for sending and
receiving purposes.
o Internal Symbol ID: information that uniquely identifies each
symbol associated with an extended source block for encoding and
decoding purposes.
5.1.2. Symbols
i, j, u, v, h, d, a, b, d1, a1, b1, v, m, x, y represent values or
variables of one type or another, depending on the context.
X denotes a non-negative integer value that is either an ISI value
or an ESI value, depending on the context.
ceil(x) denotes the smallest integer which is greater than or equal
to x, where x is a real value.
floor(x) denotes the largest positive integer which is less than or
equal to x, where x is a real value.
min(x,y) denotes the minimum value of the values x and y, and in
general the minimum value of all the argument values.
max(x,y) denotes the maximum vaue of the values x and y, and in
general the maximum value of all the argument values.
i % j denotes i modulo j.
u ^ v denotes, for equal-length bit strings u and v, the bitwise
exclusive-or of u and v.
A denotes a matrix A.
Transpose[A] denotes the transposed matrix of matrix A.
A^^-1 denotes the inverse matrix of matrix A.
Luby, et al. Expires May 14, 2010 [Page 15]
Internet-Draft RaptorG FEC Scheme November 2009
K denotes the number of symbols in a single source block.
K' denotes the number of source plus padding symbols in an extended
source block. For the majority of this specification, the
padding symbols are considered to be additional source symbols.
K'_max denotes the maximum number of source symbols that can be in a
single source block. Set to 56404.
L denotes the number of intermediate symbols for a single extended
source block.
S denotes the number of LDPC symbols for a single extended source
block. These are LT symbols. For each value of K' shown in
Table 2 in Section 5.6, the corresponding value of S is a prime
number.
H denotes the number of HDPC symbols for a single extended source
block. These are PI symbols.
B denotes the number of intermediate symbols that are LT symbols
excluding the LDPC symbols.
W denotes the number of intermediate symbols that are LT symbols.
For each value of K' in Table 2 shown in Section 5.6, the
corresponding value of W is a prime number.
P denotes the number of intermediate symbols that are PI symbols.
These contain all HDPC symbols.
P1 denotes the smallest prime number greater than or equal to P.
U denotes the number of non-HDPC intermediate symbols that are PI
symbols.
C denotes an array of intermediate symbols, C[0], C[1], C[2],...,
C[L-1].
C' denotes an array of the symbols of the extended source block,
where C'[0], C'[1], C'[2],..., C'[K-1] are the source symbols of
the source block and C'[K], C'[K+1],..., C'[K'-1] are padding
symbols.
V0, V1, V2, V3 denote four arrays of 4-byte integers, V0[0],
V0[1],..., V0[255] ; V1[0], V1[1],..., V1[255]; V2[0],
V2[1],..., V2[255]; and V3[0], V3[1],..., V3[255] as shown in
Section 5.5.
Luby, et al. Expires May 14, 2010 [Page 16]
Internet-Draft RaptorG FEC Scheme November 2009
Rand[y, i, m] a pseudo-random number generator
Deg[v] a degree generator
Enc[K', C ,(d, a, b, d1, a1, b1)] an encoding symbol generator
Tuple[K', X] a tuple generator function
GF(n) denotes the Galois field with n elements.
T denotes the symbol size in bytes.
Q Q = 4294967291, i.e., Q is the largest prime smaller than 2^^32.
J(K') denotes the systematic index associated with K'.
G denotes any generator matrix.
I_S denotes the SxS identity matrix.
a ^^ b denotes the operation a raised to the power b.
5.1.3. Abbreviations
ESI Encoding Symbol ID
GF Galois Field
HDPC High Density Parity Check
ISI Internal Symbol ID
LDPC Low Density Parity Check
LT Luby Transform
PI Permanently Interactive
SBN Source Block Number
SBL Source Block Length (in units of symbols)
5.2. Overview
This section defines the systematic RaptorG FEC code.
Symbols are the fundamental data units of the encoding and decoding
process. For each source block all symbols are the same size,
Luby, et al. Expires May 14, 2010 [Page 17]
Internet-Draft RaptorG FEC Scheme November 2009
referred to as the symbol size T. The atomic operations performed on
symbols for both encoding and decoding are the exclusive-or operation
between symbols and an operation of the elements of the finite field
GF(256) upon symbols.
The basic encoder is described in Section 5.3. The encoder first
derives a block of intermediate symbols from the source symbols of a
source block. This intermediate block has the property that both
source and repair symbols can be generated from it using the same
process. The encoder produces repair symbols from the intermediate
block using an efficient process, where each such repair symbol is
the exclusive OR of a small number of intermediate symbols from the
block. Source symbols can also be reproduced from the intermediate
block using the same process. The encoding symbols are the
combination of the source and repair symbols.
An example of a decoder is described in Section 5.4. The process for
producing source and repair symbols from the intermediate block is
designed so that the intermediate block can be recovered from any
sufficiently large set of encoding symbols, independent of the mix of
source and repair symbols in the set. Once the intermediate block is
recovered, missing source symbols of the source block can be
recovered using the encoding process.
If a RaptorG compliant decoding algorithm receives a mathematically
sufficient set of encoding symbols generated according to the encoder
specification in Section 5.3 for reconstruction of a source block
then such a decoder SHALL recover the entire source block. A number
of decoding algorithms are possible to achieve this optimal behavior.
An efficient decoding algorithm to achieve this is provided in
Section 5.4.
The construction of the intermediate and repair symbols is based in
part on a pseudo-random number generator described in Section 5.3.
This generator is based on a fixed set of 1024 random numbers which
must be available to both sender and receiver. These numbers are
provided in Section 5.5. Encoding and decoding operations for
RaptorG use operations in the field GF(256). Section 5.7 provides a
recommended way to perform these operations.
Finally, the construction of the intermediate symbols from the source
symbols is governed by "systematic indices", values of which are
provided in Section 5.6 for specific extended source block sizes
between 6 and K'_max = 56404 source symbols. Thus, the RaptorG code
supports source blocks with between 1 and 56404 source symbols.
Luby, et al. Expires May 14, 2010 [Page 18]
Internet-Draft RaptorG FEC Scheme November 2009
5.3. Systematic RaptorG encoder
5.3.1. Introduction
For a given source block of K source symbols, for encoding and
decoding purposes the source block is augmented with K'-K additional
padding symbols, where K' is the smallest value that is at least K in
the systematic index Table 2 of Section 5.6. The reason for padding
out a source block to a multiple of K' is to enable faster encoding
and decoding, and to minimize the amount of table information that
needs to be stored in the encoder and decoder.
For purposes of transmitting and receiving data, the value of K is
used to determine the number of source symbols in a source block, and
thus K needs to be known at the sender and the receiver. In this
case the sender and receiver can compute K' from K and the K'-K
padding symbols can be automatically added to the source block
without any additional communication. The encoding symbol ID (ESI)
is used by a sender and receiver to identify the encoding symbols of
a source block, where the encoding symbols of a source block consist
of the source symbols and the repair symbols associated with the
source block. For a source block with K source symbols, the ESIs for
the source symbols are 0,1,2,...,K-1 and the ESIs for the repair
symbols are K, K+1, K+2,... . Using the ESI for identifying encoding
symbols in transport ensures that the ESI values continue
consecutively between the source and repair symbols.
For purposes of encoding and decoding data, the value of K' derived
from K is used as the number of source symbols of the extended source
block upon which encoding and decoding operations are performed,
where the K' source symbols consist of the original K source symbols
and an additional K'-K padding symbols. The internal symbol ID (ISI)
is used by the encoder and decoder to identify the symbols associated
with the extended source block, i.e., for generating encoding symbols
and for decoding. For a source block with K original source symbols,
the ISIs for the original source symbols are 0,1,2,...,K-1, the ISIs
for the K'-K padding symbols are K, K+1, K+2,..., K'-1, and the ISIs
for the repair symbols are K', K'+1, K'+2,... . Using the ISI for
encoding and decoding allows the padding symbols of the extended
source block to be treated the same way as other source symbols of
the extended source block, and that a given prefix of repair symbols
are generated in a consistent way for a given number K' of source
symbols in the extended source block independent of K.
The relationship between the ESIs and the ISIs is simple: the ESIs
and the ISIs for the original K source symbols are the same, the K'-K
padding symbols have an ISI but do not have a corresponding ESI
(since they are symbols that are neither sent nor received), and a
Luby, et al. Expires May 14, 2010 [Page 19]
Internet-Draft RaptorG FEC Scheme November 2009
repair symbol ISI is simply the repair symbol ESI plus K'-K. The
translation between ESIs used to identify encoding symbols sent and
received and the corresponding ISIs used for encoding and decoding,
and the proper padding of the extended source block with padding
symbols used for encoding and decoding, is the responsibility of the
padding function in the RaptorG encoder/decoder.
5.3.2. Encoding overview
The systematic RaptorG encoder is used to generate any number of
repair symbols from a source block that consists of K source symbols
placed into an extended source block C'. Figure 4 shows the encoding
overview.
The first step of encoding is to construct an extended source block
by adding zero or more padding symbols such that the total number of
symbols, K', is one of the values listed in Section 5.6. Each
padding symbol consists of T bytes where the value of each byte is
zero. K' MUST be selected as the smallest value of K' from the table
of Section 5.6 which is greater than or equal to K.
-----------------------------------------------------------+
| |
| +-----------+ +--------------+ +-------------+ |
C' | | | C' | Intermediate | C | | |
----+--->| Padding |--->| Symbol |--->| Encoding |--+-->
K | | | K' | Generation | L | | |
| +-----------+ +--------------+ +-------------+ |
| | (d,a,b, ^ |
| | d1,a1,b1)| |
| | +------------+ |
| | K' | Tuple | |
| +----------------------------->| | |
| | Generation | |
| +------------+ |
| ^ |
+-------------------------------------------------+--------+
|
ISI X
Figure 4: Encoding Overview
Let C'[0],..., C'[K-1] denote the K source symbols.
Let C'[K], ..., C'[K'-1] denote the K'-K padding symbols, which are
Luby, et al. Expires May 14, 2010 [Page 20]
Internet-Draft RaptorG FEC Scheme November 2009
all set to zero bits. Then, C'[0],..., C'[K'-1] are the symbols of
the extended source block upon which encoding and decoding are
performed.
In the remainder of this description these padding symbols will be
considered as additional source symbols and referred to as such.
However, these padding symbols are not part of the encoding symbols,
i.e., they are not sent as part of the encoding. At a receiver, the
value of K' can be computed based on K, then the receiver can insert
K'-K padding symbols at the end of a source block of K' source
symbols and recover the remaining K source symbols of the source
block from received encoding symbols.
The second step of encoding is to generate a number, L > K', of
intermediate symbols from the K' source symbols. In this step, K'
source tuples (d[0], a[0], b[0], d1[0], a1[0], b1[0]), ..., (d[K'-1],
a[K'-1], b[K'-1], d1[K'-1], a1[K'-1], b1[K'-1]) are generated using
the Tuple[] generator as described in Section 5.3.5.4. The K' source
tuples and the ISIs associated with the K' source symbols are used to
determine L intermediate symbols C[0],..., C[L-1] from the source
symbols using an inverse encoding process. This process can be
realized by a RaptorG decoding process.
Certain "pre-coding relationships" must hold within the L
intermediate symbols. Section 5.3.3.3 describes these relationships.
Section 5.3.3.4 describes how the intermediate symbols are generated
from the source symbols.
Once the intermediate symbols have been generated, repair symbols can
be produced. For a repair symbol with ISI X>K', the tuple of
integers, (d, a, b, d1, a1, b1) can be generated, using the Tuple[]
generator as described in Section 5.3.5.4. Then, the (d, a, b, d1,
a1, b1)-tuple and the ISI X is used to generate the corresponding
repair symbol from the intermediate symbols using the Enc[] generator
described in Section 5.3.5.3. The corresponding ESI for this repair
symbol is then X-(K'-K). Note that source symbols of the extended
source block can also be generated using the same process, i.e., for
any X < K', the symbol generated using this process has the same
value as C'(X).
5.3.3. First encoding step: Intermediate Symbol Generation
5.3.3.1. General
This encoding step is a pre-coding step to generate the L
intermediate symbols C[0], ..., C[L-1] from the source symbols C'[0],
..., C'[K'-1], , where L > K is defined in Section 5.3.3.3. The
intermediate symbols are uniquely defined by two sets of constraints:
Luby, et al. Expires May 14, 2010 [Page 21]
Internet-Draft RaptorG FEC Scheme November 2009
1. The intermediate symbols are related to the source symbols by a
set of source symbol tuples and by the ISIs of the source
symbols. The generation of the source symbol tuples is defined
in Section 5.3.3.2 using the the Tuple[] generator as described
in Section 5.3.5.4.
2. A set of pre-coding relationships hold within the intermediate
symbols themselves. These are defined in Section 5.3.3.3
The generation of the L intermediate symbols is then defined in
Section 5.3.3.4
5.3.3.2. Source symbol tuples
Each of the K' source symbols is associated with a source symbol
tuple (d[X], a[X], b[X], d1[X], a1[X], b1[X]) for 0 <= X < K'. The
source symbol tuples are determined using the Tuple generator defined
in Section 5.3.5.4 as:
For each X, 0 <= X < K'
(d[X], a[X], b[X], d1[X], a1[X], b1[X]) = Tuple[K, X]
5.3.3.3. Pre-coding relationships
The pre-coding relationships amongst the L intermediate symbols are
defined by requiring that a set of S+H linear combinations of the
intermediate symbols evaluate to zero. There are S LDPC and H HDPC
symbols, and thus L = K'+S+H. Another partition of the L intermediate
symbols is into two sets, one set of W LT symbols and another set of
P PI symbols, and thus it is also the case that L = W+P. The P PI
symbols are treated differently than the W LT symbols in the encoding
process. The P PI symbols consist of the H HDPC symbols together
with a set of U = P-H of the other K' intermediate symbols. The W LT
symbols consist of the S LDPC symbols together with W-S of the other
K' intermediate symbols. The values of these parameters are
determined from K' as described below where H(K'), S(K'), and W(K')
are derived from Table 2 in Section 5.6.
Let
o S = S(K')
o H = H(K')
o W = W(K')
Luby, et al. Expires May 14, 2010 [Page 22]
Internet-Draft RaptorG FEC Scheme November 2009
o L = K' + S + H
o P = L - W
o P1 denote the smallest prime number greater than or equal to P
o U =P - H
o B = W - S
o C[0], ..., C[B-1] denote the intermediate symbols that are LT
symbols but not LDPC symbols.
o C[B], ..., C[B+S-1] denote the S LDPC symbols that are also LT
symbols.
o C[W], ..., C[W+U-1] denote the intermediate symbols that are PI
symbols but not HDPC symbols.
o C[L-H], ..., C[L-1] denote the H HDPC symbols that are also PI
symbols.
The first set of pre-coding relations, called LDPC relations, is
described below and requires that at the end of this process the set
of symbols D[0] , ..., D[S-1] are all zero:
o Initialize the symbols D[0] = C[B], ... , D[S-1] = C[B+S-1].
o For i = 0, ..., B-1 do
* a = 1 + (floor(i/S) % (S-1))
* b = i % S
* D[b] = D[b] ^ C[i]
* b = (b + a) % S
* D[b] = D[b] ^ C[i]
* b = (b + a) % S
* D[b] = D[b] ^ C[i]
o For i = 0, ..., B-1 do
* a = i % P
Luby, et al. Expires May 14, 2010 [Page 23]
Internet-Draft RaptorG FEC Scheme November 2009
* b = (i+1) % P
* D[i] = D[i] ^ C[W+a] ^ C[W+b]
The second set of relations, called HDPC relations, is obtained by
considering each intermediate symbol as a sequence of elements from
the finite field GF(256). We represent elements of GF(256) in the
usual way as polynomials in one variable, x, with coefficients from
the finite field GF(2) modulo an irreducible polynomial f(x). A
single byte of data from a symbol, b7,b6,b5,b4,b3,b2,b1,b0, where b7
is the highest order bit and b0 is the lowest order bit, corresponds
to the finite field element
b7 x^^7 + b6 x^^6 + b5 x^^5 + b4 x^^4 + b3 x^^3 + b2 x^^2 + b1 x +
b0 mod f(x)
The irreducible polynomial f(x) is defined to be:
f(x) = x^^8 + x^^4 + x^^3 + x^^2 + 1.
We then define the operation of elements of GF(256) on symbols as
follows:
Let
o beta denote an element of GF(256).
o C denote a symbol of length T bytes.
o c[0], ..., c[T-1] denote the bytes of C.
o gamma[0], ..., gamma[T-1] denote the elements of GF(256)
corresponding to c[0], ..., c[T-1] respectively.
Then we define
delta[i] = beta*gamma[i] for i=0, ..., T-1
where '*' represents the usual multiplication operation in GF(256).
A multiplication table for GF(256) and a recommended way to perform
calculations in GF(256) is provided in Section 5.7. Then the
operation of beta on C is defined as follows:
beta*C = d[0], ..., d[T-1]
where d[i] is the byte value corresponding to delta[i] for i=0,...,
T-1.
Luby, et al. Expires May 14, 2010 [Page 24]
Internet-Draft RaptorG FEC Scheme November 2009
The set of HDPC relations among the intermediate symbols C[0], ...,
C[K'+S+H-1] is defined as follows:
Let
o alpha denote a generator element of GF(256), specifically the
element represented by the polynomial x mod f(x).
o T denote an H x (K' +S ) matrix with elements from GF(256), where
for j=0,...,K'+S-2 the entry T[i,j] is the identity element if i=
Rand[j,6,H] or i = (Rand[j,6,H] + Rand[j,7,H-1] + 1) % H and
T[i,j] is the zero element for all other values of i, and for
j=K'+S-1, T[i,j] = alpha^^i for i=0,...,H-1.
o GAMMA denote a (K'+S ) x (K'+S ) matrix with elements from
GF(256), where
o
GAMMA[i,j] =
alpha ^^ (i-j) for i <= j
0 otherwise
Then the relationship between the first K'+S intermediate symbols
C[0], ..., C[K'+S-1] and the H HDPC symbols C[K'+S], ..., C[K'+S+H-1]
is given by:
Transpose[C[K'+S], ..., C[K'+S+H-1]] + T* GAMMA * Transpose[C[0],
..., C[K'+S-1]] = 0
where '*' represents standard matrix multiplication utilizing the
above defined operation to define the multiplication between a matrix
over GF(256) and a matrix of symbols (in particular the column vector
of symbols).
The H HDPC relations may be conveniently described using the
following algorithm, where u is a working register containing a
single symbol. These relations require that the values of the
symbols D[S], ..., D[S+H-1] are zero at the end of the following
process.
o Initialize the symbols D[S] = C[K'+S], ..., D[S+H-1] = C[K'+S+H-1]
o u = C[0]
Luby, et al. Expires May 14, 2010 [Page 25]
Internet-Draft RaptorG FEC Scheme November 2009
o For j = 1, ..., K'+S-1 do
* pos1 = Rand[j,6,H]
* pos2 = (pos1 + Rand[j,7,H-1] + 1) % H
* D[S+pos1] = D[S+pos1] ^ u
* D[S+pos2] = D[S+pos2] ^ u
* u = (alpha*u) ^ C[j]
o For i = 0, ..., H-1
* D[S+i] = D[S+i] ^ u
* u = (alpha*u)
5.3.3.4. Intermediate symbols
5.3.3.4.1. Definition
Given the K' source symbols C'[0], C'[1],..., C'[K'-1] the L
intermediate symbols C[0], C[1],..., C[L-1] are the uniquely defined
symbol values that satisfy the following conditions:
1. The K' source symbols C'[0], C'[1],..., C'[K'-1] satisfy the K'
constraints
C'[X] = Enc[K', (C[0],..., C[L-1]), (d[X], a[X], b[X], d1[X],
a1[X], b1[X])], for all X, 0 <= X < K',
where (d[X], a[X], b[X], d1[X], a1[X], b1[X])) = Tuple[K',X],
Tuple[] is defined in Section 5.3.5.4 and Enc[] is described in
Section 5.3.5.3.
2. The L intermediate symbols C[0], C[1],..., C[L-1] satisfy the
pre-coding relationships defined in Section 5.3.3.3
5.3.3.4.2. Example method for calculation of intermediate symbols
This section describes a possible method for calculation of the L
intermediate symbols C[0], C[1],..., C[L-1] satisfying the
constraints in Section 5.3.3.4.1
The generator matrix G for a code which generates n output symbols
from k input symbols is an n x k matrix over GF(256), where each row
corresponds to one of the output symbols and each column to one of
Luby, et al. Expires May 14, 2010 [Page 26]
Internet-Draft RaptorG FEC Scheme November 2009
the input symbols and where the i-th output symbol is equal to the
sum of the product of each input symbol with the corresponding entry
in row i.
Then, the L intermediate symbols can be calculated as follows:
Let
o C denote the column vector of the L intermediate symbols, C[0],
C[1],..., C[L-1].
o D denote the column vector consisting of S+H zero symbols followed
by the K' source symbols C'[0], C'[1], ..., C'[K'-1].
Then the above constraints define an L x L matrix A over GF(256) such
that:
A*C = D
The matrix A can be constructed as follows:
Let:
o G_LDPC,1 and G_LDPC,2 be S x B and S x P matrices such that
G_LDPC,1 * Transpose[(C[0],...., C[B-1])] + G_LDPC,2 *
Transpose(C[W], ..., C[W+U-1]) + Transpose[(C[B], ...,
C[B+S-1])] = 0
and "+" is the component-wise XOR of the vectors involved.
o G_HDPC be the H x (K'+S) generator matrix of the HDPC symbols, So,
G_HDPC * Transpose(C[0], ..., C[K'+S-1]) = Transpose(C[K'+S],
..., C[L-1]),
i.e. G_HDPC = H*GAMMA
o I_S be the S x S identity matrix
o I_H be the H x H identity matrix
o G_ENC be the K'x L generator matrix of the encoding symbols
generated by the Encoder. So,
G_ENC * Transpose[(C[0], ..., C[L-1])] =
Transpose[(C'[0],C'[1],...,C'[K'-1])],
Luby, et al. Expires May 14, 2010 [Page 27]
Internet-Draft RaptorG FEC Scheme November 2009
i.e. G_ENC[i,j] = 1 if and only if C[j] is included in the
symbols which are XORed to produce Enc[K', (C[0], ..., C[L-1]),
(d[i], a[i], b[i], d1[i], a1[i], b1[i])] and G_ENC[i,j] = 0
otherwise.
Then:
o The first S rows of A are equal to G_LDPC,1 | I_S | G_LDPC,2.
o The next H rows of A are equal to G_HDPC | I_H.
o The remaining K' rows of A are equal to G_ENC.
The matrix A is depicted in Figure (Figure 5) below:
B S U H
+-----------------------+-------+------------------+
| | | |
S | G_LDPC,1 | I_S | G_LDPC,2 |
| | | |
+-----------------------+-------+----------+-------+
| | |
H | G_HDPC | I_H |
| | |
+------------------------------------------+-------+
| |
| |
K' | G_LT |
| |
| |
+--------------------------------------------------+
Figure 5: The matrix A
The intermediate symbols can then be calculated as:
C = (A^^-1)*D
The source tuples are generated such that for any K' matrix A has
full rank and is therefore invertible. This calculation can be
realized by applying a RaptorG decoding process to the K' source
symbols C'[0], C'[1],..., C'[K'-1] to produce the L intermediate
symbols C[0], C[1],..., C[L-1].
To efficiently generate the intermediate symbols from the source
symbols, it is recommended that an efficient decoder implementation
such as that described in Section 5.4 be used.
Luby, et al. Expires May 14, 2010 [Page 28]
Internet-Draft RaptorG FEC Scheme November 2009
5.3.4. Second encoding step: Encoding
In the second encoding step, the repair symbol with ISI X (X >= K')
is generated by applying the generator LTEnc[K', (C[0], C[1],...,
C[L-1]), (d, a, b, d1, a1, b1)] defined in Section 5.3.5.3 to the L
intermediate symbols C[0], C[1],..., C[L-1] using the tuple (d, a, b,
d1, a1, b1)=Tuple[K',X].
5.3.5. Generators
5.3.5.1. Random Generator
The random number generator Rand[y, i, m] is defined as follows,
where y is a non-negative integer, i is a non-negative integer less
than 256, and m is a positive integer and the value produced is an
integer between 0 and m-1. Let V0, V1, V2 and V3 be arrays of 256
entries each, where each entry is a 4-byte unsigned integer. These
arrays are provided in Section 5.5.
Let
o x0 = (y + i) mod 2^^8
o x1 = (floor(y / 2^^8) + i) mod 2^^8
o x2 = (floor(y / 2^^16) + i) mod 2^^8
o x3 = (floor(y / 2^^24) + i) mod 2^^8
Then,
Rand[y, i, m] = (V0[x0] ^ V1[x1] ^ V2[x2] ^ V3[x3]) % m
5.3.5.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 = 1048576. Given v,
find index d in Table 1 such that f[d-1] <= v < f[d], and set Deg[v]
= min(d, W-2).
Luby, et al. Expires May 14, 2010 [Page 29]
Internet-Draft RaptorG FEC Scheme November 2009
+---------+---------+---------+---------+
| Index d | f[d] | Index d | f[d] |
+---------+---------+---------+---------+
| 0 | 0 | 1 | 5243 |
+---------+---------+---------+---------+
| 2 | 529531 | 3 | 704294 |
+---------+---------+---------+---------+
| 4 | 791675 | 5 | 844104 |
+---------+---------+---------+---------+
| 6 | 879057 | 7 | 904023 |
+---------+---------+---------+---------+
| 8 | 922747 | 9 | 937311 |
+---------+---------+---------+---------+
| 10 | 948962 | 11 | 958494 |
+---------+---------+---------+---------+
| 12 | 966438 | 13 | 973160 |
+---------+---------+---------+---------+
| 14 | 978921 | 15 | 983914 |
+---------+---------+---------+---------+
| 16 | 988283 | 17 | 992138 |
+---------+---------+---------+---------+
| 18 | 995565 | 19 | 998631 |
+---------+---------+---------+---------+
| 20 | 1001391 | 21 | 1003887 |
+---------+---------+---------+---------+
| 22 | 1006157 | 23 | 1008229 |
+---------+---------+---------+---------+
| 24 | 1010129 | 25 | 1011876 |
+---------+---------+---------+---------+
| 26 | 1013490 | 27 | 1014983 |
+---------+---------+---------+---------+
| 28 | 1016370 | 29 | 1017662 |
+---------+---------+---------+---------+
| 30 | 1048576 | | |
+---------+---------+---------+---------+
Table 1: Defines the degree distribution for encoding symbols
5.3.5.3. Encoding Symbol Generator
The encoding symbol generator Enc[K', (C[0], C[1],..., C[L-1]), (d,
a, b, d1, a1, b1)] takes the following inputs:
o K' is the number of source symbols for the extended source block.
Let L, W, B, S, and P be derived from K' as described in
Section 5.3.3.3.
Luby, et al. Expires May 14, 2010 [Page 30]
Internet-Draft RaptorG FEC Scheme November 2009
o (C[0], C[1],..., C[L-1]) is the array of L intermediate symbols
(sub-symbols) generated as described in Section 5.3.3.4
o (d, a, b, d1, a1, b1) is a source tuple determined from ISI X
using the Tuple generator defined in Section 5.3.5.4, whereby
* d is an integer denoting an encoding symbol LT degree
* a is an integer between 1 and W-1 inclusive
* b is an integer between 0 and W-1 inclusive
* d1 is an integer between 2 and 3 inclusive denoting an encoding
symbol PI degree
* a1 is an integer between 1 and P1-1 inclusive
* b1 is an integer between 0 and P1-1 inclusive
The encoding symbol generator produces a single encoding symbol as
output, according to the following algorithm:
o result = C[b].
o For j = 1, ..., d-1 do
* b = (b + a) % W
* result = result ^ C[b]
o while (b1 >= P) do b1 = (b1+a1) % P1
o result = result ^ C[W+b1]
o For j = 1, ..., d1-1 do
* b1 = (b1 + a1) % P1
* while (b1 >= P) do b1 = (b1+a1) % P1
* result = result ^ C[W+b1]
o Return result
Luby, et al. Expires May 14, 2010 [Page 31]
Internet-Draft RaptorG FEC Scheme November 2009
5.3.5.4. Tuple generator
The tuple generator Tuple[K',X] takes the following inputs:
o K' - The number of source symbols in the extended source block
o X - An Intermediate symbol ID (ISI)
Let
o L be determined from K' as described in Section 5.3.3.3
o Q = 4294967291, the largest prime smaller than 2^^32.
o J=J(K') be the systematic index associated with K', as defined
inTable 2 inSection 5.6
The output of the source symbol tuple generator is a tuple, (d, a, b,
d1, a1, b1) determined as follows:
o A = 1 + (53591 + J*997) % Q
o B = 10267*(J+1) % Q
o y = (B + X*A) % Q
o v = Rand[y, 0, 2^^20]
o d = Deg[v]
o a = 1 + Rand[y, 1, W-1]
o b = Rand[y, 2, W]
o if (d<4) { d1 = 2 + Rand[y, 3, 2] } else { d1 = 2 }
o a1 = 1 + Rand[y, 4, P1-1]
o d1 = Rand[y, 5, P1]
5.4. Example FEC decoder
5.4.1. General
This section describes an efficient decoding algorithm for the
RaptorG code introduced in this specification. Note that each
received encoding symbol can be considered as the value of an
equation amongst the intermediate symbols. From these simultaneous
Luby, et al. Expires May 14, 2010 [Page 32]
Internet-Draft RaptorG FEC Scheme November 2009
equations, and the known pre-coding relationships amongst the
intermediate symbols, any algorithm for solving simultaneous
equations can successfully decode the intermediate symbols and hence
the source symbols. However, the algorithm chosen has a major effect
on the computational efficiency of the decoding.
5.4.2. Decoding an extended source block
5.4.2.1. General
It is assumed that the decoder knows the structure of the source
block it is to decode, including the symbol size, T, and the number K
of symbols in the source block and the number K' of source symbols in
the extended source block.
From the algorithms described in Sections Section 5.3, the RaptorG
decoder can calculate the total number L = K'+S+H of intermediate
symbols and determine how they were generated from the extended
source block to be decoded. In this description it is assumed that
the received encoding symbols for the extended source block to be
decoded are passed to the decoder. Furthermore, for each such
encoding symbol it is assumed that the number and set of intermediate
symbols whose exclusive-or is equal to the encoding symbol is passed
to the decoder. In the case of source symbols, including padding
symbols, the source symbol tuples described in Section 5.3.3.2
indicate the number and set of intermediate symbols which sum to give
each source symbol.
Let N >= K' be the number of received encoding symbols to be used for
decoding, including padding symbols for an extended source block and
let M = S+H+N. Then with the notation of Section 5.3.3.4.2 we have
A*C=D.
Decoding an extended source block is equivalent to decoding C from
known A and D. It is clear that C can be decoded if and only if the
rank of A is L. Once C has been decoded, missing source symbols can
be obtained by using the source symbol tuples to determine the number
and set of intermediate symbols which must be exclusive-ORed to
obtain each missing source symbol.
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
Luby, et al. Expires May 14, 2010 [Page 33]
Internet-Draft RaptorG FEC Scheme November 2009
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.
o Each time a multiple, beta, of row i of A is added to row i' in
the decoding schedule then in the decoding process the symbol
beta*D[d[i]] is added to symbol D[d[i']] .
o Each time a row i of A is multiplied by a field element beta, then
in the decoding process the symbol D[d[i]] is also multiplied by
beta.
o 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'].
o 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
operations on symbols in the decoding of the extended 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 is
not described here). The remainder of this section describes an
order in which Gaussian elimination could be performed that is
relatively efficient.
5.4.2.2. First Phase
The first phase of the Gaussian elimination the matrix A is
conceptually partitioned into submatrices and additionally, a matrix
X is created. This matrix has as many rows and columns as A, and it
will be a lower triangular matrix throughout the first phase. At the
beginning of this phase, the matrix A is copied into the matrix X.
The submatrix sizes are parameterized by non-negative integers i and
Luby, et al. Expires May 14, 2010 [Page 34]
Internet-Draft RaptorG FEC Scheme November 2009
u which are initialized to 0 and P, the number of PI symbols,
respectively. 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.
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 V formed by the intersection of all but the first i
columns and the last u columns and all but the first i rows.
Figure 6 illustrates the submatrices of A. At the beginning of the
first phase V = A. In each step, a row of A is chosen.
+-----------+-----------------+---------+
| | | |
| I | All Zeros | |
| | | |
+-----------+-----------------+ U |
| | | |
| | | |
| All Zeros | V | |
| | | |
| | | |
+-----------+-----------------+---------+
Figure 6: Submatrices of A in the first phase
The following graph defined by the structure of V is used in
determining which row of A is chosen. The columns that intersect V
are the nodes in the graph, and the rows that have exactly 2 non-zero
entries in V and are not HDPC rows 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.
Luby, et al. Expires May 14, 2010 [Page 35]
Internet-Draft RaptorG FEC Scheme November 2009
There are at most L steps in the first phase. The phase ends
successfully when i + u = L, i.e., when V and the all zeroes
submatrix above V 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 V disappears there is no non-
zero row in V to choose in that step. In each step, a row of A is
chosen as follows:
o If all entries of V are zero then no row is chosen and decoding
fails.
o Let r be the minimum integer such that at least one row of A has
exactly r ones in V.
* If r != 2 then choose a row with exactly r ones in V with
minimum original degree among all such rows, except that HDPC
rows should not be chosen until all non-HDPC rows have been
processed.
* If r = 2 then choose any row with exactly 2 ones in V that is
part of a maximum size component in the graph described above
which is defined by V.
After the row is chosen in this step the first row of A that
intersects V is exchanged with the chosen row so that the chosen row
is the first row that intersects V. The columns of A among those that
intersect V are reordered so that one of the r ones in the chosen row
appears in the first column of V and so that the remaining r-1 ones
appear in the last columns of V. The same row and column operations
are also performed on the matrix X. Then, an appropriate multiple of
the chosen row is added to all the other rows of A below the chosen
row that have a non-zero entry in the first column of V.
Specifically, if a row below the chosen row has entry beta in the
first column of V, and the chosen row has entry alpha in the first
column of V, then beta/alpha multiplied by the chosen row is added to
this row to leave a zero value in the first column of V. Finally, i
is incremented by 1 and u is incremented by r-1, which completes the
step.
Note that efficiency can be improved if the row operations identified
above are not actually performed until the affected row is itself
chosen during the decoding process. This avoids processing of row
operations for rows which are not eventually used in the decoding
process and in particular avoid those rows for which beta!=1 until
they are actually required. Furthermore, the row operations required
for the HDPC rows may be performed for all such rows in one process,
by using the algorithm described in Section 5.3.3.3.
Luby, et al. Expires May 14, 2010 [Page 36]
Internet-Draft RaptorG FEC Scheme November 2009
5.4.2.3. Second Phase
At this point, all the entries of X outside the first i rows and i
columns are discarded, so that X has lower triangular form. The last
i rows and columns of X are discarded, so that X now has i rows i
columns. The submatrix U is further partitioned into the first i
rows, U_upper, and the remaining M - i rows, Ulower. Gaussian
elimination is performed in the second phase on U_lower 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 I_u. The M - L rows of A that intersect U_lower - I_u are
discarded. After this phase A has L rows and L columns.
5.4.2.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
U_upper. The number of rows i of the submatrix U_upper is generally
much larger than the number of columns u of U_upper. Moreover, at
this time, the matrix U_upper is typically dense, i.e., the number of
nonzero entries of this matrix is large. To reduce this matrix to a
sparse form, the sequence of operations performed to obtain the
matrix U_lower needs to be inverted. To this end, the matrix X is
multiplied with the submatrix of A consisting of the first i rows of
A. After this operation the submatrix of A consisting of the
intersection of the first i rows and columns equals to X, whereas the
matrix U_upper is transformed to a sparse form.
5.4.2.5. Fourth Phase
For each of the first i rows of U_upper do the following: if the row
has a nonzero entry at position j, and if the value of that nonzero
entry is b, then add to this row b times row j of I_u. After this
step, the submatrix of A consisting of the intersection of the first
i rows and columns is equal to X, the submatrix U_upper consists of
zeros, the submatrix consisting of the intersection of the last u
rows and the first i columns consists of zeros, and the submatrix
consisting of the last u rows and columns is is the matrix I_u.
5.4.2.6. Fifth Phase
For j from 1 to i perform the following operations:
1. if A[j,j] is not one, then divide row j of A by A[j,j].
2. For l from 1 to j-1, if A[j,l] is nonzero, then add A[j,l]
multiplied with row l of A to row j of A.
Luby, et al. Expires May 14, 2010 [Page 37]
Internet-Draft RaptorG FEC Scheme November 2009
After this phase A is the L by L identity matrix and a complete
decoding schedule has been successfully formed. Then, the
corresponding decoding consisting of exclusive-ORing known encoding
symbols can be executed to recover the intermediate symbols based on
the decoding schedule. The tuples associated with all source symbols
are computed according to Section 5.3.3.2. The tuples for received
source symbols are used in the decoding. The tuples for missing
source symbols are used to determine which intermediate symbols need
to be exclusive-ORed to recover the missing source symbols.
5.5. Random Numbers
The four tables V0, V1, V2 and V3 described in Section 5.3.5.1 are
given below. Each entry is a 32-bit integer in decimal
representation.
5.5.1. The table V0
251291136, 3952231631, 3370958628, 4070167936, 123631495, 3351110283,
3218676425, 2011642291, 774603218, 2402805061, 1004366930,
1843948209, 428891132, 3746331984, 1591258008, 3067016507,
1433388735, 504005498, 2032657933, 3419319784, 2805686246,
3102436986, 3808671154, 2501582075, 3978944421, 246043949,
4016898363, 649743608, 1974987508, 2651273766, 2357956801, 689605112,
715807172, 2722736134, 191939188, 3535520147, 3277019569, 1470435941,
3763101702, 3232409631, 122701163, 3920852693, 782246947, 372121310,
2995604341, 2045698575, 2332962102, 4005368743, 218596347,
3415381967, 4207612806, 861117671, 3676575285, 2581671944,
3312220480, 681232419, 307306866, 4112503940, 1158111502, 709227802,
2724140433, 4201101115, 4215970289, 4048876515, 3031661061,
1909085522, 510985033, 1361682810, 129243379, 3142379587, 2569842483,
3033268270, 1658118006, 932109358, 1982290045, 2983082771,
3007670818, 3448104768, 683749698, 778296777, 1399125101, 1939403708,
1692176003, 3868299200, 1422476658, 593093658, 1878973865,
2526292949, 1591602827, 3986158854, 3964389521, 2695031039,
1942050155, 424618399, 1347204291, 2669179716, 2434425874,
2540801947, 1384069776, 4123580443, 1523670218, 2708475297,
1046771089, 2229796016, 1255426612, 4213663089, 1521339547,
3041843489, 420130494, 10677091, 515623176, 3457502702, 2115821274,
2720124766, 3242576090, 854310108, 425973987, 325832382, 1796851292,
2462744411, 1976681690, 1408671665, 1228817808, 3917210003,
263976645, 2593736473, 2471651269, 4291353919, 650792940, 1191583883,
3046561335, 2466530435, 2545983082, 969168436, 2019348792,
2268075521, 1169345068, 3250240009, 3963499681, 2560755113,
911182396, 760842409, 3569308693, 2687243553, 381854665, 2613828404,
2761078866, 1456668111, 883760091, 3294951678, 1604598575,
1985308198, 1014570543, 2724959607, 3062518035, 3115293053,
138853680, 4160398285, 3322241130, 2068983570, 2247491078,
Luby, et al. Expires May 14, 2010 [Page 38]
Internet-Draft RaptorG FEC Scheme November 2009
3669524410, 1575146607, 828029864, 3732001371, 3422026452,
3370954177, 4006626915, 543812220, 1243116171, 3928372514,
2791443445, 4081325272, 2280435605, 885616073, 616452097, 3188863436,
2780382310, 2340014831, 1208439576, 258356309, 3837963200,
2075009450, 3214181212, 3303882142, 880813252, 1355575717, 207231484,
2420803184, 358923368, 1617557768, 3272161958, 1771154147,
2842106362, 1751209208, 1421030790, 658316681, 194065839, 3241510581,
38625260, 301875395, 4176141739, 297312930, 2137802113, 1502984205,
3669376622, 3728477036, 234652930, 2213589897, 2734638932,
1129721478, 3187422815, 2859178611, 3284308411, 3819792700,
3557526733, 451874476, 1740576081, 3592838701, 1709429513,
3702918379, 3533351328, 1641660745, 179350258, 2380520112,
3936163904, 3685256204, 3156252216, 1854258901, 2861641019,
3176611298, 834787554, 331353807, 517858103, 3010168884, 4012642001,
2217188075, 3756943137, 3077882590, 2054995199, 3081443129,
3895398812, 1141097543, 2376261053, 2626898255, 2554703076,
401233789, 1460049922, 678083952, 1064990737, 940909784, 1673396780,
528881783, 1712547446, 3629685652, 1358307511
5.5.2. The table V1
807385413, 2043073223, 3336749796, 1302105833, 2278607931, 541015020,
1684564270, 372709334, 3508252125, 1768346005, 1270451292,
2603029534, 2049387273, 3891424859, 2152948345, 4114760273,
915180310, 3754787998, 700503826, 2131559305, 1308908630, 224437350,
4065424007, 3638665944, 1679385496, 3431345226, 1779595665,
3068494238, 1424062773, 1033448464, 4050396853, 3302235057,
420600373, 2868446243, 311689386, 259047959, 4057180909, 1575367248,
4151214153, 110249784, 3006865921, 4293710613, 3501256572, 998007483,
499288295, 1205710710, 2997199489, 640417429, 3044194711, 486690751,
2686640734, 2394526209, 2521660077, 49993987, 3843885867, 4201106668,
415906198, 19296841, 2402488407, 2137119134, 1744097284, 579965637,
2037662632, 852173610, 2681403713, 1047144830, 2982173936, 910285038,
4187576520, 2589870048, 989448887, 3292758024, 506322719, 176010738,
1865471968, 2619324712, 564829442, 1996870325, 339697593, 4071072948,
3618966336, 2111320126, 1093955153, 957978696, 892010560, 1854601078,
1873407527, 2498544695, 2694156259, 1927339682, 1650555729,
183933047, 3061444337, 2067387204, 228962564, 3904109414, 1595995433,
1780701372, 2463145963, 307281463, 3237929991, 3852995239,
2398693510, 3754138664, 522074127, 146352474, 4104915256, 3029415884,
3545667983, 332038910, 976628269, 3123492423, 3041418372, 2258059298,
2139377204, 3243642973, 3226247917, 3674004636, 2698992189,
3453843574, 1963216666, 3509855005, 2358481858, 747331248,
1957348676, 1097574450, 2435697214, 3870972145, 1888833893,
2914085525, 4161315584, 1273113343, 3269644828, 3681293816,
412536684, 1156034077, 3823026442, 1066971017, 3598330293,
1979273937, 2079029895, 1195045909, 1071986421, 2712821515,
3377754595, 2184151095, 750918864, 2585729879, 4249895712,
Luby, et al. Expires May 14, 2010 [Page 39]
Internet-Draft RaptorG FEC Scheme November 2009
1832579367, 1192240192, 946734366, 31230688, 3174399083, 3549375728,
1642430184, 1904857554, 861877404, 3277825584, 4267074718,
3122860549, 666423581, 644189126, 226475395, 307789415, 1196105631,
3191691839, 782852669, 1608507813, 1847685900, 4069766876,
3931548641, 2526471011, 766865139, 2115084288, 4259411376,
3323683436, 568512177, 3736601419, 1800276898, 4012458395, 1823982,
27980198, 2023839966, 869505096, 431161506, 1024804023, 1853869307,
3393537983, 1500703614, 3019471560, 1351086955, 3096933631,
3034634988, 2544598006, 1230942551, 3362230798, 159984793, 491590373,
3993872886, 3681855622, 903593547, 3535062472, 1799803217, 772984149,
895863112, 1899036275, 4187322100, 101856048, 234650315, 3183125617,
3190039692, 525584357, 1286834489, 455810374, 1869181575, 922673938,
3877430102, 3422391938, 1414347295, 1971054608, 3061798054,
830555096, 2822905141, 167033190, 1079139428, 4210126723, 3593797804,
429192890, 372093950, 1779187770, 3312189287, 204349348, 452421568,
2800540462, 3733109044, 1235082423, 1765319556, 3174729780,
3762994475, 3171962488, 442160826, 198349622, 45942637, 1324086311,
2901868599, 678860040, 3812229107, 19936821, 1119590141, 3640121682,
3545931032, 2102949142, 2828208598, 3603378023, 4135048896
5.5.3. The table V2
1629829892, 282540176, 2794583710, 496504798, 2990494426, 3070701851,
2575963183, 4094823972, 2775723650, 4079480416, 176028725,
2246241423, 3732217647, 2196843075, 1306949278, 4170992780,
4039345809, 3209664269, 3387499533, 293063229, 3660290503,
2648440860, 2531406539, 3537879412, 773374739, 4184691853,
1804207821, 3347126643, 3479377103, 3970515774, 1891731298,
2368003842, 3537588307, 2969158410, 4230745262, 831906319,
2935838131, 264029468, 120852739, 3200326460, 355445271, 2296305141,
1566296040, 1760127056, 20073893, 3427103620, 2866979760, 2359075957,
2025314291, 1725696734, 3346087406, 2690756527, 99815156, 4248519977,
2253762642, 3274144518, 598024568, 3299672435, 556579346, 4121041856,
2896948975, 3620123492, 918453629, 3249461198, 2231414958,
3803272287, 3657597946, 2588911389, 242262274, 1725007475,
2026427718, 46776484, 2873281403, 2919275846, 3177933051, 1918859160,
2517854537, 1857818511, 3234262050, 479353687, 200201308, 2801945841,
1621715769, 483977159, 423502325, 3689396064, 1850168397, 3359959416,
3459831930, 841488699, 3570506095, 930267420, 1564520841, 2505122797,
593824107, 1116572080, 819179184, 3139123629, 1414339336, 1076360795,
512403845, 177759256, 1701060666, 2239736419, 515179302, 2935012727,
3821357612, 1376520851, 2700745271, 966853647, 1041862223, 715860553,
171592961, 1607044257, 1227236688, 3647136358, 1417559141,
4087067551, 2241705880, 4194136288, 1439041934, 20464430, 119668151,
2021257232, 2551262694, 1381539058, 4082839035, 498179069, 311508499,
3580908637, 2889149671, 142719814, 1232184754, 3356662582,
2973775623, 1469897084, 1728205304, 1415793613, 50111003, 3133413359,
4074115275, 2710540611, 2700083070, 2457757663, 2612845330,
Luby, et al. Expires May 14, 2010 [Page 40]
Internet-Draft RaptorG FEC Scheme November 2009
3775943755, 2469309260, 2560142753, 3020996369, 1691667711,
4219602776, 1687672168, 1017921622, 2307642321, 368711460,
3282925988, 213208029, 4150757489, 3443211944, 2846101972,
4106826684, 4272438675, 2199416468, 3710621281, 497564971, 285138276,
765042313, 916220877, 3402623607, 2768784621, 1722849097, 3386397442,
487920061, 3569027007, 3424544196, 217781973, 2356938519, 3252429414,
145109750, 2692588106, 2454747135, 1299493354, 4120241887,
2088917094, 932304329, 1442609203, 952586974, 3509186750, 753369054,
854421006, 1954046388, 2708927882, 4047539230, 3048925996,
1667505809, 805166441, 1182069088, 4265546268, 4215029527,
3374748959, 373532666, 2454243090, 2371530493, 3651087521,
2619878153, 1651809518, 1553646893, 1227452842, 703887512,
3696674163, 2552507603, 2635912901, 895130484, 3287782244,
3098973502, 990078774, 3780326506, 2290845203, 41729428, 1949580860,
2283959805, 1036946170, 1694887523, 4880696, 466000198, 2765355283,
3318686998, 1266458025, 3919578154, 3545413527, 2627009988,
3744680394, 1696890173, 3250684705, 4142417708, 915739411,
3308488877, 1289361460, 2942552331, 1169105979, 3342228712,
698560958, 1356041230, 2401944293, 107705232, 3701895363, 903928723,
3646581385, 844950914, 1944371367, 3863894844, 2946773319,
1972431613, 1706989237, 29917467, 3497665928
5.5.4. The table V3
1191369816, 744902811, 2539772235, 3213192037, 3286061266,
1200571165, 2463281260, 754888894, 714651270, 1968220972, 3628497775,
1277626456, 1493398934, 364289757, 2055487592, 3913468088,
2930259465, 902504567, 3967050355, 2056499403, 692132390, 186386657,
832834706, 859795816, 1283120926, 2253183716, 3003475205, 1755803552,
2239315142, 4271056352, 2184848469, 769228092, 1249230754,
1193269205, 2660094102, 642979613, 1687087994, 2726106182, 446402913,
4122186606, 3771347282, 37667136, 192775425, 3578702187, 1952659096,
3989584400, 3069013882, 2900516158, 4045316336, 3057163251,
1702104819, 4116613420, 3575472384, 2674023117, 1409126723,
3215095429, 1430726429, 2544497368, 1029565676, 1855801827,
4262184627, 1854326881, 2906728593, 3277836557, 2787697002,
2787333385, 3105430738, 2477073192, 748038573, 1088396515,
1611204853, 201964005, 3745818380, 3654683549, 3816120877,
3915783622, 2563198722, 1181149055, 33158084, 3723047845, 3790270906,
3832415204, 2959617497, 372900708, 1286738499, 1932439099,
3677748309, 2454711182, 2757856469, 2134027055, 2780052465,
3190347618, 3758510138, 3626329451, 1120743107, 1623585693,
1389834102, 2719230375, 3038609003, 462617590, 260254189, 3706349764,
2556762744, 2874272296, 2502399286, 4216263978, 2683431180,
2168560535, 3561507175, 668095726, 680412330, 3726693946, 4180630637,
3335170953, 942140968, 2711851085, 2059233412, 4265696278,
3204373534, 232855056, 881788313, 2258252172, 2043595984, 3758795150,
3615341325, 2138837681, 1351208537, 2923692473, 3402482785,
Luby, et al. Expires May 14, 2010 [Page 41]
Internet-Draft RaptorG FEC Scheme November 2009
2105383425, 2346772751, 499245323, 3417846006, 2366116814,
2543090583, 1828551634, 3148696244, 3853884867, 1364737681,
2200687771, 2689775688, 232720625, 4071657318, 2671968983,
3531415031, 1212852141, 867923311, 3740109711, 1923146533,
3237071777, 3100729255, 3247856816, 906742566, 4047640575,
4007211572, 3495700105, 1171285262, 2835682655, 1634301229,
3115169925, 2289874706, 2252450179, 944880097, 371933491, 1649074501,
2208617414, 2524305981, 2496569844, 2667037160, 1257550794,
3399219045, 3194894295, 1643249887, 342911473, 891025733, 3146861835,
3789181526, 938847812, 1854580183, 2112653794, 2960702988,
1238603378, 2205280635, 1666784014, 2520274614, 3355493726,
2310872278, 3153920489, 2745882591, 1200203158, 3033612415,
2311650167, 1048129133, 4206710184, 4209176741, 2640950279,
2096382177, 4116899089, 3631017851, 4104488173, 1857650503,
3801102932, 445806934, 3055654640, 897898279, 3234007399, 1325494930,
2982247189, 1619020475, 2720040856, 885096170, 3485255499,
2983202469, 3891011124, 546522756, 1524439205, 2644317889,
2170076800, 2969618716, 961183518, 1081831074, 1037015347,
3289016286, 2331748669, 620887395, 303042654, 3990027945, 1562756376,
3413341792, 2059647769, 2823844432, 674595301, 2457639984,
4076754716, 2447737904, 1583323324, 625627134, 3076006391, 345777990,
1684954145, 879227329, 3436182180, 1522273219, 3802543817,
1456017040, 1897819847, 2970081129, 1382576028, 3820044861,
1044428167, 612252599, 3340478395, 2150613904, 3397625662,
3573635640, 3432275192
5.6. Systematic indices and other parameters
Table 2 below specifies the supported values of K'. The table also
specifies for each supported value of K' the systematic index J(K'),
the number H(K') of HDPC symbols, the number S(K') of LDPC symbols,
and the number W(K') of LT symbols. For each value of K', the
corresponding values of S(K') and W(K') are prime numbers.
The systematic index J(K') is designed to have the property that the
set of source symbol tuples (d[0], a[0], b[0], d1[0], a1[0], b1[0]),
..., (d[K'-1], a[K'-1], b[K'-1], d1[K'-1], a1[K'-1], b1[K'-1]) are
such that the L intermediate symbols are uniquely defined, i.e., the
matrix A in Figure 6 has full rank and is therefore invertible.
+-------+-------+-------+-------+-------+
| K' | J(K') | S(K') | H(K') | W(K') |
+-------+-------+-------+-------+-------+
| 6 | 3 | 5 | 10 | 11 |
+-------+-------+-------+-------+-------+
| 12 | 57 | 7 | 10 | 19 |
+-------+-------+-------+-------+-------+
| 18 | 27 | 11 | 10 | 29 |
Luby, et al. Expires May 14, 2010 [Page 42]
Internet-Draft RaptorG FEC Scheme November 2009
| 26 | 96 | 11 | 10 | 37 |
+-------+-------+-------+-------+-------+
| 32 | 959 | 11 | 10 | 43 |
+-------+-------+-------+-------+-------+
| 36 | 564 | 11 | 10 | 47 |
+-------+-------+-------+-------+-------+
| 42 | 39 | 11 | 10 | 53 |
+-------+-------+-------+-------+-------+
| 48 | 10 | 13 | 10 | 61 |
+-------+-------+-------+-------+-------+
| 55 | 531 | 13 | 10 | 67 |
+-------+-------+-------+-------+-------+
| 62 | 55 | 13 | 10 | 73 |
+-------+-------+-------+-------+-------+
| 69 | 235 | 13 | 10 | 79 |
+-------+-------+-------+-------+-------+
| 75 | 234 | 17 | 10 | 89 |
+-------+-------+-------+-------+-------+
| 88 | 113 | 17 | 10 | 101 |
+-------+-------+-------+-------+-------+
| 101 | 8 | 17 | 10 | 113 |
+-------+-------+-------+-------+-------+
| 114 | 8 | 19 | 10 | 127 |
+-------+-------+-------+-------+-------+
| 127 | 184 | 19 | 10 | 139 |
+-------+-------+-------+-------+-------+
| 140 | 7 | 19 | 10 | 151 |
+-------+-------+-------+-------+-------+
| 160 | 39 | 23 | 10 | 173 |
+-------+-------+-------+-------+-------+
| 185 | 751 | 23 | 10 | 197 |
+-------+-------+-------+-------+-------+
| 213 | 1 | 23 | 10 | 223 |
+-------+-------+-------+-------+-------+
| 242 | 10 | 29 | 10 | 257 |
+-------+-------+-------+-------+-------+
| 267 | 195 | 29 | 10 | 281 |
+-------+-------+-------+-------+-------+
| 295 | 572 | 29 | 10 | 307 |
+-------+-------+-------+-------+-------+
| 324 | 447 | 31 | 10 | 337 |
+-------+-------+-------+-------+-------+
| 362 | 751 | 31 | 10 | 373 |
+-------+-------+-------+-------+-------+
| 403 | 234 | 37 | 10 | 419 |
+-------+-------+-------+-------+-------+
| 443 | 974 | 37 | 10 | 457 |
+-------+-------+-------+-------+-------+
Luby, et al. Expires May 14, 2010 [Page 43]
Internet-Draft RaptorG FEC Scheme November 2009
+-------+-------+-------+-------+-------+
| 497 | 115 | 37 | 10 | 509 |
+-------+-------+-------+-------+-------+
| 555 | 17 | 41 | 10 | 569 |
+-------+-------+-------+-------+-------+
| 619 | 75 | 41 | 10 | 631 |
+-------+-------+-------+-------+-------+
| 685 | 476 | 47 | 10 | 701 |
+-------+-------+-------+-------+-------+
| 759 | 112 | 47 | 10 | 773 |
+-------+-------+-------+-------+-------+
| 839 | 454 | 53 | 10 | 857 |
+-------+-------+-------+-------+-------+
| 932 | 424 | 53 | 10 | 947 |
+-------+-------+-------+-------+-------+
| 1032 | 34 | 59 | 10 | 1051 |
+-------+-------+-------+-------+-------+
| 1144 | 600 | 61 | 11 | 1163 |
+-------+-------+-------+-------+-------+
| 1281 | 75 | 67 | 11 | 1303 |
+-------+-------+-------+-------+-------+
| 1420 | 726 | 67 | 11 | 1439 |
+-------+-------+-------+-------+-------+
| 1575 | 39 | 73 | 11 | 1597 |
+-------+-------+-------+-------+-------+
| 1734 | 83 | 79 | 11 | 1759 |
+-------+-------+-------+-------+-------+
| 1906 | 394 | 83 | 11 | 1931 |
+-------+-------+-------+-------+-------+
| 2103 | 75 | 89 | 11 | 2131 |
+-------+-------+-------+-------+-------+
| 2315 | 772 | 97 | 11 | 2347 |
+-------+-------+-------+-------+-------+
| 2550 | 726 | 97 | 11 | 2579 |
+-------+-------+-------+-------+-------+
| 2812 | 683 | 103 | 11 | 2843 |
+-------+-------+-------+-------+-------+
| 3101 | 512 | 113 | 11 | 3137 |
+-------+-------+-------+-------+-------+
| 3411 | 650 | 127 | 11 | 3457 |
+-------+-------+-------+-------+-------+
| 3751 | 838 | 127 | 11 | 3793 |
+-------+-------+-------+-------+-------+
| 4086 | 547 | 131 | 11 | 4127 |
+-------+-------+-------+-------+-------+
| 4436 | 305 | 139 | 11 | 4481 |
+-------+-------+-------+-------+-------+
| 4780 | 3 | 149 | 11 | 4831 |
Luby, et al. Expires May 14, 2010 [Page 44]
Internet-Draft RaptorG FEC Scheme November 2009
| 5134 | 518 | 157 | 11 | 5189 |
+-------+-------+-------+-------+-------+
| 5512 | 229 | 163 | 11 | 5569 |
+-------+-------+-------+-------+-------+
| 6070 | 980 | 173 | 11 | 6131 |
+-------+-------+-------+-------+-------+
| 6688 | 596 | 191 | 11 | 6761 |
+-------+-------+-------+-------+-------+
| 7360 | 960 | 197 | 11 | 7433 |
+-------+-------+-------+-------+-------+
| 8087 | 85 | 211 | 11 | 8167 |
+-------+-------+-------+-------+-------+
| 8886 | 479 | 223 | 11 | 8971 |
+-------+-------+-------+-------+-------+
| 9793 | 200 | 239 | 11 | 9887 |
+-------+-------+-------+-------+-------+
| 10779 | 290 | 257 | 11 | 10883 |
+-------+-------+-------+-------+-------+
| 11864 | 543 | 277 | 12 | 11981 |
+-------+-------+-------+-------+-------+
| 13046 | 893 | 293 | 12 | 13171 |
+-------+-------+-------+-------+-------+
| 14355 | 527 | 311 | 12 | 14489 |
+-------+-------+-------+-------+-------+
| 15786 | 601 | 337 | 12 | 15937 |
+-------+-------+-------+-------+-------+
| 17376 | 479 | 359 | 12 | 17539 |
+-------+-------+-------+-------+-------+
| 19126 | 518 | 389 | 12 | 19309 |
+-------+-------+-------+-------+-------+
| 21044 | 933 | 419 | 13 | 21247 |
+-------+-------+-------+-------+-------+
| 23177 | 85 | 449 | 13 | 23399 |
+-------+-------+-------+-------+-------+
| 25491 | 710 | 479 | 13 | 25733 |
+-------+-------+-------+-------+-------+
| 28035 | 11 | 521 | 13 | 28319 |
+-------+-------+-------+-------+-------+
| 30898 | 738 | 557 | 14 | 31219 |
+-------+-------+-------+-------+-------+
| 33988 | 602 | 599 | 14 | 34351 |
+-------+-------+-------+-------+-------+
| 37372 | 545 | 647 | 14 | 37783 |
+-------+-------+-------+-------+-------+
| 41127 | 11 | 701 | 15 | 41593 |
+-------+-------+-------+-------+-------+
| 45245 | 639 | 757 | 15 | 45767 |
+-------+-------+-------+-------+-------+
Luby, et al. Expires May 14, 2010 [Page 45]
Internet-Draft RaptorG FEC Scheme November 2009
+-------+-------+-------+-------+-------+
| 49791 | 249 | 821 | 15 | 50377 |
+-------+-------+-------+-------+-------+
| 54768 | 300 | 877 | 16 | 55411 |
+-------+-------+-------+-------+-------+
| 56404 | 733 | 907 | 16 | 57077 |
+-------+-------+-------+-------+-------+
Table 2: Systematic indices and other parameters
5.7. Arithmetic in GF(256)
5.7.1. Introduction
Elements of GF(256) are represented by bytes. In this section, we
opt to represent them by integers in the range 0 through 255. For
ease of exposition, operations in GF(256) are facilitated by two
tables: GF256_EXP, and GF256_LOG. GF256_EXP has 512 entries, whereas
GF256_LOG has 256 entries. For an integer i between 0 and 511,
GF256_EXP[i] is the binary value of the polynomial x^^i modulo x^^8 +
x^^4 + x^^3 + x^^2 + 1, whereas for i between 1 and 255 the value of
GF256_LOG[i] is the integer j such that the binary value of x^^j
modulo x^^8 + x^^4 + x^^3 + x^^2 + 1 is i. In this representation we
have
i + j = i ^ j, and
i * j =
0, if either i or j are 0,
GF256_EXP[GF256_LOG[i] + GF256_LOG[j]] otherwise
5.7.2. The table GF256_EXP
1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76,
152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157,
39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35,
70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222,
161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60,
120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 163,
91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26, 52,
104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 59,
118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218,
169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85,
170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198,
145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171,
75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25,
Luby, et al. Expires May 14, 2010 [Page 46]
Internet-Draft RaptorG FEC Scheme November 2009
50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81,
162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9,
18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11,
22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71,
142, 1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38,
76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192,
157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159,
35, 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111,
222, 161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30,
60, 120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223,
163, 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26,
52, 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147,
59, 118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218,
169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85,
170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198,
145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171,
75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25,
50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81,
162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9,
18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11,
22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71,
142, 1, 2
5.7.3. The table GF256_LOG
255, 0, 1, 25, 2, 50, 26, 198, 3, 223, 51, 238, 27, 104, 199, 75, 4,
100, 224, 14, 52, 141, 239, 129, 28, 193, 105, 248, 200, 8, 76, 113,
5, 138, 101, 47, 225, 36, 15, 33, 53, 147, 142, 218, 240, 18, 130,
69, 29, 181, 194, 125, 106, 39, 249, 185, 201, 154, 9, 120, 77, 228,
114, 166, 6, 191, 139, 98, 102, 221, 48, 253, 226, 152, 37, 179, 16,
145, 34, 136, 54, 208, 148, 206, 143, 150, 219, 189, 241, 210, 19,
92, 131, 56, 70, 64, 30, 66, 182, 163, 195, 72, 126, 110, 107, 58,
40, 84, 250, 133, 186, 61, 202, 94, 155, 159, 10, 21, 121, 43, 78,
212, 229, 172, 115, 243, 167, 87, 7, 112, 192, 247, 140, 128, 99, 13,
103, 74, 222, 237, 49, 197, 254, 24, 227, 165, 153, 119, 38, 184,
180, 124, 17, 68, 146, 217, 35, 32, 137, 46, 55, 63, 209, 91, 149,
188, 207, 205, 144, 135, 151, 178, 220, 252, 190, 97, 242, 86, 211,
171, 20, 42, 93, 158, 132, 60, 57, 83, 71, 109, 65, 162, 31, 45, 67,
216, 183, 123, 164, 118, 196, 23, 73, 236, 127, 12, 111, 246, 108,
161, 59, 82, 41, 157, 85, 170, 251, 96, 134, 177, 187, 204, 62, 90,
203, 89, 95, 176, 156, 169, 160, 81, 11, 245, 22, 235, 122, 117, 44,
215, 79, 174, 213, 233, 230, 231, 173, 232, 116, 214, 244, 234, 168,
80, 88, 175
Luby, et al. Expires May 14, 2010 [Page 47]
Internet-Draft RaptorG FEC Scheme November 2009
6. Security Considerations
Data delivery can be subject to denial-of-service attacks by
attackers which send corrupted packets that are accepted as
legitimate by receivers. This is particularly a concern for
multicast delivery because a corrupted packet may be injected into
the session close to the root of the multicast tree, in which case
the corrupted packet will arrive at many receivers. This is
particularly a concern when the code described in this document is
used because the use of even one corrupted packet containing encoding
data may result in the decoding of an object that is completely
corrupted and unusable. It is thus RECOMMENDED that source
authentication and integrity checking are applied to decoded objects
before delivering objects to an application. For example, a SHA-1
hash [SHA1] of an object may be appended before transmission, and the
SHA-1 hash is computed and checked after the object is decoded but
before it is delivered to an application. Source authentication
SHOULD be provided, for example by including a digital signature
verifiable by the receiver computed on top of the hash value. It is
also RECOMMENDED that a packet authentication protocol such as TESLA
[RFC4082] be used to detect and discard corrupted packets upon
arrival. This method may also be used to provide source
authentication. Furthermore, it is RECOMMENDED that Reverse Path
Forwarding checks be enabled in all network routers and switches
along the path from the sender to receivers to limit the possibility
of a bad agent successfully injecting a corrupted packet into the
multicast tree data path.
Another security concern is that some FEC information may be obtained
by receivers out-of-band in a session description, and if the session
description is forged or corrupted then the receivers will not use
the correct protocol for decoding content from received packets. To
avoid these problems, it is RECOMMENDED that measures be taken to
prevent receivers from accepting incorrect session descriptions,
e.g., by using source authentication to ensure that receivers only
accept legitimate session descriptions from authorized senders.
Luby, et al. Expires May 14, 2010 [Page 48]
Internet-Draft RaptorG FEC Scheme November 2009
7. 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 [RFC5052]. This document assigns the
Fully-Specified FEC Encoding ID XXX under the ietf:rmt:fec:encoding
name-space to "RaptorG Code".
Luby, et al. Expires May 14, 2010 [Page 49]
Internet-Draft RaptorG FEC Scheme November 2009
8. Acknowledgements
Thanks are due to Lorenz Minder and Ranganathan (Ranga) Krishnan.
Lorenz Minder did the original implementation of RaptorG, supervised
by Amin Shokrollahi. Ranga Krishnan has been very supportive in
finding and resolving implementation details and in finding the
systematic indices.
Luby, et al. Expires May 14, 2010 [Page 50]
Internet-Draft RaptorG FEC Scheme November 2009
9. References
9.1. Normative references
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC4082] Perrig, A., Song, D., Canetti, R., Tygar, J., and B.
Briscoe, "Timed Efficient Stream Loss-Tolerant
Authentication (TESLA): Multicast Source Authentication
Transform Introduction", RFC 4082, June 2005.
[SHA1] "Secure Hash Standard", Federal Information Processing
Standards Publication (FIPS PUB) 180-1,
April 2005.
[RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error
Correction (FEC) Building Block", RFC 5052, August 2007.
[RFC5053] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer,
"Raptor Forward Error Correction Scheme for Object
Delivery", RFC 5053, October 2007.
9.2. Informative references
[RFC3453] 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.
Luby, et al. Expires May 14, 2010 [Page 51]
Internet-Draft RaptorG FEC Scheme November 2009
Authors' Addresses
Michael Luby
Qualcomm, Inc.
3165 Kifer Road
Santa Clara, 95051 94538
U.S.A.
Email: luby@qualcomm.com
Amin Shokrollahi
EPFL
Laboratoire d'algorithmique
EPFL
Station 14
Batiment BC
Lausanne 1015
Switzerland
Email: amin.shokrollahi@epfl.ch
Mark Watson
Qualcomm, Inc.
3165 Kifer Road
Santa Clara, CA 95051
U.S.A.
Email: watson@qualcomm.com
Thomas Stockhammer
Nomor Research
Brecherspitzstrasse 8
Munich 81541
Germany
Email: stockhammer@nomor.de
Luby, et al. Expires May 14, 2010 [Page 52]