The discrete fractional Fourier transform based on the DFT matrix

We introduce a new discrete fractional Fourier transform (DFrFT) based on only the DFT matrix and its powers. Eigenvectors of the DFT matrix are obtained in a simple-yet-elegant and straightforward manner. We show that this DFrFT definition based on the eigentransforms of the DFT matrix mimics the properties of continuous fractional Fourier transform (FrFT) by approximating the samples of the continuous FrFT. By appropriately combining existing commuting matrices we obtain a new commuting matrix which performs better. We show the validity of the proposed algorithms by computer simulations comparing DFrFT points and continuous FrFT samples for various signals.     

Discrete Fractional Fourier Transform Based on New Nearly Tridiagonal Commuting Matrices

Based on discrete Hermite–Gaussian-like functions, a discrete fractional Fourier transform (DFRFT), which provides sample approximations of the continuous fractional Fourier transform, was defined and investigated recently. In this paper, we propose a new nearly tridiagonal matrix, which commutes with the discrete Fourier transform (DFT) matrix. The eigenvectors of the new nearly tridiagonal matrix are shown to be DFT eigenvectors, which are more similar to the continuous Hermite–Gaussian functions than those developed before. Rigorous discussions on the relations between the eigendecomposition of the newly proposed nearly tridiagonal matrix and the DFT matrix are described. Furthermore, by appropriately combining two linearly independent matrices that both commute with the DFT matrix, we develop a method to obtain DFT eigenvectors even more similar to the continuous Hermite–Gaussian functions (HGFs). Then, new versions of DFRFT produce their transform outputs closer to the samples of the continuous fractional Fourier transform, and their applications are described. Related computer experiments are performed to illustrate the validity of the works in this paper.     

Discrete fractional Fourier transform based on orthogonalprojections

The continuous fractional Fourier transform (FRFT) performs a spectrum rotation of signal in the time-frequency plane, and it becomes an important tool for time-varying signal analysis. A discrete fractional Fourier transform has been developed by Santhanam and McClellan (see ibid., vol.42, p.994-98, 1996) but its results do not match those of the corresponding continuous fractional Fourier transforms. We propose a new discrete fractional Fourier transform (DFRFT). The new DFRFT has DFT Hermite eigenvectors and retains the eigenvalue-eigenfunction relation as a continous FRFT. To obtain DFT Hermite eigenvectors, two orthogonal projection methods are introduced. Thus, the new DFRFT will provide similar transform and rotational properties as those of continuous fractional Fourier transforms. Moreover, the relationship between FRFT and the proposed DFRFT has been established in the same way as the conventional DFT-to-continuous-Fourier transform     

Tridiagonal Commuting Matrices and Fractionalizations of DCT and DST Matrices of Types I, IV, V, and VIII

In this paper, we first establish new relationships in matrix forms among discrete Fourier transform (DFT), generalized DFT (GDFT), and various types of discrete cosine transform (DCT) and discrete sine transform (DST) matrices. Two new independent tridiagonal commuting matrices for each of DCT and DST matrices of types I, IV, V, and VIII are then derived from the existing commuting matrices of DFT and GDFT. With these new commuting matrices, the orthonormal sets of Hermite-like eigenvectors for DCT and DST matrices can be determined and the discrete fractional cosine transform (DFRCT) and the discrete fractional sine transform (DFRST) are defined. The relationships among the discrete fractional Fourier transform (DFRFT), fractional GDFT, and various types of DFRCT and DFRST are developed to reduce computations for DFRFT and fractional GDFT.     

A unified framework for the fractional Fourier transform

The paper investigates the possibility for giving a general definition of the fractional Fourier transform (FRT) for all signal classes [one-dimensional (1-D) and multidimensional, continuous and discrete, periodic and aperiodic]. Since the definition is based on the eigenfunctions of the ordinary Fourier transform (FT), the preliminary conditions is that the signal domain/periodicity be the same as the FT domain/periodicity. Within these classes, a general FRT definition is formulated, and the FRT properties are established. In addition, the multiplicity (which is intrinsic in a fractional operator) is clearly developed. The general definition is checked in the case in which the FRT is presently available and, moreover, to establish the FRT in new classes of signals     

从DFT导出过程和频谱分析谈DFT教学

信号处理中离散傅里叶变换DFT是一个重要的计算手段,可以完成很多计算,包括对连续时间信号的频谱估计。这在教学中是一个重点和难点。本文构建了由连续时间傅里叶变换CTFT和离散时间傅里叶变换DTFT导出DFT的过程,通过一系列操作和推导,以此理解DFT和DTFT以及离散时间傅里叶级数DTFS的密切联系,并深刻体会利用DFT做频谱分析的特点和考虑。     

Uncertainty principles for discrete signals associated with the fractional Fourier and linear canonical transforms

The fractional Fourier transform (FRFT), which generalizes the classical Fourier transform, has gained much popularity in recent years because of its applications in many areas, including optics, radar, and signal processing. There are relations between duration in time and bandwidth in fractional frequency for analog signals, which are called the uncertainty principles of the FRFT. However, these relations are only suitable for analog signals and have not been investigated in discrete signals. In practice, an analog signal is usually represented by its discrete samples. The purpose of this paper is to propose an equivalent uncertainty principle for the FRFT in discrete signals. First, we define the time spread and the fractional frequency spread for discrete signals. Then, we derive an uncertainty relation between these two spreads. The derived results are also extended to the linear canonical transform, which is a generalized form of the FRFT.     

Closed-Form Orthogonal DFT Eigenvectors Generated by Complete Generalized Legendre Sequence

In this paper, we propose a new method for deriving the closed-form orthogonal discrete Fourier transform (DFT) eigenvectors of arbitrary length using the complete generalized Legendre sequence (CGLS). From the eigenvectors, we then develop a novel method for computing the DFT. By taking a specific eigendecomposition to the DFT matrix, after proper arrangement, we can derive a new fast DFT algorithm with systematic construction of an arbitrary length that reduces the number of multiplications needed as compared with the existing fast algorithm. Moreover, we can also use the proposed CGLS-like DFT eigenvectors to define a new type of the discrete fractional Fourier transform, which is efficient in implementation and effective for encryption and OFDM.      

Digital computation of the fractional Fourier transform

An algorithm for efficient and accurate computation of the fractional Fourier transform is given. For signals with time-bandwidth product N, the presented algorithm computes the fractional transform in O(NlogN) time. A definition for the discrete fractional Fourier transform that emerges from our analysis is also discussed     

A new numerical Fourier transform in d-dimensions

The classical method of numerically computing Fourier transforms of digitized functions in one or in d-dimensions is the so-called discrete Fourier transform (DFT) efficiently implemented as fast Fourier transform (FFT) algorithms. In many cases, the DFT is not an adequate approximation to the continuous Fourier transform, and because the DFT is periodical, spectrum aliasing may occur. The method presented in this contribution provides accurate approximations of the continuous Fourier transform with similar time complexity. The assumption of signal periodicity is no longer posed and allows the computation of numerical Fourier transforms in a broader domain of frequency than the usual half-period of the DFT. In addition, this method yields accurate numerical derivatives of any order and polynomial splines of any odd degree. The numerical error on results is easily estimated. The method is developed in one and in d dimensions, and numerical examples are presented.     

Generalized eigenvectors and fractionalization of offset DFTs and DCTs

The offset discrete Fourier transform (DFT) is a discrete transform with kernel exp[-j2/spl pi/(m-a)(n-b)/N]. It is more generalized and flexible than the original DFT and has very close relations with the discrete cosine transform (DCT) of type 4 (DCT-IV), DCT-VIII, discrete sine transform (DST)-IV, DST-VIII, and discrete Hartley transform (DHT)-IV. In this paper, we derive the eigenvectors/eigenvalues of the offset DFT, especially for the case where a+b is an integer. By convolution theorem, we can derive the close form eigenvector sets of the offset DFT when a+b is an integer. We also show the general form of the eigenvectors in this case. Then, we use the eigenvectors/eigenvalues of the offset DFT to derive the eigenvectors/eigenvalues of the DCT-IV, DCT-VIII, DST-IV, DST-VIII, and DHT-IV. After the eigenvectors/eigenvalues are derived, we can use the eigenvectors-decomposition method to derive the fractional operations of the offset DFT, DCT-IV, DCT-VIII, DST-IV, DST-VIII, and DHT-IV. These fractional operations are more flexible than the original ones and can be used for filter design, data compression, encryption, and watermarking, etc.     

基于一种新的交换矩阵的离散分数阶傅立叶变换实现

分数阶傅立叶变换比傅立叶变换更具有一般性,多年来引起人们深入研究.由于连续的分数阶傅立叶变换在工程实现时都要抽样离散化,直接对连续分数阶傅立叶变换的核离散化会失去很多重要的性质,因此人们研究它的离散实现并保持它具有与连续分数阶变换同样的性质.本文提出了一种新的交换矩阵实现离散分数阶傅立叶变换,其变换的离散核矩阵与连续变换的分数阶傅立叶变换核有相似性,诸如酉特性、可加性、正交性和可逆性.仿真结果证实了所提出的分数阶傅立叶变换核与连续分数阶傅立叶变换核的相似性以及两种变换对矩形信号这种典型信号的分数阶傅立叶变换的相似性.     

基于自适应分数阶傅里叶变换的线性调频信号检测及参数估计

该文提出了一种基于最小均方算法的自适应计算分数阶傅里叶变换的方法并将该方法应用到多分量chirp信号的检测与估计之中。该方法通过对连续型分数阶傅里叶反变换进行离散化采样,得到适合数值计算的离散形式,进而通过适当的选择输入向量和目标函数构造自适应滤波器,经过最小均方算法进行训练后所得的滤波器权系数即为分数阶傅里叶变换的结果。仿真实验表明,该方法可以用来计算分数阶傅里叶变换及对chirp信号进行检测和参数估计,且计算延时相对较小。     

多参数离散分数傅里叶变换的应用

离散分数傅里叶变换是离散傅里叶变换的推广,文中将离散分数傅里叶变换推广到了带有N个参数的多参数分数傅里叶变换.并将它应用于数字图像加密解密过程中.给出了加密解密模型,实验结果表明本方法保密性能高,实现简单,具有广泛的应用前景.     

Closed-form discrete fractional and affine Fourier transforms

The discrete fractional Fourier transform (DFRFT) is the generalization of discrete Fourier transform. Many types of DFRFT have been derived and are useful for signal processing applications. We introduce a new type of DFRFT, which are unitary, reversible, and flexible; in addition, the closed-form analytic expression can be obtained. It works in performance similar to the continuous fractional Fourier transform (FRFT) and can be efficiently calculated by the FFT. Since the continuous FRFT can be generalized into the continuous affine Fourier transform (AFT) (the so-called canonical transform), we also extend the DFRFT into the discrete affine Fourier transform (DAFT). We derive two types of the DFRFT and DAFT. Type 1 is similar to the continuous FRFT and AFT and can be used for computing the continuous FRFT and AFT. Type 2 is the improved form of type 1 and can be used for other applications of digital signal processing. Meanwhile, many important properties continuous FRFT and AFT are kept in the closed-form DFRFT and DAFT, and some applications, such as filter design and pattern recognition, are also discussed. The closed-form DFRFT we introduce has the lowest complexity among all current DFRFTs that is still similar to the continuous FRFT     

Efficient DFT Architectures Based Upon Symmetries

This paper presents an efficient discrete Fourier transform (DFT) approach based upon an eigenvalue decomposition method. The work is based on some recent results on DFT eigenvectors, expressed exactly (not numerically) with simple exponential terms, with a considerable number of elements constrained to 0, and with a high degree of symmetry. The result provides a generalization of known fast Fourier transform (FFT) algorithms based upon a divide-and-conquer approach. Moreover, it can have interesting applications in the context of fractional Fourier transforms, where it provides an efficient implementation.     

Image and video processing using discrete fractional transforms

The mathematical transforms such as Fourier transform, wavelet transform and fractional Fourier transform have long been influential mathematical tools in information processing. These transforms process signal from time to frequency domain or in joint time–frequency domain. In this paper, with the aim to review a concise and self-reliant course, the discrete fractional transforms have been comprehensively and systematically treated from the signal processing point of view. Beginning from the definitions of fractional transforms, discrete fractional Fourier transforms, discrete fractional Cosine transforms and discrete fractional Hartley transforms, the paper discusses their applications in image and video compression and encryption. The significant features of discrete fractional transforms benefit from their extra degree of freedom that is provided by fractional orders. Comparison of performance states that discrete fractional Fourier transform is superior in compression, while discrete fractional cosine transform is better in encryption of image and video. Mean square error and peak signal-to-noise ratio with optimum fractional order are considered quality check parameters in image and video.     

特征分解型离散分数阶Fourier变换

分数阶Fourier变换作为Fourier变换的广义形式,广泛应用于科学计算和研究,离散分数阶Fourier变换是其得以应用的关键。特征分解算法是由可交换对角矩阵得到近似连续Hermite-Gaussian函数的特征向量,再对Hermite-Gaussian函数进行加权和运算。对一种基于数特征分解的方法进行了改进,并进行计算机仿真。仿真结果表明所得的Hermite-Gaussian函数与连续函数的近似度更为优异,从而提高了离散分数阶Fourier变换的近似度。     

Fractional Fourier transform of the Gaussian and fractional domain signal support

The fractional Fourier transform (FrFT) provides an important extension to conventional Fourier theory for the analysis and synthesis of linear chirp signals. It is a parameterised transform which can be used to provide extremely compact representations. The representation is maximally compressed when the transform parameter, /spl alpha/, is matched to the chirp rate of the input signal. Existing proofs are extended to demonstrate that the fractional Fourier transform of the Gaussian function also has Gaussian support. Furthermore, expressions are developed which allow calculation of the spread of the signal representation for a Gaussian windowed linear chirp signal in any fractional domain. Both continuous and discrete cases are considered. The fractional domains exhibiting minimum and maximum support for a given signal define the limit on joint time-frequency resolution available under the FrFT. This is equated with a restatement of the uncertainty principle for linear chirp signals and the fractional Fourier domains. The calculated values for the fractional domain support are tested empirically through comparison with the discrete transform output for a synthetic signal with known parameters. It is shown that the same expressions are appropriate for predicting the support of the ordinary Fourier transform of a Gaussian windowed linear chirp signal.     

Multichannel transforms for signal/image processing

This paper presents a novel approach to the Fourier analysis of multichannel time series. Orthogonal matrix functions are introduced and are used in the definition of multichannel Fourier series of continuous-time periodic multichannel functions. Orthogonal transforms are proposed for discrete-time multichannel signals as well. It is proven that the orthogonal matrix functions are related to unitary transforms (e.g., discrete Hartley transform (DHT), Walsh-Hadamard transform), which are used for single-channel signal transformations. The discrete-time one-dimensional multichannel transforms proposed in this paper are related to two-dimensional single-channel transforms, notably to the discrete Fourier transform (DFT) and to the DHT. Therefore, fast algorithms for their computation can be easily constructed. Simulations on the use of discrete multichannel transforms on color image compression have also been performed.