Jetzek Galois Fields, Linear Feedback Shift Registers and their Applications

1. Auflage 2018
ISBN: 978-3-446-45613-6
Verlag: Carl Hanser
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 224 Seiten

Focus on Applications
This book gives an excellent introduction to finite groups and fields as well as their applications.
Readers learn to understand and use galois fields and their relationship with linear feedback shift registers. The book has a strong focus on the technical application of galois fields, such as navigation systems and cryptography.
Includes: Finite Groups and Fields; Working with Galois Fields; Linear Feedback Shift Registers (LFSR); Auto- and Crossrelation Functions; Applications: Navigation Systems, Cryptographical Applications, Channel Coding, Mobile Communication Systems

Autoren/Hrsg.

Jetzek, Ulrich

Fachgebiete

• Mathematik | Informatik Mathematik Algebra Algebraische Strukturen, Gruppentheorie

Inhaltsverzeichnis

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