Graph-based Inference, Networks and Coding Theory

ECTS Credits

10

Level of Study

Bachelor and Master

Full-time/Part-time

Full-time

Teaching semester

Autumn

Objectives and Content

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.

Learning Outcomes

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.

Required Previous Knowledge

At least 60 ECTS in Computer Science and at least 10 ECTS in mathematics

Access to the Course

Access to the course requires admission to a programme of study at The Faculty of Mathematics and Natural Sciences

Teaching and learning methods

The teaching comprises lectures and assignments

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

Compulsory Assignments and Attendance

Submission of compulsory assignments.

Compulsory assignments are valid for one subsequent semester.

Forms of Assessment

Written examination or Digital written examination (3 hours).
Compulsory exercises may count towards the final grade.

Due to the measures taken to avoid the spread of Covid-19, UiB is closed for on-campus assessment. As a consequence, the following changes is made to assessment autumn semester 2020:

• Written home examination instead of written examination

Examination Support Material

Non-programmable calculator, according to the faculty regulations

Grading Scale

The grading scale used is A to F. Grade A is the highest passing grade in the grading scale, grade F is a fail.

Assessment Semester

Examination both spring semester and autumn semester. In semesters without teaching the examination will be arranged at the beginning of the semester.

Reading List

The reading list will be available within June 1st for the autumn semester and December 1st for the spring semester

Course Evaluation

The course will be evaluated by the students in accordance with the quality assurance system at UiB and the department.

Programme Committee

The Programme Committee is responsible for the content, structure and quality of the study programme and courses.

Course Coordinator

Course coordinator and administrative contact person can be found on Mitt UiB, or contact Student adviser

Course Administrator

The Faculty of Mathematics and Natural Sciences represented by the Department of Informatics is the course administrator for the course and study programme.