TMA4185 Coding theory - Spring 2015

Huffman and Pless: Fundamentals of Error-Correcting Codes.

The exam will be on May 21st 2015, with permitted aids code C. There will be allowed to bring a simple calculator and one handwritten yellow sheet of size A4 where a blanck sheet with the department´s stamp can be obtained outside the department office on the 7th floor og SII. Previous exams are available. Exam may 2014.

First lecture: Monday January 12th at 12.15

Last lecture: Monday April 27th Summary

Material covered in lecture one: ISBN-numbers (International Standard Book Numbering System), how they are obtained. The Social Sequrity Number System of Norway. How to create a 12 digit telphone number systen with digits between 0 and 9 so that each person on earth gets his own number, and in addition having the property that anybody calling will reach the right person even when one diled digit is wrong. The finite fields with 2, 3 and 4 elements. Linear codes.

Lecture 2: Codes and linear codes, Hamming distance, wieghts, generator matrix, generator matrix in standard form (after permuting the coordinates, and elementary row operations), parity check matrix, dual code, the Hamming [7,4] code with weight distrbution, a perfect code that can correct one error.

Lecture 3: Repeated some of the main notions. Introduced the dot product for the vector spaces F_q^n, and the Hermitian products for the vector spaces F_4^n. Introduced the orthogonal of a code, the hermitian orthogonal of a code, and the terms self-orthogonal, Hermittian self-orthogonal, self-dual and Hermitian self-dual. Ended the lecture by going through Theorem 1.4.5.

Lecture 4: Cover the rest of 1.4, Wieghts and distances.

Lecture 5: Cover section 1.5 with a bit more linear algebra explanations than in the book.

Lecture 6: Cover section 1.6 and 1.7; Equivalence of Codes.

Lecture 7: Cover section 1.8, and started on 1.10, finishing with the proof of part (i) th. 1.10.1.

Lecture 8: Finish section 1.10, Cover 1.11.1, 1.11.2 to page 44, start 1.12. Remark: if the probability of sendin a 0 or a 1 is the same, then the probability of reciving a 0 or a 1 is the same in a binary symmetric code, and hence prob c= prob y on page 39, so the two probabilities there are the same.

Lecture 9: Finish section 1.12, and end with proof of th.2.1.2.

Lecture 10: Finish 2.1; 2.4;and 2.8. Start 3.1.

Lecture 11: Cover 3.1, 3.2, 3.3, 3.4 including the existence of finite fields for any prime power.

Lecture 12: Cover 3.5, 3.6 and part of 3.7. Give the result that the number of monic primitive polynomial of degree n over the field with p elements is the number of numbers relative prime to p^n-1 between 1 and p^n-1 divided by n.

Lecture 13: Cover the rest of 3.7 and start Chapter 4 and cover most of 4.1.

Lecture 14: Cover 4.2. More examples of shift registers will be given in the next lecture.

Lecture 15: Examples of shift registers for multiplying with a polynomial will be given. Idempotent elements and generators for cyclic codes will be established.

Lecture 16: This lecture ends with Th 4.3.12 where the opoeration \my_a will be introduced when gcd(a,n)=1.

Lecture 17: Finish section 4.3 and start section 4.4.

Lecture 18: Cover everything until Theorem 4.4.15.

Lecture 19: Cover the rest of section 4.4. Give a proof of the determinant of the Vandermonde matrix and end with Theorem 4.5.3.

Lecture 20: Cover the BCH bound and the van Lint-Wilson Bounding techniques and includ several examples.

Lecture 21: Includ the Hartmann-Tzeng Bound and illustarat with example 4.5.9. Cover 5.1, BCH-codes, and defin the Reed-Solomon codes.

Lecture 22: Finish section 5.2, Reed-Solomon codes, and finish 5.4.1, The Peterson-Gorenstein-Zierler Decoding Algorithm.

Lecture 23: Illustrat the P-G-Z algorithm by working through Examples 5.4.3 and 5.4.6. Start on Chaper 14, Convolution codes.

Lecture 24: Generating matrices of polynomials, encoding using linear feedforward shify-registers, State diagrams, and trellis diagram for encoding and decoding.

Lecture 25: The Viterbi algorithm for decoding, illustrated with example 14.2.5, and start on canonical generator matrices.

1, Thursday 15/1-15, 13.15 R60: Exercise 3 page 5; exercise 4, 5 page 6; exercise 6, 7, 8, 10 page 7.

2, Thursday 22/1-15, 12.15 R60: Exercise 17 p.10, 19 p.12, 22 p.13, 23 p.14, 25 p.15, 26 p.15, 27 p.16, Prove th.1.5.7 on p.17, Exercise 29 p.18, 31 p.18, 33 p.19.

3, Thursday 29/1-15, 12.15 R60: Exercise 34, 35 p.20, 36, 37 p.21, 38, 39, 40, 41 p.22, 43 p.23, 46, 48 p.26.

4, Thursday 5/2-15, 12.15 R60: Exercise 49 (a) and (b) p.26, 50 (a) and (b) p.27, 56 p.29, 58 p.30.

5, Thursday 12/2-15, 12.15 R60: Exercise 64 (b and c) p.38, 65 p.41, 68 p.43, 82 p.50, 85 p.55, 89 p.56, 90, 93 p.57,

6, Thursday 19/2-15, 12.15 R60: Exercise 86 p.55, 112 p.72, 152 p.101, 156 p.103, 159 p.104, 165 p.106.

7, Thursday 26/2-15, 12.15 R60: Exercise 167 p.107, 169 (d), 170, 174 p.109, 178, 179 p.111, 180, 181 p.112, 190, 191 p.116.

8, Thursday 5/3-15, 12.15 R60: Exercise 201 p.122, 202 (a) p.124, 209 p.128, 217 p131, 228 p.137.

9, Thursday 12/3-15 12.15 R60: Exercise 220, 221 p.134, 230 p.138, 232, 234 a),b), p.139, 238 p.142, 240 p.143, 243, 245 p.145, 248 p.146, 249, 251 p.147

10, Thursday 19/3-15 12.15 R60: Exercise 262 p.149, 265 p.152, 266, 267, 268 p.154, 272 p. 156.

11, Thursday 26/3-15 12.15 R60: Exam problem 1,2,3 and 5 Mai 5th 2003, and problem 5 mai 19th 2004. (You find these problems on the homepage for TMA4185 for 2013)

12, Thursday 16/4-15 12.15-14 R60: Exercise 301 a) p. 186, Exam problem 4 5th of Mai 2003, Exam problem 1 and 3 19th of May 2004. Exam problem 2 2012.

13, Thursday 23/4-15 12.15-14 R60: Exam may 2014 (finnes under eksamen på toppen av siden).

Chapters from the book:

• 1.1-1.8, 1.10, 1.11(up to page 44), 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:

• Reed-Muller codes
• Convolutional codes