RFC 6330

RaptorQ Forward Error Correction Scheme for Object Delivery

📅 published August 2011, from ietf

RFC 6330 ✨ RaptorQ Forward Error Correction Scheme for Object Delivery 🦋

okay bestie, let's start with the vibes check 💅 This is RFC 6330, a Standards Track doc (so it's an official Internet standard, no cap 👑). It came out in August 2011 and has ISSN 2070-1721. It was written by five people:

  • M. Luby at Qualcomm Incorporated 🌸
  • A. Shokrollahi at EPFL 🌸
  • M. Watson at Netflix Inc. 🌸
  • T. Stockhammer at Nomor Research 🌸
  • L. Minder at Qualcomm Incorporated 🌸

The title block doesn't list anything it obsoletes or updates, so this one is a fresh start 🌈

Abstract 🎀

This doc describes a Fully-Specified Forward Error Correction (FEC) scheme. It has FEC Encoding ID 6, it's built on the RaptorQ FEC code, and it's meant for reliable delivery of data objects 🔥

RaptorQ codes are a new family that give you way more flexibility, support much bigger source block sizes, and get better coding efficiency than the Raptor codes from RFC 5053. RaptorQ is also a fountain code, which means the encoder can make as many encoding symbols as you need, on the fly, from the source symbols of a source block. The decoder can rebuild the source block from pretty much any set of encoding symbols that's big enough. Usually a set the same size as the number of source symbols does the trick, and in rare cases you need a set that's a little bigger than that 🧚

The RaptorQ code here is a systematic code. That just means every single source symbol is one of the encoding symbols you can generate 💖

Status of This Memo 🌙

This is an Internet Standards Track document 📜

It's a product of the Internet Engineering Task Force (IETF), so it reflects what the IETF community agreed on. It went through public review and got approved for publication by the Internet Engineering Steering Group (IESG). If you want more on Internet Standards, check Section 2 of RFC 5741 🦋

For the current status, any errata, and how to send feedback, go to http://www.rfc-editor.org/info/rfc6330 🌸

Copyright (c) 2011 IETF Trust and the persons identified as the document authors. All rights reserved. 🫶

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) as they stood on the publication date. Please actually read these, because they spell out your rights and restrictions for this doc. Any Code Components pulled out of this document have to include the Simplified BSD License text, as described in Section 4.e of the Trust Legal Provisions, and they come with no warranty, as described in the Simplified BSD License 💅

Table of Contents 🧚

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  4
   2.  Requirements Notation  . . . . . . . . . . . . . . . . . . . .  4
   3.  Formats and Codes  . . . . . . . . . . . . . . . . . . . . . .  5
     3.1.  Introduction . . . . . . . . . . . . . . . . . . . . . . .  5
     3.2.  FEC Payload IDs  . . . . . . . . . . . . . . . . . . . . .  5
     3.3.  FEC Object Transmission Information  . . . . . . . . . . .  5
       3.3.1.  Mandatory  . . . . . . . . . . . . . . . . . . . . . .  5
       3.3.2.  Common . . . . . . . . . . . . . . . . . . . . . . . .  5
       3.3.3.  Scheme-Specific  . . . . . . . . . . . . . . . . . . .  6
   4.  Procedures . . . . . . . . . . . . . . . . . . . . . . . . . .  7
     4.1.  Introduction . . . . . . . . . . . . . . . . . . . . . . .  7
     4.2.  Content Delivery Protocol Requirements . . . . . . . . . .  7
     4.3.  Example Parameter Derivation Algorithm . . . . . . . . . .  7
     4.4.  Object Delivery  . . . . . . . . . . . . . . . . . . . . .  9
       4.4.1.  Source Block Construction  . . . . . . . . . . . . . .  9
       4.4.2.  Encoding Packet Construction . . . . . . . . . . . . . 11
       4.4.3.  Example Receiver Recovery Strategies . . . . . . . . . 12
   5.  RaptorQ FEC Code Specification . . . . . . . . . . . . . . . . 12
     5.1.  Background . . . . . . . . . . . . . . . . . . . . . . . . 12
       5.1.1.  Definitions  . . . . . . . . . . . . . . . . . . . . . 13
       5.1.2.  Symbols  . . . . . . . . . . . . . . . . . . . . . . . 14
     5.2.  Overview . . . . . . . . . . . . . . . . . . . . . . . . . 17
     5.3.  Systematic RaptorQ Encoder . . . . . . . . . . . . . . . . 18
       5.3.1.  Introduction . . . . . . . . . . . . . . . . . . . . . 18
       5.3.2.  Encoding Overview  . . . . . . . . . . . . . . . . . . 19
       5.3.3.  First Encoding Step: Intermediate Symbol Generation  . 21
       5.3.4.  Second Encoding Step: Encoding . . . . . . . . . . . . 27
       5.3.5.  Generators . . . . . . . . . . . . . . . . . . . . . . 27
     5.4.  Example FEC Decoder  . . . . . . . . . . . . . . . . . . . 30
       5.4.1.  General  . . . . . . . . . . . . . . . . . . . . . . . 30
       5.4.2.  Decoding an Extended Source Block  . . . . . . . . . . 31
     5.5.  Random Numbers . . . . . . . . . . . . . . . . . . . . . . 36
       5.5.1.  The Table V0 . . . . . . . . . . . . . . . . . . . . . 36
       5.5.2.  The Table V1 . . . . . . . . . . . . . . . . . . . . . 37
       5.5.3.  The Table V2 . . . . . . . . . . . . . . . . . . . . . 38
       5.5.4.  The Table V3 . . . . . . . . . . . . . . . . . . . . . 40
     5.6.  Systematic Indices and Other Parameters  . . . . . . . . . 41
     5.7.  Operating with Octets, Symbols, and Matrices . . . . . . . 62
       5.7.1.  General  . . . . . . . . . . . . . . . . . . . . . . . 62
       5.7.2.  Arithmetic Operations on Octets  . . . . . . . . . . . 62
       5.7.3.  The Table OCT_EXP  . . . . . . . . . . . . . . . . . . 63
       5.7.4.  The Table OCT_LOG  . . . . . . . . . . . . . . . . . . 64
       5.7.5.  Operations on Symbols  . . . . . . . . . . . . . . . . 65
       5.7.6.  Operations on Matrices . . . . . . . . . . . . . . . . 65
     5.8.  Requirements for a Compliant Decoder . . . . . . . . . . . 65
   6.  Security Considerations  . . . . . . . . . . . . . . . . . . . 66
   7.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 67
   8.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 67
   9.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 67
     9.1.  Normative References . . . . . . . . . . . . . . . . . . . 67
     9.2.  Informative References . . . . . . . . . . . . . . . . . . 68

1. Introduction 🌸

okay so this doc specifies an FEC scheme for the RaptorQ forward error correction code, aimed at object delivery apps 🎀 The idea of an FEC scheme comes from RFC 5052 [RFC5052]. This doc follows the format laid out there and uses the same terminology 💅

RaptorQ is the next generation of the Raptor code from RFC 5053 [RFC5053]. It gives you better reliability, better coding efficiency, and bigger source block sizes than RFC 5053 [RFC5053] does. All of that makes RaptorQ way easier to use in an object delivery Content Delivery Protocol compared to RFC 5053 RFC 5053 [RFC5053]. (Yes, the RFC 5053 is repeated in the original, that's just how it reads 🙈) If you want the full math, the design and analysis, plus tons of simulation results, they're in [RaptorCodes] 🤓

The RaptorQ FEC scheme is a Fully-Specified FEC scheme with FEC Encoding ID 6 ✨

RaptorQ is a fountain code, so the encoder can make as many encoding symbols as you need, on the fly, from the source symbols of a block. The decoder can recover the source block from almost any set of encoding symbols whose size is only a little bigger than the number of source symbols 🧚

The code in this doc is systematic, which means two things come along for the ride: the original, unmodified source symbols, and a bunch of repair symbols, can both be sent from sender to receiver 🦋 If you want background on FEC in reliable multicast, see [RFC3453] 🌈

2. Requirements Notation 🫶

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 [RFC2119] 📜 Those capitalised words are the official requirement words, so read them exactly as RFC 2119 defines them 💖

3. Formats and Codes 🎀

3.1. Introduction 🌷

The octet order of all fields is network byte order, which is big-endian 🍓

3.2. FEC Payload IDs 🦋

The FEC Payload ID MUST be a 4-octet field, laid out like this 👑

     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
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |     SBN       |               Encoding Symbol ID              |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 1: FEC Payload ID Format

Here's the breakdown of the two fields:

  • Source Block Number (SBN): 8-bit unsigned integer. It's a non-negative integer that identifies the source block the encoding symbols in the packet belong to 🌸
  • Encoding Symbol ID (ESI): 24-bit unsigned integer. It's a non-negative integer that identifies the encoding symbols inside the packet 🧚

How the Source Block Number and the Encoding Symbol Identifier get interpreted is defined in Section 4 🔥

3.3. FEC Object Transmission Information 💅

3.3.1. Mandatory 🌈

The value of the FEC Encoding ID MUST be 6, as IANA assigns it (see Section 7) 🫶

3.3.2. Common ✨

The Common FEC Object Transmission Information elements this FEC scheme uses are:

  • Transfer Length (F): 40-bit unsigned integer. It's a non-negative integer that's at most 946270874880. This is the transfer length of the object, measured in octets 💖
  • Symbol Size (T): 16-bit unsigned integer. It's a positive integer that's less than 2^^16. This is the size of one symbol, measured in octets 🌙

The encoded Common FEC Object Transmission Information (OTI) format looks like this in Figure 2 🎀

     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
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                      Transfer Length (F)                      |
    +               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |               |    Reserved   |           Symbol Size (T)     |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 2: Encoded Common FEC OTI for RaptorQ FEC Scheme

NOTE: The 946270874880 limit on transfer length isn't random. It comes from three limits working together: the symbol size maxes out at 2^^16-1, a source block can hold at most 56403 symbols, and you can have at most 2^^8 source blocks 🤯

Part 1 of 16 done ✨ Up next: Section 3.3.3, Scheme-Specific 🦋

3.3.3. Scheme-Specific ✨

okay so the scheme-specific bit carries three params for this FEC scheme 💅:

  • The number of source blocks (Z): 8-bit unsigned integer.
  • The number of sub-blocks (N): 16-bit unsigned integer.
  • A symbol alignment parameter (Al): 8-bit unsigned integer.

all three are positive integers 🎀. they get packed into a 4-octet field, Z then N then Al, like this:

     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
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |       Z       |              N                |       Al      |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 3: Encoded Scheme-Specific FEC Object Transmission Information

the full encoded FEC Object Transmission Information is a 12-octet field 🦋, which is just the encoded Common part glued onto the encoded Scheme-Specific part. and these three params are what decide how the source block partitioning works, see Section 4.4.1.2 🧚

4. Procedures 🔥

4.1. Introduction

for any undefined symbols or functions in this section, especially "ceil" and "floor", go check Section 5.1 🌸

4.2. Content Delivery Protocol Requirements

this section is all about the info that gets passed between the RaptorQ FEC scheme and any Content Delivery Protocol (CDP) that uses RaptorQ to deliver objects 🫶

the RaptorQ encoder and decoder for object delivery need these from the CDP:

  • F: the transfer length of the object, in octets
  • Al: the symbol alignment parameter
  • T: the symbol size in octets, which MUST be a multiple of Al
  • Z: the number of source blocks
  • N: the number of sub-blocks in each source block

the encoder also needs one extra thing:

  • the object to be encoded, which is F octets long

and for every packet it sends, the encoder hands the CDP these:

  • Source Block Number (SBN)
  • Encoding Symbol ID (ESI)
  • Encoding symbol(s)

bestie, the CDP MUST communicate this information to the receiver 😭

4.3. Example Parameter Derivation Algorithm

this part gives recommendations for working out the three transport params, T, Z, and N 🍓 it starts from these inputs:

  • F: the transfer length of the object, in octets
  • WS: the maximum size block that is decodable in working memory, in octets
  • P': the maximum payload size in octets, which is assumed to be a multiple of Al
  • Al: the symbol alignment parameter, in octets
  • SS: a parameter where the desired lower bound on the sub-symbol size is SS*Al
  • K'_max: the maximum number of source symbols per source block.

Note: Section 5.1.2 defines K'_max to be 56403.

from there, T, Z, and N get calculated like this 🧮:

Let

o  T = P'

o  Kt = ceil(F/T)

o  N_max = floor(T/(SS*Al))

o  for all n=1, ..., N_max

   *  KL(n) is the maximum K' value in Table 2 in Section 5.6 such
      that

         K' <= WS/(Al*(ceil(T/(Al*n))))

o  Z = ceil(Kt/KL(N_max))

o  N is the minimum n=1, ..., N_max such that ceil(Kt/Z) <= KL(n)

it is RECOMMENDED that each packet contains exactly one symbol 💜 however, receivers SHALL support the reception of packets that contain multiple symbols, so nobody gets left behind 🙈

Kt is just the total number of symbols needed to represent the object's source data ✨

the algorithm above plus the one in Section 4.4.1.2 make sure the sub-symbol sizes are a multiple of Al. this is super useful because the sums used in encoding and decoding usually get done several octets at a time (like 4 octets at a time on a 32-bit processor), so things go faster when the sub-symbol sizes line up with that 🚀

the recommended setting for the input Al is 4 🌈

the WS param can be used to make encoded data that decodes efficiently with limited working memory at the decoder. the real max decoder memory for a given WS depends on the implementation, but it's possible to implement decoding with working memory only slightly bigger than WS 👑

4.4. Object Delivery

4.4.1. Source Block Construction

4.4.1.1. General

to run the RaptorQ encoder on an object, the object may be broken into Z >= 1 blocks, called source blocks 🦋 the encoder runs on each source block independently. each one gets a unique Source Block Number (SBN), where the first is zero, the second is one, and so on. each source block is split into K source symbols, each T octets, and each source symbol gets a unique Encoding Symbol Identifier (ESI), where the first is zero, the second is one, etc. 💖

each source block with K source symbols is split into N >= 1 sub-blocks, small enough to decode in working memory. each sub-block is split into K sub-symbols of size T' 🧚

K isn't necessarily the same for every source block, and T' isn't necessarily the same for every sub-block. BUT the symbol size T is the same for all source blocks of an object, and K is the same for every sub-block of a source block. the exact partitioning is in Section 4.4.1.2 below 🫶

4.4.1.2. Source Block and Sub-Block Partitioning

this part is determined by five input params, F, Al, T, Z, and N, plus a function called Partition[] 🍓 they go like this:

  • F: the transfer length of the object, in octets
  • Al: a symbol alignment parameter, in octets
  • T: the symbol size, in octets, which MUST be a multiple of Al
  • Z: the number of source blocks
  • N: the number of sub-blocks in each source block

these params MUST be set so that ceil(ceil(F/T)/Z) <= K'_max. the recommendations for deriving them are in Section 4.3 ✨

Partition[I,J] takes a block of size I and splits it into J roughly equal-sized blocks. specifically, it makes JL blocks of length IL and JS blocks of length IS. the output of Partition[I, J] is the sequence (IL, IS, JL, JS), where IL = ceil(I/J), IS = floor(I/J), JL = I - IS * J, and JS = J - JL 💅

the source object MUST be partitioned into source blocks and sub-blocks like this 👑:

Let

o  Kt = ceil(F/T),

o  (KL, KS, ZL, ZS) = Partition[Kt, Z],

o  (TL, TS, NL, NS) = Partition[T/Al, N].

then the object MUST be partitioned into Z = ZL + ZS contiguous source blocks. the first ZL source blocks each have KL*T octets (that's KL source symbols of T octets each), and the remaining ZS source blocks each have KS*T octets (KS source symbols of T octets each) 🦋

if Kt*T > F, then for encoding purposes, the last symbol of the last source block MUST be padded at the end with Kt*T-F zero octets. no skipping this one, it's important 🙈

next, each source block with K source symbols MUST be split into N = NL + NS contiguous sub-blocks. the first NL sub-blocks each have K contiguous sub-symbols of size TL*Al octets, and the remaining NS sub-blocks each have K contiguous sub-symbols of size TS*Al octets. the symbol alignment parameter Al makes sure sub-symbols are always a multiple of Al octets 🌸

finally, the mth symbol of a source block is made by concatenating the mth sub-symbol from each of the N sub-blocks 💜. which means that when N > 1, a symbol is NOT a contiguous portion of the object. wild, right? 🤯

4.4.2. Encoding Packet Construction

each encoding packet has this info 📦:

  • Source Block Number (SBN)
  • Encoding Symbol ID (ESI)
  • encoding symbol(s)

every source block is encoded independently of the others. each encoding packet only has encoding symbols made from the one source block its SBN points to. source blocks are numbered consecutively from zero 🎀

ESI values from 0 to K-1 identify the source symbols of a source block in order (K being the number of source symbols in that block). ESIs from K onwards identify repair symbols that the RaptorQ encoder generated from the source symbols 🧚

each encoding packet is EITHER only source symbols (a source packet) OR only repair symbols (a repair packet). a packet can hold any number of symbols from the same source block. if the last source symbol in a source packet has padding octets added for FEC encoding, those octets don't need to be included in the packet. otherwise, each packet MUST contain only whole symbols 🫶

the Encoding Symbol ID, X, in each source packet is the ESI of the first source symbol in that packet. the next source symbols in the packet are X+1 to X+G-1 in order, where G is the number of symbols in the packet 💅

the same goes for repair packets: the ESI X placed in a repair packet is the ESI of the first repair symbol in it, and the following repair symbols are X+1 to X+G-1 in sequence, where G is the number of symbols in the packet ✨

and the receiver doesn't need to know the total number of repair packets, which is honestly such a relief 😭🌈

4.4.3. Example Receiver Recovery Strategies ✨

okay so a receiver can use the encoding symbols it got for each source block of an object to recover that block's source symbols, totally independently of all the other source blocks 🫶 no cap, that's the whole vibe.

If there's one sub-block per source block (so N = 1), then the part of the original object that belongs to a source block is just the source symbols of that block, stitched together in consecutive ESI order. easy 💅

If there are multiple sub-blocks per source block (N > 1), it gets a little more layered 🌸 The part of the original object for that source block is the sub-blocks for it, concatenated, and inside each sub-block the sub-symbols go in consecutive ESI order. Here, the best recovery strategy depends on how much Random Access Memory (RAM) the receiver has, and there are two main options worth thinking about.

Strategy one: recover the source symbols of the whole source block using the decoding procedures in Section 5, then reorder the sub-symbols so that all the consecutive sub-symbols of the first sub-block come first, then all of the second sub-block's, and so on, up to the Nth sub-block. This one is especially great if the receiver has enough RAM to decode an entire source block at once 👑

Strategy two: recover each sub-block separately. For example, a receiver could split up the sub-symbols as encoding symbol packets arrive, store each sub-block's sub-symbols on their own, and then use those stored sub-symbols to recover that sub-block with the decoding procedures in Section 5. This is especially useful if the receiver only has enough RAM to decode one sub-block at a time 🧚

5. RaptorQ FEC Code Specification ✨

5.1. Background 🌊

okay now we're in the deep end. For the purpose of the RaptorQ FEC code specification in this section, the definitions, symbols, and abbreviations below apply. You're expected to have a basic understanding of linear algebra, matrix operations, and finite fields. Specifically, matrix multiplication and matrix inversion over a mix of the finite fields GF[2] and GF[256] get used here. Familiarity with sparse linear equations, and with efficient algorithms that take advantage of them, is also honestly super beneficial for anyone implementing this 🤓

5.1.1. Definitions 💜

  • Source block: a block of K source symbols that get considered together for RaptorQ encoding and decoding.
  • Extended Source Block: a block of K' source symbols, where K' >= K, built from a source block plus zero or more padding symbols.
  • Symbol: a unit of data. Its size in octets is the symbol size, which is always a positive integer.
  • Source symbol: the smallest unit of data used during the encoding process. All source symbols in a source block are the same size.
  • Padding symbol: a symbol with all zero bits, added to the source block to form the extended source block.
  • Encoding symbol: a symbol that can be sent as part of encoding a source block. Encoding symbols are the source symbols of the block plus the repair symbols generated from it. Repair symbols generated from a source block are the same size as that block's source symbols.
  • Repair symbol: an encoding symbol of a source block that isn't a source symbol. Repair symbols are generated from the block's source symbols.
  • Intermediate symbols: symbols generated from the source symbols using an inverse encoding process based on pre-coding relationships. Repair symbols are then generated directly from the intermediate symbols. Encoding symbols don't include intermediate symbols, which means intermediate symbols are never sent as part of a source block's encoding. For the encoding process, intermediate symbols are split into LT symbols and PI symbols.
  • LT symbols: a process similar to the one in [LTCodes] makes part of the contribution to each generated encoding symbol, using the intermediate symbols designated as LT symbols.
  • PI symbols: a process even simpler than the one in [LTCodes] makes the other part of the contribution to each generated encoding symbol, using the intermediate symbols designated as PI symbols. In the decoding algorithm suggested in Section 5.4, PI symbols are inactivated at the start, meaning they're placed into the matrix U at the beginning of the first phase of decoding. The symbols for U's columns are sometimes called "inactivated" symbols, and since PI symbols get inactivated right at the beginning, they're considered "permanently inactivated". 🔒
  • HDPC symbols: a small subset of the intermediate symbols. Each HDPC symbol has a pre-coding relationship with a large fraction of the other intermediate symbols. HDPC means "High Density Parity Check".
  • LDPC symbols: a moderate-sized subset of the intermediate symbols. Each LDPC symbol has a pre-coding relationship with a small fraction of the other intermediate symbols. LDPC means "Low Density Parity Check".
  • Systematic code: a code in which all source symbols are included as part of the encoding symbols of a source block. The RaptorQ code described here is a systematic code 🎀
  • Encoding Symbol ID (ESI): information that uniquely identifies each encoding symbol associated with a source block, for sending and receiving purposes.
  • Internal Symbol ID (ISI): information that uniquely identifies each symbol associated with an extended source block, for encoding and decoding purposes.
  • Arithmetic operations on octets and symbols and matrices: the operations used to produce encoding symbols from source symbols, and vice versa. See Section 5.7.

5.1.2. Symbols 🦋

okay this is the notation you'll see all over this section. Some of these letters are variables whose meaning depends on where they show up, so keep your eyes peeled 👀

  • i, j, u, v, h, d, a, b, d1, a1, b1, v, m, x, y: values or variables of one type or another, depending on context.
  • X: a non-negative integer that's either an ISI value or an ESI value, depending on context.
  • ceil(x): the smallest integer that is greater than or equal to x, where x is a real value.
  • floor(x): the largest integer that is less than or equal to x, where x is a real value.
  • min(x,y): the minimum of the values x and y, and in general the minimum of all the argument values.
  • max(x,y): the maximum of the values x and y, and in general the maximum of all the argument values.
  • i % j: i modulo j.
  • i + j: the sum of i and j. If i and j are octets or symbols, this is arithmetic on octets or symbols, respectively, as defined in Section 5.7. If i and j are integers, it's the usual integer addition.
  • i * j: the product of i and j. If i and j are octets, this is arithmetic on octets, as defined in Section 5.7. If i is an octet and j is a symbol, it's the multiplication of a symbol by an octet, also defined in Section 5.7. And if i and j are integers, i * j is the usual product of integers.
  • a ^^ b: a raised to the power b. If a is an octet and b is a non-negative integer, this means a*a*...a (b terms), with '' being the octet product defined in Section 5.7.
  • u ^ v: for equal-length bit strings u and v, the bitwise exclusive-or of u and v.
  • Transpose[A]: the transposed matrix of matrix A. In this specification, all matrices have entries that are octets.
  • A^^-1: the inverse matrix of matrix A. All matrices here have octets as entries, so the matrix entry operations are done as stated in Section 5.7, and A^^-1 is the matrix inverse of A with respect to octet arithmetic.
  • K: the number of symbols in a single source block.
  • K': the number of source plus padding symbols in an extended source block. For most of this specification, padding symbols are treated as additional source symbols.
  • K'_max: the maximum number of source symbols that can be in a single source block. Set to 56403.
  • L: the number of intermediate symbols for a single extended source block.
  • S: the number of LDPC symbols for a single extended source block. These are LT symbols. For each value of K' shown in Table 2 in Section 5.6, the corresponding value of S is a prime number.
  • H: the number of HDPC symbols for a single extended source block. These are PI symbols.
  • B: the number of intermediate symbols that are LT symbols, excluding the LDPC symbols.
  • W: the number of intermediate symbols that are LT symbols. For each value of K' in Table 2 shown in Section 5.6, the corresponding value of W is a prime number.
  • P: the number of intermediate symbols that are PI symbols. These contain all HDPC symbols.
  • P1: the smallest prime number greater than or equal to P.
  • U: the number of non-HDPC intermediate symbols that are PI symbols.
  • C: an array of intermediate symbols, C[0], C[1], C[2], ..., C[L-1].
  • C': an array of the symbols of the extended source block, where C'[0], C'[1], C'[2], ..., C'[K-1] are the source symbols of the source block and C'[K], C'[K+1], ..., C'[K'-1] are padding symbols.
  • V0, V1, V2, V3: four arrays of 32-bit unsigned integers, V0[0], V0[1], ..., V0[255]; V1[0], V1[1], ..., V1[255]; V2[0], V2[1], ..., V2[255]; and V3[0], V3[1], ..., V3[255], as shown in Section 5.5. 🌈
  • Rand[y, i, m]: a pseudo-random number generator.
  • Deg[v]: a degree generator.
  • Enc[K', C ,(d, a, b, d1, a1, b1)]: an encoding symbol generator.
  • Tuple[K', X]: a tuple generator function.
  • T: the symbol size in octets.
  • J(K'): the systematic index associated with K'.
  • G: any generator matrix.
  • I_S: the S x S identity matrix.

5.2. Overview ✨

okay so this section is where the systematic RaptorQ FEC code gets defined, and it's giving main character energy 💅

Symbols are the basic units of data for encoding and decoding 🦋 For each source block, every symbol is the same size, called the symbol size T. The only atomic operations used on symbols, for both encoding and decoding, are the arithmetic operations in Section 5.7 🔥

The basic encoder is in Section 5.3. It starts by deriving a block of intermediate symbols from the source symbols of a source block 🌸 That intermediate block is special because both source and repair symbols can be generated from it using the same process 🫶 The encoder makes repair symbols from the intermediate block efficiently: each repair symbol is the exclusive-or of a small number of intermediate symbols from the block. Source symbols can be reproduced from the intermediate block with that same process too ✨ The encoding symbols are just the source and repair symbols put together 💖

An example decoder is in Section 5.4 🧚 The whole process for making source and repair symbols from the intermediate block is built so that the intermediate block can be recovered from any sufficiently large set of encoding symbols, no matter how the source and repair symbols are mixed in that set 😭 Once the intermediate block is back, missing source symbols can be recovered using the encoding process. iconic 👑

The requirements for a RaptorQ-compliant decoder are in Section 5.8 💅 There are a bunch of decoding algorithms that could meet these requirements, and an efficient one is given in Section 5.4 🍓

The construction of intermediate and repair symbols is partly based on a pseudo-random number generator, described in Section 5.3 🎀 That generator uses a fixed set of 1024 random numbers that must be available to both sender and receiver. Those numbers are in Section 5.5. RaptorQ encoding and decoding operate on octets, and Section 5.7 explains how to do those operations 🌈

Last but not least, building the intermediate symbols from the source symbols is controlled by "systematic indices" ⭐ Their values are listed in Section 5.6 for specific extended source block sizes between 6 and K'_max = 56403 source symbols. So the RaptorQ code supports source blocks with anywhere from 1 to 56403 source symbols. Literally a whole range 🦋

5.3. Systematic RaptorQ Encoder

5.3.1. Introduction

okay bestie, so for a source block with K source symbols, the encoder and decoder pad the block out with K'-K extra padding symbols 🧁 Here K' is the smallest value that is at least K in the systematic index Table 2 of Section 5.6 🌸 Why pad? It makes encoding and decoding faster and means the encoder and decoder don't have to store as much table info 💜

When it comes to sending and receiving data, K is what sets the number of source symbols in a source block, so the sender and receiver both need to know K 🫶 Once they know K, they can work out K' themselves, and the K'-K padding symbols get added to the source block automatically. No extra communication needed, pretty smart right? ✨

The encoding symbol ID (ESI) is how a sender and receiver label the encoding symbols of a source block. The encoding symbols are the source symbols plus the repair symbols tied to that source block 🦋 For a source block with K source symbols, the ESIs for the source symbols are 0, 1, 2, ..., K-1, and the ESIs for the repair symbols are K, K+1, K+2, .... Using ESIs in transport means the values run on consecutively from source to repair symbols, which is so clean 🥹

For encoding and decoding, the value K' derived from K is used as the number of source symbols of the extended source block 💅 The K' source symbols are the original K source symbols plus K'-K padding symbols. The Internal Symbol ID (ISI) is what the encoder and decoder use to identify symbols in the extended source block, both for generating encoding symbols and for decoding 🔥 For a source block with K original source symbols, the ISIs for the original source symbols are 0, 1, 2, ..., K-1, the ISIs for the K'-K padding symbols are K, K+1, K+2, ..., K'-1, and the ISIs for the repair symbols are K', K'+1, K'+2, .... Using ISIs for encoding and decoding lets the padding symbols get treated the same way as the other source symbols in the extended block 🌈 It also means a given prefix of repair symbols gets generated consistently for a given K', no matter what K is 🍓

Now the ESI-ISI relationship is simple 🧚 The ESIs and ISIs for the original K source symbols are identical. The K'-K padding symbols have an ISI but no ESI, because they're never sent or received. And a repair symbol's ISI is just its ESI plus K'-K 💖 Translating between ESIs (used for the encoding symbols that get sent and received) and ISIs (used for encoding and decoding), plus padding the extended source block with padding symbols, is handled internally by the RaptorQ encoder and decoder. Not your problem, bestie 🫶

5.3.2. Encoding Overview

the systematic RaptorQ encoder can make any number of repair symbols from a source block of K source symbols that have been placed into an extended source block C' 🦋 Figure 4 shows the overview.

The first step of encoding is to build the extended source block by adding zero or more padding symbols, so the total number of symbols, K', is one of the values in Section 5.6 🌸 Each padding symbol is T octets long, and every octet in it is zero 💜 K' MUST be the smallest value from the Section 5.6 table that is greater than or equal to K 🔥

     -----------------------------------------------------------+
     |                                                          |
     |    +-----------+    +--------------+    +-------------+  |
  C' |    |           | C' | Intermediate | C  |             |  |
 ----+--->|  Padding  |--->|    Symbol    |--->|   Encoding  |--+-->
  K  |    |           | K' |  Generation  | L  |             |  |
     |    +-----------+    +--------------+    +-------------+  |
     |           |                             (d,a,b, ^        |
     |           |                            d1,a1,b1)|        |
     |           |                              +------------+  |
     |           |              K'              |   Tuple    |  |
     |           +----------------------------->|            |  |
     |                                          | Generation |  |
     |                                          +------------+  |
     |                                                 ^        |
     +-------------------------------------------------+--------+
                                                       |
                                                     ISI X

Figure 4: Encoding Overview 🎀

Let C'[0], ..., C'[K-1] be the K source symbols. ✨

Let C'[K], ..., C'[K'-1] be the K'-K padding symbols, and they're all zero bits 🌈 Then C'[0], ..., C'[K'-1] are the symbols of the extended source block that encoding and decoding work on 💅

From here on, these padding symbols get treated as extra source symbols and called that 🧚 But they're not part of the encoding symbols, so they never get sent as part of the encoding 🫶 At a receiver, K' can be computed from K. The receiver then inserts K'-K padding symbols at the end of a source block of K' source symbols, and recovers the remaining K source symbols from the received encoding symbols 🦋

The second step is to generate L, where L > K', intermediate symbols from the K' source symbols 💖 Here, K' source tuples (d[0], a[0], b[0], d1[0], a1[0], b1[0]), ..., (d[K'-1], a[K'-1], b[K'-1], d1[K'-1], a1[K'-1], b1[K'-1]) are generated with the Tuple[] generator from Section 5.3.5.4 ⭐ The K' source tuples plus the ISIs of the K' source symbols are then used to work out L intermediate symbols C[0], ..., C[L-1] from the source symbols, using an inverse encoding process. That process can be done by a RaptorQ decoding process 🔥

Certain "pre-coding relationships" have to hold among the L intermediate symbols 🌸 Section 5.3.3.3 describes these, and Section 5.3.3.4 describes how the intermediate symbols get generated from the source symbols 🍓

Once the intermediate symbols exist, repair symbols can be produced 🎀 For a repair symbol with ISI X > K', a tuple of non-negative integers (d, a, b, d1, a1, b1) can be generated with the Tuple[] generator from Section 5.3.5.4 🧁 Then the tuple (d, a, b, d1, a1, b1) and the ISI X are used to generate the matching repair symbol from the intermediate symbols with the Enc[] generator in Section 5.3.5.3 ✨ The ESI for that repair symbol is then X-(K'-K) 🦋 Also, source symbols of the extended source block can be generated with this same process: for any X < K', the symbol generated has the same value as C'[X] 💜

5.3.3. First Encoding Step: Intermediate Symbol Generation

5.3.3.1. General

okay so this encoding step is a pre-coding step that generates the L intermediate symbols C[0], ..., C[L-1] from the source symbols C'[0], ..., C'[K'-1], where L > K' is defined in Section 5.3.3.3 🌈 The intermediate symbols are uniquely defined by two sets of constraints 🫶

  1. The intermediate symbols are related to the source symbols by a set of source symbol tuples and by the ISIs of the source symbols. How those source symbol tuples get generated is defined in Section 5.3.3.2, using the Tuple[] generator from Section 5.3.5.4 🦋
  2. A number of pre-coding relationships hold within the intermediate symbols themselves. Those are defined in Section 5.3.3.3 💖

Then the generation of the L intermediate symbols is defined in Section 5.3.3.4 🍓

5.3.3.2. Source Symbol Tuples

each of the K' source symbols is linked to a source symbol tuple (d[X], a[X], b[X], d1[X], a1[X], b1[X]) for 0 <= X < K' 🧚 The source symbol tuples are worked out with the Tuple[] generator from Section 5.3.5.4, like this:

For each X, 0 <= X < K'

   (d[X], a[X], b[X], d1[X], a1[X], b1[X]) = Tuple[K, X]

5.3.3.3. Pre-Coding Relationships

okay so the pre-coding relationships are the rules that tie all the intermediate symbols together 🎀 Basically, a set of S+H linear combinations of the intermediate symbols has to evaluate to zero ✨ There are S LDPC symbols and H HDPC symbols, so L = K'+S+H. There's also a second way to split up the L intermediate symbols: W LT symbols and P PI symbols, which means L = W+P too 🫶 The PI symbols get treated differently from the LT symbols during encoding, so it matters which is which 💅

The P PI symbols are the H HDPC symbols plus a set of U = P-H of the other K' intermediate symbols. The W LT symbols are the S LDPC symbols plus W-S of the other K' intermediate symbols. All of these parameters come from K'. H(K'), S(K'), and W(K') are derived from Table 2 in Section 5.6 🌸

Here's the setup:

  • S = S(K')
  • H = H(K')
  • W = W(K')
  • L = K' + S + H
  • P = L - W
  • P1 denotes the smallest prime number greater than or equal to P.
  • U = P - H
  • B = W - S
  • C[0], ..., C[B-1] denote the intermediate symbols that are LT symbols but not LDPC symbols.
  • C[B], ..., C[B+S-1] denote the S LDPC symbols that are also LT symbols.
  • C[W], ..., C[W+U-1] denote the intermediate symbols that are PI symbols but not HDPC symbols.
  • C[L-H], ..., C[L-1] denote the H HDPC symbols that are also PI symbols.

The first set of pre-coding relations is called the LDPC relations 🌈 They require that, once the process finishes, the symbols D[0] , ..., D[S-1] are all zero:

  • Initialize the symbols D[0] = C[B], ..., D[S-1] = C[B+S-1].
  • For i = 0, ..., B-1 do:
    • a = 1 + floor(i/S)
    • b = i % S
    • D[b] = D[b] + C[i]
    • b = (b + a) % S
    • D[b] = D[b] + C[i]
    • b = (b + a) % S
    • D[b] = D[b] + C[i]
  • For i = 0, ..., S-1 do:
    • a = i % P
    • b = (i+1) % P
    • D[i] = D[i] + C[W+a] + C[W+b]

Quick reminder that symbol addition works the way Section 5.7 says 💖

Since the LDPC relations in that algorithm are linear, there's a S x B matrix G_LDPC,1 and a S x P matrix G_LDPC,2 that make this true:

G_LDPC,1 * Transpose[(C[0], ..., C[B-1])] + G_LDPC,2 *
Transpose(C[W], ..., C[W+P-1]) + Transpose[(C[B], ..., C[B+S-1])]
= 0

(G_LDPC,1 comes from the first loop in the algorithm above, and G_LDPC,2 can be worked out from the second loop 🧚)

The second set of relations among C[0], ..., C[L-1] are the HDPC relations, and they go like this 😭

Let:

  • alpha denote the octet represented by integer 2 as defined in Section 5.7.
  • MT denote an H x (K' + S) matrix of octets. For j=0, ..., K'+S-2, the entry MT[i,j] is the octet represented by the integer 1 if i= Rand[j+1,6,H] or i = (Rand[j+1,6,H] + Rand[j+1,7,H-1] + 1) % H, and MT[i,j] is the zero element for all other values of i. For j=K'+S-1, MT[i,j] = alpha^^i for i=0, ..., H-1.
  • GAMMA denote a (K'+S) x (K'+S) matrix of octets, where:
GAMMA[i,j] =

   alpha ^^ (i-j) for i >= j,

   0 otherwise.

Then the relationship between the first K'+S intermediate symbols C[0], ..., C[K'+S-1] and the H HDPC symbols C[K'+S], ..., C[K'+S+H-1] is:

Transpose[C[K'+S], ..., C[K'+S+H-1]] + MT * GAMMA *
Transpose[C[0], ..., C[K'+S-1]] = 0,

where * means standard matrix multiplication, using octet multiplication to multiply a matrix of octets by a matrix of symbols (basically the column vector of symbols), and + means addition over octet vectors 💅✨

5.3.3.4. Intermediate Symbols

5.3.3.4.1. Definition

okay so given the K' source symbols C'[0], C'[1], ..., C'[K'-1], the L intermediate symbols C[0], C[1], ..., C[L-1] are the uniquely defined symbol values that satisfy these two conditions 🦋

  1. The K' source symbols C'[0], C'[1], ..., C'[K'-1] satisfy the K' constraints:
C'[X] = Enc[K', (C[0], ..., C[L-1]), (d[X], a[X], b[X], d1[X],
a1[X], b1[X])], for all X, 0 <= X < K',

where (d[X], a[X], b[X], d1[X], a1[X], b1[X])) = Tuple[K',X], Tuple[] is defined in Section 5.3.5.4, and Enc[] is described in Section 5.3.5.3.

  1. The L intermediate symbols C[0], C[1], ..., C[L-1] satisfy the pre-coding relationships defined in Section 5.3.3.3.

5.3.3.4.2. Example Method for Calculation of Intermediate Symbols

this section is a possible method for working out the L intermediate symbols C[0], C[1], ..., C[L-1] that satisfy the constraints in Section 5.3.3.4.1 🌸

Here's the setup. Let:

  • C denote the column vector of the L intermediate symbols, C[0], C[1], ..., C[L-1].
  • D denote the column vector made of S+H zero symbols followed by the K' source symbols C'[0], C'[1], ..., C'[K'-1].

Then the above constraints define an L x L matrix A of octets such that:

A*C = D

The matrix A can be built like this. Let:

  • G_LDPC,1 and G_LDPC,2 be S x B and S x P matrices as defined in Section 5.3.3.3.
  • G_HDPC be the H x (K'+S) matrix such that:
G_HDPC * Transpose(C[0], ..., C[K'+S-1]) = Transpose(C[K'+S],
..., C[L-1]),

i.e., G_HDPC = MT*GAMMA

  • I_S be the S x S identity matrix.
  • I_H be the H x H identity matrix.
  • G_ENC be the K' x L matrix such that:
G_ENC * Transpose[(C[0], ..., C[L-1])] =
Transpose[(C'[0],C'[1], ...,C'[K'-1])],

i.e., G_ENC[i,j] = 1 if and only if C[j] is included in the symbols that are summed to produce Enc[K', (C[0], ..., C[L-1]), (d[i], a[i], b[i], d1[i], a1[i], b1[i])], and G_ENC[i,j] = 0 otherwise.

Then:

  • The first S rows of A are equal to G_LDPC,1 | I_S | G_LDPC,2.
  • The next H rows of A are equal to G_HDPC | I_H.
  • The remaining K' rows of A are equal to G_ENC.

Here's the picture of matrix A, Figure 5 🎀

                   B               S         U         H
        +-----------------------+-------+------------------+
        |                       |       |                  |
      S |        G_LDPC,1       |  I_S  |      G_LDPC,2    |
        |                       |       |                  |
        +-----------------------+-------+----------+-------+
        |                                          |       |
      H |                G_HDPC                    |  I_H  |
        |                                          |       |
        +------------------------------------------+-------+
        |                                                  |
        |                                                  |
     K' |                      G_ENC                       |
        |                                                  |
        |                                                  |
        +--------------------------------------------------+

                         Figure 5: The Matrix A

The intermediate symbols can then be calculated as:

C = (A^^-1)*D

The source tuples are generated so that, for any K', matrix A has full rank and is therefore invertible 🔥 This calculation can be done by applying a RaptorQ decoding process to the K' source symbols C'[0], C'[1], ..., C'[K'-1] to produce the L intermediate symbols C[0], C[1], ..., C[L-1].

To generate the intermediate symbols from the source symbols efficiently, it is recommended that an efficient decoder implementation, such as the one described in Section 5.4, be used 🧚

5.3.4. Second Encoding Step: Encoding

in the second encoding step, the repair symbol with ISI X (X >= K') is generated by applying the generator Enc[K', (C[0], C[1], ..., C[L-1]), (d, a, b, d1, a1, b1)], defined in Section 5.3.5.3, to the L intermediate symbols C[0], C[1], ..., C[L-1] using the tuple (d, a, b, d1, a1, b1)=Tuple[K',X] 💖

5.3.5. Generators

5.3.5.1. Random Number Generator

the random number generator Rand[y, i, m] works like this, where y is a non-negative integer, i is a non-negative integer less than 256, and m is a positive integer. The value it produces is an integer between 0 and m-1 🌈 Let V0, V1, V2, and V3 be the arrays provided in Section 5.5.

Let:

  • x0 = (y + i) mod 2^^8
  • x1 = (floor(y / 2^^8) + i) mod 2^^8
  • x2 = (floor(y / 2^^16) + i) mod 2^^8
  • x3 = (floor(y / 2^^24) + i) mod 2^^8

Then:

Rand[y, i, m] = (V0[x0] ^ V1[x1] ^ V2[x2] ^ V3[x3]) % m

5.3.5.2. Degree Generator

the degree generator Deg[v] is defined as follows, where v is a non-negative integer less than 2^^20 = 1048576 ✨ Given v, find index d in Table 1 such that f[d-1] <= v < f[d], and set Deg[v] = min(d, W-2). Remember that W is derived from K' as described in Section 5.3.3.3 🌸

+---------+---------+---------+---------+
| Index d | f[d]    | Index d | f[d]    |
+---------+---------+---------+---------+
| 0       | 0       | 1       | 5243    |
+---------+---------+---------+---------+
| 2       | 529531  | 3       | 704294  |
+---------+---------+---------+---------+
| 4       | 791675  | 5       | 844104  |
+---------+---------+---------+---------+
| 6       | 879057  | 7       | 904023  |
+---------+---------+---------+---------+
| 8       | 922747  | 9       | 937311  |
+---------+---------+---------+---------+
| 10      | 948962  | 11      | 958494  |
+---------+---------+---------+---------+
| 12      | 966438  | 13      | 973160  |
+---------+---------+---------+---------+
| 14      | 978921  | 15      | 983914  |
+---------+---------+---------+---------+
| 16      | 988283  | 17      | 992138  |
+---------+---------+---------+---------+
| 18      | 995565  | 19      | 998631  |
+---------+---------+---------+---------+
| 20      | 1001391 | 21      | 1003887 |
+---------+---------+---------+---------+
| 22      | 1006157 | 23      | 1008229 |
+---------+---------+---------+---------+
| 24      | 1010129 | 25      | 1011876 |
+---------+---------+---------+---------+
| 26      | 1013490 | 27      | 1014983 |
+---------+---------+---------+---------+
| 28      | 1016370 | 29      | 1017662 |
+---------+---------+---------+---------+
| 30      | 1048576 |         |         |
+---------+---------+---------+---------+

Table 1: Defines the Degree Distribution for Encoding Symbols 🦋

5.3.5.3. Encoding Symbol Generator ✨

Okay so this is where an encoding symbol actually gets cooked 🍳 The encoding symbol generator is written Enc[K', (C[0], C[1], ..., C[L-1]), (d, a, b, d1, a1, b1)], and it takes three inputs:

  • K' is the number of source symbols for the extended source block. Derive L, W, B, S, P, and P1 from K' as described in Section 5.3.3.3. 💅
  • (C[0], C[1], ..., C[L-1]) is the array of L intermediate symbols (sub-symbols) generated as described in Section 5.3.3.4. 🦋
  • (d, a, b, d1, a1, b1) is a source tuple figured out from ISI X using the Tuple[] generator from Section 5.3.5.4. The tuple breaks down like this:
    • d is a positive integer denoting an encoding symbol LT degree
    • a is a positive integer between 1 and W-1 inclusive
    • b is a non-negative integer between 0 and W-1 inclusive
    • d1 is a positive integer that has value either 2 or 3, denoting an encoding symbol PI degree
    • a1 is a positive integer between 1 and P1-1 inclusive
    • b1 is a non-negative integer between 0 and P1-1 inclusive

The generator produces one encoding symbol as output (called result) using this algorithm, and it's giving main character energy 👑

result = C[b]
For j = 1, ..., d-1 do
  b = (b + a) % W
  result = result + C[b]
While (b1 >= P) do b1 = (b1+a1) % P1
result = result + C[W+b1]
For j = 1, ..., d1-1 do
  b1 = (b1 + a1) % P1
  While (b1 >= P) do b1 = (b1+a1) % P1
  result = result + C[W+b1]
Return result

5.3.5.4. Tuple Generator 🎀

Now the tuple generator 🧚 It's written Tuple[K',X] and takes two inputs:

  • K': the number of source symbols in the extended source block
  • X: an ISI

Along the way we set:

  • L is determined from K' as described in Section 5.3.3.3
  • J = J(K') is the systematic index associated with K', as defined in Table 2 in Section 5.6

The tuple generator's output is a tuple, (d, a, b, d1, a1, b1), and it gets worked out like this:

A = 53591 + J*997
if (A % 2 == 0) { A = A + 1 }
B = 10267*(J+1)
y = (B + X*A) % 2^^32
v = Rand[y, 0, 2^^20]
d = Deg[v]
a = 1 + Rand[y, 1, W-1]
b = Rand[y, 2, W]
If (d < 4) { d1 = 2 + Rand[X, 3, 2] } else { d1 = 2 }
a1 = 1 + Rand[X, 4, P1-1]
b1 = Rand[X, 5, P1]

5.4. Example FEC Decoder 🌈

5.4.1. General 🔥

Okay, this section walks through an efficient way to decode the RaptorQ code introduced in this specification. Here's the key vibe: every encoding symbol you receive is a known linear combination of the intermediate symbols. So each one gives you a linear equation among the intermediate symbols. Combine those with the known pre-coding relationships between the intermediate symbols and you get a full system of linear equations 🧮 That means any algorithm for solving linear equations can decode the intermediate symbols, and therefore the source symbols. ngl, though, the algorithm you pick makes a huge difference in how fast decoding goes 💀

5.4.2. Decoding an Extended Source Block 💖

5.4.2.1. General ✨

So the decoder is assumed to know the structure of the source block it's decoding. That includes the symbol size T, the number K of symbols in the source block, and the number K' of source symbols in the extended source block.

From the algorithms in Section 5.3, the RaptorQ decoder can work out the total number of intermediate symbols, L = K'+S+H, and figure out how they were generated from the extended source block. In this description, the received encoding symbols for the extended source block get passed to the decoder. For each one, the number and set of intermediate symbols that sum to that encoding symbol also get passed in. For source symbols (padding symbols included), the source symbol tuples from Section 5.3.3.2 tell you the number and set of intermediate symbols that sum to each source symbol. 🫶

Let N >= K' be the number of received encoding symbols used for decoding, padding symbols for an extended source block included, and let M = S+H+N. Then, using the notation of Section 5.3.3.4.2, we have A*C = D.

Decoding an extended source block is the same as decoding C from known A and D. It's clear that C can be decoded if and only if the rank of A is L. Once C is decoded, any missing source symbols can be found by using the source symbol tuples to determine the number and set of intermediate symbols that must be summed to get each missing one. 🦋

The first step in decoding C is forming a decoding schedule. Here, A gets converted using Gaussian elimination (row operations plus row and column reorderings), and after discarding M - L rows, it becomes the L x L identity matrix. The decoding schedule is the sequence of row operations and row and column reorderings during that elimination, and it only depends on A, not on D. 📋

Decoding C from D can happen at the same time as forming the decoding schedule, or it can happen afterwards, based on the schedule. 🌸

Here's how the decoding schedule lines up with decoding C. Start with c[0] = 0, c[1] = 1, ..., c[L-1] = L-1 and d[0] = 0, d[1] = 1, ..., d[M-1] = M-1.

  • Each time a multiple, beta, of row i of A is added to row i' in the decoding schedule, the decoding process adds the symbol beta*D[d[i]] to symbol D[d[i']].
  • Each time a row i of A is multiplied by an octet beta, the decoding process also multiplies the symbol D[d[i]] by beta.
  • Each time row i is exchanged with row i' in the decoding schedule, the value of d[i] is exchanged with the value of d[i'] in the decoding process.
  • Each time column j is exchanged with column j' in the decoding schedule, the value of c[j] is exchanged with the value of c[j'].

From this mapping, it's clear that the total number of operations on symbols while decoding the extended source block equals the number of row operations (not exchanges) in the Gaussian elimination. 🔥 Since A is the L x L identity matrix after elimination and after discarding the last M - L rows, it's clear that at the end of successful decoding, the L symbols D[d[0]], D[d[1]], ..., D[d[L-1]] are the values of the L symbols C[c[0]], C[c[1]], ..., C[c[L-1]]. 👑

The order in which Gaussian elimination happens to form the decoding schedule has no bearing on whether decoding succeeds. BUT the speed of decoding depends heavily on that order 😭 (And keeping a sparse representation of A is crucial too, although that isn't described here.) The rest of this section describes an order for Gaussian elimination that is relatively efficient 🍓

5.4.2.2. First Phase ✨

okay bestie, the first phase of Gaussian elimination is where the magic starts 🦋 we conceptually split the matrix A into submatrices, and we also make a brand new matrix X. X has as many rows and columns as A, and it stays lower triangular the whole way through this phase. right at the start, A gets copied into X 💖

the submatrix sizes are controlled by two non-negative integers, i and u. i starts at 0, and u starts at P, which is the number of PI symbols 🌸 the submatrices of A are:

  1. the submatrix I, made from the intersection of the first i rows and first i columns. at the end of each step in this phase it's the identity matrix ✨
  2. the submatrix made from the intersection of the first i rows and all but the first i columns and last u columns. every entry in here is zero 🫶
  3. the submatrix made from the intersection of the first i columns and all but the first i rows. every entry in here is zero too 💅
  4. the submatrix U, made from the intersection of all the rows and the last u columns 👑
  5. the submatrix V, formed by the intersection of all but the first i columns and the last u columns and all but the first i rows 🔥

check out Figure 6 for the vibe. at the start of the first phase, V is the first L-P columns of A, and U is the last P columns, the ones for the PI symbols 🎀 in each step, we pick a row of A.

           +-----------+-----------------+---------+
           |           |                 |         |
           |     I     |    All Zeros    |         |
           |           |                 |         |
           +-----------+-----------------+    U    |
           |           |                 |         |
           |           |                 |         |
           | All Zeros |       V         |         |
           |           |                 |         |
           |           |                 |         |
           +-----------+-----------------+---------+

Figure 6: Submatrices of A in the First Phase

now here's the graph that V defines, which decides which row of A we choose 🧚 the columns that cross V are the nodes, and the rows that have exactly 2 nonzero entries in V and are not HDPC rows are the edges connecting the two columns sitting at the two ones 🌈 a component is a maximal set of nodes (columns) and edges (rows) where there's a path between every pair of nodes and edges in the graph. the size of a component is just the number of nodes (columns) in it 💜

there are at most L steps in this phase. the phase ends successfully when i + u = L, which means V and the all zeros submatrix above V have vanished, and A is just I, the all zeros submatrix below I, and U 🥳 the phase ends unsuccessfully in decoding failure if, at some step before V disappears, there's no nonzero row in V to choose 💀 in each step, a row of A gets picked like this:

  • if all entries of V are zero, then no row gets chosen and decoding fails 😭
  • let r be the minimum integer such that at least one row of A has exactly r nonzeros in V.
    • if r != 2, then choose a row with exactly r nonzeros in V that has the minimum original degree among all such rows, except that HDPC rows should not be chosen until all non-HDPC rows have been processed 🙈
    • if r = 2 and there is a row with exactly 2 ones in V, then choose any row with exactly 2 ones in V that is part of a maximum size component in the graph described above, the one defined by V ✨
    • if r = 2 and there is no row with exactly 2 ones in V, then choose any row with exactly 2 nonzeros in V 🍓

once the row is chosen, the first row of A that intersects V gets swapped with the chosen row, so the chosen row becomes the first row that intersects V 🦋 then the columns of A that intersect V get reordered. one of the r nonzeros in the chosen row lands in the first column of V, and the other r-1 nonzeros land in the last columns of V 💖 the exact same row and column operations also get done on X 🫶

next, an appropriate multiple of the chosen row gets added to all the other rows below it that have a nonzero entry in the first column of V 💅 specifically, if a row below the chosen row has entry beta in the first column of V, and the chosen row has entry alpha in that same column, then beta/alpha multiplied by the chosen row gets added to that row, which leaves a zero in the first column of V 👑 finally, i goes up by 1 and u goes up by r-1, and that wraps up the step 🎀

ngl there's a glow-up trick here 🌸 the row operations above don't have to actually happen until the affected row is itself chosen during decoding. this skips processing row operations for rows that never get used in the decoding, and in particular it avoids those rows where beta!=1 until they're actually needed 🔥 also, the row operations for the HDPC rows can be done for all of those rows in one go, using the algorithm in Section 5.3.3.3 ✨

5.4.2.3. Second Phase 🫧

okay now, all the entries of X outside the first i rows and i columns get tossed, so X is lower triangular 💅 the last i rows and columns of X get tossed too, so X ends up with i rows and i columns. then the submatrix U gets split into its first i rows, called U_upper, and the remaining M - i rows, called U_lower 🦋

Gaussian elimination runs on U_lower in this phase. it either figures out that its rank is less than u (decoding failure), or it turns it into a matrix where the first u rows are the identity matrix (success for this phase) 🌈 we call that u x u identity matrix I_u. the M - L rows of A that intersect U_lower - I_u get discarded 🗑️ after this phase, A has L rows and L columns, and it's giving clean 💖

5.4.2.4. Third Phase 🧚

after the second phase, the only part of A that still needs zeroing out to turn A into the L x L identity matrix is U_upper 🎀 the number of rows i in U_upper is usually way bigger than the number of columns u, and at this point U_upper is typically dense, meaning it has lots of nonzero entries 😭 to make it sparse, we need to invert the sequence of operations we used to get U_lower 🫶 so the matrix X gets multiplied with the submatrix of A made from the first i rows of A 💜 after that, the submatrix of A made from the intersection of the first i rows and columns equals X, and U_upper is now in sparse form ✨

5.4.2.5. Fourth Phase 💅

for each of the first i rows of U_upper, here's the move: if the row has a nonzero entry at position j, and that entry has value b, then add b times row j of I_u to this row 🔥 after this step, the submatrix of A made from the intersection of the first i rows and columns is equal to X. U_upper is all zeros, the submatrix made from the intersection of the last u rows and the first i columns is all zeros, and the submatrix made from the last u rows and columns is I_u 👑

5.4.2.6. Fifth Phase 🌸

for j from 1 to i, do the following:

  1. if A[j,j] is not one, then divide row j of A by A[j,j] 🙈
  2. for l from 1 to j-1, if A[j,l] is nonzero, then add A[j,l] multiplied with row l of A to row j of A 🍓

after this phase, A is the L x L identity matrix, and a complete decoding schedule has been successfully formed 🥳 then the decoding, which means summing the known encoding symbols, can run to recover the intermediate symbols based on that decoding schedule ✨ the tuples for all source symbols are computed according to Section 5.3.3.2 💖 the tuples for the received source symbols get used in the decoding 🫶 and the tuples for the missing source symbols get used to figure out which intermediate symbols need to be summed to recover the missing source symbols 🦋

5.5. Random Numbers 🎲

the four arrays V0, V1, V2, and V3, which are used in Section 5.3.5.1, are given below 🧚 each array has 256 entries. the indexing into each array starts at 0, and the entries are 32-bit unsigned integers 💜

5.5.1. The Table V0 ✨

251291136, 3952231631, 3370958628, 4070167936, 123631495,
3351110283, 3218676425, 2011642291, 774603218, 2402805061,
1004366930, 1843948209, 428891132, 3746331984, 1591258008,
3067016507, 1433388735, 504005498, 2032657933, 3419319784,
2805686246, 3102436986, 3808671154, 2501582075, 3978944421,
246043949, 4016898363, 649743608, 1974987508, 2651273766,
2357956801, 689605112, 715807172, 2722736134, 191939188,
3535520147, 3277019569, 1470435941, 3763101702, 3232409631,
122701163, 3920852693, 782246947, 372121310, 2995604341,
2045698575, 2332962102, 4005368743, 218596347, 3415381967,
4207612806, 861117671, 3676575285, 2581671944, 3312220480,
681232419, 307306866, 4112503940, 1158111502, 709227802,
2724140433, 4201101115, 4215970289, 4048876515, 3031661061,
1909085522, 510985033, 1361682810, 129243379, 3142379587,
2569842483, 3033268270, 1658118006, 932109358, 1982290045,
2983082771, 3007670818, 3448104768, 683749698, 778296777,
1399125101, 1939403708, 1692176003, 3868299200, 1422476658,
593093658, 1878973865, 2526292949, 1591602827, 3986158854,
3964389521, 2695031039, 1942050155, 424618399, 1347204291,
2669179716, 2434425874, 2540801947, 1384069776, 4123580443,
1523670218, 2708475297, 1046771089, 2229796016, 1255426612,
4213663089, 1521339547, 3041843489, 420130494, 10677091,
515623176, 3457502702, 2115821274, 2720124766, 3242576090,
854310108, 425973987, 325832382, 1796851292, 2462744411,
1976681690, 1408671665, 1228817808, 3917210003, 263976645,
2593736473, 2471651269, 4291353919, 650792940, 1191583883,
3046561335, 2466530435, 2545983082, 969168436, 2019348792,
2268075521, 1169345068, 3250240009, 3963499681, 2560755113,
911182396, 760842409, 3569308693, 2687243553, 381854665,
2613828404, 2761078866, 1456668111, 883760091, 3294951678,
1604598575, 1985308198, 1014570543, 2724959607, 3062518035,
3115293053, 138853680, 4160398285, 3322241130, 2068983570,
2247491078, 3669524410, 1575146607, 828029864, 3732001371,
3422026452, 3370954177, 4006626915, 543812220, 1243116171,
3928372514, 2791443445, 4081325272, 2280435605, 885616073,
616452097, 3188863436, 2780382310, 2340014831, 1208439576,
258356309, 3837963200, 2075009450, 3214181212, 3303882142,
880813252, 1355575717, 207231484, 2420803184, 358923368,
1617557768, 3272161958, 1771154147, 2842106362, 1751209208,
1421030790, 658316681, 194065839, 3241510581, 38625260,
301875395, 4176141739, 297312930, 2137802113, 1502984205,
3669376622, 3728477036, 234652930, 2213589897, 2734638932,
1129721478, 3187422815, 2859178611, 3284308411, 3819792700,
3557526733, 451874476, 1740576081, 3592838701, 1709429513,
3702918379, 3533351328, 1641660745, 179350258, 2380520112,
3936163904, 3685256204, 3156252216, 1854258901, 2861641019,
3176611298, 834787554, 331353807, 517858103, 3010168884,
4012642001, 2217188075, 3756943137, 3077882590, 2054995199,
3081443129, 3895398812, 1141097543, 2376261053, 2626898255,
2554703076, 401233789, 1460049922, 678083952, 1064990737,
940909784, 1673396780, 528881783, 1712547446, 3629685652,
1358307511

5.5.2. The Table V1 💜

807385413, 2043073223, 3336749796, 1302105833, 2278607931,
541015020, 1684564270, 372709334, 3508252125, 1768346005,
1270451292, 2603029534, 2049387273, 3891424859, 2152948345,
4114760273, 915180310, 3754787998, 700503826, 2131559305,
1308908630, 224437350, 4065424007, 3638665944, 1679385496,
3431345226, 1779595665, 3068494238, 1424062773, 1033448464,
4050396853, 3302235057, 420600373, 2868446243, 311689386,
259047959, 4057180909, 1575367248, 4151214153, 110249784,
3006865921, 4293710613, 3501256572, 998007483, 499288295,
1205710710, 2997199489, 640417429, 3044194711, 486690751,
2686640734, 2394526209, 2521660077, 49993987, 3843885867,
4201106668, 415906198, 19296841, 2402488407, 2137119134,
1744097284, 579965637, 2037662632, 852173610, 2681403713,
1047144830, 2982173936, 910285038, 4187576520, 2589870048,
989448887, 3292758024, 506322719, 176010738, 1865471968,
2619324712, 564829442, 1996870325, 339697593, 4071072948,
3618966336, 2111320126, 1093955153, 957978696, 892010560,
1854601078, 1873407527, 2498544695, 2694156259, 1927339682,
1650555729, 183933047, 3061444337, 2067387204, 228962564,
3904109414, 1595995433, 1780701372, 2463145963, 307281463,
3237929991, 3852995239, 2398693510, 3754138664, 522074127,
146352474, 4104915256, 3029415884, 3545667983, 332038910,
976628269, 3123492423, 3041418372, 2258059298, 2139377204,
3243642973, 3226247917, 3674004636, 2698992189, 3453843574,
1963216666, 3509855005, 2358481858, 747331248, 1957348676,
1097574450, 2435697214, 3870972145, 1888833893, 2914085525,
4161315584, 1273113343, 3269644828, 3681293816, 412536684,
1156034077, 3823026442, 1066971017, 3598330293, 1979273937,
2079029895, 1195045909, 1071986421, 2712821515, 3377754595,
2184151095, 750918864, 2585729879, 4249895712, 1832579367,
1192240192, 946734366, 31230688, 3174399083, 3549375728,
1642430184, 1904857554, 861877404, 3277825584, 4267074718,
3122860549, 666423581, 644189126, 226475395, 307789415,
1196105631, 3191691839, 782852669, 1608507813, 1847685900,
4069766876, 3931548641, 2526471011, 766865139, 2115084288,
4259411376, 3323683436, 568512177, 3736601419, 1800276898,
4012458395, 1823982, 27980198, 2023839966, 869505096,
431161506, 1024804023, 1853869307, 3393537983, 1500703614,
3019471560, 1351086955, 3096933631, 3034634988, 2544598006,
1230942551, 3362230798, 159984793, 491590373, 3993872886,
3681855622, 903593547, 3535062472, 1799803217, 772984149,
895863112, 1899036275, 4187322100, 101856048, 234650315,
3183125617, 3190039692, 525584357, 1286834489, 455810374,
1869181575, 922673938, 3877430102, 3422391938, 1414347295,
1971054608, 3061798054, 830555096, 2822905141, 167033190,
1079139428, 4210126723, 3593797804, 429192890, 372093950,
1779187770, 3312189287, 204349348, 452421568, 2800540462,
3733109044, 1235082423, 1765319556, 3174729780, 3762994475,
3171962488, 442160826, 198349622, 45942637, 1324086311,
2901868599, 678860040, 3812229107, 19936821, 1119590141,
3640121682, 3545931032, 2102949142, 2828208598, 3603378023,
4135048896

5.5.3. The Table V2 🌸

1629829892, 282540176, 2794583710, 496504798, 2990494426,
3070701851, 2575963183, 4094823972, 2775723650, 4079480416,
176028725, 2246241423, 3732217647, 2196843075, 1306949278,
4170992780, 4039345809, 3209664269, 3387499533, 293063229,
3660290503, 2648440860, 2531406539, 3537879412, 773374739,
4184691853, 1804207821, 3347126643, 3479377103, 3970515774,
1891731298, 2368003842, 3537588307, 2969158410, 4230745262,
831906319, 2935838131, 264029468, 120852739, 3200326460,
355445271, 2296305141, 1566296040, 1760127056, 20073893,
3427103620, 2866979760, 2359075957, 2025314291, 1725696734,
3346087406, 2690756527, 99815156, 4248519977, 2253762642,
3274144518, 598024568, 3299672435, 556579346, 4121041856,
2896948975, 3620123492, 918453629, 3249461198, 2231414958,
3803272287, 3657597946, 2588911389, 242262274, 1725007475,
2026427718, 46776484, 2873281403, 2919275846, 3177933051,
1918859160, 2517854537, 1857818511, 3234262050, 479353687,
200201308, 2801945841, 1621715769, 483977159, 423502325,
3689396064, 1850168397, 3359959416, 3459831930, 841488699,
3570506095, 930267420, 1564520841, 2505122797, 593824107,
1116572080, 819179184, 3139123629, 1414339336, 1076360795,
512403845, 177759256, 1701060666, 2239736419, 515179302,
2935012727, 3821357612, 1376520851, 2700745271, 966853647,
1041862223, 715860553, 171592961, 1607044257, 1227236688,
3647136358, 1417559141, 4087067551, 2241705880, 4194136288,
1439041934, 20464430, 119668151, 2021257232, 2551262694,
1381539058, 4082839035, 498179069, 311508499, 3580908637,
2889149671, 142719814, 1232184754, 3356662582, 2973775623,
1469897084, 1728205304, 1415793613, 50111003, 3133413359,
4074115275, 2710540611, 2700083070, 2457757663, 2612845330,
3775943755, 2469309260, 2560142753, 3020996369, 1691667711,
4219602776, 1687672168, 1017921622, 2307642321, 368711460,
3282925988, 213208029, 4150757489, 3443211944, 2846101972,
4106826684, 4272438675, 2199416468, 3710621281, 497564971,
285138276, 765042313, 916220877, 3402623607, 2768784621,
1722849097, 3386397442, 487920061, 3569027007, 3424544196,
217781973, 2356938519, 3252429414, 145109750, 2692588106,
2454747135, 1299493354, 4120241887, 2088917094, 932304329,
1442609203, 952586974, 3509186750, 753369054, 854421006,
1954046388, 2708927882, 4047539230, 3048925996, 1667505809,
805166441, 1182069088, 4265546268, 4215029527, 3374748959,
373532666, 2454243090, 2371530493, 3651087521, 2619878153,
1651809518, 1553646893, 1227452842, 703887512, 3696674163,
2552507603, 2635912901, 895130484, 3287782244, 3098973502,
990078774, 3780326506, 2290845203, 41729428, 1949580860,
2283959805, 1036946170, 1694887523, 4880696, 466000198,
2765355283, 3318686998, 1266458025, 3919578154, 3545413527,
2627009988, 3744680394, 1696890173, 3250684705, 4142417708,
915739411, 3308488877, 1289361460, 2942552331, 1169105979,
3342228712, 698560958, 1356041230, 2401944293, 107705232,
3701895363, 903928723, 3646581385, 844950914, 1944371367,
3863894844, 2946773319, 1972431613, 1706989237, 29917467,
3497665928

5.5.4. The Table V3 🎀

Okay so this one is literally just a giant list of numbers, but they're the good kind of numbers 🔢💖 Here's the V3 table, copied exactly as the spec has it:

      1191369816, 744902811, 2539772235, 3213192037, 3286061266,
      1200571165, 2463281260, 754888894, 714651270, 1968220972,
      3628497775, 1277626456, 1493398934, 364289757, 2055487592,
      3913468088, 2930259465, 902504567, 3967050355, 2056499403,
      692132390, 186386657, 832834706, 859795816, 1283120926,
      2253183716, 3003475205, 1755803552, 2239315142, 4271056352,
      2184848469, 769228092, 1249230754, 1193269205, 2660094102,
      642979613, 1687087994, 2726106182, 446402913, 4122186606,
      3771347282, 37667136, 192775425, 3578702187, 1952659096,
      3989584400, 3069013882, 2900516158, 4045316336, 3057163251,
      1702104819, 4116613420, 3575472384, 2674023117, 1409126723,
      3215095429, 1430726429, 2544497368, 1029565676, 1855801827,
      4262184627, 1854326881, 2906728593, 3277836557, 2787697002,
      2787333385, 3105430738, 2477073192, 748038573, 1088396515,
      1611204853, 201964005, 3745818380, 3654683549, 3816120877,
      3915783622, 2563198722, 1181149055, 33158084, 3723047845,
      3790270906, 3832415204, 2959617497, 372900708, 1286738499,
      1932439099, 3677748309, 2454711182, 2757856469, 2134027055,
      2780052465, 3190347618, 3758510138, 3626329451, 1120743107,
      1623585693, 1389834102, 2719230375, 3038609003, 462617590,
      260254189, 3706349764, 2556762744, 2874272296, 2502399286,
      4216263978, 2683431180, 2168560535, 3561507175, 668095726,
      680412330, 3726693946, 4180630637, 3335170953, 942140968,
      2711851085, 2059233412, 4265696278, 3204373534, 232855056,
      881788313, 2258252172, 2043595984, 3758795150, 3615341325,
      2138837681, 1351208537, 2923692473, 3402482785, 2105383425,
      2346772751, 499245323, 3417846006, 2366116814, 2543090583,
      1828551634, 3148696244, 3853884867, 1364737681, 2200687771,
      2689775688, 232720625, 4071657318, 2671968983, 3531415031,
      1212852141, 867923311, 3740109711, 1923146533, 3237071777,
      3100729255, 3247856816, 906742566, 4047640575, 4007211572,
      3495700105, 1171285262, 2835682655, 1634301229, 3115169925,
      2289874706, 2252450179, 944880097, 371933491, 1649074501,
      2208617414, 2524305981, 2496569844, 2667037160, 1257550794,
      3399219045, 3194894295, 1643249887, 342911473, 891025733,
      3146861835, 3789181526, 938847812, 1854580183, 2112653794,
      2960702988, 1238603378, 2205280635, 1666784014, 2520274614,
      3355493726, 2310872278, 3153920489, 2745882591, 1200203158,
      3033612415, 2311650167, 1048129133, 4206710184, 4209176741,
      2640950279, 2096382177, 4116899089, 3631017851, 4104488173,
      1857650503, 3801102932, 445806934, 3055654640, 897898279,
      3234007399, 1325494930, 2982247189, 1619020475, 2720040856,
      885096170, 3485255499, 2983202469, 3891011124, 546522756,
      1524439205, 2644317889, 2170076800, 2969618716, 961183518,
      1081831074, 1037015347, 3289016286, 2331748669, 620887395,
      303042654, 3990027945, 1562756376, 3413341792, 2059647769,
      2823844432, 674595301, 2457639984, 4076754716, 2447737904,
      1583323324, 625627134, 3076006391, 345777990, 1684954145,
      879227329, 3436182180, 1522273219, 3802543817, 1456017040,
      1897819847, 2970081129, 1382576028, 3820044861, 1044428167,
      612252599, 3340478395, 2150613904, 3397625662, 3573635640,
      3432275192

5.6. Systematic Indices and Other Parameters 💅

Okay, next up is Table 2! It lists the supported values of K' ✨ and, for each one, shows the systematic index J(K'), the number H(K') of HDPC symbols, the number S(K') of LDPC symbols, and the number W(K') of LT symbols. Lowkey the important bit is that for every K', the S(K') and W(K') values are prime numbers 🧚

The systematic index J(K') is designed so that the source symbol tuples (d[0], a[0], b[0], d1[0], a1[0], b1[0]), ..., (d[K'-1], a[K'-1], b[K'-1], d1[K'-1], a1[K'-1], b1[K'-1]) give you a set where the L intermediate symbols are uniquely defined 🦋 In other words, the matrix A in Figure 6 has full rank, so it's invertible. Iconic behaviour, honestly 👑

Okay so the table keeps going, bestie 🎀 Here's the rest of the K' lineup, every row exactly as it is ✨

                 +-------+-------+-------+-------+-------+
                 | K'    | J(K') | S(K') | H(K') | W(K') |
                 +-------+-------+-------+-------+-------+
                 | 10    | 254   | 7     | 10    | 17    |
                 +-------+-------+-------+-------+-------+
                 | 12    | 630   | 7     | 10    | 19    |
                 +-------+-------+-------+-------+-------+
                 | 18    | 682   | 11    | 10    | 29    |
                 +-------+-------+-------+-------+-------+
                 | 20    | 293   | 11    | 10    | 31    |
                 +-------+-------+-------+-------+-------+
                 | 26    | 80    | 11    | 10    | 37    |
                 +-------+-------+-------+-------+-------+
                 | 30    | 566   | 11    | 10    | 41    |
                 +-------+-------+-------+-------+-------+
                 | 32    | 860   | 11    | 10    | 43    |
                 +-------+-------+-------+-------+-------+
                 | 36    | 267   | 11    | 10    | 47    |
                 +-------+-------+-------+-------+-------+
                 | 42    | 822   | 11    | 10    | 53    |
                 +-------+-------+-------+-------+-------+
                 | 46    | 506   | 13    | 10    | 59    |
                 +-------+-------+-------+-------+-------+
                 | 48    | 589   | 13    | 10    | 61    |
                 +-------+-------+-------+-------+-------+
                 | 49    | 87    | 13    | 10    | 61    |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 55    | 520   | 13    | 10    | 67    |
                 +-------+-------+-------+-------+-------+
                 | 60    | 159   | 13    | 10    | 71    |
                 +-------+-------+-------+-------+-------+
                 | 62    | 235   | 13    | 10    | 73    |
                 +-------+-------+-------+-------+-------+
                 | 69    | 157   | 13    | 10    | 79    |
                 +-------+-------+-------+-------+-------+
                 | 75    | 502   | 17    | 10    | 89    |
                 +-------+-------+-------+-------+-------+
                 | 84    | 334   | 17    | 10    | 97    |
                 +-------+-------+-------+-------+-------+
                 | 88    | 583   | 17    | 10    | 101   |
                 +-------+-------+-------+-------+-------+
                 | 91    | 66    | 17    | 10    | 103   |
                 +-------+-------+-------+-------+-------+
                 | 95    | 352   | 17    | 10    | 107   |
                 +-------+-------+-------+-------+-------+
                 | 97    | 365   | 17    | 10    | 109   |
                 +-------+-------+-------+-------+-------+
                 | 101   | 562   | 17    | 10    | 113   |
                 +-------+-------+-------+-------+-------+
                 | 114   | 5     | 19    | 10    | 127   |
                 +-------+-------+-------+-------+-------+
                 | 119   | 603   | 19    | 10    | 131   |
                 +-------+-------+-------+-------+-------+
                 | 125   | 721   | 19    | 10    | 137   |
                 +-------+-------+-------+-------+-------+
                 | 127   | 28    | 19    | 10    | 139   |
                 +-------+-------+-------+-------+-------+
                 | 138   | 660   | 19    | 10    | 149   |
                 +-------+-------+-------+-------+-------+
                 | 140   | 829   | 19    | 10    | 151   |
                 +-------+-------+-------+-------+-------+
                 | 149   | 900   | 23    | 10    | 163   |
                 +-------+-------+-------+-------+-------+
                 | 153   | 930   | 23    | 10    | 167   |
                 +-------+-------+-------+-------+-------+
                 | 160   | 814   | 23    | 10    | 173   |
                 +-------+-------+-------+-------+-------+
                 | 166   | 661   | 23    | 10    | 179   |
                 +-------+-------+-------+-------+-------+
                 | 168   | 693   | 23    | 10    | 181   |
                 +-------+-------+-------+-------+-------+
                 | 179   | 780   | 23    | 10    | 191   |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 181   | 605   | 23    | 10    | 193   |
                 +-------+-------+-------+-------+-------+
                 | 185   | 551   | 23    | 10    | 197   |
                 +-------+-------+-------+-------+-------+
                 | 187   | 777   | 23    | 10    | 199   |
                 +-------+-------+-------+-------+-------+
                 | 200   | 491   | 23    | 10    | 211   |
                 +-------+-------+-------+-------+-------+
                 | 213   | 396   | 23    | 10    | 223   |
                 +-------+-------+-------+-------+-------+
                 | 217   | 764   | 29    | 10    | 233   |
                 +-------+-------+-------+-------+-------+
                 | 225   | 843   | 29    | 10    | 241   |
                 +-------+-------+-------+-------+-------+
                 | 236   | 646   | 29    | 10    | 251   |
                 +-------+-------+-------+-------+-------+
                 | 242   | 557   | 29    | 10    | 257   |
                 +-------+-------+-------+-------+-------+
                 | 248   | 608   | 29    | 10    | 263   |
                 +-------+-------+-------+-------+-------+
                 | 257   | 265   | 29    | 10    | 271   |
                 +-------+-------+-------+-------+-------+
                 | 263   | 505   | 29    | 10    | 277   |
                 +-------+-------+-------+-------+-------+
                 | 269   | 722   | 29    | 10    | 283   |
                 +-------+-------+-------+-------+-------+
                 | 280   | 263   | 29    | 10    | 293   |
                 +-------+-------+-------+-------+-------+
                 | 295   | 999   | 29    | 10    | 307   |
                 +-------+-------+-------+-------+-------+
                 | 301   | 874   | 29    | 10    | 313   |
                 +-------+-------+-------+-------+-------+
                 | 305   | 160   | 29    | 10    | 317   |
                 +-------+-------+-------+-------+-------+
                 | 324   | 575   | 31    | 10    | 337   |
                 +-------+-------+-------+-------+-------+
                 | 337   | 210   | 31    | 10    | 349   |
                 +-------+-------+-------+-------+-------+
                 | 341   | 513   | 31    | 10    | 353   |
                 +-------+-------+-------+-------+-------+
                 | 347   | 503   | 31    | 10    | 359   |
                 +-------+-------+-------+-------+-------+
                 | 355   | 558   | 31    | 10    | 367   |
                 +-------+-------+-------+-------+-------+
                 | 362   | 932   | 31    | 10    | 373   |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 368   | 404   | 31    | 10    | 379   |
                 +-------+-------+-------+-------+-------+
                 | 372   | 520   | 37    | 10    | 389   |
                 +-------+-------+-------+-------+-------+
                 | 380   | 846   | 37    | 10    | 397   |
                 +-------+-------+-------+-------+-------+
                 | 385   | 485   | 37    | 10    | 401   |
                 +-------+-------+-------+-------+-------+
                 | 393   | 728   | 37    | 10    | 409   |
                 +-------+-------+-------+-------+-------+
                 | 405   | 554   | 37    | 10    | 421   |
                 +-------+-------+-------+-------+-------+
                 | 418   | 471   | 37    | 10    | 433   |
                 +-------+-------+-------+-------+-------+
                 | 428   | 641   | 37    | 10    | 443   |
                 +-------+-------+-------+-------+-------+
                 | 434   | 732   | 37    | 10    | 449   |
                 +-------+-------+-------+-------+-------+
                 | 447   | 193   | 37    | 10    | 461   |
                 +-------+-------+-------+-------+-------+
                 | 453   | 934   | 37    | 10    | 467   |
                 +-------+-------+-------+-------+-------+
                 | 466   | 864   | 37    | 10    | 479   |
                 +-------+-------+-------+-------+-------+
                 | 478   | 790   | 37    | 10    | 491   |
                 +-------+-------+-------+-------+-------+
                 | 486   | 912   | 37    | 10    | 499   |
                 +-------+-------+-------+-------+-------+
                 | 491   | 617   | 37    | 10    | 503   |
                 +-------+-------+-------+-------+-------+
                 | 497   | 587   | 37    | 10    | 509   |
                 +-------+-------+-------+-------+-------+
                 | 511   | 800   | 37    | 10    | 523   |
                 +-------+-------+-------+-------+-------+
                 | 526   | 923   | 41    | 10    | 541   |
                 +-------+-------+-------+-------+-------+
                 | 532   | 998   | 41    | 10    | 547   |
                 +-------+-------+-------+-------+-------+
                 | 542   | 92    | 41    | 10    | 557   |
                 +-------+-------+-------+-------+-------+
                 | 549   | 497   | 41    | 10    | 563   |
                 +-------+-------+-------+-------+-------+
                 | 557   | 559   | 41    | 10    | 571   |
                 +-------+-------+-------+-------+-------+
                 | 563   | 667   | 41    | 10    | 577   |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 573   | 912   | 41    | 10    | 587   |
                 +-------+-------+-------+-------+-------+
                 | 580   | 262   | 41    | 10    | 593   |
                 +-------+-------+-------+-------+-------+
                 | 588   | 152   | 41    | 10    | 601   |
                 +-------+-------+-------+-------+-------+
                 | 594   | 526   | 41    | 10    | 607   |
                 +-------+-------+-------+-------+-------+
                 | 600   | 268   | 41    | 10    | 613   |
                 +-------+-------+-------+-------+-------+
                 | 606   | 212   | 41    | 10    | 619   |
                 +-------+-------+-------+-------+-------+
                 | 619   | 45    | 41    | 10    | 631   |
                 +-------+-------+-------+-------+-------+
                 | 633   | 898   | 43    | 10    | 647   |
                 +-------+-------+-------+-------+-------+
                 | 640   | 527   | 43    | 10    | 653   |
                 +-------+-------+-------+-------+-------+
                 | 648   | 558   | 43    | 10    | 661   |
                 +-------+-------+-------+-------+-------+
                 | 666   | 460   | 47    | 10    | 683   |
                 +-------+-------+-------+-------+-------+
                 | 675   | 5     | 47    | 10    | 691   |
                 +-------+-------+-------+-------+-------+
                 | 685   | 895   | 47    | 10    | 701   |
                 +-------+-------+-------+-------+-------+
                 | 693   | 996   | 47    | 10    | 709   |
                 +-------+-------+-------+-------+-------+
                 | 703   | 282   | 47    | 10    | 719   |
                 +-------+-------+-------+-------+-------+
                 | 718   | 513   | 47    | 10    | 733   |
                 +-------+-------+-------+-------+-------+
                 | 728   | 865   | 47    | 10    | 743   |
                 +-------+-------+-------+-------+-------+

okay bestie, the table keeps going and it's giving pure math drama 🧮💖

                 | 736   | 870   | 47    | 10    | 751   |
                 +-------+-------+-------+-------+-------+
                 | 747   | 239   | 47    | 10    | 761   |
                 +-------+-------+-------+-------+-------+
                 | 759   | 452   | 47    | 10    | 773   |
                 +-------+-------+-------+-------+-------+
                 | 778   | 862   | 53    | 10    | 797   |
                 +-------+-------+-------+-------+-------+
                 | 792   | 852   | 53    | 10    | 811   |
                 +-------+-------+-------+-------+-------+
                 | 802   | 643   | 53    | 10    | 821   |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 811   | 543   | 53    | 10    | 829   |
                 +-------+-------+-------+-------+-------+
                 | 821   | 447   | 53    | 10    | 839   |
                 +-------+-------+-------+-------+-------+
                 | 835   | 321   | 53    | 10    | 853   |
                 +-------+-------+-------+-------+-------+
                 | 845   | 287   | 53    | 10    | 863   |
                 +-------+-------+-------+-------+-------+
                 | 860   | 12    | 53    | 10    | 877   |
                 +-------+-------+-------+-------+-------+
                 | 870   | 251   | 53    | 10    | 887   |
                 +-------+-------+-------+-------+-------+
                 | 891   | 30    | 53    | 10    | 907   |
                 +-------+-------+-------+-------+-------+
                 | 903   | 621   | 53    | 10    | 919   |
                 +-------+-------+-------+-------+-------+
                 | 913   | 555   | 53    | 10    | 929   |
                 +-------+-------+-------+-------+-------+
                 | 926   | 127   | 53    | 10    | 941   |
                 +-------+-------+-------+-------+-------+
                 | 938   | 400   | 53    | 10    | 953   |
                 +-------+-------+-------+-------+-------+
                 | 950   | 91    | 59    | 10    | 971   |
                 +-------+-------+-------+-------+-------+
                 | 963   | 916   | 59    | 10    | 983   |
                 +-------+-------+-------+-------+-------+
                 | 977   | 935   | 59    | 10    | 997   |
                 +-------+-------+-------+-------+-------+
                 | 989   | 691   | 59    | 10    | 1009  |
                 +-------+-------+-------+-------+-------+
                 | 1002  | 299   | 59    | 10    | 1021  |
                 +-------+-------+-------+-------+-------+
                 | 1020  | 282   | 59    | 10    | 1039  |
                 +-------+-------+-------+-------+-------+
                 | 1032  | 824   | 59    | 10    | 1051  |
                 +-------+-------+-------+-------+-------+
                 | 1050  | 536   | 59    | 11    | 1069  |
                 +-------+-------+-------+-------+-------+
                 | 1074  | 596   | 59    | 11    | 1093  |
                 +-------+-------+-------+-------+-------+
                 | 1085  | 28    | 59    | 11    | 1103  |
                 +-------+-------+-------+-------+-------+
                 | 1099  | 947   | 59    | 11    | 1117  |
                 +-------+-------+-------+-------+-------+
                 | 1111  | 162   | 59    | 11    | 1129  |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 1136  | 536   | 59    | 11    | 1153  |
                 +-------+-------+-------+-------+-------+
                 | 1152  | 1000  | 61    | 11    | 1171  |
                 +-------+-------+-------+-------+-------+
                 | 1169  | 251   | 61    | 11    | 1187  |
                 +-------+-------+-------+-------+-------+
                 | 1183  | 673   | 61    | 11    | 1201  |
                 +-------+-------+-------+-------+-------+
                 | 1205  | 559   | 61    | 11    | 1223  |
                 +-------+-------+-------+-------+-------+
                 | 1220  | 923   | 61    | 11    | 1237  |
                 +-------+-------+-------+-------+-------+
                 | 1236  | 81    | 67    | 11    | 1259  |
                 +-------+-------+-------+-------+-------+
                 | 1255  | 478   | 67    | 11    | 1277  |
                 +-------+-------+-------+-------+-------+
                 | 1269  | 198   | 67    | 11    | 1291  |
                 +-------+-------+-------+-------+-------+
                 | 1285  | 137   | 67    | 11    | 1307  |
                 +-------+-------+-------+-------+-------+
                 | 1306  | 75    | 67    | 11    | 1327  |
                 +-------+-------+-------+-------+-------+
                 | 1347  | 29    | 67    | 11    | 1367  |
                 +-------+-------+-------+-------+-------+
                 | 1361  | 231   | 67    | 11    | 1381  |
                 +-------+-------+-------+-------+-------+
                 | 1389  | 532   | 67    | 11    | 1409  |
                 +-------+-------+-------+-------+-------+
                 | 1404  | 58    | 67    | 11    | 1423  |
                 +-------+-------+-------+-------+-------+
                 | 1420  | 60    | 67    | 11    | 1439  |
                 +-------+-------+-------+-------+-------+
                 | 1436  | 964   | 71    | 11    | 1459  |
                 +-------+-------+-------+-------+-------+
                 | 1461  | 624   | 71    | 11    | 1483  |
                 +-------+-------+-------+-------+-------+
                 | 1477  | 502   | 71    | 11    | 1499  |
                 +-------+-------+-------+-------+-------+
                 | 1502  | 636   | 71    | 11    | 1523  |
                 +-------+-------+-------+-------+-------+
                 | 1522  | 986   | 71    | 11    | 1543  |
                 +-------+-------+-------+-------+-------+
                 | 1539  | 950   | 71    | 11    | 1559  |
                 +-------+-------+-------+-------+-------+
                 | 1561  | 735   | 73    | 11    | 1583  |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 1579  | 866   | 73    | 11    | 1601  |
                 +-------+-------+-------+-------+-------+
                 | 1600  | 203   | 73    | 11    | 1621  |
                 +-------+-------+-------+-------+-------+
                 | 1616  | 83    | 73    | 11    | 1637  |
                 +-------+-------+-------+-------+-------+
                 | 1649  | 14    | 73    | 11    | 1669  |
                 +-------+-------+-------+-------+-------+
                 | 1673  | 522   | 79    | 11    | 1699  |
                 +-------+-------+-------+-------+-------+
                 | 1698  | 226   | 79    | 11    | 1723  |
                 +-------+-------+-------+-------+-------+
                 | 1716  | 282   | 79    | 11    | 1741  |
                 +-------+-------+-------+-------+-------+
                 | 1734  | 88    | 79    | 11    | 1759  |
                 +-------+-------+-------+-------+-------+
                 | 1759  | 636   | 79    | 11    | 1783  |
                 +-------+-------+-------+-------+-------+
                 | 1777  | 860   | 79    | 11    | 1801  |
                 +-------+-------+-------+-------+-------+
                 | 1800  | 324   | 79    | 11    | 1823  |
                 +-------+-------+-------+-------+-------+
                 | 1824  | 424   | 79    | 11    | 1847  |
                 +-------+-------+-------+-------+-------+
                 | 1844  | 999   | 79    | 11    | 1867  |
                 +-------+-------+-------+-------+-------+
                 | 1863  | 682   | 83    | 11    | 1889  |
                 +-------+-------+-------+-------+-------+
                 | 1887  | 814   | 83    | 11    | 1913  |
                 +-------+-------+-------+-------+-------+
                 | 1906  | 979   | 83    | 11    | 1931  |
                 +-------+-------+-------+-------+-------+
                 | 1926  | 538   | 83    | 11    | 1951  |
                 +-------+-------+-------+-------+-------+
                 | 1954  | 278   | 83    | 11    | 1979  |
                 +-------+-------+-------+-------+-------+
                 | 1979  | 580   | 83    | 11    | 2003  |
                 +-------+-------+-------+-------+-------+
                 | 2005  | 773   | 83    | 11    | 2029  |
                 +-------+-------+-------+-------+-------+
                 | 2040  | 911   | 89    | 11    | 2069  |
                 +-------+-------+-------+-------+-------+
                 | 2070  | 506   | 89    | 11    | 2099  |
                 +-------+-------+-------+-------+-------+
                 | 2103  | 628   | 89    | 11    | 2131  |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 2125  | 282   | 89    | 11    | 2153  |
                 +-------+-------+-------+-------+-------+
                 | 2152  | 309   | 89    | 11    | 2179  |
                 +-------+-------+-------+-------+-------+
                 | 2195  | 858   | 89    | 11    | 2221  |
                 +-------+-------+-------+-------+-------+
                 | 2217  | 442   | 89    | 11    | 2243  |
                 +-------+-------+-------+-------+-------+
                 | 2247  | 654   | 89    | 11    | 2273  |
                 +-------+-------+-------+-------+-------+
                 | 2278  | 82    | 97    | 11    | 2311  |
                 +-------+-------+-------+-------+-------+
                 | 2315  | 428   | 97    | 11    | 2347  |
                 +-------+-------+-------+-------+-------+
                 | 2339  | 442   | 97    | 11    | 2371  |
                 +-------+-------+-------+-------+-------+
                 | 2367  | 283   | 97    | 11    | 2399  |
                 +-------+-------+-------+-------+-------+
                 | 2392  | 538   | 97    | 11    | 2423  |
                 +-------+-------+-------+-------+-------+
                 | 2416  | 189   | 97    | 11    | 2447  |
                 +-------+-------+-------+-------+-------+
                 | 2447  | 438   | 97    | 11    | 2477  |
                 +-------+-------+-------+-------+-------+
                 | 2473  | 912   | 97    | 11    | 2503  |
                 +-------+-------+-------+-------+-------+
                 | 2502  | 1     | 97    | 11    | 2531  |
                 +-------+-------+-------+-------+-------+
                 | 2528  | 167   | 97    | 11    | 2557  |
                 +-------+-------+-------+-------+-------+
                 | 2565  | 272   | 97    | 11    | 2593  |
                 +-------+-------+-------+-------+-------+
                 | 2601  | 209   | 101   | 11    | 2633  |
                 +-------+-------+-------+-------+-------+
                 | 2640  | 927   | 101   | 11    | 2671  |
                 +-------+-------+-------+-------+-------+
                 | 2668  | 386   | 101   | 11    | 2699  |
                 +-------+-------+-------+-------+-------+
                 | 2701  | 653   | 101   | 11    | 2731  |
                 +-------+-------+-------+-------+-------+
                 | 2737  | 669   | 101   | 11    | 2767  |
                 +-------+-------+-------+-------+-------+
                 | 2772  | 431   | 101   | 11    | 2801  |
                 +-------+-------+-------+-------+-------+
                 | 2802  | 793   | 103   | 11    | 2833  |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 2831  | 588   | 103   | 11    | 2861  |
                 +-------+-------+-------+-------+-------+

Okay bestie, the table keeps going and it's giving pattern 🦋✨ Every row is a fresh little combo of numbers, so here we go 💖

                 | 2875  | 777   | 107   | 11    | 2909  |
                 +-------+-------+-------+-------+-------+
                 | 2906  | 939   | 107   | 11    | 2939  |
                 +-------+-------+-------+-------+-------+
                 | 2938  | 864   | 107   | 11    | 2971  |
                 +-------+-------+-------+-------+-------+
                 | 2979  | 627   | 107   | 11    | 3011  |
                 +-------+-------+-------+-------+-------+
                 | 3015  | 265   | 109   | 11    | 3049  |
                 +-------+-------+-------+-------+-------+
                 | 3056  | 976   | 109   | 11    | 3089  |
                 +-------+-------+-------+-------+-------+
                 | 3101  | 988   | 113   | 11    | 3137  |
                 +-------+-------+-------+-------+-------+
                 | 3151  | 507   | 113   | 11    | 3187  |
                 +-------+-------+-------+-------+-------+
                 | 3186  | 640   | 113   | 11    | 3221  |
                 +-------+-------+-------+-------+-------+
                 | 3224  | 15    | 113   | 11    | 3259  |
                 +-------+-------+-------+-------+-------+
                 | 3265  | 667   | 113   | 11    | 3299  |
                 +-------+-------+-------+-------+-------+
                 | 3299  | 24    | 127   | 11    | 3347  |
                 +-------+-------+-------+-------+-------+
                 | 3344  | 877   | 127   | 11    | 3391  |
                 +-------+-------+-------+-------+-------+
                 | 3387  | 240   | 127   | 11    | 3433  |
                 +-------+-------+-------+-------+-------+
                 | 3423  | 720   | 127   | 11    | 3469  |
                 +-------+-------+-------+-------+-------+
                 | 3466  | 93    | 127   | 11    | 3511  |
                 +-------+-------+-------+-------+-------+
                 | 3502  | 919   | 127   | 11    | 3547  |
                 +-------+-------+-------+-------+-------+
                 | 3539  | 635   | 127   | 11    | 3583  |
                 +-------+-------+-------+-------+-------+
                 | 3579  | 174   | 127   | 11    | 3623  |
                 +-------+-------+-------+-------+-------+
                 | 3616  | 647   | 127   | 11    | 3659  |
                 +-------+-------+-------+-------+-------+
                 | 3658  | 820   | 127   | 11    | 3701  |
                 +-------+-------+-------+-------+-------+
                 | 3697  | 56    | 127   | 11    | 3739  |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 3751  | 485   | 127   | 11    | 3793  |
                 +-------+-------+-------+-------+-------+
                 | 3792  | 210   | 127   | 11    | 3833  |
                 +-------+-------+-------+-------+-------+
                 | 3840  | 124   | 127   | 11    | 3881  |
                 +-------+-------+-------+-------+-------+
                 | 3883  | 546   | 127   | 11    | 3923  |
                 +-------+-------+-------+-------+-------+
                 | 3924  | 954   | 131   | 11    | 3967  |
                 +-------+-------+-------+-------+-------+
                 | 3970  | 262   | 131   | 11    | 4013  |
                 +-------+-------+-------+-------+-------+
                 | 4015  | 927   | 131   | 11    | 4057  |
                 +-------+-------+-------+-------+-------+
                 | 4069  | 957   | 131   | 11    | 4111  |
                 +-------+-------+-------+-------+-------+
                 | 4112  | 726   | 137   | 11    | 4159  |
                 +-------+-------+-------+-------+-------+
                 | 4165  | 583   | 137   | 11    | 4211  |
                 +-------+-------+-------+-------+-------+
                 | 4207  | 782   | 137   | 11    | 4253  |
                 +-------+-------+-------+-------+-------+
                 | 4252  | 37    | 137   | 11    | 4297  |
                 +-------+-------+-------+-------+-------+
                 | 4318  | 758   | 137   | 11    | 4363  |
                 +-------+-------+-------+-------+-------+
                 | 4365  | 777   | 137   | 11    | 4409  |
                 +-------+-------+-------+-------+-------+
                 | 4418  | 104   | 139   | 11    | 4463  |
                 +-------+-------+-------+-------+-------+
                 | 4468  | 476   | 139   | 11    | 4513  |
                 +-------+-------+-------+-------+-------+
                 | 4513  | 113   | 149   | 11    | 4567  |
                 +-------+-------+-------+-------+-------+
                 | 4567  | 313   | 149   | 11    | 4621  |
                 +-------+-------+-------+-------+-------+
                 | 4626  | 102   | 149   | 11    | 4679  |
                 +-------+-------+-------+-------+-------+
                 | 4681  | 501   | 149   | 11    | 4733  |
                 +-------+-------+-------+-------+-------+
                 | 4731  | 332   | 149   | 11    | 4783  |
                 +-------+-------+-------+-------+-------+
                 | 4780  | 786   | 149   | 11    | 4831  |
                 +-------+-------+-------+-------+-------+
                 | 4838  | 99    | 149   | 11    | 4889  |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 4901  | 658   | 149   | 11    | 4951  |
                 +-------+-------+-------+-------+-------+
                 | 4954  | 794   | 149   | 11    | 5003  |
                 +-------+-------+-------+-------+-------+
                 | 5008  | 37    | 151   | 11    | 5059  |
                 +-------+-------+-------+-------+-------+
                 | 5063  | 471   | 151   | 11    | 5113  |
                 +-------+-------+-------+-------+-------+
                 | 5116  | 94    | 157   | 11    | 5171  |
                 +-------+-------+-------+-------+-------+
                 | 5172  | 873   | 157   | 11    | 5227  |
                 +-------+-------+-------+-------+-------+
                 | 5225  | 918   | 157   | 11    | 5279  |
                 +-------+-------+-------+-------+-------+
                 | 5279  | 945   | 157   | 11    | 5333  |
                 +-------+-------+-------+-------+-------+
                 | 5334  | 211   | 157   | 11    | 5387  |
                 +-------+-------+-------+-------+-------+
                 | 5391  | 341   | 157   | 11    | 5443  |
                 +-------+-------+-------+-------+-------+
                 | 5449  | 11    | 163   | 11    | 5507  |
                 +-------+-------+-------+-------+-------+
                 | 5506  | 578   | 163   | 11    | 5563  |
                 +-------+-------+-------+-------+-------+
                 | 5566  | 494   | 163   | 11    | 5623  |
                 +-------+-------+-------+-------+-------+
                 | 5637  | 694   | 163   | 11    | 5693  |
                 +-------+-------+-------+-------+-------+
                 | 5694  | 252   | 163   | 11    | 5749  |
                 +-------+-------+-------+-------+-------+
                 | 5763  | 451   | 167   | 11    | 5821  |
                 +-------+-------+-------+-------+-------+
                 | 5823  | 83    | 167   | 11    | 5881  |
                 +-------+-------+-------+-------+-------+
                 | 5896  | 689   | 167   | 11    | 5953  |
                 +-------+-------+-------+-------+-------+
                 | 5975  | 488   | 173   | 11    | 6037  |
                 +-------+-------+-------+-------+-------+
                 | 6039  | 214   | 173   | 11    | 6101  |
                 +-------+-------+-------+-------+-------+
                 | 6102  | 17    | 173   | 11    | 6163  |
                 +-------+-------+-------+-------+-------+
                 | 6169  | 469   | 173   | 11    | 6229  |
                 +-------+-------+-------+-------+-------+
                 | 6233  | 263   | 179   | 11    | 6299  |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 6296  | 309   | 179   | 11    | 6361  |
                 +-------+-------+-------+-------+-------+
                 | 6363  | 984   | 179   | 11    | 6427  |
                 +-------+-------+-------+-------+-------+
                 | 6427  | 123   | 179   | 11    | 6491  |
                 +-------+-------+-------+-------+-------+
                 | 6518  | 360   | 179   | 11    | 6581  |
                 +-------+-------+-------+-------+-------+
                 | 6589  | 863   | 181   | 11    | 6653  |
                 +-------+-------+-------+-------+-------+
                 | 6655  | 122   | 181   | 11    | 6719  |
                 +-------+-------+-------+-------+-------+
                 | 6730  | 522   | 191   | 11    | 6803  |
                 +-------+-------+-------+-------+-------+
                 | 6799  | 539   | 191   | 11    | 6871  |
                 +-------+-------+-------+-------+-------+
                 | 6878  | 181   | 191   | 11    | 6949  |
                 +-------+-------+-------+-------+-------+
                 | 6956  | 64    | 191   | 11    | 7027  |
                 +-------+-------+-------+-------+-------+
                 | 7033  | 387   | 191   | 11    | 7103  |
                 +-------+-------+-------+-------+-------+
                 | 7108  | 967   | 191   | 11    | 7177  |
                 +-------+-------+-------+-------+-------+
                 | 7185  | 843   | 191   | 11    | 7253  |
                 +-------+-------+-------+-------+-------+
                 | 7281  | 999   | 193   | 11    | 7351  |
                 +-------+-------+-------+-------+-------+
                 | 7360  | 76    | 197   | 11    | 7433  |
                 +-------+-------+-------+-------+-------+
                 | 7445  | 142   | 197   | 11    | 7517  |
                 +-------+-------+-------+-------+-------+
                 | 7520  | 599   | 197   | 11    | 7591  |
                 +-------+-------+-------+-------+-------+
                 | 7596  | 576   | 199   | 11    | 7669  |
                 +-------+-------+-------+-------+-------+
                 | 7675  | 176   | 211   | 11    | 7759  |
                 +-------+-------+-------+-------+-------+
                 | 7770  | 392   | 211   | 11    | 7853  |
                 +-------+-------+-------+-------+-------+
                 | 7855  | 332   | 211   | 11    | 7937  |
                 +-------+-------+-------+-------+-------+
                 | 7935  | 291   | 211   | 11    | 8017  |
                 +-------+-------+-------+-------+-------+
                 | 8030  | 913   | 211   | 11    | 8111  |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 8111  | 608   | 211   | 11    | 8191  |
                 +-------+-------+-------+-------+-------+
                 | 8194  | 212   | 211   | 11    | 8273  |
                 +-------+-------+-------+-------+-------+
                 | 8290  | 696   | 211   | 11    | 8369  |
                 +-------+-------+-------+-------+-------+
                 | 8377  | 931   | 223   | 11    | 8467  |
                 +-------+-------+-------+-------+-------+
                 | 8474  | 326   | 223   | 11    | 8563  |
                 +-------+-------+-------+-------+-------+
                 | 8559  | 228   | 223   | 11    | 8647  |
                 +-------+-------+-------+-------+-------+
                 | 8654  | 706   | 223   | 11    | 8741  |
                 +-------+-------+-------+-------+-------+
                 | 8744  | 144   | 223   | 11    | 8831  |
                 +-------+-------+-------+-------+-------+
                 | 8837  | 83    | 223   | 11    | 8923  |

Okay bestie, here's the next chunk of the table, and it's giving a lot of numbers 🧚💅

                 +-------+-------+-------+-------+-------+
                 | 8928  | 743   | 223   | 11    | 9013  |
                 +-------+-------+-------+-------+-------+
                 | 9019  | 187   | 223   | 11    | 9103  |
                 +-------+-------+-------+-------+-------+
                 | 9111  | 654   | 227   | 11    | 9199  |
                 +-------+-------+-------+-------+-------+
                 | 9206  | 359   | 227   | 11    | 9293  |
                 +-------+-------+-------+-------+-------+
                 | 9303  | 493   | 229   | 11    | 9391  |
                 +-------+-------+-------+-------+-------+
                 | 9400  | 369   | 233   | 11    | 9491  |
                 +-------+-------+-------+-------+-------+
                 | 9497  | 981   | 233   | 11    | 9587  |
                 +-------+-------+-------+-------+-------+
                 | 9601  | 276   | 239   | 11    | 9697  |
                 +-------+-------+-------+-------+-------+
                 | 9708  | 647   | 239   | 11    | 9803  |
                 +-------+-------+-------+-------+-------+
                 | 9813  | 389   | 239   | 11    | 9907  |
                 +-------+-------+-------+-------+-------+
                 | 9916  | 80    | 239   | 11    | 10009 |
                 +-------+-------+-------+-------+-------+
                 | 10017 | 396   | 241   | 11    | 10111 |
                 +-------+-------+-------+-------+-------+
                 | 10120 | 580   | 251   | 11    | 10223 |
                 +-------+-------+-------+-------+-------+
                 | 10241 | 873   | 251   | 11    | 10343 |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 10351 | 15    | 251   | 11    | 10453 |
                 +-------+-------+-------+-------+-------+
                 | 10458 | 976   | 251   | 11    | 10559 |
                 +-------+-------+-------+-------+-------+
                 | 10567 | 584   | 251   | 11    | 10667 |
                 +-------+-------+-------+-------+-------+
                 | 10676 | 267   | 257   | 11    | 10781 |
                 +-------+-------+-------+-------+-------+
                 | 10787 | 876   | 257   | 11    | 10891 |
                 +-------+-------+-------+-------+-------+
                 | 10899 | 642   | 257   | 12    | 11003 |
                 +-------+-------+-------+-------+-------+
                 | 11015 | 794   | 257   | 12    | 11119 |
                 +-------+-------+-------+-------+-------+
                 | 11130 | 78    | 263   | 12    | 11239 |
                 +-------+-------+-------+-------+-------+
                 | 11245 | 736   | 263   | 12    | 11353 |
                 +-------+-------+-------+-------+-------+
                 | 11358 | 882   | 269   | 12    | 11471 |
                 +-------+-------+-------+-------+-------+
                 | 11475 | 251   | 269   | 12    | 11587 |
                 +-------+-------+-------+-------+-------+
                 | 11590 | 434   | 269   | 12    | 11701 |
                 +-------+-------+-------+-------+-------+
                 | 11711 | 204   | 269   | 12    | 11821 |
                 +-------+-------+-------+-------+-------+
                 | 11829 | 256   | 271   | 12    | 11941 |
                 +-------+-------+-------+-------+-------+
                 | 11956 | 106   | 277   | 12    | 12073 |
                 +-------+-------+-------+-------+-------+
                 | 12087 | 375   | 277   | 12    | 12203 |
                 +-------+-------+-------+-------+-------+
                 | 12208 | 148   | 277   | 12    | 12323 |
                 +-------+-------+-------+-------+-------+
                 | 12333 | 496   | 281   | 12    | 12451 |
                 +-------+-------+-------+-------+-------+
                 | 12460 | 88    | 281   | 12    | 12577 |
                 +-------+-------+-------+-------+-------+
                 | 12593 | 826   | 293   | 12    | 12721 |
                 +-------+-------+-------+-------+-------+
                 | 12726 | 71    | 293   | 12    | 12853 |
                 +-------+-------+-------+-------+-------+
                 | 12857 | 925   | 293   | 12    | 12983 |
                 +-------+-------+-------+-------+-------+
                 | 13002 | 760   | 293   | 12    | 13127 |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 13143 | 130   | 293   | 12    | 13267 |
                 +-------+-------+-------+-------+-------+
                 | 13284 | 641   | 307   | 12    | 13421 |
                 +-------+-------+-------+-------+-------+
                 | 13417 | 400   | 307   | 12    | 13553 |
                 +-------+-------+-------+-------+-------+
                 | 13558 | 480   | 307   | 12    | 13693 |
                 +-------+-------+-------+-------+-------+
                 | 13695 | 76    | 307   | 12    | 13829 |
                 +-------+-------+-------+-------+-------+
                 | 13833 | 665   | 307   | 12    | 13967 |
                 +-------+-------+-------+-------+-------+
                 | 13974 | 910   | 307   | 12    | 14107 |
                 +-------+-------+-------+-------+-------+
                 | 14115 | 467   | 311   | 12    | 14251 |
                 +-------+-------+-------+-------+-------+
                 | 14272 | 964   | 311   | 12    | 14407 |
                 +-------+-------+-------+-------+-------+
                 | 14415 | 625   | 313   | 12    | 14551 |
                 +-------+-------+-------+-------+-------+
                 | 14560 | 362   | 317   | 12    | 14699 |
                 +-------+-------+-------+-------+-------+
                 | 14713 | 759   | 317   | 12    | 14851 |
                 +-------+-------+-------+-------+-------+
                 | 14862 | 728   | 331   | 12    | 15013 |
                 +-------+-------+-------+-------+-------+
                 | 15011 | 343   | 331   | 12    | 15161 |
                 +-------+-------+-------+-------+-------+
                 | 15170 | 113   | 331   | 12    | 15319 |
                 +-------+-------+-------+-------+-------+
                 | 15325 | 137   | 331   | 12    | 15473 |
                 +-------+-------+-------+-------+-------+
                 | 15496 | 308   | 331   | 12    | 15643 |
                 +-------+-------+-------+-------+-------+
                 | 15651 | 800   | 337   | 12    | 15803 |
                 +-------+-------+-------+-------+-------+
                 | 15808 | 177   | 337   | 12    | 15959 |
                 +-------+-------+-------+-------+-------+
                 | 15977 | 961   | 337   | 12    | 16127 |
                 +-------+-------+-------+-------+-------+
                 | 16161 | 958   | 347   | 12    | 16319 |
                 +-------+-------+-------+-------+-------+
                 | 16336 | 72    | 347   | 12    | 16493 |
                 +-------+-------+-------+-------+-------+
                 | 16505 | 732   | 347   | 12    | 16661 |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 16674 | 145   | 349   | 12    | 16831 |
                 +-------+-------+-------+-------+-------+
                 | 16851 | 577   | 353   | 12    | 17011 |
                 +-------+-------+-------+-------+-------+
                 | 17024 | 305   | 353   | 12    | 17183 |
                 +-------+-------+-------+-------+-------+
                 | 17195 | 50    | 359   | 12    | 17359 |
                 +-------+-------+-------+-------+-------+
                 | 17376 | 351   | 359   | 12    | 17539 |
                 +-------+-------+-------+-------+-------+
                 | 17559 | 175   | 367   | 12    | 17729 |
                 +-------+-------+-------+-------+-------+
                 | 17742 | 727   | 367   | 12    | 17911 |
                 +-------+-------+-------+-------+-------+
                 | 17929 | 902   | 367   | 12    | 18097 |
                 +-------+-------+-------+-------+-------+
                 | 18116 | 409   | 373   | 12    | 18289 |
                 +-------+-------+-------+-------+-------+
                 | 18309 | 776   | 373   | 12    | 18481 |
                 +-------+-------+-------+-------+-------+
                 | 18503 | 586   | 379   | 12    | 18679 |
                 +-------+-------+-------+-------+-------+
                 | 18694 | 451   | 379   | 12    | 18869 |
                 +-------+-------+-------+-------+-------+
                 | 18909 | 287   | 383   | 12    | 19087 |
                 +-------+-------+-------+-------+-------+
                 | 19126 | 246   | 389   | 12    | 19309 |
                 +-------+-------+-------+-------+-------+
                 | 19325 | 222   | 389   | 12    | 19507 |
                 +-------+-------+-------+-------+-------+
                 | 19539 | 563   | 397   | 12    | 19727 |
                 +-------+-------+-------+-------+-------+
                 | 19740 | 839   | 397   | 12    | 19927 |
                 +-------+-------+-------+-------+-------+
                 | 19939 | 897   | 401   | 12    | 20129 |
                 +-------+-------+-------+-------+-------+
                 | 20152 | 409   | 401   | 12    | 20341 |
                 +-------+-------+-------+-------+-------+
                 | 20355 | 618   | 409   | 12    | 20551 |
                 +-------+-------+-------+-------+-------+
                 | 20564 | 439   | 409   | 12    | 20759 |
                 +-------+-------+-------+-------+-------+
                 | 20778 | 95    | 419   | 13    | 20983 |
                 +-------+-------+-------+-------+-------+
                 | 20988 | 448   | 419   | 13    | 21191 |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 21199 | 133   | 419   | 13    | 21401 |
                 +-------+-------+-------+-------+-------+
                 | 21412 | 938   | 419   | 13    | 21613 |
                 +-------+-------+-------+-------+-------+
                 | 21629 | 423   | 431   | 13    | 21841 |
                 +-------+-------+-------+-------+-------+
                 | 21852 | 90    | 431   | 13    | 22063 |
                 +-------+-------+-------+-------+-------+
                 | 22073 | 640   | 431   | 13    | 22283 |
                 +-------+-------+-------+-------+-------+
                 | 22301 | 922   | 433   | 13    | 22511 |
                 +-------+-------+-------+-------+-------+
                 | 22536 | 250   | 439   | 13    | 22751 |
                 +-------+-------+-------+-------+-------+
                 | 22779 | 367   | 439   | 13    | 22993 |
                 +-------+-------+-------+-------+-------+
                 | 23010 | 447   | 443   | 13    | 23227 |
                 +-------+-------+-------+-------+-------+
                 | 23252 | 559   | 449   | 13    | 23473 |
                 +-------+-------+-------+-------+-------+
                 | 23491 | 121   | 457   | 13    | 23719 |
                 +-------+-------+-------+-------+-------+
                 | 23730 | 623   | 457   | 13    | 23957 |
                 +-------+-------+-------+-------+-------+
                 | 23971 | 450   | 457   | 13    | 24197 |
                 +-------+-------+-------+-------+-------+
                 | 24215 | 253   | 461   | 13    | 24443 |
                 +-------+-------+-------+-------+-------+
                 | 24476 | 106   | 467   | 13    | 24709 |
                 +-------+-------+-------+-------+-------+
                 | 24721 | 863   | 467   | 13    | 24953 |
                 +-------+-------+-------+-------+-------+
                 | 24976 | 148   | 479   | 13    | 25219 |
                 +-------+-------+-------+-------+-------+
                 | 25230 | 427   | 479   | 13    | 25471 |
                 +-------+-------+-------+-------+-------+
                 | 25493 | 138   | 479   | 13    | 25733 |
                 +-------+-------+-------+-------+-------+
                 | 25756 | 794   | 487   | 13    | 26003 |
                 +-------+-------+-------+-------+-------+
                 | 26022 | 247   | 487   | 13    | 26267 |
                 +-------+-------+-------+-------+-------+
                 | 26291 | 562   | 491   | 13    | 26539 |
                 +-------+-------+-------+-------+-------+
                 | 26566 | 53    | 499   | 13    | 26821 |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 26838 | 135   | 499   | 13    | 27091 |
                 +-------+-------+-------+-------+-------+
                 | 27111 | 21    | 503   | 13    | 27367 |
                 +-------+-------+-------+-------+-------+
                 | 27392 | 201   | 509   | 13    | 27653 |
                 +-------+-------+-------+-------+-------+
                 | 27682 | 169   | 521   | 13    | 27953 |
                 +-------+-------+-------+-------+-------+
                 | 27959 | 70    | 521   | 13    | 28229 |
                 +-------+-------+-------+-------+-------+
                 | 28248 | 386   | 521   | 13    | 28517 |
                 +-------+-------+-------+-------+-------+
                 | 28548 | 226   | 523   | 13    | 28817 |
                 +-------+-------+-------+-------+-------+
                 | 28845 | 3     | 541   | 13    | 29131 |
                 +-------+-------+-------+-------+-------+
                 | 29138 | 769   | 541   | 13    | 29423 |
                 +-------+-------+-------+-------+-------+
                 | 29434 | 590   | 541   | 13    | 29717 |
                 +-------+-------+-------+-------+-------+
                 | 29731 | 672   | 541   | 13    | 30013 |
                 +-------+-------+-------+-------+-------+
                 | 30037 | 713   | 547   | 13    | 30323 |
                 +-------+-------+-------+-------+-------+
                 | 30346 | 967   | 547   | 13    | 30631 |
                 +-------+-------+-------+-------+-------+
                 | 30654 | 368   | 557   | 14    | 30949 |
                 +-------+-------+-------+-------+-------+
                 | 30974 | 348   | 557   | 14    | 31267 |
                 +-------+-------+-------+-------+-------+
                 | 31285 | 119   | 563   | 14    | 31583 |
                 +-------+-------+-------+-------+-------+
                 | 31605 | 503   | 569   | 14    | 31907 |
                 +-------+-------+-------+-------+-------+
                 | 31948 | 181   | 571   | 14    | 32251 |
                 +-------+-------+-------+-------+-------+
                 | 32272 | 394   | 577   | 14    | 32579 |
                 +-------+-------+-------+-------+-------+
                 | 32601 | 189   | 587   | 14    | 32917 |
                 +-------+-------+-------+-------+-------+
                 | 32932 | 210   | 587   | 14    | 33247 |
                 +-------+-------+-------+-------+-------+
                 | 33282 | 62    | 593   | 14    | 33601 |
                 +-------+-------+-------+-------+-------+
                 | 33623 | 273   | 593   | 14    | 33941 |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 33961 | 554   | 599   | 14    | 34283 |
                 +-------+-------+-------+-------+-------+
                 | 34302 | 936   | 607   | 14    | 34631 |
                 +-------+-------+-------+-------+-------+
                 | 34654 | 483   | 607   | 14    | 34981 |
                 +-------+-------+-------+-------+-------+
                 | 35031 | 397   | 613   | 14    | 35363 |
                 +-------+-------+-------+-------+-------+
                 | 35395 | 241   | 619   | 14    | 35731 |
                 +-------+-------+-------+-------+-------+
                 | 35750 | 500   | 631   | 14    | 36097 |
                 +-------+-------+-------+-------+-------+
                 | 36112 | 12    | 631   | 14    | 36457 |
                 +-------+-------+-------+-------+-------+
                 | 36479 | 958   | 641   | 14    | 36833 |
                 +-------+-------+-------+-------+-------+
                 | 36849 | 524   | 641   | 14    | 37201 |
                 +-------+-------+-------+-------+-------+
                 | 37227 | 8     | 643   | 14    | 37579 |
                 +-------+-------+-------+-------+-------+
                 | 37606 | 100   | 653   | 14    | 37967 |
                 +-------+-------+-------+-------+-------+
                 | 37992 | 339   | 653   | 14    | 38351 |
                 +-------+-------+-------+-------+-------+
                 | 38385 | 804   | 659   | 14    | 38749 |
                 +-------+-------+-------+-------+-------+
                 | 38787 | 510   | 673   | 14    | 39163 |
                 +-------+-------+-------+-------+-------+
                 | 39176 | 18    | 673   | 14    | 39551 |
                 +-------+-------+-------+-------+-------+
                 | 39576 | 412   | 677   | 14    | 39953 |
                 +-------+-------+-------+-------+-------+
                 | 39980 | 394   | 683   | 14    | 40361 |
                 +-------+-------+-------+-------+-------+
                 | 40398 | 830   | 691   | 15    | 40787 |
                 +-------+-------+-------+-------+-------+
                 | 40816 | 535   | 701   | 15    | 41213 |
                 +-------+-------+-------+-------+-------+
                 | 41226 | 199   | 701   | 15    | 41621 |
                 +-------+-------+-------+-------+-------+
                 | 41641 | 27    | 709   | 15    | 42043 |
                 +-------+-------+-------+-------+-------+
                 | 42067 | 298   | 709   | 15    | 42467 |
                 +-------+-------+-------+-------+-------+
                 | 42490 | 368   | 719   | 15    | 42899 |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 42916 | 755   | 727   | 15    | 43331 |
                 +-------+-------+-------+-------+-------+
                 | 43388 | 379   | 727   | 15    | 43801 |
                 +-------+-------+-------+-------+-------+
                 | 43840 | 73    | 733   | 15    | 44257 |
                 +-------+-------+-------+-------+-------+
                 | 44279 | 387   | 739   | 15    | 44701 |
                 +-------+-------+-------+-------+-------+
                 | 44729 | 457   | 751   | 15    | 45161 |
                 +-------+-------+-------+-------+-------+
                 | 45183 | 761   | 751   | 15    | 45613 |
                 +-------+-------+-------+-------+-------+
                 | 45638 | 855   | 757   | 15    | 46073 |
                 +-------+-------+-------+-------+-------+
                 | 46104 | 370   | 769   | 15    | 46549 |
                 +-------+-------+-------+-------+-------+
                 | 46574 | 261   | 769   | 15    | 47017 |
                 +-------+-------+-------+-------+-------+
                 | 47047 | 299   | 787   | 15    | 47507 |
                 +-------+-------+-------+-------+-------+
                 | 47523 | 920   | 787   | 15    | 47981 |
                 +-------+-------+-------+-------+-------+
                 | 48007 | 269   | 787   | 15    | 48463 |
                 +-------+-------+-------+-------+-------+
                 | 48489 | 862   | 797   | 15    | 48953 |
                 +-------+-------+-------+-------+-------+
                 | 48976 | 349   | 809   | 15    | 49451 |
                 +-------+-------+-------+-------+-------+
                 | 49470 | 103   | 809   | 15    | 49943 |
                 +-------+-------+-------+-------+-------+
                 | 49978 | 115   | 821   | 15    | 50461 |
                 +-------+-------+-------+-------+-------+
                 | 50511 | 93    | 821   | 16    | 50993 |
                 +-------+-------+-------+-------+-------+
                 | 51017 | 982   | 827   | 16    | 51503 |
                 +-------+-------+-------+-------+-------+
                 | 51530 | 432   | 839   | 16    | 52027 |
                 +-------+-------+-------+-------+-------+
                 | 52062 | 340   | 853   | 16    | 52571 |
                 +-------+-------+-------+-------+-------+
                 | 52586 | 173   | 853   | 16    | 53093 |
                 +-------+-------+-------+-------+-------+
                 | 53114 | 421   | 857   | 16    | 53623 |
                 +-------+-------+-------+-------+-------+
                 | 53650 | 330   | 863   | 16    | 54163 |
                 +-------+-------+-------+-------+-------+
                 +-------+-------+-------+-------+-------+
                 | 54188 | 624   | 877   | 16    | 54713 |
                 +-------+-------+-------+-------+-------+
                 | 54735 | 233   | 877   | 16    | 55259 |
                 +-------+-------+-------+-------+-------+
                 | 55289 | 362   | 883   | 16    | 55817 |
                 +-------+-------+-------+-------+-------+
                 | 55843 | 963   | 907   | 16    | 56393 |
                 +-------+-------+-------+-------+-------+
                 | 56403 | 471   | 907   | 16    | 56951 |
                 +-------+-------+-------+-------+-------+

             Table 2: Systematic Indices and Other Parameters

5.7. Operating with Octets, Symbols, and Matrices ✨

5.7.1. General 🦋

okay so this bit is the setup for all the actual maths-y stuff coming up, and I'm obsessed already 💅 the vibe is that we're gonna be doing arithmetic on octets (aka 8-bit bytes 🫶). Mathematically, these octets can be treated as elements of a finite field, specifically the finite field GF(256), which has 256 elements. That means addition, multiplication, identity elements, and inverses are all defined over both operations, so the whole thing is giving very structured 🌈. Matrix operations and symbol operations are then built on top of that octet arithmetic ✨. The best part? You can fully implement all of these operations without having to understand the underlying finite field mathematics first, which is literally such a relief 😭🎀

5.7.2. Arithmetic Operations on Octets ✨

Okay bestie, octets are just bytes, and we map them to plain non-negative integers from 0 through 255 🔢. A single octet B[7],B[6],B[5],B[4],B[3],B[2],B[1],B[0] (where B[7] is the highest order bit and B[0] is the lowest) becomes the integer i using this formula:

i=B[7]*128+B[6]*64+B[5]*32+B[4]*16+B[3]*8+B[2]*4+B[1]*2+B[0]

Now the fun part 💅. Addition of two octets u and v is just XOR:

u + v = u ^ v.

Subtraction is the same thing 🫶, so:

u - v = u ^ v.

The zero element (the additive identity) is the octet for the integer 0. Every octet is its own additive inverse, because:

u + u = 0.

Iykyk 😭.

Multiplication is where it gets spicy 🔥. It runs on two lookup tables, OCT_EXP and OCT_LOG, which live in Section 5.7.3 and Section 5.7.4. OCT_LOG maps every octet except zero to an integer, and OCT_EXP maps integers back to octets. For two octets u and v:

u * v =

   0, if either u or v are 0,

   OCT_EXP[OCT_LOG[u] + OCT_LOG[v]] otherwise.

Quick heads up 👀: the + on the right-hand side is regular integer addition, since those arguments are ordinary integers and not octets.

Division of u by v (where v != 0) works like this:

u / v =

   0, if u == 0,

   OCT_EXP[OCT_LOG[u] - OCT_LOG[v] + 255] otherwise.

The one element (the multiplicative identity) is the octet for the integer 1 ✨. For an octet u that is not the zero element, i.e., the multiplicative inverse of u is:

OCT_EXP[255 - OCT_LOG[u]].

The octet called alpha is the one with integer representation 2 🦋. For any integer 0 <= i < 256, we have:

alpha^^i = OCT_EXP[i].

5.7.3. The Table OCT_EXP 🧚

The table OCT_EXP holds 510 octets. Indexing starts at 0 and runs up to 509, and the entries are the octets with these positive integer representations:

1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76,
152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157,
39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35,
70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222,
161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60,
120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 163,
91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26, 52,
104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 59,
118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218,
169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85,
170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198,
145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171,
75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25,
50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81,
162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9,
18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11,
22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71,
142, 1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38,
76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192,
157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159,
35, 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111,
222, 161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30,
60, 120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223,
163, 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26,
52, 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147,
59, 118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218,
169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85,
170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198,
145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171,
75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25,
50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81,
162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9,
18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11,
22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71,
142

5.7.4. The Table OCT_LOG 🌸

The table OCT_LOG holds 255 non-negative integers 💜. It is indexed by octets read as integers. The octet for the zero element (integer 0) is not allowed as an index, so indexing starts at 1 and goes up to 255. The entries are:

0, 1, 25, 2, 50, 26, 198, 3, 223, 51, 238, 27, 104, 199, 75, 4, 100,
224, 14, 52, 141, 239, 129, 28, 193, 105, 248, 200, 8, 76, 113, 5,
138, 101, 47, 225, 36, 15, 33, 53, 147, 142, 218, 240, 18, 130, 69,
29, 181, 194, 125, 106, 39, 249, 185, 201, 154, 9, 120, 77, 228, 114,
166, 6, 191, 139, 98, 102, 221, 48, 253, 226, 152, 37, 179, 16, 145,
34, 136, 54, 208, 148, 206, 143, 150, 219, 189, 241, 210, 19, 92,
131, 56, 70, 64, 30, 66, 182, 163, 195, 72, 126, 110, 107, 58, 40,
84, 250, 133, 186, 61, 202, 94, 155, 159, 10, 21, 121, 43, 78, 212,
229, 172, 115, 243, 167, 87, 7, 112, 192, 247, 140, 128, 99, 13, 103,
74, 222, 237, 49, 197, 254, 24, 227, 165, 153, 119, 38, 184, 180,
124, 17, 68, 146, 217, 35, 32, 137, 46, 55, 63, 209, 91, 149, 188,
207, 205, 144, 135, 151, 178, 220, 252, 190, 97, 242, 86, 211, 171,
20, 42, 93, 158, 132, 60, 57, 83, 71, 109, 65, 162, 31, 45, 67, 216,
183, 123, 164, 118, 196, 23, 73, 236, 127, 12, 111, 246, 108, 161,
59, 82, 41, 157, 85, 170, 251, 96, 134, 177, 187, 204, 62, 90, 203,
89, 95, 176, 156, 169, 160, 81, 11, 245, 22, 235, 122, 117, 44, 215,
79, 174, 213, 233, 230, 231, 173, 232, 116, 214, 244, 234, 168, 80,
88, 175

5.7.5. Operations on Symbols 🎀

Operations on symbols work exactly like operations on vectors of T octets in this specification 🧩. So if U and V are two symbols made of the octets u[0], ..., u[T-1] and v[0], ..., v[T-1], the sum U + V is the component-wise sum of the octets. That gives a symbol D made of d[0], ..., d[T-1], where:

d[i] = u[i] + v[i], 0 <= i < T.

And if beta is an octet, then beta*U is the symbol D you get by multiplying each octet of U by beta:

d[i] = beta*u[i], 0 <= i < T.

5.7.6. Operations on Matrices 🌈

Every matrix in this specification has octets as its entries. That means matrix operations and definitions (matrix rank, matrix inversion, and so on) are all built on the octet arithmetic we just covered 🙌.

5.8. Requirements for a Compliant Decoder 🔥

If a RaptorQ-compliant decoder gets a mathematically sufficient set of encoding symbols, generated by the encoder specification in Section 5.3 for reconstructing a source block, then such a decoder SHOULD recover the entire source block 💅.

A RaptorQ-compliant decoder SHALL have the following recovery properties for source blocks with K' source symbols, for all values of K' in Table 2 of Section 5.6 👑.

  1. If the decoder receives K' encoding symbols generated according to the encoder specification in Section 5.3, with corresponding ESIs chosen independently and uniformly at random from the range of possible ESIs, then on average the decoder will fail to recover the entire source block at most 1 out of 100 times.
  2. If the decoder receives K'+1 encoding symbols generated according to the encoder specification in Section 5.3, with corresponding ESIs chosen independently and uniformly at random from the range of possible ESIs, then on average the decoder will fail to recover the entire source block at most 1 out of 10,000 times.
  3. If the decoder receives K'+2 encoding symbols generated according to the encoder specification in Section 5.3, with corresponding ESIs chosen independently and uniformly at random from the range of possible ESIs, then on average the decoder will fail to recover the entire source block at most 1 out of 1,000,000 times.

Note that the Example FEC Decoder specified in Section 5.4 meets both requirements ⭐:

  1. it can reconstruct a source block as long as it receives a mathematically sufficient set of encoding symbols generated according to the encoder specification in Section 5.3, and
  2. it fulfills the mandatory recovery properties from above.

6. Security Considerations 🚨

Data delivery can be subject to denial-of-service attacks, where attackers send corrupted packets that receivers accept as legitimate 😱. This is especially scary for multicast delivery, because a corrupted packet may be injected into the session close to the root of the multicast tree. If that happens, the corrupted packet arrives at many receivers at once. Even one corrupted packet containing encoding data may lead to decoding an object that is completely corrupted and unusable 💀.

It is thus RECOMMENDED that source authentication and integrity checking are applied to decoded objects before those objects are delivered to an application 🔐. For example, a SHA-256 hash [FIPS.180-3.2008] of an object may be appended before transmission. The SHA-256 hash is then computed and checked after the object is decoded, but before it is delivered to an application. Source authentication SHOULD be provided, for example, by including a digital signature that the receiver can verify, computed on top of the hash value.

It is also RECOMMENDED that a packet authentication protocol, such as TESLA [RFC4082], be used to detect and discard corrupted packets upon arrival 🛡️. This method may also be used to provide source authentication.

Furthermore, it is RECOMMENDED that Reverse Path Forwarding checks be enabled in all network routers and switches along the path from the sender to receivers 🚦. This limits the possibility of a bad agent successfully injecting a corrupted packet into the multicast tree data path.

Another security concern: some FEC information may be obtained by receivers out-of-band in a session description. If the session description is forged or corrupted, then the receivers will not use the correct protocol for decoding content from received packets. Not okay 😤.

To avoid these problems, it is RECOMMENDED that measures be taken to prevent receivers from accepting incorrect session descriptions. For example, source authentication can be used to make sure receivers only accept legitimate session descriptions from authorized senders 🫶.

7. 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]. IANA has assigned the value 6 under the ietf:rmt:fec:encoding registry to "RaptorQ Code" as the Fully-Specified FEC Encoding ID value associated with this specification 🎉.

8. Acknowledgements 🙏✨

Big thank-yous to Ranganathan (Ranga) Krishnan 🫶. Ranga has been so supportive, helping find and sort out implementation details and tracking down the systematic indices. Habeeb Mohiuddin Mohammed and Antonios Pitarokoilis, both from the Munich University of Technology (TUM), plus Alan Shinsato, each built their own independent implementation of the RaptorQ encoder/decoder 💅. Those two implementations helped clarify things and resolve issues in this specification, which is seriously iconic.

9. References 📚

9.1. Normative References

[FIPS.180-3.2008]
           National Institute of Standards and Technology, "Secure
           Hash Standard", FIPS PUB 180-3, October 2008.

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

[RFC4082]  Perrig, A., Song, D., Canetti, R., Tygar, J., and B.
           Briscoe, "Timed Efficient Stream Loss-Tolerant
           Authentication (TESLA): Multicast Source Authentication
           Transform Introduction", RFC 4082, June 2005.

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

9.2. Informative References 🌸

[LTCodes]  Luby, M., "LT codes", Annual IEEE Symposium on Foundations
           of Computer Science, pp. 271-280, November 2002.

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

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

[RaptorCodes]
           Shokrollahi, A. and M. Luby, "Raptor Codes", Foundations
           and Trends in Communications and Information Theory: Vol.
           6: No. 3-4, pp. 213-322, 2011.

Authors' Addresses 🦋

Michael Luby
Qualcomm Incorporated
3165 Kifer Road
Santa Clara, CA  95051
U.S.A.

EMail: luby@qualcomm.com


Amin Shokrollahi
EPFL
Laboratoire d'algorithmique
Station 14
Batiment BC
Lausanne  1015
Switzerland

EMail: amin.shokrollahi@epfl.ch


Mark Watson
Netflix Inc.
100 Winchester Circle
Los Gatos, CA  95032
U.S.A.

EMail: watsonm@netflix.com


Thomas Stockhammer
Nomor Research
Brecherspitzstrasse 8
Munich  81541
Germany

EMail: stockhammer@nomor.de


Lorenz Minder
Qualcomm Incorporated
3165 Kifer Road
Santa Clara, CA  95051
U.S.A.

EMail: lminder@qualcomm.com
📦 where this page comes from