Non-coherent Network Coding: An Arbitrarily Varying Channel Approach

In this paper, we propose an “arbitrarily varying channel” (AVC) approach to study the capacity of non-coherent transmission in a network that employs randomized linear network coding. The network operation is modeled by a matrix channel over a finite field where the transfer matrix changes arbitrarily from time-slot to time-slot but up to a known distribution over its rank. By extending the AVC results to this setup, we characterize the capacity of such a non-coherent transmission scheme and show that subspace coding is optimal for achieving the capacity. By imposing a probability distribution over the state space of an AVC, we obtain a channel which we called “partially arbitrarily varying channel” (PAVC). In this work, we characterize the “randomized” as well as the “deterministic” code capacity of a PAVC under the average error probability criterion. Although we introduce the PAVC to model the non-coherent network coding, this extension to an AVC might be of its own interest as well.