Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » Fast Fourier Transforms » The DFT as Convolution or Filtering

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • Rice Digital Scholarship

    This collection is included in aLens by: Digital Scholarship at Rice University

    Click the "Rice Digital Scholarship" link to see all content affiliated with them.

  • NSF Partnership display tagshide tags

    This collection is included inLens: NSF Partnership in Signal Processing
    By: Sidney Burrus

    Click the "NSF Partnership" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

  • Featured Content display tagshide tags

    This collection is included inLens: Connexions Featured Content
    By: Connexions

    Comments:

    "The Fast Fourier Transform (FFT) is a landmark algorithm used in fields ranging from signal processing to high-performance computing. First popularized by two American scientists in 1965, the […]"

    Click the "Featured Content" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

Also in these lenses

  • UniqU content

    This collection is included inLens: UniqU's lens
    By: UniqU, LLC

    Click the "UniqU content" link to see all content selected in this lens.

  • Lens for Engineering

    This module and collection are included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

The DFT as Convolution or Filtering

Module by: C. Sidney Burrus. E-mail the author

A major application of the FFT is fast convolution or fast filtering where the DFT of the signal is multiplied term-by-term by the DFT of the impulse (helps to be doing finite impulse response (FIR) filtering) and the time-domain output is obtained by taking the inverse DFT of that product. What is less well-known is the DFT can be calculated by convolution. There are several different approaches to this, each with different application.

Rader's Conversion of the DFT into Convolution

In this section a method quite different from the index mapping or polynomial evaluation is developed. Rather than dealing with the DFT directly, it is converted into a cyclic convolution which must then be carried out by some efficient means. Those means will be covered later, but here the conversion will be explained. This method requires use of some number theory, which can be found in an accessible form in [12] or [13] and is easy enough to verify on one's own. A good general reference on number theory is [14].

The DFT and cyclic convolution are defined by

C ( k ) = n = 0 N - 1 x ( n ) W n k C ( k ) = n = 0 N - 1 x ( n ) W n k
(1)
y ( k ) = n = 0 N - 1 x ( n ) h ( k - n ) y ( k ) = n = 0 N - 1 x ( n ) h ( k - n )
(2)

For both, the indices are evaluated modulo NN. In order to convert the DFT in Equation 1 into the cyclic convolution of Equation 2, the nknk product must be changed to the k-nk-n difference. With real numbers, this can be done with logarithms, but it is more complicated when working in a finite set of integers modulo NN. From number theory [1], [12], [13], [14], it can be shown that if the modulus is a prime number, a base (called a primitive root) exists such that a form of integer logarithm can be defined. This is stated in the following way. If NN is a prime number, a number rr called a primitive roots exists such that the integer equation

n = ( ( r m ) ) N n = ( ( r m ) ) N
(3)

creates a unique, one-to-one map of the N-1N-1 member set m={0,...,N-2}m={0,...,N-2} and the N-1N-1 member set n={1,...,N-1}n={1,...,N-1}. This is because the multiplicative group of integers modulo a prime, pp, is isomorphic to the additive group of integers modulo (p-1)(p-1) and is illustrated for N=5N=5 below.

Table 1: Table of Integers n=((rm))n=((rm)) modulo 5, [* not defined]
r m= 0 1 2 3 4 5 6 7
1   1 1 1 1 1 1 1 1
2   1 2 4 3 1 2 4 3
3   1 3 4 2 1 3 4 2
4   1 4 1 4 1 4 1 4
5   * 0 0 0 * 0 0 0
6   1 1 1 1 1 1 1 1

Table 1 is an array of values of rmrm modulo NN and it is easy to see that there are two primitive roots, 2 and 3, and Equation 3 defines a permutation of the integers nn from the integers mm (except for zero). Equation 3 and a primitive root (usually chosen to be the smallest of those that exist) can be used to convert the DFT in Equation 1 to the convolution in Equation 2. Since Equation 3 cannot give a zero, a new length-(N-1) data sequence is defined from x(n)x(n) by removing the term with index zero. Let

n = r - m n = r - m
(4)

and

k = r s k = r s
(5)

where the term with the negative exponent (the inverse) is defined as the integer that satisfies

( ( r - m r m ) ) N = 1 ( ( r - m r m ) ) N = 1
(6)

If NN is a prime number, r-mr-m always exists. For example, ((2-1))5=3((2-1))5=3. Equation 1 now becomes

C ( r s ) = m = 0 N - 2 x ( r - m ) W r - m r s + x ( 0 ) , C ( r s ) = m = 0 N - 2 x ( r - m ) W r - m r s + x ( 0 ) ,
(7)

for s=0,1,..,N-2s=0,1,..,N-2, and

C ( 0 ) = n = 0 N - 1 x ( n ) C ( 0 ) = n = 0 N - 1 x ( n )
(8)

New functions are defined, which are simply a permutation in the order of the original functions, as

x ' ( m ) = x ( r - m ) , C ' ( s ) = C ( r s ) , W ' ( n ) = W r n x ' ( m ) = x ( r - m ) , C ' ( s ) = C ( r s ) , W ' ( n ) = W r n
(9)

Equation 7 then becomes

C ' ( s ) = m = 0 N - 2 x ' ( m ) W ' ( s - m ) + x ( 0 ) C ' ( s ) = m = 0 N - 2 x ' ( m ) W ' ( s - m ) + x ( 0 )
(10)

which is cyclic convolution of length N-1 (plus x(0)x(0)) and is denoted as

C ' ( k ) = x ' ( k ) * W ' ( k ) + x ( 0 ) C ' ( k ) = x ' ( k ) * W ' ( k ) + x ( 0 )
(11)

Applying this change of variables (use of logarithms) to the DFT can best be illustrated from the matrix formulation of the DFT. Equation 1 is written for a length-5 DFT as

C ( 0 ) C ( 1 ) C ( 2 ) C ( 3 ) C ( 4 ) = 0 0 0 0 0 0 1 2 3 4 0 2 4 1 3 0 3 1 4 2 0 4 3 2 1 x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) C ( 0 ) C ( 1 ) C ( 2 ) C ( 3 ) C ( 4 ) = 0 0 0 0 0 0 1 2 3 4 0 2 4 1 3 0 3 1 4 2 0 4 3 2 1 x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 )
(12)

where the square matrix should contain the terms of WnkWnk but for clarity, only the exponents nknk are shown. Separating the x(0)x(0) term, applying the mapping of Equation 9, and using the primitive roots r=2r=2 (and r-1=3r-1=3) gives

C ( 1 ) C ( 2 ) C ( 4 ) C ( 3 ) = 1 3 4 2 2 1 3 4 4 2 1 3 3 4 2 1 x ( 1 ) x ( 3 ) x ( 4 ) x ( 2 ) + x ( 0 ) x ( 0 ) x ( 0 ) x ( 0 ) C ( 1 ) C ( 2 ) C ( 4 ) C ( 3 ) = 1 3 4 2 2 1 3 4 4 2 1 3 3 4 2 1 x ( 1 ) x ( 3 ) x ( 4 ) x ( 2 ) + x ( 0 ) x ( 0 ) x ( 0 ) x ( 0 )
(13)

and

C ( 0 ) = x ( 0 ) + x ( 1 ) + x ( 2 ) + x ( 3 ) + x ( 4 ) C ( 0 ) = x ( 0 ) + x ( 1 ) + x ( 2 ) + x ( 3 ) + x ( 4 )
(14)

which can be seen to be a reordering of the structure in Equation 12. This is in the form of cyclic convolution as indicated in Equation 10. Rader first showed this in 1968 [12], stating that a prime length-N DFT could be converted into a length-(N-1) cyclic convolution of a permutation of the data with a permutation of the W's. He also stated that a slightly more complicated version of the same idea would work for a DFT with a length equal to an odd prime to a power. The details of that theory can be found in [12], [10].

Until 1976, this conversion approach received little attention since it seemed to offer few advantages. It has specialized applications in calculating the DFT if the cyclic convolution is done by distributed arithmetic table look-up [5] or by use of number theoretic transforms [1], [12], [13]. It and the Goertzel algorithm [16], [3] are efficient when only a few DFT values need to be calculated. It may also have advantages when used with pipelined or vector hardware designed for fast inner products. One example is the TMS320 signal processing microprocessor which is pipelined for inner products. The general use of this scheme emerged when new fast cyclic convolution algorithms were developed by Winograd [21].

The Chirp Z-Transform (or Bluestein's Algorithm)

The DFT of x(n)x(n) evaluates the Z-transform of x(n)x(n) on NN equally spaced points on the unit circle in the zz plane. Using a nonlinear change of variables, one can create a structure which is equivalent to modulation and filtering x(n)x(n) by a “chirp" signal. [2], [20], [19], [16], [18], [3].

The mathematical identity (k-n)2=k2-2kn+n2(k-n)2=k2-2kn+n2 gives

n k = ( n 2 - ( k - n ) 2 + k 2 ) / 2 n k = ( n 2 - ( k - n ) 2 + k 2 ) / 2
(15)

which substituted into the definition of the DFT in Multidimensional Index Mapping: Equation 1 gives

C ( k ) = { n = 0 N - 1 [ x ( n ) W n 2 / 2 ] W - ( k - n ) 2 / 2 } W k 2 / 2 C ( k ) = { n = 0 N - 1 [ x ( n ) W n 2 / 2 ] W - ( k - n ) 2 / 2 } W k 2 / 2
(16)

This equation can be interpreted as first multiplying (modulating) the data x(n)x(n) by a chirp sequence (Wn2/2Wn2/2, then convolving (filtering) it, then finally multiplying the filter output by the chirp sequence to give the DFT.

Define the chirp sequence or signal as h(n)=Wn2/2h(n)=Wn2/2 which is called a chirp because the squared exponent gives a sinusoid with changing frequency. Using this definition, Equation 16 becomes

C ( n ) = { [ x ( n ) h ( n ) ] * h - 1 } h ( n ) C ( n ) = { [ x ( n ) h ( n ) ] * h - 1 } h ( n )
(17)

We know that convolution can be carried out by multiplying the DFTs of the signals, here we see that evaluation of the DFT can be carried out by convolution. Indeed, the convolution represented by ** in Equation 17 can be carried out by DFTs (actually FFTs) of a larger length. This allows a prime length DFT to be calculated by a very efficient length-2M2M FFT. This becomes practical for large NN when a particular non-composite (or NN with few factors) length is required.

As developed here, the chirp z-transform evaluates the z-transform at equally spaced points on the unit circle. A slight modification allows evaluation on a spiral and in segments [19], [16] and allows savings with only some input values are nonzero or when only some output values are needed. The story of the development of this transform is given in [18].

Two Matlab programs to calculate an arbitrary length DFT using the chirp z-transform is shown in Code 1.

Listing 1
function y = chirpc(x);
% function y = chirpc(x)
% computes an arbitrary-length DFT with the
% chirp z-transform algorithm.  csb.  6/12/91
%
N  = length(x);  n = 0:N-1;     %Sequence length
W  = exp(-j*pi*n.*n/N);         %Chirp signal
xw = x.*W;                      %Modulate with chirp
WW = [conj(W(N:-1:2)),conj(W)]; %Construct filter
y  = conv(WW,xw);               %Convolve w filter
y  = y(N:2*N-1).*W;             %Demodulate w chirp
 
 
function y = chirp(x);
% function y = chirp(x)
% computes an arbitrary-length Discrete Fourier Transform (DFT)
% with the chirp z transform algorithm. The linear convolution
% then required is done with FFTs.
% 1988: L. Arevalo; 11.06.91 K. Schwarz, LNT Erlangen; 6/12/91 csb.
%
N   = length(x);                %Sequence length
L   = 2^ceil(log((2*N-1))/log(2)); %FFT length
n   = 0:N-1;
W   = exp(-j*pi*n.*n/N);        %Chirp signal
FW  = fft([conj(W), zeros(1,L-2*N+1), conj(W(N:-1:2))],L);
y   = ifft(FW.*fft(x.'.*W,L));  %Convolve using FFT
y   = y(1:N).*W;                %Demodulate
 

Goertzel's Algorithm (or A Better DFT Algorithm)

Goertzel's algorithm [7], [3], [15] is another methods that calculates the DFT by converting it into a digital filtering problem. The method looks at the calculation of the DFT as the evaluation of a polynomial on the unit circle in the complex plane. This evaluation is done by Horner's method which is implemented recursively by an IIR filter.

The First-Order Goertzel Algorithm

The polynomial whose values on the unit circle are the DFT is a slightly modified z-transform of x(n) given by

X ( z ) = n = 0 N - 1 x ( n ) z - n X ( z ) = n = 0 N - 1 x ( n ) z - n
(18)

which for clarity in this development uses a positive exponent . This is illustrated for a length-4 sequence as a third-order polynomial by

X ( z ) = x ( 3 ) z 3 + x ( 2 ) z 2 + x ( 1 ) z + x ( 0 ) X ( z ) = x ( 3 ) z 3 + x ( 2 ) z 2 + x ( 1 ) z + x ( 0 )
(19)

The DFT is found by evaluating Equation 18 at z=Wkz=Wk, which can be written as

C ( k ) = X ( z ) | z = W k = D F T { x ( n ) } C ( k ) = X ( z ) | z = W k = D F T { x ( n ) }
(20)

where

W = e - j 2 π / N W = e - j 2 π / N
(21)

The most efficient way of evaluating a general polynomial without any pre-processing is by “Horner's rule" [11] which is a nested evaluation. This is illustrated for the polynomial in Equation 19 by

X ( z ) = [ x ( 3 ) z + x ( 2 ) ] z + x ( 1 ) z + x ( 0 ) X ( z ) = [ x ( 3 ) z + x ( 2 ) ] z + x ( 1 ) z + x ( 0 )
(22)

This nested sequence of operations can be written as a linear difference equation in the form of

y ( m ) = z y ( m - 1 ) + x ( N - m ) y ( m ) = z y ( m - 1 ) + x ( N - m )
(23)

with initial condition y(0)=0y(0)=0, and the desired result being the solution at m=Nm=N. The value of the polynomial is given by

X ( z ) = y ( N ) . X ( z ) = y ( N ) .
(24)

Equation 23 can be viewed as a first-order IIR filter with the input being the data sequence in reverse order and the value of the polynomial at zz being the filter output sampled at m=Nm=N. Applying this to the DFT gives the Goertzel algorithm [17], [15] which is

y ( m ) = W k y ( m - 1 ) + x ( N - m ) y ( m ) = W k y ( m - 1 ) + x ( N - m )
(25)

with y(0)=0y(0)=0 and

C ( k ) = y ( N ) C ( k ) = y ( N )
(26)

where

C ( k ) = n = 0 N - 1 x ( n ) W n k . C ( k ) = n = 0 N - 1 x ( n ) W n k .
(27)

The flowgraph of the algorithm can be found in [3], [15] and a simple FORTRAN program is given in the appendix.

When comparing this program with the direct calculation of Equation 27, it is seen that the number of floating-point multiplications and additions are the same. In fact, the structures of the two algorithms look similar, but close examination shows that the way the sines and cosines enter the calculations is different. In Equation 27, new sine and cosine values are calculated for each frequency and for each data value, while for the Goertzel algorithm in Equation 25, they are calculated only for each frequency in the outer loop. Because of the recursive or feedback nature of the algorithm, the sine and cosine values are “updated" each loop rather than recalculated. This results in 2N2N trigonometric evaluations rather than 2N22N2. It also results in an increase in accumulated quantization error.

It is possible to modify this algorithm to allow entering the data in forward order rather than reverse order. The difference Equation 23 becomes

y ( m ) = z - 1 y ( m - 1 ) + x ( m - 1 ) y ( m ) = z - 1 y ( m - 1 ) + x ( m - 1 )
(28)

if Equation 24 becomes

C ( k ) = z N - 1 y ( N ) C ( k ) = z N - 1 y ( N )
(29)

for y(0)=0y(0)=0. This is the algorithm programmed later.

The Second-Order Goertzel Algorithm

One of the reasons the first-order Goertzel algorithm does not improve efficiency is that the constant in the feedback or recursive path is complex and, therefore, requires four real multiplications and two real additions. A modification of the scheme to make it second-order removes the complex multiplications and reduces the number of required multiplications by two.

Define the variable q(m)q(m) so that

y ( m ) = q ( m ) - z - 1 q ( m - 1 ) . y ( m ) = q ( m ) - z - 1 q ( m - 1 ) .
(30)

This substituted into the right-hand side of Equation 23 gives

y ( m ) = z q ( m - 1 ) - q ( m - 2 ) + x ( N - m ) . y ( m ) = z q ( m - 1 ) - q ( m - 2 ) + x ( N - m ) .
(31)

Combining Equation 30 and Equation 31 gives the second order difference equation

q ( m ) = ( z + z - 1 ) q ( m - 1 ) - q ( m - 2 ) + x ( N - m ) q ( m ) = ( z + z - 1 ) q ( m - 1 ) - q ( m - 2 ) + x ( N - m )
(32)

which together with the output Equation 30, comprise the second-order Goertzel algorithm where

X ( z ) = y ( N ) X ( z ) = y ( N )
(33)

for initial conditions q(0)=q(-1)=0q(0)=q(-1)=0.

A similar development starting with Equation 28 gives a second-order algorithm with forward ordered input as

q ( m ) = ( z + z - 1 ) q ( m - 1 ) - q ( m - 2 ) + x ( m - 1 ) q ( m ) = ( z + z - 1 ) q ( m - 1 ) - q ( m - 2 ) + x ( m - 1 )
(34)
y ( m ) = q ( m ) - z q ( - 1 ) y ( m ) = q ( m ) - z q ( - 1 )
(35)

with

X ( z ) = z N - 1 y ( N ) X ( z ) = z N - 1 y ( N )
(36)

and for q(0)=q(-1)=0q(0)=q(-1)=0.

Note that both difference Equation 32 and Equation 34 are not changed if zz is replaced with z-1z-1, only the output Equation 30 and Equation 35 are different. This means that the polynomial X(z)X(z) may be evaluated at a particular zz and its inverse z-1z-1 from one solution of the difference Equation 32 or Equation 34 using the output equations

X ( z ) = q ( N ) - z - 1 q ( N - 1 ) X ( z ) = q ( N ) - z - 1 q ( N - 1 )
(37)

and

X ( 1 / z ) = z N - 1 ( q ( N ) - z q ( N - 1 ) ) . X ( 1 / z ) = z N - 1 ( q ( N ) - z q ( N - 1 ) ) .
(38)

Clearly, this allows the DFT of a sequence to be calculated with half the arithmetic since the outputs are calculated two at a time. The second-order DE actually produces a solution q(m)q(m) that contains two first-order components. The output equations are, in effect, zeros that cancel one or the other pole of the second-order solution to give the desired first-order solution. In addition to allowing the calculating of two outputs at a time, the second-order DE requires half the number of real multiplications as the first-order form. This is because the coefficient of the q(m-2)q(m-2) is unity and the coefficient of the q(m-1)q(m-1) is real if zz and z-1z-1 are complex conjugates of each other which is true for the DFT.

Analysis of Arithmetic Complexity and Timings

Analysis of the various forms of the Goertzel algorithm from their programs gives the following operation count for real multiplications and real additions assuming real data.

Table 2
Algorithm Real Mults. Real Adds Trig Eval.
Direct DFT 4 N 2 4 N 2 4 N 2 4 N 2 2 N 2 2 N 2
First-Order 4 N 2 4 N 2 4 N 2 - 2 N 4 N 2 - 2 N 2 N 2 N
Second-Order 2 N 2 + 2 N 2 N 2 + 2 N 4 N 2 4 N 2 2 N 2 N
Second-Order 2 N 2 + N N 2 + N 2 N 2 + N 2 N 2 + N N N

Timings of the algorithms on a PC in milliseconds are given in the following table.

Table 3
Algorithm N = 125 N = 125 N = 257 N = 257
Direct DFT 4.90 19.83
First-Order 4.01 16.70
Second-Order 2.64 11.04
Second-Order 2 1.32 5.55

These timings track the floating point operation counts fairly well.

Conclusions

Goertzel's algorithm in its first-order form is not particularly interesting, but the two-at-a-time second-order form is significantly faster than a direct DFT. It can also be used for any polynomial evaluation or for the DTFT at unequally spaced values or for evaluating a few DFT terms. A very interesting observation is that the inner-most loop of the Glassman-Ferguson FFT [6] is a first-order Goertzel algorithm even though that FFT is developed in a very different framework.

In addition to floating-point arithmetic counts, the number of trigonometric function evaluations that must be made or the size of a table to store precomputed values should be considered. Since the value of the WnkWnk terms in Equation 23 are iteratively calculate in the IIR filter structure, there is round-off error accumulation that should be analyzed in any application.

It may be possible to further improve the efficiency of the second-order Goertzel algorithm for calculating all of the DFT of a number sequence. Perhaps a fourth order DE could calculate four output values at a time and they could be separated by a numerator that would cancel three of the zeros. Perhaps the algorithm could be arranged in stages to give an Nlog(N)Nlog(N) operation count. The current algorithm does not take into account any of the symmetries of the input index. Perhaps some of the ideas used in developing the QFT [4], [8], [9] could be used here.

The Quick Fourier Transform (QFT)

One stage of the QFT can use the symmetries of the sines and cosines to calculate a DFT more efficiently than directly implementing the definition Multidimensional Index Mapping: Equation 1. Similar to the Goertzel algorithm, the one-stage QFT is a better N2N2 DFT algorithm for arbitrary lengths. See The Cooley-Tukey Fast Fourier Transform Algorithm: The Quick Fourier Transform, An FFT based on Symmetries.

References

  1. Blahut, Richard E. (1985). Fast Algorithms for Digital Signal Processing. Reading, Mass.: Addison-Wesley.
  2. Bluestein, L. I. (1970, December). A Linear Filtering Approach to the Computation of Discrete Fourier Transform. IEEE Transactions on Audio Electroacoustics, AU-18, 451–455.
  3. Burrus, C. S. and Parks, T. W. (1985). DFT/FFT and Convolution Algorithms. New York: John Wiley & Sons.
  4. Burrus, C. S. (1992). The Quick Fourier Transform. Unpublished Notes. ECE Dept., Rice University.
  5. Chu, Shuni and Burrus, C. S. (1982, April). A Prime Factor FFT Algorithm using Distributed Arithmetic. IEEE Transactions on Acoustics, Speech, and Signal Processing, 30(2), 217–227.
  6. Ferguson, Jr., W. E. (1982). A Simple Derivation of Glassman General-N Fast Fourier Transform. [Also, in Report AD-A083811, NTIS, Dec. 1979]. Comput. and Math. with Appls., 8(6), 401–411.
  7. Goertzel, G. (1958, January). An Algorithm for the Evaluation of Finite Trigonometric Series. Amer. Math. Monthly, 65, 34-35.
  8. Guo, H. and Sitton, G. A. and Burrus, C. S. (1994, April 19–22). The Quick Discrete Fourier Transform. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. (p. III:445–448). IEEE ICASSP-94, Adelaide, Australia
  9. Guo, H. and Sitton, G. A. and Burrus, C. S. (1998, February). The Quick Fourier Transform: an FFT based on Symmetries. IEEE Transactions on Signal Processing, 46(2), 335–341.
  10. Heideman, M. T. (1986, May). Fast Algorithms for the DFT and Convolution with Constrained Inputs and Restricted Outputs. Ph. D. Thesis. Rice University.
  11. Knuth, Donald E. (1997). The Art of Computer Programming, Vol. 2, Seminumerical Algorithms. (Third). Reading, MA: Addison-Wesley.
  12. McClellan, J. H. and Rader, C. M. (1979). Number Theory in Digital Signal Processing. Englewood Cliffs, NJ: Prentice-Hall.
  13. Nussbaumer, H. J. (1981, 1982). Fast Fourier Transform and Convolution Algorithms. (Second). Heidelberg, Germany: Springer-Verlag.
  14. Niven, Ivan and Zuckerman, H. S. (1980). An Introduction to the Theory of Numbers. (Fourth). New York: John Wiley & Sons.
  15. Oppenheim, A. V. and Schafer, R. W. (1989). Discrete-Time Signal Processing. Englewood Cliffs, NJ: Prentice-Hall.
  16. Oppenheim, A. V. and Schafer, R. W. (1999). Discrete-Time Signal Processing. (Second). [Earlier editions in 1975 and 1989]. Englewood Cliffs, NJ: Prentice-Hall.
  17. Parks, T. W. and Burrus, C. S. (1987). Digital Filter Design. New York: John Wiley & Sons.
  18. Rabiner, Lawrence. (2004, March). The chirp z-transform algorithm: a lesson in serendipity. IEEE Signal Processing Magazine, 24, 118–119.
  19. Rabiner, L. R. and Gold, B. (1975). Theory and Application of Digital Signal Processing. Englewood Cliffs, NJ: Prentice-Hall.
  20. Rabiner, L.R. and Schafer, R.W. and Rader, C.M. (1969, June). The Chirp Z-Transform Algorithm. IEEE Transactions on Audio Electroacoustics, AU-17, 86–92.
  21. Winograd, S. (1976, April). On Computing the Discrete Fourier Transform. Proc. National Academy of Sciences, USA, 73, 1006–1006.

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks