Algebraic Methods for Signal Processing and Communications Coding

1 Introduction.- 1.1 Digital Signal Processing.- 1.2 Digital Communications.- 2 Mathematical Fundamentals.- 2.1 Algebraic Fields.- 2.2 Elementary Number Theory.- 2.3 Extension Fields.- 2.3.1 Fields of Characteristic 2.- 2.3.2 Fields That Mimic the Complex Field.- 2.3.3 Fields That Cannot Mimic the Complex Field.- 2.3.4 Fields of Rational Functions.- 2.3.5 Cyclotomic Extensions of the Rational Field.- 2.4 Rings and Groups.- 2.5 Algebraic Integers.- 3 Sequences and Spectra.- 3.1 Weight and Complexity.- 3.1.1 Linear Complexity.- 3.1.2 Cyclic Complexity.- 3.1.3 Linear and Cyclic Complexity.- 3.2 The Fourier Transform.- 3.3 Examples of Fourier Transforms.- 3.4 Properties of the Fourier Transform.- 3.4.1 Cyclic Decimation.- 3.4.2 The Cyclic Complexity Property.- 3.4.3 Conjugacy Constraints.- 3.5 Decimation of Shift Register Sequences.- 3.6 A Universal Eigenvector.- 3.7 Bounds on the Weight of Sequences.- 3.8 The Gleason-Prange Theorem.- 4 Cyclic Codes and Related Codes.- 4.1 Theory of Reed-Solomon Codes.- 4.2 Reed-Solomon Codes in Infinite Fields.- 4.2.1 Reed-Solomon Codes in the Complex Field.- 4.2.2 Reed-Solomon Codes in the Extended Rationals.- 4.3 Reed-Solomon Codes in Finite Fields.- 4.4 Radix-2 Reed-Solomon Codes.- 4.5 Conjugaey Constraints and BCH Codes.- 5 Fast Algorithms for Convolution.- 5.1 Convolution by Blocks.- 5.2 Fast Algorithms for Cyclic Convolution.- 5.3 Convolution of Integer Sequences.- 5.4 Convolutions Using Residue Number Systems.- 5.5 Convolution of Polynomial Sequences.- 6 Solving Toeplitz Systems.- 6.1 The Sugiyama Algorithm.- 6.2 The Berlekamp-Massey Algorithm.- 6.3 Relationships Between Algorithms.- 6.4 The Levinson and Durbin Algorithms.- 7 Fast Algorithms for the Fourier Transform.- 7.1 The Cooley-Tukey FFT.- 7.2 Radix-2 Transforms.- 7.3 The Good-Thomas FFT.- 7.4 FFT Algorithms for Subblocks.- 7.5 FFT Algorithms Using Algebraic Integers.- 7.6 The Winograd FFT.- 8 Decoding of Cyclic Codes.- 8.1 Decoding of Reed-Solomon Codes.- 8.1.1 The Forney Algorithm.- 8.1.2 The Berlekamp Algorithm.- 8.2 Erasures and Errors Decoding.- 8.3 Time Domain Decoder Algorithms.- 8.3.1 A Time Domain Decoder with n2 Steps.- 8.3.2 A Time Domain Decoder with 2tn Steps.- 8.3.3 A Time Domain Decoder with (More Than) 4t2 Steps.- 8.4 A Universal Decoder Architecture.- References.