Batched network coding is a solution to reliable communications in multi-hop networks with packet loss. Adaptive recoding is a technique to enhance the throughput of batched network coding. Two pieces of information is needed to apply adaptive recoding: the distribution of the information remained in the received batches and the channel condition of the outgoing link. A simple way to obtain the former information is to make a short observation by grouping a few batches into a block. This way to apply adaptive recoding is called blockwise adaptive recoding (BAR), which can achieve a nice throughput even when the block size is small. Previous literature assumes that the latter information is known in advance and would not be changed over time. However in practice, these assumptions do not hold in general. In this paper, we investigate the impact of inaccurate channel condition on BAR and show by numerical evaluations that the throughput is very close to the one with accurate channel condition. To adapt the varying channel condition, we also propose a feedback scheme for BAR and a method to reduce the computational time for BAR.

Batched network coding (BNC) is a low-complexity solution to network transmission in multi-hop packet networks with packet loss. BNC encodes the source data into batches of packets. As a network coding scheme, the intermediate nodes perform recoding on the received packets belonging to the same batch instead of just forwarding them. A recoding scheme that may generate more recoded packets for batches of a higher rank is also called adaptive recoding. Meanwhile, in order to combat burst packet loss, the transmission of a block of batches can be interleaved. Stream interleaving studied in literature achieves the maximum separation among any two consecutive packets of a batch, but permutes packets across blocks and hence cannot bound the buffer size and the latency. To resolve the issue of stream interleaver, we design an intrablock interleaver for adaptive recoding that can preserve the advantages of using a block interleaver when the number of recoded packets is the same for all batches. We use potential energy in classical mechanics to measure the performance of an interleaver, and propose an algorithm to optimize the interleaver with this performance measure. Our problem formulation and algorithm for intrablock interleaving are also of independent interest.

Zero-error single-channel source coding has been studied extensively over the past decades. Its natural multi-channel generalization is however seldom investigated. While the special case with multiple symmetric-alphabet channels was studied a decade ago, codes in such setting have no advantage over single-channel codes in data compression, making them worthless in most applications. With essentially no development since the last decade, in this paper, we break the stalemate by showing that it is possible to beat single-channel source codes in terms of compression assuming asymmetric-alphabet channels. We present the multi-channel analogs of several classical results in single-channel source coding, e.g., a multi-channel Huffman code is an optimal tree-decodable code. We also show evidences that finding an efficient construction of multi-channel Huffman codes may be hard. Nevertheless, we propose a construction whose redundancy is guaranteed to be no larger than that of an optimal single-channel source code.

Although n-channel prefix-free codes are natural extensions of their 1-channel counterpart, the extra dimensions greatly increase the complexity of the problem such that most classical results cannot be generalized directly. Recently, a greedy algorithm was developed for deciding if it is possible to construct a 2-channel prefix-free code from a given multiset of codeword lengths. By dropping the information about codeword assignments which are not necessary for the decision problem, the greedy algorithm runs in polynomial time. However, if we naively turn the decision algorithm into a search algorithm (for constructing a prefix-free code) by retaining the information about codeword assignments, the computational complexity becomes exponential. One puzzle left unsolved was that whether the search problem can also be solved in polynomial time. In this paper, we give an affirmative answer to this question by designing a tailor-made data structure and a new lazy evaluation technique.

Wireless relay network is a solution for transmitting information from a source node to a sink node far away by installing a relay in between. The broadcasting nature of wireless communication allows the sink node to receive part of the data sent by the source node. In this way, the relay does not need to receive the whole piece of data from the source node and it does not need to forward everything it received. In this paper, we consider the application of batched network coding, a practical form of random linear network coding, for a better utilization of such a network. The amount of innovative information at the relay which is not yet received by the sink node, called the innovative rank, plays a crucial role in various applications including the design of the transmission scheme and the analysis of the throughput. We present a visualization of the innovative rank which allows us to understand and derive formulae related to the innovative rank with ease.

Batched network coding is a practical branch of random linear network coding which encodes the input file into small batches of coded packets. Although burst erasures within the batches can reduce the advantage of network coding, it can be alleviated by applying a block interleaver which spreads the burst across multiple batches. On the other hand, the intermediate network nodes are required to perform recoding on the batches unlike the traditional forwarding strategy. The recoding of a batch can be started once all the packets in that batch which are not dropped by the channel are received. This means that the intermediate network nodes have to deinterleave the batches for recoding and reinterleave the batches again for transmission, which gives us a choice to use different interleaver depths at different network nodes. In this paper, we study the memory requirements of the schemes for transmitting batches which apply different interleaver depths. We investigate the periodic structure of buffer sizes and the connection between buffer sizes and the total delay induced by the interleaver. More importantly, we show that there exists a scheme which can achieve the lowest memory requirement and minimum total delay simultaneously.

The Kraft inequality gives a necessary and sufficient condition for the existence of a single channel prefix-free code. However, the multichannel Kraft inequality does not imply the existence of a multichannel prefix-free code in general. It is natural to ask whatever there exists an efficient decision procedure for the existence of multichannel prefix-free codes. In this paper, we tackle the two-channel case of the above problem by relating it to a constrained rectangle packing problem. Although a general rectangle packing problem is NP-complete, the extra imposed constraints allow us to propose an algorithm which can solve the problem efficiently.

Batched network coding is a practical realization of random linear network coding, which encodes the packets for transmission into small batches of coded packets. The advantage of network coding can be reduced when a burst loss occurs. Block interleaver is one of the approach to spread the burst across multiple batches. However, an intermediate node has to receive all the packets in a batch which are not dropped by the channel before it can perform recoding on the batch, which means that the node has to deinterleave for recoding and reinterleave again for transmission. This gives us the freedom to select heterogeneous interleaver depth among the intermediate nodes. In general, the larger the interleaver depth, the better the spread of the bursts. On the other hand, we want the delay as short as possible to enable real-time applications. In this paper, we investigate the delay induced by applying a block interleaver on batched network codes. We also show that a homogeneous interleaver depth is the largest interleaver depth we can use to achieve a minimum delay.

Batched network coding is a variation of random linear network coding which has low computational and storage costs. In order to adapt random fluctuations in the number of erasures in individual batches, it is not optimal to recode and transmit the same number of packets for all batches. Different distributed optimization problems, which are called adaptive recoding, were formulated for this purpose. The key component of these optimization problems is the expected value of the rank distribution of a batch at the next network node, which also known as the expected rank. In this paper, we put forth a unified adaptive recoding framework. We show that the expected rank functions are concave when the packet loss pattern follows a stationary stochastic process regardless of the field size, which covers but not limited to independent packet loss and burst packet loss. Under this concavity property, we show that there always exists a preferred solution which not only can make the number of recoded packets almost deterministic but can also tolerate rank distribution errors due to inaccurate measurements or limited precision of the machine. To obtain such an optimal solution, we propose tuning schemes that can turn any feasible solution into one with the above desired properties.

BATS codes are a class of random linear network coding scheme which have close-to-optimal achievable rates, while adaptive recoding is a packet combining scheme which adds a boost to the throughput by adapting the packet combining at the relay to the random fluctuations in the number of erasures in individual batches. In this paper, we apply BATS code with adaptive recoding for the transmission on wireless relay network. In contrast to the existing adaptive recoding schemes, we propose a model which can make use of the broadcast nature of wireless communication to enhance the achievable rates via overhearing. We also optimize the packet efficiency, i.e., minimizing the average number of channel use for each input packet for a successful decoding.