TMA4185 Coding theory - Spring 2021
| Lecturer | Kristian Gjøsteen |
|---|---|
| Schedule | |
| Lectures: | Thursday 14.15-16 on Zoom, but later also in EL1 |
| Friday 10.15-12 on Zoom, but later also in H1 | |
| Office hours: | No office hours planned |
| Exercises: | No formal exercise classes |
Messages
2/6: This year's exam. No suggested solutions are available.
24/5: Office hours before the exam will be on Zoom, Thursday 27/5 11:00-13:00 and Monday 31/5 10:00-12:00. Zoom links are available in Blackboard.
16/5: Three new exercise sets are ready.
16/4: There will be no recordings of April lectures. There may eventually be slides.
16/4: The lectures on Thursday April 22 and 23 will be Q&A sessions, and they will be purely digital.
24/3: The lectures on Thursday March 25/3, Friday 26/3, Thursday 8/4 and Friday 9/4 will be purely digital. Later lectures may also end up being purely digital.
5/3: There will be no lecture Friday March 19.
2/3: The project is out and available in Blackboard, and the deadline for handing it in is April 26. Your final grade will be max{0.8*exam score + 0.2*project score, exam score}.
22/2: The third exercise set is ready.
22/2: Completely off-topic, but for those who are interested in risk analysis, I recommend Analyser av krisescenarioer (also available in English), perhaps in particular Section 4.2.
22/2: Physical lectures begin March 4. The physical lectures will also be broadcast via Zoom and recordings will be made available. Those going to physical lectures must use NTNU Check-in and follow regulations for wearing masks. I also recommend that everyone install Smittestopp. (I recommend Smittestopp even if you don't go to the lectures.)
12/2: Physical lectures have been postponed, as you are aware. As consolation, a new exercise set is ready.
1/2: The first exercise set is ready. A Zoom room has been set up for the exercise class, as well as a Piazza forum. Links can be found in Blackboard, under "Learning materials".
17/1: The reference group is ready. Thank you all for volunteering.
17/1: The first videos and slides have been posted. You can find them in Blackboard, under "Learning materials".
14/1: I have turned off authentication for the Zoom lectures (the requirement that you are logged in with your NTNU account), since that caused problems for some of you. I will turn it back on soon, so please sort out your Zoom logins quickly.
13/1: The links to the Zoom lectures are available under "Course information" in Blackboard.
4/1: Zoom it is! Initially the lectures will be on Zoom only. Links will appear in Blackboard. I hope we will be able to return to physical lectures soon, but these will also be available on Zoom. I expect to make recordings of lectures available. Some lectures (or parts of lectures) may also be pre-recorded. We may also use some of the lecture time for general question sessions and help for exercises.
Book
Huffman and Pless: Fundamentals of Error-Correcting Codes.
You may also find Lindell's lecture notes (available from his course home page) useful.
Exam
More information to follow.
Reference group
| Name | |
|---|---|
| Sofie Holtestaul | sofiehol (at) stud.ntnu.no |
| Andreas Palm Sivertsen | andreaps (at) stud.ntnu.no |
| Oskar Goldhahn | oskar (at) goldhahn.name |
Contents
Chapters from the book:
- 1.1-1.8, 1.10-1.12.
- 2.1, 2.4, 2.8.
- 3.1-3.7
- 4.1-4.5
- 5.1-5.2, 5.4.1, 5.4.2
- 14.1-14.5
Notes:
Exercise sets
For some of the exercises, you will need to read material from the book that has not been covered in the lectures.
Exercise sets:
| # | What |
|---|---|
| 1 | Exercises 1 (p. 4), 4 (p. 6), 6 (p. 7), 9 (p. 7), 13 (p. 8), 21 (p. 13), 35 (p. 20) |
| 2 | Exercises 45 (1.7), 55 (1.8), 64, 65, 70 (1.11), 82 (1.12), 90 (2.1) |
| 3 | Exercises 3.1: 157, 3.3: 164, 165, 3.4: 169, 170, 3.5: 178, 3.6: 180, 3.7: 190, 192 |
| 4 | Exercises 4.1: 202, 4.2: 205, 212, 214, 4.3: 222, 228, 4.4: 239, 243, 4.5: 265 |
| 5 | Exercises 5.1: 284, 5.2: 291, 5.4: 295, 297 |
| 6 | Exercises 14.1: 798, 14.2: 812, 816, 14.4: 823, 14.5: 833. |
Plan
A tentative lecture plan, which will likely be changed.
| Uke | Hva | Book | Notes |
|---|---|---|---|
| 2 | Encoding and decoding, Shannon's theorem, linear codes, distance, weight. | 1.11, 1.2 | |
| 3 | Linear codes. Shannons teorem. Hamming codes. | 1.2-8 | |
| 4 | Syndrome decoding. Reed-Muller codes. Sphere packing bounds. | 1.10-12. | Reed-Muller codes |
| 5 | Bounds on code sizes. | 2.1, 2.4, 2.8 | |
| 6 | Finite fields. | 3.1-3.7 | |
| 7 | Cyclic codes | 4.2 | |
| 8 | Equivalence of cyclic codes, ideals, polynomial factors and cyclotomic cosets | 4.1-4.4. | |
| 9 | Minimum distance of cyclic codes. BCH codes. Decoding BCH codes | 4.5, 5.4.1 | |
| 10 | BCH codes. Decoding BCH codes. Applications | 5.4.2, 5.5, 5.6 | |
| 11 | Convolutional codes | 14.1, 14.3, 14.4, 14.5 | Convolutional codes |
| 12 | Convolutional codes | 14.1, 14.3, 14.4, 14.5 | Convolutional codes |
| 13 | Easter | ||
| 14 | Algebraic geometric codes, cryptography from coding theory | 13.1-5 | |
| 15 | Summary/review | ||
| 16 | Old exams | ||