RFC 5510

Reed-Solomon Forward Error Correction (FEC) Schemes

📅 published April 2009, from ietf

RFC 5510: Reed-Solomon Forward Error Correction (FEC) Schemes 🦋

okay bestie, this one is from the Network Working Group and it's a Standards Track doc, so it's a real spec people build against 💅. It came out in April 2009, written by J. Lacan (ISAE/LAAS-CNRS), V. Roca (INRIA), and J. Peltotalo and S. Peltotalo (Tampere University of Technology). The header doesn't list anything it obsoletes or updates, so no drama there ✨

Status of This Memo 🌸

this is an Internet standards track protocol for the Internet community, and it's asking for discussion and suggestions for improvements 🫶 for where it stands, check the current edition of the "Internet Official Protocol Standards" (STD 1). distribution of this memo is unlimited, so share away 💖

Copyright Notice 🎀

this doc is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents, as they were on the publication date. the link is http://trustee.ietf.org/license-info. read those carefully, because they spell out your rights and restrictions 📜

heads up for the copyright drama 😭 this doc may contain material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. the people who control the copyright in some of that older material may not have given the IETF Trust permission to allow modifications outside the IETF Standards Process. so unless you get an adequate license from those copyright holders, this document may not be modified outside the IETF Standards Process, and derivative works of it may not be created outside the IETF Standards Process. the one exceptions are formatting it for publication as an RFC or translating it into languages other than English 🌈

Abstract ✨

this doc describes a Fully-Specified Forward Error Correction (FEC) Scheme for the Reed-Solomon FEC codes over GF(2^^m), where m is in {2..16}. it also covers how that gets applied to the reliable delivery of data objects on the packet erasure channel. that's a communication path where packets are either received without any corruption or discarded during transmission 🦋

it also describes a Fully-Specified FEC Scheme for the special case of Reed-Solomon codes over GF(2^^8) when there is no encoding symbol group. and finally, in the context of the Under-Specified Small Block Systematic FEC Scheme (FEC Encoding ID 129), this doc assigns an FEC Instance ID to the special case of Reed-Solomon codes over GF(2^^8) 💅

Reed-Solomon codes belong to the class of Maximum Distance Separable (MDS) codes. that means a receiver can recover the k source symbols from any set of k received symbols 🔥 the schemes in here are compatible with the implementation from Luigi Rizzo 💜

Table of Contents 🧚

   1. Introduction ....................................................4
   2. Terminology .....................................................5
   3. Definitions Notations and Abbreviations .........................5
      3.1. Definitions ................................................5
      3.2. Notations ..................................................6
      3.3. Abbreviations ..............................................7
   4. Formats and Codes with FEC Encoding ID 2 ........................7
      4.1. FEC Payload ID .............................................7
      4.2. FEC Object Transmission Information ........................8
           4.2.1. Mandatory Elements ..................................8
           4.2.2. Common Elements .....................................8
           4.2.3. Scheme-Specific Elements ............................9
           4.2.4. Encoding Format .....................................9
   5. Formats and Codes with FEC Encoding ID 5 .......................11
      5.1. FEC Payload ID ............................................11
      5.2. FEC Object Transmission Information .......................12
           5.2.1. Mandatory Elements .................................12
           5.2.2. Common Elements ....................................12
           5.2.3. Scheme-Specific Elements ...........................12
           5.2.4. Encoding Format ....................................12
   6. Procedures with FEC Encoding IDs 2 and 5 .......................13
      6.1. Determining the Maximum Source Block Length (B) ...........13
      6.2. Determining the Number of Encoding Symbols of a Block .....14
   7. Small Block Systematic FEC Scheme (FEC Encoding ID 129)
      and Reed-Solomon Codes over GF(2^^8) ...........................15
   8. Reed-Solomon Codes Specification for the Erasure Channel .......16
      8.1. Finite Field ..............................................16
      8.2. Reed-Solomon Encoding Algorithm ...........................17
           8.2.1. Encoding Principles ................................17
           8.2.2. Encoding Complexity ................................18
      8.3. Reed-Solomon Decoding Algorithm ...........................18
           8.3.1. Decoding Principles ................................18
           8.3.2. Decoding Complexity ................................19
      8.4. Implementation for the Packet Erasure Channel .............19
   9. Security Considerations ........................................22
      9.1. Problem Statement .........................................22
      9.2. Attacks against the Data Flow .............................23
           9.2.1. Access to Confidential Objects .....................23
           9.2.2. Content Corruption .................................23
      9.3. Attacks against the FEC Parameters ........................24
   10. IANA Considerations ...........................................25
   11. Acknowledgments ...............................................25
   12. References ....................................................26
      12.1. Normative References .....................................26
      12.2. Informative References ...................................26

1. Introduction 🌷

FEC codes are a classic way to make multicast and broadcast transmissions more reliable 💖 the [RFC5052] document lays out a general framework for using FEC in Content Delivery Protocols (CDPs). its companion, [RFC3453], covers some applications of FEC codes for content delivery 🎀

newer FEC schemes like [RFC5053] and [RFC5170] came up with erasure codes built on sparse graphs and matrices. these are efficient to process, but they aren't optimal at correction when you're dealing with "small" objects 🥺

the FEC schemes in this document belong to the class of Maximum Distance Separable codes, which are optimal for erasure correction capability. in other words, a receiver can recover the k source symbols from any set of exactly k encoding symbols 🔥 they're also systematic codes, which means the k source symbols are part of the encoding symbols. yes the encoding and decoding complexity is higher than [RFC5053] or [RFC5170], but this family of codes is still super useful 💅

lots of applications for content transmission or content storage already rely on packet-based Reed-Solomon codes. a bunch of them use the Reed-Solomon codec of Luigi Rizzo [RS-codec] [Rizzo97]. so the goal of this doc is to specify an implementation of Reed-Solomon codes that's compatible with that codec 🧚

the present document:

introduces the Fully-Specified FEC Scheme with FEC Encoding ID 2, which specifies the use of Reed-Solomon codes over GF(2^^m), where m is in {2..16},
introduces the Fully-Specified FEC Scheme with FEC Encoding ID 5, which focuses on the special case of Reed-Solomon codes over GF(2^^8) and no encoding symbol group (i.e., exactly one symbol per packet), and
in the context of the Under-Specified Small Block Systematic FEC Scheme (FEC Encoding ID 129) [RFC5445], assigns the FEC Instance ID 0 to the special case of Reed-Solomon codes over GF(2^^8) and no encoding symbol group.

for a definition of the terms Fully-Specified and Under-Specified FEC Schemes, see [RFC5052], Section 4 📖

2. Terminology 💜

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 RFC 2119 [RFC2119] ✨

3. Definitions Notations and Abbreviations 🦋

3.1. Definitions 🌸

this doc uses the same terms and definitions as [RFC5052]. it also uses these definitions:

Source symbol: a unit of data used during the encoding process.
Encoding symbol: a unit of data generated by the encoding process.
Repair symbol: an encoding symbol that is not a source symbol.
Code rate: the k/n ratio, i.e., the ratio between the number of source symbols and the number of encoding symbols. by definition, the code rate is such that 0 < code rate <= 1. a code rate close to 1 means only a small number of repair symbols were produced during encoding 🍓
Systematic code: an FEC code where the source symbols are part of the encoding symbols.
Source block: a block of k source symbols that get considered together for encoding.
Encoding Symbol Group: a group of encoding symbols that are sent together within the same packet, where their relationship to the source block can be derived from a single Encoding Symbol ID.
Source Packet: a data packet containing only source symbols.
Repair Packet: a data packet containing only repair symbols.
Packet Erasure Channel: a communication path where packets are either dropped (e.g., by a congested router, or because the number of transmission errors exceeds the correction capabilities of the physical layer codes) or received. when a packet is received, it's assumed not to be corrupted 💀

3.2. Notations ✨

okay so here's the notation cheat sheet, bestie 📝🎀 this doc uses these, and you'll want them locked in before we get to the good stuff:

L: the object transfer length in bytes 📦
k: the number of source symbols in a source block 🧩
n_r: the number of repair symbols generated for a source block 🛠️
n: the encoding block length, i.e., the number of encoding symbols generated for a source block. So basically n = k + n_r 🔢
max_n: the maximum number of encoding symbols generated for any source block 📈
B: the maximum source block length in symbols, i.e., the maximum number of source symbols per source block 🍓
N: the number of source blocks the object shall be partitioned into 🧁
E: the encoding symbol length in bytes 💜
S: the symbol size in units of m-bit elements. When m = 8, then S and E are equal 🌸
m: the length of the elements in the finite field, in bits. In this document, m belongs to {2..16} 🦋
q: the number of elements in the finite field. We have q = 2^^m in this specification 👑
G: the number of encoding symbols per group, i.e., the number of symbols sent in the same packet 📬
GM: the Generator Matrix of a Reed-Solomon code 🧠
CR: the "code rate", i.e., the k/n ratio 🌈
a^^b: a raised to the power b ⭐
a^^-1: the inverse of a 🔁
I_k: the k*k identity matrix 🪞

3.3. Abbreviations 💅

these are the abbreviations the doc uses, so no surprises later 🫶

ESI: Encoding Symbol ID. 🆔
FEC OTI: FEC Object Transmission Information. 📋
RS: Reed-Solomon. 🧑‍🔬
MDS: Maximum Distance Separable code. 🏆
GF(q): a finite field (also known as Galois Field) with q elements. We assume that q = 2^^m in this document. 🌟

4. Formats and Codes with FEC Encoding ID 2 🎀

okay this section is the intro to the whole FEC Encoding ID 2 crew. it's the fully-specified FEC scheme, and it uses Reed-Solomon codes over GF(2^^m). iconic 👑

4.1. FEC Payload ID 🪪

the FEC Payload ID is made of two things: the Source Block Number and the Encoding Symbol ID. how long each one is depends on m, which gets sent in the FEC OTI. here's the tea:

The Source Block Number (field of size 32-m bits) tells you which source block of the object the encoding symbol(s) in the payload came from. There's a max of 2^^(32-m) blocks per object 🧱
The Encoding Symbol ID (field of size m bits) tells you which specific encoding symbol(s) generated from the source block are riding along in the packet payload. There's a max of 2^^m encoding symbols per block. The first k values (0 to k - 1) are for source symbols, and the remaining n-k values are for repair symbols 🛟

There MUST be exactly one FEC Payload ID per source or repair packet. 🚨 In case of an Encoding Symbol Group, when multiple encoding symbols get sent in the same packet, the FEC Payload ID refers to the first symbol of the packet. The other symbols can be deduced from the ESI of the first symbol by incrementing sequentially the ESI. so smart, right? 🧠✨

 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     Source Block Number (32-8=24 bits)        | Enc. Symb. ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    Figure 1: FEC Payload ID Encoding Format for m = 8 (Default)

 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Src Block Nb (32-16=16 bits)  |  Enc. Symbol ID (m=16 bits)   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

         Figure 2: FEC Payload ID Encoding Format for m = 16

the formats for m = 8 and m = 16 are shown in Figure 1 and Figure 2. you're welcome 💖

4.2. FEC Object Transmission Information 📋

4.2.1. Mandatory Elements 🧾

FEC Encoding ID: the Fully-Specified FEC Scheme described in this section uses FEC Encoding ID 2. 🔖

4.2.2. Common Elements 🌷

The following elements MUST be defined with the present FEC scheme. 🚨

Transfer-Length (L): a non-negative integer indicating the length of the object in bytes. There are some restrictions on the maximum Transfer-Length that can be supported:

max_transfer_length = 2^^(32-m) * B * E

okay so for m = 8, for B = 2^^8 - 1 (because the codec operates on a finite field with 2^^8 elements), and if E = 1024 bytes, then the maximum transfer length is approximately equal to 2^^42 bytes (i.e., 4 terabytes). 🤯 Similarly, for m = 16, for B = 2^^16 - 1, and if E = 1024 bytes, then the maximum transfer length is also approximately equal to 2^^42 bytes. For larger objects, another FEC scheme, with a larger Source Block Number field in the FEC Payload ID, could be defined. Another solution consists in fragmenting large objects into smaller objects, each of them complying with the above limits. 🧩

Encoding-Symbol-Length (E): a non-negative integer indicating the length of each encoding symbol in bytes. 📏
Maximum-Source-Block-Length (B): a non-negative integer indicating the maximum number of source symbols in a source block. 🍓
Max-Number-of-Encoding-Symbols (max_n): a non-negative integer indicating the maximum number of encoding symbols generated for any source block. 📈

Section 6 explains how to derive the values of each of these elements. 🗺️

4.2.3. Scheme-Specific Elements 🎛️

The following element MUST be defined with the present FEC scheme. It contains two distinct pieces of information: 💅

G: a non-negative integer indicating the number of encoding symbols per group used for the object. The default value is 1, meaning that each packet contains exactly one symbol. When no G parameter is communicated to the decoder, then the latter MUST assume that G = 1. 🎯
m: The m parameter is the length of the finite field elements, in bits. It also characterizes the number of elements in the finite field: q = 2^^m elements. The default value is m = 8. When no finite field size parameter is communicated to the decoder, then the latter MUST assume that m = 8. 🌸

4.2.4. Encoding Format 🖍️

this part shows the two possible encoding formats for the above FEC OTI. the doc doesn't say when you should use one or the other, so that's your call 🤷‍♀️

4.2.4.1. Using the General EXT_FTI Format 🪄

here's the FEC OTI binary format when the EXT_FTI mechanism is used (e.g., within the ALC [ALC] or NORM [NORM] protocols).

 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   HET = 64    |    HEL = 4    |                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               +
|                      Transfer Length (L)                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|       m       |       G       |   Encoding Symbol Length (E)  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Max Source Block Length (B)  |  Max Nb Enc. Symbols (max_n)  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                    Figure 3: EXT_FTI Header Format

4.2.4.2. Using the FDT Instance (FLUTE specific) 📻

when you want the FEC OTI to ride along in the FDT (File Delivery Table) Instance of a FLUTE session [FLUTE], these XML attributes must be described for the associated object: 🎀

FEC-OTI-FEC-Encoding-ID
FEC-OTI-Transfer-Length (L)
FEC-OTI-Encoding-Symbol-Length (E)
FEC-OTI-Maximum-Source-Block-Length (B)
FEC-OTI-Max-Number-of-Encoding-Symbols (max_n)
FEC-OTI-Scheme-Specific-Info

the FEC-OTI-Scheme-Specific-Info holds the string you get from Base64 encoding (in the XML Schema xs:base64Binary sense) of this value: 🧃

 0                   1
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|       m       |       G       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

 Figure 4: FEC OTI Scheme Specific Information To Be Included in the
                            FDT Instance

when no m parameter is going to be carried in the FEC OTI, the m field gets set to 0 (which is not a valid seed value). otherwise, the m field has a valid value, as explained in Section 4.2.3. same deal for G: when no G parameter is carried, the G field is set to 0 (which is not a valid seed value). otherwise it has a valid value, as explained in Section 4.2.3. and when neither m nor G is carried in the FEC OTI, the sender just leaves out the FEC-OTI-Scheme-Specific-Info attribute entirely 🙌

during Base64 encoding, the 2 bytes of the FEC OTI Scheme-Specific Information turn into a string of 4 printable characters (in the 64-character alphabet), and that string gets added to the FEC-OTI-Scheme-Specific-Info attribute. 🔤✨

5. Formats and Codes with FEC Encoding ID 5 🌈

okay, round two! this section covers the fully-specified FEC scheme with FEC Encoding ID 5. it focuses on the special case of Reed-Solomon codes over GF(2^^8) with no encoding symbol group. so simple, so cute 🦋

5.1. FEC Payload ID 🪪

the FEC Payload ID is made of the Source Block Number and the Encoding Symbol ID: 💖

The Source Block Number (24-bit field) tells you which source block of the object the encoding symbol in the payload came from. There's a max of 2^^24 blocks per object. 🧱
The Encoding Symbol ID (8-bit field) tells you which specific encoding symbol generated from the source block is carried in the packet payload. There's a max of 2^^8 encoding symbols per block. The first k values (0 to k - 1) identify source symbols; the remaining n-k values identify repair symbols. 🛟

There MUST be exactly one FEC Payload ID per source or repair packet. 🚨 This FEC Payload ID refers to the one and only symbol of the packet. 🫶

 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|        Source Block Number (24 bits)          | Enc. Symb. ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Figure 5: FEC Payload ID Encoding Format with FEC Encoding ID 5

5.2. FEC Object Transmission Information 📋

5.2.1. Mandatory Elements 🧾

FEC Encoding ID: the Fully-Specified FEC Scheme described in this section uses FEC Encoding ID 5. 🔖

5.2.2. Common Elements 🌷

the Common elements are the same as the ones in Section 4.2.2 when m = 8 and G = 1. easy peasy 🍋

5.2.3. Scheme-Specific Elements 🎛️

no Scheme-Specific elements are defined by this FEC scheme. nothing extra to juggle here 💜

5.2.4. Encoding Format 🖍️

this part shows the two possible encoding formats for the above FEC OTI. the doc doesn't say when one format or the other should be used, so again, you pick 💅

5.2.4.1. Using the General EXT_FTI Format 💖

Okay so here's the FEC OTI binary format for when you're using the EXT_FTI mechanism (like inside the ALC [ALC] or NORM [NORM] protocols) 🎀

    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   HET = 64    |    HEL = 3    |                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               +
   |                      Transfer Length (L)                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   Encoding Symbol Length (E)  | MaxBlkLen (B) |     max_n     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 6: EXT_FTI Header Format with FEC Encoding ID 5

5.2.4.2. Using the FDT Instance (FLUTE specific) 🧚

Ok so when you want the FEC OTI to ride along in the FDT Instance of a FLUTE session [FLUTE], the following XML attributes must be described for the associated object:

FEC-OTI-FEC-Encoding-ID
FEC-OTI-Transfer-Length (L)
FEC-OTI-Encoding-Symbol-Length (E)
FEC-OTI-Maximum-Source-Block-Length (B)
FEC-OTI-Max-Number-of-Encoding-Symbols (max_n)

6. Procedures with FEC Encoding IDs 2 and 5 ✨

This section is the home of the procedures that FEC Encoding IDs 2 and 5 both share 👯‍♀️ In the case of FEC Encoding ID 5, m = 8 and G = 1. The block partitioning algorithm defined in Section 9.1 of [RFC5052] MUST be used with FEC Encoding IDs 2 and 5. No skipping that one, bestie 💅

6.1. Determining the Maximum Source Block Length (B) 🌸

The finite field size parameter, m, defines the number of non-zero elements in this field, which works out to q - 1 = 2^^m - 1. Fun fact (well, it's fun to me 🤓): q - 1 is also the theoretical maximum number of encoding symbols that can be produced for a source block. For instance, when m = 8 (default) there is a maximum of 2^^8 - 1 = 255 encoding symbols.

So, given the target FEC code rate (for example, the user supplies it when they start a FLUTE sending application), the sender calculates:

   max1_B = floor((2^^m - 1) * CR)

This max1_B value leaves enough room for the sender to make the number of parity symbols it wants 🙌

Additionally, a codec MAY impose other limitations on the maximum block size. Yet it is not expected that such limits exist when you're using the default m = 8 value. This decision MUST be clarified at implementation time, when the target use case is known. This gives you a max2_B limitation.

Then, B is given by:

   B = min(max1_B, max2_B)

Note that this calculation is only required at the coder, since the B parameter is communicated to the decoder through the FEC OTI. The decoder just reads it, no math needed 😌

6.2. Determining the Number of Encoding Symbols of a Block 🦋

Okay this is the n-algorithm (yes, that's its actual name 💀). It explains how to figure out the maximum number of encoding symbols generated for any source block (max_n), and the number of encoding symbols for a given block (n), as a function of the target code rate.

AT A SENDER:

Input:

B: Maximum source block length, for any source block. Section 6.1 explains how to determine its value.
k: Current source block length. This parameter is given by the block partitioning algorithm.
CR: FEC code rate, which is given by the user (e.g., when starting a FLUTE sending application). It is expressed as a floating point value.

Output:

max_n: Maximum number of encoding symbols generated for any source block.
n: Number of encoding symbols generated for this source block.

Algorithm:

   max_n = ceil(B / CR);

   if (max_n > 2^^m - 1), then return an error ("invalid code rate");

   n = floor(k * max_n / B);

AT A RECEIVER:

Input:

B: Extracted from the received FEC OTI.
max_n: Extracted from the received FEC OTI.
k: Given by the block partitioning algorithm.

Output:

Algorithm:

   n = floor(k * max_n / B);

It is RECOMMENDED that the "n-algorithm" be used by a sender, but other algorithms remain possible to determine max_n and/or n. You've got options, babe 🌈

At a receiver, the max_n value is extracted from the received FEC OTI. Since the Reed-Solomon decoder does not need to know the actual n value, using the receiver part of the "n-algorithm" is not necessary from a decoding point of view.

However, a receiver may want an estimate of n for other reasons (e.g., for memory management purposes). In that case, a receiver knows that the number of encoding symbols of a block cannot exceed max_n. Additionally, if a receiver believes that a sender uses the "n-algorithm", this receiver MAY use the receiver part of the "n-algorithm" to get a better estimate of n. When this is the case, a receiver MUST be prepared to handle symbols with an Encoding Symbol ID superior or equal to the computed n value (e.g., it can choose to simply drop them). Be ready for the surprise symbols, girl 😭🫶

7. Small Block Systematic FEC Scheme (FEC Encoding ID 129) and Reed-Solomon Codes over GF(2^^8) 🔥

In the context of the Under-Specified Small Block Systematic FEC Scheme (FEC Encoding ID 129) [RFC5445], this document assigns the FEC Instance ID 0 to the special case of Reed-Solomon codes over GF(2^^8) and no encoding symbol group. Think of it as a special-edition look 👑

The FEC Instance ID 0 uses the Formats and Codes specified in [RFC5445].

The FEC scheme with FEC Instance ID 0 MAY use the block partitioning algorithm defined in Section 9.1 of [RFC5052] to partition the object into source blocks. This FEC scheme MAY also use another algorithm. For instance, the CDP sender may change the length of each source block dynamically, depending on some external criteria (e.g., to adjust the FEC coding rate to the current loss rate experienced by NORM receivers) and inform the CDP receivers of the current block length by means of the EXT_FTI mechanism. This choice is out of the scope of the current document. Not this doc getting into it, periodt 🙅‍♀️

8. Reed-Solomon Codes Specification for the Erasure Channel 🧁

Reed-Solomon (RS) codes are linear block codes. They also belong to the class of MDS codes. A [n,k]-RS code encodes a sequence of k source elements defined over a finite field GF(q) into a sequence of n encoding elements, where n is upper bounded by q - 1. The implementation described in this document is based on a generator matrix built from a Vandermonde matrix put into systematic form.

Sections 8.1 to 8.3 specify the [n,k]-RS codes when applied to m-bit elements, and Section 8.4 specifies the use of [n,k]-RS codes when applied to symbols composed of several m-bit elements. The use described in Section 8.4 is the crux of this specification, so pay extra attention there 👀

A reader who wants to understand the underlying theory is invited to refer to references [Rizzo97] and [MWS77]. Go get your nerd on 🤓

8.1. Finite Field 🌷

A finite field GF(q) is defined as a finite set of q elements that has a structure of field. It necessarily contains q = p^^m elements, where p is a prime number. With packet erasure channels, p is always set to 2. The elements of the field GF(2^^m) can be represented by polynomials with binary coefficients (i.e., over GF(2)) of degree lower or equal to m-1. The polynomials can be associated with binary vectors of length m. For example, the vector (11001) represents the polynomial 1 + x + x^^4. This representation is often called polynomial representation.

The addition between two elements is defined as the addition of binary polynomials in GF(2), and the multiplication is the multiplication modulo a given irreducible polynomial over GF(2) of degree m. Note that all the roots of this polynomial are in GF(2^^m) but not in GF(2). Wild, right? 🤯

The chosen polynomial representation of the finite field GF(2^^m) is completely characterized by the irreducible polynomial. The following polynomials are chosen to represent the field GF(2^^m), for m varying from 2 to 16:

      m = 2, "111" (1+x+x^^2)

      m = 3, "1101", (1+x+x^^3)

      m = 4, "11001", (1+x+x^^4)

      m = 5, "101001", (1+x^^2+x^^5)

      m = 6, "1100001", (1+x+x^^6)
      m = 7, "10010001", (1+x^^3+x^^7)

      m = 8, "101110001", (1+x^^2+x^^3+x^^4+x^^8)

      m = 9, "1000100001", (1+x^^4+x^^9)

      m = 10, "10010000001", (1+x^^3+x^^10)

      m = 11, "101000000001", (1+x^^2+x^^11)

      m = 12, "1100101000001", (1+x+x^^4+x^^6+x^^12)

      m = 13, "11011000000001", (1+x+x^^3+x^^4+x^^13)

      m = 14, "110000100010001", (1+x+x^^6+x^^10+x^^14)

      m = 15, "1100000000000001", (1+x+x^^15)

      m = 16, "11010000000010001", (1+x+x^^3+x^^12+x^^16)

In order to make implementing this easier, these polynomials are also primitive. This means that any element of GF(2^^m) can be expressed as a power of a given root of this polynomial. These polynomials are also chosen so that they contain the minimum number of monomials. Efficiency stan 💅

8.2. Reed-Solomon Encoding Algorithm ✨

8.2.1. Encoding Principles 🦋

Let s = (s_0, ..., s_{k-1}) be a source vector of k elements over GF(2^^m). Let e = (e_0, ..., e_{n-1}) be the corresponding encoding vector of n elements over GF(2^^m). Since this is a linear code, encoding is performed by multiplying the source vector by a generator matrix, GM, of k rows and n columns over GF(2^^m). Thus:

   e = s * GM.

The definition of the generator matrix completely characterizes the RS code. Main character energy 👑

Let us consider that n = 2^^m - 1 and that 0 < k <= n. Let us denote by alpha the root of the primitive polynomial of degree m chosen in the list of Section 8.1 for the corresponding value of m. Let us consider a Vandermonde matrix of k rows and n columns, denoted by V_{k,n}, and built as follows: the {i, j} entry of V_{k,n} is v_{i,j} = alpha^^(i*j), where 0 <= i <= k - 1 and 0 <= j <= n - 1. This matrix generates a MDS code. However, this MDS code is not systematic, which is a problem for many networking applications. To obtain a systematic matrix (and code), the simplest solution consists in considering the matrix V_{k,k} formed by the first k columns of V_{k,n}, then inverting it and multiplying this inverse by V_{k,n}. Clearly, the product V_{k,k}^^-1 * V_{k,n} contains the identity matrix I_k on its first k columns, meaning that the first k encoding elements are equal to source elements. Besides, the associated code keeps the MDS property. Systematic and still MDS, iykyk 🧠

Therefore, the generator matrix of the code considered in this document is:

   GM = (V_{k,k}^^-1) * V_{k,n}

Note that, in practice, the [n,k]-RS code can be shortened to a [n',k]-RS code, where k <= n' < n, by considering the sub-matrix formed by the n' first columns of GM. Shortening it down, literally the best trick 🎀

8.2.2. Encoding Complexity ✨

okay so encoding can be done by pre-computing GM first and then multiplying the source vector (k elements) by GM (k rows and n columns) 💅. The pre-computation cost can be estimated as the cost of multiplying the inverse of a Vandermonde matrix by n-k vectors (i.e., the last n-k columns of V_{k,n}). Since inverting a k*k-Vandermonde matrix by a vector is O(k * (log(k))^^2), the generator matrix can be computed in 0((n-k)* k * (log(k))^^2)) operations. Once GM is pre-computed, encoding needs k operations per repair element (vector-matrix multiplication) 🔥.

encoding can also be done by first computing s * V_{k,k}^^-1 and then multiplying the result with V_{k,n} 🧚. Multiplying by the inverse of a square Vandermonde matrix is known as the interpolation problem, and its complexity is O(k * (log(k))^^2). Multiplying by a Vandermonde matrix, known as the multipoint evaluation problem, requires O((n-k) * log(k)) by using Fast Fourier Transform, as explained in [GO94] 🌸. The total complexity of this encoding algorithm is then O((k/(n-k)) * (log(k))^^2 + log(k)) operations per repair element 💖.

8.3. Reed-Solomon Decoding Algorithm 🦋

8.3.1. Decoding Principles

the Reed-Solomon decoding algorithm for the erasure channel lets you recover the k source elements from any set of k received elements 🎀. It's based on the fundamental property of the generator matrix, which is that any k*k-submatrix is invertible (see [MWS77]) 👑. Step one of decoding is extracting the k*k submatrix of the generator matrix by looking at the columns that correspond to the received elements. This works because every encoding element is the source vector multiplied by one column of the generator matrix, so the received vector of k encoding elements can be seen as the source vector multiplied by a k*k submatrix of the generator matrix ✨. Since that submatrix is invertible, step two is to invert it and multiply the received vector by the result to recover the source vector 🫶.

8.3.2. Decoding Complexity

the decoding algorithm above includes the matrix inversion and the vector-matrix multiplication 🍓. With the classical Gauss-Jordan algorithm, the matrix inversion takes O(k^^3) operations and the vector-matrix multiplication takes O(k^^2) operations 😭.

this can be improved by noticing that the received submatrix of GM is the product of the inverse of a Vandermonde matrix (V_(k,k)^^-1) and another Vandermonde matrix (called V', which is a submatrix of V_(k,n)) 🌈. So decoding can be done by multiplying the received vector by V'^^-1 (the interpolation problem, with complexity O( k * (log(k))^^2 )) and then by V_{k,k} (multipoint evaluation, with complexity O(k * log(k))). The global decoding complexity is then O((log(k))^^2) operations per source element 🧚‍♀️✨.

8.4. Implementation for the Packet Erasure Channel 🌷

in a packet erasure channel, each packet (including its symbol(s), since packets contain G >= 1 symbols) is either correctly received or erased 📦. The location of the erased symbols in the sequence of symbols MUST be known 🚨. The following specification describes how to use Reed-Solomon codes to generate redundant symbols from the k source symbols and to recover the source symbols from any set of k received symbols 💜.

The k source symbols of a source block are assumed to be made up of S m-bit elements. Each m-bit element corresponds to an element of the finite field GF(2^^m) through the polynomial representation (Section 8.1) 🍭. If some of the source symbols contain fewer than S elements, they MUST be virtually padded with zero elements (this can be the case for the last symbol of the last block of the object). However, this padding does not need to be actually sent with the data to the receivers 🙈.

The encoding process produces n encoding symbols of size S m-bit elements, of which k are source symbols (this is a systematic code) and n-k are repair symbols (Figure 7) 🌟. The m-bit elements of the repair symbols are calculated using the matching m-bit elements of the source symbol set. A logical u-th source vector, made of the u-th elements from the set of source symbols, is used to calculate a u-th encoding vector. That u-th encoding vector then gives the u-th elements for the set of encoding symbols calculated for the block 🦄. As a systematic code, the first k encoding symbols are the same as the k source symbols, and the last n-k repair symbols are the result of the Reed-Solomon encoding 🎀.

      Input:  k source symbols

0             u                                S-1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|             |X|                                 | source symbol 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|             |X|                                 | source symbol 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
              . . .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|             |X|                                 | source symbol k-1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                *

      +--------------------+
      |  generator matrix  |
      |         GM         |
      |       (k x n)      |
      +--------------------+

                |
                V

      Output: n encoding symbols (source + repair)

0             u                                S-1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|             |X|                                 | enc. symbol 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|             |X|                                 | enc. symbol 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
              . . .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|             |Y|                                 | enc. symbol n-1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 7: Packet Encoding Scheme 🖼️

one of the perks of this scheme is that losing some encoding symbols produces the same erasure pattern for each of the S encoding vectors 🧠. That means the matrix inversion only has to be done once and can be reused by all S encoding vectors. For large S, this matrix inversion cost becomes negligible next to the S vector-matrix multiplications 💅.

another perk is that the n-k repair symbols can be produced on demand 🌈. For example, a sender can start by producing a limited number of repair symbols and later, depending on the erasures it observes on the channel, decide to produce more, up to the n-k upper limit. To produce the repair symbol e_j, where k <= j < n, it's enough to multiply the S source vectors with column j of GM 🦋.

9. Security Considerations 🛡️

okay bestie, this part is serious, so let's get into it 🚨.

9.1. Problem Statement

a content delivery system can face lots of attacks 😈. Some target the network (e.g., to compromise the routing infrastructure by compromising the congestion control component), others target the Content Delivery Protocol (CDP) (e.g., to compromise its normal behavior), and some target the content itself. Since this document focuses on a FEC building block independent of any particular CDP (even though ALC and NORM are two natural candidates), this section only discusses the additional threats an arbitrary CDP may face when using this building block 🔐.

More specifically, several kinds of attacks exist 👀:

those that are meant to give access to confidential content (e.g., in case of non-free content),
those that try to corrupt the object being transmitted (e.g., to inject malicious code within an object or to prevent a receiver from using an object),
and those that try to compromise the receiver's behavior (e.g., by making the decoding of an object computationally expensive) 💀.

These attacks can be launched either against the data flow itself (e.g., by sending forged symbols) or against the FEC parameters that are sent either in-band (e.g., in an EXT_FTI or FDT Instance) or out-of-band (e.g., in a session description) 🙅‍♀️.

9.2. Attacks against the Data Flow

first of all, let's look at the attacks against the data flow 🌊.

9.2.1. Access to Confidential Objects

access control to the object being transmitted is typically provided by encryption 🔒. This encryption can be applied to the whole object (e.g., by the content provider, before the FEC encoding process), or be applied on a per-packet basis (e.g., when IPsec Encapsulating Security Payload (ESP) is used [RFC4303]) ✨. If access control is a concern, it is RECOMMENDED that one of these solutions be used 💖. Even though we mention these attacks here, they aren't related to or made easier by the use of FEC 🫶.

9.2.2. Content Corruption 🧯

okay so, what if someone sends forged packets to mess with your data? 😱 Protection against corruption (like after forged packets get sent) comes from a content integrity verification and sender authentication scheme. You can do this at the object level, but then if the object fails the check, a receiver has no way to figure out which symbol(s) got corrupted 💀. You can also do it at the packet level. In that case, after all the forged packets are removed, the object may be recovered sometimes ✨ (sometimes, bestie, not always 🙈). These techniques can provide this source authentication/content integrity service:

At the object level, the object MAY be digitally signed (with public key cryptography), for instance by using RSASSA-PKCS1-v1_5 [RFC3447]. This signature lets a receiver check the object integrity once the object has been fully decoded. Digital signatures are computationally expensive, but this calculation only happens once per object, which is usually fine 💖.
At the packet level, each packet can be digitally signed. The big catch is the high computational and transmission overheads this brings, unless Elliptic Curve Cryptography (ECC) is used 😩. To avoid that, the signature may span a set of symbols (instead of just one) to amortize the signature calculation. But if a single symbol is missing, the integrity of the whole set cannot be checked 🥲.
At the packet level, a Group Message Authentication Code (MAC) [RFC2104] scheme can be used. For instance, you can use HMAC-SHA-256 with a secret key shared by all the group members (the sender(s) and receivers) 🔐. Thanks to the secret key, this technique creates a cryptographically secured digest of a packet that gets sent along with the packet. The Group MAC scheme doesn't create prohibitive processing load or transmission overhead, but it has a major limitation. It only provides a group authentication/integrity service, since every group member shares the same secret group key. That means each member can send a forged packet 🚩. So it's only for situations where group members are fully trusted, or it's paired with another technique as a pre-check.
At the packet level, TESLA [RFC4082] is a very attractive and efficient solution. It's robust to losses, it provides a true authentication/integrity service, and it doesn't create any prohibitive processing load or transmission overhead 👑. The catch is that checking a packet requires a small delay (a second or more) after its reception ⏳.

Techniques relying on public key cryptography (digital signatures, and TESLA during the bootstrap process when it's used) require that public keys be securely associated to the entities. You can achieve this with a Public Key Infrastructure (PKI), a PGP Web of Trust, or by pre-distributing the public keys of each group member 🗝️.

Techniques relying on symmetric key cryptography (group MAC) require that a secret key be shared by all group members. You can achieve this with a group key management protocol, or by simply pre-distributing the secret key. (That manual solution has many limitations, so be careful 🙃.)

Honestly, it's up to the developer and deployer, since they know the security requirements and features of the target application area, to decide which solution is the most appropriate 🧠. Still, if there's any concern about the threat of object corruption, it is RECOMMENDED that at least one of these techniques be used 🛡️✨.

9.3. Attacks against the FEC Parameters

Okay, now let's talk about attacks on the FEC parameters (a.k.a. the FEC OTI) 👀. The FEC OTI can be sent in-band (in an EXT_FTI or in an FDT Instance containing FEC OTI for the object) or out-of-band (for example, in a session description). Attacks on these FEC parameters can stop the associated object from being decoded. For instance, modifying the B parameter leads to a different block partitioning at a receiver, which compromises decoding 💔. Or, setting the m parameter to 16 instead of 8 with FEC Encoding ID 2 increases the processing load while also compromising decoding 🥵.

So it is RECOMMENDED that security measures be taken to guarantee the FEC OTI integrity 🔒. For that, packets carrying FEC parameters sent in-band in an EXT_FTI header extension SHOULD be protected by one of the per-packet techniques described above: digital signature, group MAC, or TESLA 🫶. When FEC OTI is contained in an FDT Instance, that FDT Instance object SHOULD be protected, for instance by digitally signing it with XML digital signatures [RFC3275] ✍️. Finally, when FEC OTI is sent out-of-band (for example, in a session description), this FEC OTI SHOULD be protected, for instance by digitally signing the object that includes it 💅.

The same key management considerations apply here too 🔑.

10. 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 2 under the "ietf:rmt:fec:encoding" name-space to "Reed-Solomon Codes over GF(2^^m)" 🌸.

This document assigns the Fully-Specified FEC Encoding ID 5 under the "ietf:rmt:fec:encoding" name-space to "Reed-Solomon Codes over GF(2^^8)" 🌈.

This document assigns the FEC Instance ID 0, scoped by the Under-Specified FEC Encoding ID 129, to "Reed-Solomon Codes over GF(2^^8)" 🧚. More specifically, under the "ietf:rmt:fec:encoding:instance" sub-name-space that is scoped by the "ietf:rmt:fec:encoding" called "Small Block Systematic FEC Codes", this document assigns FEC Instance ID 0 to "Reed-Solomon Codes over GF(2^^8)" 💜.

11. Acknowledgments 🫶

The authors want to thank Brian Adamson, Igor Slepchin, Stephen Kent, Francis Dupont, Elwyn Davies, Magnus Westerlund, and Alfred Hoenes for their valuable comments 💖. The authors also want to thank Luigi Rizzo for his comments and for the design of the reference Reed-Solomon codec ✨.

12. References 📚

12.1. Normative References

[RFC2119]   Bradner, S., "Key words for use in RFCs to Indicate
            Requirement Levels", BCP 14, RFC 2119, March 1997.

[RFC5052]   Watson, M., Luby, M., and L. Vicisano, "Forward Error
            Correction (FEC) Building Block", RFC 5052, August 2007.

[RFC5445]   Watson, M., "Basic Forward Error Correction (FEC)
            Schemes", RFC 5445, March 2009.

12.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.

[RS-codec]  Rizzo, L., "Reed-Solomon FEC codec", available at
            http://info.iet.unipi.it/~luigi/vdm98/vdm980702.tgz and
            mirrored at http://planete-bcast.inrialpes.fr/, revised
            version of July 1998.

[Rizzo97]   Rizzo, L., "Effective Erasure Codes for Reliable Computer
            Communication Protocols", ACM SIGCOMM Computer
            Communication Review Vol.27, No.2, pp.24-36, April 1997.

[MWS77]     Mac Williams, F. and N. Sloane, "The Theory of Error
            Correcting Codes", North Holland, 1977.

[GO94]      Gohberg, I. and V. Olshevsky, "Fast algorithms with
            preprocessing for matrix-vector multiplication problems",
            Journal of Complexity, pp. 411-427, vol. 10, 1994.

[RFC5170]   Roca, V., Neumann, C., and D. Furodet, "Low Density
            Parity Check (LDPC) Forward Error Correction", RFC 5170,
            June 2008.

[RFC5053]   Luby, M., Shokrollahi, A., Watson, M., and T.
            Stockhammer, "Raptor Forward Error Correction Scheme",
            RFC 5053, October 2007.

[ALC]       Luby, M., Watson, M., and L. Vicisano, "Asynchronous
            Layered Coding (ALC) Protocol Instantiation", Work
            in Progress, November 2008.

[NORM]      Adamson, B., Bormann, C., Handley, M., and J. Macker,
            "NACK-Oriented Reliable Multicast Protocol", Work
            in Progress, March 2009.

[FLUTE]     Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V.
            Roca, "FLUTE - File Delivery over Unidirectional
            Transport", Work in Progress, September 2008.

[RFC3447]   Jonsson, J. and B. Kaliski, "Public-Key Cryptography
            Standards (PKCS) #1: RSA Cryptography Specifications
            Version 2.1", RFC 3447, February 2003.

[RFC4303]   Kent, S., "IP Encapsulating Security Payload (ESP)",
            RFC 4303, December 2005.

[RFC2104]   "HMAC: Keyed-Hashing for Message Authentication",
            RFC 2104, February 1997.

[RFC4082]   "Timed Efficient Stream Loss-Tolerant Authentication
            (TESLA): Multicast Source Authentication Transform
            Introduction", RFC 4082, June 2005.

[RFC3275]   Eastlake 3rd, D., Reagle, J., and D. Solo, "(Extensible
            Markup Language) XML-Signature Syntax and Processing",
            RFC 3275, March 2002.

Authors' Addresses 🧑‍💻

Jerome Lacan
ISAE/LAAS-CNRS
1, place Emile Blouin
Toulouse  31056
France

EMail: jerome.lacan@isae.fr
URI:   http://pagespro.isae.fr/jerome-lacan/


Vincent Roca
INRIA
655, av. de l'Europe
Inovallee; Montbonnot
ST ISMIER cedex  38334
France

EMail: vincent.roca@inria.fr
URI:   http://planete.inrialpes.fr/people/roca/


Jani Peltotalo
Tampere University of Technology
P.O. Box 553 (Korkeakoulunkatu 1)
Tampere  FIN-33101
Finland

EMail: jani.peltotalo@tut.fi
URI:   http://mad.cs.tut.fi/


Sami Peltotalo
Tampere University of Technology
P.O. Box 553 (Korkeakoulunkatu 1)
Tampere  FIN-33101
Finland

EMail: sami.peltotalo@tut.fi
URI:   http://mad.cs.tut.fi/

📦 where this page comes from

ietf: rfc5510 2009-04
💖 girlified by claude-haiku-5-5 on 2026-10-17: a language model's rewrite of the original, under its terms