Low Density Parity Check (LDPC) Staircase and Triangle Forward Error Correction (FEC) Schemes
Extracted elements (28)
For small objects, reducing the encoding symbol length E artificially increases the number of symbols k, which improves LDPC code protection since LDPC codes perform better with larger block sizes. The E parameter is therefore optionally made a function of the object transfer length.
Sending repair symbols in sequential order is suboptimal for erasure recovery; it is recommended to shuffle (randomize) the transmission order of repair symbols. The random permutation tables (Section 5.6) implement this shuffling transparently at both sender and receiver.
The choice between the trivial iterative decoding algorithm and Gaussian elimination (or a hybrid) is left to the codec developer because interoperability does not depend on the decoding algorithm. Gaussian elimination recovers from more erasures but requires more CPU; the trivial algorithm is faster but less powerful.
The default N1m3 value of 0 (giving N1=3 ones per column) is recommended when the sender has no information about the receivers' decoding scheme. Higher N1m3 values (denser parity matrix) can improve performance when Gaussian elimination is known to be used at all receivers, but no specific value is mandated.
The B, E, G, max_n, and PRNG seed parameters are communicated via the FEC OTI, so alternative algorithms for determining B, E, G, and max_n may be used without compromising interoperability. However, both sender and receiver MUST use the same n-algorithm and the same PRNG.
For each source block, the actual number of encoding symbols n MUST be determined using the n-algorithm: n = floor(k * max_n / B), where k is the current source block length, max_n is the maximum number of encoding symbols for any block, and B is the maximum source block length.
LDPC-Staircase encoding MUST follow natural repair symbol order: the first repair symbol is generated first, and repair symbol with ESI i must be generated before ESI i+1, because each repair symbol equals the XOR sum of associated source symbols plus the previous repair symbol.
LDPC-Triangle encoding MUST follow natural repair symbol order: repair symbol with ESI i equals the XOR sum of all source and repair symbols with ESI lower than i in the associated equation.
PRNG scaling MUST use the formula: scaled_value = (unsigned long)((double)maxv * (double)raw_value / (double)0x7FFFFFFF). Modulo-based scaling must be avoided because least-significant bits of the PRNG output are less random.
The left side of the LDPC-Staircase parity check matrix MUST be generated using the specified left_matrix_init() function, which places N1 ones per column with a homogeneous distribution, adding extra bits to ensure no row has fewer than two ones.
The Park-Miller 'minimal standard' PRNG (A=16807, M=2^31-1) MUST be used for parity check matrix construction and symbol group randomization. A validation criterion: with seed=1, the 10,000th value returned MUST equal 1043618065.
The random permutation table initialization function (for G > 1) MUST be called immediately after creating the parity check matrix, before any further PRNG calls, both at sender and receiver. This ensures both sides use the same repair symbol ordering.
The right side of the LDPC-Staircase parity check matrix MUST be generated using the specified right_matrix_staircase_init() function, which creates a staircase structure: the first row has a single entry at column k, and each subsequent row i has entries at k+i (identity) and k+i-1 (staircase).
The right side of the LDPC-Triangle parity check matrix MUST be generated using the triangle initialization function: in addition to the staircase structure, each row i adds randomly chosen entries from columns k to k+i-2 (filling the triangle), using the PRNG.
The source object MUST be partitioned using the block partitioning algorithm specified in RFC 5052, using B, L, and E as inputs, producing N consecutively numbered source blocks.
There MUST be exactly one FEC Payload ID per packet. In the case of an Encoding Symbol Group where multiple encoding symbols are sent in the same packet, the FEC Payload ID refers to the first symbol; other symbols are derived using the dedicated function in Section 5.6.
When multiple encoding symbols are sent in the same packet (G > 1), all symbols in an Encoding Symbol Group MUST be either all source symbols or all repair symbols; mixed packets are not permitted. Symbols are stored consecutively in the packet without padding.
LDPC-Staircase is identified by FEC Encoding ID 3; LDPC-Triangle is identified by FEC Encoding ID 4. Both are Fully-Specified FEC schemes registered under the 'ietf:rmt:fec:encoding' namespace.
Scheme-specific FEC OTI elements are N1m3 (integer 0–7, default 0, representing N1-3 ones per column in the left parity check matrix), G (integer 1–31, default 1, encoding symbols per group/packet), and a 32-bit PRNG seed (value between 1 and 0x7FFFFFFE inclusive).
The FEC Object Transmission Information (OTI) common elements are Transfer-Length (L), Encoding-Symbol-Length (E), Maximum-Source-Block-Length (B), and Max-Number-of-Encoding-Symbols (max_n). The maximum transfer length is 2^12 * B * E bytes, with an upper bound of approximately 128 TB.
The FEC Payload ID for FEC Encoding IDs 3 and 4 is a 32-bit field composed of a 12-bit Source Block Number (allowing up to 2^12 blocks per object) and a 20-bit Encoding Symbol ID (allowing up to 2^20 encoding symbols per block). ESIs 0 to k-1 identify source symbols; k to n-k-1 identify repair symbols.
The maximum source block length B depends on the code rate CR and the 20-bit ESI field: max1_B = 2^(20 - ceil(log2(1/CR))). For CR in [1/2, 1), max1_B = 2^19 = 524,288 symbols. Codec-internal limitations (e.g., 16-bit ESI storage) may further constrain B to max2_B, giving B = min(max1_B, max2_B).
This document assigns FEC Encoding ID 3 ('LDPC Staircase Codes') and FEC Encoding ID 4 ('LDPC Triangle Codes') under the IANA 'ietf:rmt:fec:encoding' name-space for Fully-Specified FEC Encoding IDs.
Access to confidential objects should be protected via encryption at the object level or per-packet (e.g., IPsec/ESP). If confidentiality is a concern, it is RECOMMENDED that one of these solutions be used; these threats are not specific to or facilitated by FEC.
Attacks against FEC parameters (FEC OTI) can prevent decoding by, for example, causing a different block partitioning (e.g., modifying B). It is RECOMMENDED that FEC OTI integrity be protected: in-band EXT_FTI via digital signature, Group MAC, or TESLA; FDT Instances via XML digital signatures; out-of-band OTI via CMS signatures.
Content corruption attacks can be mitigated at the object level via digital signatures (e.g., RSASSA-PKCS1-v1_5) or at the packet level via per-packet digital signatures, Group MAC (HMAC-SHA-1 with shared key), or TESLA. It is RECOMMENDED that at least one of these techniques be used when object corruption is a concern.
The EXT_FTI encoding of the FEC OTI spans five 32-bit words (HET=64, HEL=5): Transfer-Length L (48-bit), Encoding Symbol Length E (16-bit), N1m3 (3-bit), G (5-bit), B split across two words (20-bit total: 8 MSB + 12 LSB), max_n (20-bit), and PRNG seed (32-bit).
The FEC Payload ID is encoded as a 32-bit word: bits 0-11 carry the Source Block Number (12 bits), and bits 12-31 carry the Encoding Symbol ID (20 bits). There MUST be exactly one FEC Payload ID per packet.