56 IEEE TRANSACTIONS ON ACOUSTICS, SPEECH, AND SIGNAL PROCESSING, VOL. ASSP-26, NO.

1 , FEBRUARY 1978

Abstract-The paper shows how discrete Fourier transformation can A . The Complex D F T
be implemented as a Filter bank in a way which reduces the number of
filter coefficients. A particular implementation of sucha filter bank Given N complex values x(O),x(l), x(2),
* * -
, x(N - l), the
is directly related to the normal complex FFT algorithm. The prin- DFT is defined by
ciple developed furtherleads to types of DFT filter bankswhich
utilize aminimum of complex coefficients. These implementations N-I
lead to new forms of FFT's, among which is a cos/sin FFT for a real a(n)= x@) W G ~ ~ (1)
k=O
signal which only employs real coefficients. The new FFT algorithms
use only half as manyreal multiplications as does the classical FFT. where
WN = exp (25~j/N). (2)
INTRODUCTION
n can take the values 0, 1, . * (N - 1).
N thispaper we deal withfdters which perform discrete
Fourier transforms (DFT). In one type of such filters, B. The Real DFT
z-transform filters, a sampled signal is analyzed by means of
Given N real values y(O), y(l), y ( 2 ) , . . , y(N - l ) , the cos-
delay sections and multipliers. Such afilter can either be
DFT is defined by
analog or digital. The analog types of z-transform filters have
recently become of increasing importance, as they can be N- 1
implemented as transversal filters by using CCD or bucket- A(n) = y ( k ) cos (25~nklN) (3)
k=O
brigade circuits as delay sections.
In a study of DFT z-transform filters we are attacking the and the sin-DFT by
problem: Can we at the cost of an increased number of delay
N- 1
sectionsreducethenumber of multipliers? It appears that
B(n) = y ( k ) sin (2nnklN). (4)
this is possible. The result of the search leads to a general k=l
type of filter which in a special case handles the signal to be
analyzed in a way which is analog to the classical fast Fourier WedefineA(n)forn=O,l;..,(N/2)andB(n)forn=1,2,
transform (FFT) algorithm. * . , (N/2 - 1);N is assumed being even.
In the analysis of a signalusing the z-transform filter, to
obtain the FFT algorithm we just need at a fmed time to con- II. THE DFT Z-TRANSFORMS
sider how the set of filter output sample values are calculated We letthetwo series x ( k ) and y ( k ) represent two time
from the set of sample values of the input signal loaded into series, x(O), x(l), . . , x ( k ) . . . being signal values at times
+

the filter at that particular time. An example of thispro- t = 0 , 1 , * , k , * * , and similarly for the y ( k ) series.The
cedure is given in Section V. The result is the classical FFT. DFT's can then be implemented by well-known transversal
Using the methods mentioned above, we develop in Section filters. Fig. 1 shows such a filter for the complex DFT. The
VI types of FFT algorithms which to the best of the author's sampled data delay line or shift register shown on top of the
knowledge are new. In Section VI, the following question is figure containsthe complex time seriessignal. The Fourier
raised concerning the z-transform filter: Is it possible to re- transforms of the time series are taken from a set of adding
duce the number of complex multipliers? In answer to this devices after multiplication has takenplace.
question, the general filter principle mentioned above leads The result which is obtained in accordance with (1) is
to a filter configuration, which performs complex DFT with obtained at time t = N - 1 . Becauseof the intricacy of the
a minimum of complex coefficients, and to another filter with complex multiplications needed, it is most realistic to think
only real coefficients which performs cos- and sin-DFTon of the filter shown as a digital filter. The filter of Fig. 1 pro-
a real signal. These two filters lead directly to the new FFT vides Nz-transfer functions, one at each port, of the form
algorithms. Fn(z) = Z-(N-l) + W-1'nz-(N-2)
I. THE DISCRETE FOURIER TRANSFORMS + . . . w-k-nZ-(N-k-1) + . . . w-(N-l)'n (5)
The representations of the DFT we are dealing with are the
The transfer functions corresponding to the real transforms
complex DFT and the real cos/sin DFT's.
A(n) and B(n) in (3) and (4) are considered under the assump-
tion of N being even.
Manuscript received November 22, 1976; revised September 7, 1977.
The author is with the Electronics Laboratory, Technical University The transfer functions for the A(n) coefficient part of the
of Denmark, Lyngby, Denmark. filter are

0096-3518/78/0200-0056$00.75 01978 IEEE

BRUUN: DFT FILTERS AND FFT'S

Fig. 1. Transversal filter performing complex DFT; the a(0) circuit is not shown.

( z ) t cos (n * 2n - I / N ) z - ( ~ - ~ )
~ ~ ~= z-(N-l) transmitted when m = n. This result indicates that we have the
same set of equidistant zeros on the unitcircle, but as we deal
-
t cos (n 2n 2 / ~ ) ~ - ( ~ - ~ )
+
with a z-transform with real coefficients, a pair of conjugate
. . . t cos (n . 2 n . ( N - l)/N) (6) zerosatexp (?j(2n/N) n ) is excluded. This result isvalid
when n # O and n #N/2. When n = 0 or when n = N/2, one
and for theB(n) coefficients zero at t 1 or at - 1, respectively, is missing.
( z(n *) 2n * I / N ) z - ( ~ - ~ )
~ ~ ~= sin When n # 0 and n #N/2, we find that the highest power
2-l in F A ~ (must
Z ) be (N - 1). The remaining missing zero is
t sin (n * 2n * 2 / ~ ) ~ - ( ~ - ~ ) found at l/cos ((2n/N * n); see the example shownin Fig. 2(b)
* t sin (n * 2n(N - I)/N). (7) for the same values of N and n as in Fig. 2(a). To locate this
extra zero, we write the expressionfrom (6) in the form
111. THE CONFIGURATION OF ZEROS
The filter from Fig. 1 and the corresponding A(n) and B(n)
filters can in principle, of course, be operating at all different
frequencies. For the sake of simplicity, we will in the follow-
ing let them be thought of as operating at a sample frequency
f, = 1 Hz, which is a shift-angular frequency w, = 2n rad/s or a If, in the last part of (9), we combine terms two at a time
delay in the shift registers of T = 1 s. We will now consider corresponding to conjugate pairs of zeros, we find that the
thezeroconfigurationsforthe filters corresponding to (5), expression canbe written in the form
(61, and (7). FAn(Z)= z-W-1) +- .. * Pi:.
From (1) we can see directly that the particular stationary
signal x,(k)=exp (mk*2nj/N), m = 0 , l;.., (N- 1) will Comparing (10) and (6) we confirm
only be transmitted by the discrete filter Fn(z) when the fre-
quency m/N is equal to n/N. This is a way of realizing that the pnx = (cos (n .2n(N - I)/N))-l = cos (-$- * n)
-1
. (1 1)
zeros of Fn(z) willallbe locatedattheunit circle ofthe
z-plane, and only one of a set of equidistant zeros is missing. Using the same method as was used for FA~(z), we find the
The zeros are at zeros of FBn(z) (7)to be at the same equidistant locations on

Pnk=eXp 1 - (.;.I k , k = 0 , 1,2,'",(N-

kfn.
1)
theunit circleas found in thetwo previouscases. Further-
more, a constant factor is needed as seen below. In this case,
the same pair of conjugate zeros used for the cos-transforma-
tion is missing. We get
Fig. 2(a) shows the zero configuration for the case of N = 16
andn=3. FB~(z) = sin
n+O
(n * 2 n / ~ ) n
N-1

k=O
(z-l - p i ; )
From this result we can write N kfn
n+y
Fn(z) = n
N-1

k= 0
(z-1 - pi:). k f ( N - n ).
Fig. 2(c) shows an example of zero locations forFBn(z).
kfn
Forthefiltercharacterizedby FA~(z),(6) atransmission I v . A FILTERTREE FOR THE COMPLEXDFT
consideration analogous to the one used above shows that a Fromthe results of theprevioussection wesee that it is
steady-state signal y, ( k ) = cos (mk 2n/N) also will only be possible for several of the Fn(z) sections of the filter t o share
58 IEEE TRANSACTIONS ON ACOUSTICS, SPEECH, AND SIGNAL PROCESSING, VOL. ASSP-26, NO. 1, FEBRUARY 1978

(4 (b) (Cl
Fig. 2. Examples of zero configurations for DFT's;N= 1 6 , n = 3 for (a) complex DFT, (b) cos-DFT, (c) Sin-DFT.

1 alp) o l r ~ ~

(z-f-q;') (z-'-q-')

Fig. 3. Complex DFT-filter tree.

a number of zeros. This fact is utilized in the design procedure designate the zeros contained in the particular filter unit.
to be discussed in this section. We show a filter configuration This filter is built according to the following principle:
which utilizes a much smaller number of multipliers, whereas,
on the other hand, the total number of shift register units is AUB=U
much higher than the N units used forthe filter shown in CUD=B
Fig. 1.
Such a filter which corresponds to the complex DFT-transfer EUF=A
functions ( 5 ) and (8) is shown schematically in Fig. 3. The J U K =C
filter is composed of filter units which are in principle of the
same type as the transversal filter from Fig. 1. The filter units L UM=F
can, however, aswe shallsee inlater examples, be much N U P = E , etc.
simpler as they can be made to contain only one or two multi-
-
pliers. In Fig. 3, the filter units A , B, C . . are thought of as This way the filter may be built such that when passing from
consisting of a cascade of subunits of the type shown on top the input at the top to the last splitting node at the bottom,
of Fig. 3, each representing one of the N zeros on the unit only two of the complete set U of unit circle zeros willbe
circle. A hypothetical fiiter unit containing the complete set missing. For such a particular node, we will, forexample,
of zeros is designated by U, and in the following, A , B , C, etc., miss the zeros q p and q p . Now, by adding one extra set of
BRUUN: DFT FILTERS AND FFT'S 59

I
I '- ' I
'+
n even
/odd nbr. roofs/ I ''-' 1 n odd
/even nbr. roots)

n.'~,~.a... n ' 2.6,IO,. , n: 1,s.9 , . . n:3, 7, 11,. .

FP -j f++j

I I i 1 I I I I
I I I
I , I

n:O,8,.. n:4.12,.. n'2.10. . . n:6,1L,.. n:1,9,.. n'5,13,.. n:3,11,.. n:7,15,..

Fig.4. Principle of complex DFT-filter tree.

one-zero branches to each of these nodes at the bottom of the of the filter. Following the same procedure as above, we con-
filter, we obtainacompleteDFT filter. Forthe particular clude with the following expression:
node mentioned, the connection o f a branch with gain (z-' -
q;'), we obtain the output a@) and by a branch (z-' - qp'),
we obtain a(r).
According to this principle, a DFT filter can, of course, be
where u = 2t.
builtup in many different ways.One important class of
If we start from the top in Fig. 4, we find the blocks repre-
configuration is the one made in such a way that all branches
sentingthe first factor in (13)orthefactor in (15)which
at a certain levelhave the same number of zeros. This pro-
corresponds t o t = 1. The next factor is
cedure can, of course, only be followed when N is an integer
power of 2. In the following, we will only deal with cases of
this restriction.
In Fig. 4 is shown the principle o f a DFT filter according
to the principle last mentioned. The structure is developed as
follows. For the last term in (16) we find
Equation (5) can be written
(1 [n=0,4,8 * * a

F (z) = ( z - ( N / 2 ) +.W - ( N / 2 ) ' n ) ( z - ( ( N / ~ ) - ~ )

W - n . l Z - ( ( N / 2 ) - 2 )+ . . . + . . . +. V-(WP)-~).~).
exp (-j 4 n(modulo
-j [n=l,5,9
[ n =- 12 , 6 , 1 0 . * *
a * *

Blocks representing these results are shown in the second row

In the second factor of (13), we find again a polynomium in of blocksin Fig. 4.
z-', thedifferencefromthe originalbeing thatthe highest In Fig. 5, an example is shown how this development leads
power has been reduced byN / 2 ;otherwise the formis exactly to a block diagram for determining the complex DFT's for the
the same as of (5). From case of N = 8.
It is now necessary to show that the development which we

i
~ - ( N / 2 ) ' n= exp - 2nj - =
3{ -1
1

we find that the N / 2 roots of the first factor in (13) are

(n even)

(n odd)
have demonstrated is carried out in accordance with the princi-
ple discussed above in connection with Fig. 3. For the part of
the filter which is shown in Fig. 4, wesee directly that we
follow the principle of Fig. 3. The two blocks in the upper
row represent all the N zeros on the unit circle, and the prod-
uct of the z-transforms for the two blocks to the right in the
second row is equal to the z-transform for the block to the left
inthe first row.Thatthesystem, in general, followsthe
principle of Fig. 3 can be seen by induction.
V. THE DFTz-TRANSFORM FILTER AND THE FAST
k=O,l,*-,(;- 1). FOURIER TRANSFORM (FFT)
The filter developed in the previous paragraphcan be used to
According to this result, wesee inFig. 4 how the blocks show the developmentofthewell-knownalgorithm of the
(z-(~/') t 1) and ( z - ( ~ / '-) 1) are taken as the first branches FFT of a complex signal.Fig. 6 shows oneof the possible
60 IEEE TRANSACTIONS ON ACOUSTICS, SPEECH, AND SIGNAL PROCESSING, VOL. ASSP-26, NO. 1, FEBRUARY 1978

Ix
X

$ n evec n cdd

n: 0 4 2 6 1 5 3 7

Fig. 5 . Example of complex DFT-filter tree f o r N = 8.

n: 7 3 5 1 6 2 L 0

77
W = expl). 5) w”;-w-/=i w-6 = _ w-2 --I

--
Fig. 6. Signal-flow graph for classical FFT; N = 8. The graph can also be deducted from the filter tree in Fig. 5.

signal-flow diagrams foracomplex8-point FFT. On top of of blocks ( z - ( ~ / ’ )t 1) and (z-(~/’) - 1) have exclusively real
the diagram, nodes representing the input signal are indicated, coefficients. Using the following identity (1 7) we can, for the
and at the bottom we find the DFT values a(O)-a(7). To see complex DFT, continue with real coefficients until we reach
the relationship between the block diagram in Fig. 5 and the the bottom row of blocks. The identity we use is
signal-flow graph, let us take the output from the block giving 1 t m 2 q t 2 4 q = ( 1 + - V E T 24 tz’4)(1 24
4 7 ) . This output is obtained through the (z-’ - W 3 ) block,
which means that the value a(7) can be obtainedfromtwo t z2*). (1 7)
other complex values, one of which is shifted one time unit in Fig. 7 shows a filter for the case of N = 16 built up by utiliz-
relation to the other. In Fig. 6 wesee how this same result, ing an expansion which follows from (1 7) and is in accordance
a(7), is obtained from two nodes which can be thought of as with the principle of Section N. We see that the product of
representing signal values with a relative shift of one time unit. the z-transforms of two adjacent blocks a and b is equal to the
From Fig. 5, we see that each of the latter signal values in turn z-transform of the block which is adjacent to the block a and
are found from two other values with a time difference of two b are connected to.
units. Following this kind of development, we are able to In Fig. 7 the blocks are ordered such that of two neighbor-
translate Fig. 5 directly into Fig. 6. ing blocks, the one having plussigns before the square-root
signis placed above the minus block. InFig. 8 is shown a
VI. DFT FILTERTREESWITH REAL COEFFICIENTS table with the series of the same square-root coefficients for
Building up a DFT tree according to Fig. 3, we have a possi- rows 2, 3, and 4 of a filter, i.e., coefficients from 3 of the 5
bility of choosing branches with a maximum of real filter rows of blocks needed for a filter for N = 32. Note how a part
coefficients. For the filter shown in Fig. 4, only the first row of the same series of coefficients is used in each row.
62 IEEE TRANSACTIONS ON ACOUSTICS, SPEECH, AND SIGNAL PROCESSING, VOL. ASSP-26, NO. 1 , FEBRUARY 1978

151.5 13 1 2 1 1 10 9 8 7 6 5 L 3 2 1 0

n: 71 5 113 3 9 7 115 I 10 6 ',,I_,, 12 L 8 o

-exp~jfT.n~= - e x p l j e . nI = -expljff.141 -exp(jE.2)
-exp(j!f.15) -exp(jfb.131

Fig. 9. Complex FFT signal-flow graph corresponding to the filter in Fig. 7; N = 16. Branches with gains which are not +1
or -1 are shown as dotted lines. For the coefficients F1, F,, . . . see the table Fig. 8.

lcost

ICOS)

4 i V +1 t icosl

Isin I

IC 0 st

ls~nl

(cost

lsint

(cos)

lsln)

lcost

Islnl

~ 2.'- 1
(cost

(sin1
L
icosl

ls~nt

Fig. 10. Filtertreeforreal signalcos/sin DFT; N = 16. AU filter

coefficients are real.

VIII. THE NUMBERO F MULTIPLIERS FOR THE complex numbers. The new algorithm uses the same number
NEW FFT ALGORITHMS of multiplications, but each multiplication is now the product
The FFT algorithm developed in Section VI uses Nlog, N of one real and one complex number. Ifwe decompose the
arithmetic operations, which is the same as for the classical multiplications into real multiplications, we thus find a reduc-
FFT. tion by a factor of 2 for the new algorithm as compared to the
The classical FFT uses asymptotically (N/2)log, N complex conventional; the figures are Nlog, Nversus 2 Nlog, N .
multiplications, each multiplication being theproduct of two For the real FFT discussed in Section VII, wehave (N/2)
BRUUN: DFT FILTERS AND FFT’S 63

1 5 1 L 1 3 1 2 11 10 9 8 7 6 5 4 3 2 I O

n : 5 5 3 3 7 7 1 1 6 6 2 2 L 4 8 0
cos cos cos cos COS cos cos cos cos
sin sin sin sin sin sin sin

Fig. 11. Realsignalcos/sin FFT signal-flowgraphcorresponding to

the fiiter in Fig. 8 ; N = 16. All filter coefficients are real.

log, N real multiplications, or a reduction by a factor of 2 FFT withonly real coefficients. Thenew FFT algorithms
relative to the algorithmofSection VI.Using theconven- only use half as many real multiplications as the classical type
tional complex FFT for real numbers,it isalsopossible to of FFT.
obtain a reduction in thenumber of multiplicationsbya
factor 2.‘ Thenumber ofreal multiplications will then be ACKNOWLEDGMENT
Nlog, N which is still twice as many as for the algorithm of The author wishes to express his thanks to his colleagues for
Section VII. suggestions for the editing of this paper.Specialthanks are
Sometimes one wishes to decompose an FFT for complex due to P. G. Thomsen of the Institute for NumericalAnalysis,
numbers into two parts so that the transform of the real part Technical University of Denmark, for helpful discussions, and
of the N values is calculated before the imaginary
- _ -partis dealt to two unknown reviewers for suggestions and corrections.
with. This procedure may be performed in a very simple way
by using thealgorithmofSectionVI twice. Note thatthis REFERENCES
calculationcan be madewithoutany increase in thetotal [ l ] J. W. Cooley and J. W. Tukey, “An algorithm for the machine
number of real multiplications. calculationofcomplexFourierseries,” Math. Comput., vol. 19,
pp. 297-301,1965.
CONCLUSION P I W. T.Cochran et al., “What is the fast Fourier transform?” IEEE
Trans.Audio Electroacoust., vol. AU-15, pp. 45-55, June 1967.
In this paper wehave shown how the DFT canbe repre- [3l B. Gold and C. M. Rader, DigitalProcessingof Signals. NewYork:
McGraw-Hill, 1969.
sentedby a coefficient savingdigitalor analogtypeof delay [41 L. R. Rabiner and B. Gold, Theory and Application of Digital
filter. Furthermore,the direct relationship betweensuch a Signal Processing. Englewood Cliffs, NJ: Prentice-Hall, 1975.
filter representing the complexDFTandthe classical FFT is [SI A. V. Oppenheim and R. W. Schafer, Digital Sigma1 Processing.
Englewood Cliffs, NJ: Prentice-Hall, 1975.
shown.Atypeof radix-2 DFT filter is developed which [6] A. V. Aho, J. E. Hopcroft,andJ. D. Ullman, The Designand
utilizes a minimum of complex coefficients. This fiter leads Analysis of Computer Algorithms. Reading, MA: Addison-Wesley,
to a new type of complex FFT and to a type of real-signal 1974.
r71 J. W. Cooley, P. A. W. Lewis, and P. D. Welch, “The fast Fourier
transform algorithm: Programming considerations in the calcula-
‘Thisimpliesusinga methodproposedbyCooley et al. (seePro- tion of sine,cosineandLaplacetransforms,” J. Sound Vib.,
cedure 4 in [7]). vol. 12, no. 3, pp. 315-337, 1970.