COURSE OUTLINE: MH4310

Course Title

Coding Theory

Course Code

MH4310

Offered Study Year 4, Semester 2
Course Coordinators Xing Chaoping (Prof) xingcp@ntu.edu.sg 6513 7473
Frederique Elise Oggier (Assoc Prof) frederique@ntu.edu.sg 6513 2026
Pre-requisites MH1301 and MH2200
AU 4
Contact hours Lectures: 39, Tutorials: 12
Approved for delivery from AY 2020/21 semester 2
Last revised 18 Mar 2020, 11:31

Course Aims

This course aims to introduce the topic of coding theory, which studies the design of mechanisms to ensure reliability of data transmission (or storage) in the presence of perturbance. In this course, you will learn what are linear codes, their properties, how to construct them, and how to use them to ensure data reliability.

Intended Learning Outcomes

Upon successfully completing this course, you should be able to:

  1. Define what is a linear code.
  2. Give examples of linear codes.
  3. Compute the minimum distance of a linear code.
  4. Encode and decode a linear code.
  5. Explain where coding theory is being used.
  6. Weigh the trade-offs involving code parameters.

Course Content

The definition of a linear code, its dimension and its length.

The definition of generator matrix, parity check matrix and dual code.

The definition of Hamming distance/weight, and how to compute it.

How to encode and decode.

Hamming codes

Perfect codes

Golay codes

Maximum distance separable (MDS) codes

Reed-Mueller codes

BCH codes

Reed-Solomon codes

Bounds on code parameters

Assessment

Component Course ILOs tested SPMS-MAS Graduate Attributes tested Weighting Team / Individual Assessment Rubrics
Continuous Assessment
Mid-semester Quiz
Short Answer Questions 1, 2, 3, 4, 5, 6 1. a, b
 20 individual See Appendix for rubric
Short Answer Questions 1 1, 2, 3, 4, 5, 6 1. a, b
 20 individual See Appendix for rubric
Examination (2 hours)
Short Answer Questions 1, 2, 3, 4, 5, 6 1. a, b, c
 60 individual See Appendix for rubric
Total 100%

These are the relevant SPMS-MAS Graduate Attributes.

1. Competence

a. Independently process and interpret mathematical theories and methodologies, and apply them to solve problems

b. Formulate mathematical statements precisely using rigorous mathematical language

c. Discover patterns by abstraction from examples

Formative Feedback

Feedback will be given after the CA, so that you know where you stand, and what are the weakest points to be improved upon.

Since the class size for this class is not very large, you are welcome to ask for personal consultation should you want or need a more personalized feedback.

After the final exam, the Examiner's Report will be available on NTUlearn.

Learning and Teaching Approach

Lectures
(39 hours)

During the lecture, the new concepts are introduced and explained to you. In order to improve the effectiveness of learning, the following steps are taken:
(1) while there are prerequisites, concepts needed from linear algebra will be recalled and reinterpreted in the context of the course, while concepts from algebra will be explained from the beginning.
(2) emphasis will be given on examples and explicit computations, to help give examples of linear codes, and compute their minimum distance and other properties.
(3) motivations from real applications will be provided, to provide contexts where coding theory is being used.
(4) a few demonstrations will be exhibited to render the concepts more concrete.

Tutorials
(12 hours)

In tutorials, you will mostly be asked to compute codes and their properties, and to use them in different application scenarios.

Reading and References

C. Xing and X. Ling, ``Coding Theory: A First Course"
ISBN-13: 978-0521529235
ISBN-10: 0521529239

W. Cary Huffman and Vera Pless, ``Fundamentals of Error Correcting Codes", Cambridge
Online ISBN: 9780511807077
DOI: https://doi.org/10.1017/CBO9780511807077

Course Policies and Student Responsibilities

As for any class you attend, it is your responsibility to learn the material, whether you decide to attend the class or to read the material, as well as to try out the tutorial questions.

Academic Integrity

Good academic work depends on honesty and ethical behaviour. The quality of your work as a student relies on adhering to the principles of academic integrity and to the NTU Honour Code, a set of values shared by the whole university community. Truth, Trust and Justice are at the core of NTU’s shared values.

As a student, it is important that you recognize your responsibilities in understanding and applying the principles of academic integrity in all the work you do at NTU. Not knowing what is involved in maintaining academic integrity does not excuse academic dishonesty. You need to actively equip yourself with strategies to avoid all forms of academic dishonesty, including plagiarism, academic fraud, collusion and cheating. If you are uncertain of the definitions of any of these terms, you should go to the Academic Integrity website for more information. Consult your instructor(s) if you need any clarification about the requirements of academic integrity in the course.

Course Instructors

Instructor Office Location Phone Email
Frederique Elise Oggier (Assoc Prof) MAS05-13 6513 2026 frederique@ntu.edu.sg
Xing Chaoping (Prof) SPMS-MAS-05-27 6513 7473 xingcp@ntu.edu.sg

Planned Weekly Schedule

Week Topic Course ILO Readings/ Activities
1

Definition of coding theory, what it is and where it is used. Definition of encoding, linear code, generator matrix, parity check matrix

 1, 2, 4, 5

introduction of chapter 1, 1.1 and 1.2 (Huffman and Pless)

2

Dual codes, Hamming distance

 1, 2, 3

1.3, 1.4 (Huffman and Pless)

3

Error correction, Hamming spheres.

 4

1.11 (Huffman and Pless)

4

Syndrome decoding

 4

1.11 (Huffman and Pless)

5

Rate, Sphere Packing Bound, Hamming codes

 2, 3, 6

1.12 and 1.8 (Huffman and Pless)

6

Golay codes, puncturing and extending

 2, 3, 6

1.9 and 1.5.2, 1.5.3 (Huffman and Pless)

7

Reed-Mueller codes

 2, 3, 6

1.10 (Huffman and Pless)

8

Bounds

 6

section 2 (Huffman and Pless)

9

Finite fields

 6

section 3 (Huffman and Pless)

10

Reed-Solomon codes

 2, 3

section 5.2 (Huffman and Pless)

11

Cyclic codes

 2, 3, 6

section 4(Huffman and Pless)

12

BCH codes: introduction

 2, 3, 6

section 5(Huffman and Pless)

13

More on BCH codes and Reed-Solomon codes

 2, 3

section 5 (Huffman and Pless)

Appendix 1: Assessment Rubrics

Rubric for Mid-semester Quiz: Short Answer Questions (20%)

The midterm has for goals to check that the concepts taught in class, in particular the examples seen and the exercises, are clear to the students. Therefore most questions should be doable based on homeworks and examples already seen.

Rubric for Mid-semester Quiz: Short Answer Questions 1 (20%)

The midterm has for goals to check that the concepts taught in class, in particular the examples seen and the exercises, are clear to the students. Therefore most questions should be doable based on homeworks and examples already seen.The second midterm is similar to the first midterm, topics from the first midterms will be de-emphasized in the second midterm, they may instead reappear in the final exam.

Rubric for Examination: Short Answer Questions (60%)

The examination will be a bit different from the midterm in the sense that around 60% of the examination will be in the same spirit as the midterm, namely containing examples and exercises close to what was practiced in class. However there might be around 40% of the examination which contains questions that are more challenging, meaning that they may invoke a deeper understanding of the topics taught. To get a sense as in one is ready for these questions, hints would be: do you understand things enough to actually explain to others what they are, can you come up with new questions regarding the topics seen that were not explicitly covered in class?