Coding theory is concerned with successfully transmitting data through a noisy channel and correcting errors in corrupted messages. It is of central importance for many applications in computer science or engineering. This seminar gives an introduction to the study of those codes arising from algebraic structures such as matricies or algebraic curves, with emphasis on topics covered in the book "Coding theory, a first course" by San Ling and Chaoping Xing.
| Instructor | Shane Kelly |
| shanekelly64 [at] gmail [dot] com | |
| Webpage | http://www.mi.fu-berlin.de/users/shanekelly/LinearCodes2016-17WS.html |
| University webpage | http://www.fu-berlin.de/vv/de/lv/348182?m=211645\&pc=130948\&sm=273470 |
| Textbook | "Coding theory: A First Course" by San Ling and Chaoping Xing. |
| Room | SR 210/A3 Seminarraum (Arnimallee 3-5) |
| Time | Mo 16:00-18:00 |
This is a student seminar which means that the students each make one of the presentations. The presentation should be about 75 minutes long, leaving 15 minutes for potential questions and discussion.
Students are not required to hand in any written notes. However, students are encouraged to prepare some notes if they feel it will improve the presentation. This should be considered seriously, especially if the student has not made many presentations before.
For example, its helpful to have
If notes are prepared I will collect them and give feedback if desired.
Each talk covers roughly 9 pages of the text book. The material listed below should be considered as a skeleton of the talk, to be padded out with other material (from those 9 pages for example) that the student finds interesting, relevant, enlightening, useful, etc.
If you have any questions please feel free to contact me at the email address above.
When transmitting information, the channel is often noisy, and introduces errors in the message. For example, communicating with a space station, or just using the internet with bad wifi reception.
So the problem is: How do we detect errors in the message, and how do we correct them.
The first step is to choose a set of words in an alphabet, for example:
{ 00000000, 01010101, 10101010, 11111111,
00110011, 01100110, 10011001, 11001100,
00001111, 01011010, 10100101, 11110000,
00111100, 01101001, 10010110, 11000011 }
has sixteen words of length eight chosen from the alphabet {0, 1}.
If we receive a message with a word which is not one of these, for example, 10101101, then we can detect that at least one error has occurred.
Moreover, we can make a reasonable guess as to what the original message was, since 10100101 shares seven letters in common with 10101101, whereas all other words in our code share only five or less letters. So we could even correct this error.
This lecture will cover the following:
Define and give examples of codes (2.1.1), symmetric channels (2.1.4, 2.1.5, 2.1.6), maximum likelihood decoding (2.2), Hamming distance (2.3.1), nearest neighbour decoding (2.4), distance, (n, M, d)-codes, u-error-detecting codes, v-error-correcting codes (2.5).
If we do addition and multiplication mod 2, the alphabet {0, 1} chosen above satisfies a list of properties also shared by the real and complex numbers. Such a thing is called a field. Other finite examples are ℤ mod p for any prime p (written ℤp in the textbook). We get the complex numbers ℂ from the real numbers ℝ by adjoining a solution i = √-1 of x^2 + 1 = 0. Similarly, we get more finite fields by adjoining solutions to certain polynomials to the finite fields ℤp For example
𝔽4 = {0, 1, ω, ω + 1} with 1 + 1 = 0 and ω2 + ω + 1 = 0
Many useful alphabets are obtained in this way. For example, the field with four elements is useful when encoding DNA.
This lecture will cover the following:
Prove finite fields have pn elements (Them 3.1.9, Thm 3.1.12, Thm 3.1.14), define polynomial rings, define gcd and lcm, discuss the analogies in Tables 3.1 and 3.2, polynomial residue fields (Thm 3.2.6, Ex 3.2.8, primitive elements (Def 3.3.4, Prop 3.3.9), Minimal polynomials (Def 3.4.1, Ex 3.4.2, Def 3.4.5, Ex 3.4.7, Thm 3.4.8, Thm 3.4.11, Cor 3.4.12).
The code above is a linear code: if we add any two elements together mod 2, then we get another element of the code, e.g.,
1 0 1 0 1 0 1 0
+ 0 0 1 1 1 1 0 0
-----------------------
= 1 0 0 1 0 1 1 0
We can also multiply by any element in the field {0, 1}, although in this case, the result is not very exciting since 0·v = 0 and 1·v = v.
This lecture will cover the following:
Define vectors spaces, subspaces, linear independence, linear spans, bases, orthogonality (Defs 4.1.1, 4.1.4, 4.1.8 4.1.10, 4.1.13, 4.1.17). Define linear codes, the dual code, dimension of a code, self-orthogonal, and sel-dual codes (Def 4.2.1, Def 4.2.3, Def 4.2.7). Introduce the terminology [n,k,d]-code (4.2.6). Define the Hamming weight of a codeword (Def 4.3.1). Describe the relationship to Hamming distance (Lemm 4.3.3, Cor 4.3.4). Define minimum Hamming weight (Def 4.3.7). Give examples of everything mentioned.
The code above is generated by the matrix
1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1
0 0 1 1 0 0 1 1
0 0 0 0 1 1 1 1
in the sense that every code word is obtained by adding some rows of this matrix together (e.g., 00000000 = 11111111 + 11111111). This is called a generator matrix. There is another important matrix associated to it:
0 0 0 1 1 1 1 0
0 1 1 0 0 1 1 0
1 0 1 0 1 0 1 0
1 1 1 1 1 1 1 1
This is called the parity-check matrix. The words of the above code are exactly the words which have 0 dot product with every row of the parity check matrix.
This lecture will cover the following:
Recall elementary row operations and row equivalence (Defs 4.4.1, 4.4.2). Present algorithms 4.1, 4.2, 4.3 for finding bases of linear codes. Define generator and parity-check matricies, and standard form (Def 4.5.1, 4.5.3). Criterion of a matrix to be a parity check matrix (Lemm 4.5.4). Relationship between distance and parity check matricies (Thm 4.5.6, Cor 4.5.7). Converting between parity check and generator matricies (Thm 4.5.9). Define equivalence of linear codes (4.6.1). Theorem 4.6.3. Examples of equivalent codes.
As a vector space, the code above is isomorphic to the vector space ℤ24 of tuples of ℤ2 of length 4. The generator matrix sets up such an isomorphism of vector spaces. Not only does the parity-check matrix detect whether a word is in our code or not, it can also be used to correct errors.
This lecture will cover the following:
Encoding elements of 𝔽qk using generator matricies. Remark 4.7.2 about the advantages of standard form, check digits, and redundancy. Define cosets (Def 4.8.1). Properties of cosets (Thm 4.8.4) Define coset leaders (4.8.7) and error patterns. Example 4.8.9. Define the syndrome of a word (Def 4.8.10) and syndrome lookup table (4.8.13). Properties of syndromes (4.8.11) Decoding procedure for syndrome decoding. Example 4.8.19.
If we only used the first two rows of the above code, we would still get a linear code which can correct two errors. However, we would only have eight codewords, so we can't transmit data as efficiently.
Once we choose an alphabet, a set a length for the words, and a number of errors to correct, the main coding theory problem is to find the most words possible.
This lecture will cover the following:
Define relative minimum distance (5.1.1), the notation Aq(n,d), optimal codes (5.1.4), and Bq(n,d) (5.1.6). First properties of Aq and Bq (5.1.7). Extended codes (Def 5.1.8, Thm 5.1.9, Ex 5.1.10, Thm 5.1.11). Sphere-covering bound (Def 5.2.1, 5.2.2, Lem 5.2.3, Thm 5.2.4). Gilbert-Varshamov bound (5.2.6).
These are certain kinds of codes. A Golay code was used on Voyager 1 and 2 launched towards Jupiter and Saturn in 1977.
This lecture will cover the following:
Hamming bound (5.3.1), perfect codes (5.3.2), binary Hamming codes (Def 5.3.3, Ex 5.3.5, Prop 5.3.6), Decoding binary Hamming codes algorythm. Extended binary Hamming codes (5.3.9, 5.3.10, 5.3.12). q-ary Hamming codes (5.3.13, 5.3.14, 5.3.15). Decoding q-ary Hamming codes. Binary Golay codes (5.3.17, 5.3.19, 5.3.20 5.3.22) Ternary Golay codes (5.3.23, 5.3.25).
This lecture will cover the following:
Singleton bound (5.4.1). MDS codes (5.4.3, 5.4.5, 5.4.6). Plotkin bound (5.5.2, 5.5.3). Hadamard matrix codes, the Nordstrom-Robinson code, Preparata codes, Kerdock codes. Residual codes (5.7.1, 5.7.2, 5.7.3). Griesmer bound (5.7.4). Krawtchouk pokynomials (5.8.1, 5.8.2). Distance distribution (5.8.3) Linear programming bound (5.8.5, 5.8.6, 5.8.7).
We can construct new codes from old codes. For example, as we mentioned above, we can only take the first two rows of the above code. In fact, the code above was constructed from the code
{ 0000, 0101, 1010, 1111
0011, 0110, 1001, 1100 }
by first taking each word twice, then taking each word with its "opposite". Moreover, this latter was constructed using the same procedure from
{ 00, 01, 10, 11 }
If we go in the other direction, the code obtained like this whose words have length 25 = 32 was used by Mariner 9 to transmit black and white pictures of Mars to the Earth in 1972. These codes are called Reed-Muller codes.
This lecture will cover the following:
Propogation rules (6.1.1, 6.1.3, 6.1.5, 6.1.8, 6.1.11). Reed-Muller codes (Def 6.2.1, 6.2.3, 6.2.4, 6.2.5, 6.2.7). Concatenated code (6.3.1, 6.3.2). Subfield subcode (6.3.5, 6.3.6). Trace code (6.3.7, 6.3.8).
Some codes stay the same if we rotate the coordinates, by sending (a1, a2, ..., an-1, an) to (a2, a3, ..., an, a1). Such codes are called cyclic codes. They correspond to coefficients of polynomials in ideals of certain quotient polynomial rings. The algebra of these rings contains a lot of information about the codes.
This lecture will cover the following:
Define cyclic codes (7.1.1). Ideals (7.1.5, 7.1.7, 7.1.8, 7.1.9, 7.1.10). Cyclic codes correspond to ideals (7.2.1). Generator polynomials (7.2.3, 7.2.5, 7.2.6, 7.2.8, 7.2.9). Counting cyclic codes (7.2.12). The dimension of a cyclic code (7.2.14). Generator matrix of a cyclic code (7.3.1) and its dual (7.3.3, 7.3.7). Parity check polynomials and matricies (7.3.8, 7.3.9).
When errors occur in signals, often they occur in short intervals, rather than at random. Cyclic codes are particularly efficient for correcting burst errors.
This lecture will cover the following:
Syndromes and error patterns from generator polynomials (7.4.1, 7.4.3). Decoding algorythm for cyclic codes. Bursts (7.5.1) l-burst-error-correcting codes (7.5.3, 7.5.4). Decoding algorythm for cyclic burst-error-correcting-codes.
BCH are a generalisation of Hamming codes, in order to correct more than one error.
This lecture will cover (8.1) if necessary.
Reed-Solomon codes are an important class of codes which are both BCH codes and cyclic codes.
Given a prime p, a quadratic residue is different prime number l which is a square mod p. Quadratic residue codes are certain cyclic codes of length p over ℤl, where l is a quadratic residue mod p.
This lecture will cover (8.2) and (8.3) if necessary.