Hartung-Gorre Verlag

Inh.: Dr. Renate Gorre

D-78465 Konstanz

Fon: +49 (0)7533 97227

Fax: +49 (0)7533 97228



ETH Series in Information Theory and its Applications, Vol. 9
edited by Amos Lapidoth




Tibor Keresztfalvi


Some Data are More Important than Others


1st edition 2018. XIV, 110 pages, € 64,00.

ISBN 978-3-86628-625-2
















This thesis is comprised of two parts. Both parts study informationtheoretic aspects of joint transmission of data of different levels of sensitivity. The more sensitive data is better protected than the less sensitive data. In the first part the data streams have different robustness criteria with respect to variations of the underlying channel model, and in the second part, the data streams have different decoding error requirements.

In the first part, we establish the deterministic-code capacity region of a network with one transmitter and two receivers: an “ordinary receiver” and a “robust receiver.” The channel to the ordinary receiver is a given (known) discrete memoryless channel, whereas the channel to the robust receiver is an arbitrarily varying channel. Both receivers are required to decode the “common message” (the more sensitive data), whereas only the ordinary receiver is required to decode the “private message” (the less sensitive data).

In the second part, two independent data streams are to be transmitted over a noisy discrete memoryless channel: the “zero-error stream” (the more sensitive data) and the “rare-error stream” (the less sensitive data). Errors are tolerated only in the rare-error stream, provided that their probability tends to zero as the blocklength tends to infinity.

If the encoder has access to a noiseless feedback link from the output of the channel, the rate of the zero-error stream cannot, of course, exceed the channel’s zero-error feedback capacity, and nor can the sum of the streams’ rates exceed the channel’s Shannon capacity. Using a suitable feedback coding scheme, these necessary conditions are shown to characterize all the achievable rate pairs and thus the multiplexing capacity region with feedback. Planning for the worst—as is needed to achieve zero-error communication—and planning for the true channel— as is needed to communicate near the Shannon limit—are thus not incompatible.

If the encoder has no feedback, computing the multiplexing capacity region is at least as hard as computing the zero-error capacity of a discrete memoryless channel. We present some outer bounds that show that feedback may be beneficial for the multiplexing problem even on channels on which it does not increase the zero-error capacity.


Keywords: Unequal error protection, arbitrarily varying channel, broadcast channel, degraded message set, robust communications, feedback, multiplexing, Shannon capacity, zero-error capacity.



About the Author


Tibor Keresztfalvi was born in Budapest, Hungary on 24 September 1991. He attended elementary school in Arlesheim, Switzerland, and high school in Budapest, Hungary with a specialization in mathematics. During this time he attended various national mathematic competitions in Hungary.

In 2010, after graduating high school, he moved back to Switzerland and entered ETH Zurich to study Electrical Engineering and Information Technology. There he obtained his Bachelor degree in 2013.

He continued his studies with focus on communications at ETH Zurich. During that time he spent an exchange semester at University of Pennsylvania, Philadelphia where in addition to his field of specialization he took courses at the Wharton Business School. He also became interested in information theory and wrote his master thesis in this field. He obtained his masters degree in 2013.

Since 2015, he has been a PhD candidate and full research assistant at the Signal and Information Processing Laboratory (ISI) at ETH Zurich under the supervision of Prof. Dr. Amos Lapidoth.


Reihe "ETH Series in Information Theory and its Applications" im Hartung-Gorre Verlag


Direkt bestellen bei / to order directly from:

Hartung-Gorre Verlag / D-78465 Konstanz / Germany

Telefon: +49 (0) 7533 97227  Telefax: +49 (0) 7533 97228
http://www.hartung-gorre.de   eMail: verlag@hartung-gorre.de