On Codes and Lattices

Sueli I. R. Costa (State University of Campinas)

It will be given an introduction to q-ary codes, their properties and examples. Lattices will be presented with the fundamental concepts of generator and Gram matrices, packing density, dual lattices, and theta series. Quantization, AWGN codes and associations between codes and lattices (Constructions A and B) considered in different metrics will be approached. Some applications to spherical codes and highsuelis to other applications to be developed in two following short-courses will also be presented.

On Codes and Lattices

Sueli I. R. Costa (State University of Campinas)

It will be given an introduction to q-ary codes, their properties and examples. Lattices will be presented with the fundamental concepts of generator and Gram matrices, packing density, dual lattices, and theta series. Quantization, AWGN codes and associations between codes and lattices (Constructions A and B) considered in different metrics will be approached. Some applications to spherical codes and highsuelis to other applications to be developed in two following short-courses will also be presented.

Introduction to Network Coding

Danilo Silva (Federal University of Santa Catarina)

This tutorial will review the basic principles of network coding, as well as some of its applications, challenges and related problems. Special attention will be given to two problems where algebraic codes (namely, rank-metric codes and lattice codes) have important applications: network error/erasure correction and wireless physical-layer network coding.

Introduction to Network Coding

Danilo Silva (Federal University of Santa Catarina)

This tutorial will review the basic principles of network coding, as well as some of its applications, challenges and related problems. Special attention will be given to two problems where algebraic codes (namely, rank-metric codes and lattice codes) have important applications: network error/erasure correction and wireless physical-layer network coding.

Introduction to Information Theory (aka IT in a nutshell)

Max Costa (University of Campinas)

This is intended to be a brief introduction to Information Theory (IT), one of the jewels of 20th Century Applied Mathematics, with rich transdisciplinary implications. We start with some definitions: entropy, relative entropy (Kullback Leibler distance), mutual information, and differential entropy. Then we see a simple and intuitive relation that has surprisingly strong consequences, the data processing inequality (DPI). Next we visit what I consider to be the DNA of IT, the asymptotic equipartition property (AEP). We then look at some applications in source coding and channel coding, with highlight to some simple codes of both kinds. We plan to close with some multiple user variations of the theme, such as distributed source coding (Slepian-Wolf), multiple access channels, broadcast channels and interference channels.

Introduction to Information Theory (aka IT in a nutshell)

Max Costa (University of Campinas)

This is intended to be a brief introduction to Information Theory (IT), one of the jewels of 20th Century Applied Mathematics, with rich transdisciplinary implications. We start with some definitions: entropy, relative entropy (Kullback Leibler distance), mutual information, and differential entropy. Then we see a simple and intuitive relation that has surprisingly strong consequences, the data processing inequality (DPI). Next we visit what I consider to be the DNA of IT, the asymptotic equipartition property (AEP). We then look at some applications in source coding and channel coding, with highlight to some simple codes of both kinds. We plan to close with some multiple user variations of the theme, such as distributed source coding (Slepian-Wolf), multiple access channels, broadcast channels and interference channels.

Introduction to Convolutional Codes

Reginaldo Palazzo Jr (University of Campinas)

1) Upper and lower bounds on the error probability: Shannon channel coding theorem,random coding argument, cut-off rate with two codewords.

2) Convolutional codes topological structure: Tree codes, Trellis codes, distance properties.

3) Classes of convolutional codes: specific convolutional codes, unit-memory convolutional codes, M-ary convolutional codes, punctured convolutional codes.

4) Transfer function bounds for fixed convolutional codes: discrete-time model, Viterbi algorithm, error events, average distortion, evaluation of the transfer function, examples.

5) Periodically time-varying convolutional codes: construction of periodically time-varying convolutional codes, distance properties, codeword enumeration function.

Structure of the capacity region and its use in multiuser systems

Ninoslav Marina (Haute Ecole ARC)

In this tutorial we will describe the structure of the capacity region of the asynchronous memoryless multiple access channel. The asynchronous capacity region of memoryless multiple-access channels is the union of certain polytopes. It is well-known that vertices of such polytopes may be approached via a technique called successive decoding. It is also known that an extension of successive decoding applies to the dominant face of such polytopes. The extension consists of forming groups of users in such a way that users within a group are decoded jointly whereas groups are decoded successively. We show that successive decoding extends to every face of the above mentioned polytopes. The group composition as well as the decoding order for all rates on a face of interest are obtained from a label assigned to that face. From this label one can extract a number of geometrical properties, such as the dimension of the corresponding face and whether or not two faces intersect. Expressions for the number of faces of any given dimension are also derived from the labels. We explain also the derivation of the total number of vertices (faces of dimension zero) in the capacity region, that equals floor(eM!).

Wireless Network Coding: Algorithms and Applications

Alex Sprintson (Texas A&M)

This mini-course will provide basic and in-depth knowledge of the rapidly evolving area of wireless network coding. It will cover concepts, theories, and solutions for a broad range of wireless network coding problems as well as a comprehensive survey of practical applications of networking coding in various areas of wireless networking. We will cover fundamental wireless network coding problems such as Index Coding and Coded Cooperative Data Exchange problems. We will emphasize the security aspects of the problems. The mini-course will emphasize deep connections between network coding and other areas of information theory, complexity theory, graph theory, matroid theory, and coding theory. We will provide a comprehensive survey of discoveries and insights gained from years of intensive research and discuss open problems and present new exciting opportunities in wireless coding research and applications. The mini course will enable the students to get familiar with the recent developments and pursue research in this exciting area.

Wireless Network Coding: Algorithms and Applications

Alex Sprintson (Texas A&M)

This mini-course will provide basic and in-depth knowledge of the rapidly evolving area of wireless network coding. It will cover concepts, theories, and solutions for a broad range of wireless network coding problems as well as a comprehensive survey of practical applications of networking coding in various areas of wireless networking. We will cover fundamental wireless network coding problems such as Index Coding and Coded Cooperative Data Exchange problems. We will emphasize the security aspects of the problems. The mini-course will emphasize deep connections between network coding and other areas of information theory, complexity theory, graph theory, matroid theory, and coding theory. We will provide a comprehensive survey of discoveries and insights gained from years of intensive research and discuss open problems and present new exciting opportunities in wireless coding research and applications. The mini course will enable the students to get familiar with the recent developments and pursue research in this exciting area.

Explicit Lattice Constructions: From Codes to Number Fields

Frédérique Oggier (Nanyang Technological University) and Jean-Claude Belfiore (Télécom Paris Tech)

We start this course by presenting wiretap lattice codes for Gaussian channels. To analyze and design such codes, we will explain:

- the notion of a dual lattice, and of l-modular lattices

- theta series and Jacobi Poisson summation for lattices

- lattice coset encoding

- extended construction A of lattices from number fields

Lattice Coding for Signals and Networks

Ram Zamir (Tel Aviv University)

It will cover some of the following topics:

- dithering, generalized dither and the "crypto lemma"

- entropy-coded dithered lattices quantization

- infinite constellations and probabilistic shaping

- existence of good (high-dimensional) lattices

- Voronoi codes, shaping and lattice decoding with Wiener estimation

- Side information problems (lattice Wyner-Ziv and dirty-paper coding)

- modulo-lattice modulation (joint source-channel coding)

Lattice Coding for Signals and Networks

Ram Zamir (Tel Aviv University)

It will cover some of the following topics:

- dithering, generalized dither and the "crypto lemma"

- entropy-coded dithered lattices quantization

- infinite constellations and probabilistic shaping

- existence of good (high-dimensional) lattices

- Voronoi codes, shaping and lattice decoding with Wiener estimation

- Side information problems (lattice Wyner-Ziv and dirty-paper coding)

- modulo-lattice modulation (joint source-channel coding)

Simple Tools for an Information Theory for Large Networks

Michelle Effros (Caltech)

The goal of expanding information theory from the study of very small networks to the understanding of extremely large networks is understood to be both critically important and insurmountably difficult. This talk considers the challenges faced and some simple tools for tackling them.

Spatial Coupling - A Primer

Rudiger Urbanke (EPFL)

Designing good sparse-graph codes is the problem of finding graphical structures that interact well with the message-passing decoder. Over the past 20 years many such structures have been proposed and have been found to be useful. Prominent examples of structures that work well are turbo codes, low-density parity-check codes with properly chosen degree distributions, or multi-edge ensembles.
I will talk about a further such structure which emerges if we "couple" several of our favorite graphical models along a spatial dimension. Here, "coupling" means that we connect neighbouring graphical models and we do it in such a way that the local connectivity of the graphs stays undisturbed. Due to this spatial structure, and a well chosen boundary condition, such graphical models behave under iterative decoding as well as if one had taken one of the underlying components and decoded it in an optimal fashion. I will explain why this happens and how we can take advantage of this effect. As I will discuss, this is the same phenomenon which is responsible for crystal growth and the formation of hail.
Although most of this talk will center on how to design good error correcting codes, the principle of spatial coupling can also be used in other areas (such as compressive sensing or constraint satisfaction problems). Time permitting, I will briefly paint the broader picture.

Optimality of Gaussian auxiliaries via single-letterization arguments

Chandra Nair (Chinese University of Hong Kong)

In this tutorial we will visit a recently developed technique that establishes the optimality of Gaussian (auxiliary) random variables. This technique combines a characterization of Gaussian random variables (known since 1940s) and single-letterization arguments that form the central body of converses to coding theorems or outer bounds. The technique will be introduced via well-known examples and the power will be illustrated by using it to obtain the capacity region of vector Gaussian broadcast channels with common information; a scenario that had resisted attempts using traditional techniques.

Spatial Coupling - A Primer

Rudiger Urbanke (EPFL)

Designing good sparse-graph codes is the problem of finding graphical structures that interact well with the message-passing decoder. Over the past 20 years many such structures have been proposed and have been found to be useful. Prominent examples of structures that work well are turbo codes, low-density parity-check codes with properly chosen degree distributions, or multi-edge ensembles.
I will talk about a further such structure which emerges if we "couple" several of our favorite graphical models along a spatial dimension. Here, "coupling" means that we connect neighbouring graphical models and we do it in such a way that the local connectivity of the graphs stays undisturbed. Due to this spatial structure, and a well chosen boundary condition, such graphical models behave under iterative decoding as well as if one had taken one of the underlying components and decoded it in an optimal fashion. I will explain why this happens and how we can take advantage of this effect. As I will discuss, this is the same phenomenon which is responsible for crystal growth and the formation of hail.
Although most of this talk will center on how to design good error correcting codes, the principle of spatial coupling can also be used in other areas (such as compressive sensing or constraint satisfaction problems). Time permitting, I will briefly paint the broader picture.

Optimality of Gaussian auxiliaries via single-letterization arguments

Chandra Nair (Chinese University of Hong Kong)

In this tutorial we will visit a recently developed technique that establishes the optimality of Gaussian (auxiliary) random variables. This technique combines a characterization of Gaussian random variables (known since 1940s) and single-letterization arguments that form the central body of converses to coding theorems or outer bounds. The technique will be introduced via well-known examples and the power will be illustrated by using it to obtain the capacity region of vector Gaussian broadcast channels with common information; a scenario that had resisted attempts using traditional techniques.