Coding Theory : A First Course

Coding Theory Is Concerned With Successfully Transmitting Data Through A Noisy Channel And Correcting Errors In Corrupted Messages. It Is Of Central Importance For Many Applications In Computer Science Or Engineering. This Book Gives A Comprehensive Introduction To Coding Theory Whilst Only Assuming Basic Linear Algebra. It Contains A Detailed And Rigorous Introduction To The Theory Of Block Codes And Moves On To More Advanced Topics Like Bch Codes, Goppa Codes And Sudan's Algorithm For List Decoding. The Issues Of Bounds And Decoding, Essential To The Design Of Good Codes, Features Prominently. The Authors Of This Book Have, For Several Years, Successfully Taught A Course On Coding Theory To Students At The National University Of Singapore. This Book Is Based On Their Experiences And Provides A Thoroughly Modern Introduction To The Subject. There Are Numerous Examples And Exercises, Some Of Which Introduce Students To Novel Or More Advanced Material. San Ling, Chaoping Xing. Title From Publisher's Bibliographic System (viewed On 01 Jun 2016). Mode Of Access: World Wide Web. Cover......Page 1 Half-title......Page 3 Title......Page 5 Copyright......Page 6 Dedication......Page 7 Contents......Page 9 Preface......Page 13 1 Introduction......Page 15 Exercises......Page 18 2.1 Communication channels......Page 19 2.3 Hamming distance......Page 22 2.4 Nearest neighbour/minimum distance decoding......Page 24 2.5 Distance of a code......Page 25 Exercises......Page 28 3.1 Fields......Page 31 3.2 Polynomial rings......Page 36 3.3 Structure of finite fields......Page 40 3.4 Minimal polynomials......Page 44 Exercises......Page 50 4.1 Vector spaces over finite fields......Page 53 4.2 Linear codes......Page 59 4.3 Hamming weight......Page 60 4.4 Bases for linear codes......Page 62 4.5 Generator matrix and parity-check matrix......Page 66 4.6 Equivalence of linear codes......Page 70 4.7 Encoding with a linear code......Page 71 4.8.1 Cosets......Page 73 4.8.2 Nearest neighbour decoding for linear codes......Page 75 4.8.3 Syndrome decoding......Page 76 Exercises......Page 80 5.1 The main coding theory problem......Page 89 5.2.1 Sphere-covering bound......Page 94 5.2.2 Gilbert–Varshamov bound......Page 96 5.3 Hamming bound and perfect codes......Page 97 5.3.1 Binary Hamming codes......Page 98 Decoding with a binary Hamming code......Page 99 5.3.2 q-ary Hamming codes......Page 101 5.3.3 Golay codes......Page 102 Binary Golay codes......Page 103 Ternary Golay codes......Page 105 5.4 Singleton bound and MDS codes......Page 106 5.5 Plotkin bound......Page 109 5.6 Nonlinear codes......Page 110 5.6.2 Nordstrom–Robinson code......Page 112 5.6.4 Kerdock codes......Page 113 5.7 Griesmer bound......Page 114 5.8 Linear programming bound......Page 116 Exercises......Page 120 6.1 Propagation rules......Page 127 6.2 Reed–Muller codes......Page 132 6.3 Subfield codes......Page 135 Exercises......Page 140 7.1 Definitions......Page 147 7.2 Generator polynomials......Page 150 7.3 Generator and parity-check matrices......Page 155 7.4 Decoding of cyclic codes......Page 159 Decoding algorithm for cyclic codes......Page 162 Decoding algorithm for cyclic burst-error-correcting codes......Page 165 7.5 Burst-error-correcting codes......Page 164 Exercises......Page 167 8.1.1 Definitions......Page 173 8.1.2 Parameters of BCH codes......Page 175 8.1.3 Decoding of BCH codes......Page 182 8.2 Reed–Solomon codes......Page 185 8.3 Quadratic-residue codes......Page 189 Exercises......Page 197 9.1 Generalized Reed–Solomon codes......Page 203 9.2 Alternant codes......Page 206 9.3 Goppa codes......Page 210 9.4 Sudan decoding for generalized RS codes......Page 216 9.4.1 Generation of the (P, k, t)-polynomial......Page 217 9.4.2 Factorization of the (P, k, t)-polynomial......Page 219 Factoring algorithm......Page 222 Exercises......Page 223 References......Page 229 Bibliography......Page 231 Index......Page 233 Preface page xi 1 Introduction 1 Exercises 4 2 Error detection, correction and decoding 5 2.1 Communication channels 5 2.2 Maximum likelihood decoding 8 2.3 Hamming distance 8 2.4 Nearest neighbour/minimum distance decoding 10 2.5 Distance of a code 11 Exercises 14 3 Finite fields 17 3.1 Fields 17 3.2 Polynomial rings 22 3.3 Structure of finite fields 26 3.4 Minimal polynomials 30 Exercises 36 4 Linear codes 39 4.1 Vector spaces over finite fields 39 4.2 Linear codes 45 4.3 Hamming weight 46 4.4 Bases for linear codes 48 4.5 Generator matrix and parity-check matrix 52 4.6 Equivalence of linear codes 56 4.7 Encoding with a linear code 57 4.8 Decoding of linear codes 59 4.8.1 Cosets 59 4.8.2 Nearest neighbour decoding for linear codes 61 4.8.3 Syndrome decoding 62 Exercises 66 5 Bounds in coding theory 75 5.1 The main coding theory problem 75 5.2 Lower bounds 80 5.2.1 Sphere-covering bound 80 5.2.2 Gilbert-Varshamov bound 82 5.3 Hamming bound and perfect codes 83 5.3.1 Binary Hamming codes 84 5.3.2 q-ary Hamming codes 87 5.3.3 Golay codes 88 5.3.4 Some remarks on perfect codes 92 5.4 Singleton bound and MDS codes 92 5.5 Plotkin bound 95 5.6 Nonlinear codes 96 5.6.1 Hadamard matrix codes 98 5.6.2 Nordstrom-Robinson code 98 5.6.3 Preparata codes 99 5.6.4 Kerdock codes 99 5.7 Griesmer bound 100 5.8 Linear programming bound 102 Exercises 106 6 Constructions of linear codes 113 6.1 Propagation rules 113 6.2 Reed-Muller codes 118 6.3 Subfield codes 121 Exercises 126 7 Cyclic codes 133 7.1 Definitions 133 7.2 Generator polynomials 136 7.3 Generator and parity-check matrices 141 7.4 Decoding of cyclic codes 145 7.5 Burst-error-correcting codes 150 Exercises 153 8 Some special cyclic codes 159 8.1 BCH codes 159 8.1.1 Definitions 159 8.1.2 Parameters of BCH codes 161 8.1.3 Decoding of BCH codes 168 8.2 Reed-Solomon codes 171 8.3 Quadratic-residue codes 175 Exercises 183 9 Goppa codes 189 9.1 Generalized Reed-Solomon codes 189 9.2 Altemant codes 192 9.3 Goppa codes 196 9.4 Sudan decoding for generalized RS codes 202 9.4.1 Generation of the (P, k, t)-polynomial 203 9.4.2 Factorization of the (P, k, t)-polynomial 205 Exercises 209 References 215 Bibliography 217 Index 219 Concerned with successfully transmitting data through a noisy channel, coding theory can be applied to electronic engineering and communications. Based on the authors' extensive teaching experience, this text provides a completely modern and accessible course on the subject. It includes sections on linear programming and decoding methods essential for contemporary mathematics. Numerous examples and exercises make the volume ideal for students and instructors. Based on the authors' teaching experiences, this book provides a thoroughly modern introduction to the coding theory - a subject of central importance for many applications in engineering and computer science. There are numerous examples and exercises, some of which introduce students to novel or more advanced material Information media, such as communication systems and storage devices of data, are not absolutely reliable in practice because of noise or other forms of introduced interference.

modern Introduction To Theory Of Coding And Decoding With Many Exercises And Examples.