## 2 Overview of Random Linear Network Coding
### Introduction to RLNC  
The system model under consideration contains RLNC encoder block at the transmitter and RLNC decoder block at one or more receivers, connected via independent packet erasure channels. An example with a single transmitter and a single receiver is illustrated in Figure 1.  
**RLNC encoder block**: The input to the RLNC encoder is a source block \(\mathbf{s}=[\mathbf{s}_{1},\mathbf{s}_{2},\ldots,\mathbf{s}_{K}]\) containing \(K\) equal-length _source packets_, each containing \(L\) symbols of a finite field \(\mathbb{F}_{q}\) of size \(q\). RLNC encoder encodes \(\mathbf{s}\) into a stream of _coded packets_\(\mathbf{c}=[\mathbf{c}_{1},\mathbf{c}_{2},\ldots,\mathbf{c}_{N}]\), where each encoded packet \(\mathbf{c}_{i}\) represents a random linear combination of the source packets, i.e., \(\mathbf{c}_{i}=\sum_{j=1}^{K}g_{ij}\mathbf{s}_{j}\), and is of the same length \(L\) symbols of \(\mathbb{F}_{q}\) as source packets. The _coding coefficients_\(g_{ij}\in\mathbb{F}_{q}\) are selected uniformly at random from \(\mathbb{F}_{q}\), and for each \(\mathbf{c}_{i}\), the associated set of coding coefficients forms the _coding vector_\(\mathbf{g}_{i}=[g_{i,1},g_{i,2},\ldots,g_{i,K}]\). Note that the transmitter can produce arbitrarily many encoded packets \(N\) from \(K\) source packets in a rateless fashion. Fixing \(N\), the set of encoded packets can be represented as \(\mathbf{c}=\mathbf{s}\cdot\mathbf{G}^{T}\), where _coding matrix_\(\mathbf{G}\) represents a \(N\times K\) random matrix over \(\mathbb{F}_{q}\). Frequently, systematic RLNC is also considered, where \(\mathbf{c}_{i}=\mathbf{s}_{i},1\leq i\leq K\), i.e., the first \(K\) coded packets are replicas of source packets, thus the first \(K\) rows of \(\mathbf{G}\) represent \(\mathbf{I}_{K\times K}\) identity matrix. **Packet erasure channel**: Coded packets are transmitted to one or more receivers via independent packet erasure channels. For the \(j\)-th receiver, the erasure probability of the corresponding channel is denoted as \(\epsilon_{j}\), where \(0\leq\epsilon_{j}\leq 1\). If the focus is on a single receiver, we will omit index and use \(\epsilon\) as erasure probability. Packet erasure channel is adopted as, further in the paper, we will only consider integration of RLNC as part of the higher protocol layers, without considering any details or information available from physical (PHY) layer. **RLNC decoder block**: Due to possible packet losses, a receiver receives a subset of \(n\leq N\) coded packets. Extracting the corresponding coding vectors, the receiver obtains \(\mathbf{c}=\mathbf{s}\cdot\mathbf{D}^{T}\), where, with some abuse of notation, \(\mathbf{c}=[\mathbf{c}_{1},\mathbf{c}_{2},\ldots,\mathbf{c}_{n}]\) represents the set of received coded packets, while \(\mathbf{D}\) is a random \(n\times K\) matrix over \(\mathbb{F}_{q}\). To recover source packets, the receiver applies Gaussian Elimination (GE) decoding, which successfully recovers the source block \(\mathbf{s}\) iff for the rank \(r(\mathbf{D})\) of the decoding matrix \(\mathbf{D}\) it holds that \(r(\mathbf{D})=K\). We note that for shorter source block lengths \(K\), the complexity of GE decoding is acceptable, which is why longer source blocks are typically divided into sub-blocks called generations [17]. The complexity of GE decoding can be further reduced by exploiting systematic, sparse and tunable sparse RLNC we describe shortly below. **Performance measures**: One of the main RLNC performance measures is the probability the source block \(\mathbf{s}\) is successfully recovered given the number of received coded packets \(n\). This _decoding probability_ can be easily calculated [26; 27]:  
\[P_{d}(n)=\left\{ \begin{array}{ll}0&\text{if }n<K,\\ \prod_{i=1}^{K-1}(1-\frac{1}{q^{n-j}})&\text{if }n\geq K.\end{array} \right. \tag{1}\]  
Note that (1) represents a cumulative distribution function (cdf) of the probability that \(K\) linearly independent packets are collected among \(n\) received coded packets.