Algebraic Methods for Signal Processing and Communications Coding

Algorithms for computation are a central part of both digital signal pro­ cessing and decoders for error-control codes and the central algorithms of the two subjects share many similarities. Each subject makes extensive use of the discrete Fourier transform, of convolutions, and of algorithms for the inversion of Toeplitz systems of equations. Digital signal processing is now an established subject in its own right; it no longer needs to be viewed as a digitized version of analog signal process­ ing. Algebraic structures are becoming more important to its development. Many of the techniques of digital signal processing are valid in any algebraic field, although in most cases at least part of the problem will naturally lie either in the real field or the complex field because that is where the data originate. In other cases the choice of field for computations may be up to the algorithm designer, who usually chooses the real field or the complex field because of familiarity with it or because it is suitable for the particular application. Still, it is appropriate to catalog the many algebraic fields in a way that is accessible to students of digital signal processing, in hopes of stimulating new applications to engineering tasks.

Contenu

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.