# TMA4185 Coding theory - Spring 2019

 Lecturer Sverre O. Smalø 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.) Tuesday 13-15 in 850, SBII 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.

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

WeekDatesWhat
315/1Exercises 1, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, what is the cardinality og Gl_n(F_q)?
422/1Exercises 34, 35, 37+45+47, 38, 39, 46, 55, 64, 67
529/1Exercises 23, 25, 26, 31, 33, 48, 78, 79. Problem 2 from the 2015 exam.
65/2Exercises 85, 86, 89, 93, 111, 132, 162, 163, 166, 168, 177, 178, Problem 3 from the 2016 exam.
712/2Exercises 180, 181, 201, 206, 214, 215, 216. Problem 4 from the 2012 exam.
819/2Exercises 220, 223, 226, 229, 230, 239. Problem 2 from the 2014 exam.
926/2Exercises 240, 241, 243, 244, 247, 248, 285, 289, 291, 295, 297, 299. Problem 4 from the 2009 exam.
105/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

A tentative lecture plan, which will likely be changed.

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
14Repetisjon
15 Gjennomgå gamle eksamensoppgaver
16 Easter
17Easter