Elements of Algebraic Coding Systems

Content: 1. Basic concepts --
1.1 Introduction --
1.2 Types of errors --
1.3 Channel models --
1.4 Linear codes and non-linear codes --
1.5 Block codes and convolutional codes --
1.6 Problems with solutions. 2. Block codes --
2.1 Introduction --
2.2 Matrix representation --
2.3 Minimum distance --
2.4 Error syndrome and decoding --
2.4.1 Maximum likelihood decoding --
2.4.2 Decoding by systematic search --
2.4.3 Probabilistic decoding --
2.5 Simple codes --
2.5.1 Repetition codes --
2.5.2 Single parity-check codes --
2.5.3 Hamming codes --
2.6 Low-density parity-check codes --
2.7 Problems with solutions. 3. Cyclic codes --
3.1 Matrix representation of a cyclic code --
3.2 Encoder with n --
k shift-register stages --
3.3 Cyclic Hamming codes --
3.4 Maximum-length-sequence codes --
3.5 Bose-Chaudhuri-Hocquenghem codes --
3.6 Reed-Solomon codes --
3.7 Golay codes --
3.7.1 The binary (23, 12, 7) Golay code --
3.7.2 The ternary (11, 6, 5) Golay code --
3.8 Reed-Muller codes --
3.9 Quadratic residue codes --
3.10 Alternant codes --
3.11 Problems with solutions. 4. Decoding cyclic codes --
4.1 Meggitt decoder --
4.2 Error-trapping decoder --
4.3 Information set decoding --
4.4 Threshold decoding --
4.5 Algebraic decoding --
4.5.1 Berlekamp-Massey time domain decoding --
4.5.2 Euclidean frequency domain decoding --
4.6 Soft-decision decoding --
4.6.1 Decoding LDPC codes --
4.7 Problems with solutions. 5. Irreducible polynomials over finite fields --
5.1 Introduction --
5.2 Order of a polynomial --
5.3 Factoring xqn --
x --
5.4 Counting monic irreducible q-ary polynomials --
5.5 The Moebius inversion technique --
5.5.1 The additive Moebius inversion formula --
5.5.2 The multiplicative Moebius inversion formula --
5.5.3 The number of irreducible polynomials of degree n over GF(q) --
5.6 Chapter citations --
5.7 Problems with solutions. 6. Finite field factorization of polynomials --
6.1 Introduction --
6.2 Cyclotomic polynomials --
6.3 Canonical factorization --
6.4 Eliminating repeated factors --
6.5 Irreducibility of ̲[phi]n(x) over GF(q) --
6.6 Problems with solutions. 7. Constructing f-reducing polynomials --
7.1 Introduction --
7.2 Factoring polynomials over large finite fields --
7.2.1 Resultant --
7.2.2 Algorithm for factorization based on the resultant --
7.2.3 The Zassenhaus algorithm --
7.3 Finding roots of polynomials over finite fields --
7.3.1 Finding roots when p is large --
7.3.2 Finding roots when q = pm is large but p is small --
7.4 Problems with solutions. 8. Linearized polynomials --
8.1 Introduction --
8.2 Properties of L(x) --
8.3 Properties of the roots of L(x) --
8.4 Finding roots of L(x) --
8.5 Affine q-polynomials --
8.6 Problems with solutions. 9. Goppa codes --
9.1 Introduction --
9.2 Parity-check equations --
9.3 Parity-check matrix of Goppa codes --
9.4 Algebraic decoding of Goppa codes --
9.4.1 The Patterson algorithm --
9.4.2 The Blahut algorithm --
9.5 The asymptotic Gilbert bound --
9.6 Quadratic equations over GF(2m) --
9.7 Adding an overall parity-check digit --
9.8 Affine transformations --
9.9 Cyclic binary double-error correcting --
10. Extended Goppa codes --
9.10 Extending the Patterson algorithm for decoding Goppa codes --
9.11 Problems with solutions. 10. Coding-based cryptosystems --
10.1 Introduction --
10.2 McEliece\'s public-key cryptosystem --
10.2.1 Description of the cryptosystem --
10.2.2 Encryption --
10.2.3 Decryption --
10.2.4 Cryptanalysis --
10.2.5 Trapdoors --
10.3 Secret-key algebraic coding systems --
10.3.1 A (possible) known-plaintext attack --
10.3.2 A chosen-plaintext attack --
10.3.3 A modified scheme --
10.4 Problems with solutions. 11. Majority logic decoding --
11.1 Introduction --
11.2 One-step majority logic decoding --
11.3 Multiple-step majority logic decoding I --
11.4 Multiple-step majority logic decoding II --
11.5 Reed-Muller codes --
11.6 Affine permutations and code construction --
11.7 A class of one-step decodable codes --
11.8 Generalized Reed-Muller codes --
11.9 Euclidean geometry codes --
11.10 Projective geometry codes --
11.11 Problems with solutions. Appendices --
A. The Gilbert bound --
A.1. Introduction --
A.2. The binary asymptotic Gilbert bound --
A.3. Gilbert bound for linear codes --
B. MacWilliams\' identity for linear codes --
B.1. Introduction --
B.2. The binary symmetric channel --
B.3. Binary linear codes and error detection --
B.4. The q-ary symmetric channel --
B.5. Linear codes over GF(q) --
B.6. The binomial expansion --
B.7. Digital transmission using N regenerative repeaters --
C. Frequency domain decoding tools --
C.1. Finite field Fourier transform --
C.2. The Euclidean algorithm.