Optimization of Generalized Discrete Fourier Transform for CDMA

Optimization of Generalized Discrete Fourier Transform for CDMA

Vaishali Patil

Department of Electronics and Communication

Sri SatyaSai Institute of Science and Technology, Sehore M.P.

Prof Jaikaran Singh

Department of Electronics and Communication

Sri SatyaSai Institute of Science and Technology, Sehore M.P.

Prof MukeshTiwari Department of Electronics and Communication

Sri SatyaSai Institute of Science and Technology, Sehore M.P.

ABSTRACT

Generalized Discrete Fourier Transform (GDFT) with non-linear phase is a complex valued, constant modulus orthogonal function set. GDFT can be effectively used in several engineering applications, including discrete multi-tone (DMT), orthogonal frequency division multiplexing (OFDM) and code division multiple access (CDMA) communication systems. The constant modulus transforms lik e discrete Fourier transform (DFT), Walsh transform, and Gold codes have been successfully used in above mentioned applications over several decades. However, these transforms are suffering from low cross- correlation features. This problem can be addressed by using GDFT transform. This paper describes the optimization of Generalized Discrete Fourier Transform with Non-Linear Phase for code division multiple access (CDMA). We have also implemented Gold, Walsh and DFT codes. Their performance is analyzed and compared on the basis of various parameters such as Maximum Value of Out-of-Phase Auto-Correlation, Maximum Value of Out-of-Phase Cross-Correlation, Mean-Square Value of Auto-Correlation, Mean-Square Value of Cross- Correlation and merit factor. The result of simulation in the form o f co mparison of Bit-error-rate (BER) and Signal-to-noise (SNR) ratio for various spreading codes is presented.

Keywords

CDMA, Simu lation, Orthogonal, BER, SNR, corre lation

1. INTRODUCTION

   CDMA uses unique spreading codes to spread the baseband data before transmission. The signal is transmitted in a channel, which is below noise level. The receiver then uses a correlator to dispread the wanted

   signal, which is passed through a narrow band pass filter. Unwanted signals will not be dispread and will not pass through the filter. Codes take the form of a carefu lly designed one/zero sequence produced at a much higher rate than that of the baseband data. The rate of a spreading code is referred to as chip rate rather than bit rate. The concept of CDMA is based around the fact that a data sequence is mult iplied by a spreading code or sequence which increases the bandwidth of the signal. Then within the receiver the same spreading code or sequence is used to extract the required data. Only when the required code is used, does the required data appear fro m the signal. The process of e xtracting the data is called corre lation. When a code exactly the same as that used in the transmitter is used, then it is said to have a correlation of one and data is e xtracted. When a spreading code that does not correlate is used, then the data will not be extracted and a different set of data will appear. This means that it is necessary for the same spreading code to be used within the transmitter and receiver for the data to be extracted.

   1.1 CDMA CODE TYPES

   There are several types of codes that can be used within a CDMA system for providing the spreading function:

   PN codes: Pseudo-random number codes

   (pseudo-noise or PN code) can be generated very easily. These codes will sum to zero over a period of time. A lthough the sequence is deterministic because of the limited length of the linear shift register used to generate the

   sequence, they provide a PN code that can be used within a CDMA system to provide the

   spreading code required. They are used within many systems as there is a very la rge number that can be used.

   1

   A feature of PN codes is that if the same versions of the PN code are time shifted, then they become almost orthogonal, and can be used as virtually orthogonal codes within a CDMA

   system.

   Truly orthogonal codes: Two codes are said to be orthogonal if when they are mu ltip lied together the result is added over a period of time they sum to ze ro. For e xa mp le a codes 1 -1 -1 1 and 1 -1 1 -1 when multip lied together give 1 1 – 1 -1 which gives the sum ze ro. An exa mple of an orthogonal code set is the Walsh codes used within the IS95 / CDMA2000 system.

   Let {er(n)} be a periodic, constant modulus, comple x

   sequence which can be e xpressed as the rth power of the first primitive Nth root of unity z1 raised to the nth power as [1]

   (1)

   n = 0,1,2,……….., N -1 and r = 0,1,2,………………., N-1

   The comple x sequence (1) over a finite d iscrete-time interval in a geo metric series is e xpressed as follows [10],[11]:

   Among known binary spreading code families, Gold

   codes have been successfully used for asynchronous communicat ions in direct sequence CDMA (DS -CDMA)

   systems due to their lo w cross -correlation features.

   Walsh, Go ld, Wa lsh-like [3] and several other binary spreading code sets are designed to optimize so called

   even correlation functions. However, the odd correlations

   (2)

   are as important as even correlations. Therefore, Fuku masa, Kohno and Ima i proposed a new set of comple x pseudo-random noise (PN) sequences, called equal odd and even (EOE) sequences, with good odd and even correlations [4]. EOE sequences are generated by using one of the binary code sets like Go ld or Walsh.

   More recently, research has refocused on constant modulus spreading codes for radio communicat ions applications due to the efficiency limitations of non-linear

   Then, (2) is rewritten as the definition of the discrete Fourier transform (DFT) set {ek(n)} satisfying the orthonorma lity conditions

   gain characteristics of co mmonly used power a mp lifiers in transceivers. Hence, the comple x roots of unity are

   wide ly proposed as comple x spreading codes by several authors in the literature. All codes of such a set are placed on the unit circ le of the comp le x p lane. FrankZadoff, Chu and Oppermann have forwarded a variety of co mp le x spreading codes [5][8]. Moreover, Oppermann has shown that FrankZadoff and Chu sequences are special

   cases of his fa mily of spreading sequences [9]. This paper introduces generalized d iscrete Fourier

   transform (GDFT) with nonlinear phase. GDFT provides a unified theoretical fra me work where popular constant

   modulus orthogonal function sets including DFT and others are shown to be special solutions. Therefore,

   (3)

   GDFT provides a foundation to explo it the phase space in its entirety in order to improve correlat ion properties of constant modulus orthogonal codes. We present GDFT and demonstrate its improved correlations over the popular DFT, Go ld, Walsh and Oppermann fa milies leading to superior communicat ions performance for the scenarios considered in the paper.

2. DISCRETE FOURIER TRANS FORM (DFT)

   The notation (*) represents the comple x conjugate

   function of a function. One might rewrite the first primitive Nth root of unity as where , and it is called the fundamental frequency defined in radians. We are going to extend the phase functions in (3) in order to define the nonlinear phase GDFT in the fo llo wing section.

3. GEN ERALIZED DISCRET E FOURIER TRANS FORM (GDFT)

   (10)

   Let us generalize (2) by re writ ing the phase as the diffe rence of two functions

   and expressing a constant modulus orthogonal set as follows,

   The otation indicates that conjugate and transpose operations applied to the matrix, and is the identity matrix. Therefore, the transform kernel generating A GDFT matrix through this methodology is expressed as follows:

   (11)

   Therefore, by inspection

   (4)

   (5)

   4.1 ALGORITHM

   S tep 1) Find N X N DFT

   k,n=0,1,,N-1

   S tep 2) Find G1 & G2

   Hence, the basis functions of the new set are defined as

   (6)

   We call th is orthogonal function set as the Generalized Discrete Fourier Transform (GDFT).

4. GDFT DES IGN MET HODS

   Step 3) Calculate GDFT

   (7)

   The square GDFT matrix as a product of the three orthogonal matrices as follows

   ,

   ,

   (8)

   Where G1 and G2 are constant modulus diagonal matrices and written as follows:

   (9)

   and

   Step 4) Find dam, dcm, dmax, RAC, RCC, F

   1. Maximum value of out-of-phase Auto- correlation:

   2. Maximum value of out-of-phase Cross- correlation:

   3. Mean squa re Value of Auto-Correla tion,RAC.

   4. Mean squa re Value of Cross-Correla tion,RCC

   5. The Meri t Fa ctor.

      S tep 5) S imulate using AWGN S tep 6) Plot BER vs S NR

5. Optimal Design of GDFT

   The optima l design of phase shaping function (n), based on a performance metric is presented in this section . The phase function {k(n) n}, of (8) is now deco mposed into two functions in the time variab le as follows:

   The linear term of phase function kn is highlighted due to its significance in the orthogonality require ments . The GDFT fra mewo rk offers us the fle xib ility to define the phase shaping function according to the design require ments. Note that any function will give us an orthogonal GDFT.

   The cross-correlation sequence of a GDFT basis function pair (k ,l) with length N is defined as

   The auto-correlation function of a GDFT basis function as

6. RES ULT & DISCUSS ION

   The GDFT and other codes are implemented in M atlab and the results are shown below

   Fig 1 : The Periodic constant modulus sequence er(n)

   Fig 1 shows er(n) which is a periodic constant modulus sequence and plays an important role in Generalized Discrete Fourier Transform. It is a complex valued sequence as the rth power of the first primitive Nth root of unity. Hence it has zeros on the unit circle in z-plane as shown in fig. 2

   Fig 2 : Pole/zero plot for primitive Nth root of unity

   As spreading codes are to be dispread after transmission, the correlator function is required for it. It has been found that the GDFT provides good Auto-correlation and Cross-correlation values. Following figures depicts the results of simulation of different spreading codes such as Walsh, Gold, DFT and GDFT. Their Correlation is displayed along with Bit -error rate and Signal-to-Noise ratio.

   Fig 3 : Performance comparison of various codes

   Fig 4 : Optimum Design of (n) using RAC

   Fig 5 : Optimum Design of (n) using RCC

   The ma in advantage of the proposed method is the ability to design a wide collection of constant modulus orthogonal code sets based on the desired correlation performance mimic king the specs of interest. Moreover, the proposed GDFT technique can also be considered as a natural enhancement to DFT to obtain improved performance. Note that the auto-correlation magnitude functions of the codes in any GDFT set are the same. displays auto-correlation function of a size 16 GDFT code optimized based on along with size 16 DFT set for comparison purposes.

   Similarly, cross-correlation functions (CCF) of the first and second codes of optima l GDFT design based on metric and DFT set for a re displayed in Fig. 6. These figures highlight the me rit of the proposed GDFT fra me work over the traditional DFT.

   In order to compare performance of code families, several objective performance metrics are used. All the metrics used in this study depend on aperiodic correlat ion functions (ACF) of the spreading code set

   Table 1 : Performance comparison of various codes

   Code	dam	Dcm	Dmax	RAC	RCC	F
   Walsh	1.000	0.031	1.000	1.960	0.002	2.213
   Gold	1.000	0.306	1.000	0.247	0.007	0.786
   8 x 8 DFT	0.875	0.326	0.875	1.637	0.006	0.002
   16 x 16 DFT	0.937	0.088	0.937	7.318	0.002	0.001
   GDFT	0.342	0.454	0.454	0.335	0.014	0.006

7. CONCLUS ION

   In this paper, we have discussed the MATLAB implementation of Walsh, Gold, DFT and GDFT codes. These codes are simulated and their results are presented. It has been observed from the results that GDFT provides better and effective correlation functions which can be exploited in optimum way in asynchronous CDM A communication systems. However, there is further scope for optimization.

8. REFERENCES.

1. Ali N. Akansu, Handan Agirman-Tosun, Generalized Discrete Fourier Transform With Nonlinear Phase, IEEE

   TRANSACTIONS ON S IGNAL P ROCESSING, VOL. 58, NO. 9, SEP TEMBER 2010

2. R. Gold, Optimal binary sequences for spread spectrum

   multiplexing, IEEE Trans. Inf. Theory, vol. 13, no. 4, pp. 619621, Oct. 1967.

3. A. N. Akansu and R. Poluri, Walsh-like nonlinear phase orthogonal codes for direct sequence CDMA communications, IEEE Trans. Signal Process., vol. 55, no. 7, pp. 38003806, Jul. 2007.

4. H. Fukumasa, R. Kohno, and H. Imai, Design of pseudo noise sequences with good odd and even correlation properties for DS/CDMA, IEEE J. Sel. Areas Commun., vol. 12, no. 5, pp. 855884, Jun. 1994.

5. R. L. Frank, S. A. Zadoff, and R. Heimiller, Phase shift pulse codes with good periodic correlation properties, IRE Trans. Inf. Theory, vol. IT -8, no. 6, pp. 381382, 1962. [6] R. L. Frank, Polyphase codes with good non-periodic correlation

properties, IEEE Trans. Inf. Theory, vol. IT-9, no. 1, pp. 4345, 1963.

1. D. C. Chu, Polyphase codes with good periodic correlation

   properties, IEEE Trans. Inf. Theory, vol. IT-18, pp. 720724, Jul. 1972.

2. I. Oppermann and B. S.Vucetic, Complex valued spreading sequences with a wide range of correlation properties, IEEE Trans. Commun., vol. 45, pp. 365375, Mar. 1997.

3. I. Oppermann, Orthogonal complex-valued spreading sequences

   with a wide range of correlation properties, IEEE Trans. Commun., vol. 45, pp. 13791380, Nov. 1997.

4. K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory. New York: Springer-Verlag, 1993.

5. W. Narkiewicz, Elementary and Analytic Theory of Num bers. New York: Springer-Verlag, 1990.

6. A. Papoulis, Signal Analysis. New York: McGraw-Hill, 1977.

7. A. N. Akansu and R. A. Haddad, Multiresolution Signal Decomposition: Transform s, Subbands and Wavelets, 2nd ed. Amsterdam, The Netherlands: Elsevier, 2001.

   4556 IEEE TRANSACTIONS ON SIGNAL P ROCESSING, VOL. 58, NO. 9,

   SEP TEMBER 2010

8. G. Bongiovanni, P. Corsini, and G. Frosini, One-dimensional and two-dimensional generalized ciscrete Fourier transform, IEEE Trans.

Acoust., Speech, Signal Process.,, vol. ASSP -24, pp. 9799, Feb. 1976.

1. L. Rinaldi and P. E. Ricci, Complex symmetric functions and Generalized Discrete Fourier Transform, Rendiconti del Circolo Matematicodi Palerm o vol. 45, no. 1, Jan. 1996 [Online]. Available: http://www. springerlink.com/content/6310t2352461n4u1/

2. E. Stade and E. G. Layton, Generalized discrete Fourier

   transforms: The discrete FourierRiccatiBesseltransform, Comput. Phys. Commun., vol. 85, pp. 336370, Mar. 1995.

3. V. Britanak and K. R. Rao, The fast generalized discrete Fourier transforms: A unified approach to the discrete sinusoidal transforms computation, Signal Process., vol. 79, pp. 135150, Dec. 1999.

4. S. A. Martucci, Symmetric convolution and the discrete sine and cosine transforms, IEEE Trans. Signal Process., vol. 42, pp. 1038 1051, May 1994.

5. D. Sarwate, M. Pursley, and W. Stark, Error probability for direct- sequence spread-spectrum multiple-access communicationsPart

   I: Upper and lower bounds, IEEE Trans. Commun., vol. 30, pp. 975984, May 1982.

6. D. Sarwate, Bounds on crosscorrelation and autocorrelation of

   sequences, IEEE Trans. Inf. Theory, vol. 25, pp. 724725, Nov. 1979.

   fszf

7. L. Welch, Lower bounds on the maximum cross correlation of signals, IEEE Trans. Inf. Theory, vol. 20, pp. 397399, May 1974.

8. M. Golay, The merit factor of long low autocorrelation binary

   sequences, IEEE Trans. Inf. Theory, vol. 28, pp. 543549, May 1982.

9. B. Natarajan, S. Das, and D. Stevens, Design of optimal complex spreading codes for DS-CDMA using an evolutionary approach, in Proc. IEEE GLOBECOM, 2004, vol. 6, pp. 38823886

10. D. E. Goldberg, Genetic Algorithm s in Search, Optim ization and Machine

    Learning. Reading, MA: Addison-Wesley, 1989.

11. K. Fazel and S. Kaiser,Multi-Carrier and Spread Spectrum Systems. New York: Wiley, 2003.

12. A. N. Akansu and H. Agirman-Tosun, Generalized discrete Fourier

    transform: Theory and design methods, in Proc. IEEE Sarnoff Symp., Mar. 2009, pp. 17.

13. A. N. Akansu and H. Agirman-Tosun, Improved correlation of generalized

discrete Fourier transform with nonlinear phase for OFDM and CDMA communications, in Proc. EUSIPCO Eur. Signal Processing Conf., Aug. 2009, pp. 13691373.