Reach Project

The Fast Vector Transform: algorithms and applications to multicarrier communication systems

Page 1 of 77

The Fast Vector Transfom: algorithms and applications to multicarrier communication systems

A project submitted to the faculty of San Francisco State University In partial fulfillment of The requirements for The degree

Master of Science In Engineering: Computer and Communications

By Kyung Tae, Kang San Francisco, California May, 2007

Page 2 of 77

CERTIFICATION OF APPROVAL

I certify that I have read the report on Implementation and performance of The Fast Vector Transform: algorithms and applications to multicarrier communication systems by Kyung T, Kang and that in my opinion that this work meets the criteria for approving a research project submitted in partial fulfillment of the requirements for the degree: Master of Science in Engineering: Computer and Communications at San Francisco State University.

_______________________________________ Dr. Todor Cooklev Professor of Electrical Engineering, School of Engineering __________________________________________ Dr. Tom Holton Professor of Electrical Engineering, School of Engineering __________________________________________

Dr. Hamid Shahnasser Professor of Electrical Engineering, School of Engineering __________________________________________

Page 3 of 77

ACKNOWLEDGEMENTS

I would like to thank Dr. Todor Cooklev for his constant and kind support during the project. Importantly, I would like to thank my parents for their love and support throughout my studies

Kyung T, Kang May 2007

Page 4 of 77

The Fast Vector Transform Abstract The Vector transform (VT) has recently been shown to be an alternative to the discrete Fourier fransform (DFT). However until recently no efficient algorithms for the vector transforms were known. We develop novel algorithms for the VT, called fast vector transforms (FVT). The FVT algorithms proposed here are comparable to the well-known decimation-in-time (DIT) and decimation-in-frequency (DIF) algorithms. We advance recursive and non-recursive vector transform algorithms. We review fast algortims such as the fast Fourier transform (FFT) and fast Hartley transform (FHT). One application of the proposed FVT is in multicarrier wireless systems, where it outperforms the conventional DFT-OFDM system. We also construct a vector transform-based system for multicarrier modulation with multiple transmit and receive antennas, and show that it outperforms the corresponding conventional multiple-input multiple-output (MIMO) OFDM system.

.

Page 5 of 77

TABLE OF CONTENTS

Abstract................................................................................................................................5 Chapter 1 Introduction.........................................................................................................8 1.1The DFT and the FFT.................................................................................................8 1.2Radix-2 algorithm.....................................................................................................10 1.3Radix-4 algorithm.....................................................................................................14 1.4 The Hartley transform and the FHT........................................................................19 Chapter 2 OFDM...............................................................................................................22 2.1. Definition ...............................................................................................................22 2.3. Conventional OFDM..............................................................................................26 3. The Vector Transform (VT)...........................................................................................29 3.2. Real- Valued Kernel Vector Transform (VT)..........................................................37 CHAPTER 4 Fast Vector Transform.................................................................................40 4.1 Radix-2 FVT ...........................................................................................................40 4.2 FVT Radix-4............................................................................................................44 CHAPTER 5 VT Application of VT to OFDM.................................................................49 5.2Multiple-input multiple-output (MIMO) OFDM..........................................................53 References..........................................................................................................................57 APPENDIX Ⅰ...................................................................................................................60 A. Radix-2 FVT ................................................................................................................60 Recursive algorithms: ......................................................................................................60 1. ivt2.m (inverse FVT radix 2).....................................................................................60 2. ivtfft.m (sub-function of inverse radix 2 FVT)..........................................................60 3. vt2.m (radix-2 FVT)..................................................................................................61 4. vtfft.m (sub-function of FVT radix-2).......................................................................61 Non-recursive algorithms: ...............................................................................................62 5. ivtfft2.m (non-recursive inverse FVT radix-2)..........................................................62 6. vtfft2.m (non-recursive FVT radix-2)........................................................................63 B. Radix-4 FVT.............................................................................................................64 7. ivt4.m ( inverse FVT radix-4)....................................................................................64 8 ivtfft4.m (sub-function of inverse FVT radix-4)........................................................65 9 vt4.m (FVT radix-4)...................................................................................................66 10 vtfft4.m (sub-function of FVT radix-4)....................................................................66 APPENDIXⅡ....................................................................................................................68 VT-OFDM ........................................................................................................................68 1.VTbasedOFDM.m..........................................................................................................68 2. qpskmod.m.................................................................................................................72 3. giins.m.......................................................................................................................73 4. makeVector.m............................................................................................................73

Page 6 of 77

5. ivt.m...........................................................................................................................74 6.vt.m.............................................................................................................................74 7. vector_guard_ins.m..................................................................................................75 8 comb.m.......................................................................................................................75 9. girem.m......................................................................................................................76 10 qpskdemod.m............................................................................................................76

LIST OF FIGURES

LIST OF TABLES

LIST OF Matlab programs Page 7 of 77

Chapter 1 Introduction 1.1 The DFT and the FFT The Decrete Fourier Transform (DFT) is of fundamental importance to signal processing and communications. The DFT of a time sequence x[ n] is defined as [1]: N 1

X [k ]   WNnk x[ n] , k  0,1,..., N  1 ,

(1)

n 0

WN  e  j 2

N

.

In general, the data sequence x[ n] is also assumed to be complex valued. Similarly, the IDFT is defined as x[ n]  1 N

N 1

W n0

 nk N

X [k ] , n  0,1,..., N  1 .

(2)

Since DFT and IDFT involve basically the same type of computations, our discussion of efficient computational algorithms for the DFT applies as well to the efficient computation

Page 8 of 77

of the IDFT. We observe that for each value of k, direct computation of X [k ] involves N complex multiplications (4N real multiplications) and N-1 complex additions (4N-2 real additions). Consequently, the computation of all N values of the DFT requires N 2 complex multiplications and N 2-N complex additions. Direct computation of the DFT is basically inefficient primarily because it does not exploit the symmetry and periodicity properties of the phase factor WN . In particular, these two properties are:

Symmetry

property : WNk  N / 2   WNk

Periodicity property : WNk  N  WNk The computationally efficient algorithms described in this chapter, known collectively as fast Fourier transform (FFT) algorithms, exploit these two basic properties of the phase factor. The fast Fourier transform (FFT) is a faster version of the DFT. It is not a new kind of transform different from the DFT. Instead it is simply an algorithm for computing the DFT, and its output is precisely the same set of complex values. The FFT algorithm eliminates most of the repeated complex products in the DFT, and its execution n time is much shorter [1-3]. Many tricks and techniques have been developed to speed up the computation of FFTs. The basic idea behind decimation-in-time FFT algorithm is to decompose sequentially the N-point sequence x[n] into sets of smaller and smaller subsequences and then form a weighted combination of the DFTs of these subsequences. The same idea can be applied to the N-point DFT sequence X [k ] to decompose it sequentially into sets of

Page 9 of 77

smaller and smaller subsequences. This approach leads to another class of DFT computation schemes collectively known as the decimation-in-frequency (DIT) FFT algorithm. Basically, the computational problem for the DFT is to compute the sequence X [k ] of N complex-valued numbers, given another sequence of data x[ n] of length N, according to the equation (1).

1.2 Radix-2 algorithm The simplest and most common form of the Cooley-Tukey algorithm is called radix-2 decimation-in-time (DIT) FFT: it divides the problem size into two interleaved halves with each recursive stage. Recall that the DFT is defined by the formula: Radix-2 DIT first computes the Fourier transforms of the even-indexed numbers x[0], x[1]...x[n  2] , and of the odd-indexed numbers x[1], x[3]...x[n  1] , and then combines those two results to produce the Fourier transform of the whole sequence. Let us consider the computation of the N = 2v point DFT by the divide-and conquer approach We split the N-point data sequence into two N/2-point data sequences f1[n] and f 2 [n] , corresponding to the evennumbered and odd-numbered samples of x[ n] , respectively, that is, f1[n]  x[2n], f 2 [n]  x[2n  1],

n  0,1,..., N / 2  1

Thus f 2 [n] and f 2 [n] are obtained by decimating x[ n] by a factor of 2, and hence the resulting FFT algorithm is called a decimation-in-time algorithm. Now the N-point DFT equation (1) can be expressed in terms of the DFT's of the decimated sequences as follows: Page 10 of 77

X [k ] 



n  even

WNnk x[n] 

W

n  odd

nk N

x[ n] ,

(3)

and, X [k ] 

N / 2 1

W

2 nk N

n 0

x[2n] 

N / 2 1

W n0

(2 n 1) k N

x[2n  1] , n  0,1,..., N  1 , (4)

2 and we use another propertiy of DFT kernel which is WN / 2  WN . It can be derived in

following way: WN / 2

2

2   2     exp   j  exp  j  WN2 ,      N / 2  N     

(5)

2 and, taking WN / 2  WN into accout, the equation can be expressed as

X [k ] 

N / 2 1

W n 0

f [ n]  WNk

nk N /2 1

N / 2 1

W n 0

 F1[n]  W F2 [n], k N

nk N /2 2

f [ n]

, (6) k  0,1,..., N  1

where F1[ n] and F2 [n] are the N/2-point DFTs of the sequences f1[n] and f 2 [n] , respectively. Since F1[ n] and F2 [n] are periodic, with period N/2, we have F1[n  N / 2] = F1[ n] and F2 [n  N / 2] = F2 [n] . In addition, taking the factor WNk  N / 2   WNk into account, the equation may be expressed as X [k ]  F1[k ]  WNk F2 [k ]

, n  0,1,..., N 2  1 . N k X [k  ]  F1[k ]  WN F2 [k ] 2

(7)

Fig.1. indicates the computation involved in computing X [k ] according to Equation (7), for an 8-points.

Page 11 of 77

F1[0]

x[0]

x[4] x[2]

N/2-point DFT

x[6]

X [0]

F1[1]

WN0

F1[2]

WN1

F1[3]

WN2

X [1] X [2] X [3]

WN3

F2 [0]

x[1] x[5] x[3]

N/2-point DFT

x[7]

F2 [1] F2 [2] F2 [3]

X [4] − WN0 X [5] − WN1 X [6] − WN2 X [7] − WN3

Fig.1. Flow graph of the decimation-in-time decomposition of an N-point DFT computation into two N/2-point DFT computations (N=8) We observe that the direct computation of F1[ k ] requires (N/2)2 complex multiplications. The same applies to the computation of F2 [k ] . Furthermore, there are N/2 additional k complex multiplications required to compute WN F2 [k ] . Hence the computation of X [ k ]

requires 2(N/2)2 + N = N 2/2 + N complex multiplications. This first step results in a reduction of the number of multiplications from N 2 to N 2/2 + N, which is about a factor of 2 for N large. The decimation of the data sequence can be repeated again and again until the resulting sequences are reduced to two-point sequences. For N = 2v, this decimation can be performed v = log2N times.

Page 12 of 77

X [0]

x[0]

x[4]

W20

X [1]

−1

W40

x[2]

W41

W20 x[6]

W80

X [4]

W81

W20 −1

W40

x[3]

x[7]

X [3]

−1

−1

x[1]

x[5]

X [2]

−1

X [5]

W82

X [6]

−1

W41

W20

−1

W83

X [7]

−1

Fig.2. Eight-point decimation-in-time FFT algorithm Observe that the basic computation performed at every stage, as illustrated in Fig.2 is to k take two complex numbers, say the pair (a,b), multiply b by WN , and then add and subtract

the product from a to form two new complex numbers (A, B). This is basic computation, which is shown in Fig.3 is called a butterfly because the flow graph resembles a butterfly. A = a + WNk b

a

WNk

B = a − WNk b

b −1

Fig.3. Basic butterfly computation in radix-2 FFT algorithm

Page 13 of 77

In general each butterfly involves one complex multiplication and two complex additions. For N = 2v there are N/2 butterflies per stage of the computation process and log 2 N stages. Therefore, as previously indicated, the total number of complex multiplications in ( N / 2) log 2 N and complex additions is N log 2 N .

1.3 Radix-4 algorithm When the number of data points N in the DFT is a power of 4 (i.e., N = 4v), we can, of course, always use a radix-2 algorithm for the computation. However, for this case, it is more efficient computationally to employ a radix-4 FFT algorithm. Let us re-derive the radix-4 decimation-in-frequency algorithm by breaking the Npoint DFT formula (1) into four smaller DFTs. We have X [k ] 

N 1 4

 x[n]W n 0



N 1 4

kn N

 x[n]W n 0

kn N

N 1 2

 x[n]W



n N

kn N

4

 WNNk / 4

N 1 4





3 N 1 4

 x[n]W

nN

2

N

 x  n  4  n 0

kn N



N 1



n 3 N

WNkn  WNNk / 2

x[n]WNkn 4

N 1 4



. (8) N

 x  n  2  n 0

WNkn  WN3 N / 4

N / 4 1



 x  n  n 0

3N  kn WN 4 

From the definition of the twiddle factors, we have WNkN/4  ( j ) k , WNkN/2  (1) k , WN3kN/4  ( j ) k ,

(9)

and, taking the property of the twiddle factors (8) into account, the equation is expressed as: X [k ] 

N / 4 1

 n 0



N N 3N      k k k nk  x[n]  (  j ) x  n  4   (1) x  n  2   ( j ) x  n  4   WN . (10)        

The relation is not an N/4-point DFT because the twiddle factor depends on N and not on N/4. To convert it into an N/4-point DFT we subdivede the DFT sequence into four N/4-

Page 14 of 77

point subsequences, X(4k), X(4k+1), X(4k+2), and X(4k+3), k = 0, 1, ..., N/4. Thus, we obtain the radix-4 decimation-in frequency DFT as

x[4k ] 

N / 4 1

 n0

x[4k  1] 



N N 3N      x[n]  x  n  4   x  n  2   x  n  4        

N / 4 1

 n 0

x[4k  2] 



N N 3N      x[n]  x  n  4   x  n  2   x  n  4        



N / 4 1 n 0



N N 3N      x[n]  jx  n  4   x  n  2   jx  n  4        

N / 4 1



0 kn  WN WN/4



n 0

x[4k  3] 





N N     x[n]  jx  n  4   x  n  2   jx       



n kn  WN WN/4





2n kn  WN WN/4

 3N  n 4 

, (11)



3n kn  WN WN/4



where we have used the property WN4kn = WknN/4. Note that the input to each N/4-point DFT is a linear combination of four signal samples scaled by a twiddle factor. This procedure is repeated v times, where v = log4N. For the purpose of deriving a matrix form, let us re-derive the radix-4 decimationin-frequency algorithm by breaking the N-point DFT formula into four smaller DFTs. X [ p, q ] 

3

  l 0

F [l , q ] 

WNlq F [l , q ] W4lq

( N / 4) 1



M 0

, (12)

x[l , m] WNmq/ 4

p  0,1, 2, 3; l  0,1, 2, 3;

where x[l , m]  x[4m  l ] and X [ p, q ]  X [

q  0,1, 2,..., N / 4  1

N p  q ] . Thus, the four N/4-point DFTs F [l , q ] 4

obtained from the above equation are combined to yield the N –point DFT. The expression for combining the N/4-point DFTs defines a radix-4 decimation-in-time butterfly, which can be expressed in matrix form as

Page 15 of 77

0 q  WN2 q F [2, q ]  WN3q F [3, q ]   X [0, q ]  WN F [0, q]  WN F [1, q ]  X [1, q]   W 0 F [0, q]  W q  N / 4 F [1, q ]  W 2( q  N / 4) F [2, q ]  W 3( q  N / 4) F [3, q ]   N N N    N   . (13) 0 q  N / 4 2( q  N / 4) 3( q  N / 4)  X [2, q ] W F [0, q ]  W F [1, q ]  W F [2, q ]  W F [3, q ] N N N N      X [3, q]   WN0 F [0, q]  WNq 3 N / 4 F [1, q]  WN2( q 3 N / 4) F [2, q ]  WN3( q 3 N / 4) F [3, q ] 0 Note that each matrix involve involves 12 complex multiplications, since WN =1, and 12

complex additions. By performing the one more step, it is possible to reduce the complex multiplications to form 12 to 3  X [0, q ]   X [1, q]       X [2, q ]      X [3, q]  

1 1 1 1 1  j  1 j  1  1 1  1  1 j  1 j 

 WN0 F [0, q ] 

 1  WN F [1, q]   W 2 F [2, q ] , (14)  N   WN3 F [3, q]   

In the case of radix-4 decimation-in-time in matrix form (13), the flow graph can be shown in Fig.4

Page 16 of 77

WNk

WN2 k WN3k WN( k +N / 4)

WN2( k +N / 4) WN3( k +N / 4)

WN( k +N / 2)

WN2( k +N / 2)

WN3( k +N / 2)

WN( k +3 N / 4) WN2( k +3 N / 4)

WN3( k +3 N / 4)

Fig.4. Flow graph of the basic butterfly computation for radix-4 Fig.4. can be redrawn as in Fig 5, which is basically same computation as the butterfly in matrix form (14).

Page 17 of 77

WNk

−j − 1

WN2 k

1

j

−1

−1

−1

j

−j

3k WN

Fig.5. Alternative arrangement of Fig.4 resulting in savings of multiplications This decimation-in-time procedure can be repeated recursively log 4 N times. Hence the resulting FFT algorithm consists of log 4 N stages, where each stage contains N/4 butterflies. Consequently, the computation burden for the algorithm is (3N / 4) log 4 N complex multiplications and (3N ) log 4 N additions, which are computed respectively in Table 1 and Table 2. Table1: Complexity comparison of complex multiplications Radix-2 FFT and Radix-4 FFT Complex multiplications N points Radix-2 ( ( N / 2) log 2 N ) Radix-4 ( (3N / 4) log 4 N ) 16 32 24 32 80 64 192 144 128 448 256 1,024 768 512 2,034 1024 5,120 3,840 2048

11,264

4096

24,576

Page 18 of 77 18,432

Complex additions N log N Radix-2 ( ) Radix-4 ( (3N ) log 4 N ) 2 16 64 96 32 160 64 384 576 128 896 256 2048 3072 512 4,068 1024 10,240 15360 2048 22,528 4096 49,152 73728 Table 2: Complexity comparison of complex addtions Radix-2 FFT and Radix-4 FFT N points

1.4 The Hartley transform and the FHT The discrete Hartley transform (DHT) is a real transform with a convolution property [4],[5] which has been proposed as an alternative to the DFT for real data [4], [6], [7]. It is indeed an invertible linear transform closely related to the DFT. In the DFT, one multiplies  j 2 each input by WN  e

N

 cos(2 / N )  j sin(2 / N ) , whereas in the DHT each input is

multiplied by simply cos(2 / N )  sin(2 / N ) . Thus, the DHT transforms N real numbers to N real numbers, and exhibits the convenient property of being its own inverse. Furthermore, the fast algorithms for DHT computation can also reduce the computational complexity in a similar manner to that of the FFT techniques for the DFT computation. A properly designed real-input FFT has no more operations in general than the fast Hartley transfom (FHT), Even if the Hartley transform offers no computational advantages and recursion over the Fourier transform., it does possess certain structual advantages. We will

Page 19 of 77

therefore discuss the construction of the fast Hartley transform (FHT) mathematically. The discrete Hartley transform (DHT) of a time sequence x(n) is defined as:  2 nk  , k  0,1,...N  1 ,  N 

N 1

H (k )   x( n)cas  n 0

(15)

where cas u = cos u + sin u

.

(16)

In a similar development to the FFT, (15) can be decomposed as H (k ) 

( N / 2) 1

 n0

N 1  2 nk   2 nk  x (n)cas    x(n)cas  , (17)  N  n N / 2  N 

Let n = n + N/2 in the second summation of (17) H (k ) 

( N / 2) 1

 n0



N  2 nk    2 k[n  N / 2]    x  n  cas   , (18) 2 N  N     



 x( n)cas 

Using the identities sin( A  B)  sin A cos B  cos A sin B , (19) cos( A  B )  cos A cos B  sin A sin B for odd k,  2 k[ n  N / 2]   2 nk   2 nk    cos  cos( k )  sin  sin( k ) N N  N       2 nk   2 nk   sin  cos( k )  cos  sin( k ) N  N    , (20)  2 nk   2 nk    cos   sin   N  N     2 nk   cas  N   

cas 

and for even k,  2 k[n  N / 2]   2 nk   2 nk   2 nk  , (21)   cos   sin    cas   N    N   N   N 

cas 

Page 20 of 77

Using (20) and (21), (18) becomes H (k ) 

( N / 2) 1

 n 0

N    2 nk   x(n)  x  n  2  cas  N , for even k ,      

(22)

N    2 nk   x(n)  x  n  2  cas  N , for odd k ,      

(23)



and H (k ) 

( N / 2) 1

 n 0



let k =2k for even k, and let k =2k+1 for odd k, equation (22) and (23) become ( N / 2) 1



H (2k ) 

n0

H (2k  1) 

N    2 n 2k  ,  x  n   x  n  2  cas  N       

( N / 2) 1

 n 0

(24)

N    2 n[2k  1]  , (25)  x  n   x  n  2  cas  N       

Furthermore, using (19)  2 k[2k  1]   2 n    2 n2k   2 n2k    2 n    2 n2k   2 n2k   ,(26)   cos   cos   sin    sin   cos   sin   N    N   N   N   N   N   N 

cas  and

 2 kn   2 k[ N  n]     sin   N  N   

sin 

 2 kn   2 k[ N  n]  cos    cos   N  N   

,

(27)

equation (15) becomes H (2k  1) 

( N / 2) 1

 n 0

N   2 n   2 n 2k   2 n   2 2k[ N  n]     x(n)  x(n  )  cos  cas   sin  cas   , (28) 2  N  N   N   N       

Substituting N/2 – n for n in the second summation, (22) becomes

H (2k  1) 

( N / 2) 1

 n 0

 

N   2 n     x(n)  x(n  )  cos    2   N    

  N   2 n    2 n2k   n  x( N  n)  sin   cas  , (29)  2   N   N  

x

Page 21 of 77

Equation (26) and (27) become H (2k ) 

( N / 2) 1

 n0

H (2k  1) 

( N / 2) 1

 n 0

 

N   2 n 2k  ,  x(n)  x(n  2 )  cas  N  

N   2 n2k     x(n)  x(n  )  cas    2    N  

(30)

  2 n    N   2 n2k   n  x( N  n)  sin   cas  .(31)  2   N    N 

x

As shown, the Fourer tranform is defined in fields other than the complex field, Whereas complex additions and multiplications are required for an FFT, the Hartley transform [5][89] requires only real multiplications and additions. The FFT maps a real function of time into a complex function of frequency, whereas the fast Hartley transform (FHT) maps the same real-valued function into a real function of frequency. The FHT can be particulary useful in cases where the phase is not a concern.

Chapter 2 OFDM 2.1. Definition Frequency division multiplexing (FDM) is a technology that transmits multiple signals simultaneously over a single transmission path, such as a cable or wireless system. Each signal travels within its own unique frequency range (carrier), which is modulated by the data (text, voice, video, etc.). Orthogonal frequency division multiplexing (OFDM) is a technique that distributes the data over a large number of carriers that are spaced apart at precise frequencies. This spacing provides the "orthogonality" in this technique, which prevents the demodulators from detecting frequencies other than their own. Some benefits of OFDM are:

Page 22 of 77



High spectral efficiency



Resiliency to RF interference



Lower multi-path distortion

OFDM is useful, because in a typical terrestrial broadcasting scenario there are multipathchannels (i.e. the transmitted signal arrives at the receiver using various paths of different length). Because multiple versions of the signal interfere with each other (inter symbol interference (ISI)), it becomes difficult to extract the original information. Channel simulation allows us to examine the effects of noise and multi-path on the OFDM scheme. By adding a small amount of random data to the transmitted signal, simple noise can be simulated. Multi-path simulation involves adding attenuated and delayed copies of the transmitted signal to the original. This simulates the problems in wireless communication, in which the signal propagates on many paths. For example, a receiver may detect a signal via a direct path as well as a path that bounces off a building. The receiver will perform the inverse of the transmitter by first separating the data into parallel streams. Next, the FFT will convert these parallel data streams into frequency domain data. The data is now available in modulated form on the orthogonal carriers. Demodulation down-converts this information back to the base band. Finally, this parallel data is converted back into a serial stream to recover the original signal. OFDM is also referred to as a multi-carrier or as discrete multi-tone modulation. It is the modulation technique used for digital television in Europe, Japan, and Australia. It is important that the overall system design be well matched to its service profiles to maximize the performance of the system and balance the ultimate user experience it provides, relative to the cost of the operator. OFDM enables the creation of a very flexible system architecture that can be efficiently used for a wide range of services, including voice and Page 23 of 77

data. For a mobile system to create a satisfactory user experience, it must provide fast, ubiquitous, and user-friendly connectivity. OFDM possesses several unique properties that make it especially well-suited to handle the challenging environmental conditions experienced by wireless data applications. Many systems currently use OFDM to enhance their performances. DAB-OFDM forms the basis for the Digital Audio Broadcasting (DAB) standard in the European market. ADSL-OFDM forms the basis for the global ADSL (asymmetric digital subscriber line) standard. Wireless local area network development continues to thrive for wireless point-to-point and point-to-multipoint configurations using OFDM technology. In a supplement to the IEEE 802.11 standard, the IEEE 802.11 working group published IEEE 802.11a, which outlines the use of OFDM in the 5.8-GHz band.

2.2. Orthogonality In OFDM, the sub-carrier frequencies are chosen so that the sub-carriers are orthogonal to each other other—meaning that cross-talk between the sub-channels is eliminated and inter-carrier guard bands are not required [10] [11]. This greatly simplifies the design of both the transmitter and the receiver, and unlike conventional FDM, a separate filter for each sub-channel is not required. Orthogonality also allows for high spectral efficiency, near the Nyquist rate. Almost the entire available frequency band can be utilized. OFDM generally exhibits an almost “white” spectrum, which imparts it with benign electromagnetic interference properties, with respect to other co-channel users. The orthogonality allows for efficient modulator and demodulator implementation using the FFT algorithm. Although these principles, as well as some benefits, have been known since the 1960s, OFDM has only recently gained

Page 24 of 77

popularity for wideband communications, as a result of low-cost digital signal processing components that can efficiently calculate the FFT. Two periodic signals are said to be orthogonal when the integral of their product over one period is equal to zero. To maintain orthogonality between sub-carriers, it is necessary to ensure that the symbol-time contains one or more multiple cycles of each sinusoidal carrier waveform. Orthogonality is critical because it prevents inter-carrier interference (ICI). ICI occurs when the integral of the carrier products are no longer zero over the integration period—signal components from one sub-carrier cause interference on neighboring sub-carriers. As such, OFDM is highly sensitive to frequency dispersion caused by Doppler shifts, which results in loss of orthogonality between sub-carriers. Furthermore, orthogonalty can be defined using matrices. An orthogonal matrix is a real valued unitary matrix, and is thus always a normal matrix. The normal matrix is a complex matrix if AAT  AT A where A is the conjugate transpose of AT [15]. Although we consider only real matrices here, this definition can extend to matrices with entries from any field.

Orthogonal

matrices arise naturally from inner products, however, as well as for matrices of complex numbers that lead to the unitary requirement. Thus, finite-dimensional linear isometries— rotations, reflections, and their combinations—produce orthogonal matrices. The converse is also true: orthogonal matrices imply orthogonal transformations. Orthogonal matrices are important for a number of reasons, both practical and theoretical. The n×n orthogonal matrices form a group—the orthogonal group—which, with its subgroups, is widely used in mathematics and the physical sciences. Because floating point versions of orthogonal matrices exhibit advantageous properties, they are key

Page 25 of 77

to many algorithms in numerical linear algebra, such as QR decomposition. As another example, with appropriate normalization the discrete cosine transform (used in MP3 compression) is represented by an orthogonal matrix.

2.3. Conventional OFDM Multicarrier modulation is based on the discrete Fourier transform (DFT) in conventional OFDM, as originally suggested in [1-3], [11]. Fig.6 shows a conventional OFDM transmitter and receiver. The first two blocks are the serial-to-parallel (S/P) converter and the bit-to-symbol mapping such as quadrature phase shift keying (QPSK), 16 quadrature amplitude modulation (16-QAM), or another QAM modulation. Let X [k ] , k  0,1,..., N  1 , be the sequence of information symbols after the bit-to-symbol mapping. All carriers are combined using the inverse DFT x  FN* X ,

(32)

* where FN is the inverse discrete Fourier transform matrix of size N  N , where N is the

number of carriers. Next, Cyclic Prefix (CP) is added to the OFDM symbol. The Cyclic Prefix prevents inter-symbol interference (ISI), as long as its length exceeds the duration of the impulse response of the channel. Including the CP, the time to transmit one OFDM symbol, also called OFDM symbol period, is Ts=(K+N)T, where T is the sampling period and K is the number of samples in CP. After the CP has been added the resulting complex samples are transmitted by an in-phase and quadrature modulator.

S/P

bit-to-symbol mapping

xcp [m]

x[n]

X [k ]

N-point IFFT

Add CP

P/S

Page 26 of 77

(a) Xˆ [ k ]

P/S

synchronization

Y [k ]

symbol -to-bit

H [k ]

N-point FFT

S/P

Remove CP

N-point FFT

channel impulse response

channel estimation

(b) Fig. 6 Conventional OFDM transmitter (a) and receiver (b)

In this model the many scattered paths that may exist in a real wireless channel are replaced by L multipath components. With respect to the baseband, the channel can be modeled by an FIR model with transfer function L 1

H ( z )   h( n) z  n .

(33)

n0

The channel impulse response coefficients are modeled as independent zero-mean random Gaussian processes. To make the CP longer than the channel delay spread, it is necessary that K  L . In a slowly fading wireless channel where the channel does not change within one OFDM symbol, the CP converts the linear convolution with the channel impulse response into a cyclic convolution. The received signal is given by y  HFN* Xη ,

(34)

where

Page 27 of 77

 h0  h H 1  L   hN 1

hN 1 L h0 L

h1  h2 

, (35) 

hN  2 L



h0 

is a circular matrix and η is a vector with the noise components [n] , which can be 2 assumed to be Gaussian with zero mean and variance   N 0 / 2 , with N 0 being the

single-sided power spectral density. In the receiver, shown in Fig.6.b, the CP is removed and the forward DFT is applied to obtain Y  FN y  FN HFN* X  Fη N .

(36)

* The product FN HFN is equal to a diagonal matrix with the DFT of the channel impulse

response H [ k ]  H ( z ) z e j 2 k / N on the main diagonal: FN HFN*  diag  H [0] H [1] L

H [ N  1] .(37)

This diagonalization effectively decomposes the channel into parallel and decoupled subchannels. In other words, the frequency-selective channel is transformed into a channel with flat fading per carrier. In the receiver, the information sequence X [ k ] must be detected from Y [k ] , where Y [k ]  H [k ] X [k ]  [k ] , k  0,1,..., N  1 .

(38)

In the above equation [k ] is the DFT of the noise. Then, a zero-forcing (ZF) detector can be used that requires one division per carrier. All commercial systems for multicarrier modulation use the set of complex exponential functions as orthogonal basis. Recently, multicarrier modulation systems based on the discrete cosine transform (DCT) have also been studied [12], [13].

Page 28 of 77

3. The Vector Transform (VT) The vector transform pair are X[k ] 

x[ n] 

N 1

1 N

W

1 N

W

nk

x[n] ,

(39)

n 0

N 1

 nk

X[k ] ,

(40)

k 0

where x[n] and X[k ] are sequences of vectors of dimension M  1 constitute forward and inverse vector transform if the matrix kernel W of dimension M  M satisfies two conditions. First, it must provide an orthogonal basis: N 1

W k 0

nk

W*mk   m  n NI , 0  m, n  N  1 ,(41)

Page 29 of 77

where W* means transposition of the matrix and conjugation of the coefficients, and second, following properties of the W matrix are of interest to the discussion of the vector transform W N  I, W ( N / 2)  I, WT  W 1  W N 1 .

(42)

If (39) is written in a matrix form, then we have      

X[0]   X[1]    ...     X[ N  1] 

I I I W ... ... I W N 1

... I   N 1 ... W   ... ... ( N 1)( N 1)  ... W  











x[0]  x[1]  .(43) ...   x[ N  1]

In general any scalar transform of length MN can be written in the form (43) above, although the partitioning of the MN  MN transformation matrix of the scalar transform into N 2 matrices of size M  M is done only artificially. Vector transforms also have more degrees of freedom than scalar transforms and must be designed first. One known matrix is  0 1 0  0 0 1  W =  ... ... ...   0 0 0  -1 0 0

... 0 0  ... 0 0  ... ... ...  ,  ... 0 1  ... 0 0 

(44)

which satisfies conditions (41) and (42) only when it is of dimension N / 2  N / 2 , or equivalently when the vectors have M  N / 2 components. Furthermore its elements are only real numbers. This makes it inconvenient for applications like multicarrier modulation. The transforms mentioned above are not the only transforms that can be used to construct multicarrier signals. The goal of this paper is to propose a new type of multicarrier modulation system. Modulation in the proposed system is performed

Page 30 of 77

using an inverse vector transform, and demodulation is performed using a forward vector transform. We call the system proposed here VT-OFDM, and the conventional OFDM system, DFT-OFDM. The vector transform has been shown in [14], [16], [17] to have a T vector-based decorrelation property, where E[ Xi X j ] are small for i  j and large for i  j .

First, let us begin our discussion with the definition of E[ X] . If X has a single continuous variable, the expected value of X with density function f ( x) is defined by

E[ X]  



x f ( x )dx ,



(45)

and, considering two random variables, the joint probability function can be used to find the expected value of functions of two random variables in much the same way as with the single variable density function. These functions involving both variable x and y will lead to statistics that will partially characterize the relationships between the two random variables. In gerneal, the expected value of any function, g(X,Y), can be found from E[ g ( X, Y)]  











g ( x, y ) f ( x, y )dx dy ,

(46)

and when g ( x, y )  XY , this expected value is known as the correlation and is given by E[ X, Y]  











xy f ( x, y )dx dy ,

(47)

if two random variable that have a correlation of zero are said to be orthogonal. One statistical parameter related to a pair of random variables is the correlation coefficient. The correlation coefficient of two random variables, x and y , when  XY is defined as

 XY 

Cov( X, Y) , Var ( X)Var (Y)

(48)

where, Cov( X, Y) is the covariance between two random variables:

Page 31 of 77

Cov( X, Y)  E[( X  E ( X))(Y  E (Y))] . (49) The correlation is 1 in the case of an increasing linear relationship, -1 in the case of a decreasing linear relationship, and some value in between in all other cases, indicating the degree of linear dependence between variables. The close the coefficient is to either -1 or 1, the stronger the correlation between the variables. Therefore, to analyze quantitatively how much decorrelation and enery packing are achieved by the vector transform based OFDM, we first suppose use a complex valued kernel of dimension M  M as mentioned in chapter 3 and the vector transform takes as input a sequence of N vectors, x[ n] generates as output another sequence of N vectors X[k ] are sequences of vectors of dimension M  1 . Considering a block of image data of N columns and M rows and taking each column as a vector, then the block of complex-valed becomes a set of N vectors, then the block of complex-valued data becomes a set of N vectors with each vector having M components as shown below.  x0.0  x  1.0

K   xM 1.0

x0.1

K

x1.1

K

K

K K

xM 1.0

x0. N 1  x1. N 1 

, 

K

(50)



xM 1. N 1 

and  x0  

x0.0  x1.0 

x1  

x0.1  x1.1 









 



K 



 xM 1.0 



 x2  

x0. N 1  x1. N 1  





...

K 

 xM 1.1 



. (51) 

K

 xM 1. N 1 

By taking the vector transform of this set of N vectors, we obtain another set of N vectors, Similar to the scalar transforms, the vectors in the vector transform domain are less correlated than the vectors in the data transform domain, and the energy is concentrated in

Page 32 of 77

fewer vectors in the vector transform domain than in the data domain. For example, correlation of a pair of vector sequences of dimension 2  1 can be shown as follows:  E[ x0,m x0,n ] E[ x0,m x1,n ]

 1     , (52)  E[ x1,m x0,n ] E[ x1,m x1,n ]    1 

E[xi xTj ]  

If N = 8 and

 =0.91, the correlation matrix of two data vectors x m and x n can be

respectively shown as follows:  1.000 0.910   ,  0.910 1.000 

E[x m xTn ]  0.91|m  n| 

(53)

the kernel of an 8-point VT is  -0.7071 + 0.0000i, -0.6937 - 0.1369i  W8    .  0.6937 - 0.1369i -0.7071 + 0.0000i 

(54).

Using the equation in (39), the correlation of a pair of Xi and X j in the vector transform domain can be written as follows:   1 N 1 mi   1 N 1 T   E[ Xi XTj ]    W x m  x n ( W nj )T      N n 0     N m0 , (55). N 1 N 1 1 mi T nj T   W E  x m x n  ( W ) N m  0 n 0 If we consider the sum of elements for i = j in each matrix, the correlations in the vector transform domain are computed in a following way:

Page 33 of 77

 6.3435 5.7726    5.7726 6.3435 

E[ X0 XT0 ]  

 6.3721 - 0.0000i 0.1875 - 1.1020i    0.1875 + 1.1020i 6.3128 - 0.0000i 

E[ X1X1T ]  

 6.3107 - 0.0000i 0.1880 - 1.1015i    0.1880 + 1.1015i 6.3699 - 0.0000i 

E[ X2 XT2 ]  

 6.3369 + 0.0000i 5.7687 - 0.0000i    5.7687 + 0.0000i 6.3415 - 0.0000i 

E[ X3 XT3 ]  

 6.3369 + 0.0000i 5.7687 - 0.0000i    5.7687 + 0.0000i 6.3415 - 0.0000i 

E[ X4 XT4 ]  

 6.3686 - 0.0000i 0.1876 - 1.1012i    0.1876 + 1.1012i 6.3077 + 0.0000i 

E[ X5 XT5 ]  

 6.3375 - 0.0000i 0.2169 - 1.0952i    0.2169 + 1.0952i 6.3366 + 0.0000i 

E[ X6 XT6 ]  

 6.3063 - 0.0000i 0.1887 - 1.1006i    0.1887 + 1.1006i 6.3657 + 0.0000i 

E[ X7 XT7 ]  

Page 34 of 77

 6.3435 5.7726   -0.0178 + 0.0024i 0.0083 + 0.0026i  E[ X0 X1T ]      5.7726 6.3435   -0.0185 + 0.0026i 0.0066 + 0.0024i   -0.0033 - 0.0058i -0.0625 - 0.0064i   -0.2601 + 0.0139i -0.0948 + 0.0153i  E[ X0 XT2 ]   E[ X0 XT3 ]      0.0026 - 0.0064i -0.0625 - 0.0058i   -0.2500 + 0.0153i -0.1189 + 0.0139i   0.4224 - 0.0292i 0.0876 - 0.0320i   -0.1188 - 0.0141i -0.2514 - 0.0155i  E[ X0 XT4 ]   E[ X0 XT5 ]      0.4123 - 0.0320i 0.1269 - 0.0292i   -0.0947 - 0.0155i -0.2615 - 0.0141i  E[ X0 XT0 ]  

 -0.0618 + 0.0058i 0.0031 + 0.0064i   E[ X0 XT7 ]     -0.0619 + 0.0064i -0.0027 + 0.0058i  

E[ X0 XT6 ]  

0.0073 - 0.0025i -0.0187 - 0.0027i  0.0091 - 0.0027i -0.0179 - 0.0025i 

 -0.0178 - 0.0024i -0.0185 - 0.0026i   6.3721 - 0.0000i 0.1875 - 1.1020i  E[ X1X1T ]      0.0083 - 0.0026i 0.0066 - 0.0024i   0.1875 + 1.1020i 6.3128 - 0.0000i 

E[ X1XT0 ]  

 -0.0761 + 0.0024i -0.1527 - 0.0292i   -0.0326 - 0.0059i -0.0336 - 0.0007i  T E [ X X ]  1 3   0.0318 - 0.0122i -0.0329 - 0.0059i   -0.1796 + 0.0345i 0.0652 + 0.0024i   

E[ X1XT2 ]  

 -0.1180 + 0.0140i -0.0951 + 0.0152i   -0.0291 - 0.0000i -0.0284 - 0.0057i  E[ X1XT5 ]      -0.2510 + 0.0155i -0.2606 + 0.0140i   -0.0281 + 0.0056i 0.0300 - 0.0000i 

E[ X1XT4 ]  

 -0.1773 - 0.0141i -0.0898 + 0.0164i   -0.0344 + 0.0059i 5.5840 + 1.1078i  E[ X1XT7 ]      0.0676 - 0.0475i -0.2026 - 0.0141i   5.5187 - 1.0949i -0.0298 + 0.0059i 

E[ X1XT6 ]  

 -0.0033 + 0.0058i 0.0026 + 0.0064i   -0.0761 - 0.0024i -0.1796 - 0.0345i  E[ X 2 X1T ]      -0.0625 + 0.0064i -0.0625 + 0.0058i   -0.1527 + 0.0292i 0.0652 - 0.0024i 

E[ X 2 XT0 ]  

0.2166 - 1.0961i   6.3415 - 0.0000i  0.0660 + 0.0024i -0.1532 - 0.0293i  E[ X 2 XT3 ]      0.2166 + 1.0961i 6.3412 - 0.0000i   -0.1803 + 0.0346i -0.0766 + 0.0024i   -0.0622 - 0.0059i -0.0622 - 0.0064i   -0.0622 - 0.0059i -0.0622 - 0.0064i  E[ X 2 XT4 ]   E[ X 2 XT5 ]      0.0034 - 0.0065i -0.0031 - 0.0059i   0.0034 - 0.0065i -0.0031 - 0.0059i  E[ X 2 XT2 ]  

 -0.0018 - 0.0000i 5.5523 + 1.0956i   -0.2019 - 0.0142i -0.0898 + 0.0164i  E[ X 2 XT7 ]      5.5526 - 1.0957i 0.0029 - 0.0000i   0.0683 - 0.0476i -0.1777 - 0.0142i 

E[ X 2 XT6 ]  

 -0.2601 - 0.0139i -0.2500 - 0.0153i   -0.0326 + 0.0059i 0.0318 + 0.0122i  E[ X3 X1T ]      -0.0948 - 0.0153i -0.1189 - 0.0139i   -0.0336 + 0.0007i -0.0329 + 0.0059i 

E[ X3 XT0 ]   

0.0660 - 0.0024i -0.1803 - 0.0346i   6.3107 - 0.0000i E[ X3 XT3 ]     -0.1532 + 0.0293i -0.0766 - 0.0024i   0.1880 + 1.1015i  0.0075 + 0.0024i 0.0088 + 0.0027i   -0.0348 - 0.0059i E[ X3 XT4 ]   E[ X3 XT5 ]     -0.0184 + 0.0027i -0.0178 + 0.0024i   5.5843 - 1.1079i E[ X3 XT2 ]  

 -0.2010 + 0.0141i 0.0679 + 0.0473i  -0.0894 - 0.0163i -0.1768 + 0.0141i

E[ X3 XT6 ]  

0.1880 - 1.1015i  6.3699 - 0.0000i  5.5184 + 1.0949i  -0.0302 - 0.0059i 



 0.0311 - 0.0000i -0.0287 - 0.0058i  T  E[ X3 X7 ]   -0.0284 + 0.0057i -0.0297 - 0.0000i    

It is also clear that correlations between the vectors in the transform domain are much less than that between the vectors in the data domain. For example, X 4 and X0 are almost Page 35 of 77

T T decorrelated because E[ X0 X 4 ] , E[ X 4 X0 ] is very close to zero.The above-mentioned

decorrelation property of the VT leads to better performance in the presence of ICI and ISI.

3.1. Complex Kernel Vector Transform (VT) All commercial systems for multicarrier modulation use the set of complex exponential functions as orthogonal basis. Clearly, the transform kernel of scalar transforms is uniquely specified, but in the case of vector transforms, the kernel must be designed. One way to construct vector transform kernels is the following: First, suppose that  a1 ,..., aM  are not necessarily distinct integers in the set

 1, 2,..., N -1

for which gcd(ak , N )  1 . Then

consider the M  M diagonal matrix

V = diag  e j 2 a1 / N , e j 2 a2 / N ,..., e j 2 aM / N  .

(56)

It can be shown that the matrix (56) satisfies conditions (41) and (42). First V N  diag (1,1,...,1)  I , i.e. condition (42) is satisfied. Second, since V*  diag  e  j 2 a1 / N , e  j 2 a2 / N ,..., e  j 2 aM / N  condition (41) is also satisfied: N 1

N 1

n 0

n 0

 V mk V*nk  diag  e j 2 a1k ( mn) / N , e j 2 a2k ( mn) / N ,..., e j 2 aM k ( mn) / N   diag   m  n N ,  m  n N ,...,  m  n N    m  n NI . Furthermore, if T is an arbitrary unitary matrix, W  TVT*

(57)

Page 36 of 77

is also a kernel of dimension M  M . Note that the obtained W is a normal matrix, since it is unitarily similar to a diagonal matrix

3.2. Real- Valued Kernel Vector Transform (VT) If the data symbols are obtained by modulation schemes such as BPSK or PAM and are therefore real-valued, and if the VT kernel is real-valued, the baseband signal is still a real signal and the bandwidth of a VT-OFDM system is one half the bandwidth of a DFTOFDM system with the same number of sub-carriers. In this case single-sideband (SSB) or vestigial side-band (VSB) techniques can be used to improve the bandwidth efficiency. SSB or VSB technologies cannot be used if the baseband signal is complex-valuedIn a sense, the VT is a generalization of the DFT: when the dimension M becomes equal to 1 the DFT is obtained. For M>1, and for the special case of a1  ...  aM  1 , the transform kernel is W  e j 2 / N I and the VT becomes equivalent to M DFTs acting on every dimension separately. In the scalar case (dimension M=1) the equation (42) cannot be solved over the set of real numbers for N>2. However, as observed in [14], real-valued VT kernels are possible even for N>2. In general, we can derive kernel below when M = 2

1 W 2



e j 2 (    



e j 2 a1 / N  e j 2 a2 / N  e j 2 (   

a1

N)

e

j 2 (    a2 N )

e

a1

N)

j 2 a1 / N

 e j 2 (    e

 j 2 a2 / N

a2



N)





, (58)

For example, if we define T

1 2

 1  j  j 1  ,  

(59)

and

Page 37 of 77

 e j 2 a / N 0 

Va  

e

0



 j 2 a / N



 ,

(60)

then  cos(2 a / N )  sin(2 a / N )  Wa  TVa T*    (61)  sin(2 a / N ) cos(2 a / N ) 

is a kernel with real elements. The notation Wa and Va means that these vector transform kernels are generated by the number a. Furthermore, the block-diagonal matrix

 Wa1 

0  

Wa2

W 



(62)



... 

 0



WaM / 2 

is also a kernel of dimension M  M for even values of M. While the fact that real-valued vector transform kernels are possible is known, the fact that real-valued kernels do not exist when M is odd has not been established up to now.

Theorem 1 There exists no M x M real-valued matrix that can be a VT kernel (i.e. that satisfies the kernel conditions) if the dimension M is odd and N is greater than 2. Proof: First, note that the characteristic polynomial det W   I has degree M. If M is odd, the characteristic polynomial must have at least one real root. Since W N  I , this root must be either 1 or -1. Then, consider the following four cases: 1)N>2,   1 . Therefore, there must be a non-zero vector v such that Wv  v . Then, we must have on one hand N 1

N 1

k 0

k 0

 W k v   v  Nv (63) Page 38 of 77

But on the other hand the orthogonality condition (41) for m=0 and n=1 requires

N 1

W

k

0 . The contradiction that is obtained means that there is no real-valued kernel for

k 0

N>2,   1 . 2)N>2,   1 . A contradiction is obtained in a similar way. There must be a non-zero

N 1

vector v such that Wv   v . This means that

W

orthogonality (48) for m=0 and n=2 requires that

W

2k

k 0

N 1

N 1

v  v  Nv . On the other hand, k 0

2k

0 .

k 0

3)N=1. This case is easily analyzed. If   1 an immediate contradiction is obtained. Therefore, only   1 is possible. In this case the only solution to the equations (41) and (42) is W  I . 4)N=2,   1 . In this case the only possible kernel is W  I . Q.E.D.

Page 39 of 77

CHAPTER 4 Fast Vector Transform 4.1 Radix-2 FVT Radix-2 DFT reduces the computational number of complex multiplication to Nlog2N and of complex additions to Nlog2N, because each butterfly requires one complex multiplication k n and two additions and the twiddle factors WN and WN are complex exponents. In the

algorithms of FVT, however, the twiddle factors are matrices and exhibit the following properties: WNk  N / 2  WNN / 2 WNk   WNk .

(64)

where the notation WN denotes a vector transform kernel of order N and of a dimension assumed to be M  M in general. Using the aforementioned properties, and assuming that N is a power of two, we can devide VT into two sequences as follows: N X[k ] 

N / 2 1

 n0

WN2 nk x[2n] 

N / 2 1

W n0

(2 n 1) k N

x[2n  1] , (65)

and N X[k ] 

N / 2 1

 n 0

WN2 nk x[2n]  WNk

N / 2 1

W n 0

2 nk N

x[2n  1] , (66)

In a similar vein to the equation represented in (5-6), the above equation may be expressed as: X[k ] = F2 [k ]  WNk F2 [k ] X[k +

, n  0,1,..., N 2  1 N ] = F2 [k ]  WNk F2 [k ] 2

(67)

Page 40 of 77

Using the information represnted in the equations above, a VT operating over N vectors can be expressed as two VTs operating over N/2 vectors. The algorithms in (65) and (66) are similar to the radix-2 FFT decimation-in-time and decimation-in-frequency algorithms and are referred to as fast vector transform (FVT) algorithms. Fig. 7 is an illustration of the FVT. x[0] x[2] x[ N − 2] x[1] x[3] x[ N − 1]

N/2vector VT

X[ k ]

N/2vector VT

X[k + N / 2]

WNk

Fig. 7 Radix-2 fast vector transform (FVT) algorithm In VT, decimation can also be reiterated until two vector datas remains. For illustrative purposes, Fig.8 depicts the computation of an N = 8 points VT. We observe that the computation is performed in three stages, beginning with the computations of four twopoint VTs, then two four-point VTs, and finally one eight-point VT. The combination of the smaller VTs to form the larger VT is illustrated in Fig.9 for N = 8 First stage x[0]

x[4] x[2] x[6] x[1] x[5]

x[3] x[7]

2- point VT 2- point VT 2- point VT 2- point VT

Second stage

Third stage (last stage)

X[0]

Combine 2-point VT

X[1] X[2]

Combine 4- point VT Combine 2- point VT

X[3] X[4]

X[5] X[6] X[7]

Fig.8. Three stages in the computation of an N = 8 point VT

Page 41 of 77

X[0]

x[0]

x[4]

W80

X[1]

W82

X[2]

x[2]

W80

W82

x[6]

X[3]

W84

X[4]

x[1]

W80

W84 X[5]

x[5]

x[3]

x[7]

W80

W82

W84

W82

W84

X[6]

X[7]

Fig.9. Eight-point radix-2 FVT algorithm In the FVT algorithms, these algorithms are valid for all VT kernels which are unitarily similar to a diagonal matrix. Observe that a point of b should be multiplieb by WNk ( N / N

*

)

in

FVT as illustrated in Fig.9, where N is the number of vector points in last stage and N * is the number of subvector points in the computation stage in FVT algorithms. For example, W82 in the second stage in Fig.8 is not equal to W41 since the twiddle factors WNk and WN n are not complex exponential. The butterfly in radix-2 VT is shown in Fig .10. a

*

A = a +WNk ( N / N )b WNk ( N / N b

*

)

*

B = a −WNk ( N / N )b

Fig.10. Basic butterfly in radix-2 FVT algorithm

Page 42 of 77

The computational complexity of radix-2 FVT algorithms, in general, is N log 2 N matrixvector multiplications and vector additions. The total number of matrix-multiplications and additions in the FVT algorithms is therefore equal to N log 2 N —including some possible minor multiplications and additions. In these computations, the matrices are M  M in general and the vectors are M  1 ,and all numbers are complex. One matrix-vector multiplication takes M2 complex scalar multiplications and M(M-1) complex scalar additions. Therefore the FVT has a complexity O( M 2 N log 2 N ) . For M=2, the total number of complex scalar multiplications in the FVT is 4 N log 2 N and 2Nlog2N complex scalar additions. In the special case of W  e j 2 / N I , the twiddle factor matrices become diagonal. The multiplication of a diagonal matrix by a vector requires M complex scalar multiplications. In this special case, the FVT algorithms developed here are equivalent to M FFTs operating parallel with total complexity O( MN log 2 N ) . Whereas a FVT is generally computationally more complex than an FFT, it is should be noted that the FFT always requires complex arithmetic, whereas the FVT only requires real arithmetic if the input to the VT is real (for example, if obtained using BPSK modulation) and if the VT kernel is real, M=2,

Radix-2 FFT complexity

Radix-2 FVT complexity

N points

Complex multiplications

Complex multiplications

2 4 8 16 32 64 128 256

( ( NM / 2) log 2 NM ) 4 12 32 80 192 448 1024 2304

2 ( ( M N / 2) log 2 N ) 8 32 96 256 640 1,536 3,584 8,192

Page 43 of 77

512 5120 1024 11264 2048 24576 4096 53248 8192 106496 Table 3: Complexity comparison of complex multiplications

18,432 40,960 90,112 196608 435984 between Radix-2 FFT

and Radix-2 FVT

M=2,

Radix-2 FFT complexity

Radix-2 FVT complexity

N points

Comlex additions

Complex additions

2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 Table

( NM log 2 NM ) ( M ( M  1) N log 2 N ) 8 4 24 16 64 48 160 128 384 320 896 768 2,048 1,792 4,608 4,096 10,240 4,068 22,528 20,480 49,152 45,056 106,496 49,152 229,376 106,496 4: Complexity comparison of complex multiplications between Radix-2 FFT

and Radix-2 FVT

4.2 FVT Radix-4 In Vector Transform, if the number of vector sequences N is a power of four, the VT kernel in VT will have the same properties as the twiddle factor in FFT, which is already shown in the equation (9). We will have the following properties: WNkN/4  ( jI ) k , WNkN/2  (I ) k , WN3kN/4  ( jI ) k ,

(68)

and in much the same way we derive the equation (8), we can have:

Page 44 of 77

N X[k ] 

N 1 4

 x[n]W

kn N

n 0



N 1 4



 x[n]W

n N

kn N



3 N 1 4

 x[n]W

n N

4

kn N

2

N 1 4



N 1



n 3 N

x[n]WNkn 4

N 1 4

N N    WNNk / 4  x  n   WNkn  WNNk / 2  x  n   WNkn  WN3 N / 4 4 2  n 0 n 0 

 x[n]W

kn N

n 0

N 1 2

(69) N / 4 1



 x  n  n 0

3N  kn WN 4 

And then using (68), we derive the following: N X[k ] 

N / 4 1

 n0



N N 3N     k k k  x[n]  (  jI ) x  n  4   (I ) x  n  2   ( jI ) x  n  4        



nk  WN ,( 70)



Next, we decompose the VT data into four N/4 point subvectors. The result is:

N N 3N      0 4kn  x[n]  x  n  4   x  n  2   x  n  4   WN WN        n 0  N / 4 1  N N 3 N   n 4kn    N X[4k  1]    x[n]  jIx  n    Ix  n    jIx  n  WN WN 4 2 4      n 0  N X[k ] 

N / 4 1



N X[4k  2] 





N / 4 1



N N 3N     x[n]  Ix  n  4   x  n  2   Ix  n  4        

n0

N X[4k  3] 

N / 4 1

 n 0





, (71)

2n 4kn  WN WN





N N 3N      x[n]  jIx  n  4   Ix  n  2   jIx  n  4        



3n 4kn  WN WN



And the above equation is expressed by following Fig.11.

Page 45 of 77

x[0] x[4] x[ N − 2] x[1] x[5] x[ N −1] x[0]

x[6] x[ N − 2] x[0] x[7]

x[ N −1]

WN4kn

N/4vector VT

N/4vector VT

WN(4 k +1) n − jI

−I

N/4vector VT

X[ k ]

X[4k +1]

jI

1

−IW (4 k +2) n N

X[4k + 2]

−I jI

N/4vector VT

WN(4 k +3) n

−I − jI

X[4k + 3]

Fig.11. Radix-4 fast vector transform (FVT) algorithm

We verified that aVT operating over N point can be expressed as four VTs operating over N/4 vectors. The algorithm in (70) and (71) are also similar to the radix-4 FFT style algorithms. And thus, the butterfly of radix-4 FVT can be expressed by

Page 46 of 77

*

WNN / N k *

WN2 N / N k *

WN3 N / N k WNN / N WN2 N / N

*

*

( k +N * / 4)

( k +N * / 4)

WN3 N / N

WNN / N

*

*

( k +N * / 2)

WN3 N / N *

( k +N * / 4)

( k +N * / 2)

WN2 N / N

WNN / N

*

*

( k +N * / 2)

( k +3 N * / 4)

WN2 N / N

*

( k +3 N * / 4)

WN3 N / N

*

( k +3 N * / 4)

Fig.12. Butterfly in radix-4 FVT Observe that the radix-4 FVT butterfly is derived from the radix-4 FFT butterfly in Fig.4. To computate recursively in a radix-4 FVT, we should also consider N and N * appropriately in a simiar manner of a radix-2 FVT. In general, FVT radix-4 has (3N/4)log4N vector multiplications and 3Nlog4N additions. Since one matrix-vector multiplication takes M2 complex scalar multiplications and M(M-1) complex scalar additions, the FVT has (3M2N/4)log4N complex scalar

Page 47 of 77

multiplications and 3M(M-1)Nlog4N complex additions as shown in Table 5 and Table 6. Therefore, the total number of complex multiplications and additions in the FVT radix-4 is higher than complexity in the FVT radix-2. M=2,

Radix-2 FVT complexity

Radix-4 FVT complexity

N points

Complex multiplications

Complex multiplications (

2 ( ( M N / 2) log 2 N )

(3M 2 N / 4) log 4 N ) 96

16 80 32 192 64 448 576 128 1024 256 2304 3,072 512 5120 1024 11264 15,360 2048 24576 4096 53248 73,726 Table 5: Complexity comparison of complex multiplications between Radix-2 FVT and Radix-4 FVT

M=2,

Radix-2 FVT complexity

Radix-4 FVT complexity

N points

Complex additions

Complex additions (

( M ( M  1) N log 2 N )

3M ( M  1) N log 4 N ) 192

16 32 64 128 256 512 1024 2048 4096

160 384 896 2,048 4,608 10,240 22,528 49,152 106,496

1,152 6,144 30,720 147,456

Page 48 of 77

Table 6: Complexity comparison of complex additions between Radix-2 FVT and Radix-4 FVT

CHAPTER 5 VT Application of VT to OFDM 5.1 Single-input single-output (SISO) OFDM The term “vector OFDM” is used in some publications to denote multiple- input multipleoutput OFDM systems [18] or OFDM systems where the samples are grouped into vectors and the processing is done on vectors [19]. However in these systems the orthogonal transform is still the DFT. None of the previously known OFDM systems is based on vector transforms, as proposed here and then we describe the proposed VT-OFDM system. First, Let X[k ] , k  0,1,..., N  1 be the vector sequence of the complex information symbols after the bit-to-symbol mapping that must be transmitted. Each vector is of dimension M  1 . The signal to be transmitted is subjected to an N-point inverse vector

Page 49 of 77

transform to obtain the vector sequence x[ n] , n  0,1,..., N  1 . The vector cyclic prefix is to add the last K v vectors at the beginning of the vector sequence x[ n] . The transmitted sequence is obtained via a parallel-to-serial conversion and contains M ( K v  N ) samples. A VT-OFDM transceiver is shown on Fig.13. Note that in conventional OFDM systems the overhead due to the CP is (N+K)/N, but

 K in vector transform-based OFDM the overhead is M ( K v  N ) /MN. Since K v   it is  M  clear that compared to conventional OFDM, in the proposed vector transform-based system the overhead due to the cyclic prefix has been reduced by a factor of M, where M is the vector size. At the receiver first the vector cyclic prefix is removed and then equalization is performed. Equalization is performed in the DFT domain. However, equalization and demodulation are performed separately. After the frequency-domain equalization the signal is transformed back to the time domain via an IFFT. Then a vector sequence is formed and a forward VT is applied. Note that on Fig.13, if the IVT and VT are replaced by the IFFT and FFT, then Fig.6 would be obtained.

X[ k ] form vector sequence

bit-tosymbol

x[n] I V T

x cp [m] Add vector CP

vector sequence / serial

Page 50 of 77

ˆ [k ] X

synchronization

ˆ[n] x

vector form sequence symbol V vector / -to-bit T M sequence M serial M M

Y [k ]

I F F T

M

M

F F T

M

S / P

Remove vector CP

H [k ] channel estimation

Fig.13. A VT-based transmitter and receiver

The VT is a generalization of the DFT: the DFT operates on scalars, and the VT operates on vectors. It has been verified that vector transforms have a fundamental advantage compared with scalar transforms. The proposed system achieves lower bit error rate than the DFT-based OFDM for wireless systems with one transmit and receive antennas. To compare the performance of the proposed system in Fig.13 with the conventional OFDM system illustrated in Fig. 6 computer simulations have been performed. An OFDM system with 64 carriers and a CP of length K=16 was implemented. In the vector transform-based system the vectors were chosen to be of dimension 2 1 , or M=2. To compare both systems at the same data rate, the vector transform is applied to 32 vectors. The symbol duration of both systems is 4  s , including the cyclic prefix. For comparison purposes double side-band transmission is used so that both systems occupy the same bandwidth.

Page 51 of 77

The vector transform kernel is constructed in the following way. First, two integers are selected such that gcd( ai ,32)  1 , i=1,2. Any two integers that are mutually prime with the vector transform length can be used. Therefore, ai can be selected in a random fashion. The j 2 a / N j 2 a / N seed is obtained as V = diag  e 1 , e 2  . Second, the unitary matrix

T

1 2

 e j 2 

 j 2  e

e j 2 

 ,

(72)

e  j 2 

is used, where the real numbers  ,  are random with uniform distribution over the interval [0,1] . The kernel of the vector transform is W  TVT* , as discussed in Chapter 3. It is interesting that, unlike DFT-OFDM, infinitely many kernels can be used. However, it must be noted that once the kernel of the vector transform is determined, it is fixed at the transmitter and at the receiver. In other words, the transmitter and the receiver are designed to use the same kernel. Furthermore, the kernel of the transform does not change from packet to packet to avoid the overhead of sending the kernel to the receiver. The performance of both systems for QPSK and 16 QAM is illustrated in Fig.14. The specific kernel that is used is 1 W 2



e j 2 0.514   j 2 0.8459  e

*

e j 2 0.8459   e j 2 3/ 32   e  j 2 0.514   0

 1 j 2 29 / 32  e  2 0

0.8315 j 0.4844  0.272 j   0.8315 j  0.4844  0.272 j  





e j 2 0.514   j 2 0.8459  e

e j 2 0.8459   e  j 2 0.514 

(73)

The wireless channel that is used is the so-called ETSI channel model ‘A’, which is characterized by 50 ns rms delay spread and delay spread of 390 ns. This is a fixed indoor wireless channel applicable for homes/small offices. We assume that the channel is known by the receiver, but not by the transmitter, and remains constant during one OFDM symbol. Page 52 of 77

The channel estimation phase, during which the receiver learns the channel impulse response, is outside the scope of this paper. From the results in Fig.14 we see that VTOFDM consistently outperforms DFT-OFDM both at low and high SNR values. The performance advantage of VT-OFDM is about 0.6 dB at BER of 10-4. ­2

 

10

­3

Bit Error Rate

10

­4

10

­5

10

DFT­OFDM QPSK VT­OFDM QPSK DFT­OFDM 16 QAM VT­OFDM 16 QAM

­6

10

­7

10   6

7

8

9

10

11 Eb/No

12

13

14

15

16

Fig.14. Performance comparison between the proposed VT-OFDM and DFT-OFDM

5.2 Multiple-input multiple-output (MIMO) OFDM At the moment high data rate wireless systems using multiple transmit and receive antennas, i.e. MIMO systems, are a subject of significant interest [20-25]. MIMO spacedivision multiplexing (SDM) is a technique that achieves a higher throughput by transmitting independent data streams on the different transmit branches simultaneously and at the same carrier frequency. At present MIMO SDM DFT-OFDM is a leading technology for high data rate wireless systems. Page 53 of 77

A MIMO SDM VT-OFDM system can be constructed as proposed in Fig. 15. In the proposed transceiver QAM mapping is performed and a vector sequence of the QAM symbols is obtained. An IVT is performed on the resulting vector sequence and a CP is added. After the IVT the first component of the obtained vector sequence is supplied to the first transmit antenna and the second component to the second transmit antenna. At every discrete-time instance n the transmitter sends a twodimensional complex vector x[n] , and the receiver records a two-dimensional vector y[n] , where x  U* X ,

(74)

y  HU* Xη

.

(75)

Several approaches can be used to perform symbol detection, ranging from ZF to maximum likelihood (ML). With a ZF detection method, an estimate of the transmitted information symbols can be obtained by: ˆ 1  F  I   HU Xη Y  U  FN*  I 2  H N 2 *

form vector sequence

bit-tosymbol

I V T



1 .  X  UHη

Add vector CP

(76)

vector sequence / serial

vector Remove form sequence symbol V processing vector vector / T M unit -to-bit CP M sequence M serial M M

Fig. 15 A MIMO multicarrier modulation system based on vector transform

Page 54 of 77

To compare the performance of the MIMO VT-OFDM system with the corresponding MIMO DFT-OFDM system computer simulations have been performed. The 2  2 DFT-OFDM system has for every transmit antenna 64 carriers and a CP of length K=16. The 2  2 VT-OFDM system uses a VT operating on 64 vectors of dimension 2 1 . Both the VT-OFDM and the DFT-OFDM systems achieve twice the data rate of the SISO systems investigated earlier. The kernel in (57) is for a VT operating on 32 vectors and cannot be used. A new kernel is constructed as follows: *

1  e j 2 0.708 W  2  e  j 2 0.5475

e j 2 0.5475   e j 2 3/ 64   e  j 2 0.708   0

 1  e j 2 0.708   e j 2 29 / 64  2  e j 2 0.5475 0

0.2903 j 0.5084  0.81 j  0.2903 j   0.5084  0.81 j 



e j 2 0.5475   e j 2 0.708 

(77)

Note that encoding in the VT-OFDM system is done jointly over the two transmitter branches, but the two branches can be separated at the receiver because of the properties of the VT. Furthermore, note that when the VT uses the kernel e j 2 / N I and reduces to two FFTs operating on each branch, then the encoding reduces to per-transmitter branch encoding and the entire proposed system reduces to the known MIMO DFT-OFDM system. We consider a flat-fading MIMO Rayleigh channel [20] ,[22], reflecting a richly scattered indoor radio environment. Fig. 16 shows the performance of both systems assuming zero-forcing detection. It is seen that the MIMO DFT-OFDM system, which is equivalent to a VT-OFDM system with the simple kernel e j 2 / N I achieves an inferior performance of approximately 1.5 dB at BER of 10-4, compared with the VT-OFDM system with the kernel given in (77) above. Page 55 of 77

­1

10

 

­2

10

­3

Bit Error Rate

10

­4

10

­5

10

2x2 MIMO DFT­OFDM QPSK 2x2 MIMO VT­OFDM QPSK 2x2 MIMO DFT­OFDM 16 QAM 2x2 MIMO VT­OFDM 16 QAM

­6

10

­7

10   6

7

8

9

10 Eb/No

11

12

13

14

Fig. 16 Performance comparison between MIMO DFT-OFDM and VT-OFDM for transmission over a flat-fading channel

Page 56 of 77

References

[1] S. Mitra, Digital Signal Processing: A Computer Based Approach, New York: McGrawHill, 2006. [2] S. Stearns and R.A. David, Signal Processing Algorithms in MATLAB, New Jersey: Prentice Hall, 1996. [3] B.P. Lathi, Modern Digital and Analog Communication Systems, New York: Oxford University Press, 1998. [4] R.N. Bracewell, “Discrete Hartley Transforms,” J. Opt. Soc. Amer., pp. 1812-1835, Aug. 1984. [5] R.N. Bracewell. The Fourier Transform and Its Applications, New York: McGraw-Hill, 1986. [6] P. Duhamel and M. Vetterli, “Fast Fourier transforms: a tutorial review and a state of the art,” Signal Processing, vol 19, no 4, pp. 259-299, Jan. 1990. [7] K.R. Rao and P.Yip, Discrete Cosine Transform: Algorithms, Advantages, and Applications, Academic Press, 1990. [8] R. N Bracewell, The Hartley Transform, New Yok: Oxford University Press, 1986. [9] R. N Bracewell, The Fourier Transform and its Applications, New York: McGraw-Hill, 2000. [10] T. Cooklev, Wireless communications standards: A study of IEEE 802.11, 802.15, and 802.16, New York: IEEE Press, 2004.

Page 57 of 77

[11] J. Bingham, “Multicarrier modulation for data transmission: An idea whose time has come,” IEEE Commun. Mag., pp. 5-14, May 1990. [12] G. Mandyam, “On the discrete cosine transform and OFDM systems,” in Proc. Int. Conf. Acoust., Speech Signal Process, 2003, pp. 544–547. [13] N. Al-Dhahir, and H. Minn, “A new multicarrier transceiver based on the discrete cosine transform,” in Proc. IEEE Wireless Comm. Networking Conf, 2005, pp. 45-50. [14] W. Li, “FIR filtering using vector transformation and convolution processor,” in Proc. IEEE Int. Symp. on Circuits Syst., 1990, pp. 1223-1226. [15] F. R. Gantmacher, The Theory of Matrices, New York: Chelsea, 1959. [16] W. Li, “Vector transform and image coding,” IEEE Trans. Circuits Syst. Video Technol., vol. 1, no. 6, pp. 297-307, Dec. 1991. [17] W. Li, “On vector transformation,” IEEE Trans. Signal Processing, vol. 41, no. 11, pp. 3114-3126, Nov. 1993. [18] E. Ayanoglu, V.K. Jones and others, VOFDM Broadband Wireless Transmission and Its Advantages over Single Carrier Modulation, ICC, 2001. [19] X. G. Xia, “Precoded and Vector OFDM Robust to Channel Spectral Nulls and With Reduced Cyclic Prefix Length in Single Transmit Antenna Systems,” IEEE Trans. Commun., vol. 49, no. 8, pp. 1363-1374, Aug. 2001. [20] S. Haykin, M. Moher, Modern wireless communications, Prentice-Hall, Upper Saddle River, 2005.

Page 58 of 77

[21] G. J. Foschini and M. J. Gans, “On limits of wireless communications in a fading environment when using multiple antennas,” Wireless Personal Commun., vol. 6, no. 3, pp. 311–335, Mar. 1998. [22] A. van Zelst, and T. C. W. Schenk, “Implementation of a MIMO OFDM-based wireless LAN system”, IEEE Trans. Signal Processing, vol. 52, no. 2, pp. 483-494, Feb. 2004. [23] G. J. Foschini, “Layered space-time architecture for wireless communication," Bell Labs Technical Journal, vol. 1, pp. 41-59, 1996. [24] G. D. Golden, G. J. Foschini, R. A. Valenzuela, and P.W.Wolniansky, “Detection algorithm and initial laboratory results using the V-BLAST space-time communication architecture," Electronics Letters, vol. 35, no. 1, pp. 14-15, 1999. [25] Geert Awater, Allert van Zelst and Richard van Nee, “Reduced Complexity Space Division Multiplexing Receivers”, Proc. IEEE Vehicular Technolgy Conf. 2000, pp. 11-15.

Page 59 of 77

APPENDIX Ⅰ A. Radix-2 FVT Recursive algorithms: 1. ivt2.m (inverse FVT radix 2) function z = ivt2(y,kernel) % checking the size of vector points and dememsion of x variable ss = size(y); vtlen = ss(2); z = ivtfft(y,kernel,vtlen)/sqrt(vtlen); 2. ivtfft.m (sub-function of inverse radix 2 FVT) function x = ivtfft(y,kernel,vtlen) % checking the size of vector points and dememsion of y variable

ss = size(y); len= ss(2); vs=ss(1); if(len==1) x=y(:,1); return end if(rem(len,2)~=0) return else for j=1:len/2 % if vector points are a power of 2, we subdivide the vector points into odd and even yeven(:,j) = y(:,2*j); yodd(:,j) = y(:,2*j-1); end % calling self functions inside a main function, it performs the radix-2 calculation % in all N log 2 N

Page 60 of 77

ivtfftYEven =ivtfft(yeven,kernel,vtlen); ivtfftYOdd = ivtfft(yodd,kernel,vtlen); % computating a radix-2 butterfly for n=1:len/2 x(:,n) = ivtfftYOdd(:,n)+ kernel^(-(n-1)*vtlen/len)*ivtfftYEven(:,n); x(:,n+len/2) = ivtfftYOdd(:,n) - kernel^(-(n-1)*vtlen/len)*ivtfftYEven(:,n); end end 3. vt2.m (radix-2 FVT) function z = vt2(x,kernel) ss = size(x); vtlen = ss(2); z = vtfft(x,kernel,vtlen)/sqrt(vtlen); 4. vtfft.m (sub-function of FVT radix-2) function y = vtfft(x,kernel,vtlen) ss = size(x); len = ss(2); vs=ss(1); if(len==1) y=x(:,1); return; end if(rem(len,2)~=0) return; else for j=1:len/2 %% If vector points are a power of 2, we subdivide the vector points into odd and even xeven(:,j) = x(:,2*j); xodd(:,j) = x(:,2*j-1);

Page 61 of 77

end % Calling self functions inside a main function, it performs the radix-2 calculation % in all N log 2 N vtfftYEven =vtfft(xeven,kernel,vtlen); vtfftYOdd = vtfft(xodd,kernel,vtlen); % computating a radix-2 butterfly for n=1:len/2 y(:,n) = vtfftYOdd(:,n) + kernel^((n-1)*vtlen/len)*vtfftYEven(:,n); y(:,n+len/2) = vtfftYOdd(:,n) - kernel^((n-1)*vtlen/len)*vtfftYEven(:,n); end Non-recursive algorithms: 5. ivtfft2.m (non-recursive inverse FVT radix-2) function [Y] = ivtfft2(X,kernel) %%

checking the size of vector points and dememsion of X variable

ss = size(X); N = ss(2); vs=ss(1); nu=log2(N); NM=N-1; kk=0:NM; %% Rearrange data by bit reversing jj=1; for ii=2:NM k=N/2; while(k<jj) jj=jj-k; k=k/2; end jj=jj+k; if (ii<jj); T=X(:,jj); X(:,jj)=X(:,ii);

Page 62 of 77

X(:,ii)=T; end end %% FFT Calculation for m=1:nu LE=2^m; LE1=LE/2; U=1; W=kernel^(-N/LE); % for IFFT for n=1:LE1 for p=n:LE:N-1 pp=p+LE1; temp=U*X(:,pp); X(:,pp)=X(:,p)-temp; X(:,p)=X(:,p)+temp; end U=U*W; end end Y=X./sqrt(N); 6. vtfft2.m (non-recursive FVT radix-2) function [Y] = vtfft2(X,kernel) % checking the size of vector points and dememsion of X variable ss = size(X); N = ss(2); vs=ss(1); nu=log2(N); NM=N-1; kk=0:NM; %% Rearrange data by bit reversing jj=1; for ii=2:NM k=N/2; while(k<jj) jj=jj-k;

Page 63 of 77

k=k/2; end jj=jj+k; if (ii<jj); T=X(:,jj); X(:,jj)=X(:,ii); X(:,ii)=T; end end %% FFT Calculation for m=1:nu LE=2^m; LE1=LE/2; U=1; % W=kernel^(-N/LE) for IFFT W=kernel^(N/LE); % for FFT for n=1:LE1 for p=n:LE:N-1 pp=p+LE1; temp=U*X(:,pp); X(:,pp)=X(:,p)-temp; % computating the butterfly of radix-2 FVT X(:,p)=X(:,p)+temp; end U=U*W; end end Y=X./sqrt(N); end U=U*W; end end Y=X;

B. Radix-4 FVT 7. ivt4.m ( inverse FVT radix-4) function z = ivt4(y,kernel) % checking the size of vector points and dememsion of y variable

Page 64 of 77

ss = size(y); vtlen = ss(2); z = ivtfft4(y,kernel,vtlen)/sqrt(vtlen); 8 ivtfft4.m (sub-function of inverse FVT radix-4) function x = ivtfft4(y,kernel,vtlen) ss = size(y); len= ss(2); vs=ss(1); if(len==1) x=y(:,1); return; end if(rem(len,2)~=0) return; else for j=1:len/4 y0(:,j) = y(:,4*j-3); % shuffling the vector points y1(:,j) = y(:,4*j-2); % by the method of radix-4 decimation by a factor of 4 y2(:,j) = y(:,4*j-1); y3(:,j) = y(:,4*j); end % using self functions inside a main function, it performs the calculation in N log 4 N fft00 = ivtfft4(y0,kernel,vtlen); fft11 = ivtfft4(y1,kernel,vtlen); fft22 = ivtfft4(y2,kernel,vtlen); fft33 = ivtfft4(y3,kernel,vtlen); % computating the butterfly of radix-4 FVT for n=1:len/4 x(:,n) = fft00(:,n) + kernel^(-(n-1)*vtlen/len) * fft11(:,n) + kernel^(-2*(n-1)*vtlen/len) * fft22(:,n) + kernel^(-3*(n-1)*vtlen/len) * fft33(:,n); x(:,n+len/4) = fft00(:,n) + kernel^(-(n+len/4-1)*vtlen/len) * fft11(:,n) + kernel^(2*(n+len/4-1)*vtlen/len) * fft22(:,n) + kernel^(-3*(n+len/4-1)*vtlen/len) * fft33(:,n); x(:,n+len/2) = fft00(:,n) + kernel^(-(n+len/2-1)*vtlen/len) * fft11(:,n) + kernel^(2*(n+len/2-1)*vtlen/len) * fft22(:,n) + kernel^(-3*(n+len/2-1)*vtlen/len) * fft33(:,n);

Page 65 of 77

x(:,n+3*len/4) = fft00(:,n) + kernel^(-(n+3*len/4-1)*vtlen/len)* fft11(:,n) + kernel^(2*(n+3*len/4-1)*vtlen/len) * fft22(:,n) + kernel^(-3*(n+3*len/4-1)*vtlen/len) * fft33(:,n); end end 9 vt4.m (FVT radix-4) function z = vt4(x,kernel) % checking the size of vector points and dememsion of x variable ss = size(x); vtlen = ss(2); z = vtfft4(x,kernel,vtlen)/sqrt(vtlen); 10 vtfft4.m (sub-function of FVT radix-4) function y = vtfft4(x,kernel,vtlen) % checking the size of vector points and dememsion of x variable ss = size(x); len= ss(2); vs=ss(1); if(len==1) y=x(:,1); return; end if(rem(len,2)~=0) return; else for j=1:len/4 x0(:,j) = x(:,4*j-3); % shuffling the vector points x1(:,j) = x(:,4*j-2); % by the method of radix-4 decimation by a factor of 4 x2(:,j) = x(:,4*j-1); x3(:,j) = x(:,4*j); end

Page 66 of 77

% using self functions inside a main function, it performs the calculation in N log 4 N fft00 = vtfft4(x0,kernel,vtlen); fft11 = vtfft4(x1,kernel,vtlen); fft22 = vtfft4(x2,kernel,vtlen); fft33 = vtfft4(x3,kernel,vtlen); % computating the butterfly of radix-4 FVT for n=1:len/4 y(:,n) = fft00(:,n) + kernel^((n-1)*vtlen/len) * fft11(:,n) + kernel^(2*(n-1)*vtlen/len) * fft22(:,n) + kernel^(3*(n-1)*vtlen/len) * fft33(:,n); y(:,n+len/4) = fft00(:,n) + kernel^((n+len/4-1)*vtlen/len) * fft11(:,n) + kernel^(2*(n+len/4-1)*vtlen/len) * fft22(:,n) + kernel^(3*(n+len/4-1)*vtlen/len) * fft33(:,n); y(:,n+len/2) = fft00(:,n) + kernel^((n+len/2-1)*vtlen/len) * fft11(:,n) + kernel^(2*(n+len/2-1)*vtlen/len) * fft22(:,n) + kernel^(3*(n+len/2-1)*vtlen/len) * fft33(:,n); y(:,n+3*len/4) = fft00(:,n) + kernel^((n+3*len/4-1)*vtlen/len)* fft11(:,n) + kernel^(2*(n+3*len/4-1)*vtlen/len) * fft22(:,n) + kernel^(3*(n+3*len/4-1)*vtlen/len) * fft33(:,n); end end

Page 67 of 77

APPENDIXⅡ VT-OFDM 1.VTbasedOFDM.m %This program requires the following Matlab files: % qpskmod.m for QPSK % giins.m % makeVector.m % ivt.m % vector_guard_ins.m % comb.m % girem.m % qpskdemod.m para=128; % Number of carriers fftlen=128; % FFT length gilen=fftlen/4; % Length of guard interval (points) nd=1;

% Number of information OFDM symbols for one loop

ml=2;

% Modulation level : 2-QPSK, or 4 - 16 QAM

sr=250000; % Symbol rate per second br=sr.*ml; % Bit rate per carrier loop=5;

% Number of EbNo values for which to calculate

BER=zeros(1,loop); % BER for OFDM vt_ber=zeros(1,loop); % BER for vector transform %****************** determine vector transform kernel vt_size = 2; % transform which is 2x2 vtlen = fftlen/vt_size; % vt_guard_len=gilen/vt_size; % vector transform guard length vt_len2 = vtlen + vt_guard_len; cone=sqrt(-1); alfa=rand; beta=rand; % next, a random unitary matrix u2gen=(1/sqrt(2))*[exp(cone*2*pi*alfa) exp(cone*2*pi*beta);... -exp(-cone*2*pi*beta) exp(-cone*2*pi*alfa)]; % The kernel can be obtained using the program kernel %%%% vt_kernel=kernel(vtlen,u2gen);

Page 68 of 77

% In this case we choose two numbers such that gcd(number,vtlen) = 1 a1 = 3; a2 = 63; w=exp(j*2*pi/vtlen); vt_kernel = diag([w^a1 w^a2]); vt_kernel = u2gen'*vt_kernel*u2gen; % Select the initial value of ebn0 and the step size ebn0_start=6; ebstep = 2; %**************** Channel ************* % all of these are appropriate wireless channels % note that the sampling period is 50 ns chanE = [-0.0462-0.9989i 0.3033-0.0600i 0.0762+0.1891i -0.0160+0.0848i ... 0.0356+0.0646i -0.0312+0.0271i 0.0244-0.0062i 0.0017-0.0151i]; channel = chanE; for ebn0=1:loop % loop to calculate BER for different SNR ebno(ebn0)=ebn0_start+(ebn0-1)*ebstep; noe = 0; % Number of bits in error OFDM nod = 0; % Number of transmitted bits OFDM vt_noe = 0; % Number of bits in error VT-based OFDM vt_nod = 0; % Number of transmitted bits VT-based OFDM %************************** main loop part ************************** nloop = ebn0 * 300; % this determines number of loops % more loops are necessary for higher ebn0 (lower BER) % when the coefficient is 300 the program runs for % about 20 minutes for iii=1:nloop %************************** Transmitter ********************************* seldata=rand(1,para*nd*ml)>0.5; % generate random bits paradata=reshape(seldata,para,nd*ml); % Serial/Parallel conversion % [ich,qch] = paradata.*2 - 1; %BPSK [ich1,qch1]=qpskmod(paradata,para,nd,ml); % QPSK %**************************OFDM ************************************ x=ich1+qch1.*i; Page 69 of 77

y=ifft(x); % IFFT ich2=real(y); qch2=imag(y); [ich3,qch3]= giins(ich2,qch2,fftlen,gilen,nd); % Insert CP %******************* Now vector transform-based Transmitter *************** [ich1_vt,qch1_vt]=makeVector(ich1,qch1,vt_size);%Form vector sequence iq_vt=ich1_vt+i*qch1_vt; y_vt=ivt(iq_vt,vt_kernel); % Inverse Vector transform iqvt20 = vector_guard_ins(y_vt,vt_guard_len); % Vector guard sequence iqvt21=reshape(iqvt20,1,vt_size*vt_len2); % Par/Serial ivt22=real(iqvt21); qvt22=imag(iqvt21); %********* Attenuation Calculation OFDM ********* spow=sum(ich3.^2+qch3.^2)/nd./para; attn=0.5*spow*sr/br*10.^(-ebno(ebn0)/10); attn=sqrt(attn); % ********** Channel for OFDM ****************************************** rx_ofdm= conv(channel,ich3+i*qch3); % convolution with channel [ich4,qch4]=comb(real(rx_ofdm),imag(rx_ofdm),attn); % add AWGN %********* Attenuation Calculation VT ********* spow=sum(ivt22.^2+qvt22.^2)/nd./para; attn=0.5*spow*sr/br*10.^(-ebno(ebn0)/10); attn=sqrt(attn); % ************** Channel for vector transform rx_vt = conv(channel,ivt22+i*qvt22); ivt23= real(rx_vt); qvt23= imag(rx_vt); [ivt24,qvt24]=comb(ivt23,qvt23,attn); % add AWGN %*************************** Receiver ***************************** % synchronization and channel estimation are assumed perfect % **************** first OFDM ************************************** [ich5,qch5]= girem(ich4,qch4,fftlen,gilen,nd); % remove CP for OFDM %****************** FFT and equalization ****************** Page 70 of 77

rx=ich5+qch5.*i; fchan=transpose(fft(channel,length(rx))); frx=fft(rx)./fchan; % this is equalization %***************** symbol-to-bit ******************* ich6=real(frx); qch6=imag(frx); [demodata]=qpskdemod(ich6,qch6,para,nd,ml); demodata1=reshape(demodata,1,para*nd*ml); % Parallel-to-serial % ****** DONE WITH OFDM ***************************************** % ***************** NOW VT ****************************************** %

first remove vector CP rx_vt=ivt24(gilen+1:gilen+fftlen)+cone*qvt24(gilen+1:gilen+fftlen);

%

** equalization ** fchan=fft(channel,length(rx_vt)); fvt=fft(rx_vt)./fchan; % this is equalization rvt=ifft(fvt); % this is necessary before the vector transform

%

Make vector sequence [ivt26,qvt26] = makeVector(real(rvt),imag(rvt),vt_size); rvt27=ivt26+i*qvt26; ry_vt=vt(rvt27,vt_kernel); rvt28=reshape(ry_vt,para,[]);

%

% Vector transform % Parallel-serial for the symbols

symbol-to-bit vt_demodata=qpskdemod(real(rvt28),imag(rvt28),para,nd,ml); vt_demodata1=reshape(vt_demodata,1,para*nd*ml); % Parallel-to-serial

%************************** Bit Error Rate (BER) OFDM******************* % instantaneous number of errors and bits noe2=sum(abs(demodata1-seldata)); nod2=length(seldata); % cumulative number of errors and bits noe=noe+noe2; nod=nod+nod2; %************************** Bit Error Rate (BER) VT ********************** % instantaneous number of errors and bits vt_noe2=sum(abs(vt_demodata1-seldata)); vt_nod2=length(seldata); % cumulative the number of errors and bits Page 71 of 77

vt_noe=vt_noe+vt_noe2; vt_nod=vt_nod+vt_nod2; % ************** END VECTOR TRANSFORM ********************** end % for iii=1:nloop %********************** bit error rates *************************** BER(ebn0)=noe/nod; vt_BER(ebn0) = vt_noe/vt_nod; end % for ebn0=1:loop %******************* Plot results **************************** figure; semilogy(ebno,BER, 'ro:'), ... ylabel('Bit Error Rate'), xlabel('Eb/No'); hold on; semilogy(ebno,vt_BER, 'bx:'), legend('BER OFDM','BER VT'); hold off; %******************** end of file *************************** 2. qpskmod.m % Function to perform QPSK modulation %****************** variables ************************* % paradata : input data (para-by-nd matrix) % iout :output Ich data % qout :output Qch data % para : Number of paralell channels % nd : Number of data % ml : Number of modulation levels % (QPSK ->2 16QAM -> 4) % ***************************************************** m2=ml./2; paradata2=paradata.*2-1; count2=0; for jj=1:nd isi = zeros(para,1); isq = zeros(para,1); for ii = 1 : m2

Page 72 of 77

isi = isi + 2.^( m2 - ii ) .* paradata2((1:para),ii+count2); isq = isq + 2.^( m2 - ii ) .* paradata2((1:para),m2+ii+count2); end iout((1:para),jj)=isi; qout((1:para),jj)=isq; count2=count2+ml; end %******************** end of file *************************** 3. giins.m % Add guard interval (cyclic prefix) to an OFDM symbol % %****************** variables ********************************************* % idata : Input Ich data % qdata : Input Qch data % fftlen : FFT length % gilen : Length of guard interval (number of points) % nd : number of OFDM symbols processed simultaneously (should be =1) % iout : Output Ich data % qout : Output Qch data % ************************************************************************* function [iout,qout]= giins(idata,qdata,fftlen,gilen,nd); idata1=reshape(idata,fftlen,nd); qdata1=reshape(qdata,fftlen,nd); idata2=[idata1(fftlen-gilen+1:fftlen,:); idata1]; qdata2=[qdata1(fftlen-gilen+1:fftlen,:); qdata1]; iout=reshape(idata2,1,(fftlen+gilen)*nd); qout=reshape(qdata2,1,(fftlen+gilen)*nd); %******************** end of file *************************** 4. makeVector.m % Make a vector sequence from a scalar sequence % %****************** variables ******************************************

Page 73 of 77

% ich : Input Ich data % qch : Input Qch data % vec_len : vector length % vec_i : Output vector Ich % vec_q : Output vector Qch % ********************************************************************** function [vec_i,vec_q] = makeVector(ich, qch, vec_len); len = length(ich); % i and q must be of the same length mm = len/vec_len; vec_i=zeros(vec_len,len/vec_len); vec_q=zeros(vec_len,len/vec_len); for jj = 1:vec_len vec_i(jj,:) = transpose(ich(jj:vec_len:len)); vec_q(jj,:) = transpose(qch(jj:vec_len:len)); end 5. ivt.m %****************** variables ************************* %y : input sequence of vectors % kernel : kernel of the vector transform %x : output sequence of vectors %****************************************************** function x = ivt(y,kernel) ss = size(y); len = ss(2); vs=ss(1); % vector size for k=1:len x(:,k)=zeros(vs,1); for n=1:len x(:,k) = x(:,k) + kernel^(-(n-1)*(k-1)) * y(:,n); end x(:,k) = x(:,k) / sqrt(len); end 6.vt.m % Forward vector transform

Page 74 of 77

%****************** variables ************************* % kernel : kernel of the vector transform %x : input sequence of vectors %y : output sequence of vectors %****************************************************** function y = vt(x,kernel) ss = size(x); len = ss(2); vs=ss(1); % vector size for k=1:len y(:,k)=zeros(vs,1); for n=1:len y(:,k) = y(:,k) + kernel^((n-1)*(k-1)) * x(:,n); end y(:,k) = y(:,k) / sqrt(len); end 7. vector_guard_ins.m %****************** variables ************************* % vec_in : Input vector sequence % guard_len : Length of guard interval (number of points) % vec_out : Output vector sequence % ***************************************************** function vec_out = vector_guard_ins(vec_in, guard_len); ss=size(vec_in); len = ss(2); vec_out(:,1:guard_len)=vec_in(:,len-guard_len+1:len); vec_out(:,guard_len+1:len+guard_len)=vec_in; %******************** end of file *************************** 8 comb.m % Add additive white gausian noise %****************** variables ************************* % idata : input Ich data % qdata : input Qch data

Page 75 of 77

% attn : attenuation level caused by Eb/No or C/N % iout output Ich data % qout output Qch data %****************************************************** function [iout,qout] = comb (idata,qdata,attn) iout = randn(1,length(idata)).*attn; qout = randn(1,length(qdata)).*attn; iout = iout+idata(1:length(idata)); qout = qout+qdata(1:length(qdata)); % ************************end of file*********************************** 9. girem.m % Remove guard interval (cyclic prefix) from an OFDM symbol % %****************** variables ************************* % idata : Input Ich data % qdata : Input Qch data % fftlen2 : FFT length + GI length % gilen : Length of guard interval (number of points) % nd : number of OFDM symbols % iout : Output Ich data % qout : Output Qch data % ***************************************************** function [iout,qout]= girem(idata,qdata,fftlen2,gilen,nd); idata2=reshape(idata,[],nd); qdata2=reshape(qdata,[],nd); iout=idata2(gilen+1:gilen+fftlen2,:); qout=qdata2(gilen+1:gilen+fftlen2,:); %******************** end of file *************************** 10 qpskdemod.m % Function to perform QPSK demodulation

Page 76 of 77

function [demodata]=qpskdemod(idata,qdata,para,nd,ml) %****************** variables ************************* % idata :input Ich data % qdata :input Qch data % demodata: demodulated data (para-by-nd matrix) % para : Number of paralell channels % nd : Number of data % ml : Number of modulation levels % (QPSK ->2 16QAM -> 4) % ***************************************************** demodata=zeros(para,ml*nd); demodata((1:para),(1:ml:ml*nd-1))=idata((1:para),(1:nd))>=0; demodata((1:para),(2:ml:ml*nd))=qdata((1:para),(1:nd))>=0; %******************** end of file ***************************

Page 77 of 77