Berlekamp E.E. Algebraic coding theory (Singapore, 2015). - ОГЛАВЛЕНИЕ / CONTENTS
Навигация

Архив выставки новых поступлений | Отечественные поступления | Иностранные поступления | Сиглы
ОбложкаBerlekamp E.E. Algebraic coding theory. - Rev. ed. - Singapore: World scientific, 2015. - xxiv, 474 p.: ill. - Bibliogr.: p.443-459. - Ind.: p.461-474. - ISBN 978-981-4635-89-9
Шифр: (И/З.81-B47) 02

 

Место хранения: 02 | Отделение ГПНТБ СО РАН | Новосибирск

Оглавление / Contents
 
Preface to the Revised Edition ................................ vii
Preface to the Second Edition ................................ xiii
Preface ........................................................ xv
Acknowledgments ............................................... xix

1  Basic Binary Codes ........................................... 1
   1.1  Repetition Codes and Single-Parity-Check Codes .......... 1
   1.2  Linear Codes ............................................ 4
   1.3  Hamming Codes ........................................... 8
   1.4  Manipulative Introduction to Double-Error-
        Correcting BCH Codes ................................... 12
   Problems .................................................... 20
2  Arithmetic Operations Modulo an Irreducible Binary
   Polynomial .................................................. 21
   2.1  A Closer Look at Euclid's Algorithm .................... 21
   2.2  Logical Circuitry ...................................... 30
   2.3  Multiplicative Inversion ............................... 36
   2.4  Multiplication ......................................... 44
   2.5  The Solution of Simultaneous Linear Equations .......... 51
   2.6  Special Methods for Solving Simultaneous Linear
        Equations When the Coefficient Matrix is Mostly
        Zeros .................................................. 63
   Problems .................................................... 69
3  The Number of Irreducible q-ary Polynomials of Given
   Degree ...................................................... 70
   3.1  A Brute-Force Attack ................................... 70
   3.2  Generating Functions ................................... 73
   3.3  The Number of Irreducible Monic q-ary Polynomials
        of Given Degree - A Refined Approach ................... 76
   3.4  The Moebius Inversion Formulas ......................... 81
   Problems .................................................... 85

STARRED SECTIONS MAY BE SKIPPED ON FIRST READING.
4  The Structure of Finite Fields .............................. 87
   4.1  Definitions ............................................ 87
   4.2  Multiplicative Structure of Finite Fields .............. 88
   4.3  Cyclotomic Polynomials ................................. 90
   4.4  Algebraic Structure of Finite Fields ................... 96
   4.5  Examples .............................................. 105
   4.6 Algebraic Closure ...................................... 111
   4.7   Determining Minimal Polynomials ...................... 112
   Problems ................................................... 117
5  Cyclic Binary Codes ........................................ 119
   5.1  Reordering the Columns of the Parity-Check
        Matrix of Hamming Codes ............................... 119
   5.2  Reordering the Columns of the Parity-Check Matrix
        of Double-Error-Correcting Binary BCH Codes ........... 125
   5.3  General Properties of Cyclic Codes .................... 129
   5.4  The Chien Search ...................................... 132
   5.5  Outline of General Decoder for Any Cyclic Binary
        Code .................................................. 136
   5.6  Example ............................................... 138
   5.7  Example ............................................... 139
   5.8  Equivalence of Cyclic Codes Defined in Terms
        of Different Primitive nth Roots of Unity ............. 141
   Problems ................................................... 144
6  The Factorization of Polynomials Over Finite Fields ........ 146
   6.1   A General Algorithm .................................. 146
   6.2  Determining the Period of a Polynomial ................ 150
   6.3  Trinomials Over GF(2) ................................. 153
   6.4  Factoring xn - 1 Explicitly ........................... 154
   6.5  Determining the Degrees of the Irreducible
   Factors of the Cyclotomic Polynomials ...................... 156
   6.6  Is the Number of Irreducible Factors of ƒ(x)
        Over GF(q) Odd or Even? ............................... 159
   6.7  Quadratic Reciprocity ................................. 171
   Problems ................................................... 173
7  Binary BCH Codes for Correcting Multiple Errors ............ 176
   7.1  Examples .............................................. 176
   7.2  The Key Equation for Decoding Binary BCH Codes ........ 178
   7.3  Heuristic Solution of the Key Equation ................ 180
   7.4  An Algorithm for Solving the Key Equation Over
        Any Field ............................................. 184
   7.5  Relation to Matrix Decoding Methods ................... 188
   7.6  Simplifications in Algorithm 7.4 for Binary BCH
        Codes ................................................. 192
   7.7  Implementation of Binary BCH Decoders ................. 195
   Problems ................................................... 199
8  Nonbinary Coding ........................................... 200
   8.1  Modulation Schemes .................................... 200
   8.2  Weight Functions ...................................... 204
   Problem .................................................... 206
9  Negacyclic Codes for the Lee Metric ........................ 207
   9.1  Error Locations and the Error-Locator Polynomial ...... 207
   9.2  Double-Error-Correcting Codes ......................... 209
   9.3  Negacyclic Codes ...................................... 211
   Problems ................................................... 217
10 Gorenstein-Zierler Generalized Nonbinary BCH Codes for
   the Hamming Metric ......................................... 218
   10.1 The Generalized BCH Codes and An Algorithm to
        Decode Them ........................................... 218
   10.2 Examples .............................................. 221
   10.3 Alternate BCH Codes and Extended BCH Codes ............ 223
   10.4 Decoding Erasures as Well as Errors ................... 229
   10.5 Decoding More Than t Errors ........................... 231
   10.6 Examples .............................................. 237
   Problem .................................................... 240
11 Linearized Polynomials and Affine Polynomials .............. 241
   11.1 How to Find Their Roots ............................... 241
   11.2 The Least Affine Multiple ............................. 245
   11.3 Abstract Properties of Linearized and Affine
        Polynomials ........................................... 247
   11.4 Transformations of fig.1(z) ............................... 255
   11.5 Root Counting ......................................... 257
   11.6 Low-Weight Codewords in Certain Codes ................. 262
   Problems ................................................... 271
12 The Enumeration of Information Symbols in BCH Codes ........ 273
   12.1 Converting the Problem to an Enumeration
        of Certain Integers mod n ............................. 273
   12.2 Converting the Problem for Primitive BCH Codes to
        an Enumeration of Certain q-ary Sequences ............. 275
   12.3 Sequence Enumeration Theorems ......................... 278
   12.4 Examples .............................................. 284
   12.5 The Enumeration of Information Symbols in
        Nonprimitive BCH Codes ................................ 287
   12.6 Asymptotic Results .................................... 290
   12.7 Actual Distance ....................................... 294
   Problems ................................................... 296
13 The Information Rate of the Optimum Codes .................. 298
   13.1 The Hamming-Rao High-Rate Volume Bound ................ 298
   13.2 Perfect Codes ......................................... 302
   13.3 The Bound d ≤ n + 1 - k ............................... 309
   13.4 Plotkin's Low-Rate Average Distance Bound ............. 311
   13.5 Equidistant Codes ..................................... 315
   13.6 The Elias Bound ....................................... 318
   13.7 The Gilbert Bound ..................................... 321
   13.8 Asymptotic Error Bounds and Finite Special Cases ...... 324
14 Codes Derived by Modifying or Combining Other Codes ........ 331
   14.1 Extending a Code by Annexing More Check Digits ........ 333
   14.2 Puncturing a Code by Deleting Check Digits ............ 334
   14.3 Augmenting Additional Codewords to the Code ........... 335
   14.4 Expurgating Codewords from the Code ................... 335
   14.5 Lengthening the Code by Annexing More Message
        Digits ................................................ 336
   14.6 Shortening the Code by Omitting Message Digits ........ 336
   14.7 Subfield Subcodes ..................................... 336
   14.8 Direct-Product Codes and Their Relatives .............. 338
   14.9 Concatenated Codes .................................... 347
15 Other Important Coding and Decoding Methods ................ 350
   15.1 Srivastava Codes - Noncyclic Codes with an
        Algebraic Decoding Algorithm .......................... 350
   15.2 Residue Codes - Good Codes Which are Hard to Decode ... 352
   15.3 Reed-Muller Codes - Weak Codes Which are Easy to
        Decode ................................................ 361
   15.4 Threshold Decoding - The Best Known Algorithm for
        Decoding Certain Codes ................................ 367
   15.5 Orthogonalizable Codes Based on Finite Geometries ..... 375
   15.6 Convolutional Codes - A Survey ........................ 388
   Problems ................................................... 394
16 Weight Enumerators ......................................... 397
   16.1 The Relationship between Weight Enumerators
        and the Probability of Decoding Failure ............... 397
   16.2 The MacWilliams-Pless Equations for the
        Weight Enumerators of Dual Codes ...................... 400
   16.3 Weight Restrictions ................................... 407
   16.4 Kasami's Weight Enumerators for Certain
        Subcodes of the Second - Order RM Code ................ 417
   16.5 The Weight Enumerator for the Reed - Solomon 
        Codes ................................................. 429

Appendix A .................................................... 441
Appendix В .................................................... 442
References .................................................... 443
References to the Second Edition .............................. 453
Index ......................................................... 461


Документ изменен: . Размер: bytes.
Посещение N c 13.09.2016