# Design and Analysis of Systematic Batched Network Codes
## 4 Triangular Embedding: A Structured Systematic Outer Code Design
### Triangular Embedding Design  
Consider the encoding of \(K\) message packets with respect to a general rank distribution \(\mathbf{h}\). We discuss how to generate the first \(n_{s}\) batches, where \(n_{s}\geq K/\,\mathbb{E}[\mathbf{h}]\). The precode is the same as the ordinary outer code. Let \(K\) and \(K^{\prime}\) be the number of message packets and the number of precoded packets, respectively. The precoded packets are also separated into active and inactive packets. Let \(A\) be the number of active packets, where \(A\geq K\). abla}\) optimized for \(\mathbf{h}\), we assume that the degree probability is zero for degrees from \(1\) to \(M-1\) (This assumption does not affect the generality of our design as it is asymptotically optimal to use such a degree distribution when the rank \(M\) probability of the batch transfer matrix is positive. When the probability of transfer matrix rank \(M\) is zero, we should reduce the batch size to improve the network's communication efficiency). Generate the active degree values \(d_{1}^{\mathrm{A}},\ldots,d_{n_{s}}^{\mathrm{A}}\) for the first \(n_{s}\) batches by sampling \(\boldsymbol{\
abla}\). To simplify the discussion, we assume that the degree values are ordered so that \(M\leq d_{1}^{\mathrm{A}}\leq d_{2}^{\mathrm{A}}\leq\cdots\leq d_{n_{s}}^{ \mathrm{A}}\). The inactive degree \(d_{i}^{\mathrm{B}}\) of the \(i\)th batch is obtained in the same way as the ordinary outer code. Fix positive integers \(M_{1},M_{2},\ldots,M_{n_{s}}\) such that \(\sum_{i=1}^{n_{s}}M_{i}=K\) and \(M_{i}\leq M\leq d_{i}^{\mathrm{A}}\). For example, when \(n_{s}\) divides \(K\), we may choose \(M_{i}=K/n_{s}\). When \(n_{s}\) does not divide \(K\), there exist unique non-negative integers \(a\) and \(b<n_{s}\) such that \(K=an_{s}+b\). We may let \(M_{i}=a+1\) for \(i=1,\ldots,b\) and let \(M_{i}=a\) for \(i=b+1,\ldots,n_{s}\). \begin{table}
\begin{tabular}{c c c c c c} \hline \(n_{s}-K/M\) & \(K=10M\) & \(K=100M\) & \(K=200M\) & \(K=400M\) & \(K=600M\) \\ \hline
0 & 4784 & 3552 & 836 & 4 & 0 \\
1 & 173 & 175 & 50 & 0 & 0 \\
2 & 34 & 113 & 53 & 0 & 0 \\ \(\geq\)3 & 9 & 1160 & 4061 & 4996 & 5000 \\ \hline \end{tabular}
\end{table} 
Table 1: Experiments of random design. Here, \(M=16\) and \(\mathbf{h}\) has rank \(M\). For each value of \(K=10M,100M,1000M,5000\) instances of the ordinary outer code are sampled. As a BATS code is rateless, for each instance, we can try a range of values of \(n_{s}\). The table gives the number of consistent instances when \(n_{s}=K/M,K/M+1,K/M+2\), and \(n_{s}\geq K/M+3\). Let \(N_{\text{inac}}\) be the maximum number of dynamic inactive packets allowed during inactivation decoding. We should determine the total number of inactive packets \(N_{\text{inac}}+K^{\prime}-A\) according to the decoding computation cost constraint. For example, \(N_{\text{inac}}+K^{\prime}-A=2\lceil\sqrt{K}\rceil\). We further assume that for \(i=1,\ldots,n_{s}\),  
\[d_{i}^{A}\leq\min\{A-K,N_{\text{inac}}\}+\sum_{j=1}^{i}M_{j}. \tag{4}\]  
This assumption is usually satisfied by the degrees sampled as 1) \(A-K\) is linear in \(K\) and 2) the average degree of a BATS code degree distribution is only around two times the batch size \(M\) and even the maximum degree is \(O(M)\). If \(d_{i}^{A}\) does not satisfy (4), which should occur rarely, we can modify \(d_{i}^{A}\) to this upper bound or re-sample the active degrees. Let \(m_{1}=0\), and, for \(i\geq 2\), let \(m_{i}=m_{i-1}+M_{i-1}\). For \(i\geq 1\), the \(d_{i}^{A}\) active packets in \(\mathbf{B}_{i}\) include  
* the \((m_{i}+1)\)th to the \((m_{i}+M_{i})\)th active packets, and
* a set of \(d_{i}^{A}-M_{i}\) packets chosen from the first \(m_{i}\) active packets and the last \(\min\{A-K,N_{\text{inac}}\}\) active packets. The inactive packets in \(\mathbf{B}_{i}\) are obtained in the same way as the ordinary outer code. The \(i\)th batch is generated as \(\mathbf{B}_{i}\mathbf{G}_{i}\), where \(\mathbf{G}_{i}\) is a \(d_{i}\times M\) matrix different from the ordinary outer code.