ML p(r)ior | The Capacity of Online (Causal) $q$-ary Error-Erasure Channels

### The Capacity of Online (Causal) $q$-ary Error-Erasure Channels

2016-01-31
1602.00276 | cs.IT
In the $q$-ary online (or "causal") channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword $\mathbf{x} =(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 $\mathbf{x}$. 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^{*}$.

Highlights - Most important sentences from the article

# Related Articles

2019-04-26
1904.11925 | cs.IT

We study communication over multiple access channels (MAC) where one of the users is possibly advers… show more

Highlights - Most important sentences from the article

2019-01-28
1901.09646 | cs.IT

Concurrent coding is an unconventional encoding technique that simultaneously provides protection ag… show more

Highlights - Most important sentences from the article

2018-02-13
1802.04719 | cs.IT

As an attempt to bridge the gap between the probabilistic world of classical information theory and … show more

Highlights - Most important sentences from the article

2019-01-06
1901.01573 | cs.IT

Previous works on age of information and erasure channels have dealt with specific models and comput… show more

Highlights - Most important sentences from the article

2018-11-23
1811.09695 | cs.IT

We develop a low-complexity coding scheme to achieve covert communications over binary-input discret… show more

Highlights - Most important sentences from the article

2018-10-18
1810.08161 | cs.IT

We extend the notion of list decoding to {\em ratio list decoding} which involves a list decoder who… show more

Highlights - Most important sentences from the article

2017-01-21
1701.06085 | cs.IT

A binary matrix is called an s-separable code for the disjunctive multiple-access channel (disj-MAC)… show more

Highlights - Most important sentences from the article

2017-01-24
1701.06969 | cs.IT

Highlights - Most important sentences from the article

2018-11-29
1811.11932 | cs.IT

This paper studies the joint design of optimal convolutional codes (CCs) and CRC codes when serial l… show more

Highlights - Most important sentences from the article

2019-01-09
1901.02590 | cs.IT

In this paper, we propose a new concept of secure list decoding. While the conventional list decodin… show more

Highlights - Most important sentences from the article

2018-08-28
1808.09556 | cs.IT

Highlights - Most important sentences from the article

2019-01-12
1901.03790 | cs.IT

We study the list decodability of different ensembles of codes over the real alphabet under the assu… show more

Highlights - Most important sentences from the article

2017-01-30
1701.08783 | cs.IT

In this paper, the trade-off between the number of transmissions (or burstiness) $K_n=e^{n\nu}$ of a… show more

Highlights - Most important sentences from the article

2016-12-19
1612.06335 | cs.IT

We consider binary error correcting codes when errors are deletions. A basic challenge concerning de… show more

Highlights - Most important sentences from the article

2013-09-02
1309.0458 | cs.IT

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), encode messages $s$ i… show more

Highlights - Most important sentences from the article

2013-09-04
1309.1151 | cs.IT

Non-malleable coding, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), aims for protecting … show more

Highlights - Most important sentences from the article