分数域信号与信息处理及其应用 (25).pdf

1338IEEE TRANSACTIONS ON SIGNAL PROCESSING,VOL.48,NO.5,MAY 2000Closed-Form Discrete Fractional and Affine FourierTransformsAbstractThe discrete fractional Fourier transform(DFRFT)is the generalization of discrete Fourier transform.Many typesof DFRFT have been derived and are useful for signal processingapplications.In this paper,we will introduce a new type ofDFRFT,which are unitary,reversible,and flexible;in addition,the closed-form analytic expression can be obtained.It worksin performance similar to the continuous fractional Fouriertransform(FRFT)and can be efficiently calculated by FFT.Sincethe continuous FRFT can be generalized into the continuous affineFourier transform(AFT)(the so-called canonical transform),wealso extend the DFRFT into the discrete affine Fourier transform(DAFT).We will derive two types of the DFRFT and DAFT.Type1 will be similar to the continuous FRFT and AFT and can beused for computing the continuous FRFT and AFT.Type 2 is theimproved form of type 1 and can be used for other applications ofdigital signal processing.Meanwhile,many important propertiescontinuous FRFT and AFT are kept in closed-form DFRFT andDAFT,and some applications,such as the filter design and patternrecognition,will also be discussed.The closed-form DFRFT weintroduce will have the lowest complexity among all currentDFRFTs that are still similar to the continuous FRFT.Index TermsAffine Fourier transform,discrete affine Fouriertransform,discrete Fourier transform,discrete fractional Fouriertransform,Fourier transform.I.INTRODUCTIONTHE continuous fractional Fourier transform(FRFT)1,2,which is the generalization of Fourier transform,isdefined as(1)where the phase ofis constrained in the range of.It has been discussed in recent years and used inmany applications such as optical system analysis,filter design,soluiton of differential equations,phase retrieval,pattern recog-nition,etc.The continuous FRFT satisfies the additivity prop-erty as(2)Manuscript received January 15,1999;revised November 20,1999.Thiswork was supported by the National Science Council,R.O.C.,under ContractNSC89-2213-E-002-092.The associate editor coordinating the review of thispaper and approving it for publication was Prof.Chin-Liang Wang.The authors are with the Department of Electrical Engineering,NationalTaiwan University,Taipei,Taiwan,R.O.C.(e-mail:peicc.ee.ntu.edu.tw).Publisher Item Identifier S 1053-587X(00)03291-8.The FRFT has been further generalized into the special affineFouriertransform(SAFT)3(theso-calledcanonicaltransform4).It is defined aswhen(3)when(4)wheremust be satisfied.Special affine Fouriertransform has the additive property(5)whereand it has the reversible property(5a)We will call this special affine Fourier transform the affineFourier transform(AFT).The affine Fourier transform canextend the utilities of FRFT and is a useful tool for the opticalsystem analysis.The effect of the FRFT and AFT can beinterpreted by the Wigner distribution function(WDF).Afterdoing the FRFT,the WDF ofwill be the rotation ofthe WDF ofwith angle23,and after doing the AFT,the WDF ofwill be the twisting of the WDFof.After the continuous fractional Fourier transform has beenderived,many researchers have tried to derive their discretecounterpart,that is,the discrete fractional Fourier transform(DFRFT).WebrieflyreviewDFRFTsbelow.Thenameforeachtype of DFRFT is not recalled by the original authors.We givetheir names for easy classification.1)Direct form of DFRFT.The simplest way to derive theDFRFT is sampling the continuous FRFT and computingit directly,but when we sample the continuous FRFTdirectly,then the resultant discrete transform we obtainwill lose many important properties.The most seriousproblem is the DFRFT of this type will not be unitary andreversible.Besides,lacks closed-form properties,and notadditive,so its applications are very limited.2)Improved sampling-type DFRFT.In 5,a way to samplethecontinuousFRFTproperlyisintroduced,andthen,theresultantDFRFTwillhavethesimilartransformresultsas1053587X/00$10.00 2000 IEEEPEI AND DING:CLOSED-FORM DISCRETE FRACTIONAL AND AFFINE FOURIER TRANSFORMS1339the continuous FRFT.Although,in this case,the DFRFTcan work very similarly to the continuous case and has afastalgorithm,butthetransformkernelwillnotbeorthog-onal and additive.Besides,many constraints,includingthe input signal constraint,should be satisfied.3)Linearcombination-typeDFRFT.In68,and24,thediscrete fractional Fourier transform is derived by usingthe linear combination of identity operation,DFT,timeinverse operation,and IDFT.In this case,the transformmatrix is orthogonal,and the additivity property and thereversibility property will satisfy for this type of DFRFT.However,the main problem is that the transform resultswill not match to the continuous FRFT.Besides,it willwork very similarly to the original Fourier transform orthe identity operation and lose the important character-istic of“fractionalization.”4)Eigenvectors decomposition-type DFRFT.In 911,and 16,the authors derive another type of discrete frac-tional Fourier transform by searching the eigenvectorsand eigenvalues of the DFT matrix and then compute thefractional power of the DFT matrix.This type of DFRFTwill work very similarly to the continuous FRFT andwill also have the properties of orthogonal,additivity,and reversibility.In 11,they have further improved thistype of DFRFT by modifying their eigenvectors moresimilarly to the continuous Hermite functions,which arethe eigenfunctions of the FRFT.These types of DFRFTslack the fast computation algorithm,and the eigenvectorscannot be written in a closed form.5)Group theory-type DFRFT.In 13,the concept of grouptheory 15 is used,and the DFRFT as the multiplicationof DFT and the periodic chirps are derived.The DFRFTderived will satisfy the rotation property on the Wignerdistribution,and the additivity and reversible propertywill also be satisfied.However,this type of DFRFT canbe derived only when the fractional order of the DFRFTequals some specified angles,and when the number ofpointsis not prime,it will be very complicated to de-rive.6)Impulse train-type DFRFT.Recently,in 14,anothertype of DFRFT is derived.This type of DFRFT can beviewed as a special case of the continuous FRFT.In thiscase,the input functionis a periodic,equally spacedimpulse train,and if the number of impulses in a periodis,and the period is,then.Besides,thevalue ofis limited and must be a rational number(is the order of FRFT).Because this type of DFRFTcan be viewed as a special case of continuous FRFT,many properties of the FRFT will also exist and have thefast algorithm.However,this type of DFRFT has manyconstraints and cannot be defined for all values of.Although many types of the discrete fractional Fourier trans-form(DFRFT)have been derived recently,no discrete affineFourier transform(DAFT)has yet been derived.In this paper,we will derive a new type of DFRFT,and thenextend it into the discrete affine Fourier transform(DAFT).TheDFRFT and DAFT we derived come from the proper samplingof the continuous FRFT and AFT.The DFRFT introduced in5 is also derived from the sampling of the continuous FRFT.Here,however,we will sample the continuous FRFT and affineFourier transform by some proper intervals,and therefore,thetransform matrix will be orthogonal and reversible.It can bewritten in the closed form so that many properties can be de-rived,and the fast algorithms can be achieved.Our idea comesfrom the 12 and 22.In these papers,when we sample thefractional Fourier transform properly,we will obtain an unitarytransform.We will improve upon these ideas.In this paper,our focus is on the practical applications.Thus,although our DFRFT/DAFT seem neat in concepts andsacrifice the additivity property,they are very suitable for thepractical applications due to the simpler and closed form ofdiscrete fractional convolution and correlation introduced inSection II-D and the advantages listed in Section II-E.OurDFRFT/DAFT will have the lowest complexity among all thecurrent the DFRFT/DAFTs that still have the similar propertiesas the continuous FRFT/AFT.Due to the orientation of practical usage,we will derive twotypes of DFRFT/DAFT.These two types of DFRFT/DAFT areessentially the same but different in parameterizations.The firsttype we derive has the parameters that are more directly linkedto the continuous FRFT/AFT and suits the applications of com-puting the continuous FRFT/AFT.On the other hand,type 2has the simpler parameters set and allows more elegant expres-sion for the operator kernels.It is suitable for other applicationsof DFRFT/DAFT,such as the filter design,pattern recognition(described in Section IV),and the use for the phase retrievaldiscussed in 12 and 22 can also be improved by the type 2DFRFT/DAFT proposed in this paper.In Section II,we will give the derivation and definitions ofour new types of DFRFT and DAFT.For different applications,we will use different parameterizations to define 2 types ofDFRFT/DAFT.In Section III,we will discuss their propertiesand their transform results for some special signals.In SectionIV,we discuss their applications.Finally,in Section V,wemake a conclusion.II.DERIVATION OFCLOSED-FORMDISCRETEFRACTIONALANDAFFINEFOURIERTRANSFORMSA.The Closed-Form Discrete Fractional Fourier Transformof Type 11)The Derivation:To derive the DFRFT,we first samplethe input functionand the output functionof theFRFT see(1)by the interval,as(6)where,and.Here,we do not start our sampling atand.Instead,we try to make the DC component in the center.From(6),we can convert(1)as(7)1340IEEE TRANSACTIONS ON SIGNAL PROCESSING,VOL.48,NO.5,MAY 2000Theaboveequationcanbewrittenastheformoftransformationmatrix(8)where(9)in order for(8)to be reversible.We will try to make the inversetransform to be the Hermitian(conjugation and transpose)ofwhen,i.e.,for(10)Then,from(8)and(9)(11)If we want the summation forin(11)to become,then(12)whereis some integer prime to.In this case,(9)becomes(13)and(14)Wethennormalizetosatisfy(11)andobtainthetrans-form matrixassgn(15)For simplicity,we can choosesgn,andrewrite(15)assgn(16)Then,we obtain the following two formulas of discrete frac-tional Fourier transforms(DFRFT)for 1)and 2)DFRFT of type 1:1)whenis integeri.e.,(17)2)whenis integeri.e.,(18)Additionally,the constraints thatare the number of pointsin the time,frequency domain(19)must also be satisfied.We note that whenand,(17)will become the DFT,and when,(18)will become the inverse DFT.We also notethat whenandis some integer,there is noproper choice forandthat satisfies this constraintof(15),and we cannot use(17)or(18)as the definitionof DFRFT when.In fact,in these cases,we canjust use the following definitions:3)when(20)4)when(21)Equations(17)(21)are the definition of the DFRFT.2)Some Important Discussion About the DFRFT of Type1:We also note,from(1)and(2),the inverse of the forwardcontinuous FRFT with orderis just the forward continuousFRFT with order.In fact,this property will also exist forthe DFRFT defined as(17)(21).Since,from(11),the inverseofis just its Hermitian,i.e.,and if we de-fineas(16),then we find(22)In the above equation,we notice that the sampling interval ofthe input(the second subscript)and the sampling interval ofthe output(the third subscript)are exchanged.Then,we canconclude that(23)thatis,theDFRFToforderwiththesamplingintervalinthe input andat the output will be the inverse of the DFRFTof orderwith the sampling intervalin the input andatthe output.This is the reversible property of the DFRFT of type1.PEI AND DING:CLOSED-FORM DISCRETE FRACTIONAL AND AFFINE FOURIER TRANSFORMS1341As the continuous FRFT,the DFRFT of type 1 also has theperiodic property,that is(24)The DFRFT of type 1 will have the period ofas the contin-uous FRFT.The DFRFTs of type 1 also have the conjugationproperty thatifis real(25)The rest important properties will be derived in the Section III.Although the DFRFT introduced here has no additivity prop-erty,it can be convertible,that is,we can convert the DFRFTwith some set of parameters into the DFRFT with another set ofparameters.Suppose we usefor the DFRFT with theparameterand usefor the DFRFT with the param-eter(The sampling interval in both time domains is the sameand fixed).Then,from(16),we findwhereis the DFT or IDFT of(26)In additionwhereis some integer such that(27)Therefore,we obtain(28)Although the DFRFTdefinedin(17)(21)hasno additiveprop-erty,ifwefix,thenwecanconvertthetransformresultoftheDFRFTwithorderintoorderbytwochirpmultiplicationsand one convolution operation.We note,in(19),that ifis very small,thenandmustalsobeverysmall,andthenumberofpointsmustincrease.This will increase the computation time of the DFRFT becausefor the continuous FRFTso whenis very small,we can first do the forward DFTfor the sampling ofand do the DFRFT defined as(17)or(18)with the order.Thus,we can change the DFRFTof type 1 to(29)where(29a)Then,becausefor the case thatis small,we can define the DFRFT asfollows.Modification form of the DFRFT of type 1 when(30)whereisthesameas(29a),andtheconstraintforbecomes(31)Whenis small,we can use(30)as the DFRFT.The DFRFT of type 1 has a very important advantage,that is,it is efficient to calculate and implement.Because there are twochirp multiplications and one FFT,the total number of the mul-tiplication operations required is,whereis the length of the output.Among all types ofDFRFT,the linear combination type DFRFT 68,24 willhavethe least complexity and only requiremulti-plication operations.However,it does not match the continuousFRFT and lacks many of the characteristics of the continuousFRFT.For example,it is hard to filter out the chirp noise withthistype ofDFRFT.Formost of theother types ofDFRFT,suchas the improved directly sampling-type DFRFT 5,we needmultiplication operations because there is oneconvolution operation and two chirp multiplication operationsrequired.The DFRFT we introduce will have the lowest com-plexity among all types of DFRFT that still work similarly tothe continuous FRFT.3)Applications for Calculating the Continuous FRFT:Wecan use the DFRFT of type 1 to calculate the continuous FRFT.When using the DFRFT for this application,we first sample theinput continuous function into a discrete sequence,do the for-ward DFRFT,and get the output of DFRFT as the sampling ofthe transform results of continuous FRFT.We note that becausewhen we derive the DFRFT of type 1,we have normalized the1342IEEE TRANSACTIONS ON SIGNAL PROCESSING,VOL.48,NO.5,MAY 2000unitaryfrom(14)to(15).Thus,whenusingtheDFRFToftype1toimplementthecontinuousFRFT,wemustconsiderthisnor-malization factor,that is,if(32)then(33)We will use some examples to discuss this.In Figs.1 and 2,we will give some examples to illustrate theapplicationofDFRFTforcalculatingthecontinuousFRFT.Theoriginal continuous input functions are:Fig.1:(rectangular)Fig.2:(triangular).Then,we sample the input function with the sampling intervalFig.1:(rectangular)Fig.2:and use the DFRFT of orderand.Th