Course syllabus

Course-PM

SSY196 SSY196 Error control coding lp3 VT22 (7.5 hp)

Course is offered by the department of Electrical Engineering

 

Course purpose

Error control coding (also referred to as error correcting coding) is the science of adding redundancy to the transmitted (or stored) data with the purpose of correcting (and/or detecting) errors that occur during the communication process. 

The application of coding goes far beyond the classical transmission and storage problem. Coding is a very powerful, fundamental tool that plays a key role in a myriad of other applications and research fields, such as distributed computing, distributed storage and caching, uncoordinated multiple-access, quantum key distribution, post-quantum cryptography, or DNA storage.

This course provides students with the theoretical and practical tools to understand, analyze, and apply error control codes, covering in particular modern coding theory.

This course is recommended to

• PhD students
• Master students with an interest in a research-oriented career:
  • R&D job in industry
  • Potentially interested in pursuing a PhD later on at Chalmers or elsewhere
•  Master students that would like to develop skills that are not addressed in conventional Master courses (see Learning outcomes)

 

Content

• Linear block codes and convolutional codes
• Modern coding theory (codes-on-graphs):
  • Low-density parity-check (LDPC) codes
  • Turbo-like codes
  • Product codes
  • Rateless codes
• Iterative decoding: belief propagation decoding
• Tools for the analysis of modern codes and iterative receivers in general: Density evolution, EXIT charts

 

Learning outcomes

The students will acquire technical/mathematical skills in error control coding. After the course, the students will be able to:

• Explain the relations between minimum distance, error correcting and error detecting capability, block and bit error rate and coding gain, and calculate or estimate these quantities for simple block codes
• Implement a transmitter and syndrome-based decoder for an arbitrary block code, and evaluate their performance by simulations
• Define and analyze the properties of product-like codes, LDPC codes, turbo-like codes, and rateless codes
• Explain the principles of iterative decoding, the sum-product algorithm, EXIT chart analysis and density evolution
• Implement transmitters and receivers for turbo and LDPC codes using iterative decoding
• Choose a code family, code parameters, and a decoding method, to fulfill given requirements on error correcting capability and complexity

In addition, students of this course will develop critical thinking skills necessary for mastering advanced topics  in engineering and practice some general (non-technical) skills. After the course should be able to:

• Participate in a scientific discussion by sharing ideas and experiences, asking and answering questions, explaining problem solutions and giving and taking criticism
• Independently identify relevant literature and use it to learn a selected research topic
• Prepare and give a presentation on a research paper matched to the audience pre-knowledge, while keeping time limits, crediting and referencing other researchers, and answering questions in a professional manner

Students who have only studied regular Master courses before may have had limited opportunity to practice these general skills, whereas they are part of the daily life for Ph.D. students and engineers with researcher-oriented jobs in industry.

 

Prerequisite

Solid foundation in probability and linear algebra. Basic knowledge of digital communications is an advantage but not required. The course difficulty is on the PhD level, which means that it is mathematically more advanced and runs at a higher pace than most Master courses.

 

Course organization

The course is organized as a discussion club, which is possible because a relatively small number of students follow the course. It comprises about 13-15 group meetings, divided into text sessions and problem sessions, about 7 homework assignments, and 1 paper and research seminar per student. There are no "classical lectures". Please, see Sections "Course Meetings", "Homework" and "Research Seminars" for further information.

 

Course literature

The course book is

• W. E. Ryan and S. Lin, Channel Codes: Classical and Modern, Cambridge, 2009 (ISBN 978-0-521-84868-8).

The following books may be useful as supplementary literature and side reading.

• S. Lin and D. J. Costello, Jr., Error Control Coding, 2nd edition, Pearson Education/Prentice Hall, 2004.
• S. J. Johnson, Iterative Error Correction, Cambridge, 2010.

A set of lecture notes will also be made available. 

 

Course staff

• Examiner and Lecturer: Alexandre Graell i Amat (alexandre.graell@chalmers.se). Office: Room 6409, Department of Electrical Engineering

 

Course meetings

There are two types of course meetings: text sessions and problem sessions.

• In the text sessions, the text homework is discussed, section by section. The students identify parts of each section that were perceived as difficult, strange, or particularly interesting. This may often lead to interesting discussions. Everyone is encouraged to participate by asking questions, answering questions, commenting, etc. There are no "stupid" questions! The teacher will lead the discussion, answer questions, and if needed give a mini lecture on some topic. Students are responsible for bringing up everything that was not clear to them, so that at the end of the discussion, everyone understands the section. During the discussion the teacher may ask questions to check the understanding.
• In the problem sessions, the homework problems are discussed. First the students declare which problems they have solved in a circulated table, and their level of confidence in their solutions. Then the students take turns demonstrating their solutions on the whiteboard. Other students and the teacher comment. If there are different solutions for the same problem, these are compared. Finally, the teacher announces text and problem homework for the next week.

 

Homework

The homework each week consists of reading (and understanding!) about 40--50 pages in the book and solving about 5-10 problems. The homework is handed out weekly, and it will be demonstrated and discussed in the next week. 

Each student is required to make a serious effort to solve the problems alone. Having done this, it is allowed (and recommended) to compare solutions with other students and get help. It is not allowed to discuss the solutions with others without first trying yourself.

Discussing the text in the book with other students is encouraged.

 

Research seminars

The course is concluded by a simulated conference session, in which each student gives a seminar. The task is to present the results from an interesting research article and to reproduce some of the results by simulations. For a successful result, each student should do the following.

• Choose a topic in coding theory (must be approved by the teacher).
• Select an interesting research article, new or old, within this topic, preferably one which reports significant results in some sense (must be approved by the teacher).
• Identify relevant background literature and use it to learn enough of the topic in order to understand the selected article and to put its results into a context.
• Reproduce a subset of the article's results by simulations. Change some parameter values and produce at least one result that was not in the article. Draw conclusions.
• Write a 2-3 page paper where you i) put the research article that you have chosen into context, ii) summarize the main contributions of the article, iii) include some of your own results, if any, iv) summarize the main conclusions/outcomes of the article.
• Prepare and give a seminar in a format similar to a conference presentation, supported by a slideshow. The time limits, which are strict, are 20 minutes for the presentation and 5 for questions.
• Attend the other seminars and participate in the subsequent discussions.

The teacher and students will together give each speaker feedback on the presentation. Was it well structured? How was the slideshow? Was the problem clearly stated? Was the seminar well matched to the audience pre-knowledge? Were time limits met? Were other researchers properly credited and referenced? How were questions handled? Etc.

 

Grading

The assessment is based on

• understanding homework texts
• solutions of homework problems
• participation in discussions at group meetings
• writing a 2-3 page paper on a research article and giving a seminar
• participation at the other seminars

There is no written examination, and hence no re-examinations. Grades are pass/fail only. To miss 1-2 group meetings and to fail up to 20% of the homework problems may be acceptable, if the student performs very well otherwise. The examination is a continuous process throughout the course. You can always ask the teacher how you are doing with respect to the passing threshold.