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

Christoph Bunte

**Error-Free Source and Channel Coding with Lists**

1st edition 2014. XII, 110 pages, € 64,00.

ISBN 978-3-86628-503-3

**Abstract**

This
thesis is comprised of three independent parts.

In
the first part, a source-coding problem is studied, where a task that is
randomly drawn from a finite set of tasks is to be described using a fixed
number of bits. All the tasks that share its description must be performed.
Upper and lower bounds on the minimum ** ρ**-th
moment of the number of performed tasks are derived. The case where a sequence
of tasks is produced by a source and

The
second part of this thesis studies the listsize
capacity of discrete memoryless channels with
feedback. The listsize capacity is the supremum of achievable rates, where achievable means that
the *ρ**
*-th moment of the number
of messages that could have produced the output of the channel approaches one
as the blocklength tends to infinity. It is shown
that for channels with feedback this rate is upper-bounded by the maximum of Gallager’s *E*** _{0}**
function divided by

The
third part of this thesis contains a proof of a conjecture by Ahlswede, Cai,
and Zhang on the relationship between the zero-undetected-error capacity of
almost noise-free channels and the Sperner capacity
of directed graphs. The zero-undetected-error capacity is the supremum of achievable rates when the decoder must either
produce the correct message or declare an erasure, where achievable means that
the erasure probability tends to zero as the blocklength
tends to infinity. Sperner capacity is a
generalization of Shannon’s graph capacity to directed graphs. Ahlswede, Cai,
and Zhang proved that, in the noise-free limit, the zeroundetected-
error capacity is lower bounded by the Sperner
capacity of the channel graph, and they conjectured equality. Here an upper
bound is derived that proves the conjecture.

**Keywords: **Cutoff rate, directed graphs, discrete memoryless
channels, erasures, feedback, lists, Rényi entropy, Sperner capacity, tasks, undetected errors.

**About the
Author**

Christoph Bunte was born in Bremen, Germany, on June 19, 1984. He
received the BSc and MSc degrees in electrical engineering from ETH Zurich in
2010 and 2011. In May 2011 he joined the Signal and Information Processing
Laboratory at ETH Zurich as a PhD student and research assistant.

Direkt bestellen
bei / to order directly from: Hartung.Gorre@t-online.de

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

**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**