| |
| |
| Preface | |
| |
| |
| |
| Coding Theory | |
| |
| |
| |
| Introduction to Coding Theory | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Basic assumptions | |
| |
| |
| |
| Correcting and detecting error patterns | |
| |
| |
| |
| Information rate | |
| |
| |
| |
| The effects of error correction and detection | |
| |
| |
| |
| Finding the most likely codeword transmitted | |
| |
| |
| |
| Some basic algebra | |
| |
| |
| |
| Weight and distance | |
| |
| |
| |
| Maximum likelihood decoding | |
| |
| |
| |
| Reliability of MLD | |
| |
| |
| |
| Error-detecting codes | |
| |
| |
| |
| Error-correcting codes | |
| |
| |
| |
| Linear Codes | |
| |
| |
| |
| Linear codes | |
| |
| |
| |
| Two important subspaces | |
| |
| |
| |
| Independence, basis, dimension | |
| |
| |
| |
| Matrices | |
| |
| |
| |
| Bases for C = [S] and C[superscript perpendicular, bottom] | |
| |
| |
| |
| Generating matrices and encoding | |
| |
| |
| |
| Parity-check matrices | |
| |
| |
| |
| Equivalent codes | |
| |
| |
| |
| Distance of a linear code | |
| |
| |
| |
| Cosets | |
| |
| |
| |
| MLD for linear codes | |
| |
| |
| |
| Reliability of IMLD for linear codes | |
| |
| |
| |
| Perfect and Related Codes | |
| |
| |
| |
| Some bounds for codes | |
| |
| |
| |
| Perfect codes | |
| |
| |
| |
| Hamming codes | |
| |
| |
| |
| Extended codes | |
| |
| |
| |
| The extended Golay code | |
| |
| |
| |
| Decoding the extended Golay code | |
| |
| |
| |
| The Golay code | |
| |
| |
| |
| Reed-Muller codes | |
| |
| |
| |
| Fast decoding for RM(1, m) | |
| |
| |
| |
| Cyclic Linear Codes | |
| |
| |
| |
| Polynomials and words | |
| |
| |
| |
| Introduction to cyclic codes | |
| |
| |
| |
| Generating and parity check matrices for cyclic codes | |
| |
| |
| |
| Finding cyclic codes | |
| |
| |
| |
| Dual cyclic codes | |
| |
| |
| |
| BCH Codes | |
| |
| |
| |
| Finite fields | |
| |
| |
| |
| Minimal polynomials | |
| |
| |
| |
| Cyclic Hamming codes | |
| |
| |
| |
| BCH codes | |
| |
| |
| |
| Decoding 2 error-correcting BCH code | |
| |
| |
| |
| Reed-Solomon Codes | |
| |
| |
| |
| Codes over GF(2[superscript r]) | |
| |
| |
| |
| Reed-Solomon codes | |
| |
| |
| |
| Decoding Reed-Solomon codes | |
| |
| |
| |
| Transform approach to Reed-Solomon codes | |
| |
| |
| |
| Berlekamp-Massey algorithm | |
| |
| |
| |
| Erasures | |
| |
| |
| |
| Burst Error-Correcting Codes | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Interleaving | |
| |
| |
| |
| Application to compact discs | |
| |
| |
| |
| Convolutional Codes | |
| |
| |
| |
| Shift registers and polynomials | |
| |
| |
| |
| Encoding convolutional codes | |
| |
| |
| |
| Decoding convolutional codes | |
| |
| |
| |
| Truncated Viterbi decoding | |
| |
| |
| |
| Reed-Muller and Preparata Codes | |
| |
| |
| |
| Reed-Muller codes | |
| |
| |
| |
| Decoding Reed-Muller codes | |
| |
| |
| |
| Extended Preparata codes | |
| |
| |
| |
| Encoding extended Preparata codes | |
| |
| |
| |
| Decoding extended Preparata codes | |
| |
| |
| |
| Cryptography | |
| |
| |
| |
| Classical Cryptography | |
| |
| |
| |
| Encryption schemes | |
| |
| |
| |
| Symmetric-key encryption | |
| |
| |
| |
| Feistel ciphers and DES | |
| |
| |
| |
| The New Data Seal | |
| |
| |
| |
| The Data Encryption Standard | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Topics in Algebra and Number Theory | |
| |
| |
| |
| Algorithms, complexity, and modular arithmetic | |
| |
| |
| |
| Quadratic residues | |
| |
| |
| |
| Primality testing | |
| |
| |
| |
| Factoring and square roots | |
| |
| |
| |
| Pollard's rho | |
| |
| |
| |
| Random squares | |
| |
| |
| |
| Square roots | |
| |
| |
| |
| Discrete logarithms | |
| |
| |
| |
| Baby-step giant-step | |
| |
| |
| |
| Index calculus | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Public-key Cryptography | |
| |
| |
| |
| One-way and hash functions | |
| |
| |
| |
| RSA | |
| |
| |
| |
| Provable security | |
| |
| |
| |
| ElGamal | |
| |
| |
| |
| Cryptographic protocols | |
| |
| |
| |
| Diffie-Hellman key agreement | |
| |
| |
| |
| Zero-knowledge proofs | |
| |
| |
| |
| Coin-tossing and mental poker | |
| |
| |
| |
| Notes | |
| |
| |
| |
| The Euclidean Algorithm | |
| |
| |
| |
| Factorization of 1 + x[superscript n] | |
| |
| |
| |
| Example of Compact Disc Encoding | |
| |
| |
| |
| Solutions to Selected Exercises | |
| |
| |
| Bibliography | |
| |
| |
| Index | |