7.4: Discussion and Further Reading
- Last updated
-
-
Save as PDF
This chapter only scratches the surface of the connection between algebra and the DFT or signal processing in general. We provide a few references for further reading.
Algebraic Derivation of Transform Algorithms
As mentioned before, the use of polynomial algebras and the CRT underlies much of the early work on FFTs and convolution algorithms. For example, Winograd's work on FFTs minimizes the number of non-rational multiplications. This and his work on complexity theory in general makes heavy use of polynomial algebras (see Chapter Winograd's Short DFT Algorithms for more information and references).
Since \(\mathbb{C}[x]/(s^N-1)=\mathbb{C}[C_N]\) can be viewed a group algebra for the cyclic group, the methods shown in this chapter can be translated into the context of group representation theory. However, Fourier transforms for groups have found only sporadic applications. Along a related line of work, using group theory it is possible that to discover and generate certain algorithms for trigonometric transforms, such as discrete cosine transforms (DCTs), automatically using a computer program.
More recently, the polynomial algebra framework was extended to include most trigonometric transforms used in signal processing, besides the DFT, the discrete cosine and sine transforms and various real DFTs including the discrete Hartley transform. It turns out that the same techniques shown in this chapter can then be applied to derive, explain, and classify most of the known algorithms for these transforms and even obtain a large class of new algorithms including general-radix algorithms for the discrete cosine and sine transforms (DCTs/DSTs).
This latter line of work is part of the algebraic signal processing theory briefly discussed next.
Algebraic Signal Processing Theory
The algebraic properties of transforms used in the above work on algorithm derivation hints at a connection between algebra and (linear) signal processing itself. This is indeed the case and was fully developed in a recent body of work called algebraic signal processing theory (ASP).
ASP first identifies the algebraic structure of (linear) signal processing: the common assumptions on available operations for filters and signals make the set of filters an algebraAA" role="presentation" style="position:relative;" tabindex="0"> \(\mathfrak{A}\) and the set of signals an associated AA" role="presentation" style="position:relative;" tabindex="0">\(\mathfrak{A}\)-module AA" role="presentation" style="position:relative;" tabindex="0">\(\mathfrak{M}\). ASP then builds a signal processing theory formally from the axiomatic definition of a signal model: a triple (A,M,Φ)(A,M,Φ)" role="presentation" style="position:relative;" tabindex="0">\(\mathfrak{A,M,\Phi }\) where \(\mathfrak{\Phi }\) generalizes the idea of the zz" role="presentation" style="position:relative;" tabindex="0">\(z\)-transform to mappings from vector spaces of signal values to AA" role="presentation" style="position:relative;" tabindex="0">\(\mathfrak{M}\). If a signal model is given, other concepts, such as spectrum, Fourier transform, frequency response are automatically defined but take different forms for different models. For example, infinite and finite time as discussed in Table 7.4.1 below, are two examples of signal models. Their complete definition is provided in Table 7.4.1 and identifies the proper notion of a finite zz" role="presentation" style="position:relative;" tabindex="0">MM" role="presentation" style="position:relative;" tabindex="0">\(\mathbb{C}^n\rightarrow \mathbb{C}[s]/(s^n-1)\)
Signal model |
Infinite time |
Finite time |
AA" role="presentation" style="position:relative;" tabindex="0">\[\mathfrak{A} \nonumber \] |
\[\left \{ \sum_{n\in \mathbb{Z}}H(n)s^n\mid (...,H(-1),H(0),H(1),...)\in l^1(\mathbb{Z}) \right \} \nonumber \] |
\[\mathbb{C}[x]/(s^n-1) \nonumber \] |
\[\mathfrak{M} \nonumber \] |
\[\left \{ \sum_{n\in \mathbb{Z}}X(n)s^n\mid (...,X(-1),X(0),X(1),...)\in l^2(\mathbb{Z}) \right \} \nonumber \] |
\[\mathbb{C}[s]/(s^n-1) \nonumber \] |
\[\mathfrak{\Phi} \nonumber \] |
\[\Phi :l^2(\mathbb{Z})\rightarrow \mathfrak{M} \nonumber \] |
\[\Phi :\mathbb{C}^n\rightarrow \mathfrak{M} \nonumber \] |
Table 7.4.1 Infinite and finite time models as defined in ASP
ASP shows that many signal models are in principle possible, each with its own notion of filtering and Fourier transform. Those that support shift-invariance have commutative algebras. Since finite-dimensional commutative algebras are precisely polynomial algebras, their appearance in signal processing is explained. For example, ASP identifies the polynomial algebras underlying the DCTs and DSTs, which hence become Fourier transforms in the ASP sense. The signal models are called finite space models since they support signal processing based on an undirected shift operator, different from the directed time shift. Many more insights are provided by ASP including the need for and choices in choosing boundary conditions, properties of transforms, techniques for deriving new signal models, and the concise derivation of algorithms mentioned before.