Raptor Forward Error Correction Scheme for Object Delivery
Extracted elements (27)
Raptor is a systematic code: source symbols (ESI 0 to K-1) are transmitted unmodified alongside repair symbols, so receivers that receive all K source symbols need no decoding computation. This minimises complexity in the common low-loss case.
The sub-block partitioning scheme (N sub-blocks per source block) allows decoding to proceed in working memory bounded by sub-block size W. The recommended parameter derivation ensures sub-symbol sizes are multiples of Al to facilitate multi-byte XOR operations.
The symbol alignment parameter Al (recommended value 4) ensures sub-symbols are always a multiple of Al bytes, enabling XOR encoding and decoding operations to be performed 4 or more bytes at a time on typical processors, significantly improving throughput.
The Transfer Length field is encoded as 48 bits for simplicity, even though the effective limit is 2^^45 bytes—a consequence of symbol size < 2^^16, maximum K <= 8192 (2^^13), and maximum source blocks <= 2^^16. The encoding leaves headroom for alignment without a narrower field.
The Raptor code defined in this document is identical to that in the 3GPP MBMS specification [MBMS], enabling interoperability between IETF object delivery applications and 3GPP Multimedia Broadcast/Multicast Service implementations.
Certain pre-coding relationships MUST hold within the L intermediate symbols: S LDPC symbols are defined as XOR combinations of the first K intermediate symbols, and H Half symbols are defined using the Gray-code-based half-symbol construction.
If Kt*T > F (total symbol bytes exceed object size), the last source symbol MUST be padded at the end with Kt*T - F zero bytes for encoding purposes; these padding bytes need not be transmitted.
Only whole symbols MUST be included in encoding packets, except that zero-padding bytes appended to the last source symbol for FEC encoding need not be sent.
The 512 random numbers in tables V0 and V1 (each containing 256 four-byte unsigned integers) MUST be available to both sender and receiver, as they underpin the pseudo-random number generator used throughout encoding and decoding.
The FEC Encoding ID MUST be 1 (one), as assigned by IANA, identifying this Fully-Specified FEC Scheme as the Raptor code.
The source object MUST be partitioned into source blocks and sub-blocks using the Partition[] function, which splits I items into J approximately equal groups (JL groups of size IL = ceil(I/J), JS groups of size IS = floor(I/J)).
The symbol size T MUST be a multiple of the symbol alignment parameter Al. The CDP MUST communicate SBN, ESI, and encoding symbols to the receiver for each transmitted packet.
The transport parameters MUST be set such that ceil(ceil(F/T)/Z) <= Kmax (8192), ensuring that no source block contains more than Kmax source symbols.
ESI values 0 to K-1 identify source symbols in sequential order; ESI values K and above identify repair symbols. A packet must consist entirely of source symbols or entirely of repair symbols; G consecutive symbols starting from ESI X are carried in one packet.
Kmax is fixed at 8192 source symbols per source block. The number of pre-coding symbols is L = K+S+H, where S is the smallest prime >= ceil(0.01*K)+X (X the smallest integer with X*(X-1)>=2*K), and H is the smallest integer with choose(H, ceil(H/2)) >= K+S.
Systematic indices J(K) are precomputed for K=4 to 8192 (tabulated in Section 5.7) such that the L×L matrix A constructed from source symbol triples has full rank and is invertible, guaranteeing unique intermediate symbol recovery.
The degree generator Deg[v] maps a value v in [0, 2^^20) to a degree in {1, 2, 3, 4, 10, 11, 40} using a fixed cumulative distribution table, yielding a specific soliton-like distribution for encoding symbol connectivity.
The LT encoding symbol generator LTEnc[K, C, (d, a, b)] produces a single encoding symbol as the XOR of min(d, L) intermediate symbols selected by stepping b by a modulo the smallest prime L' >= L, skipping indices >= L.
The pseudo-random number generator Rand[X, i, m] = (V0[(X+i) % 256] XOR V1[(floor(X/256)+i) % 256]) % m, using the two fixed 256-entry tables V0 and V1 from Section 5.6.
The systematic Raptor encoder operates in two steps: first, generate L = K+S+H intermediate symbols from K source symbols by solving a linear system (inverse encoding); second, generate each repair symbol as the XOR of selected intermediate symbols via the LTEnc generator.
The triple generator Trip[K, X] derives (d, a, b) from the systematic index J(K) and ESI X via: A=(53591+J(K)*997)%Q, B=10267*(J(K)+1)%Q, Y=(B+X*A)%Q, then d=Deg[Rand[Y,0,2^^20]], a=1+Rand[Y,1,L'-1], b=Rand[Y,2,L'], where Q=65521.
IANA assigned FEC Encoding ID 1 to the Raptor FEC Scheme defined in this document, under the FEC Encoding ID registry established by RFC 5052.
No significant security considerations specific to this FEC scheme are identified. The security considerations of RFC 5052 (the FEC building block framework) apply to this specification.
The example decoder performs four phases: (1) systematic Gaussian elimination on submatrix V using row-selection based on minimum degree and graph-component size; (2) Gaussian elimination on U_lower to obtain I_u; (3) precomputation of U' (all 2^8-1 non-zero row combinations per group of 8 I_u rows); (4) zeroing U_upper using U'. Failure occurs if V empties before i+u=L or U_lower has rank < u.
The Common FEC OTI encodes Transfer Length F as a 48-bit field (upper 32 bits + lower 16 bits, with 16 reserved bits), followed by Encoding Symbol Length T as a 16-bit field, totalling 10 octets. F must be less than 2^^45; T must be less than 2^^16.
The FEC Payload ID is a 4-octet field with two 16-bit subfields: Source Block Number (SBN) and Encoding Symbol ID (ESI), in that order.
The Scheme-Specific FEC OTI is a 4-octet field: Z (number of source blocks, 16 bits), N (number of sub-blocks, 8 bits), Al (symbol alignment parameter, 8 bits). Combined with the Common OTI, the total encoded FEC OTI is 14 octets.