Reed-Solomon Forward Error Correction (FEC) Schemes
Extracted elements (25)
A non-systematic Vandermonde matrix is converted to systematic form by multiplying V_{k,k}^^-1 * V_{k,n}. The systematic property is required because many networking applications need the source symbols to be directly accessible from encoded output without decoding.
Encoding and decoding over packets with G>=1 symbols per packet means that symbol erasures produce the same erasure pattern for each of the S m-bit element positions. As a result, the matrix inversion needs to be performed only once and applied to all S encoding vectors, making the inversion cost negligible for large S.
FEC Encoding ID 5 is defined as a special case of ID 2 (fixing m=8 and G=1) to provide a simpler fixed-format scheme with a compact 8-byte EXT_FTI header versus the 12-byte header required by the general ID 2 scheme. This enables implementations that only need GF(2^^8) without encoding symbol groups to avoid carrying unnecessary parameters.
Repair symbols can be produced on demand: a sender can initially produce a limited number of repair symbols and later produce additional ones (up to n-k) based on observed channel erasures, since producing repair symbol e_j only requires multiplying the S source vectors by column j of GM.
The Reed-Solomon schemes described in this document are designed to be compatible with the implementation from Luigi Rizzo (RS-codec). The generator matrix construction using a Vandermonde matrix in systematic form matches the Rizzo codec, enabling interoperability with widely deployed existing implementations.
In a packet erasure channel implementation, the location of erased symbols in the sequence MUST be known. Source symbols containing fewer than S m-bit elements (e.g., the last symbol of the last block) MUST be virtually padded with zero elements, though this padding need not be transmitted.
It is RECOMMENDED that the 'n-algorithm' be used by a sender to determine max_n and n, though other algorithms remain possible. A receiver MAY use the receiver part of the n-algorithm to estimate n, but MUST be prepared to handle symbols with an ESI >= the computed n value.
The block partitioning algorithm defined in Section 9.1 of RFC 5052 MUST be used with FEC Encoding IDs 2 and 5.
The Common Elements (Transfer-Length L, Encoding-Symbol-Length E, Maximum-Source-Block-Length B, Max-Number-of-Encoding-Symbols max_n) MUST be defined with FEC Encoding ID 2.
The Scheme-Specific elements G (encoding symbols per group) and m (finite field element length in bits) MUST be defined for FEC Encoding ID 2. When G is not communicated to the decoder, it MUST assume G=1; when m is not communicated, the decoder MUST assume m=8.
There MUST be exactly one FEC Payload ID per source or repair packet. In an Encoding Symbol Group (multiple symbols per packet), the FEC Payload ID refers to the first symbol; subsequent ESIs are derived by incrementing sequentially.
FEC Encoding ID 2 specifies a Fully-Specified FEC Scheme for Reed-Solomon codes over GF(2^^m), where m is in {2..16}. The FEC Payload ID consists of a Source Block Number field of (32-m) bits and an Encoding Symbol ID field of m bits, totaling 32 bits.
FEC Encoding ID 5 is a Fully-Specified FEC Scheme for the special case of Reed-Solomon codes over GF(2^^8) with no encoding symbol group (G=1). Its FEC Payload ID is a fixed 32-bit field: 24-bit Source Block Number and 8-bit Encoding Symbol ID.
The finite field GF(2^^m) for m in {2..16} is represented using specific primitive irreducible polynomials, one per value of m (e.g., m=8 uses 1+x^^2+x^^3+x^^4+x^^8). These polynomials are chosen to be primitive with the minimum number of monomials to facilitate implementation.
The generator matrix GM is constructed as (V_{k,k}^^-1) * V_{k,n}, where V_{k,n} is a Vandermonde matrix with entry {i,j} = alpha^^(i*j). This construction yields a systematic MDS code where the first k encoding symbols equal the k source symbols.
The maximum source block length B is determined by the finite field size: max1_B = floor((2^^m - 1) * CR), where CR is the code rate. A codec MAY impose additional max2_B limits, and B = min(max1_B, max2_B). This is only computed at the sender; B is communicated to receivers via FEC OTI.
The 'n-algorithm' determines max_n and n: at the sender, max_n = ceil(B / CR); if max_n > 2^^m - 1, return error; n = floor(k * max_n / B). At the receiver, n = floor(k * max_n / B) using B and max_n from the FEC OTI.
Under FEC Encoding ID 129 (Under-Specified Small Block Systematic FEC Scheme), this document assigns FEC Instance ID 0 to Reed-Solomon codes over GF(2^^8) with no encoding symbol group. The FEC Instance ID 0 MAY use the RFC 5052 block partitioning algorithm or another algorithm.
This document assigns FEC Encoding ID 2 under the 'ietf:rmt:fec:encoding' namespace to 'Reed-Solomon Codes over GF(2^^m)', FEC Encoding ID 5 to 'Reed-Solomon Codes over GF(2^^8)', and FEC Instance ID 0 (scoped by FEC Encoding ID 129) to 'Reed-Solomon Codes over GF(2^^8)'.
Attacks on FEC OTI parameters (sent in-band via EXT_FTI/FDT or out-of-band) can prevent decoding or increase processing load. It is RECOMMENDED that FEC OTI integrity be protected: in-band parameters SHOULD be protected by digital signature, group MAC, or TESLA; FDT Instance SHOULD be digitally signed; out-of-band FEC OTI SHOULD be digitally signed.
If confidentiality is a concern, it is RECOMMENDED that encryption be applied either over the whole object before FEC encoding or on a per-packet basis (e.g., using IPsec ESP). FEC itself neither introduces nor mitigates access control vulnerabilities.
Protection against content corruption can be achieved via: (a) object-level digital signatures (e.g., RSASSA-PKCS1-v1_5), (b) per-packet digital signatures, (c) Group MAC (e.g., HMAC-SHA-256 with shared key), or (d) TESLA. It is RECOMMENDED that at least one of these techniques be used when object corruption is a concern.
For FEC Encoding ID 2 with m=8 (default), the FEC Payload ID is 32 bits: a 24-bit Source Block Number followed by an 8-bit Encoding Symbol ID. For m=16, it is a 16-bit Source Block Number followed by a 16-bit Encoding Symbol ID.
The FEC OTI EXT_FTI encoding format for FEC Encoding ID 2 is 12 bytes: HET=64 (8 bits), HEL=4 (8 bits), Transfer Length L (48 bits), m (8 bits), G (8 bits), Encoding Symbol Length E (16 bits), Max Source Block Length B (16 bits), Max Nb Encoding Symbols max_n (16 bits).
The FEC OTI EXT_FTI format for FEC Encoding ID 5 is 8 bytes: HET=64 (8 bits), HEL=3 (8 bits), Transfer Length L (48 bits), Encoding Symbol Length E (16 bits), Max Source Block Length B (8 bits), max_n (8 bits). No Scheme-Specific elements are defined.