Sparse Discrete Fractional Fourier Transform and Its Applications

parameter estimation method for linear amplitude modulated chirp signals based on Discrete Fractional Fourier Transform Cross-Layer Secure Communication Model
Dr.TomHunt Profile Pic
Dr.TomHunt,United States,Teacher
Published Date:28-11-2017
Your Website URL(Optional)
Performance of Discrete Fractional Fourier Transform Classes in Signal Processing Applications A thesis submitted in fulfillment of the requirement for the award of degree of Doctor of Philosophy Submitted by KULBIR SINGH Supervisor Prof. RAJIV SAXENA Head, Department of Electronics Engineering Madhav Institute of Technology and Science, Gwalior (M.P.) India Formerly: Head, Department of Electronics and Communication Engineering Thapar Institute of Engineering and Technology, Patiala (Punjab) India DEPARTMENT OF ELECTRONICS AND COMMUNICATION ENGINEERING THAPAR INSTITUTE OF ENGINEERING AND TECHNOLOGY, PATIALA (Deemed University)ABSTRACT Given the widespread use of ordinary Fourier transform in science and engineering, it is important to recognize this integral transform as the fractional power of FT. Indeed, it has been this recognition, which has inspired most of the many recent applications replacing the ordinary FT with FrFT (which is more general and includes FT as special case) adding an additional degree of freedom to problem, represented by the fraction or order parameter a. This in turn may allow either a more general formulation of the problem or improvement based on possibility of optimizing over a (as in optimal wiener filter resulting in smaller mean square error at practically no additional cost). The FrFT has been found to have several applications in the areas of optics and signal processing and it also lead to generalization of notion of time (or space) and frequency domains which are central concepts of signal processing. In every area where FT and frequency domain concepts are used, there exists the potential for generalization and implementation by using FrFT. With the advent of computers and enhanced computational capabilities the Discrete Fourier Transform (DFT) came into existence in evaluation of FT for real time processing. Further these capabilities are enhanced by the introduction of DSP processors and Fast Fourier Transform (FFT) algorithms. On similar lines, so there arises a need for discretization of FrFT. Furthermore, DFT is having only one basic definition and nearly 200 algorithms are available for fast computation of DFT. But when FrFT is analysed in discrete domain there are many definitions of Discrete Fractional Fourier Transform (DFrFT). These definitions are broadly classified according to the methodology of computation adopted. ivIn the current study the various class of DFrFT algorithms are studied and compared on the basis of computational complexity, deviation factor, properties of FrFT retained by particular class and constraints on the order or fraction parameter a etc. As discussed earlier, the FrFT has found a lot of applications in signal processing, so the DFrFT is used for some of the one-dimensional and two-dimensional applications in the present work. The one dimensional applications discussed include filtering using window functions, optimal filtering of faded signals, beamforming for the mobile antenna and optimal beamforming in faded channels. In the two dimensional applications the image processing for compression and encryption are discussed. Window functions have been successfully used in various areas of filtering, beam forming, signal processing and communication. The role of windows is quite impressive and economical from the point of view of computational complexity and ease associated with its application. An attempt has been made to evaluate the window functions in FrFT domain. The study of side lobe fall of rate (SLFOR), main side lobe level (MSLL) and half main lobe width (HMLW) for window functions are done for different values of a. A new FrFT based Minimum Mean Square Error (MMSE) filtering technique is also suggested and it is also established that the results are much better as compared to FT. The signals in real life are non-stationary random processes. This may be attributed to the randomness of signals due to variation in amplitude and phase and associated Doppler shift, delay spread etc (as in the case of mobile sources and receivers). The multipath environment of mobile communication also makes the signal non-stationary due to changing spatial position with time. In these type of applications, where signal and noise both are non-stationary (time–frequency varying) FrFT is a powerful tool in vdesigning an optimal filter. The proposed filter is compared with time and frequency domain filtering. This algorithm is also used as an optimal beamformer for mobile and wireless communication, as in this is also an example of non-stationary signal and noise. This beamforming technique also works more efficiently for faded signals. The FrFT and FrCT are used for image compression and the results are much better than FT. It is also shown that in compression the FrFT gives better results than FrCT. The image encryption is also done using FrCT and phase masking. This technique gives an advantage of additional keys i.e. order parameter of the transform. The number of these additional keys can be further enhanced by using repetition the FrCT with various orders. The merits of FrFT are that it is not only richer in theory and more flexible in application but the cost of implementation is also low as it can be implemented with same complexity as that of conventional Fast Fourier transform. The FrFT provides additional degree of freedom to the problem as parameter a gives multidirectional applications in various areas of optics and signal processing in particular and physics and mathematics in general. The most important aspect of the FrFT is its use in time varying signals for which the FT fails to work. In past few years researchers are trying to fractionalize every transform so as to formulate a more general problem. It is obvious this that an era has been opened up for a generalization of the problems to get better results in every area of engineering by using Fractional Domains of a Transform opening up a new signal processing technique may be referred as FRACTIONAL SIGNAL PROCESSING. viThe advances in FrFT are multidimensional but still it is interesting to note that the algebra of Fractional Fourier domain is far from complete at present and there are several unforeseen identities and results to be derived. viiCHAPTER1 INTRODUCTION 1.1 PREAMBLE Fourier analysis, given by Jean-Baptiste-Joseph Fourier (1768-1830), is a frequently used tool in signal processing and analysis. Fourier Transform (FT) finds applications in many areas of science and engineering. Optics, physics, acoustics, statistics, heat conduction and diffusion, electrical engineering, antenna and array processing are some areas where this transform is widely applicable. It is a linear transform used to solve linear system problems. Impressed by the capability of this transform Wittaker placed it amongst the three most important mathematical th advances of the last quarter of the 19 century. However, the FT is unable to solve certain classes of ordinary and partial differential equations of optics, signal processing and quantum mechanics 1. Looking into the applicability of FT the concept of fraction was introduced in the FT in the year 1929 2 and lead to the development of fractional Fourier transform (FrFT). On tracing the th history of fractional concept it is found that in 17 century Bernoulli (1695) formulated a question about the meaning of a non-integer order derivative. This was the beginning of the fractional calculus which is the base of the continuous time fractional systems described by the fractional 1differential equations. Since then, the concept of fractional calculus has evolved in pure mathematics and developed by famous mathematicians. Inspite of the progress in pure mathematics this concept had been applied in applied sciences only in 1920’s. Furthermore, it is only in the last three decades that the applications of fractional calculus have emerged in engineering field which lead to a significant impact in several areas and attracted the scientific and technical community to the fractional objects. Presently, the related themes of active research are Brownian motion, discrete time fractional linear systems, fractional delay filtering, fractional splines and wavelets. Also, worth mentioning is the fact that earlier most of the reported applications on FrFT were in the field of optics. Recently, the FrFT has also made inroad in the digital signal analysis and processing with filtering, encoding, watermarking, phase retrieval being the key application arenas 3. 1.2 HISTORICAL PERSPECTIVE OF FrFT The generalization of FT called FrFT was first introduced in 1980 by Namias 4, apparently unaware of the previous work done by various researchers which dates back to 1929. All the authors discussed the FrFT in a broader context and not by the same name, although the idea was same. Mustard in 1987 5-7 did a lot of work taking Condon 8 and Bargmann 9 as his base without citing the Namias work. Moreover, FrFT is a special case of linear canonical transform (LCT) and all the work previously done on LCT covers FrFT in some sense. In some cases FrFT 2has not been given any special attention but in other cases the authors have commented on it as a one-parameter sub-class with the FT as a special case. Many variant, relatives or essentially equivalent forms of FrFT can be found under different guises but it is practically impossible to trace all of them 3. A lot of work is done by Mendlovic, Ozaktas and Lohmann in years 1993 10-13, 1994 14, 1995 15-16 and they established that various definitions of FrFT are equivalent to each other. Almedia, in 1993 17, independently reintroduced the transform as ‘angular’ FT. Pei et al. also did a lot of work in 1990’s to consolidate FrFT 18-27. Furthermore, a general definition of FrFT for all classes of signals (one-dimensional and multidimensional, continuous and discrete, periodic and non-periodic) is given by Cariolario et al. in 28. With the advent of computers the discrete Fourier transform (DFT) came into existence to evaluate FT of discrete time signals. This capability has been further enhanced by the introduction of DSP processors and fast Fourier transform (FFT) algorithms. On similar lines, there aroused a need for discretization of FrFT. DFT is having only one basic definition and nearly 200 FFT algorithms are available for fast computation of DFT. But when FrFT is analyzed in discrete domain there are many definitions of discrete fractional Fourier transform (DFrFT) 18-23, 27, 29-35. It has also been established that none of these definitions satisfy all the properties of continuous FrFT 24. Santhanam and McClellan first reported the work on DFrFT in 1995 30. Thereafter, within a short span of time many definitions of DFrFT came into existence and these definitions are classified according to the methodology used for calculations in 2000 by Pie et al. 24. 3 The FrFT has been found to have several applications in the areas of optics 10-12, 36- 50 and signal processing 51-70 and it also leads to generalization of notion of space (or time) and frequency domains, which are central concepts of signal processing. Applications of FrFT have been reported in the solution of differential equations3, 4, 71, optical beam propagation and spherical mirror resonators 40, optical diffraction theory 49, quantum mechanics 4, statistical optics 3, 38, 39, 47, optical system design and optical signal processing 42-45, signal detectors 64, 68, correlation 38, 64 and pattern recognition 52, space or time variant filtering 54, 56, 59, 63, 67, 70, multiplexing 72, signal and image recovery 51, 57- 58, image restoration and enhancement 60, study of space or time–frequency distributions (TFD’s) 26, 51, 56, etc. Thus, it can be said that the FrFT can replace the FT and related concepts. 1.3 FRACTIONAL OPERATIONS Breaking up an entity into fractions represents a relatively major conceptual leap. For example, 4 the fourth power of 3 can be defined as 3 = 3×3×3×3 , but it is not obvious from this definition 3.5 that how 3 is defined. It must have taken sometime before the common definition 3.5 7/2 7 3 =3 = 3 emerged. Similarly, the first and second derivatives of the function f (x) are 2 2 df(x) d f(x) d df(x) ddf(x)/dx d ⎡ ⎤ ⎛ ⎞ commonly denoted by: and = = =⎜ ⎟ f(x), ⎢ ⎥ dx dx dx dx dx dx ⎣ ⎦ ⎝ ⎠ respectively. Similarly, higher order derivatives can be defined in the same way. But what is meant by the th 2.5 derivative of a function is not clear from the above definition. Let F(x ) denote the FT of a 4n d f (x) th n f (x) . The FT of the n derivative of f (x) i.e., is given by (i2πx ) F(x ), for any a a n dx positive integer n. The generalized property is obtained by replacing n with the real order a and a d f (x) th th take it as the a derivative of f (x) . Thus to find , the a derivative of f (x) , calculate the a dx a inverse Fourier transform of (i2πx ) F(x ) . a a Above examples deal with the fractions of an operation performed on an entity, rather than 0.5 0.5 fractions of the entity itself. The 3 is the square root of the integer 3. The function f (x) is 0.5 0.5 d f (x) df (x) ⎛ ⎞ th the square root of the function f (x) . But is the 0.5 derivative of f (x) , with ⎜ ⎟ 0.5 dx dx ⎝ ⎠ d being the square root of the derivative operator . Bracewell 1 has shown that the fractional dx derivatives can be used to characterize the discontinuities of certain functions used in optics and signal processing. During the last two decades, the process of going from the whole of an entity to fractions of it underlies several interesting applications such as fractal objects, fuzzy logic and fractional signal processing. The fractional signal processing leads to a more general formulation of the problems that were solved by the integral transforms in the early days, because of the additional degree of freedom available with the designers. This in turn allows better performance or greater generality based on possibility of optimization over a fractional variable parameter a. The FrFT founds several applications in signal processing. Particularly, windowing, filtering, optimal filtering are the key areas in one-dimensional signal processing 59-60, 73. Now, researchers are trying to get better results using FrFT as a tool. The capability of the FrFT is to significantly reduce the error as compared to FT for specific nature of degradation and noise 5especially in Doppler shift and chirp signals 55, 67, 72. A fast algorithm for computation of FrFT of order (N log N) is available so that real time implementation can easily be made without 2 additional cost 24, 29. One-dimensional fractional signal processing can be further extended to two-dimensional and multi-dimensional fractional signal processing. Their application includes image compression 74, image encryption 75, beamforming 55, digital watermarking 76, tomography 56, 62, image restoration 60 etc. The properties and implementation of two-dimensional FrFT has been reported by Sahin et al. 36-37, 77 and Edren et al. 45, 63. Sahin et al. have generalized the two-dimensional FT into the two-dimensional separable FrFT and two-dimensional separable canonical transform. In another reported work Sahin et al. also generalized it into the two- dimensional non-separable FrFT with four parameters. Pei and Ding have introduced the two- dimensional affine generalized FrFT 25. The FrFT has been used efficiently in image compression with better results in comparison to FT 74. The image encryption is also done using FrFT and phase masking 75. This technique gives an advantage of additional keys, i.e., order parameter of the transform. The number of additional keys can be further enhanced by repetition of the FrFT with various orders which leads to the multi-dimensional fractional signal processing. From the implementation point of view discretized version of FrFT known as DFrFT is used in all of the above mentioned one- and two-dimensional FrFT signal analysis. A good review work regarding different types of DFrFT is reported by Pei et al. 24. In this article a new type of DFrFT which is unitary, reversible, flexible and has closed form analytical current DFrFT’s that 6were similar to the continuous FrFT but it puts certain constraints on the signal 24.With this brief presentation of chronological development of FrFT and its vast application expression was introduced. But, this DFrFT looses an important property of additivity. They also extended the DFrFT into the discrete affine Fourier transform (DAFT) and derived two types of DFrFT and DAFT. The closed form expression has the lowest complexity among all domain, the problems, attempted and included, in this study are formulated in the next section. 1.4 PROBLEM FORMULATION The work in this thesis focuses on following aspects and applications of DFrFT:- 1. The available FrFT definitions are studied and equivalence between them has been verified with simulation studies. The properties of FrFT are also confirmed and demonstrated graphically. 2. The available classes of DFrFT have been studied and their comparative study has been carried out. 3. DFrFT has been applied and analysed in one dimensional time-frequency varying signal applications. Optimal filtering of faded signals, beamforming for the mobile antenna and optimal beamforming in faded channels have been selected as particular applications. 4. Applications of DFrFT in image compression and image encryption are discussed. 5. Two-dimensional signal processing applications using discrete fractional cosine transform (DFrCT) have been attempted and their performance with DFrFT is compared. Also a comparison has been done with wavelet transform. 71.5 ORGANISATION OF THE THESIS The first chapter gives the historical perspective of FrFT and an introduction to fractional operations. The limitation of FT to solve certain classes of ordinary and partial differential equations of quantum mechanics, optics and signal processing is discussed. It is also established that FrFT is a powerful tool for the analysis of time varying signals with applications in one- and two-dimensional signal processing. In second chapter so far reported definitions of FrFT are reviewed with their brief introduction. The properties of FrFT are discussed and illustrated using Riemann function. In third chapter the description of DFrFT and its historical development is given. The various classes of the DFrFT are discussed and a comparative study is done. It is established that the eigenfunction of DFrFT is the best one, although it lacks closed form expression for precise calculations. Characterization of window functions in fractional Fourier domain is also done in this chapter. Applications of DFrFT in one dimensional signal processing are discussed in chapter four. Optimal filtering of faded signals, beamforming for the mobile antenna and optimal beamforming in faded channels are the applications included in this chapter. The optimal filtering in time and frequency domain becomes a special case of optimal filtering in the FrFT domain. This method is extremely useful for the signals having Doppler shift because of moving source or receiver. It has also been shown that using FrFT domain filtering the mean square error (MSE) gets reduced in case of moving sources and receivers. Chapter five contains the two dimensional applications of DFrFT and DFrCT. Compression and encryption of images are the applications undertaken. The performances of the two transforms for these applications are compared. Also a comparison with wavelet transform is accomplished. The DFrFT and DFrCT 8give better results for image compression and image encryption respectively. It has also been shown that for very high compression ratios, FrFT gives better results for compression than wavelet transform. The last chapter concludes with critical discussion of results of the investigations carried out. Important observations are made and useful conclusions are drawn along with a discussion on future scope of this work. 9CHAPTER2 FRACTIONAL FOURIER TRANSFORM 2.1 INTRODUCTION The FrFT is a generalization of FT, which is richer in theory, flexible in application, and implementation cost is at par with FT. With the advent of FrFT and related concept, it is seen that the properties and applications of the conventional FT are special cases of those of the FrFT. However, in every area where FT and frequency domain concepts are used, there exists the potential for generalization and implementation by using FrFT. In this chapter, the basic concept and properties of FrFT are described. In 1929, Wiener, discussed a transformation kernel whose eigenfunctions are Hermite- Gaussian functions and it has eigenvalues which are of more general form than of ordinary FT eigenvalues 2. The work by Wiener motivated Weyl to develop the integral transform relationship for providing a basis of developments in group theory and quantum mechanics. In 1937, Condon, discussed the generalization of FT to a continuous group of Functional transformation. Kober, in 1939, discussed Fractional Fourier and Hankel transform. He also provided general framework for consideration of other transforms in the same manner. In 1956, Gujnand, worked on the relationship between fractional transform and matrices. Bragmann in 1961 citing the work by Condon, and Bruijn in 1973 referred to Kober, briefly discussed the transform in a much broader context. Khare, in 1971, gave a generalized transform in a physical context, 10which includes FrFT 3. All these authors discussed the FrFT in a broader context and not by the same name, although the idea was same. In 1980, Namias discussed FrFT as the fractional powers of classical FT and gave several of its properties 4. Mustard, in 1987, did a lot of work taking Condon and Bragmann as his base without citing Namias 5-7. He discussed the relationship of FrFT to time-frequency distribution (Wigner distribution) and new classes of uncertainty relationships which are invariant under FrFT. Many variants, relatives or essentially equivalent forms of FrFT are found under different guises but it is practically impossible to trace all of them. In 1990’s a lot of work is done by Mendlovic, Ozaktas, Lohmann, Almedia, Pei, Yeh, and Tseng to consolidate FrFT 3. 2.2 DEFINITIONS OF FrFT As discussed earlier, FrFT is defined in many different ways. To have a complete understanding of the transform all definitions are discussed in detail, and thereafter established that they are equivalent to each other. All definitions have different physical interpretations which is very useful in a variety of applications. These definitions of FrFT are discussed below. 2.2.1 Linear Integral Transform It is the most concrete and direct form of FrFT and is specified as a linear transform kernel. th The a order FRFT of a function f(x) is a linear operation defined by the integral 78 ∞ a a a F f(x)= K (x,x )f(x)dx = f (x ) (2.1) where, a a ∫ -∞ 2 a 2 K(x,x)=Aexpiπ(xcotα-2xxcscα+x cotα) is FrFT kernel that transforms the a α a a aπ a function f(x) in a domain x to a function f (x ) in another domain x and α = . f (x) is a a a 2 11a a function of independent variable x and f (x ) is the function of independent variable x . F is a a the FrFT operator which acts on f (x) to transform the function from an arbitrary domain to th arbitrary plus a domain. A = 1- i cotα whena≠2j. α a K(x,x)=δ(x-x) whena=4j and a a a K (x, x ) =δ (x + x ) whena = +2j, where j is an integer. a a 0 In case the arbitrary domain is a = 0, i.e. F f (x) = f (x) = f (t) , the variable x becomes (time variable) and f(x) becomes f(t). In case the arbitrary domain is a = 1, t 1 F f(x)=Ff(x)= f(f) , the variable x becomes f (frequency) and f (x) becomes f ( f ) i.e. f (.) is a function of f frequency. th th The a order transform is also referred as α order transform. The square root is defined so that the argument of the result lies in the interval (-π /2,π /2) . The A can be written for the α interval 0 a 2 (0 α π ) without any ambiguity as 71 -iπ sgn( α ) / 4-(α / 2) e A = (2.2) α sin α where, sgn(.) is the signum function. This definition is a one parameter sub-class of LCT. The transform is linear but not shift invariant (unless a = 4 j) , since the kernel is not the function of (x - x ) only. First of all the cases a 4 j 4 j±2 are examined when a is an integer. As j is an arbitrary integer, it is noted that F = F a corresponds to an identity operator and the parity operator, where F is FrFT operator. The several cases of varying j are discussed below: 12i) Whenα = 0, i.e., a = 0, the transform kernel reduces to identity operation. This is attributed to the fact that as α approaches 0, sin α approaches α and cot α approaches 1/α. Using the fact that in sense of generalized functions 71 1 2 (- x / iε ) Lim e = δ (x) (2.3) iπε ε → 0 so that the (2.1) reduces to ∞ 0 (2.4) F f (x) = δ (x - x ) f (x)dx = f (x) a ∫ -∞ ii) Whenα = π/2, i.e., a = 1 ∞ 1 1 F f (x) = f (x)exp(-ixx )dx (2.5) a ∫ 2π -∞ i.e., the ordinary FT. A similar procedure can be applied to case iii) When α = π i.e., a = 2 and the result turns out to be ∞ 2 F f (x) = δ (x + x ) f (x)dx = f (-x) (2.6) a ∫ -∞ So, for an angle from 0 to 2π, the value of a varies from 0 to 4 and the transform kernel is periodic with a period equal to 4. Table-2.1 gives the different kernels of FrFT for variation of a from 0 to 4. Thus, most of the attention is limited in the interval a∈(-2,2(orα∈(-π,π) and sometimes a∈0,4) (or α∈0,2π ) ) 29. 13Table-2.1: Various kernels available with FrFT. Value of Kernel Fractional operator Operation on α = a parameter a signal π/2 0 4 a = 0 or a = 4 Identity α = 0 or δ (x - x ) F = F = I a operator α = 2π 1 a = 1 Fourier α = π/2 exp(ixx ) F = F a operator 2 a = 2 Time inversion α = π δ (x + x ) F = P a operator 3 2 -1 a = 3 Inverse Fourier α = 3π/2 exp(-ixx ) F = FF = FP = PF = F a operator 2.2.2 Fractional Powers of Fourier Transform th The a order FrFT operation is defined as the fractional power of the FT operation. Let ψ l (or ψ (x)) denote the Hermite-Gaussian signal (or function) which are eigensignals (or l eigenfunctions) of the ordinary FT operation with respective eigenvalues λ . These eigenvalues l are known to constitute an orthogonal basis for the space of well-behaved finite-energy signals (functions). The FrFT operation defined is linear and satisfies 71 a a a -ilπ / 2 -ialπ / 2 Fψ (x) = λ ψ (x) =(e ) ψ (x) = e ψ (x) (2.7) l l l l l This definition completely defines the FrFT by specifying its eigenfunctions and eigenvalues. It depends on the particular set of eigenfunctions chosen as well as on the particular th way in which the a power of the eigenvalues are chosen. Several properties of FrFT (like special cases, index additivity property) are deduced easily from this definition in comparison to the linear integral transform definition 4, 71. 14The given signal (function) is first expanded as a linear superposition of eigenfunctions of the FrFT, to calculate the fractional transform of a function f (x) as: ∞ f (x) = C ψ (x) (2.8) ∑ l l l =0 where, C =ψ (x ) f (x )dx l l a a a ∫ th By taking the a order Fourier transform on both sides of (2.8) ∞ ∞ a -ialπ / 2 -ialπ / 2 F f (x) = e C ψ (x) = e ψ (x)ψ (x ) f (x )dx (2.9) ∑ l l ∑ l l a a a ∫ l =0 l =0 Comparing (2.9) with (2.1), yields ∞ a -ialπ / 2 K (x, x ) = e ψ (x)ψ (x ) (2.10) ∑ a l l a l=0 The equation (2.10) is known as singular value decomposition (or spectral expansion) of the kernel of FrFT 3. It is one of the properties of the Hermite-Gaussian functions. Hence, it can be said that the Hermite–Gaussian functions are indeed the eigenfunctions of the transform defined by (2.1) with the eigenvalues given by (2.7). It is also known that ψ (x) and ψ (x) are 0 1 eigenfunctions with eigenvalue 1 and exp(-iaπ /2). Then by using the recurrence relations of Hermite-Gaussian polynomials 11 H (x) = 2xH (x) - 2lH (x), (2.11) l+1 l l-1 dH(x) l =2lH(x) (2.12) l-1 dx By assuming that the same result holds for (l - 1), l and (l + 1), therefore, A A l+1 l +1 ψ (x) = 2 2π xψ (x) - 2l ψ (x), (2.13) l +1 l l-1 A A l l -1 15