The Mathematics of Coding Theory
Published on 17. December 2003
Book
Hardback
408 pages
978-0-13-101967-6 (ISBN)
Description
For undergraduate courses in Coding Theory and Network Security, in departments of Mathematics, Electrical Engineering, and Computer Science.
This text makes a very accessible introduction to a very important contemporary application of number theory, abstract algebra, and probability. From credit cards to cellphones, codes are discussed both mathematically and with regard to industry protocols.
This text makes a very accessible introduction to a very important contemporary application of number theory, abstract algebra, and probability. From credit cards to cellphones, codes are discussed both mathematically and with regard to industry protocols.
More details
Language
English
Place of publication
United States
Publishing group
Pearson Education (US)
Target group
Professional and scholarly
Dimensions
Height: 183 mm
Width: 240 mm
Thickness: 20 mm
Weight
777 gr
ISBN-13
978-0-13-101967-6 (9780131019676)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Content
1. Probability.
Counting. Preliminary Ideas of Probability. More Formal View of Probability. Random Variables, Expected Values, Variance. Markov Inequality, Chebycheff Inequality. Law of Large Numbers.
2. Information and Entropy.
Uncertainty, Acquisition of Information. Entropy. Uniquely-Decipherable and Prefix Codes. Kraft and Macmillan Inequalities.
3. Noiseless Coding.
Noiseless Coding Theorem. Huffman Coding.
4. Noisy Coding.
Noisy channels. Example: Parity Checks. Decoding from a Noisy Channel. Channel Capacity. Noisy Coding Theorem.
5. Cyclic Redundancy Checks.
The Finite Field GF(2) with 2 Elements. Polynomials over GF(2). Cyclic Redundancy Checks (CRC's). What Errors Does a CRC Catch?
6. The Integers.
Reduction Algorithm. Divisibility. Factorization into Primes. Euclidean Algorithm. Integers Modulo M. The Finite Field Z/P for P Prime. Fermat's Little Theorem. Primitive Roots. Euler's Criterion. Fast Modular Exponentiation.
7. Finite Fields.
Making Fields. Examples of Field Extensions. Addition Modulo P. Multiplication Modulo P. Multiplicative Inverses Modulo P. Primitive Roots.
8. Polynomials.
Polynomials with Coefficients in a Field. Divisibility. Factoring and Irreducibility. Euclidean Algorithm. Unique Factorization.
9. Introduction to Linear Codes.
An Ugly Example. The Hamming Binary [7,4] Code. Some Linear Algebra. A Review of Row Reduction. Definition: Linear Codes. Syndrome Decoding. Berlekamp's Algorithm.
10. Bounds for Codes.
Hamming (Sphere-Packing) Bound. Gilbert-Varshamov Bound. Singleton Bound.
11. Cyclic Codes.
Minimum Distance in Linear Codes. Cyclic Codes.
12. Primitive Roots.
Characteristics of Fields. Multiple Factors in Polynomials. Cyclotomic Polynomials. Primitive Roots in Finite Fields. Primitive Roots Modulo Prime Powers. Counting Primitive Roots. Non-Existence. An Algorithm to Find Primitive Roots.
13. Primitive Polynomials.
Definitions. Examples Modulo 2. Testing for Primitivity. Example: Periods of LFSR's. Example: Two-Bit Errors Detected by CRC's.
14. Basic Linear Codes.
Vandermonde Determinants. More Check Matrices for Cyclic Codes. RS Codes. Hamming Codes (Again). BCH Codes. Decoding BCH Codes.
15. Concatenated Codes.
Mirage Codes. Concatenated Codes. Justesen Codes. Some Explicit Irreducible Polynomials.
16. Curves and Codes.
Plane Curves. Singularities of Curves. Projective Plane Curves. Curves in Higher Dimensions. Genus, Divisors, Linear Systems. Geometric Goppa Codes. Tsfasman-Vladut-Zink Bound.
Appendices.
Sets and functions. Equivalence Relations. Stirling's Formula.
Bibliography.
Index.
Counting. Preliminary Ideas of Probability. More Formal View of Probability. Random Variables, Expected Values, Variance. Markov Inequality, Chebycheff Inequality. Law of Large Numbers.
2. Information and Entropy.
Uncertainty, Acquisition of Information. Entropy. Uniquely-Decipherable and Prefix Codes. Kraft and Macmillan Inequalities.
3. Noiseless Coding.
Noiseless Coding Theorem. Huffman Coding.
4. Noisy Coding.
Noisy channels. Example: Parity Checks. Decoding from a Noisy Channel. Channel Capacity. Noisy Coding Theorem.
5. Cyclic Redundancy Checks.
The Finite Field GF(2) with 2 Elements. Polynomials over GF(2). Cyclic Redundancy Checks (CRC's). What Errors Does a CRC Catch?
6. The Integers.
Reduction Algorithm. Divisibility. Factorization into Primes. Euclidean Algorithm. Integers Modulo M. The Finite Field Z/P for P Prime. Fermat's Little Theorem. Primitive Roots. Euler's Criterion. Fast Modular Exponentiation.
7. Finite Fields.
Making Fields. Examples of Field Extensions. Addition Modulo P. Multiplication Modulo P. Multiplicative Inverses Modulo P. Primitive Roots.
8. Polynomials.
Polynomials with Coefficients in a Field. Divisibility. Factoring and Irreducibility. Euclidean Algorithm. Unique Factorization.
9. Introduction to Linear Codes.
An Ugly Example. The Hamming Binary [7,4] Code. Some Linear Algebra. A Review of Row Reduction. Definition: Linear Codes. Syndrome Decoding. Berlekamp's Algorithm.
10. Bounds for Codes.
Hamming (Sphere-Packing) Bound. Gilbert-Varshamov Bound. Singleton Bound.
11. Cyclic Codes.
Minimum Distance in Linear Codes. Cyclic Codes.
12. Primitive Roots.
Characteristics of Fields. Multiple Factors in Polynomials. Cyclotomic Polynomials. Primitive Roots in Finite Fields. Primitive Roots Modulo Prime Powers. Counting Primitive Roots. Non-Existence. An Algorithm to Find Primitive Roots.
13. Primitive Polynomials.
Definitions. Examples Modulo 2. Testing for Primitivity. Example: Periods of LFSR's. Example: Two-Bit Errors Detected by CRC's.
14. Basic Linear Codes.
Vandermonde Determinants. More Check Matrices for Cyclic Codes. RS Codes. Hamming Codes (Again). BCH Codes. Decoding BCH Codes.
15. Concatenated Codes.
Mirage Codes. Concatenated Codes. Justesen Codes. Some Explicit Irreducible Polynomials.
16. Curves and Codes.
Plane Curves. Singularities of Curves. Projective Plane Curves. Curves in Higher Dimensions. Genus, Divisors, Linear Systems. Geometric Goppa Codes. Tsfasman-Vladut-Zink Bound.
Appendices.
Sets and functions. Equivalence Relations. Stirling's Formula.
Bibliography.
Index.