Graph-based Inference, Networks and Coding Theory
- ECTS credits10
- Teaching semesterAutumn
- Course codeINF244
- Number of semesters1
- LanguageEnglish
- Resources
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.
Contact
Exam information
For written exams, please note that the start time may change from 09:00 to 15:00 or vice versa until 14 days prior to the exam.
Type of assessment: Written examination
- Date
- 16.02.2021, 09:00
- Duration
- 3 hours
- Withdrawal deadline
- 02.02.2021
- Examination system
- Inspera
- Digital exam