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

DOI10.1109/TIT.2019.2898863zbMATH Open1432.94094arXiv1602.00276OpenAlexW2912210351MaRDI QIDQ5224005FDOQ5224005

Zitan Chen, Michael Langberg, Sidharth Jaggi

Publication date: 19 July 2019

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: In the $q$-ary online (or "causal") channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword $mathbfx=(x_1,ldots,x_n)in{0,1,ldots,q-1}^n$ symbol by symbol via a channel limited to at most $pn$ errors and/or $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 $(x_1,ldots,x_i)$. This is in contrast to the classical adversarial channel in which the corruption is chosen by a channel that has a full knowledge on the sent codeword $mathbfx$. In this work we study the capacity of $q$-ary online channels for a combined corruption model, in which the channel may impose at most $pn$ {em errors} and at most $p^{*}n$ {em 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 work, we give a full characterization of the capacity as a function of $q,p$, and $p^{*}$.

Full work available at URL: https://arxiv.org/abs/1602.00276

Recommendations

• A characterization of the capacity of online (causal) binary channels
• Asymptotics of Input-Constrained Erasure Channel Capacity
• scientific article; zbMATH DE number 493103
• An Upper Bound on the Capacity of the Causal Dirty-Paper Channel
• Capacity-achieving sequences for the erasure channel
• Capacities of Quantum Erasure Channels
• On the capacity of a cascade of identical discrete memoryless nonsingular channels (Corresp.)
• On the Capacity of the Noncausal Relay Channel
• Capacity-Achieving Ensembles for the Binary Erasure Channel With Bounded Complexity
• Upper Bounds on the Capacity of Binary Channels With Causal Adversaries

zbMATH Keywords

causal channel coding modelcombined corruption modelfull characterization of the capacityq-ary online channel coding model

Mathematics Subject Classification ID

Coding theorems (Shannon theory) (94A24) Channel models (including quantum) in information and communication theory (94A40)

Cited In (1)

• Upper Bounds on the Capacity of Binary Channels With Causal Adversaries

This page was built for publication: The Capacity of Online (Causal) $q$ -Ary Error-Erasure Channels

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5224005)