Recent interest in coding problems for memory and storage applications gave rise to some new questions of coding theory, expanding the traditional problems to new metric spaces as well as placing new restrictions on decoding algorithms of codes. We explore some of these problems, focusing on coding in the space of permutations (this problem is motivated by a coding scheme for flash memories) and codes with the local recovery property, motivated by large-scale storage applications.

Hide this content.

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.

Hide this content.

Modern electronic devices consist of a multitude of IC components: the processor, the memory, the RF modem and the baseband chip (in wireless devices), and the graphics processor, are only some examples of components scattered throughout a device. The increase of the volume of digital data that needs to be accessed and processed by such devices calls for ever faster communication between these IC's. Faster communication, however, often translates to higher susceptibility to various types of noise, and inevitably to a higher power consumption in order to combat the noise. This increase in power consumption is, for the most part, far from linear, and cannot be easily compensated for by Moore's Law. In this talk I will give a short overview of problems encountered in chip-to-chip communication, and will advocate the use of novel coding techniques to solve those problems. I will also briefly talk about Kandou Bus, and some of the approaches the company is taking to design, implement, and market such solutions.

Hide this content.

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.

Hide this content.

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.

Hide this content.

In some communication or storage applications errors tend to cluster in so called bursts. Codes that can correct a burst of length b need less redundancy than error-correcting codes that correct b random errors.
Research on burst-correcting codes peaked in the sixties and then again 25 years later. We shall start with a brief introduction to coding theory and then proceed with an overview of the most commonly used burst-correcting techniques. In particular, the following classical methods will be discussed: interleaving, concatenated codes, and Fire codes.
After that we present array codes, which have low decoding complexity, and conclude by showing how a 24 years old open problem concerning optimal, cyclic burst-correcting codes has been solved in a very satisfactory way.

Authentication codes

The name authentication code was introduced by G. Simmons in 1992. The goal is to authenticate messages in an unconditionally secure way. An authentication code is designed to protect a message against an impersonation attack or a substitution attack and typically can be used only once. Sometimes also privacy needs to be guaranteed.
Already in 1974 such codes were described by Gilbert e.a. Their code is even “perfect”, meaning that the probability of a successful impersonation and substitution is minimal. That does not mean that these codes are practical: keys are twice as long as messages.
Johansson e.a. showed in 1994 how error-correcting codes can be used to construct authentication codes (and vice-versa). Also later work, among others by Ding e.a., will be discussed.

Other connections between coding theory and cryptography

The Berlekamp-Massey algorithm is based on the decoding algorithm for BCH codes.
AES uses Reed-Solomon codes.
Secret sharing schemes use Reed-Solomon codes.

Hide this content.

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

Hide this content.

The goal of this course is to give a general overview of the basic building blocks of information- theoretic security and how they can be used to provide authentication, confidentiality and integrity at the physical layer of modern communication systems. Starting from first principles and fundamental performance bounds, we shall elaborate on the code constructions needed to achieve reliability and secrecy simultaneously and how to build secure communication protocols that leverage the additional secrecy provided by these code constructions. Finally, we will discuss how to integrate these techniques in existing standards and provide a basic cost-benefit analysis.

Hide this content.

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.

Hide this content.

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.

Hide this content.

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!).

Hide this content.

Post-quantum cryptosystems are those purely classical cryptosystems which are able, in principle, to resist attacks mounted with the help of quantum computers. Code-based cryptographic protocols are among the main proposed families of such systems, as certain constructions have withstood cryptanalysis largely unscathed since the concept was proposed by McEliece in 1978, and evidence has been found that quantum Fourier sampling, the strategy adopted in all quantum attacks known against more conventional cryptosystems, cannot possibly work against code-based alternatives. Recent engineering progress also show that code-based encryption is not only viable, but can be made fairly efficient even on the constrained platforms typical of the Internet of Things. This short course aims at introducing the essentials of code-based cryptography, from the basic protocols and supporting algorithms to the choice of parameters for actually deployable schemes, according to the state of the art.

Hide this content.

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)

Hide this content.

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.

Download: Slides

Hide this content.

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.

Hide this content.

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 highlights to other applications to be developed in two following short-courses will also be presented.

Hide this content.

Basic Concepts

Introduction; Types of errors; Channel models; Linear codes and non-linear codes; Block codes and convolutional codes.

Block Codes

Introduction; Matrix representation; Minimum distance; Error syndrome and decoding; Simple codes; Low-density parity-check codes.

Cyclic Codes

Matrix representation of a cyclic code; Encoder with n-k shift-register stages; Cyclic Hamming codes; Maximum-length-sequence codes; Bose-Chaudhuri-Hocquenghem codes; Reed-Solomon codes; Golay codes; Reed-Muller codes; Quadratic residue codes.

Decoding Cyclic Codes

Meggitt decoder; Error-trapping decoder; Information set decoding; Threshold decoding. Algebraic decoding; Berlekamp-Massey time domain decoding; Euclidean frequency domain decoding; Soft-decision Decoding; Decoding LDPC Codes.

Hide this content.