# Design and Analysis of Systematic Batched Network Codes
## 3 Systematic Outer Codes
### General Approach to Systematic Outer Codes  
We give a general approach tp systematic outer codes, which extends the idea of systematic fountain codes [37]. Suppose that we have \(K\) message packets \(\mathbf{B}\) for encoding using a systematic outer code with batch size \(M\), where \(K\) is not necessarily a multiple of \(M\). Let \(n_{s}\) be an integer larger than or equal to \(K/M\), to be decided later. We wish todesign an outer code such that the first \(n_{s}\) batches are systematic batches that include all the message packets. Our approach to a systematic outer code uses an ordinary outer code (\(\text{ENC},\text{DEC}\)), where ENC is the encoder and DEC is the decoder, as described in Sections 2.1 and 2.3, respectively. The encoder ENC has two parts \(\text{ENC}_{n_{s}}\) and \(\text{ENC}_{n_{s}^{+}}\), where \(\text{ENC}_{n_{s}}\) generates the first \(n_{s}\) batches and \(\text{ENC}_{n_{s}^{+}}\) generates all the further batches. The decoder DEC in general applies to all the batches subject to any batch transfer matrices. We denote by \(\text{DEC}_{n_{s}}\) the case of DEC when applying to the first \(n_{s}\) batches with the rank-\(M\) batch transfer matrices. To construct the systematic outer code, we require \((\text{ENC},\text{DEC})\) satisfying some additional requirements. The pair \((\text{ENC},\text{DEC})\) is said to be _consistent_ if the following conditions are satisfied:  
1. \(\text{ENC}_{n_{s}}\) and \(\text{DEC}_{n_{s}}\) are deterministic; and
2. for any \(K\) packets \(\mathbf{B}\), \[\mathbf{B}=\text{DEC}_{n_{s}}\big{(}\text{ENC}_{n_{s}}(\mathbf{B})\big{)}.\] (3)  
For the consistency requirement 2, it is possible to verify (3) without any specific value \(\mathbf{B}\) of \(K\) packets, i.e., it is not necessary to check all choices of \(K\) packets. The reason is that both \(\text{ENC}_{n_{s}}\) and \(\text{DEC}_{n_{s}}\) are linear operations and, if the decoding is successful, their joint effect is to multiply the \(K\times K\) identity matrix. We discuss how to design a consistent outer code later. Here, we focus on how to use it to construct a systematic outer code. For a consistent \((\text{ENC},\text{DEC})\), the decoder \(\text{DEC}_{n_{s}}\) solves \(K\) message packets from the \(n_{s}M\) coded packets generated by \(\text{ENC}_{n_{s}}\). Among the \(n_{s}M\) coded packets, \(n_{s}M-K\) coded packets are redundant and can be removed without affecting the decoding performance (The decoding of a BATS code requires us to solve a system of linear equations by elementary equation operations. Each coded packet corresponds to an equation of the system. Each equation can solve at most one message packet. Therefore, exactly \(K\) equations are eventually transformed into the solutions of the message packets. The other equations are redundant). All the redundant packets can be identified by a trial of \(\text{DEC}_{n_{s}}\). For \(i=1,\ldots,n_{s}\), let \(M_{i}\) be the number of non-redundant coded packets in the \(i\)th batch. We know that \(\sum_{i=1}^{n_{s}}M_{i}=K\). Denote by \(\text{DEC}_{n_{s}}^{*}\) the same decoder as \(\text{DEC}_{n_{s}}\) except that the redundant coded packets are removed from the decoder input. Now, we can construct the systematic outer code. For the systematic outer code, the encoding at the source node works as follows:  
1. Partition the message packets \(\mathbf{B}\) into \(n_{s}\) subsets \(\hat{\mathbf{X}}_{i}\), \(i=1,\ldots,n_{s}\), where the number of packets in the \(i\)th subset \(\hat{\mathbf{X}}_{i}\) is \(M_{i}\);
2. Calculate \(\tilde{\mathbf{B}}=\text{DEC}_{n_{s}}^{*}(\hat{\mathbf{X}}_{1},\ldots,\hat{ \mathbf{X}}_{n_{s}})=\text{DEC}_{n_{s}}^{*}(\mathbf{B})\);
3. Generate the first \(n_{s}\) batches \(\text{ENC}_{n_{s}}(\tilde{\mathbf{B}})\). 4. Generate more batches by performing \(\text{ENC}_{n_{s}^{+}}\) on \(\tilde{\mathbf{B}}\). See Figure 2b for an illustration of the above encoding process. We justify that the above encoding process is systematic by showing that the first \(n_{s}\) batches include all the message packets.