Digital Signal Processing Algorithms : Number Theory, Convolution, Fast Fourier Transforms, and Applications

Introduction Outline The Organization PART I: Computational Number Theory Computational Number Theory Groups, Rings, and Fields Elements of Number Theory Integer Rings and Fields Chinese Remainder Theorem for Integers Number Theory for Finite Integer Rings Polynomial Algebra Algebra of Polynomials over a Field Roots of a Polynomial Polynomial Fields and Rings The Chinese Remainder Theorem for Polynomials CRT-P in Matrix Form Lagrange Interpolation Polynomial Algebra over GF(p) Order of an Element Theoretical Aspects of Discrete Fourier Transform and Convolution The Discrete Fourier Transform Basic Formulation of Convolution Bounds on the Multiplicative Complexity Basic Formulation of Convolution Algorithms Matrix Exchange Property Cyclotomic Polynomial Factorization and Associated Fields Cyclotomic Polynomial Factorization over Complex and Real Numbers Cyclotomic Polynomial Factorization over Rational Numbers Cyclotomic Fields and Cyclotomic Polynomial Factorizations Extension Fields of Cyclotomic Fields and Cyclotomic Polynomial Factorization A Preview of Applications to Digital Signal Processing Cyclotomic Polynomial Factorization in Finite Fields Cyclotomic Polynomial Factorization Factorization of (un - 1) over GF (p) Primitive Polynomials over GF (p) Complex Finite Fields and Cyclotomic Polynomial Factorization Finite Integer Rings: Polynomial Algebra and Cyclotomic Factorization Polynomial Algebra over a Ring Lagrange Interpolation Number Theoretic Transforms Monic Polynomial Factorization Extension of CRT-P over Finite Integer Rings Polynomial Algebra and CRT-PR: The Complex Case Number Theoretic Transforms: The Complex Case Pseudo Number Theoretic Transforms Polynomial Algebra and Direct Sum Properties in Integer Polynomial Rings PART II: Convolution Algorithms Thoughts on Part II Fast Algorithms for Acyclic Convolution CRT-P Based Fast Algorithms for One-Dimensional Acyclic Convolution Casting the Algorithm in Bilinear Formulation Multidimensional Approaches to One-Dimensional Acyclic Convolution Multidimensional Acyclic Convolution Algorithms Nesting and Split Nesting Algorithms for Multidimensional Convolution Acyclic Convolution Algorithms over Finite Fields and Rings Fast One-Dimensional Cyclic Convolution Algorithms Bilinear Forms and Cyclic Convolution Cyclotomic Polynomials and Related Algorithms over Re and C Cyclotomic Polynomials and Related Algorithms over Z Other Considerations Complex Cyclotomic Polynomials and Related Algorithms over CZ The Agarwal-Cooley Algorithm Cyclic Convolution Algorithms over Finite Fields and Rings Two- and Higher Dimensional Cyclic Convolution Algorithms Polynomial Formulation and an Algorithm Improvements and Related Algorithms Discrete Fourier Transform Based Algorithms Algorithms Based on Extension Fields Algorithms for Multidimensional Cyclic Convolution Algorithms for Two-Dimensional Cyclic Convolution in Finite Integer Rings Validity of Fast Algorithms over Different Number Systems Introduction Mathematical Preliminaries Chinese Remainder Theorem over Finite Integer Rings Interrelationships among Algorithms over Different Number Systems Analysis of Two-Dimensional Cyclic Convolution Algorithms Fault Tolerance for Integer Sequences A Framework for Fault Tolerance Mathematical Structure of C over Z(M) Coding Techniques over Z(q) Examples and SFC-DFD Codes PART III: Fast Fourier Transform (FFT) Algorithms Thoughts on Part III Fast Fourier Transform: One-Dimensional Data Sequences The DFT: Definitions and Properties Rader's FFT Algorithm, n=p, p an Odd Prime Rader's FFT Algorithm, n=pc, p an Odd Prime Cooley-Tukey FFT Algorithm, n=a . b FFT Algorithms for n a Power of 2 The Prime Factor FFT n=a . b, (a,b) =1 The Winograd FFT Algorithm Fast Fourier Transform: Multidimensional Data Sequences The Multidimensional DFT: Definition and Properties FFT for n=p, p an Odd Prime Multidimensional FFT Algorithms for n a Power of 2 Matrix Formulation of Multidimensional DFT and Related Algorithms Polynomial Version of Rader's Algorithm Polynomial Transform Based FFT Algorithms PART IV: Recent Results on Algorithms in Finite Integer Rings Thoughts on Part IV Paper One: A Number Theoretic Approach to Fast Algorithms for Two-Dimensional Digital Signal Processing in Finite Integer Rings Paper Two: On Fast Algorithms for One-Dimensional Digital Signal Processing in Finite Integer and Complex Integer Rings Paper Three: Cyclotomic Polynomial Factorization in Finite Integer Rings with Applications to Digital Signal Processing Paper Four: Error Control Techniques for Data Sequences Defined in Finite Integer Rings A. Small Length Acyclic Convolution Algorithms B. Classification of Cyclotomic Polynomials Index

9780849371783

1