# Design and Analysis of Systematic Batched Network Codes
###### Abstract  
Systematic codes are of important practical interest for communications. Network coding, however, seems to conflict with systematic codes: although the source node can transmit message packets, network coding at the intermediate network nodes may significantly reduce the number of message packets received by the destination node. Is it possible to obtain the benefit of network coding while preserving some properties of the systematic codes? In this paper, we study the systematic design of batched network coding, which is a general network coding framework that includes random linear network coding as a special case. A batched network code has an outer code and an inner code, where the latter is formed by linear network coding. A systematic batched network code must take both the outer code and the inner code into consideration. Based on the outer code of a BATS code, which is a matrix-generalized fountain code, we propose a general systematic outer code construction that achieves a low encoding/decoding computation cost. To further reduce the number of random trials required to search a code with a close-to-optimal coding overhead, a triangular embedding approach is proposed for the construction of the systematic batches. We introduce new inner codes that provide protection for the systematic batches during transmission and show that it is possible to significantly increase the expected number of message packets in a received batch at the destination node, without harm to the expected rank of the batch transfer matrix generated by network coding.  
network coding; systematic code; random linear network coding; batched network coding; BATS code +
Footnote †: journal:  
0000-0002-4000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-00000  
Batched network coding allows joint batch encoding/decoding, while the original RLNC schemes can be regarded as special batched network codes where the outer code has a single batch or multiple batches encoded/decoded separately.  
In coding theory, a code is said to be systematic if all message symbols form a subset of the coded symbols [24]. Many practical codes can be designed to be systematic--for example, Reed-Solomon codes [25], fountain codes [26] and polar codes [27]. Standardized LDPC codes in both 802.11 and 5 G NR are systematic. For network communications, the retransmission-based end-to-end reliability scheme can be regarded as a systematic code. The benefits of the systematic codes are also attractive for practical applications of batched network codes, especially for latency-sensitive applications [28; 29; 30].  
Different from systematic channel coding, systematic batched network coding needs to take both the outer code and the inner code into consideration. Though not optimal in general, an overlapping outer code with batches formed by subsets of the message packets proposed in [15; 16; 17; 20] is already systematic in the sense that the union of some batches includes all the message packets. However, even with a systematic outer code, the benefits of systematic codes cannot be obtained due to network coding: using random linear coding at the intermediate nodes prevents the reception of the message packets at the destination nodes. The problem cannot be solved by simply excluding the message packets from network coding, which reduces the benefits of network coding. Most existing works on systematic RLNC focus on encoding and decoding at the source node and destination nodes, respectively, without considering network coding at the intermediate nodes [31; 32; 33; 34; 35; 36].  
In this paper, we study systematic batched network codes that have a systematic outer code and an inner code that can preserve the benefits of the systematic outer code. Our contributions are summarized as follows.