Fourier analysis on finite groups, applications in signal processing and system design

Radomir S. Stankovic, Claudio Moraga, Jaakko Astola9780471694632, 9780471745426, 0471694630

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.

---

Table of contents :
Cover……Page 1
Press……Page 2
Title page……Page 3
Date-line……Page 4
Preface……Page 5
Acknowledgments……Page 7
Contents……Page 9
List of Figures……Page 13
List of Tables……Page 19
Acronyms……Page 23
1.1 Systems……Page 25
1.2 Signals……Page 26
1.3 Mathematical Models of Signals……Page 27
References……Page 30
2 Fourier Analysis……Page 35
2.1 Representations of Groups……Page 36
2.1.1 Complete reducibility……Page 37
2.2 Fourier Transform on Finite Groups……Page 42
2.3 Properties of the Fourier transform……Page 47
2.4 Matrix interpretation of the Fourier transform on finite non-Abelian groups……Page 50
2.5 Fast Fourier transform on finite non-Abelian groups……Page 52
References……Page 59
3 Matrix Interpretation of the FFT……Page 61
3.1 Matrix interpretation of FFT on finite non-Abelian groups……Page 62
3.2 Illustrative examples……Page 65
3.3 Complexity of the FFT……Page 83
3.3.1 Complexity of calculations of the FFT……Page 86
3.4.1 Decision diagrams……Page 90
3.4.2 FFT on finite non-Abelian groups through DDs……Page 92
3.4.4 Complexity of DDs calculation methods……Page 100
References……Page 104
4 Optimization of Decision Diagrams……Page 109
4.1 Reduction Possibilities in Decision Diagrams……Page 110
4.2 Group-theoretic Interpretation of DD……Page 117
4.3.1 Fourier decision trees……Page 120
4.3.2 Fourier decision diagrams……Page 131
4.4 Discussion of Different Decompositions……Page 132
4.5 Representation of Two-Variable Function Generator……Page 134
4.6 Representation of adders by Fourier DD……Page 138
4.7 Representation of multipliers by Fourier DD……Page 141
4.8 Complexity of FN ADD……Page 147
4.9.1 Matrix-valued functions……Page 153
4.9.2 Fourier transform for matrix-valued functions……Page 154
4.10 Fourier Decision Trees with Preprocessing……Page 159
4.11 Fourier Decision Diagrams with Preprocessing……Page 160
4.12 Construction of FNAPDD……Page 161
4.13 Algorithm for Construction of FNAPDD……Page 175
4.13.1 Algorithm for representation……Page 176
4.14 Optimization of FNAPDD……Page 177
References……Page 178
5 Functional Expressions on Quaternion Groups……Page 181
5.2 Fourier Expressions on $Q_2$……Page 182
5.3 Arithmetic Expressions……Page 184
5.4 Arithmetic expressions from Walsh expansions……Page 185
5.5 Arithmetic expressions on $Q_2$……Page 187
5.5.2 Arithmetic-Haar expressions and Kronecker expressions……Page 190
5.6 Different Polarity Polynomial Expressions……Page 191
5.6.1 Fixed-polarity Fourier expansions in $C(Q_2)$……Page 192
5.6.2 Fixed-polarity arithmetic-Haar expressions……Page 193
5.7.1 FFT-like algorithm……Page 196
5.7.2 Calculation of arithmetic-Haar coefficients through decision diagrams……Page 198
References……Page 204
6 Gibbs Derivatives on Finite Groups……Page 207
6.1 Definition and properties of Gibbs derivatives on finite non-Abelian groups……Page 208
6.2 Gibbs anti-derivative……Page 210
6.3 Partial Gibbs derivatives……Page 211
6.4 Gibbs differential equations……Page 213
6.5 Matrix interpretation of Gibbs derivatives……Page 214
6.6 Fast algorithms for calculation of Gibbs derivatives on finite groups……Page 216
6.6.1 Complexity of Calculation of Gibbs Derivatives……Page 222
6.7 Calculation of Gibbs derivatives through DDs……Page 225
6.7.1 Calculation of partial Gibbs derivatives……Page 227
References……Page 231
7.1 Linear shift-invariant systems on groups……Page 235
7.2 Linear shift-invariant systems on finite non-Abelian groups……Page 237
7.3 Gibbs derivatives and linear systems……Page 238
7.3.1 Discussion……Page 239
References……Page 241
8 Hilbert Transform on Finite Groups……Page 245
8.1 Some results of Fourier analysis on finite non-Abelian groups……Page 247
8.2 Hilbert transform on finite non-Abelian groups……Page 251
8.3 Hilbert transform infinite fields……Page 255
References……Page 258
Index……Page 259