Graph-based Inference, Networks and Coding Theory
Postgraduate course
- ECTS credits
- 10
- Teaching semesters
- Autumn, Spring
- Course code
- INF244
- Number of semesters
- 1
- Teaching language
- English
- Resources
- Schedule
Course description
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.
ECTS Credits
Level of Study
Semester of Instruction
Required Previous Knowledge
Credit Reduction due to Course Overlap
Access to the Course
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.
Spring semester 2022: Digital written home examination instead of written examination on campus