Shift Register Sequences

Preface VII
Acknowledgments XI
Contents XIII
PART I. PERSPECTIVE 1
    1. The Present Status of the Shift Register Art 2
        1. Introduction 2
        2. Areas of Application 2
        3. Advantages of Shift Registers 4
    2. The Shift Register as a Finite State Machine 7
        1. Finite State Machines 7
        2. Shift Registers 12
        3. Generalized Shift Registers 19
PART II. THE LINEAR THEORY 23
    3. Sequences With Randomness Properties 24
        1. Introduction 24
        2. Shift Register Sequences 27
        3. Polynomials Modulo 2 37
        4. Randomness Properties of Shift Register Sequences 43
        5. Cyclotomic Polynomials 48
        6. Computational Techniques 59
    4. Structural Properties of PN Sequences 75
        1. Introduction 75
        2. Multipliers of PN Sequences 76
        3. The Cyclotomic Cosets 77
        4. Decimation of Sequences 78
        5. The Superposition of Cosets 79
        6. Regularities in the Cross-Correlation of PN Sequences 82
        7. The Fourier Analysis of PN Sequences 85
        8. Perfect Sequences 88
    5. On the Factorization of Trinomials Over GF(2) 90
        1. Introduction 90
        2. Theoretical Discussion 90
        3. Procedure 91
        4. Compendium of Special Results 92
        5. Unsolved Problems 96
PART III. THE NONLINEAR THEORY 109
    6. Nonlinear Shift Register Sequences 110
        1. Introduction 110
        2. Mathematical Treatment 111
        3. Experimental Results 141
        4. Tabulation of Experimental Data 147
    7. Cycles from Nonlinear Shift Registers 169
        1. Introduction 169
        2. The Deterministic Approach 169
        3. The Statistical Approach 175
        4. Alternative Approaches to the Distribution of the Longest Cycle 189
        5. Shift Register Cycles of All Lengths 192
        6. The Experimental Approach 194
        7. Tables of Complete Decompositions Into Cycles 196
    8. On the Classification of Boolean Functions 212
        1. Introduction 212
        2. The Zero- and First-Order Invariants 213
        3. The Higher-Order Invariants 215
        4. Canonical Forms 216
        5. The Rademacher-Walsh Expansion Coefficients 217
        6. Practical Methods of Computing the Invariants 219
        7. Application to Finding Asymmetrical Logical Functions 221
        8. Related Results and Problems 221
References 223