# TMA4185 Coding theory - Spring 2017

Lecturer | Kristian Gjøsteen |
---|---|

Schedule | |

Lectures: | Monday 15-17 in R92 |

Tuesday 8-10 in F4 | |

Visiting hours: | Tuesday 1030-1200 in 848, SBII |

Exercises: | 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

Name | |
---|---|

Thor Tunge | thortun at stud.ntnu.no |

Simon Meinhard | simon.meinhard at epfl.ch |

Solvei Slågedal | solvesla 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.

Week | Dates | What |
---|---|---|

3 | 16-20/1 | Exercises 1, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14 |

4 | 23-27/1 | Exercises 34, 35, 37+45+47, 38, 39, 46, 55, 64, 67 |

5 | 30/1-3/2 | Exercises 23, 25, 26, 31, 33, 48, 78, 79. Problem 2 from the 2015 exam. |

6 | 6-10/2 | Exercises 85, 86, 89, 93, 111, 132, 162, 163, 166, 168, 177, 178, Problem 3 from the 2016 exam. |

7 | 13-17/2 | Exercises 180, 181, 201, 206, 214, 215, 216. Problem 4 from the 2012 exam. |

8 | 20-24/2 | Exercises 220, 223, 226, 229, 230, 239. Problem 2 from the 2014 exam. |

9 | 27/2-3/3 | Exercises 240, 241, 243, 244, 247, 248, 285, 289, 291, 295, 297, 299. Problem 4 from the 2009 exam. |

11 | 13-17/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

This plan will change.

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 | No lectures | ||

15 | Easter | ||

16 | Easter | ||

17 | Old exams |