Generalized discrete Fourier transform with nonlinear phase


of 10
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Constant modulus transforms like discrete Fourier transform (DFT), Walsh transform, and Gold codes have been successfully used over several decades in several engineering applications, including discrete multi-tone (DMT), orthogonal frequency
  IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 58, NO. 9, SEPTEMBER 2010 4547 Generalized Discrete Fourier TransformWith Nonlinear Phase Ali N. Akansu  , Fellow, IEEE  , and Handan Agirman-Tosun  Abstract— Constant modulus transforms like discrete Fouriertransform (DFT), Walsh transform, and Gold codes have beensuccessfully used over several decades in several engineeringapplications, including discrete multi-tone (DMT), orthogonal fre-quency division multiplexing (OFDM) and code division multipleaccess(CDMA)communicationssystems.Inthispaper,wepresentageneralizedframeworkforDFTcalledGeneralizedDFT(GDFT)with nonlinear phase by exploiting the phase space. We show thatGDFT offers sizable correlation improvements over DFT, Walsh,Oppermann and Gold codes, leading to better performance inall multi-carrier communications scenarios investigated. We alsohighlight how known constant modulus orthogonal transformsarespecial solutionsoftheproposedGDFTframework.Moreover,we introduce practical design methods offering computationallyefficient implementations of GDFT as enhancements to DFT. Weconclude thepaper with examplesof communicationsapplicationswhere GDFT is shown to outperform DFT and other knownconstant modulus bases.  Index Terms— Auto-correlation function, CDMA, cross-correla-tion function, discrete Fourier transform, DMT, generalized dis-crete Fourier transform, Gold codes, OFDM, Walsh codes. I. I NTRODUCTION C ONSTANT modulus function sets have always been of great interest in various applications including commu-nications where efficient implementation is a major concern.Amongknownbinaryspreadingcode families,Goldcodeshavebeen successfully used for asynchronous communications indirect sequence CDMA (DS-CDMA) systems due to their lowcross-correlation features. Walsh, Gold, Walsh-like [1]–[3]and several other binary spreading code sets are designed tooptimize so called even correlation functions. However, the oddcorrelations are as important as even correlations. Therefore,Fukumasa, Kohno and Imai proposed a new set of complexpseudo-randomnoise(PN)sequences,calledequaloddandeven(EOE)sequences,withgoododdandevencorrelations[4].EOEsequencesaregeneratedbyusingoneofthebinarycodesetslikeGoldorWalsh.Spreading codes with non-binary real chip values were alsoproposed in the literature in order to improve auto- and cross- Manuscript received May 08, 2009; accepted May 12, 2010. Date of publi-cation May 20, 2010; date of current version August 11, 2010. The associateeditor coordinating the review of this manuscript and approving it for publica-tionwasProf.ThierryBlu.ThispaperwaspresentedinpartsattheIEEESarnoff Symposium, Princeton, NJ, March 2009, at the EUSIPCO, Glasgow, U.K., Au-gust 2009, and at the IEEE International Conference on Acoustics, Speech andSignal Processing (ICASSP), Dallas, TX, March 2010.TheauthorsarewiththeDepartmentofElectricalandComputerEngineering,New Jersey Institute of Technology, University Heights, Newark, NJ 07102USA (e-mail: versions of one or more of the figures in this paper are available onlineat Object Identifier 10.1109/TSP.2010.2050882 correlations of the set. More recently, research has refocusedon constant modulus spreading codes for radio communicationsapplications due to the efficiency limitations of non-linear gaincharacteristics of commonly used power amplifiers in trans-ceivers. Hence, the complex roots of unity are widely proposedas complex spreading codes by several authors in the litera-ture. All codes of such a set are placed on the unit circle of thecomplex plane. Frank–Zadoff, Chu and Oppermann have for-wardedavarietyofcomplexspreadingcodes[5]–[8].Moreover,Oppermann has shown that Frank–Zadoff and Chu sequencesare special cases of his family of spreading sequences [9].This paper introduces generalized discrete Fourier transform(GDFT) with nonlinear phase. GDFT provides a unified theo-retical framework where popular constant modulus orthogonalfunction sets including DFT and others are shown to be spe-cial solutions. Therefore, GDFT provides a foundation to ex-ploit the phase space in its entirety in order to improve cor-relation properties of constant modulus orthogonal codes. Wepresent GDFT and demonstrate its improved correlations overthe popular DFT, Gold, Walsh and Oppermann families leadingto superior communications performance for the scenarios con-sidered in the paper.II. M ATHEMATICAL  P RELIMINARIES An root of unity is a complex number satisfying thepolynomial equation(1)Moreover, is defined as the  primitive root of unity if , where and must becoprime integers. The complex number is theprimitive th root of unity with the smallest positive argument.There are N distinct th roots of unity for any primitive andexpressed as(2)where is any of the  primitive  th  root of unity . As an ex-ample, and are the two primitiveNth roots of unity for . All  primitive  th  roots of unity satisfy the unique summation property of a geometric series ex-pressed as follows:(3)Now, define a periodic, constant modulus, complex sequenceas the th  power   of the first  primitive  th  root of unity 1053-587X/$26.00 © 2010 IEEE  4548 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 58, NO. 9, SEPTEMBER 2010 raised to the  power   as(4)The complex sequence (4) over a finite discrete-time interval ina geometric series is expressed according to (3) as follows [10],[11]:(5)Then, (5) is rewritten as the definition of the discrete Fouriertransform (DFT) set satisfying the orthonormalitycon-ditions(6)The notation represents the complex conjugate function of afunction. One might rewrite the first primitive Nth root of unityas where , and it is called  the funda-mental frequency  defined in radians. We are going to extendthe phase functions in (6) in order to define the nonlinear phaseGDFT in the following section.III. G ENERALIZED  D ISCRETE  F OURIER  T RANSFORM Let us generalize (5) by rewriting the phase as the differenceof two functions , and ex-pressing a constant modulus orthogonal set as follows,(7.a)Therefore, by inspection(7.b)Hence, the basis functions of the new set are defined as(8)We call this orthogonal function set as the  Generalized DiscreteFourier Transform  (GDFT). It is observed from (7) and (8) thatthereareinfinitelymanysetsofconstantmodulusand nonlinear  phasefunctions available.Therefore,wemightmethodicallyde-sign such functions. As an example, one can define the discretetime function in (8) as the ratio of two polynomials,(9)Note that any function pair must satisfy the or-thogonalityrequirementsof , as stated in (7).Let us assume that the denominator polynomialand the numerator polynomial is defined as follows:(10)In general, the polynomial coefficients and arecomplex, the powers and are real numbers. Now,we make several remarks that link the proposed GDFT frame-work to the other known transforms in the literature, and itspotential impact on a multicarrier communications system.  Remark 1:  DFT is a special solution of GDFT whereand , andin (9) and (10) for all . Notethat having constant valued functions for all makesDFT a linear-phase transform where.  Remark2:  ThereareinfinitelymanypossibleGDFTsetswithconstant modulus available due to the introduction of the non-linear phase as formulated in (10) and later in (30). Therefore,one can design the optimal basis (phase) for the desired figureof merit. As an example, if the application at hand requires afunction set with minimized correlation and does not mind thelinearity of phase, naturally, DFT is not the optimal solution forthisspecs.OnemightexploitthephasetodesignvariousGDFTswhere CDMA and OFDM performances in a multicarrier com-munications system might be improved over the existing solu-tions like discrete-time Walsh transform and DFT.  Remark 3:  Since DFT is a special solution of GDFT, it offersonly one unique set to be used in a multicarriercommunicationssystem. Therefore, the carrier level (physical layer) security isvulnerable to a potential intrusion to the system. In contrast,  AKANSU AND AGIRMAN-TOSUN: GENERALIZED DISCRETE FOURIER TRANSFORM WITH NONLINEAR PHASE 4549 the proposed GDFT provides many possible constant moduluscarrier sets of various lengths with comparable or better cor-relation performance than the DFT. The additional flexibilityof changing phase functions of the GDFT set allows us to de-signadaptivesystemswherecarrierallocationsandbasisassign-ments (basis hopping) are made dynamically in order to bettermatch channel spectrum as well as for improved physical layersecurity. The phase shaping function of (30) behaves asthe security key of the system and is known in advance by thereceiver.IV. GDFT D ESIGN  M ETHODS Let us define the DFT matrix of size as(11)Now, we will define a GDFT by relaxing the linear phase prop-erty of DFT without compromising the orthogonality. This is amarkeddeparturefromthetraditionalFourieranalysisincludingDFT where any set regardless continuous or discrete in time hasits linear phase functions. Hence, we express the square GDFTmatrix as a product of the three orthogonal matrices as follows(12)where and are constant modulus diagonal matrices andwritten as follows:(13.a)and(13.b)The notation indicates that conjugate and transpose oper-ations applied to the matrix, and is the  identity matrix  . There-fore, the transform kernel generating matrix throughthis methodology is expressed as follows:(14)and are the diagonal complex orthogonal  generalizationmatrices  yielding in (12) with the desired time and fre-quency domain features. Note that allows us to phase shiftDFT basis function by while adds the nonlinearphase terms, , to the linear phasefunctions of the DFT set. The latter is independent of the func-tion index and will be discussed in detail in Section V. We aregoing to introduce several generalization matrix families thatare useful to design out of . GDFT extensionswithdiagonalgeneralization matrices areefficient toimplementwith simple modifications to the celebrated fast Fourier trans-form (FFT) algorithms. Single Diagonal Matrix:  The diagonal matrix is con-stant modulus and defined from (12)(15)offering two types of GDFT matrices as follows. a) Constant valued diagonal elements:  The elements of this diagonal matrix are the same constant modulus complexnumber as expressed in(16)This type of matrix generates radians phase shifted versionoftheDFTmatrix.Moreover,thelinearphasepropertyof is still preserved in this case. This is a well known property of traditional Fourier analysis and included here for the complete-ness of presentation [12], [13]. b) Non-constant diagonal elements:  The non-zero, non-constant and constant modulus diagonal elements of matrixare defined as(17)The rows-basis functions of in (12) are obtained as theelement by element products of rows with the elementsof diagonal matrix in this scenario. Each sample of a basisfunction in is phase shifted independently of the othersamples. Therefore, the resulting basis function set is entirelydifferent from DFT set. One might design a linear phase-phaseshifted version of DFT- or nonlinear phase GDFT by designingelementsofthediagonal matrix, .ThisformofGDFTis further studied in Section V for the design of phase shapingfunction where .The overallcomputational burden of is the combinedimplementation cost of the and the matrices. SinceDFT has its efficient fast algorithms, FFT, the complexity of matrix indicates the required additional computational re-sources to implement GDFT. Therefore, this point needs to befurther studied in applications where one might generalize DFTinto GDFT as presented in this section.  Remark 4:  Oppermann forwarded a new group of constantmodulus orthogonal spreading codes, and also showed in [9]that the well-known Frank–Zadoff and Chu sequences [5]–[7]are the special cases of his code family. It is shown below thatthe orthogonal Oppermann codes are also special solutions tothe proposed GDFT framework. The Oppermann codes in ansquare matrix notation are defined as [8], [9](18)  4550 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 58, NO. 9, SEPTEMBER 2010 In [8], it was proven that Oppermann codes are orthogonal onlyfor the case of and is any positive nonzero integer.Note that if one defines the parameters of (10) for this case asand(19)Then, we obtain the equality .As an example, for the Oppermann set of withthe parameters is expressedas (20), shown at the bottom of the page.  Remark5:  Theterm GeneralizedDFT  wasalsousedbyotherauthors [14]–[19]. Their focus was only on linear phase sets.Therefore, the non-linear phase GDFT is the superset of thosetechniques. Note that any linear phase extensions of DFT yieldthe same auto- and cross correlation performance as DFT, andhence provide no enhancements of these metrics.V. D ESIGN AND  P ERFORMANCE OF  G ENERALIZED  DFT  A. Performance Metrics Inordertocompareperformanceofcodefamilies,severalob- jective performance metrics were used in the literature. All themetrics used in this study depend on aperiodic correlation func-tions (ACF) of the spreading code set. The ACF metricis defined for the complexsequences and [18],(21)Out-of-phase auto-correlation sequence of the complex se-quence is defined also from (21) as the absolute sequenceof as . Similarly, out-of-phase cross-corre-lation of two complex sequences and is defined asthe absolute function of and expressed with .In this paper, the following correlation metrics are used foroptimal GDFT design and performance comparisons of variouscode families [20] where is the set size and is the lengthof each spreading code.a. Maximum Value of Out-of-Phase Auto-Correlation, :(22)b. MaximumValueofOut-of-PhaseCross-Correlation, :(23)(24)The relationship between the maximum out-of-phaseauto-correlation and the maximum out-of-phasecross-correlation was shown by Sarwate in [21]:(25)and leading to the Welch bound for complex spreadingsequences expressed as [22](26)c. Mean-Square Value of Auto-Correlation, :(27)d. Mean-Square Value of Cross-Correlation, :(28)e. The merit factor : The merit factor for the codeis the ratio of the energy in the main lobe of the auto-correlation function over the total energy in its side lobesand mathematically expressed as [23](29)InCDMAcommunicationssystems,meritfactorisdesiredtobeaslargeaspossibleinordertoimprovethecodesynchronizationand amiability [23].  B. Phase Shaping Function and Optimal Design The phase shaping function is formally defined, and itsoptimal design based on a performance metric is presented in(20)  AKANSU AND AGIRMAN-TOSUN: GENERALIZED DISCRETE FOURIER TRANSFORM WITH NONLINEAR PHASE 4551 this section.Thephase function of(8) is now decom-posed into two functions in the time variable as follows:(30)The linear term of phase function in (30) is highlighted dueto its significance in the orthogonality requirements of (7). Notethat there are infinitely many possibilities for in(30) and, generally speaking, it might be linear or non-linearfunction of time. The GDFT framework offers us the flexibilityto define the phase shaping function according to the de-sign requirements. Note that any function will give us anorthogonal GDFT set as stated in (8) and (30).Thecross-correlationsequenceofaGDFT basisfunctionpair  with length N is defined as(31)where ; fortheidealcase,andimplies the orthogonality of the function pair. Similarly, we candefinetheauto-correlationfunctionofaGDFTbasisfunctionas(32)where for the ideal case. The correlationsequenceofabasispairisincorporatedin and metricsof (27) and (28), respectively, in the following design example.Now, we focus on the optimal design of the phase shapingfunction, , by utilizing a performance metric. Since thereis nooptimalclosedformsolutionfor ,weused thenumer-ical optimization software tools in Mathematica and MATLABto obtain optimal phase shaping functions of (30) with respectto the metrics of (27) and (28). Note that the entire set usesthe same phase shaping function and there arebasisfunctionpairsinasetofsizeNtobeconsid-ered in the design of an optimum yielding the best cross-correlation performance. Similarly, any basis function mighthave its own optimal phase shaping function optimizing theauto-correlation sequence. Therefore, one needs to pick the se-quence providing the best auto-correlation for the entire set asthe phase shaping function.Fig.1(a)and(b)displaystheoptimalphaseshapingfunctionswhich minimize the correlation metrics and , respec-tively, for the first two functions of the GDFT with size .The resulting and values for these optimal GDFT de-signs are tabulated in Table I along with their DFT counterpartsfor comparison purposes. Fig. 1. Optimal phase shaping functions minimizing the correlation metrics:(a)    and (b)    for the first two functions of GDFT set with      .TABLE I   AND    V ALUES FOR THE  F IRST  T WO  F UNCTIONS OF  O PTIMAL  GDFTS ETS  W ITH      A LONG  W ITH  T HEIR  DFT C OUNTERPARTS Note the consistency of the two numerical search tools, andthe improvements in correlation metrics and areshown in this table. The optimal design method explained inthis section can be generalized for any performance metric and
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks