The Capacity of Online (Causal) q-Ary Error-Erasure Channels

In the q-ary online (or 'causal') channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword x =(x1,⋯,xn) ϵ {0,1,⋯,q-1 n symbol-by-symbol via a channel limited to at most pn errors and p∗ n erasures. The channel is 'online' in the sense that at the i th step of communication the channel decides whether to corrupt the i th symbol or not based on its view so far, i.e., its decision depends only on the transmitted symbols (x1,⋯,xi). This is in contrast to the classical adversarial channel in which the corruption is chosen by a channel that has full knowledge of the sent codeword x. In this paper, we study the capacity of q-ary online channels for a combined corruption model, in which the channel may impose at most pn errors and at most p∗ n erasures on the transmitted codeword. The online channel (in both the error and erasure case) has seen a number of recent studies, which present both upper and lower bounds on its capacity. In this paper, we give a full characterization of the capacity as a function of q,p, and p∗.