# Design and Analysis of Systematic Batched Network Codes
## 3 Systematic Outer Codes
### Naive Approaches  
Before introducing our approach, we first discuss some naive approaches and their limitations. For a fixed number \(n\) of batches, the outer code is a linear block code and hence the encoding process can be described as  
\[\left[\mathbf{X}_{1}\quad\cdots\quad\mathbf{X}_{n}\right]=\mathbf{B}\mathbf{ \tilde{G}}\]  
where \(\mathbf{\tilde{G}}\) is the \(K\times nM\) generator matrix of the first \(n\) batches. Suppose that \(nM\geq K\). If \(\mathbf{\tilde{G}}\) has \(K\) columns forming the identity matrix, the outer code is systematic.  
First, we show that the random encoding of the ordinary BATS outer code is not a systematic code with high probability. For a batch of total degree \(d\), the probability that a coded packet is equal to a precoded packet is \(dq^{-d}\). As not all precoded packets are message packets, the probability that a coded packet is equal to a message packet is no greater than \(dq^{-d}\). Typically, \(d\geq M\geq 2\) and \(q=256\). Thus, it is unlikely that a message packet appears in a batch using the ordinary outer code.  
When \(n\) is slightly larger than \(K/M\), the matrix \(\mathbf{\tilde{G}}\) obtained from the ordinary BATS outer code has rank \(K\) with a high probability. The general procedure to make a linear code systematic is to transform \(\mathbf{\tilde{G}}\) by elementary row operations into the reduced row echelon form. Although a systematic code can be obtained, the drawback of this approach is that the low encoding/decoding computation cost of the BATS outer code cannot be preserved.  
Now, we discuss another naive approach that seems solve the computation cost issue. To simplify the discussion, suppose that the number of message packets \(K\) is a multiple of the batch size \(M\). In this naive approach, the first \(K/M\) batches form a partition of all the message packets, and more (non-systematic) batches are generated according to the encoding of batches as an ordinary outer code discussed in Section 2.1. However, to guarantee good decoding performance using the naive approach, a high degree must be applied to all the non-systematic batches.  
We show two cases wherein a high degree of the non-systematic batches is necessary. In the first case, one systematic batch is completely erased during the communication and all the other systematic batches are received by the destination nodes, together with a non-systematic batch. Suppose that the erased batch is randomly chosen. For all the received batches, the batch transfer matrix is the \(M\times M\) identity matrix so that the decoding problem becomes one of traditional erasure coding. The total number of received packets is \(K\). To guarantee the decoding of all the message packets, it is necessary that the degree of the received non-systematic batch is \(K\).  
In the second case, we consider that for \(M\) systematic batches, only one packet is erased during communication and all the other packets are received correctly. In other words, the batch transfer matrix of these \(M\) systematic batches is the \(M\times M\) identity matrix with one column removed, chosen uniformly at random. The destination node also receives all the other systematic batches, together with a non-systematic batch, all with the identity batch transfer matrix. The total number of received packets is \(K\). To guarantee the decoding of all the message packets, it is necessary that the degree of the received non-systematic batch is \(K\).  
From these cases, we see that to achieve a high coding rate using the naive approach, the degree of the non-systematic code must be high and hence the encoding/decoding complexity is high. In the remainder of this section, we derive an approach to obtain a systematic outer code that has similar encoding/decoding complexity to the ordinary BATS outer code.