Pseudo random sequences play a significant role in several technical areas, such as navigation systems or cryptography. Such sequences can easily be generated by linear feedback shift registers (LFSRs). The design of such LFSRs is based on the mathematical theory of finite fields, the so-called Galois fields.
The goal of this book is to build a bridge from the mathematics of Galois fields, in particular extension fields, toward the related circuit theory in terms of linear feedback shift registers and their usage in several technical applications.
This book is structured into the following chapters:
- Galois and extension fields: modular arithmetic, definition of groups, rings and fields, definition and theorems on Galois and extension fields
- Working with extension fields: representations of primitive polynomials, addition and multiplication over extension fields, methods to calculate multiplicative inverses
- Linear feedback shift registers: design of LFSRs based on Galois Field Theory, methods for searching primitive polynomials
- Correlation functions: maximum-length sequences and their auto- and cross-correlation properties
- Applications of LFSRs:
• LFSRs within the global navigation satellite systems (GNSS) GPS and Galileo, the spreading principle used for transmission in GNSS
• LFSRs in cryptography, in particular the GSM stream cipher A5/1 and Trivium
• LFSRs for cyclic redundancy checks
Each chapter contains a lessons-learned section to summarize the most important aspects. Several exercises are also provided to help the reader test and apply the knowledge gained in each chapter. Solutions to these exercises are presented in the last chapter of the book.