Copyrights to these papers may be held by the publishers. The download files are preprints. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Markus Püschel and José M. F. Moura (IEEE Transactions on Signal Processing, Vol. 56, No. 8, pp. 3572-3585, 2008)
Algebraic Signal Processing Theory: Foundation and 1-D Time
Preprint (274 KB)
Published paper (link to publisher)
This paper introduces a general and axiomatic approach to linear signal processing (SP) that we refer to as the algebraic signal processing theory (ASP). Basic to ASP is the linear signal model defined as a triple (A, M, Phi) where familiar concepts like the filter space and the signal space are cast as an algebra A and a module M, respectively. The mapping Phi generalizes the concept of z-transform to bijective linear mappings from a vector space of signal samples into the module~$\md$. Common concepts like filtering, spectrum, or Fourier transform have their equivalent counterparts in ASP. Once these concepts and their properties are defined and understood in the context of ASP, they remain true and apply to specific instantiations of the ASP signal model. For example, to develop signal processing theories for infinite and finite discrete time signals, for infinite or finite discrete space signals, or for multidimensional signals, we need only to instantiate the ASP signal model to a signal model that makes sense for that specific class of signals. Filtering, spectrum, Fourier transform, and other notions follow then from the corresponding ASP concepts. Similarly, common assumptions in SP translate into requirements on the ASP signal model. For example, shift-invariance is equivalent to A being commutative. For finite (duration) signals shift invariance then restricts A to polynomial algebras. We explain how to design signal models from the specification of a special filter, the shift. The paper illustrates the general ASP theory with the standard time shift, presenting a unique signal model for infinite time and several signal models for finite time. The latter models illustrate the role played by boundary conditions and recover the discrete Fourier transform~(DFT) and its variants as associated Fourier transforms. Finally, ASP provides a systematic methodology to derive fast algorithms for linear transforms. This topic and the application of ASP to space dependent signals and to multidimensional signals are pursued in companion papers.Keywords: Algebraic signal processing theory: Current status, Discrete Fourier transform