Galois Fields, Linear Feedback Shift Registers and their Applications (eBook)

Ulrich Jetzek is a Professor at Kiel University of Applied Sciences.

Contents 10
1 Introduction 14
2 Finite Groups and Fields 18
2.1 Modular Arithmetic 19
2.2 Groups, Rings and Fields 21
2.3 Galois Fields 24
2.3.1 Prime Fields 26
2.3.1.1 Existence of Prime Fields 26
2.3.1.2 Generators of Prime Fields 28
2.3.1.3 Multiplicative Inverses in Prime Fields 29
2.3.1.4 Cyclic Structure of Prime Fields 30
2.3.2 Extension Fields 32
2.3.2.1 Existence of Extension Fields 33
2.3.2.2 Irreducible Polynomials 34
2.3.2.3 Modular Arithmetic over Polynomials 37
2.3.2.4 Primitive or Generator Polynomials 38
2.4 Lessons learned 42
2.5 Exercises 44
3 Working with Extension Fields 46
3.1 Primitive Polynomial Representations 46
3.2 Addition over Extension Fields 48
3.3 Multiplication over Extension Fields 50
3.3.1 Multiplication in polynomial form 50
3.3.2 Multiplication by means of string representation 51
3.3.3 Multiplication using the primitive polynomial 52
3.4 Multiplicative Inverse within Extension Fields 53
3.5 Lessons learned 55
3.6 Exercises 56
4 Linear Feedback Shift Registers 60
4.1 Ring Counters 61
4.2 Johnson Counters 62
4.3 Design of Linear Feedback Shift Registers Based on Galois Field Theory 64
4.3.1 Design of linear feedback shift register circuits based on primitive polynomials 65
4.3.2 LFSRs based on irreducible (non-primitive) polynomials 68
4.3.3 LFSRs based on reducible polynomials 71
4.4 Further topics related to linear feedback shift registers 73
4.4.1 Checking if a specific polynomial is primitive, irreducible or reducible 73
4.4.2 A systematic way of how to determine primitive polynomials 77
4.5 Lessons Learned 79
4.6 Exercises 80
5 Correlation Functions and Pseudo-random Sequences 82
5.1 Correlation Functions 85
5.2 Maximum Length Sequences (m-Sequences) 90
5.3 ‘Real’ random sequences and their properties 92
5.4 Properties of m-Sequences 93
5.5 Lessons learned 94
5.6 Exercises 95
6 Applications of Galois Fields and Linear Feedback Shift Registers 98
6.1 LFSRs within the Global Positioning System (GPS) 98
6.1.1 The Positioning Principle of GPS 99
6.1.2 GPS codes 100
6.1.3 C/A-code generation within the Global Positioning System (GPS) 101
6.1.4 P-code Generation within the Global Positioning System 106
6.2 Data Transmission in GPS 111
6.2.1 The spreading principle 113
6.3 LFSRs in GALILEO 120
6.3.1 Motivation behind GALILEO 120
6.3.2 History of GALILEO 122
6.3.3 GALILEO Services 123
6.3.4 GALILEO and GPS comparison 126
6.3.5 GALILEO open-service (OS) system codes 126
6.4 LFSR Applications in Cryptography 133
6.4.1 A5/1 – a stream cipher used in GSM 138
6.4.2 Trivium 141
6.5 Cyclic Redundancy Checks (CRC) Using LFSRs 142
6.5.1 The core idea of CRC 142
6.5.2 The mathematical description of CRC 143
6.5.3 Implementation aspects of CRC 149
6.5.4 Optimizing CRC-calculation 152
6.6 Lessons learned 156
6.7 Exercises 158
7 Appendix 160
7.1 Problem Solutions 160
7.1.1 Solutions to problems in Chapter 2 160
7.1.2 Solutions to problems in Chapter 3 162
7.1.3 Solutions to problems in Chapter 4 166
7.1.4 Solutions to problems in Chapter 5 170
7.1.5 Solutions to problems in Chapter 6 172
7.2 List of primitive and irreducible polynomials 172
Index 180