The Momentary Fourier Transformation Derived from Recursive Matrix Transformations

Sandor Albrecht, Ian Cumming and József Dúdás

Dept. of Electrical and Computer Engineering

The University of British Columbia

Vancouver, BC, Canada V6T 1Z4.

sandora@ee.ubc.ca ianc@ee.ubc.ca

Presented at the 13th International Conference on Digital Signal Processing, Santorini, Greece, July 2-4, 1997. Published on pages 337-340 of the proceedings.

ABSTRACT

The momentary Fourier transform (MFT) computes the DFT of a discrete-time sequence for every new sample of the sequence. It has an efficient recursive form, and an alternate derivation is given using matrix transformations. Recursive and non-recursive forms of the inverse MFT are also given, which can provide efficient frequency domain filtering.

2. Momentary matrix transformation

3. Momentary Fourier Transform

The momentary or moving Fourier transform (MFT) is a method of computing the discrete Fourier transform (DFT) of a sequence in incremental steps. It can be computed using an efficient recursive formula, and it is useful in cases where the detailed evolution of the spectra of a time series is wanted, and in cases where only a few Fourier coefficients are needed.

Uses of the incremental DFT were introduced by Papoulis in 1977 [1], and by Bitmead and Anderson in 1981 [2]. A detailed derivation of the momentary Fourier transform was given by Dudás in 1986 [3]. In 1991, Lilly gives a similar derivation, using the term "moving Fourier transform", and uses the MFT for updating the model of a time-varying system [4].

In this paper, we introduce the matrix form of the momentary transform in Section 2, and show that it has a recursive form. In Section 3, we show that when the momentary matrix transform takes the form of the discrete Fourier transform, the resulting MFT has an efficient (recursive) computational structure. In Section 4, the inverse MFT is derived for the first time. An example of the use of the MFT and a discussion of its computational efficiency is given in Section 5.

1.

Let *x _{i}* be a sample of an arbitrary discrete-time
function of one variable. The function will be analyzed through an

Figure 1: The sampled function *x _{i}*

At times *i*-1 and *i*, the windowed samples can be
represented by the column vectors:

,

Let **T** be an *N*´*N*
non-singular transformation matrix, which has the inverse
**T**^{-1}. The sequence of windowed vectors can be
transformed by **T**:

**y**_{i-1} = **Tx**_{i-1} , **y**_{i} = **Tx**_{i} , . . .

Let **P** be an N´ N elementary
cyclic permutational matrix:

When the vector **x*** _{i-1}* is premultiplying by

Then the **x*** _{i}* vector can be expressed by the
shifted

The transformation **TP** will be called the momentary matrix
transform (MMT) because it represents the matrix transform **T**
shifted one moment (*i.e. *one sample) in time.

2.1 The Recursive Form of the MMT

Substituting (6) into the transformation associated with the
*i*^{th} window in (2), the following relationships are
obtained:

where use is made of the inverse transform
**x*** _{i-1}* =

Equation (8) expresses the recursivity of the momentary matrix
transforms, since calculation of the newly transformed index vector
**y*** _{i}* needs the previously transformed index
vector

An interesting case is when the matrix transform **T** performs
the Discrete Fourier Transform (DFT). When

*W ^{k} = e^{-j2 p k/N} , *

are the N complex roots of unity (the DFT twiddle factors), the DFT can be written as the matrix transform:

and the inverse DFT is implemented by the matrix transform:

It can be shown that the similarity transform has the desired diagonal form:

so that the momentary Fourier transform (MFT) has the efficient recursive form:

To get (13), note that , which means that:

It can be shown that the DFT is the only matrix transformation which possesses the diagonal form (12).

The *N*-element vector **y**_{i} contains the Fourier
coefficients of the *N*-point sequence **x**_{i} ending
at time *i*. Note that while the vectors **x*** _{i-1
}*and

Note also that in the incremental form (13), each spectral component
**y*** _{i,k}* at time

so that the recursive formula is particularly efficient if only a few frequency components need to be computed, as in the zoom transform.

Thus we see that if the DFT of the sequence
[*x _{i-N}…x_{i-1}*] has been computed, the DFT
of the sequence [

The matrix transformation equations lead to an efficient recursive implementation of the inverse momentary Fourier transform as well. Starting with the matrix form of the inverse DFT:

note that for a recursive
calculation, only the last element of **x*** _{i}* need
be calculated at the current time. This involves only the last row of
the matrix

and the obvious recursion exists:

This recursion requires *N* complex multiplies and *N*+1
complex adds for each new output point.

Note also that in the non-recursive form (16), the oldest element of
**x*** _{i}*, can be computed using adds only:

from which the
sequence **x*** _{i}* can be computed from the
2-dimensional "sequence"

To illustrate the usage of the incremental
form of the MFT, a complex exponential of length 3*N* samples is
used. Using an analysis record length of *N* = 30, and a frequency
of 20 cycles/record, the magnitude of the evolving spectrum is shown in
Figure 2, when the MFT is
incremented by one sample at each analysis stage.

Figure 2: Illustration of MFT usage

The MFT begins with the initial
conditions of **y**_{0} = 0. This is equivalent to having
*N* zeros precede the data vector. In Figure 2, note how the energy
in the spectrum rises from zero to a maximum in the first *N*
samples. Also note how spectral leakage is observed in the first
*N*-1 time samples, because the complex exponential does not have
an integer number of cycles/record over this time. After time
*N*-1, there is an integer number of cycles/record, so all the
energy in the spectrum lies in one bin. For the last *N*-1 samples
in Figure 2, leakage occurs again, and the spectral energy decays to
zero.

In Figure 3, an example of speech analysis is given. An 72-point DFT is used, and the MFTs are spaced by 14 samples. The speech is a 0.275 s record of the word "pipe".

Figure 3: Speech analysis using the MFT

Consider the case where *N*-point DFTs are used to analyze an
*N*_{u}-point complex-valued data record. If the input data
is shifted by *q* samples between each DFT application, where , then DFTs are needed to
spectrum analyze the record. It is assumed that the coefficients are
precomputed and stored.

Then, when radix-2 FFTs are used to analyze the data,

real operations

are needed. It can be shown that in the case of the MFT, the number of real operations needed are:

where *N*_{1} is the number of DFT coefficients that are
to be computed, .

Figure 4: Comparison of MFT and FFT arithmetic.

This computing load is illustrated in Figure 4, for the case of
*N*_{u} = 1024, *N* = 64, and *N*_{1} = 4
& 64. The FFT is quite efficient if the shift increment *q*
> *N */ 4, but is very inefficient if the shift between FFTs is
only a few samples. In contrast, the MFT is very efficient compared to
the FFT if the shift between samples is small, but its relative
efficiency drops as the shift *q* increases. The efficiencies of
the FFT and the full MFT are approximately the same when
*q* = 4. However, if only a few DFT coefficients are needed
(*e.g. N*_{1} = 4), the reduced MFT is very efficient, even
for large values of shift between DFTs. Similar conclusions are reached
with different values of *N* and *N*_{u}. Note also
that:

- The MFT efficiency curves of
Figure 4 are flat because
the operations are proportional to
*q*. This means that the DFT of every sample shift can be computed with no further overhead, if desired. - The MFT does not rely upon
*N*being a power of two to obtain its efficiency. - When the input data is real-valued, the comparison of efficiencies is similar, as long as steps are taken to eliminate the unnecessary operations in each case.
- Weighting or window functions can be included in the MFT application, although not as simply as in the case of the FFT [5].

As a second example of efficiency, consider an *N*-point
frequency domain filter applied with a fast convolution. The filter is
applied with a forward FFT (or MFT), an array multiply, then an inverse
FFT (or MFT). The comparison of efficiencies is shown in Figure 5. If the full MFT is used to compute all
the DFT coefficients, then the FFT is more efficient. But if only a
subset of the DFT coefficients need be computed, the MFT/IMFT option can
be more efficient for many values of *N*.

Figure 5: Efficiency comparison in fast convolution

The momentary or moving Fourier transform has been derived using a matrix formulation of the DFT, and an incremental form has also been given. The incremental or recursive form is particularly efficient when successive DFTs with a high overlap ratio is to be computed, or when only a few DFT coefficients are needed. Recursive and non-recursive inverse MFTs have also been derived, including a non-recursive form which requires only additions to obtain the time sequence.

The authors would like to thank Dr. József Dúdás for introducing them to the momentary Fourier transform. Financial support from the NSERC/MDA Industrial Research Chair in Radar Remote Sensing is gratefully acknowledged.

[1] A. Papoulis, *Signal Analysis*. McGraw-Hill, 1977

[2] R. R. Bitmead and C. D. O. Anderson, "Adaptive frequenct sampling filters," *IEEE Trans. On Circuits and Systems*, vol. CAS-28, pp. 524-534, June 1981.

[3] J. Dúdás, *The Momentary Fourier Transform.* PhD thesis, Technical University of Budapest, 1986.

[4] J. H. Lilly, "Efficient DFT-based model reduction for continuous systems," *IEEE Trans. On Automatic Control, *vol. 36, pp. 1188-1193, Oct. 1991

[5] B. G. Sherlock and D. M. Monro, "Moving discrete Fourier transform," *IEE Proceedings-F, *vol. 139, pp. 279-282, Aug. 1992.

Last updated: 27^{th} March 1998 by Ian Cumming.