Fractional Fourier Transform (FRFT) and Linear Canonical Transform (LCT) in Signal Processing

Introduction of Fractional Fourier Transform (FRFT) Speaker: Chia-Hao Tsai Research Advisor: Jian-Jiun Ding Digital Image and Signal Processing Lab Graduate Institute of Communication Engineering National Taiwan University 10/23/2009 1

Outlines Introduction of Fractional Fourier Transform (FRFT) Introduction of Linear Canonical Transform (LCT) Introduction of Two-Dimensional Affine Generalized Fractional Fourier Transform (2-D AGFFT) Relations between Wigner Distribution Function (WDF), Gabor Transform (GT), and FRFT 10/23/2009 2

Outlines (cont.) Implementation Algorithm of FRFT /LCT Closed Form Discrete FRFT/LCT Advantages of FRFT/LCT contrast with FT Optics Analysis and Optical Implementation of the FRFT/LCT Conclusion and future works References 10/23/2009 3

Introduction of Fractional Fourier Transform (FRFT) The FRFT: a rotation in time-frequency plane. : a operator Properties of - =I: zero rotation - : FT operator - : time-reverse operator - : inverse FT operator - =I:2 rotation - : additivity (I: identity operator) 10/23/2009 R R 0 R /2 R R 3 /2 R 2 R + R = R R 4

Introduction of FRFT (cont.) Definition of FRFT: x X = R = ( ) u ( ( )) x t O F = ( ) x t ( , ) t u dt K 1 cot 2 j 2 2 u t , if isn't a multiple of cot cot csc j j jut ( ) x t dt e e e 2 2 = ( ), if is multiple of 2 ), if is multiple of 2 t + x t ( x ( : Kernel of FRFT) ( , ) t u K 10/23/2009 5

Introduction of FRFT (cont.) = 0 0.5 When : identity When : FT When isn t equal to a multiple of , the FRFT is equivalent to doing times of the FT. -when doing the FT 0.4 times. -when doing the FT 0.5 times. -when doing the FT 2/3 times. /3 = = = 0.5 /(0.5 ) = = 0.2 0.25 10/23/2009 6

Introduction of FRFT (cont.) An Example for the FRFT of a rectangle (Blue line: real part, green line: imaginary part) 10/23/2009 7

Introduction of Linear Canonical Transform (LCT) The LCT is more general than the FRFT. The FRFT has one free parameter ( ), but the LCT has four parameters (a, b, c, d) to adjust the signal. The LCT can use some specific value to change into the FRFT. 10/23/2009 8

Introduction of LCT (cont.) Definition of LCT: , , ,( ) a b c d u F ( F ) ( ) , , , a b c d = O x t 1 1 b j d j a 2 2 j ut ( ) , x t dt b 0 u u e e e 2 2 b b 2 j b = jcdu 2 = ( ), 0 d x du b e 2 with the constraint ad bc = 1 10/23/2009 9

Introduction of LCT (cont.) Additivity property: e g a c ( ) x t ( ) x t ( F ) ( F ) ( F ) , , , , , , a b c d , , , e f g h a b c d = O O O 2 2 2 2 1 1 1 1 where = a c b d b d f h 2 2 1 1 2 2 1 1 Reversibility property: ( ) F O ( ) x t ( F ) , , , , , , a b c d d b c a = ( ) x t O 10/23/2009 10

Introduction of LCT (cont.) 10/23/2009 11

Fractional / Canonical Convolution and Correlation FT for convolution: ( ) ( ) ( ) = ( ) y t ( ) ( ) IFT FT x t FT h t FT for correlation : ( ) ( ) ( ) = ( ) y t ( ) ( ) IFT FT x t FT h t 10/23/2009 12

Fractional / Canonical Convolution and Correlation (cont.) Fractional convolution (FRCV): ( ( ) F F y t O O = ( ) x t h t = transformed domain ( ) ( ) u Y X = ) ( ( ) ) ( ) ( ) x t ( ) h t O F ( ) u u H Fractional correlation (FRCR) : type1: corr O ) ) ( O = , .( ( ), ( )) x t h t P F P F P F ( ( )) x t ( ( )) h t P P P O O O 3 1 2 1 2 3 ( = , .( ( ), ( )) x t h t P F P F P F ( ( )) x t ( ( h )) t P P P corr type2: O O O 3 1 2 1 2 3 10/23/2009 13

Fractional / Canonical Convolution and Correlation (cont.) Canonical convolution (CCV): ( , , ( ) F y t O = = transformed domain ( ) a b c d u Y = ( ) ( ) ( ) , ) c a ( , , , ) a b c d F ( , , , ) a b c d F d b ( ) x t ( ) h t O O ( ) x t ( ) h t ( , , , ) a b c d ( ) u ( ) u X H ( , , , ) ( , , , ) a b c d ( , , , ) a b c d Canonical correlation (CCR) : type1: ( , , , ),( , , , ),( , , , ) a b c d e f g h m n s v corr O ( ) ) = ( , , , ) m n s v corr ( , , , ) a b c d corr ( , , , ) e f g h corr ( ( ), ( )) x t h t ( ( )) x t ( ( )) h t O O O type2: O 10/23/2009 ( = ( , , , ),( , , , ),( , , , ) a b c d e f g h corr ( , , , ) m n s v corr ( , , , ) a b c d corr ( , , , ) e f g h corr m n s v ( ( ), ( )) x t h t ( ( )) x t ( ( h )) t O O O 14

Introduction of Two-Dimensional Affine Generalized Fractional Fourier Transform (2-D AGFFT) The 2-D AGFFT that it can be regarded as generalization of 2-D FT, 2-D FRFT, and 2-D LCT. Definition of 2-D AGFFT: where , , , , and 10/23/2009 15

Introduction of 2-D AGFFT (cont.) where , Reversibility property: 10/23/2009 16

Introduction of 2-D AGFFT (cont.) sin cos sin cos cos sin cos sin cos sin 1 2 cos cos cos sin cos cos sin cos ( ) ( ) When 2 1 = A , 1 2 1 cos 2 = B , sin 2 1 1 2 ( ) ( ) 1 2 1 2 sin sin cos sin sin sin sin cos 2 1 cos cos cos cos cos sin = C , 1 1 ( ) ( ) 2 1 1 sin 1 cos 2 2 = D , cos cos cos cos 1 1 ( ) ( ) 1 1 2 2 the 2-D AGFFT can become the 2-D unseparable FRFT which was introduced by Sahin et al. 10/23/2009 17

Introduction of 2-D AGFFT (cont.) 2-D AGFFT a12=a21=b12=b21=c12 =c21=d12=d21=0 B=C=0 Sahin unseparable FRFT s 2-D 2-D separable canonical Geometric twisting a11=a22=d11=d22=1 c11=c22=0 (a11,b11,c11,d11)=(cos ,sin ,-sin ,cos ) (a22,b22,c22,d22)=(cos ,sin ,-sin ,cos ) 2-D separable Fresnel 2-D separable FRFT = = /2 = = - /2 = = 0 2-D forward Fourier 2-D inverse Fourier Identity operation 10/23/2009 18

2-D Affine Generalized Fractional Convolution/ Correlation 2-D Affine Generalized Fractional Convolution (2-D AGFCV): ( ) ( , F F z x y O O ( ) ) ( ) ( ) T T T T ( ) ( ) , , , -C D -B A ( , , , ) A B C D A B C D ( , , , ) F = , , f x y g x y O -applications of 2-D AGFCV: filter design, generalized Hilbert transform, and mask 2-D Affine Generalized Fractional Correlation (2-D AGFCR): -applications of 2-D AGFCR: 2-D pattern recognition ( ) ( ) ( ) ( F ) ( ) ( ) ( ) , , , E F G H ' ' ' ' * A B C D ( , , , ) F ( F , , , ) = C A B D , , , z x y f x y x y g O O O 10/23/2009 19

Relation Between FRFT and Wigner Distribution Function (WDF) Definition of WDF: + 1 t t * = jw ( , ) t w f d f W e f 2 2 2 The property of the WDF: -high clarity -with cross-term problem 10/23/2009 20

Relation Between FRFT and WDF (cont.) Why does the WDF have a cross-term problem? Ans: autocorrelation-term of the WDF is existed * + )/ 2) )/ 2) (( (( f t t f If , its WDF will become ( ) ( ) ( ) f t s t r t = + ( , ) ( , ) f s t w t w W W W + ( , ). t w r 10/23/2009 21

Relation Between FRFT and WDF (cont.) Clockwise-Rotation Relation: ( , ) ( cos f W W = sin , sin + cos ) Fu v u v u v The FRFT with parameter is equivalent to the clockwise-rotation operation with angle for WDF. 10/23/2009 22

Relation Between FRFT and Gabor Transforms (GT) Definition of GT: ) ( 1 ( ) ( ) 2/2 = ( ) ( /2) t t jw ( , ) ft w f d G e e 2 The property of the GT: -with clarity problem -avoid cross-term problem -cost less computation time 2 exp 2 x 0.0001, when 4.2919 x 10/23/2009 23

Relation Between FRFT and GT (cont.) Why can the GT avoid the cross-term problem? Ans: the GT no have the autocorrelation-term + * )/ 2) (( )/ 2) (( f t t f = + ( ) ( ) s t ( ) r t f t If , its GT will become ( , ) ( , ) f s t w t w G G = + ( , ). t w G r 10/23/2009 24

Relation Between FRFT and GT (cont.) Clockwise-Rotation Relation: ( , ) ( cos f u G G = sin , sin + cos ) Fu v v u v The FRFT with parameter is equivalent to the clockwise-rotation operation with angle for GT. 10/23/2009 25

Relations Between FRFT, WDF, and GT 10/23/2009 26

Relations Between FRFT, WDF, and GT (cont.) Definition of GWT: ( , ) f t w C = ( ( , ), t w ( , )) t w p G W f f Clockwise-Rotation Relation: ( , ) C = sin , sin + ( cos u cos ) Fu v v u v C f = = ( , ) p x y , xy x = ( , ) t w ( , ) t w ( , ). t w Ex1: if then Ex2: if then ( , ) p x y C G W f f f + , y = + ( , ) t w ( , ) t w ( , ). t w C G W f f f 10/23/2009 27

Implementation Algorithm of FRFT/LCT Two methods to implement FRFT/LCT: - Chirp Convolution Method - DFT-Like Method ( ) To implement the FT, we need to use multiplications. 2 log N N 2 10/23/2009 28

Implementation Algorithm of FRFT/LCT (cont.) Chirp Convolution Method: For LCT, we sample t-axis and u-axis as and , then the continuous LCT becomes q p u t 1 M j d j j a 2 2 2 2 p q = q p ( ) ( ) q f p u t e e e F u t 2 2 b b b ( , , , ) a b c d u t 2 j b = p M 1 M 1 1 j d j b j a ( ) 2 2 2 2 2 = p q q p ( ). f p u t u t e e e 2 2 2 b b t 2 j b = p M chirp multiplication chirp convolution 10/23/2009 29

Implementation Algorithm of FRFT/LCT (cont.) To implement the LCT, we need to use 2 chirp multiplications and 1 chirp convolution. To implement 1 chirp convolution, we need to use requires 2 DFTs. Complexity: 2P (2 chirp multiplications) + (2 DFTs) log P P P P log 2 2 (P = 2M+1 = the number of sampling points) 10/23/2009 30

Implementation Algorithm of FRFT/LCT (cont.) This is 2 times of complexity of FT. 2 P To implement the LCT directly, we need to use multiplications. So, we use Chirp Convolution Method to implement the LCT that it can improve the efficiency of the LCT. For FRFT, its complexity is the same as LCT. 10/23/2009 31

Implementation Algorithm of FRFT/LCT (cont.) DFT-Like Method: 1 0 1 0 1 1 0 b 1 0 1 a c b d b = , 0 b 1 0 0 d b a b (chirp multi.) (FT) (scaling) (chirp multi.) = 2 1( ) t exp( 2 ) ( ) b f t ja f Step.1: chirp multi. Step.2: scaling Step.3: FT Step.4: chirp multi. t ab 2 = = j ( ) t ( ) bt ( ) f bt b b t f f 1 2 j exp( e 2 2 1 = jut ( ) u ( ) t dt f e F 3 2 = 2 ( ) u 2 ) b ( ) u jd u F F 4 3 10/23/2009 32

Implementation Algorithm of FRFT/LCT (cont.) We can implement the LCT: b M 2 j d p q P ab 2 2 2 2 j p = ( ) j f pb q t ( , , , )( a b c d ) s e u e e F 2 t 2 b u t 2 j b = p M = 2 P where t u To implement the LCT, we need to use 2 M-points multiplication operations and 1 DFT. (P = 2M+1 = the number of sampling points) 10/23/2009 33

Implementation Algorithm of FRFT/LCT (cont.) Complexity: 2P (2 multiplication operations) + (1 DFT) ( 2) log P P 2) log ( P P 2 2 This is only half of the complexity of Chirp Convolution Method. 10/23/2009 34

Implementation Algorithm of FRFT/LCT (cont.) When using Chirp Convolution Method, the sampling interval is free to choose, but it needs to use 2 DFTs. When using the DFT-like Method, although it has some constraint for the sampling intervals, but we only need 1 DFT to implement the LCT. 10/23/2009 35

Closed Form Discrete FRFT/LCT DFRFT/DLCT of type 1: applied to digital implementing of the continuous FRFT DFRFT/DLCT of type 2: applied to the practical applications about digital signal processing 10/23/2009 36

Closed Form Discrete FRFT/LCT (cont.) Definition of DFRFT of type 1: j 2 2 n m M + j N 2 2 2 2 sin cos 1 + j cot m u cot j n t e e e = ( ) m ( ) y n Y 2 1 2 2 M = n N when 2D +(0, ), D is integer (sin > 0) j 2 2 n m M + j N 2 2 + 2 2 sin cos 1 + j cot m u cot j n t e e e = ( ) m ( ) y n Y 2 1 2 2 M = n N when 2D +( , 0), D is integer (sin < 0) 2 u t = M N with the constraint and (2N+1, 2M+1 are the number of points in the time, frequency domain) + sin /(2 1) M 10/23/2009 37

Closed Form Discrete FRFT/LCT (cont.) when and D are integer, because we can t find proper choice for u and t that can t use as above. , when = 2D , when = (2D+1) ( ) ( ) m y m Y = = D = ( ) m ( ) y m Y The DFRFT of type 1 is efficient to calculate and implement. 10/23/2009 38

Closed Form Discrete FRFT/LCT (cont.) Complexity: 2P (2 chirp multiplications)+ (1 FFT) ( 2) log P P 2) log ( P P 2 2 But it doesn t match the continuous FRFT, and lacks many of the characteristics of the continuous FRFT. 10/23/2009 39

Closed Form Discrete FRFT/LCT (cont.) Definition of DLCT of type 1: 1 ( ) 2 M N 2 2 d n m M + a (b>0) 2 2 2 2 m = j j j ( ) y n m u n t e e e Y 2 1 2 b b ( , , , ) a b c d + 1 = n N 1 N 2 2 d n m M + a 2 2 2 2 = j j j ( ) m ( ) y n m u n t (b<0) e e e Y 2 1 2 b b ( , , , ) a b c d + 2 1 M = n N = + 2 /(2 1) u t b M with the constraint 10/23/2009 40

Closed Form Discrete FRFT/LCT (cont.) When b = 0, we can t also find proper choice for u and t that can t use as above. jcdm u a d y d m e Y = 2 2 (b=0, d is integer) ( ,0, , )( ) ( ) c d m 2 1 R a k m + n k + N M 2 sgn( ) 2 2 2 c 2 2 m = j j j ( ) m ( ) y n u e e e Y 2 1 1 a M N ( ,0, , ) a c d = = n N k M (b=0, d isn t integer) = + where R= (2M+1) (2N+1) and + (2 1) /(2 1) u N a t M 10/23/2009 41

Closed Form Discrete FRFT/LCT (cont.) Definition of DLCT of type 2: From DLCT of type 1, we let p = (d/b) u2, q = (a/b) t2 1 N 2 j s n m M + j 2 2 q n = p j ( ) m ( ) y n m e e e Y 2 2 1 2 ( , , ) p q s + 2 1 M = n N where M N (2N+1, 2M+1 are the number of points in the time, frequency domain), s is prime to M 10/23/2009 42

Closed Form Discrete FRFT/LCT (cont.) By setting p = q and s = 1, we can define the DFRFT from the DLCT and get the formula of DFRFT of type 2. Definition of DFRFT of type 2: 1 N 2 2 j n m M + j 2 2 m = p j p ( ) m ( ) y n n e e e Y 2 1 2 ( ) p + 2 1 M = n N where M N Complexity of DFRFT/DLCT of type 2 is the same as complexity of DFRFT/DLCT of type 1. 10/23/2009 43

Advantages of FRFT/LCT contrast with FT The FRFT/LCT are more general and flexible than the FT. The FRFT/LCT can be applied to partial differential equations (order n > 2). If we choice appropriate parameter , then the equation can be reduced order to n-1. The FT only deal with the stationary signals, we can use the FRFT/LCT to deal with time-varying signals. 10/23/2009 44

Advantages of FRFT/LCT contrast with FT (cont.) Using the FRFT/LCT to design the filters, it can reduce the NMSE. Besides, using the FRFT/LCT, many noises can be filtered out that the FT can t remove in optical system, microwave system, radar system, and acoustics. In encryption, because the FRFT/LCT have more parameter than the FT, it s safer in using the FRFT/LCT than in using the FT. 10/23/2009 45

Advantages of FRFT/LCT contrast with FT (cont.) In signal synthesis, using the transformed domain of the FRFT/LCT to analyze some signal is easier than using the time domain or frequency domain to analyze signals. In multiplexing, we can use multiplexing in fractional domain for super-resolution and encryption. 10/23/2009 46

Applications of FRFT/LCT 10/23/2009 47

Use FRFT/LCT to Represent Optical Components Propagation through the cylinder lens with focus length f: 1 0 2 1 c d f a b = Propagation through the free space (Fresnel Transform) with length z: 1 2 0 1 c d a b z = 10/23/2009 48

Implementation FRFT/LCT by Optical Systems Case1: a c 1 1)/ 0 1 1 0 1 1)/ 0 1 b d b = , 0 b ( 1 ( d b a b Free space Cylinder lens Cylinder lens f1 f2 Input Output d0 The implementing of LCT (b 0) with 2 cylinder lenses and 1 free space. 10/23/2009 49

Implementation FRFT/LCT by Optical Systems (cont.) 2 (1 2 2 (1 b b b = = = , , , for LCT f f d 0 1 2 ) ) a d {a, b, c, d} = {cos , sin , -sin , cos } 2 cot( / 2) 2 sin = = = , , for FRFT f f d 0 1 2 10/23/2009 50