Chirp Z Transform Algorithm

Download as pdf or txt
Download as pdf or txt
You are on page 1of 7
At a glance
Powered by AI
The key takeaways are that the paper introduces the Chirp z-transform algorithm, which can efficiently evaluate the z-transform (discrete-time Fourier transform) at multiple points along circular or spiral contours in the z-plane. This is more efficient than directly evaluating the z-transform at individual points.

The Chirp z-transform (CZT) algorithm is discussed. It allows one to efficiently evaluate the z-transform at M points in the z-plane which lie on circular or spiral contours, beginning from any arbitrary point. This is more efficient than direct evaluation of the z-transform at individual points, which would be proportional to N*M, where N and M are the number of samples.

The CZT algorithm is based on the fact that values of the z-transform on a circular or spiral contour can be expressed as a discrete convolution. Therefore, well-known high-speed convolution techniques can be used to efficiently evaluate the transform, with a computation time proportional to (N+M)log(N+M).

1, Introduction

The Chirp x-Transform Algorithm


Member, IEEE IEEE Bell Telephone Laboratories, Inc. 1Murray Hill, N. J. c. M. RADER, Member, IEEE Lincoln Laboratory1 Massachusetts Institute of Technology Lexington, Mass.
L. R. RABINER,

R.

w.

SCHAFER, Member,

In dealing with sampled data the z-transform plays the role which is played by the Laplace transform in continuoustime systems. One example of itsapplication is spectrum analysis. We shall see that the computation of sampled z-transforms, which has been greatly facilitated by the fast Fourier transform (FFT) [l], [2] algorithm, is still further facilitated by the chirp z-transform (CZT) algorithm to be described in this paper. The z-transform of a sequence of numbers xn is defined as
00

X(2) =
n=--f:

X n P ,

(1 )

Abstract A computational algorithm fornumerically evaluating the z-transform of a sequence of N samples is discussed. This algorithm has been named the chirp z-transform (CZT) algorithm. Using the C Z T algorithm one can efficiently evaluate the z-transformat M points in the z-plane which lie on circular or spiral contours beginning at any arbitrary point in thez-plane. The angular spacing the points is an arbiof trary constant, andM and N are arbitrary integers. The algorithm is based on the fact that the values of the z-transbe expressed as a discrete form on a circular or spiral contour can convolution. Thusonecan use well-known high-speed convolution techniques to evaluate the transformefficiently. For M and N moderately large, the computation time is roughly proportional to ( N + M ) log(N+M) as opposed to being proportionalto N , M fordirect evaluation of the z-transform at M points.

a function of the complex variable z. In general, both xn and X(z) could be complex. It is assumed that the sum on the right side of (1) converges for at least some values of z. We restrict ourselves to the z-transform of sequences with only a finite number N of nonzero points. In this case, we can rewrite (1) without loss of generality as
N-I

X(2) =
n O =

(2)

where the sum in (2) converges for all z except z = 0. Equations (1) and (2) are like the defining expressions for the Laplace transform of a train of equally spaced impulses of magnitudes xn.Let the spacing of the impulses be T and let the train of impulses be xxnS(t-nr). Then which is the same as the Laplace transform is c x n e - S n T X ( z ) if we let
x
=

esT,

(3)

Manuscript received December 23, 1968; revised January 16, 1969. This is a condensed version of a paper published in the Bell System Technical Journal, May 1969. Operated with support from the U. S. Air Force. 86

If we are dealing with sampled waveforms the relation between the original waveform and the train of impulses is well understood in terms the phenomenon of aliasing. of Thus the z-transformof the sequence of samples of a time waveform is representative of the Laplace transform of the original waveform in a way which is well understood. The Laplace transform of a train of impulses repeats its values taken in a horizontal strip of the s-plane of width 2r/T in every other strip parallel to it. The z-transform maps each such strip into the entire z-plane, or conversely, the entire z-plane corresponds to any horizontal strip of the s-plane, e.g., the region - w <c < cc , - r / T I w <r/T, where s= u+jw. In the same correspondence, the j w axis of the s-plane, along which we generally equatethe Laplace transform with the Fourier transform, is the unit circle in the z-plane, and the origin of the s-plane corresponds to z = 1. The interior of the z-plane unit circle corresponds to the half of the x-plane, and theexterior left corresponds to the right half plane. Straight lines in the s-planecorrespond to circles or spiralsinthe z-plane. Fig. 1 shows the correspondence of a contour in the splane to a contour in the z-plane. evaluate the Laplace To transform of the impulse train along the linear contour is to evaluatethez-transform of the sequence alongthe spiral contour.
VOL.

IEEE TRANSACTIONS ON AUDIO AND ELECTROACOUSTICS

au-17, NO. 2

JUNE 1969

values of k merely repeat the sameN values of 4 , which of are the Nth roots unity. The discrete Fourier transform has assumed considerable importance, partly because of its nice properties, but mainly because since 1965 it has become widely known that the computation (6) can be of achieved, not in the N2 complex multiplications and additions called for by direct application of (6), but in something of the order of N log2N operations if N is a power of two, or N x m i operations if the integers m are the i prime factors of N . Any algorithm which accomplishes FFT. Much of the importance of the F F T this is called an is that DFT may be usedas a stepping stone computing to lagged products such as convolutions, autocorrelations, and cross convolutions more rapidly than before [3], [4]. The DFT has, however, some limitations which can be eliminated using the CZT algorithm which wewill describe.Weshallinvestigate thecomputation of the ztransform on a moregeneral contour, of the form
s-plane
zk

= AW-k,

0, 1,

.,M

-1

(7a)

\
Fig. 1. Thecorrespondence of (A) az-plane contour to (B) an s-plane contour through the relation z = e s T .

where M is an arbitrary integer and both arbitrary complex numbers of the form

A and W are

A
and

= AOei2r80

(7b)
(7c)

= Woej2r40.

Values of the z-transform are usually computed along the path corresponding to the j w axis, namely the unit circle. This gives the discrete equivalent of the Fourier transform and has many applications including the estimation of spectra,filtering,interpolation, and correlation. The applications of computing z-transforms off the and the general point on the s-plane contouris unit circle are fewer, but one is presented elsewhere [ 6 ] , 1 namely the enhancement of spectral resonances in systems Sk = SO k(Au +jaw) = - (In A - k I W ) , n T (9) for which one has some foreknowledge of the locations of poles and zeroes. k = 0, 1, * * , M - 1. Justas we canonlycompute(2)forafiniteset of wesee samples, so we can only compute (2)at a finite numberof Since A and W are arbitrary complex numbers that the pointssk lie on an arbitrary straight line segment points, say zk. ofarbitrarylengthandsamplingdensity.Clearlythe N- 1 contour indicated in (7a) is not the most general contour x = x(2,)= Xn2k-n. k (4) but it is considerably more general than that for which nO = the DFT applies. In Fig. 2, an example of this more genThe special case whichhas received the most attention eral contour is shown in both the z-plane and the s-plane. is the set of points equally spaced around the unit circle, To compute the z-transform along this more general zk = exp ( j z n k / ~ ) , k = 0, 1, . . , N - 1 ( 5 ) contour would seem to require N M multiplications and additions as the special symmetriesof exp(j2aklN) which for which are exploited in the derivation of the F F T are absent in N- 1 However, general case.the more we shall see that by using xk = n=O x n exP ( - j 2 n k / N ) , k = 0,1, * * 9 N - 1. (6) the sequence Wn2l2 variousroles we canapply the F F T in to the computation of the z-transform along the contour Equation (6) is called the discrete Fourier transform of (7a). Since for Wo=1,the sequence W7*2/2 complex is a (DFT).The readermay easily verify that,in (5), othersinusoid of linearlyincreasingfrequency, and sincea

(See Fig. 2.) The case A = 1, M = N , and W=exp( -j2n/N) corresponds to the DFT. The generalz-plane contour begins with the point z = A and, depending on the value = of W , spirals inor out with respectto theorigin. If Wo 1, the contour is an arc of a circle. The angular spacing of the samples is 2 ~ 9The. equivalent s-plane contour begins ~ with the point 1 so = uo jwo = - I A n (8) T

RABINER et

al.: CHIRPZ-TRANSFORM

ALGORITHM

87

Fig. 3. An illustration of the steps involvedin z-transform using the CZT algorithm.

computing values

of the

served. But, let us use the ingenious substitution, due to Bluestein [ 5 ] ,

nk

722
~

4-k2 -__- n)Z (k 2

(1 1 )

forthe exponent of W i n (10). This producesan parently more unwieldly expression

ap-

AT- I

I C

n=O

IL.1,A-n~~~(n2/e)~t;(k~,.2)~-(b--n)2!2

,
k
I

(12)

0,I,.

. . , 39 - I ;

but, in fact, (12) can be thought of as a three-step process consisting of:

1) forming a new sequence yn by weighting the x, according to the equation


yn
Fig. 2. Anillustration o f theindependentparametersofthe CZT algorithm. (A) How the z-transform is evaluated on a spiral contour starting a t the point z = A . (B) The corresponding straight line contour and independent parameters in the s-plane.

, Z . ~ A - - ~ F V ~ ' ; n., = 0, 1, * . ~

, .X -

1 ; (13)

2) convolving yn with the sequence v, defined as


t'n =
W--n2/2

(1 3 )

to give a sequence

gk,

similar waveform used insomeradar systems hasthe n=O picturesque name "chirp," we call the algorithm we are 3) multiplying g k by W k 2 /to give XIc, 2 about to present the chirp z-transform (CZT). Since the CZT permits computing the z-transform on a more genXI,= gI,TV~"Z, 1; = 0, 1, ' . . , 31 - 1. (16) eral tour than the F F T permits it is more flexible than the FFT, although itis also considerably slower. The addiThe three-step process is illustrated in Fig. 3. Steps 1 tional freedoms offered by the CZT include the following: and 3 require N and M multiplications, respectively, 1) The number of time samples does not have to equal and step 2 is a convolution which may be computed by the high-speed technique disclosed by Stockham [ 3 ] , the number of samples of the z-transform. based on the use of the FFT. Step 2 is the major part of 2) Neither M nor N need be a composite integer. the computational effort and requires a time roughly pro3) The angular spacing of the zk is arbitrary. 4) The contour need not be a circle but can spiral in or portional to ( N + M ) log (N+M). Bluestein employed the substitution of (1 I) to convert out with respect to the origin. In addition, the point zo is arbitrary, but this is also the case with the FFT if the a DFT to a convolution as in Fig.3. The linear system to samples xn are multiplied by zg-" before transforming. which the convolution is equivalent can be called a chirp filter which is, in fact, also sometimes used to resolve a spectrum. Bluestein [ 5 ] showed thatfor N a perfect II, Derivation of the CZT square, the chirp filter could be synthesized recursively of with z/W multipliers and the computation a DFT could Along the contour of (7a), (4) becomes then be proportional to N 3 / 2 . x- 1 The flexibility and speed of theCZT algorithm are X k = XnA-f~Wnk, 1; = 0, 1: . . . , Jl - 1 (10) related to the flexibility and speed of the method of highn-0 speed convolution using the FFT. The reader should rewhich, at first appearance, seems to require N M complex call that the product of the DFT's of two sequences is multiplicationsandadditions, as we havealready ob- the DFT of the circular convolution of the two sequences
88
IEEF, TRANSACTION ON AUDKO A N I ELECTKOACOUSlICS JUNE

1969

and, therefore, a circular convolution is computable as two DFT's, the multiplication of two arrays of complex numbers, and an inverse discrete Fourier transform (IDFT), which can also be computed by the FFT. Ordinary convolutions can be computed as circular convolutions by appending zeroes to the end of one or both sequences so that the correctnumericalanswersforthe ordinary convolution can result from a circular convolution. We shall now summarize the details of the CZT algorithm on the assumption that an already existing FFT program (or special-purpose machine) is available to compute DFT's and IDFT's. , Begin with waveform in the a form of N samples x and seek M samples of Xkwhere A and W have also been chosen.

(B)

1M ;.
t
y,

(c)
L-l

1) Choose L, the smallest integer greater equal or than to N+M- 1 which is also compatible with our highspeed FFT program. For most users this will mean L is a power of two. Note that while many FFT programs will L, they arenot equally efficient for workforarbitrary all L. At the very least, L should be highly composite. an 2 ) Form L point sequence y, from x by ,
Yn-

(D)

{A - n W n z / Z ~n, 0, 1, 2, . . 0 n=N, N+1,


=

,N * *

1
(E)
arbltrary

, L-1.

3) Compute the L point DFT of y by the FFT. (17) , Call this Y,, r=O, 1, , L-1. 4) Define an L point sequence v, by the relation
V, =

4
L-N+I
L-l n
L-l r

W-(L-n)2/z - N L
arbitrary

+15 n <L

(18)
(F)

other n, if any.

Of course, if L is exactly equal to M+N- 1, the region in which v, is arbitrary will not exist. If the region does exist an obvious possibility is to increase M , the desired number of points of the z-transform we compute, until the region does not exist. Note that v, could be cut into two with a cut between n = M - 1 and n =L- N+ 1 and if the twopieces wereabutted together differently, the resulting sequence would be a slice out of the indefinite length sequence W--n2/Z. is This illustrated in Fig. 4. The sequence v, is defined the way it is in order to force the circular convolution to give us the desired numerical results of an ordinary convolution. 5) Compute the DFT of v, and call it V,, Y = 0, 1, ., L- 1. 6) Multiply V, and Y,. point by point, giving G,:

(GI
1.1

(i-l)

e---

M-l

I-

-------___---not d L-l h

IXk
(1)

G,

V,.Y,, r

0, 1, . . . , L - 1.

7) Compute the L point IDFT g k , of G,.. 8) Multiply g k by Wk2IZ give the desired Xk: to
X k
=
Wk2/*yiC,

hn I I I I
Y-l

*
h

12

0, I., 2,

'

'

'

, nf -

1.

The gk for k > M are discarded. Fig. 4 represents typicalwaveforms (magnitudes shown, phase omitted) involved in each step of the process.
RABINER

Fig. 4. Schematic representation of the various sequences involved in CZT the algorithm. (A) The input sequence xn with N values. (B) The weighted input sequence Y ~ = A - ~ W " ' / ~ X The DFT of yft. (C)~ . (D) The values of the indefinite sequence W-"2'2. (E) The sequence vn formed appropriately from segments o f W-n2/z.(F) The DFT o f vn.

( G ) Theproduct G,=Y7.V,. (H) TheIDFTof va!ues of the r-transform.

G,.. (!) Thedesired

et a[.: CHIRP Z-TRANSFORM ALGORITHM

89

111. Fine Points of the Computation


Operation Count and Timing Considerations

By choosing No= (N-M)/2 it can be seen that thelimits 1) We assume that step 1, choosing L , is a negligible over which W-nz12i s evaluated symmetric; are Le., W-n2/2 a symmetric function is in bothitsrealand operation. 2) Forming yn from xn requires N complex multiplica- imaginary parts. (It follows thus that the transform of W-n2/2 also symmetric in both its real and imaginary is tions, not counting the generation of the constants A-nWn2/2. constants may be prestored, computed as parts.) It can be shownthat using this special value of No, The needed, or generated recursively as needed. The recursive only (L/2+1) points of W-n2/2need be calculated and computation would require two complex multiplications stored and these (L/2+ 1 ) complex points can be transformed using an L/2 point transform.2 Hence the total per point. 3) An L point D F T requires a time kFFTL L for L storagerequiredfor logz is thetransform of W--n2/2 L+2 a power of two, and a very simple F F T program. More locations. complicated (but faster) programs have more complicated The only other modifications to the detailed procedures forevaluatingthe CZT presentedin Section I1 of this computing time formulas. 4, 5) vn is computed for either M or N points, which- paper are: 1) following the L point IDFT of step 7 , the ) to permits the other data of array yk must be rotated the left by Nolocations; ever is greater. The symmetry in W-n2/2 rather and 2) the weighting factor of the gk is Wk2/2WNok values of v, to be obtained without computation. Again, than W k 2 / 2 . additional factor W7ok The represents a data v, can be computed recursively. The FFT takes the same time as that in step 3. If the same contour is used for shift of No samples to the right, thus compensating the many sets of data, V, need only be computed once, and initial shift and keeping the effective positions of the data invariant to the value of N o used. stored. An estimate of thestoragerequired to performthe 6) This step requires L complex multiplications. 7) This is another FFT and requires the same time as CZT can now be made. Assuming that the entire process is to take place in core, storage is required for V, which step 3. takes L+2 locations; for y., which takes 2L locations; 8) This step requires M complex multiplications. and perhaps for some other quantities which we wish to As the number of samples of xn or X k grow large, the save, e.g.,theinput, or values of W+n2!2 k n W n 2 I 2 . or computation time for the CZT grows asymptotically as something proportional to L lognL. This is the same sort Additional Considerations of asymptotic dependence of the FFT, but the constant Since the CZT permits M # N , it is possible that occaof proportionality is bigger for the CZT because two or sions will arise where M>>N or N>>M. In these cases, if three FFTs are required instead of one, and because L is greater than N or M . Still, the CZT is faster than the the smaller number is small enough, the direct method of directcomputation of (10) even for relatively modest (IO) is called for. However, if even the smaller number is large it may be appropriate to use the methods of sectionvalues of M and N , of the order of 50. ing described by Stockham 131. Either the lap-save or lap-addmethods may be used. Sectioning may also be Reduction in Storage used when problems too big to be handled in core memory The CZT canbe put into a more useful form for comarise. We have not actually encounteredany of these putation by redefining the substitution of (11) to read problems and have not programmed the CZT with provision for sectioning. (n - AVO)2 k 2 - ( k - n ____ __-- . + LvO) 2LVOk nk = _____ Since the contour for the CZTis a straight line segment in the s-plane, it is apparent that repeated application of the CZT can compute the z-transform along a contour Equation (12) can now be rewritten as which is piecewise spiral in the z-plane or piecewise linear X-1 XI, T Y k z / / 2 J J 7 N o k Z,A-nTTr(a-No)Y/21V-(k-n+,vo)Yi2, in the s-plane. 7L= 0 Let us briefly consider the CZT algorithm for the case circle. This meansthat thez-transform of zkall on the unit The form of the new equation is similar to (12) in that is like a Fourier transform. Unlike the DFT, which by the input dataxn are pre-weighted by a complex sequence definition gives N points of transform for N points of (A- W+*o) /2), convolved with a second sequence (W--(n-h~)2/2), and post-weighted by a third sequence 2 The techniquefor transforming two real symmetric point seL ( u r r C 2 ~ z J V ~ k ) compute the output to sequence X . Howk quences using one L / 2 point FFT was demonstrated by J. Cooley ever, there are differences in the detailed procedures for at the FFT Workshop, Arden House, October 1968. A summary of xn realizing the CZT. The input data can be thoughtof as this technique i s presented in the Appendix.

An operation count can be made, roughly, from the eight steps just presented. We willgive it step by step because there are, of course, many possible variations to be considered.

having been shifted by No samples to the left; e.g., .xo is weighted by WNo2/2 instead of Wo.The region over which W-nlz must be formed, in order to obtain correct results from the convolution, is

90

IEEE TRANSACTIONS ON AUDIO AND ELECTROACOUSTICS

JUNE

1969

data, the CZTdoes not require M = N . Furthermore, the zk need not stretch over the entire unit circle but can be equallyspacedalong anarc.Let us assume,however, that we are really interested in computing the N point DFT of N data points.Still theCZT permits us to choose any value of N , highly composite, somewhat composite, or even prime, without strongly affecting the computation time. An important application of the CZT may be computing DFT's when N is not a power of two and when the program special-purpose or device available for computing DFT's by F F T is limited to the case of N a power of two. There is also no reason why the CZT cannot be extended to the case of transforms in two or more dimensionswithsimilarconsiderations.Thetwo-dimensional DFT becomes a two-dimensional convolution which is computable by FFT techniques. We caution the reader t o note that for the ordinary FFT the starting point of the contour is still arbitrary; merely multiply the waveform x,, by A-" before using the FFT, andthe firstpoint onthecontour is effectively moved from z = 1 to z= A . However, the contour is still restricted to a circle concentric withthe origin. The angular spacing of zk for the F F T can also be controlled to some extent by appending zeroes to the end of x,, before computing the DFT (to decrease the angular spacing of x,, the zk) by choosing only P of the Npoints and adding or together all the x,, for which the n are congruent modulo P ; i.e.,wrapping the waveform around a cylinder and adding together the pieces which overlap (to increase the angular spacing).
IV. Limitations

We need one FFT and 2L storage locations for the transform of X , , A - " W " ~ / ~ ;FFT and L+2 storage locations one and for the transform W-nz12; one F F T for the inverse transform of the product of these two transforms. We of do not know a way of computing the transform W--n2/2 either recursively or by a specific formula (except in some trivial cases). Thus we must compute this transform and store it in an extra L+2 storage locations. Of course, if many transforms areto be done with the same value of L, we need not compute the transform of W--n2/2 time. each A-" recursively as We can compute the quantities W n 2 / z they are needed to save computation and storage. This is easily seen from the fact that
A - ( n f l ) T / T ' ( ~ ~ + 1 ) ~ /= 2

(A--nlvn2/2), n W I / Z A - l . W

('9)

If we define

C,
and

= A-%Hin2/2

(20)

D, = WnW1/2A-1
then
Dn+l

(21)

We Dn
Cn. Dm.

(22) (23)

and
Cn+l

One limitation in using the CZT algorithm to evaluate the z-transform off the unit circle stems from the fact for that we may be required to compute Wofn2'z large n. V. Summary A computational algorithm for numerically evaluating If Wodiffers very much from 1.0, Wo*:nZ/z becomevery can large or very small when n becomes large. (We require a the z-transform of a sequence of N time samples was preThis entitled chirp the z-transform large n when either M or N become large, since we need sented. algorithm, of t o evaluate Wna/2for n in the range - N < n< M . ) For algorithm, enables the evaluation the z-transform at M example, if W0-e -.25/1000=0.999749, and n= 1000, equi-angularly spaced points on contours which spiral in or out (circles beingaspecial case) fromanarbitrary W o i n a= i2 which exceeds the single precisionfloating starting point in the z-plane. In the s-plane the equivalent point capability of most computers by a large amount. contour is an arbitrary straight line. Hence the tails of the functions be can greatly in The CZT algorithm has great flexibility in that neither error, thus causing the tails of the convolution (the high frequency terms) to be grossly inaccurate. The low fre- N or M need be composite numbers; the output point quency terms of the convolution will also be slightly in spacing is arbitrary; the contour is fairly general and N need not be the same as M . The flexibility of the CZT error but these errors are negligible in general. The limitation on contour distance in or out from the algorithm is due to being able to express the z-transform unit circle is again due to computation of W n 2 l z . As Wo on the above contours as a convolution, permitting the deviates significantly from 1.0, the number of points for use of well-known high-speed convolution techniques to which W*n2/2 be accurately computed decreases. It is evaluate the convolution. can Applications of the CZT algorithm include enhance= of importance to stress, however, that forWo 1, there is no limitation of this type since W*"'/2is always of magni- ment of poles for use in spectral analysis; high resolution, of narrowband frequency analysis; and time interpolation tude 1. The other main limitation on the CZT algorithm stemsdata from one sampling rate to any other sampling rate. from the fact that L point, andone L/2 point, FFT's These applications are explained in detail elsewhere [ 6 ] . two The CZT algorithm also permits use of a radix-2 FFT mustbe evaluatedwhere L is the smallestconvenient integer greater than N + M - 1 as mentioned previously. program or device to compute the D F T of an arbitrary
RABINER et

Setting A = 1 in (19) to (23) provides an algorithm for the coefficients required for the output sequence. A similar recursion formula can be obtained for generating the seThe quence A-nW(n-Na)2/2. user is cautionedthat recursive computation of these coefficients may be a major source of numerical error, especially when Wo=1, or +o=O.

al.: CHIRP Z-TRANSFORM

ALGORITHM

91

number of samples. Examples illustrating the how CZT algorithm is used in specific cases are included elsewhere [6]. It is anticipated that other applications of the CZT algorithm will be found.
Appendix

= ;

i{Im [

~ k ]

+ Im

[~L,p-k]}

- ____ { Im
4 sin - k
2a

[G,] Im -

[cL/~-~I

The purpose of this Appendix is to show howthe FFTs of two real, symmetric L point sequences can be obtained using one L/2 point FFT. Let x, and yn be two real, symmetric L point sequences k with corresponding DFTs X and Yk. By definition,

for k = 1, 2, . , L/2- 1. The remaining valuesof X k and Yk are obtained from the relations
s
~~

x,=
Yo =

7,-

5
L- 1

yn

and it is easily shown that Xkand Yk are real, symmetric L point sequences, so that

XLjZ

=
n=O
L- 1

I, - I) C(

n=O

References

Define a complex L/2 point sequence u, whose real and imaginary parts are

[ l ] J. W. Cooley and J. W. Tukey, An algorithm for the machine calculation of complex Fourier series, Marh. Camp., vol.19,

The L/2 point DFT of u,& denoted U k and is calculated is by the FFT. The values of X and Yk may be computed k from U kusing the relations
=

+ { R e [C.,]

+ Re

[CT~;l-klI j

pp. 297-301,1965. [2] G-AE Subcommittee on Measurement Concepts, What is the fast Fourier transform? IEEE Trans. Audio and Electroacousfics, vol. AU-15, pp. 45-55, June 1967. 131 T. G. Stockham,Jr.,Highspeedconvolutionandcorrelation, 1966 Spring Joint Computer Cor$, AFIPS Proc., vol. 28. Washington, D. C. : Spartan, 1966, pp. 229-233. [4]H. D. Helms, Fast Fourier transform method of computing IEEE Trans. difference equations simulating and filters, Audio and Electroacoustics, vol. AU-15, pp. 85590, June 1967. [ 5 ] L. I. Bluestein, A linear filtering approach to the computation of the discrete Fouriertransform, I968 NEREM Rec., pp. 218-219. [ 6 ] L. R. Rabiner, R. W.Schafer,andC. M. Rader, The chirp z-transform algorithm and its applications, Bell Sys. Tech. J . , vol. 48,pp. 1249-1292, May 1969.

Lawrence R. Rabiner (S62-M67), for a photograph and biography, please see page 13 of the March, 1969, issue of this TRANSACTIONS. Ronald W. Schafer (S62-M67) was born in Tecumseh, Neb., on February 17, 1938. He received the B.Sc.E.E. and M.Sc.E.E. degrees from the University of Nebraska, Lincoln, in 1961 and 1962, respectively, and the Ph.D. degree in electrical engineering fromthe Massachusetts Institute of Technology, Cambridge, in February, 1968. From 1962 to 1963 he served as an Instructor in the Department of Electrical Engineering at the University of Nebraska, and from 1964 until 1968 he was an Instructor in the Department of Electrical Engineering at M.I.T., where he received a departmental award for teaching. During 1965 he was with the M.I.T. Electronic Systems Laboratory, where he worked on digital computer simulations of guidance and control systems, and from 1966 to 1968 he was with the M.I.T. Research Laboratory of Electronics. At present he is engaged in research on digital speech processing techniques at Bell Telephone Laboratories, Inc., Murray Hill, N. J. Dr. Schafer is a member of Eta Kappa Nu,Sigma Xi, and the Acoustical Society of America.

C.M. Rader (S59-M62), for a photograph andbiography, please see this issue, page 76.
92
IEEE IRANSAC-rIONS O N AUDIO AKD ELECTROACOUSTICS JUNE

1969

You might also like