Fourier Analysis On Finite Groups with Applications in Signal Processing And System Design

by Stankovic, Radomir S.; Moraga, Claudio; Astola, Jaakko

• ISBN13: 9780471694632
• ISBN10: 0471694630
• Edition: 1st
• Format: Hardcover
• Copyright: 2005-07-07
• Publisher: Wiley-IEEE Press

Summary

Discover applications of Fourier analysis on finite non-Abelian groups The majority of publications in spectral techniques consider Fourier transform on Abelian groups. However, non-Abelian groups provide notable advantages in efficient implementations of spectral methods. Fourier Analysis on Finite Groups with Applications in Signal Processing and System Design examines aspects of Fourier analysis on finite non-Abelian groups and discusses different methods used to determine compact representations for discrete functions providing for their efficient realizations and related applications. Switching functions are included as an example of discrete functions in engineering practice. Additionally, consideration is given to the polynomial expressions and decision diagrams defined in terms of Fourier transform on finite non-Abelian groups. A solid foundation of this complex topic is provided by beginning with a review of signals and their mathematical models and Fourier analysis. Next, the book examines recent achievements and discoveries in: Matrix interpretation of the fast Fourier transform Optimization of decision diagrams Functional expressions on quaternion groups Gibbs derivatives on finite groups Linear systems on finite non-Abelian groups Hilbert transform on finite groups Among the highlights is an in-depth coverage of applications of abstract harmonic analysis on finite non-Abelian groups in compact representations of discrete functions and related tasks in signal processing and system design, including logic design. All chapters are self-contained, each with a list of references to facilitate the development of specialized courses or self-study. With nearly 100 illustrative figures and fifty tables, this is an excellent textbook for graduate-level students and researchers in signal processing, logic design, and system theory-as well as the more general topics of computer science and applied mathematics.

Author Biography

RADOMIR S. STANKOVIC, PhD, is Professor, Department of Computer Science, Faculty of Electronics, University of Nis, Serbia.

CLAUDIO MORAGA, PhD, is Professor, Department of Computer Science, Dortmund University, Germany.

JAAKKO T. ASTOLA, PhD, is Professor, Institute of Signal Processing, Tampere University of Technology, Finland.

Table of Contents

Preface	v
Acknowledgments	vii
Acronyms	xxiii
Signals and Their Mathematical Models	1	(10)
Systems	1	(1)
Signals	2	(1)
Mathematical Models of Signals	3	(8)
References	6	(5)
Fourier Analysis	11	(26)
Representations of Groups	12	(6)
Complete reducibility	13	(5)
Fourier Transform on Finite Groups	18	(5)
Properties of the Fourier transform	23	(3)
Matrix interpretation of the Fourier transform on finite non-Abelian groups	26	(2)
Fast Fourier transform on finite non-Abelian groups	28	(9)
References	35	(2)
Matrix Interpretation of the FFT	37	(48)
Matrix interpretation of FFT on finite non-Abelian groups	38	(3)
Illustrative examples	41	(18)
Complexity of the FFT	59	(7)
Complexity of calculations of the FFT	62	(4)
Remarks on programming implementation of FFT	66	(1)
FFT through decision diagrams	66	(19)
Decision diagrams	66	(2)
FFT on finite non-Abelian groups through DDs	68	(8)
MTDDs for the Fourier spectrum	76	(1)
Complexity of DDs calculation methods	76	(4)
References	80	(5)
Optimization of Decision Diagrams	85	(72)
Reduction Possibilities in Decision Diagrams	86	(7)
Group-theoretic Interpretation of DD	93	(3)
Fourier Decision Diagrams	96	(12)
Fourier decision trees	96	(11)
Fourier decision diagrams	107	(1)
Discussion of Different Decompositions	108	(2)
Algorithm for optimization of DDs	110	(1)
Representation of Two-Variable Function Generator	110	(4)
Representation of adders by Fourier DD	114	(3)
Representation of multipliers by Fourier DD	117	(6)
Complexity of FNADD	123	(6)
Fourier DDs with Preprocessing	129	(6)
Matrix-valued functions	129	(1)
Fourier transform for matrix-valued functions	130	(5)
Fourier Decision Trees with Preprocessing	135	(1)
Fourier Decision Diagrams with Preprocessing	136	(1)
Construction of FNAPDD	137	(14)
Algorithm for Construction of FNAPDD	151	(2)
Algorithm for representation	152	(1)
Optimization of FNAPDD	153	(4)
References	154	(3)
Functional Expressions on Quaternion Groups	157	(26)
Fourier expressions on finite dyadic groups	158	(1)
Finite dyadic groups	158	(1)
Fourier Expressions on Q2	158	(2)
Arithmetic Expressions	160	(1)
Arithmetic expressions from Walsh expansions	161	(2)
Arithmetic expressions on Q2	163	(4)
Arithmetic expressions and arithmetic-Haar expressions	166	(1)
Arithmetic-Haar expressions and Kronecker expressions	166	(1)
Different Polarity Polynomial Expressions	167	(5)
Fixed-polarity Fourier expansions in C(Q2)	168	(1)
Fixed-polarity arithmetic-Haar expressions	169	(3)
Calculation of the arithmetic-Haar coefficients	172	(11)
FFT-like algorithm	172	(2)
Calculation of arithmetic-Haar coefficients through decision diagrams	174	(6)
References	180	(3)
Gibbs Derivatives on Finite Groups	183	(28)
Definition and properties of Gibbs derivatives on finite non-Abelian groups	184	(2)
Gibbs anti-derivative	186	(1)
Partial Gibbs derivatives	187	(2)
Gibbs differential equations	189	(1)
Matrix interpretation of Gibbs derivatives	190	(2)
Fast algorithms for calculation of Gibbs derivatives on finite groups	192	(9)
Complexity of Calculation of Gibbs Derivatives	198	(3)
Calculation of Gibbs derivatives through DDs	201	(10)
Calculation of partial Gibbs derivatives	203	(4)
References	207	(4)
Linear Systems on Finite Non-Abelian Groups	211	(10)
Linear shift-invariant systems on groups	211	(2)
Linear shift-invariant systems on finite non-Abelian groups	213	(1)
Gibbs derivatives and linear systems	214	(7)
Discussion	215	(2)
References	217	(4)
Hilbert Transform on Finite Groups	221	(14)
Some results of Fourier analysis on finite non-Abelian groups	223	(4)
Hilbert transform on finite non-Abelian groups	227	(4)
Hilbert transform in finite fields	231	(4)
References	234	(1)
Index	235