# Design and Analysis of Systematic Batched Network Codes
## 3 Systematic Outer Codes
### Random Design  
To implement the general approach to the systematic outer code, we only need to design a consistent pair (\(\mathrm{ENC},\mathrm{DEC}\)). In the following part of this section, we discuss the traditional random approach to designing a consistent (\(\mathrm{ENC},\mathrm{DEC}\)). In the next section, we discuss a new approach that can design a consistent (\(\mathrm{ENC},\mathrm{DEC}\)) more effectively. Denote by \(\mathbf{h}\) the rank distribution of the batches and let \(\boldsymbol{\Psi}^{A}\) be the degree distribution optimized for \(\mathbf{h}\) as in ([23], Chapter 6), which achieves the near-to-optimal rate of the ordinary outer code as in Section 2.1 asymptotically. We can use the ordinary encoder and decoder as introduced in Section 2.1 with the degree distribution \(\boldsymbol{\Psi}^{A}\) to design \(\mathrm{ENC}_{n_{s}^{+}}\) and \(\mathrm{DEC}\) for a consistent outer code (\(\mathrm{ENC},\mathrm{DEC}\)). The ordinary outer code is random, but we need a deterministic encoder-decoder pair (\(\mathrm{ENC}_{n_{s}},\mathrm{DEC}_{n_{s}}\)) to satisfy the consistent properties. For a given \(n_{s}\geq K/\operatorname{\mathbb{E}}[\mathbf{h}]\), we can perform random trials of the ordinary outer code using the degree distribution \(\boldsymbol{\Psi}^{A}\) until an instance (\(\mathrm{ENC}_{n_{s}},\mathrm{DEC}_{n_{s}}\)) is found such that (3) is satisfied. Note that it is sufficient for us to find only one such instance. As both \(\mathrm{ENC}_{n_{s}}\) and \(\mathrm{ENC}_{n_{s}^{+}}\) generate batch instances following the random outer code encoder with the degree distribution \(\boldsymbol{\Psi}^{A}\), which is optimized for \(\mathbf{h}\), \(\mathrm{DEC}\) can guarantee a high decoding success probability for a sufficiently large number of received batches [23]. If such an instance cannot be found for a certain value \(n_{s}\), we can increase the value of \(n_{s}\) by 1 and try again. The ordinary outer code is expected to decode correctly with a high probability when the number of batches is sufficiently large, and we expect to design a systematic code with the _expected coding overhead_\(n_{s}\operatorname{\mathbb{E}}[\mathbf{h}]-K\) as small as possible. When \(M=1\) and \(\operatorname{\mathbb{E}}[\mathbf{h}]=1\), i.e., the case of fountain codes, a consistent outer code exists for a range of the values of \(K\) when \(n_{s}=K\) using this approach [26]. For fountain codes, the random design works well as fountain codes have a universal design that can handle all packet loss patterns. The random design is only performed once for each value of the number of message packets \(K\). Therefore, the efficiency of the random design is not an issue. In other words, a large number of random trials can be performed to find a consistent outer code with a small or zero coding overhead. Although the random design is suitable for fountain codes, it can be less efficient when \(M>1\). BATS codes are not universal in the sense that the optimal degree distribution depends on the rank distribution \(\mathbf{h}\). Therefore, even for the same value of \(K\), the random design needs to be repeated for each \(\mathbf{h}\), and this may need to be carried out for \(\mathbf{h}\) obtained online. Hence, the efficiency of the random design becomes an issue for BATS codes  
Figure 4: Illustration of the decoding computation costs of the ordinary outer code and the systematic outer code. (**a**) illustrates the decoding computation cost for different numbers \(K_{m}\) of message packets received. For the ordinary outer code, the decoding computation cost is \(c\). For the systematic outer code, the decoding computation cost is approximately \(2c-K_{m}b\) when \(K_{m}<K\) and 0 when \(K_{m}=K\). (**b**) shows the number of decoded packets over time. The three curves labeled \(K_{m}=K,K/2,0\) are for the systematic outer code decoder with \(K_{m}\) message packets received. with batch size \(M\geq 2\).