Signals and Communication Technology For furthervolumes: http://www.springer.com/series/4748 . K.R. Rao D.N. Kim l l J.J. Hwang Fast Fourier Transform: Algorithms and Applications Dr.K.R.Rao Dr.D.N.Kim Univ.ofTexasatArlington Univ.ofTexasatArlington Electr.Engineering Electr.Engineering NeddermanHall NeddermanHall YatesSt.416 YatesSt.416 76013ArlingtonTexas 76013ArlingtonTexas USA USA [email protected] [email protected] Dr.J.J.Hwang KunsanNationalUniv. SchoolofElectron.&Inform. Engineering 68Miryong-dong 573-701Kunsan Korea,Republicof(SouthKorea) [email protected] ISSN1860-4862 ISBN978-1-4020-6628-3 e-ISBN978-1-4020-6629-0 DOI10.1007/978-1-4020-6629-0 SpringerDordrechtHeidelbergLondonNewYork LibraryofCongressControlNumber:2010934857 #SpringerScienceþBusinessMediaB.V.2010 Nopartofthisworkmaybereproduced,storedinaretrievalsystem,ortransmittedinanyformorbyany means, electronic, mechanical, photocopying, microfilming, recording or otherwise, without written permissionfromthePublisher,withtheexceptionofanymaterialsuppliedspecificallyforthepurpose ofbeingenteredandexecutedonacomputersystem,forexclusiveusebythepurchaserofthework. Coverdesign:SPiPublisherServices Printedonacid-freepaper SpringerispartofSpringerScienceþBusinessMedia(www.springer.com) Preface This book presents an introduction to the principles of the fast Fourier transform (FFT). It covers FFTs, frequency domain filtering, and applications to video and audiosignalprocessing. Asfieldslikecommunications,speechandimageprocessing,andrelated areas are rapidly developing, the FFT as one of the essential parts in digital signal processing has been widely used. Thus there is a pressing need from instructors andstudentsforabookdealingwiththelatestFFTtopics. This book provides a thorough and detailed explanation of important or up-to- date FFTs. It also has adopted modern approaches like MATLAB examples and projectsforbetterunderstandingofdiverseFFTs. FastFouriertransform(FFT)isanefficientimplementationofthediscreteFourier transform(DFT).Ofallthediscretetransforms,DFTismostwidelyusedindigital signal processing. The DFT maps a sequence either in the time domain or in the spatialdomainintothefrequencydomain.ThedevelopmentoftheDFToriginallyby Cooley and Tukey [A1] followed by various enhancements/modifications by other researchershasprovidedtheincentiveandtheimpetusforitsrapidandwidespread utilization in a number of diverse disciplines. Independent of the Cooley-Tukey approach, several algorithms such as prime factor, split radix, vector radix, split vectorradix,WinogradFouriertransform,andintegerFFThavebeendeveloped.The emphasis of this book is on various FFTs such as the decimation-in-time FFT, decimation-in-frequencyFFTalgorithms,integerFFT,primefactorDFT,etc. In some applications such as dual-tone multi-frequency detection and certain patternrecognition,theirspectraareskewedtosomeregionsthatarenotuniformly distributed. With this basic concept we briefly introduce the nonuniform DFT (NDFT), dealing with arbitrarily spaced samples in the Z-plane, while the DFT dealswithequallyspacedsamplesontheunitcirclewiththecenterattheoriginin theZ-plane. A number of companies provide software for implementing FFT and related basic applications such as convolution/correlation, filtering, spectral analysis, etc. on various platforms. Also general-purpose DSP chips can be programmed to implementtheFFTandotherdiscretetransforms. v vi Preface This book is designed for senior undergraduate and graduate students, faculty, engineers, and scientists in the field, and self-learners to understand FFTs and directly apply them to their fields, efficiently. It is designed to be both a text and a reference. Thus examples, projects and problems all tied with MATLAB, are providedforgraspingtheconceptsconcretely.Italsoincludesreferencestobooks andreviewpapersandlistsofapplications,hardware/software,andusefulwebsites. By including many figures, tables, bock diagrams and graphs, this book helps the readerunderstandtheconceptsoffastalgorithmsreadilyandintuitively.Itprovides newMATLABfunctionsandMATLABsourcecodes. Thematerialinthisbookispresentedwithoutassuminganypriorknowledgeof FFT.Thisbookisforanyprofessionalwhowantstohaveabasicunderstandingof thelatestdevelopmentsinandapplicationsofFFT.Itprovidesagoodreferencefor any engineer planning to work in this field, either in basic implementation or in researchanddevelopment. D.N.KimacknowledgesthesupportbytheNationalInformationTechnology(IT) Industry Promotion Agency (NIPA) and the Ministry of Knowledge Economy, RepublicofKorea,undertheITScholarshipProgram. Organization of the Book Chapter1introducesvariousapplicationsofthediscreteFouriertransform.Chapter2 is devoted to introductory material on the properties of the DFT for the equally spaced samples. Chapter 3 presents fast algorithms to be mainly categorized as decimation-in-time(DIT)ordecimation-in-frequency(DIF)approaches.Basedon these,itintroducesfastalgorithmslikesplit-radix,Winogradalgorithmandothers. Chapter 4 is devoted to integer FFT which approximates the discrete Fourier transform. One-dimensional DFT is extended to the two-dimensional signal and then to the multi-dimensional signal in Chapter 5. Applications to filtering are presented in this chapter. Variance distribution in the DFT domain is covered. It also introduces how we can diagonalize a circulant matrix using the DFT matrix. Fastalgorithmsforthe2-DDFTarecoveredinChapter6.Chapter7isdevotedto introductory material on the properties ofnonuniformDFT (NDFT) for the none- quallyspacedsamples.NumerousapplicationsoftheFFTarepresentedinChapter8. Appendix A covers performance comparison of discrete transforms. Appendix B covers spectral distance measures of image quality. Appendix C covers Integer DCTs. DCTs and DSTs are derived in Appendix D (DCT – discrete cosine transform, DST – discrete sine transform). Kronecker products and separability are briefly covered in Appendix E. Appendix F describes mathematical relations. Appendices G and H include MATLAB basics and M files. The bibliography contains lists of references to books and review papers, software/hardware, and websites.Numerousproblemsandprojectsarelistedattheendofeachchapter. Arlington,TX K.R.Rao August2010 Contents 1 Introduction ............................................................... 1 1.1 ApplicationsofDiscreteFourierTransform .......................... 2 2 DiscreteFourierTransform ............................................. 5 2.1 Definitions ............................................................. 5 2.1.1 DFT ............................................................. 5 2.1.2 IDFT ............................................................ 5 2.1.3 UnitaryDFT(Normalized) ..................................... 6 2.2 TheZ-Transform ....................................................... 7 2.3 PropertiesoftheDFT ................................................. 13 2.4 ConvolutionTheorem ................................................ 18 2.4.1 MultiplicationTheorem ....................................... 24 2.5 CorrelationTheorem .................................................. 24 2.6 Overlap-AddandOverlap-SaveMethods ............................ 27 2.6.1 TheOverlap-AddMethod ..................................... 27 2.7 ZeroPaddingintheDataDomain .................................... 31 2.8 ComputationofDFTsofTwoRealSequencesUsing OneComplexFFT .................................................... 32 2.9 ACirculantMatrixIsDiagonalizedbytheDFTMatrix ............ 34 2.9.1 ToeplitzMatrix ................................................ 34 2.9.2 CirculantMatrix ............................................... 34 2.9.3 ACirculantMatrixIsDiagonalizedbytheDFTMatrix ...... 35 2.10 Summary ............................................................. 37 2.11 Problems ............................................................. 37 2.12 Projects .............................................................. 40 3 FastAlgorithms .......................................................... 41 3.1 Radix-2DIT-FFTAlgorithm ......................................... 42 3.1.1 SparseMatrixFactorsfortheIFFTN¼8 .................... 46 3.2 FastAlgorithmsbySparseMatrixFactorization ..................... 47 vii viii Contents 3.3 Radix-2DIF-FFT ..................................................... 56 3.3.1 DIF-FFTN¼8 ................................................ 57 3.3.2 In-PlaceComputations ......................................... 61 3.4 Radix-3DITFFT ..................................................... 61 3.5 Radix-3DIF-FFT ..................................................... 63 3.6 FFTforNaCompositeNumber ...................................... 66 3.7 Radix-4DIT-FFT ..................................................... 67 3.8 Radix-4DIF-FFT ..................................................... 73 3.9 Split-RadixFFTAlgorithm ........................................... 75 3.10 FastFourierandBIFORETransformsbyMatrixPartitioning ..... 78 3.10.1 MatrixPartitioning .......................................... 78 3.10.2 DFTAlgorithm .............................................. 80 3.10.3 BT(BIFORETransform) ................................... 82 3.10.4 CBT(ComplexBIFORETransform) ....................... 82 3.10.5 DFT(SparseMatrixFactorization) ......................... 82 3.11 TheWinogradFourierTransformAlgorithm ....................... 83 3.11.1 Five-PointDFT .............................................. 83 3.11.2 Seven-PointDFT ............................................ 84 3.11.3 Nine-PointDFT ............................................. 85 3.11.4 DFTAlgorithmsforReal-ValuedInputData ............... 85 3.11.5 WinogradShort-NDFTModules ........................... 87 3.11.6 PrimeFactorMapIndexing ................................. 88 3.11.7 WinogradFourierTransformAlgorithm(WFTA) .......... 90 3.12 SparseFactorizationoftheDFTMatrix ............................ 92 3.12.1 SparseFactorizationoftheDFTMatrixUsing ComplexRotations .......................................... 92 3.12.2 SparseFactorizationoftheDFTMatrixUsing UnitaryMatrices ............................................. 94 3.13 UnifiedDiscreteFourier–HartleyTransform ....................... 97 3.13.1 FastStructureforUDFHT ................................ 101 3.14 Bluestein’sFFTAlgorithm ........................................ 104 3.15 RaderPrimeAlgorithm ........................................... 106 3.16 Summary ........................................................... 107 3.17 Problems ........................................................... 108 3.18 Projects ............................................................ 110 4 IntegerFastFourierTransform ....................................... 111 4.1 Introduction ......................................................... 111 4.2 TheLiftingScheme ................................................. 112 4.3 Algorithms .......................................................... 112 4.3.1 Fixed-PointArithmeticImplementation ...................... 117 4.4 IntegerDiscreteFourierTransform ................................ 119 4.4.1 Near-CompleteIntegerDFT .................................. 119 4.4.2 CompleteIntegerDFT ........................................ 121 4.4.3 EnergyConservation .......................................... 123 4.4.4 CircularShift .................................................. 123 Contents ix 4.5 Summary ............................................................ 125 4.6 Problems ............................................................ 126 4.7 Projects .............................................................. 126 5 Two-DimensionalDiscreteFourierTransform ....................... 127 5.1 Definitions .......................................................... 127 5.2 Properties ........................................................... 131 5.2.1 Periodicity .................................................... 131 5.2.2 ConjugateSymmetry ......................................... 131 5.2.3 CircularShiftinTime/SpatialDomain(PeriodicShift) ..... 133 5.2.4 CircularShiftinFrequencyDomain(PeriodicShift) ........ 133 5.2.5 SkewProperty ................................................ 135 5.2.6 RotationProperty ............................................. 135 5.2.7 Parseval’sTheorem ........................................... 135 5.2.8 ConvolutionTheorem ........................................ 136 5.2.9 CorrelationTheorem .......................................... 137 5.2.10 SpatialDomainDifferentiation ............................. 139 5.2.11 FrequencyDomainDifferentiation .......................... 139 5.2.12 Laplacian .................................................... 139 5.2.13 Rectangle .................................................... 139 5.3 Two-DimensionalFiltering ......................................... 140 5.3.1 InverseGaussianFilter(IGF) ................................. 142 5.3.2 RootFilter .................................................... 142 5.3.3 HomomorphicFiltering ....................................... 143 5.3.4 RangeCompression ........................................... 146 5.3.5 GaussianLowpassFilter ...................................... 148 5.4 InverseandWienerFiltering ....................................... 150 5.4.1 TheWienerFilter ............................................. 151 5.4.2 GeometricMeanFilter(GMF) ............................... 154 5.5 Three-DimensionalDFT ............................................ 156 5.5.1 3-DDFT ...................................................... 156 5.5.2 3-DIDFT ..................................................... 157 5.5.3 3DCoordinates ............................................... 157 5.5.4 3-DDFT ...................................................... 157 5.5.5 3-DIDFT ..................................................... 157 5.6 VarianceDistributioninthe1-DDFTDomain .................... 158 5.7 SumofVariancesUnderUnitaryTransformationIsInvariant .... 160 5.8 VarianceDistributioninthe2-DDFTDomain .................... 160 5.9 QuantizationofTransformCoefficientscanbeBased onTheirVariances .................................................. 162 5.10 MaximumVarianceZonalSampling(MVZS) ................... 166 5.11 GeometricalZonalSampling(GZS) .............................. 168 5.12 Summary ........................................................... 168 5.13 Problems ........................................................... 169 5.14 Projects ............................................................ 170