# Design and Analysis of Systematic Batched Network Codes
## 5 Inner Code for Systematic Batches
### Recovery of Individual Message Packets  
Although \(\mathbf{Y}^{(u)}\) does not include any message packets, it may be possible to decode some message packets from (5). When \(\text{rank}(\mathbf{H}^{(u)})=M\), all the message packets of a batch can be decoded at node \(u\). Note that for batched network coding, \(\mathbf{H}^{(u)}\) does not necessarily need to be of rank \(M\). We say that a message packet, i.e., a column of \(\mathbf{X}\), can be recovered at node \(u\) if it can be uniquely solved from the system (5). When \(\text{rank}(\mathbf{H}^{(u)})<M\), some of the message packets can be recovered by operations within a systematic batch. Denote by \(\text{Col}(\mathbf{H}^{(u)})\) the column space of the matrix \(\mathbf{H}^{(u)}\). Let \(\mathbf{e}_{i}\) be the length-\(M\) column vector with its \(i\)th entry \(1\) and all the other entries \(0\). A necessary and sufficient condition such that a message packet can be recovered from \(\mathbf{Y}^{(u)}\) is as follows. Under the condition that \(\mathbf{Y}^{(u)}=\mathbf{X}\mathbf{H}^{(u)}\) is consistent, the \(i\)th packet in \(\mathbf{X}\) has a unique solution if and only if \(\mathbf{e}_{i}\in\text{Col}(\mathbf{H}^{(u)})\). The lemma can be proven by the equivalence of the following statements:  
1. The \(i\)th packet in \(\mathbf{X}\) has a unique solution;
2. All the vectors \(\mathbf{x}\in\mathbb{F}_{q}^{N_{u}}\) such that \(\mathbf{x}\mathbf{H}^{(u)}=\mathbf{0}\) (called the left nullspace collectively) have the \(i\)th entry \(0\);
3. \(\mathbf{e}_{i}\) is orthogonal to the left nullspace of \(\mathbf{H}^{(u)}\);
4. \(\mathbf{e}_{i}\) is in the column space of \(\mathbf{H}^{(u)}\). The following proposition shows that we can test the recoverability of all the message packets in a systematic batch from the reduced column echelon form of \(\mathbf{H}^{(u)}\), which can be obtained by (column-wise) Gauss-Jordan elimination. **Proposition 1**: _Let \(\mathbf{L}\) be the reduced column echelon form for a matrix \(\mathbf{H}^{(u)}\). Then, \(\mathbf{e}_{i}\in\mathrm{Col}(\mathbf{H}^{(u)})\) if and only if \(\mathbf{e}_{i}\) is a column of \(\mathbf{L}\)._  
See Appendix A. The next proposition shows that if a message packet cannot be recovered at a node, it cannot be recovered at any of the following nodes. Equivalently, if a message packet can be recovered at a node, it can be recovered at all the previous nodes. **Proposition 2**: _If a message packet cannot be recovered at the node \(u\), then it cannot be recovered at the node \(u+\) on the next hop._  
If the \(i\)th message packet cannot be recovered at the node \(u\), by Lemma 1, we have \(\mathbf{e}_{i}\
ot\in\mathrm{Col}(\mathbf{H}^{(u)})\). Due to \(\mathrm{Col}(\mathbf{H}^{(u+)})=\mathrm{Col}(\mathbf{H}^{(u)}\Phi^{(u)}\mathbf{ E}^{(u)})\subseteq\mathrm{Col}(\mathbf{H}^{(u)})\), \(\mathbf{e}_{i}\
ot\in\mathrm{Col}(\mathbf{H}^{(u+)})\) and hence the \(i\)th message packet cannot be recovered at the node \(u^{+}\). In general, performing an elementary operation as used in Gauss-Jordan elimination on the received packets of a batch does not affect the rank of the batch, and hence does not affect the decoding performance. However, recovering message packets at the intermediate nodes helps to improve the number of message packets to be received/recovered in the next hop. We use an example to illustrate this fact. **Example 1**: _Consider a line network with \(L=2\), \(M=3\) and \(N_{1}=M\) at node \(1\). Suppose that_  
\[\mathbf{H}^{(1)}= \begin{bmatrix}1&0&a\\ 0&1&b\\ 0&0&c\end{bmatrix} ,\]  
_where \(a,b,c\
eq 0\) are elements from the base field. Using systematic recoding on \(\mathbf{H}^{(1)}\), no additional packets should be generated and \(\mathbf{Y}^{(1)}\) is transmitted by node \(1\). When the second packet is lost from node \(1\) to \(2\), we obtain_  
\[\mathbf{H}^{(2)}= \begin{bmatrix}1&a\\ 0&b\\ 0&c\end{bmatrix} ,\]  
_At destination node \(2\), we can only recover one message packet.