The capacity of online (causal) q-ary error-erasure channels

In the q-ary online (causal) channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x
1
, Ω, x
n
) ∈ {0, 1, Ω, q ™ 1}
ⁿ
symbol-by-symbol via a channel limited to at most pn errors (symbol changes) and p
^⋆
n erasures. The channel is “online” (i.e., “causal”) in the sense that at the ith step of communication the channel decides whether to corrupt the ith symbol or not only based on its view of the symbols (x
1
, Ω, x
i
). This is in contrast to the classical adversarial channel in which the corruption is chosen with full knowledge of the sent codeword x. In this work we extend the results obtained in [1]–[4] (in which the capacities of binary online bit-flip-only channels, and separately binary online erasure-only channels were characterized). We here extend those prior results in two important ways. First, we obtain the capacity of q-ary online channels for general q (rather than just q = 2). Second, we analyze combined error-erasure corruption models (rather than studying them separately). Characterization of this much broader class of symmetric online channels gives a fuller understanding of the effects of causality on jamming adversaries. The extensions in this paper require novel approaches for both optimal code designs, and matching information-theoretic converse arguments.