This a book on many aspects of algebraic methods of
generating pseudo-random sequences, focusing on properties that
may be useful in communications, especially cryptography and CDMA.
Here is the
Publisher's website.
Here is
Amazon's website.
Chapter 1: Introduction
1.1 Pseudorandom sequences
1.2 LFSR sequences
1.3 FCSR sequences
1.4 Register synthesis
1.5 Applications of pseudorandom sequences
Part I Algebraically Defined Sequences
Chapter 2: Sequences
2.1 Sequences and period
2.2 Fibonacci numbers
2.3 Distinct sequences
2.4 Sequence generators and models
2.5 Exercises
Chapter 3: Linear Feedback Shift Registers and
Linear Recurrences
3.1
Definitions
3.2 Matrix description
3.3 Initial loading
3.4 Power series
3.5 Generating functions
3.6 When the connection
polynomial factors
3.7 Algebraic Models and the ring
R[x]/(q)
3.8 Families of recurring
sequences and ideals
3.9 Examples
3.10 Exercises
Chapter 4: Feedback with Carry Shift Registers and
Multiply with Carry Sequences
4.1 Definitions
4.2 N-Adic numbers
4.3 Analysis of FCSRs
4.4 Initial Loading
4.5 Representation of FCSR
Sequences
4.6 Example
4.7 Memory Requirements
4.8 Random Number generation
using MWC
4.9 Exercises
Chapter 5 Algebraic Feedback Shift Registerss
5.1 Definitions
5.2 pi-Adic numbers
5.3 Properties of AFSRs
5.4 Memory Requirements
5.5 Periodicity
5.6 Exponential Representation
and Period of AFSR Sequences
5.7 Examples
5.8 Exercises
Chapter 6: d-FCSRs
6.1 Binary d-FCSRs
6.2 General d-FCSRs
6.3 Relation Between the Norm and
the Period
6.4 Periodicity
6.5 Elementary description of
d-FCSR sequences
6.6 An Example
6.7 Exercises
Chapter 7: Galois mode and related circuits
7.1 Galois mode LFSRs
7.2 Division by q(x) in R[[x]]
7.3 Galois mode FCSRs
7.4 Division by q in the N-adic
numbers
7.5 Galois mode d-FCSRs
7.6 Linear register
7.7 Exercises
Part II Pseudo-Random and Pseudo-Noise Sequences
Chapter 8: Measures of pseudorandomness
8.1 Why pseudo-random?
8.2 Sequences based on an
arbitrary alphabet
8.3
Correlations
8.4 Exercises
Chapter 9: Shift and add sequences
9.1 Basic properties
9.2 Characterization of shift
and add sequences
9.3 Examples of shift and add sequences
9.4 Further properties of shift
and add sequences
9.5 Proof of Theorem 9.4.1
9.6 Arithmetic Shift and Add
Sequences
12.7 Exercises
Chapter 10: m-Sequences
10.1 Basic properties of
m-sequences
10.2 Decimations
10.3 Interleaved structure
10.4 Pseudo-noise arrays
10.5 Fourier transforms and
m-sequences
10.6 Cross-correlation of an
m-sequence and its decimation
10.7 The Diaconis mind-reader
10.8 Exercises
Chapter 11: Related Sequences and their Correlations
11.1 Welch bound
11.2 Families derived from a
decimation
11.3 Gold sequences
11.4 Kasami sequences, small set
11.5 Geometric sequences
11.6 GMW sequences
11.7 d-form sequences
11.8 Legendre and Dirichlet
sequences
11.9 Frequency hopping sequences
11.10 Optical orthogonal codes
11.11 Maximal sequences over a
finite local ring
11.12 Exercises
Chapter 12: Maximal Period Function Field Sequences
12.1 The Rational function field
AFSR
12.2 Global function
fields
12.3 Exercises
Chapter 13: Maximal Period FCSRs
13.1 l-Sequences
13.2 Distributional properties of
l-sequences
13.3 Arithmetic correlations
13.4 Tables
13.5 Exercises
Chapter 14: Maximal Period d-FCSRs
14.1 Identifying maximal length sequences
14.2 Distribution properties of
d-l-Sequences
14.3 Exercises
Part III Register Synthesis and Security Measures
Chapter 15: Register Synthesis and LFSR Synthesis
15.1 Sequence generators and the
register synthesis problem
15.2 LFSRs and the
Berlekamp-Massey algorithm
15.3 Blahut’s theorem
15.4 The Gunther-Blahut theorem
15.5 Generating sequences with
large linear span
15.6
Exercises
Chapter 16: FCSR Synthesis
16.1 N-adic span and complexity
16.2 Symmetric N-adic span
16.3 Rational approximation
16.4 Exercises
Chapter 17: AFSR Synthesis
17.1 Xu’s rational approximation
algorithm
17.2 Rational approximation in Z
17.3 Proof of correctness
17.4 Rational approximation in
function fields
17.5 Rational approximation in
ramified extensions
17.6 Rational approximation in
quadratic extensions
17.7 Rational approximation by
interleaving
17.8 Rational function fields:
pi-adic vs. linear span
17.9 Exercises
Chapter 18: Average and Asymptotic Behavior of
Security Measures
18.1 Average behavior of linear
complexity
18.2 Average behavior of N-adic
complexity
18.3 Asymptotic behavior of
security measures
18.4 Asymptotic linear complexity
18.5 Asymptotic N-adic complexity
18.6 Consequences and questions
18.7 Exercises
Part IV: Algebraic Background
Chapter A: Abstract Algebra
A.1 Group Theory
A.2 Rings
A.3 Polynomials
Chapter B: Fields
B.1 Field extensions
B.2 Finite Fields
B.3 Quadratic forms over a finite field
B.4 Algebraic Number Fields
B.5 Local and global fields
Chapter C: Finite Rings and Galois Rings
C.1 Finite Local Rings
C.2 Examples
C.3 Divisibility in R[x]
C.4 Tools for Local Rings
C.5 Galois rings
Chapter D: Algebraic Realizations of Sequences
D.1 Alternate representations of pi-adic numbers
D.2 Continued fractions
D.3 Exercises;