TMA4185 Coding theory - Spring 2019
| Lecturer | Sverre O. Smalø |
|---|---|
| Schedule | |
| Lectures: | Tuesday 10.15-12 in Sentralbygg II, Room 734, First lecture on January 8th |
| Friday 08.15-10 in Sentralbygg II, Room S21 2nd floor (first time Friday 1rst of Mar.) | |
| Office hours: | Tuesday 13-15 in 850, SBII |
| Exercises: | Tuesday 15.15-16 in Sentralbygg II, Room 734 first time 15/1-19 |
Messages
Eksamens: It will be allowed to bring the textbook: Fundamentals of Error-Correcting Codes, by Huffman and Pless to the exam.
Friday April 26th, we will look at the exam problems from 2012 and 2013.
Siden to av studentene er på eskursjon til Japan, utsetter vi gjennomgang av flere eksamensoppgaver til fredag etter påske.
On Friday the seventh of April we will decode the exam problems from 2009, 2010 and 2011.
On Tuesday second of April we will go through the exam from 2007 and 2008.
On Friday 29th of March we will go through the exam from 2005.
På tirsdag 26/3 vil vi fullføre en oppsumering av innholdet i kurset.
På fredag 14/3 vil vi se på eksamen fra 2017 som ligger her. Eksamen 2017
Book
Huffman and Pless: Fundamentals of Error-Correcting Codes.
Exam
The date of the exam will be given on 27th of Mai, at 15.00 (3 p.m.) with permitted aids code C, which this year says that one can bring the textbook: Fundamentals of Error-Correcting Codes by Huffman and Pless.
Reference group
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.
We will try to find some other time for the exercise class this spring.
Tentative exercises
| Week | Dates | What |
|---|---|---|
| 3 | 15/1 | Exercises 1, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, what is the cardinality og Gl_n(F_q)? |
| 4 | 22/1 | Exercises 34, 35, 37+45+47, 38, 39, 46, 55, 64, 67 |
| 5 | 29/1 | Exercises 23, 25, 26, 31, 33, 48, 78, 79. Problem 2 from the 2015 exam. |
| 6 | 5/2 | Exercises 85, 86, 89, 93, 111, 132, 162, 163, 166, 168, 177, 178, Problem 3 from the 2016 exam. |
| 7 | 12/2 | Exercises 180, 181, 201, 206, 214, 215, 216. Problem 4 from the 2012 exam. |
| 8 | 19/2 | Exercises 220, 223, 226, 229, 230, 239. Problem 2 from the 2014 exam. |
| 9 | 26/2 | Exercises 240, 241, 243, 244, 247, 248, 285, 289, 291, 295, 297, 299. Problem 4 from the 2009 exam. |
| 10 | 5/3 | Exercises 300, 301, 302, 317, 318, 320. Problem 2 from the 2010 exam. |
Computer exercises
These are exercises that you probably need computer assistance to solve.
Consider a binary cyclic code of length 127 with generator polynomial
x^28 + x^27 + x^23 + x^21 + x^18 + x^16 + x^14 + x^13 + x^12 + x^11 + x^8 + x^5 + x^4 + x^3 + x^2 + x + 1
- What is its zero set, relative to an \(\alpha\) of order 127 satisfying \(\alpha^7 = \alpha+1\)?
- What is its dimension and minimum distance?
Suppose you have received
x^33 + x^32 + x^31 + x^30 + x^29 + x^23 + x^22 + x^19 + x^18 + x^17 + x^12 + x^11 + x^10 + x^8 + x^6 + x^5 + x^4 + x^2 + 1
- What is the nearest code word?
- If the code word was encoded as \(m(x)g(x)\), find \(m(x)\).
Plan
A tentative lecture plan, which will likely be changed.
| Uke | Hva | Book | Notes |
|---|---|---|---|
| 2 | Linear codes, distance, weight, dual codes. | 1.2, 1.3, 1.4, 1.12 | |
| 3 | Shannons teorem | 1.11 | |
| 4 | Hamming codes, equivalent codes, finite fields | 1.6, 1.8, 3.1, 3.2, 3.6 | |
| 5 | Finite fields, equivalent codes, Reed-Muller codes | 1.10, 3.4, 3.6 | Reed-Muller codes |
| 6 | Bounds on code sizes. Finite fields. | 2.1, 2.4, 2.8, 3.3, 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 | |
| 10 | BCH codes. Decoding BCH codes. Applications | 5.4, 5.5, 5.6 | |
| 11 | BCH codes, Reed-Solomon codes, algebraic geometric codes | 5.1, 5.2 | |
| 12 | Convolutional codes | 14.1, 14.3, 14.4, 14.5 | Convolutional codes |
| 13 | Convolutional codes | 14.1, 14.3, 14.4, 14.5 | Convolutional codes |
| 14 | Repetisjon | ||
| 15 | Gjennomgå gamle eksamensoppgaver | ||
| 16 | Easter | ||
| 17 | Easter | ||