TMA4185 Coding theory - Spring 2014

Huffman and Pless: Fundamentals of Error-Correcting Codes.

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

First lecture: Tuesday January 14th at 08.15

In order to compensate for the lost lecture in January there will be lectures at 10.15-12.00 on Thursday the 24th and Friday the 25th of April. The lecture will be given in S21, second floor of Sentralbygg II.

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 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: Covered the rest of 1.4, Wieghts and distances.

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

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

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

Lecture 8: Finished section 1.10, Covered 1.11.1, 1.11.2 to page 44, started 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: Finished section 1.12, and ended with proof of th.2.1.2.

Lecture 10 17/2-14: Finished 2.1; 2.4;and 2.8. Started 3.1.

Lecture 11 18/2-14: Covered 3.1, 3.2, 3.3, 3.4 including the existence of finite fields for any prime power.

Lecture 12 24/2-14: Covered 3.5, 3.6 and part of 3.7. Gave also 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 25/2-14: Covered the rest of 3.7 and started Chapter 4 and covered most of 4.1.

Lecture 14 3/3-14: Covered 4.2. I will give more examples of shift registers next lecture.

Lecture 15 4/3-14: Examples of shift registers for multiplying with a polynomial was given. Idempotent elements and generators for cyclic codes were established.

Lecture 16 10/3-14: This lecture ended with Th 4.3.12 where the opoeration \my_a was introduced with gcd(a,n)=1.

Lecture 17 11/3-14: Finished section 4.3 and started section 4.4 and ended with corollary 4.4.5 describing the defining set of the code C\my_a in terms of the defining set of the code C.

Lecture 18 17/3-14: Covered everything until Theorem 4.4.15.

Lecture 19 18/3-14: Covered the rest of section 4.4. Gave a proof of the determinant of the Vandermonde matrix and ended with Theorem 4.5.3.

Lecture 20 24/3-14: Covered the BCH bound and the van Lint-Wilson Bounding techniques and included several examples.

Lecture 21 25/3-14: Included Hartmann-Tzeng Bound and illustarated with example 4.5.9. Covered 5.1, BCH-codes and defined the Reed-Solomon codes.

Lecture 22 31/3-14: Finished section 5.2, Reed-Solomon codes, finished 5.4.1 The Peterson-Gorenstein-Zierler Decoding Algorithm.

Lecture 23 1/4-14: Illustrated the P-G-Z algorithm by working through Examples 5.4.3 and 5.4.6. Started on Chaper 14, Convolution codes.

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

Lecture 25 8/4-14: The Viterbi algorithm for decoding, illustrated with example 14.2.5, and started on canonical gnerator matrices.

1, Tuesday 21/1-14, 16.15 G012: Exercise 3 page 5; exercise 4, 5 page 6; exercise 6, 7, 8, 10 page 7.

2, Tuesday 28/1-14, 16.15 R90: 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, Tuesday 4/2-14, 16.15 R90: Exercise 34, 35 p.20, 36, 37 p.21, 38, 39, 40, 41 p.22, 43 p.23, 46, 48 p.26.

4, Tuesday 11/2-14, 16.15 R90: Exercise 49 (a) and (b) p.26, 50 (a) and (b) p.27, 56 p.29, 58 p.30.

5. Tuesday 18/2-14, 16.15 R90: 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. Tuesday 25/2-14, 16.15 R90: Exercise 86 p.55, 112 p.72, 152 p.101, 156 p.103, 159 p.104, 165 p.106.

7. Tuesday 4/3-14, 16.16 R90: Exercise 167 p.107, 169 (d), 170, 174 p.109, 178, 179 p.111, 180, 181 p.112, 190, 191 p.116.

8. Tuesday 11/3-14 16.15 R90: Exercise 201 p.122, 202 (a) p.124, 209 p.128, 217 p131, 228 p.137.

9. Tuesday 18/3-14 16.15 R90: 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. Tuesday 25/3-14 16.15 R90: Exercise 262 p.149, 265 p. 152, 266, 267, 268 p.154, 272 p. 156.

11. Tuesday 1/4-14 16.15: 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. Tuesday 8/4-14: 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.

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:

• Reed-Muller codes
• Convolutional codes