Objectives:

Codes defined on graphs enable practical communication at rates close to the Shannon bound. INF244 aims to teach the students about how such codes are designed and analyzed, and about how inference on graphs allow efficient and effective decoding.

Content:

The course will discuss message-passing algorithms on graphs, particularly in the context of coding theory. Topics include graph theory, trellis codes, the Viterbi algorithm, and iterative and convergent message-passing on graphs with cycles. Moreover, the course will cover state of the art codes with performance close to the Shannon threshold, including turbo codes, polar codes, LDPC codes, and in particular spatially coupled codes. Spatially-coupled codes comprise an important class of codes that are defined on spatially-coupled graphs. Due to the principle of spatial coupling one can prove that these codes achieve the capacity of any binary memoryless channel. Polar codes are also provably capacity-achieving, they have a nice graphical representation that can be used for decoding, and they are now part of the 5G standard.

The course will discuss methods to analyze the performance of such codes, including EXIT analysis, ensemble analysis, and error floor analysis. It will also be discussed how to message pass on simple graphs in the context of F4 additive codes, and how to use local complementation to message pass on dynamic graphs. As assignments, the students shall be asked to write computer code to realise message-passing algorithms in a number of different coding contexts.

On completion of the course the student should have the following learning outcomes defined in terms of knowledge, skills and general competence:

 Knowledge

The student

• Is familiar with modern graph based codes as described in the course, and their performance on communication channels
• will understand inference on graph systems
• will understand the limitations imposed by Shannon¿s channel theorem, and the principles for design of codes with behavior approaching the Shannon threshold

Skills

The student

• will be able to assess the performance of a given code, with a given decoder, on a given channel will be able to write code to implement message-passing algorithms
• will be able to write code to generate noise of a given probability density
• will be able to manipulate statistical information and probabilities, particularly in the context of coding theory

General competence. The student

• is familiar with new ideas and innovation processes
• can exchange opinions with others with relevant background and participate in discussions concerning the development of good practice.

The teaching comprises lectures and assignments

Lectures: 4 hours per week for 11 weeks
Group exercises: 2 hours per week for 9 weeks

Submission of compulsory assignments.

Compulsory assignments are valid for one subsequent semester.

Student adviser:

mailto:studieveileder@ii.uib.nomailto:studieveileder@ii.uib.noStudent adviser

T: 55 58 42 00