Algebraic Shift Register Sequences

Describes the design, mathematical analysis and implementation of pseudo-random sequences for applications in communications, cryptography and simulations.

Mark Goresky (Author), Andrew Klapper (Author)

9781107014992, Cambridge University Press

Hardback, published 2 February 2012

514 pages, 35 b/w illus. 35 tables 90 exercises
25.8 x 17.8 x 3.1 cm, 1.11 kg

"This elegant text casts highly practical mathematics as replete with miraculous theoretical novelties. It thus serves specialists while simultaneously envincing a broad appeal. Recommended."
D.V. Feldman, Choice magazine

Pseudo-random sequences are essential ingredients of every modern digital communication system including cellular telephones, GPS, secure internet transactions and satellite imagery. Each application requires pseudo-random sequences with specific statistical properties. This book describes the design, mathematical analysis and implementation of pseudo-random sequences, particularly those generated by shift registers and related architectures such as feedback-with-carry shift registers. The earlier chapters may be used as a textbook in an advanced undergraduate mathematics course or a graduate electrical engineering course; the more advanced chapters provide a reference work for researchers in the field. Background material from algebra, beginning with elementary group theory, is provided in an appendix.

1. Introduction
Part I. Algebraically Defined Sequences: 2. Sequences
3. Linear feedback shift registers and linear recurrences
4. Feedback with carry shift registers and multiply with carry sequences
5. Algebraic feedback shift registers
6. d-FCSRs
7. Galois mode, linear registers, and related circuits
Part II. Pseudo-Random and Pseudo-Noise Sequences: 8. Measures of pseudo-randomness
9. Shift and add sequences
10. M-sequences
11. Related sequences and their correlations
12. Maximal period function field sequences
13. Maximal period FCSR sequences
14. Maximal period d-FCSR sequences
Part III. Register Synthesis and Security Measures: 15. Register synthesis and LFSR synthesis
16. FCSR synthesis
17. AFSR synthesis
18. Average and asymptotic behavior of security measures
Part IV. Algebraic Background: A. Abstract algebra
B. Fields
C. Finite local rings and Galois rings
D. Algebraic realizations of sequences
Bibliography
Index.

Subject Areas: Signal processing [UYS], Communications engineering / telecommunications [TJK], Algebra [PBF]