it.FastFouriertransformalgorithmsabound,includingdecimation-in-time(D-I-T)algorithms,
decimation-in-frequency(D-I-F)algorithms,bit-reversedalgorithms,normallyorderedalgorithms,
mixed-radixalgorithms(forblocklengthsthatarenotpowersof2),primefactoralgorithms,and
Winogradalgorithms[7].TheD-I-TandtheD-I-Fradix-2FFTalgorithmsarethemostwidelyused
inpractice.DetaileddiscussionsofvariousFFTalgorithmscanbefoundin[3,6,7],and[10].
TheFFTiseasilyunderstoodbyexaminingthesimpleexampleofN=8.TheFFTalgorithmcan
bedevelopedinnumerousways,allofwhichdealwithanesteddecompositionofthesummation
operatorof(1.20a).Thedevelopmentpresentedhereiscalledanalgebraicdevelopmentofthe
FFTbecauseitfollowsstraightforwardalgebraicmanipulation.First,thesummationindices(k,n)
in(1.20a)areexpressedasexplicitbinaryintegers,k=k
2
4+k
1
2+k
0
andn=n
2
4+n
1
2+n
0
,
wherek
i
andn
i
arebitsthattakeonthevaluesofeither0or1.Iftheseexpressionsaresubstituted
into(1.20a),alltermsintheexponentthatcontainthefactorN=8canbedeletedbecause
e
−j2πl
=1foranyintegerl.Upondeletingsuchtermsandregroupingtheremainingterms,the
productnkcanbeexpressedineitheroftwoways:
nkψ =← (4k
0
)n
2
+(4k
1
+2k
0
)n
1
+(4k
2
+2k
1
+k
0
)n
0
(1.25a)
nkψ =← (4n
0
)k
2
+(4n
1
+2n
0
)k
1
+(4n
2
+2n
1
+n
0
)k
0
(1.25b)
Substituting(1.25a)into(1.20a)leadstotheD-I-TFFT,whereassubstituting(1.25b)leadstothe
D-I-FFFT.OnlytheD-I-TFFTisdiscussedfurtherhere.TheD-I-Fandvariousrelatedformsare
treatedindetailin[6].
TheD-I-TFFTdecomposesintolog
2
Nstagesofcomputation,plusastageofbitreversal,
x
1
[k
0
,n
1
,n
0
]=
1
X
n
2
=0
s[n
2
,n
1
,n
0
]W
4k
0
n
2
8
(stage1) (1.26a)
x
2
[k
0
,k
1
,n
0
]=
1
X
n
1
=0
x[k
0
,n
1
,n
0
]W
(4k
1
+2k
0
)n
2
8
(stage2) (1.26b)
x
3
[k
0
,k
1
,k
2
]=
1
X
n
0
=0
x[k
0
,k
1
,n
0
]W
(4k
2
+2k
1
+k
0
)n
0
8
(stage3) (1.26c)
S[k
2
,k
1
,k
0
]=x
3
[k
0
,k
1
,k
2
]← (bitreversal) (1.26d)
Ineachsummationaboveoneofthen
i
issummedoutoftheexpression,whileatthesametimeanew
k
i
isintroduced.Thenotationischosentoreflectthis.Forexample,instage3,n
0
issummedout,
k
2
isintroducedasanewvariable,andn
0
isreplacedbyk
2
intheresult.Thelastoperation,called
bitreversal,isnecessarytocorrectlylocatethefrequencysamplesX[k]inthememory.Itiseasyto
showthatifthesamplesarepairedcorrectly,anin-placecomputationcanbedonebyasequenceof
butterflyoperations.Theterm“in-place”meansthateachtimeabutterflyistobecomputed,apair
ofdatasamplesisreadfrommemory,andthenewdatapairproducedbythebutterflycalculation
iswrittenbackintothememorylocationswheretheoriginalpairwasstored,therebyoverwriting
theoriginaldata.Anin-placealgorithmisdesignedsothateachdatapairisneededforonlyone
butterfly,andthusthenewresultscanbeimmediatelystoredontopoftheoldinordertominimize
memoryrequirements.
Forexample,instage3thek=6andk=7samplesshouldbepaired,yieldinga“butterfly”
computationthatrequiresonecomplexmultiply,onecomplexadd,andonesubtract:
c
1999byCRCPressLLC