# Design and Analysis of Systematic Batched Network Codes
## 2 Ordinary Batched Network Coding
### BATS Outer Code  
The outer code introduced here is also called the _ordinary_ outer code, in contrast to the systematic outer code, to be discussed in the next section. A finite field of size \(q\), denoted as \(\mathbb{F}_{q}\), is called the base field. A packet of length \(T\) is a column vector in \(\mathbb{F}_{q}^{T}\), and a set of packets of the same length is equated to the matrix formed by juxtaposing the packets in the set. We consider the transmission of \(K\) message packets, which form the \(T\times K\) matrix \(\mathbf{B}\) from the source node to the destination node in a network. The (ordinary) outer code encodes the \(K\) message packets in two steps. The first step uses a systematic precode to generate a number of redundant packets, which are also called _parity check packets_. Let \(K^{\prime}\geq K\) be the total number of packets containing the message packets and the parity check packets. Denote by \(\mathbf{B}_{p}\) the \(K^{\prime}-K\) parity check packets. Let \(\mathbf{P}\) the \(K^{\prime}\times(K^{\prime}-K)\) parity check matrix of the precode, i.e.,  
\[[\mathbf{B}\ \ \mathbf{B}_{p}]\mathbf{P}=\mathbf{0}. \tag{1}\]  
The parity check packets can include both low-density parity check (LDPC) and high-density parity check (HDPC) packets to balance the computation cost and the decoding performance. Refer to [37] for such a design of \(\mathbf{P}\). Let \(\mathbf{B}^{\prime}=[\mathbf{B}\ \ \mathbf{B}_{p}]\), which are called the precoded packets. The second encoding step of the outer code generates batches of coded packets. Let \(M\) be a positive integer called the _batch size_, which is usually less than a hundred. For \(i=1,2,\ldots\), the \(i\)th batch \(\mathbf{X}_{i}\) includes \(M\) packets generated from a subset \(\mathbf{B}_{i}\subset\mathbf{B}^{\prime}\) as follows:  
\[\mathbf{X}_{i}=\mathbf{B}_{i}\mathbf{G}_{i},\]  
where \(\mathbf{G}_{i}\) is a matrix of \(M\) columns called the _batch generator matrix_. The number of packets in \(\mathbf{B}_{i}\), which is also the number of rows of \(\mathbf{G}_{i}\), will be specified later. When \(M=1\), the outer code becomes a fountain code. The design of \(\mathbf{B}_{i}\) is discussed as follows. Here, we discuss general batch encoding that can be used for various decoding approaches, including inactivation decoding. The precoded packets are further separated into two parts:  
* _active packets_ that include a subset of the message packets and all the LDPC packets, and
* _inactive packets_ that include all the other message packets and all the HDPC packets. Denote by \(A\) the number of active packets. Then, the number of inactive packets is \(K^{\prime}-A\). We require \(A\geq K\). As a special case, when there are no HDPC packets or inactive packets during encoding, we have \(A=K^{\prime}\). The encoding of a batch uses both active and inactive packets. The number of active packets used in a batch is determined using a degree distribution \(\boldsymbol{\
abla}=(\mathbb{V}_{1},\ldots,\mathbb{V}_{D_{\text{max}}})\), and it affects the decoding performance of both belief propagation decoding and inactivation decoding. The degree distribution \(\boldsymbol{\
abla}\) is designed based on the _batched transfer matrix rank distribution_ induced by the inner code. The maximum number \(D_{\text{max}}\) for the active packets is sufficient to be a couple of multiples of \(M\), as proven in [19]. For the encoding of each batch \(\mathbf{X}_{i}\),  
1. Independently sample \(\boldsymbol{\
abla}\) and obtain an integer \(d_{i}^{A}\), which is called the active degree of the batch;
2. Uniformly, at random, choose \(d_{i}^{A}\) active packets to be included in \(\mathbf{B}_{i}\). The inactive packets can help to further improve the inactivation decoding performance. When \(M=1\), on average, each batch may involve 2 or 3 inactive packets [26]. When \(M>1\), the number of inactive packets in a batch can be \(3(K^{\prime}-A)/n\), where \(n\) is the number of batches expected to be used for decoding.