# Design and Analysis of Systematic Batched Network Codes
### Contributions Regarding Systematic Outer Codes  
The outer code of a batched network code can be designed by extending fountain codes or LDPC codes [19; 21], which achieve higher rates than the overlapping outer codes for the same inner code. The existing outer codes obtained by coding are not designed to be systematic. In principle, any linear code can be systematic by transforming the generator matrix to the reduced echelon form. As the existing outer codes obtained by coding are linear, they can also be systematic. The main issue, however, is how to preserve the low encoding/decoding computation cost: a general transformation of the generator matrix by Gaussian elimination affects the structure of the codes and hence may increase the computation cost. In this paper, we design a systematic outer code based on the BATched Sparse (BATS) outer code, which is a matrix-generalized fountain code [19]. When the batch size is 1, the BATS outer code becomes a fountain code. The BATS outer code preserves the rateless feature of fountain codes, i.e., the number of batches that can be generated is unlimited (i.e., the rateless property) and can achieve a nearly optimal outer code rate with low encoding/decoding complexity. To preserve the salient features of the BATS outer code, the systematic outer code is also expected to be rateless, where the first \(n_{s}\) batches (called _systematic batches_) consist of a partition of the message packets. In addition to the systematic batches, the outer code can further generate more batches, called _non-systematic batches_. The fountain code has a low-complexity systematic design that benefits from the universal degree distribution [37]. When the batch size is larger than 1, the degree distribution of the BATS outer code depends on the rank distribution of the batch transfer matrices and hence is not universal. For this reason, the systematic design of BATS codes has to consider some new issues that do not appear in the systematic fountain code design. In this paper, we generalize the fountain code approach to design a systematic outer code, which uses a (non-systematic) BATS outer code that satisfies the _consistency_ requirement. In particular, a consistent outer code generates the first \(n_{s}\) batches deterministically, which can recover all the message packets. To ensure a small coding overhead, \(n_{s}\) is expected to be as small as possible. For a fountain code, the minimum value of \(n_{s}\) is the same as the number of message packets, and a consistent code with the minimum value of \(n_{s}\) can be found using a number of trials of the random encoding procedure of the fountain code. As fountain codes are universal, for each number of message packets, a consistent code can be designed once and used forever. However, BATS outer codes are not universal, and, even for the same number of message packets, the consistent code is different for different rank distributions. Our experiments show that when the number of message packets is larger, many more random trials are required to find a consistent outer code with a small coding overhead. To design a systematic outer code with a small value of \(n_{s}\) more efficiently, we propose a structured encoding approach for the first \(n_{s}\) batches, called _triangular embedding_. Using triangular embedding, zero-coding-overhead outer codes can be designed with one or two random trials for a large range of the number of message packets. Triangular embedding does not increase the computation costs of both encoding and decoding. Moreover, we also verify in experiments that the batches generated by triangular embedding can be used with the batches generated by the BATS outer code and demonstrate superior decoding performance compared to the BATS outer code. We also analyze the encoding and decoding computation costs of the proposed systematic outer code. For encoding, the systematic outer code has a lower computation cost than the corresponding BATS outer code.