Theory of Codes (eBook)

Front Cover 1
Theory of Codes 4
Copyright Page 5
Contents 8
Preface 12
Chapter 0. Preliminaries 16
0 Introduction 16
1 Notation 16
2 Monoids 17
3 Words 19
4 Automata 25
5 Ideals in a Monoid 33
6 Semirings and Matrices 41
7 Formal Series 44
8 Permutation Groups 47
9 Notes 51
Chapter 1. Codes 52
0 Introduction 52
1 Definitions 52
2 Codes and Submonoids 57
3 A Test for Codes 65
4 Measure of a Code 69
5 Complete Sets 76
6 Composition 86
7 Exercises 93
8 Notes 96
Chapter 2. Prefix Codes 98
0 Introduction 98
1 Prefix Codes 99
2 The Automaton of a Prefix Code 105
3 Maximal Prefix Codes 113
4 Operations on Prefix Codes 118
5 Semaphore Codes 122
6 Synchronous Codes 130
7 Average Length 136
8 Deciphering Delay 143
9 Exercises 149
10 Notes 154
Chapter 3. Biprefix Codes 155
0 Introduction 155
1 Parses 156
2 Maximal Biprefix Codes 159
3 Degree 165
4 Kernel 178
5 Finite Maximal Biprefix Codes 183
6 Exercises 190
7 Notes 193
Chapter 4. Automata 195
0 Introduction 195
1 Automata 197
2 Flower Automaton 204
3 Monoids of Unambiguous Relations 217
4 Rank and Minimal Ideal 232
5 Very Thin Codes 239
6 Group and Degree of a Code 249
7 Synchronization of Semaphores 263
8 Exercises 270
9 Notes 275
Chapter 5. Groups of Biprefix Codes 276
0 Introduction 276
1 Group Codes 277
2 Automata of Biprefix Codes 279
3 Depth 284
4 Groups of Finite Biprefix Codes 286
5 Examples 294
6 Exercises 300
7 Notes 303
Chapter 6. Densities 305
0 Introduction 305
1 Densities 305
2 Probabilities over a Monoid 311
3 Contexts 324
4 Exercises 333
5 Notes 335
Chapter 7. Conjugacy 336
0 Introduction 336
1 Circular Codes 337
2 Limited Codes 344
3 Length Distributions 352
4 Factorizations of Free Monoids 366
5 Finite Factorizations 379
6 Exercises 389
7 Notes 392
Chapter 8. Polynomial of a Code 394
0 Introduction 394
1 Factorizing Codes 395
2 Determinants 397
3 State Space 400
4 Evaluation of the Polynomials 409
5 Proof of the Theorem 413
6 Commutative Equivalence 419
7 Complete Reducibility 423
8 Exercises 433
9 Notes 437
References 439
Index 444