# TMA4185 Coding theory - Spring 2017

 Lecturer Kristian Gjøsteen Monday 15-17 in R92 Tuesday 8-10 in F4 Tuesday 1030-1200 in 848, SBII TBD

## Messages

11/5: My final office hours before the exam will be Friday May 12, 10-12. I will also be available by e-mail.

3/5: Note that the exam will be given in English only. You may answer in Norwegian or English.

20/4: The permitted aids code for this course is "C: Specified printed and hand-written support material is allowed. A specific basic calculator is allowed." On the exam, I will specify that all printed and hand-written support material is allowed.

## 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

The exam will be on May 15, with permitted aids code C. Previous exams are available.

## Reference group

NameE-mail
Thor Tungethortun at stud.ntnu.no
Simon Meinhardsimon.meinhard at epfl.ch
Solvei Slågedalsolvesla at stud.ntnu.no

## 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.

There will be no specific exercise class this spring. If you need help with any of the exercises, send me an e-mail or drop by my office.

WeekDatesWhat
316-20/1Exercises 1, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14
423-27/1Exercises 34, 35, 37+45+47, 38, 39, 46, 55, 64, 67
530/1-3/2Exercises 23, 25, 26, 31, 33, 48, 78, 79. Problem 2 from the 2015 exam.
66-10/2Exercises 85, 86, 89, 93, 111, 132, 162, 163, 166, 168, 177, 178, Problem 3 from the 2016 exam.
713-17/2Exercises 180, 181, 201, 206, 214, 215, 216. Problem 4 from the 2012 exam.
820-24/2Exercises 220, 223, 226, 229, 230, 239. Problem 2 from the 2014 exam.
927/2-3/3Exercises 240, 241, 243, 244, 247, 248, 285, 289, 291, 295, 297, 299. Problem 4 from the 2009 exam.
1113-17/3Exercises 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?

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

This plan will change.

UkeHvaBookNotes
2Linear codes, distance, weight, dual codes.1.2, 1.3, 1.4, 1.12
3Shannons teorem1.11
4Hamming codes, equivalent codes, finite fields1.6, 1.8, 3.1, 3.2, 3.6
5Finite fields, equivalent codes, Reed-Muller codes1.10, 3.4, 3.6Reed-Muller codes
6Bounds on code sizes. Finite fields.2.1, 2.4, 2.8, 3.3, 3.7
7Cyclic codes4.2
8Equivalence of cyclic codes, ideals, polynomial factors and cyclotomic cosets4.1-4.4.
9Minimum distance of cyclic codes. BCH codes. Decoding BCH codes4.5, 5.4
10BCH codes. Decoding BCH codes. Applications5.4, 5.5, 5.6
11BCH codes, Reed-Solomon codes, algebraic geometric codes5.1, 5.2
12Convolutional codes14.1, 14.3, 14.4, 14.5Convolutional codes
13Convolutional codes14.1, 14.3, 14.4, 14.5Convolutional codes
14No lectures
15 Easter
16 Easter
17Old exams