Linked e-resources
Details
Table of Contents
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
Bibliography
About the author
Index.
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
Bibliography
About the author
Index.