# Design and Analysis of Systematic Batched Network Codes
## 5 Inner Code for Systematic Batches
### Detailed Inner Code Formulation  
We first formulate in detail how each network node performs the inner code. We also discuss the existing inner coding schemes for systematic batches. We consider the inner code on a line network as described in Section 2. As the inner code is performed on each batch individually, we consider a generic systematic batch \(\mathbf{X}\) without the subscripts. We assume that the packets in \(\mathbf{X}\) are all message packets. By (2), the received packets \(\mathbf{Y}^{(u)}\) of the batch \(\mathbf{X}\) at node \(u\) satisfy  
\[\mathbf{Y}^{(u)}=\mathbf{X}\mathbf{H}^{(u)}, \tag{5}\]  
where \(\mathbf{H}^{(u)}\) is the transfer matrix of the batch at the node \(u\). \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Coding** & \(\mathbf{K=10}M\) & \(\mathbf{K=100}M\) & \(\mathbf{K=200}M\) & \(\mathbf{K=400}M\) & \(\mathbf{K=600}M\) \\ \hline \multicolumn{6}{l}{**(a) \(\epsilon=0.1\)**} \\ \hline \hline
0 & 4982 & 4955 & 3446 & 3 & 0 \\ \(1\sim M\) & 18 & 26 & 69 & 0 & 0 \\ \(M+1\sim 2M\) & 0 & 3 & 51 & 0 & 0 \\ \(>2M\) & 0 & 16 & 1434 & 4997 & 5000 \\ \hline \multicolumn{6}{l}{**(b) \(\epsilon=0.3\)**} \\ \hline
0 & 4983 & 4511 & 1037 & 17 & 0 \\ \(1\sim M\) & 17 & 73 & 31 & 0 & 0 \\ \(M+1\sim 2M\) & 0 & 39 & 25 & 1 & 0 \\ \(>2M\) & 0 & 377 & 3907 & 4982 & 5000 \\ \hline \multicolumn{6}{l}{**(c) \(\epsilon=0.5\)**} \\ \hline
0 & 4987 & 4155 & 1823 & 5 & 0 \\ \(1\sim M\) & 13 & 107 & 101 & 1 & 0 \\ \(M+1\sim 2M\) & 0 & 61 & 72 & 1 & 0 \\ \(>2M\) & 0 & 677 & 3004 & 4993 & 5000 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Joint decoding of batches generated by triangular embedding and the ordinary outer code. Here, \(M=16\) and \(\mathbf{h}\) has rank \(M\) with probability \(1\). In our experiments, each batch generated by triangular embedding has a probability \(\epsilon\) of being discarded, and the remaining batches are sent to the decoder. Following the batches generated by triangular embedding, batches generated by the ordinary outer code are also sent to the decoder. For each value of \(K=10M,100M,200M,400M,600M\) and \(\epsilon=0.1,0.3,0.5\), in total, 5000 instances are tested. Let \(N_{u}\) be the number of columns of \(\mathbf{Y}^{(u)}\) (or \(\mathbf{H}^{(u)}\)), i.e., the number of received packets of the batch at node \(u\). For a non-destination node \(u\), we use \(u+\) to denote the receiver of the outgoing link of \(u\) in the line network. Suppose that the node \(u\) needs to transmit \(N_{u}^{\prime}\) packets of the batch \(\mathbf{X}\) to the node \(u+\). The transmitted packets, called _decoded packets_, are generated by linear combinations as \(\mathbf{Y}^{(u)}\Phi^{(u)}=\mathbf{X}\mathbf{H}^{(u)}\Phi^{(u)}\), where \(\Phi^{(u)}\) is an \(N_{u}\times N_{u}^{\prime}\) matrix over the base field \(\mathbb{F}_{q}\). Due to packet loss, the set of received packets at \(u+\) is a subset of \(\mathbf{Y}^{(u)}\Phi^{(u)}\). Let \(\mathbf{E}^{(u)}\) be an \(N_{u}^{\prime}\times N_{u+}\) matrix obtained by removing the columns of an identity matrix specifying the packet erasures. We can write  
\[\mathbf{Y}^{(u+)}=\mathbf{X}\mathbf{H}^{(u)}\Phi^{(u)}\mathbf{E}^{(u)}= \mathbf{X}\mathbf{H}^{(u+)}, \tag{6}\]  
where \(\mathbf{H}^{(u+)}=\mathbf{H}^{(u)}\Phi^{(u)}\mathbf{E}^{(u)}\). There are many solutions to design the recoding matrix \(\Phi^{(u)}\) in the literature. One common method for RLNC is a uniformly random matrix over the base field, which is also called the _random linear inner code_ (RLIC). For multicast communications, it has been shown that RLIC achieves the multicast capacity for networks with packet loss [5; 8; 9; 10]. For the line network discussed here, the _systematic inner code_ (SIC) has been proposed [23], where all the linearly independent received packets are directly used as recoded packets. We first discuss the performance of these two existing inner code schemes for systematic batches. * When using RLIC for systematic batches, the probability that a recoded packet (a column of \(\mathbf{X}\Phi^{(u)}\)) is a message packet is \(q^{-M}\).