# Design and Analysis of Systematic Batched Network Codes
## 5 Inner Code for Systematic Batches
### Recoding with Message Packet Protection  
Let \(r=\text{rank}(\mathbf{H}^{(u)})\) and \(\mathbf{V}\) be an \(N_{u}\times N_{u}\) matrix such that \(\mathbf{H}^{(u)}\mathbf{V}\) is in reduced column echelon form. To recover message packets, we perform the same column operations on \(\mathbf{Y}^{(u)}\) and obtain \(\mathbf{Y}^{(u)}\mathbf{V}=\mathbf{X}\mathbf{H}^{(u)}\mathbf{V}\). If \(\mathbf{e}_{i}\) is the \(j\)th column of \(\mathbf{H}^{(u)}\mathbf{V}\), then the \(j\)th column of \(\mathbf{Y}^{(u)}\mathbf{V}\) is equal to the \(i\)th message packet. Let \(s\) be the number of message packets that can be recovered from \(\mathbf{Y}^{(u)}\). By Proposition 1, there are exactly \(s\) distinct columns in \(\mathbf{H}^{(u)}\mathbf{V}\) with only \(1\) non-zero entry being one. Therefore, by proper row and column permutations, \(\mathbf{H}^{(u)}\mathbf{V}\) is of the form  
\[ \begin{bmatrix}\mathbf{I}_{s}&\mathbf{0}&\mathbf{0}\\ \mathbf{0}&\mathbf{I}_{r-s}&\mathbf{0}\\ \mathbf{0}&\mathbf{T}&\mathbf{0}\end{bmatrix} , \tag{7}\]  
where \(\mathbf{I}_{k}\) is the \(k\times k\) identity matrix, \(\mathbf{0}\) is an all-zero matrix of proper size, and \(\mathbf{T}\) is an \((N_{u}-r)\times r\) matrix where each column is not zero. Denoting the first \(r\) columns of the corresponding column permutation matrix as the \(N_{u}\times r\) matrix \(\mathbf{P}\), each of the first \(s\) columns of \(\mathbf{H}^{(u)}\mathbf{V}\mathbf{P}\) has only \(1\) non-zero entry. We have discussed the decoding step, which is represented by \(\mathbf{V}\). However, to generate a recoded batch, some redundant packets are to be generated. The following proposition states that using the random linear inner code at node \(u\), the node \(u+\) can recover almost no message packets when the number of received packets at \(u+\) is fewer than \(\text{rank}(\mathbf{H}^{(u)})\). Denote by \(\zeta_{k}^{m,n}\) the probability that an \(m\times n\) uniformly random matrix over \(\mathbb{F}_{q}\) has rank \(k\). See, e.g., ([23], Section 3.3.2) for the formula of \(\zeta_{k}^{m,n}\). **Proposition 5**. : _Suppose that the random linear inner code over \(\mathbb{F}_{q}\) is used at the node \(u\) and \(N_{u+}<r=\text{rank}(\mathbf{H}^{(u)})\). Under the condition that \(\mathbf{e}_{i}\in\text{Col}(\mathbf{H}^{(u)})\), the probability that \(\mathbf{e}_{i}\in\text{Col}(\mathbf{H}^{(u+)})\) is \(1-\sum_{k=0}^{N_{u}}\zeta_{k}^{r-1,N_{u+}}q^{k-N_{u+}}\) and it converges to zero as \(q\to\infty\)._  
Proof. : See Appendix A. It is unavoidable that the number of received packets at \(u+\) is smaller than \(\text{rank}(\mathbf{H}^{(u)})\) due to packet loss. Together with Proposition 2, Proposition 5 implies that as long as the event \(N_{u+}<\text{rank}(\mathbf{H}^{(u)})\) occurs once at some node \(u\), the destination node receives almost no message packets from a systematic batch. Therefore, random linear recoding is not preferred for the recovery of message packets. Thus, we are motivated to extend systematic inner codes for the recovery of message packets. We propose two designs of recoding that can protect the message packets during recoding. We first define two recoding matrices. Suppose that \(s\) message packets are recoverable at the node \(u\) and the rank of the batch is \(r\). **Message Protection Recoding**  
For an integer \(w\) with \(0\leq w\leq N_{u}^{\prime}-s\), let \(\mathbf{R}\) be an \(r\times N_{u}^{\prime}\) matrix of the form  
\[\mathbf{R}=\left[ \begin{array}{cc}\mathbf{I}_{s}&\mathbf{U}_{s,w}&\mathbf{ U}_{r,N_{u}^{\prime}-s-w}\\ \mathbf{0}&\mathbf{0}&\end{array} \right],\]  
where \(\mathbf{U}_{m,n}\) is the \(m\times n\) uniformly random matrix. **Systematic Message Protection Recoding**  
For an integer \(w\) with \(0\leq w\leq N_{u}^{\prime}-s\), let \(\mathbf{R}^{\text{sys}}\) be an \(r\times N_{u}^{\prime}\) matrix of the form: when \(w<N_{u}^{\prime}-r\),  
\[\mathbf{R}^{\text{sys}}=\left[