| |
| |
| |
| Probability | |
| |
| |
| Counting | |
| |
| |
| Preliminary Ideas of Probability | |
| |
| |
| More Formal View of Probability | |
| |
| |
| Random Variables, Expected Values, Variance | |
| |
| |
| Markov Inequality, Chebycheff Inequality | |
| |
| |
| Law of Large Numbers | |
| |
| |
| |
| Information and Entropy | |
| |
| |
| Uncertainty, Acquisition of Information | |
| |
| |
| Entropy | |
| |
| |
| Uniquely-Decipherable and Prefix Codes | |
| |
| |
| Kraft and Macmillan Inequalities | |
| |
| |
| |
| Noiseless Coding | |
| |
| |
| Noiseless Coding Theorem | |
| |
| |
| Huffman Coding | |
| |
| |
| |
| Noisy Coding | |
| |
| |
| Noisy channels | |
| |
| |
| Example: Parity Checks | |
| |
| |
| Decoding from a Noisy Channel | |
| |
| |
| Channel Capacity | |
| |
| |
| Noisy Coding Theorem | |
| |
| |
| |
| 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 | |
| |
| |
| 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 | |
| |
| |
| |
| Finite Fields | |
| |
| |
| Making Fields | |
| |
| |
| Examples of Field Extensions | |
| |
| |
| Addition Modulo P | |
| |
| |
| Multiplication Modulo P | |
| |
| |
| Multiplicative Inverses Modulo P | |
| |
| |
| Primitive Roots | |
| |
| |
| |
| Polynomials | |
| |
| |
| Polynomials with Coefficients in a Field | |
| |
| |
| Divisibility | |
| |
| |
| Factoring and Irreducibility | |
| |
| |
| Euclidean Algorithm | |
| |
| |
| Unique Factorization | |
| |
| |
| |
| 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 | |
| |
| |
| |
| Bounds for Codes | |
| |
| |
| Hamming (Sphere-Packing) Bound | |
| |
| |
| Gilbert-Varshamov Bound | |
| |
| |
| Singleton Bound | |
| |
| |
| |
| Cyclic Codes | |
| |
| |
| Minimum Distance in Linear Codes | |
| |
| |
| Cyclic Codes | |
| |
| |
| |
| 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 | |
| |
| |
| |
| Primitive Polynomials | |
| |
| |
| Definitions | |
| |
| |
| Examples Modulo 2 | |
| |
| |
| Testing for Primitivity | |
| |
| |
| Example: Periods of LFSR's | |
| |
| |
| Example: Two-Bit Errors Detected by CRC's | |
| |
| |
| |
| Basic Linear Codes | |
| |
| |
| Vandermonde Determinants | |
| |
| |
| More Check Matrices for Cyclic Codes | |
| |
| |
| RS Codes | |
| |
| |
| Hamming Codes (Again) | |
| |
| |
| BCH Codes | |
| |
| |
| Decoding BCH Codes | |
| |
| |
| |
| Concatenated Codes | |
| |
| |
| Mirage Codes | |
| |
| |
| Concatenated Codes | |
| |
| |
| Justesen Codes | |
| |
| |
| Some Explicit Irreducible Polynomials | |
| |
| |
| |
| 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 | |