## Introduction to Zero-Error Information Theory (Exercise)

Lecturer (assistant) 0000004754 Exercise 2 SWS Sommersemester 2019 German See TUMonline See TUMonline

### Objectives

After passing the course, the student is familiar with the basic problems and methods of zero-error information theory. This allows him/her an in-depth study of the presented areas. Further, he/she can successfully apply combinatorial methods in information theory and information theoretic methods in combinatorics, respectively.

### Description

This module gives an introduction to various problems in zero-error information theory, which is at the intersection between information theory and combinatorics/graph theory. In zero-error information theory, it is required that messages are transmitted over a noisy channel with error probability 0, where the channel is discrete and memoryless. Zero-error capacity both with and without feedback is studied. Since no closed formula for zero-error capacity without feedback is known, upper bound are studied extensively. It can be calculated for some special cases, and properties like additivity are studied for the general case. Zero-error capacity with feedback is characterized completely. The necessary methods from graph theory are introduced in the course as well.

### Prerequisites

Mathematics 1-4, Information theory, Interest for mathematics

### Teaching and learning methods

In der Vorlesung wird die grundlegende Theorie der Zero-Error Informationstheorie anhand einer Tafelpräsentation des Dozenten vorgestellt und erklärt. Dazu zählt insbesondere 1) das Einführen notwendiger Begriffe und Notationen 2) das Vorstellen, Beweisen, und Erklären wichtiger Resultate und mathematischer Sätze 3) die Darstellung, wie die Theorie auf konkrete Fragestellungen der Informationstheorie angewendet werden kann In den Übungen sollen die Studenten durch das selbständige and angeleitete Lösen von Übungsaufgaben aus der Zero-Error Kapazität 1) ihr Wissen festigen 2) lernen die gewonnen Erkenntnisse auf konkrete Fragestellungen der Informationstheorie anzuwenden 3) lernen und erkennen wo der Einsatz von kombinatorischen Methoden in der Informationstheorie vorteilhaft sein kann

### Examination

Die Modulprüfung wird in Form einer mündlichen Prüfung erbracht. In dieser soll durch das Beantworten von Fragen nachgewiesen werden, dass man die grundlegenden Probleme und Methoden der Zero-Error-Informationstheorie kennt und auf konkrete Fragestellungen anwenden kann. Die Beantwortung der Fragen schließt kurze Rechnungen und Beweisskizzen mit ein. In der Prüfung sind keine Hilfsmittel zugelassen.

### Recommended literature

J. Körner, A. Orlitsky, "Zero-error information theory", IEEE Transactions on Information Theory, vol. 44, no. 6, S. 2207-2229, 1998. C. E. Shannon, “The zero-error capacity of a noisy channel,” IRE Transactions on Information Theory, vol. IT-2, S. 8-19, 1956. L. Lovász, “On the Shannon capacity of a graph,” IEEE Transactions on Information Theory, vol. IT-25, S. 1-7, 1979.