TMA4185 Coding Theory
Spring 2009


Galois Shannon Hamming

Messages
  • In the lectures I mentioned a theorem that was not in our book. This was a special case of the Gilbert-Varshamov and existence of binary linear codes. I have written a pdf that you can download. Someone pointed out a mistake in the corollary I wrote on the blackboard. I have corrected it in this paper. On the blackboard I wrote the last sentence in the paper wrong. I wrote: "there exist a binary linear code C with length n and distance d if ....". It should have been: "there exist a binary linear code C with length n and distance d such that ....""
  • I will be at the office during week 20 at the following hours: Monday 10-12, Tuesday 10-12, Thursday 10-14. Week 21: Monday 10-14. You can come to the office anytime, but during these hours I will guaranteed be in my office. If any of the hours do not fit you, but you really need to have a talk, then just send me an email.
  • Have corrected an error in the syllabus below (section 4.4).
  • I will not follow the book on convolutional codes. If you do not attend the lectures, I suggest you ask someone if you can copy the notes.
  • Final version of the curriculum is out.
  • There will be two more lectures in the course. The last lecture is April 27. We will finish convolutional codes and look at the last problem set for the rest of the time. If you have any questions or want to me go through something in class, please send an email this week and let me know.
  • Happy easter!
  • Solutions for Problem 4 (Exam 2007): Problem 4. As I mentioned in class, the definition of the RS-code for this problem is a little bit different than in our book, so there are some adjustments on the algorithm. I suggest you do the problem on the Exam 2008. If you want you can adjust the code used in Problem 4 (Exam 2007) and see if you get the same answer.
  • Solutions for Exercise 201 b) and c): Ex201b, Ex201c.
  • Today (Friday 20 February) we have a short crash course in algebra. Starting at 12:15 and ending app. 14:15 in room 822. We have to do it this week.
  • Regarding the crash course in algebra. It seems that tomorrow might be difficult. I will write on the webpage as soon as possible, when I know if tomorrow is possible. IF it is possible, it will be from 12:15 to app. 14:15.
  • I have put out what chapters we have been through below. Emphasis should be on what has been said in the lectures. There are some theorems in Chapter 1 that I did not mention in the lectures, and are not considered as a part of the syllabus.
  • In the new course description of this course, the exam is supposed to count 100%. Therefore there will be no midterm test.
  • Exercise set 3 is out.
  • Exercise set 2 is out.
  • Exercise set 1 is out (see bottom of the page). I will probably only use one hour to go through these problems (Monday next week), so one hour will be ordinary lecture.
  • There was also a problem with the Tuesday hours, and we have crossed out all other possibilities. Therefore the lectures will be on Mondays and Thursdays as originally scheduled.
  • I have been through 1.1, 1.2 and we are now looking at dual codes.
  • The lecture on Mondays might be moved to Tuesday 8.15-10.00 (alternatively Tuesday 14.15 - 16.00). Please let me know as soon as possible if this is impossible for you. If the lecture can not be moved to any of those hours, we have to stick with original time. Next lecture will anyway be on Thursday.
  • Webpage is up. First lecture is Monday January 12.

Course
description		 Introduction to the theory of error correcting codes: linear codes, perfect codes, cyclic codes, BCH codes, Reed-Solomon codes, burst codes, convolutional codes, finite fields and polynomials.
  • Prerequisite: TMA4150 or MA2201.
  • 7,5 credits - 1 semester (spring).
  • 4 lecturing hours per week.
Lecturer Hermund Torkildsen
Office: room 826, Sentralbygg 2
Email: hermunda(at)math.ntnu.no
Phone: (735) 90483
Textbook Huffmann, Pless, Fundamentals of Error-correcting codes.
Syllabus
  • Kap 1: All, except 1.10.
  • Kap 2: 2.1, 2.4 (Singleton upper bound and MDS), 2.8 (Gilbert lower bound), 2.9 (Varshamov lower bound) + extra corollaries given in the lecture and the problems.
  • Kap 3: All, except 3.8.
  • Kap 4: 4.1, 4.2 (except from after Exercise 214 and out), 4.3 (except from after Exercise 227 and out), 4.4 (except from Theorem 4.4.3 and out), 4.5 (BCH bound and Hartmann-Tzeng bound to and including p.153), 4.6 (Meggitt decoding).
  • Kap 5: 5.1 (except from after Exercise 289 and out - affine invariant codes not part of curricilum), 5.2, 5.4 (only 5.4.1 - Peterson-Gorenstein-Zierler decoding), 5.5 og 5.6.
  • Convolutional codes (shift registers, finite state machines, encoding, decoding - emphasis on the lectures and notes!).
  • Emphasis on the lectures.
Final exam The written final exam (100%) takes place May 19th.
Lectures and
problem session
Lectures:
Monday 11.15-13.00 in F3 (including problem sessions app. every second week).
Thursday 12.15-14.00 in F4.
Problem sets Exercise set 1: PDF
Exercise set 2: PDF
Exercise set 3: PDF
Exercise set 4: PDF
Exercise set 5: PDF
Exercise set 6: PDF
Old exams May 2002: PDF  
May 2003: PDF  
May 2004: PDF  
May 2005: PDF  
May 2006: PDF
June 2007 PDF  
May 2008 PDF