# Design and Analysis of Systematic Batched Network Codes
## 2 Ordinary Batched Network Coding
### General Inner Code Formulation  
We use a line network as an example to introduce the inner code, and the inner code can be extended to other network typologies as discussed in [23]. A line network of length \(L\) is formed by a sequence of network nodes labeled by \(0,1,\ldots,L\), where the first node \(0\) is the source node and the last node \(L\) is the destination node. All the other nodes are called intermediate nodes. Network links exist only between two consecutive network nodes, modeled by packet erasure channels, i.e., a packet transmitted on a network link is either correctly received or erased. Figure 1 illustrates the line network.  
The inner code is the composition of the _recoding_ operations performed on each batch separately. The recoding at the source node takes the batches generated by the outer code as the input, and the recoding at an intermediate node takes the received packets of a batch as the input. For each batch, recoding generates a number of linear combinations of the packets belonging to the batch, and the packets generated by recoding are supposed to belong to the same batch. There are various approaches to the reco  
Figure 1: A line network of length \(L\). Node \(0\) is the source node, and node \(L\) is the destination node. The direct edge from node \(i\) to node \(i+1\) (\(i=0,1,\ldots,L-1\)) illustrates the network link.  
is determined by the linear combination coefficients. The original RLNC schemes use coefficients chosen uniformly at random from the base field [4; 6; 7], and extensive research has been carried out towards recoding with lower complexity and latency [39; 40; 41; 42; 43; 44]. In this paper, we study the recoding schemes that can fulfil the systematic coding requirement.  
Without specifying a recoding scheme, we give a general formulation of recoding. Fix a certain network node \(u\). Let \(\mathbf{Y}_{i}^{(u)}\) be the received packets of the \(i\)th batch at the node \(u\). At the source node, \(\mathbf{Y}_{i}^{(0)}=\mathbf{X}_{i}\). As recoding is linear, for \(v=1,\ldots,L\),  
\[\mathbf{Y}_{i}^{(u)}=\mathbf{X}_{i}\mathbf{H}_{i}^{(u)}=\mathbf{B}_{i} \mathbf{G}_{i}\mathbf{H}_{i}^{(u)}, \tag{2}\]  
where \(\mathbf{H}_{i}^{(u)}\) is called the (_batch_) _transfer matrix_ of the \(i\)th batch at the node \(u\). The number of rows of \(\mathbf{H}_{i}^{(u)}\) is \(M\). The number of columns of \(\mathbf{H}_{i}^{(u)}\) corresponds to the number of packets received for the \(i\)th batch at the node \(u\), which may vary for different batches and is finite. If no packets are received for a batch, \(\mathbf{Y}_{i}^{(u)}\) (\(\mathbf{H}_{i}^{(u)}\)) is the empty matrix of 0 columns.  
Note that the transfer matrices are determined not only by the recoding scheme, but also by the network packet loss pattern. Due to the randomness in both recoding and packet loss, the transfer matrices cannot be derived from the recoding design. To obtain the transfer matrices, RLNC introduces _coefficient vectors_ embedded in the packet header immediately after \(\mathbf{X}_{i}\) is generated. The matrix formed by the coefficient vectors is the identity matrix. The same linear operations performed on a batch are performed on the coefficient vectors as well, so that \(\mathbf{H}_{i}^{(u)}\) can be known at each node \(u\) that receives batch \(i\) from the header of the batch.  
We say that a set of packets of a batch are linearly independent/dependent if their corresponding coefficient vectors in the packet header are linearly independent/dependent. We call \(\text{rank}(\mathbf{H}_{i}^{(u)})\) the _rank of the \(i\)th batch_ at node \(u\).