| |
| |
| Preface | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Communication systems | |
| |
| |
| |
| Channel coding | |
| |
| |
| |
| Block codes | |
| |
| |
| |
| Decoding | |
| |
| |
| |
| Levels of error handling | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Linear Codes | |
| |
| |
| |
| Definition | |
| |
| |
| |
| Encoding of linear codes | |
| |
| |
| |
| Parity-check matrix | |
| |
| |
| |
| Decoding of linear codes | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Introduction to Finite Fields | |
| |
| |
| |
| Prime fields | |
| |
| |
| |
| Polynomials | |
| |
| |
| |
| Extension fields | |
| |
| |
| |
| Roots of polynomials | |
| |
| |
| |
| Primitive elements | |
| |
| |
| |
| Field characteristic | |
| |
| |
| |
| Splitting field | |
| |
| |
| |
| Application: double error-correcting codes | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Bounds on the Parameters of Codes | |
| |
| |
| |
| The Singleton bound | |
| |
| |
| |
| The sphere-packing bound | |
| |
| |
| |
| The Gilbert-Varshamov bound | |
| |
| |
| |
| MacWilliams' identities | |
| |
| |
| |
| Asymptotic bounds | |
| |
| |
| |
| Converse Coding Theorem | |
| |
| |
| |
| Coding Theorem | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Reed-Solomon and Related Codes | |
| |
| |
| |
| Generalized Reed-Solomon codes | |
| |
| |
| |
| Conventional Reed-Solomon codes | |
| |
| |
| |
| Encoding of RS codes | |
| |
| |
| |
| Concatenated codes | |
| |
| |
| |
| Alternant codes | |
| |
| |
| |
| BCH codes | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Decoding of Reed-Solomon Codes | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Syndrome computation | |
| |
| |
| |
| Key equation of GRS decoding | |
| |
| |
| |
| Solving the key equation by Euclid's algorithm | |
| |
| |
| |
| Finding the error values | |
| |
| |
| |
| Summary of the GRS decoding algorithm | |
| |
| |
| |
| The Berlekamp-Massey algorithm | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Structure of Finite Fields | |
| |
| |
| |
| Minimal polynomials | |
| |
| |
| |
| Enumeration of irreducible polynomials | |
| |
| |
| |
| Isomorphism of finite fields | |
| |
| |
| |
| Primitive polynomials | |
| |
| |
| |
| Cyclotomic cosets | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Cyclic Codes | |
| |
| |
| |
| Definition | |
| |
| |
| |
| Generator polynomial and check polynomial | |
| |
| |
| |
| Roots of a cyclic code | |
| |
| |
| |
| BCH codes as cyclic codes | |
| |
| |
| |
| The BCH bound | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| List Decoding of Reed-Solomon Codes | |
| |
| |
| |
| List decoding | |
| |
| |
| |
| Bivariate polynomials | |
| |
| |
| |
| GRS decoding through bivariate polynomials | |
| |
| |
| |
| Sudan's algorithm | |
| |
| |
| |
| The Guruswami-Sudan algorithm | |
| |
| |
| |
| List decoding of alternant codes | |
| |
| |
| |
| Fiding linear bivariate factors | |
| |
| |
| |
| Bounds on the decoding radius | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Codes in the Lee Metric | |
| |
| |
| |
| Lee weight and Lee distance | |
| |
| |
| |
| Newton's identities | |
| |
| |
| |
| Lee-metric alternant codes and GRS codes | |
| |
| |
| |
| Decoding alternant codes in the Lee metric | |
| |
| |
| |
| Decoding GRS codes in the Lee metric | |
| |
| |
| |
| Berlekamp codes | |
| |
| |
| |
| Bounds for codes in the Lee metric | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| MDS Codes | |
| |
| |
| |
| Definition revisited | |
| |
| |
| |
| GRS codes and their extensions | |
| |
| |
| |
| Bounds on the length of linear MDS codes | |
| |
| |
| |
| GRS codes and the MDS conjecture | |
| |
| |
| |
| Uniqueness of certain MDS codes | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Concatenated Codes | |
| |
| |
| |
| Definition revisited | |
| |
| |
| |
| Decoding of concatenated codes | |
| |
| |
| |
| The Zyablov bound | |
| |
| |
| |
| Justesen codes | |
| |
| |
| |
| Concatenated codes that attain capacity | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Graph Codes | |
| |
| |
| |
| Basic concepts from graph theory | |
| |
| |
| |
| Regular graphs | |
| |
| |
| |
| Graph expansion | |
| |
| |
| |
| Expanders from codes | |
| |
| |
| |
| Ramanujan graphs | |
| |
| |
| |
| Codes from expanders | |
| |
| |
| |
| Iterative decoding of graph codes | |
| |
| |
| |
| Graph codes in concatenated schemes | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Trellis and Convolutional Codes | |
| |
| |
| |
| Labeled directed graphs | |
| |
| |
| |
| Trellis codes | |
| |
| |
| |
| Decoding of trellis codes | |
| |
| |
| |
| Linear finite-state machines | |
| |
| |
| |
| Convolutional codes | |
| |
| |
| |
| Encoding of convolutional codes | |
| |
| |
| |
| Decoding of convolutional codes | |
| |
| |
| |
| Non-catastrophic generator matrices | |
| |
| |
| Problems | |
| |
| |
| Notes | |
| |
| |
| |
| Basics in Modern Algebra | |
| |
| |
| Problems | |
| |
| |
| Bibliography | |
| |
| |
| List of Symbols | |
| |
| |
| Index | |