RaptorQ Forward Error Correction Scheme for Object Delivery
Extracted elements (31)
Each source block is subdivided into N sub-blocks so that each sub-block fits within the decoder's working memory WS. When N>1, a symbol spans one sub-symbol from each sub-block (non-contiguous in the object), allowing sub-block-at-a-time decoding on memory-constrained receivers.
RaptorQ is a fountain code, allowing the encoder to generate as many repair symbols as needed on the fly without prior coordination with receivers. The decoder can recover the source block from almost any set of received encoding symbols of cardinality only slightly exceeding K, eliminating the need to pre-specify redundancy levels.
Source blocks are padded to the next K' value in the systematic index table rather than supporting arbitrary K values. This simplifies encoder/decoder design by requiring only a finite set of pre-computed systematic indices J(K'), and enables faster encoding/decoding by keeping K' as a well-analyzed value.
The symbol alignment parameter Al (recommended value 4) ensures sub-symbols are always a multiple of Al octets, matching natural processor word widths (e.g., 4 octets on 32-bit processors) and enabling faster XOR-based encoding and decoding operations.
RaptorQ (FEC Encoding ID 6) is a next-generation successor to Raptor (RFC 5053, FEC Encoding ID 1). RaptorQ provides superior reliability, better coding efficiency, and supports larger source blocks (up to 56403 symbols vs. RFC 5053's limit), simplifying use in content delivery protocols compared to RFC 5053.
A compliant RaptorQ decoder MUST satisfy the requirements of Section 5.8; multiple decoding algorithms are permissible provided they meet those requirements. The example decoder in Section 5.4 is one such efficient implementation.
If Kt*T > F, the last symbol of the last source block MUST be padded at the end with Kt*T-F zero octets for encoding purposes.
It is RECOMMENDED that each packet contains exactly one symbol; however, receivers SHALL support reception of packets containing multiple symbols.
K' MUST be selected as the smallest value of K' from the systematic index table (Section 5.6) that is greater than or equal to K.
The FEC Payload ID MUST be a 4-octet field formatted with SBN in bits 0–7 and ESI in bits 8–31.
The parameters F, Al, T, Z, and N MUST be set so that ceil(ceil(F/T)/Z) <= K'_max (56403).
The source object MUST be partitioned into source blocks and sub-blocks using the Partition[] function as specified, with the first ZL source blocks of KL*T octets and the remaining ZS source blocks of KS*T octets.
The symbol size T MUST be a multiple of the symbol alignment parameter Al.
The value of the FEC Encoding ID MUST be 6, as assigned by IANA.
HDPC pre-coding relations define H HDPC symbols as MT * GAMMA * Transpose[C[0],...,C[K'+S-1]], where MT is an H×(K'+S) matrix of octets using Rand[] and GAMMA is a (K'+S)×(K'+S) lower-triangular matrix using octet exponentiation of alpha=2.
K'_max is the maximum number of source symbols that can be in a single source block, set to 56403. This constrains the maximum transfer length to 946270874880 octets given symbol size up to 2^16-1 and up to 256 source blocks.
L intermediate symbols are partitioned into W LT symbols (comprising S LDPC symbols and B others) and P PI symbols (comprising H HDPC symbols and U others), where L = K'+S+H = W+P. Values S, H, W are derived from K' via Table 2.
LDPC pre-coding relations require that S linear combinations of intermediate symbols evaluate to zero, enforced via matrices G_LDPC,1 (S×B) and G_LDPC,2 (S×P). Each non-LDPC LT symbol contributes to exactly 3 LDPC symbols.
The degree generator Deg[v] maps a 20-bit value v to a degree d using a fixed distribution table (Table 1) with 30 intervals. The distribution is heavily skewed toward degree 1 (~0.5% mass at d=1) and uses min(d, W-2) to cap the degree.
The encoding symbol generator Enc[K', C, (d,a,b,d1,a1,b1)] produces one encoding symbol as the XOR of d LT-selected intermediate symbols (walking C[b], C[(b+a)%W], ...) and d1 PI-selected intermediate symbols (walking C[W+b1] with stride a1 modulo P1, skipping indices >= P).
The Extended Source Block consists of K' symbols: the original K source symbols (ISI 0..K-1), K'-K zero-valued padding symbols (ISI K..K'-1), and repair symbols (ISI K' onward). Padding symbols are never transmitted; ESIs for repair symbols equal ISI minus (K'-K).
The intermediate symbols C[0..L-1] are uniquely determined by solving the L×L linear system A*C = D over GF(256), where A encodes both the pre-coding relationships and the source symbol encoding constraints, and D consists of S+H zero symbols followed by the K' source symbols.
The pseudo-random number generator Rand[y,i,m] = (V0[x0] XOR V1[x1] XOR V2[x2] XOR V3[x3]) mod m, where x0..x3 are the four bytes of y each XORed with i mod 256. It uses four fixed 256-entry tables V0–V3 of 32-bit unsigned integers specified in Section 5.5.
The systematic index J(K') and associated parameters S, H, W for each valid K' from 6 to 56403 are tabulated in Table 2 (Section 5.6). These values were chosen to ensure the encoding matrix A has full rank for all valid K', enabling unique recovery of intermediate symbols.
The tuple generator Tuple[K',X] derives (d,a,b,d1,a1,b1) from the systematic index J(K') and ISI X using: A=53591+J*997 (forced odd), B=10267*(J+1), y=(B+X*A) mod 2^32, then Rand[] and Deg[] calls. This deterministically maps each ISI to its encoding coefficients.
This document registers FEC Encoding ID 6 for the RaptorQ FEC scheme in the IANA registry for FEC Encoding IDs established by RFC 5052.
The RaptorQ FEC scheme does not include any inherent source authentication or integrity protection. A receiver that processes packets from an unauthenticated source is vulnerable to injection of malicious encoding symbols that can prevent recovery of the source block; higher-layer protocols or authentication mechanisms MUST be used to mitigate this threat.
The example decoder operates in five phases: (1) Gaussian elimination on V using a graph-based row selection strategy to build a lower-triangular X; (2) elimination of U_lower to identity I_u; (3) multiplication of X with upper rows to sparsify U_upper; (4) zeroing U_upper using I_u rows; (5) back-substitution to form the L×L identity. Failure occurs if V becomes all-zero before i+u=L, or U_lower has rank less than u.
The encoded Common FEC Object Transmission Information is an 8-octet field containing Transfer Length F (40-bit unsigned integer, max 946270874880) and Symbol Size T (16-bit unsigned integer), with 8 reserved bits between them.
The FEC Payload ID is a 4-octet field composed of an 8-bit Source Block Number (SBN) and a 24-bit Encoding Symbol ID (ESI), in network byte order.
The Scheme-Specific FEC OTI is a 4-octet field containing number of source blocks Z (8-bit), number of sub-blocks N (16-bit), and symbol alignment parameter Al (8-bit). The full encoded FEC OTI is the 12-octet concatenation of Common and Scheme-Specific OTI.