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.

Description

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

Tags

Transcript

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 computationallyefﬁcient 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 efﬁcient 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: akansu@njit.edu).Color versions of one or more of the ﬁgures in this paper are available onlineat http://ieeexplore.ieee.org.Digital Object Identiﬁer 10.1109/TSP.2010.2050882
correlations of the set. More recently, research has refocusedon constant modulus spreading codes for radio communicationsapplications due to the efﬁciency limitations of non-linear gaincharacteristics of commonly used power ampliﬁers 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 uniﬁed 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 deﬁned 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, deﬁne a periodic, constant modulus, complex sequenceas the th
power
of the ﬁrst
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 ﬁnite discrete-time interval ina geometric series is expressed according to (3) as follows [10],[11]:(5)Then, (5) is rewritten as the deﬁnition of the discrete Fouriertransform (DFT) set satisfying the orthonormalitycon-ditions(6)The notation represents the complex conjugate function of afunction. One might rewrite the ﬁrst primitive Nth root of unityas where , and it is called
the funda-mental frequency
deﬁned in radians. We are going to extendthe phase functions in (6) in order to deﬁne 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 deﬁned as(8)We call this orthogonal function set as the
Generalized DiscreteFourier Transform
(GDFT). It is observed from (7) and (8) thatthereareinﬁnitelymanysetsofconstantmodulusand
nonlinear phasefunctions
available.Therefore,wemightmethodicallyde-sign such functions. As an example, one can deﬁne 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 deﬁned as follows:(10)In general, the polynomial coefﬁcients 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:
ThereareinﬁnitelymanypossibleGDFTsetswithconstant 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 ﬁgureof 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 ﬂexibilityof 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 deﬁne the DFT matrix of size as(11)Now, we will deﬁne 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 areefﬁcient toimplementwith simple modiﬁcations to the celebrated fast Fourier trans-form (FFT) algorithms.
Single Diagonal Matrix:
The diagonal matrix is con-stant modulus and deﬁned 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 deﬁned 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 efﬁcient 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 deﬁned 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 deﬁnes 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 deﬁned for the complexsequences and [18],(21)Out-of-phase auto-correlation sequence of the complex se-quence is deﬁned also from (21) as the absolute sequenceof as . Similarly, out-of-phase cross-corre-lation of two complex sequences and is deﬁned 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 deﬁned, 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 signiﬁcance in the orthogonality requirements of (7). Notethat there are inﬁnitely many possibilities for in(30) and, generally speaking, it might be linear or non-linearfunction of time. The GDFT framework offers us the ﬂexibilityto deﬁne 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 deﬁned as(31)where ; fortheidealcase,andimplies the orthogonality of the function pair. Similarly, we candeﬁnetheauto-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 ﬁrst 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 ﬁrst 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

Similar documents

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