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.

Texte du rabat

The primary purpose of this monograph is to explore the ties between digital signal processing and error-control codes, with the thought of eventually making them two components of a unified theory, or of making a large part of the theory of error-control codes a subset of digital signal processing. By studying the properties of the Fourier transform in an arbitrary field, a perspective emerges in which the two subjects are unified. Because there are many fields and many Fourier transforms in most of these fields, the unified view will also uncover a rich set of mathematical tools, many of which have yet to find an engineering application. The author has published several well-known books, and is widely respected. The topics covered in this book are very important in Electrical Engineering, especially Signal Processing, and Applied Mathematics.

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.4 Rings and Groups.- 2.5 Algebraic Integers.- 3 Sequences and Spectra.- 3.1 Weight and Complexity.- 3.2 The Fourier Transform.- 3.3 Examples of Fourier Transforms.- 3.4 Properties of the Fourier Transform.- 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.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.2 Erasures and Errors Decoding.- 8.3 Time Domain Decoder Algorithms.- 8.4 A Universal Decoder Architecture.- References.