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.     

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     

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

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

The discrete fractional Fourier transform

We propose and consolidate a definition of the discrete fractional Fourier transform that generalizes the discrete Fourier transform (DFT) in the same sense that the continuous fractional Fourier transform generalizes the continuous ordinary Fourier transform. This definition is based on a particular set of eigenvectors of the DFT matrix, which constitutes the discrete counterpart of the set of Hermite-Gaussian functions. The definition is exactly unitary, index additive, and reduces to the DFT for unit order. The fact that this definition satisfies all the desirable properties expected of the discrete fractional Fourier transform supports our confidence that it will be accepted as the definitive definition of this transform     

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     

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

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

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.      

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.     

Eigenvalues and eigenvectors of generalized DFT, generalized DHT,DCT-IV and DST-IV matrices

In this paper, the eigenvalues and eigenvectors of the generalized discrete Fourier transform (GDFT), the generalized discrete Hartley transform (GDHT), the type-IV discrete cosine transform (DCT-IV), and the type-IV discrete sine transform (DST-IV) matrices are investigated in a unified framework. First, the eigenvalues and their multiplicities of the GDFT matrix are determined, and the theory of commuting matrices is applied to find the real, symmetric, orthogonal eigenvectors set that constitutes the discrete counterpart of Hermite Gaussian function. Then, the results of the GDFT matrix and the relationships among these four unitary transforms are used to find the eigenproperties of the GDHT, DCT-IV, and DST-IV matrices. Finally, the fractional versions of these four transforms are defined, and an image watermarking scheme is proposed to demonstrate the effectiveness of fractional transforms     

The discrete fractional cosine and sine transforms

This paper is concerned with the definitions of the discrete fractional cosine transform (DFRCT) and the discrete fractional sine transform (DFRST). The definitions of DFRCT and DFRST are based on the eigen decomposition of DCT and DST kernels. This is the same idea as that of the discrete fractional Fourier transform (DFRFT); the eigenvalue and eigenvector relationships between the DFRCT, DFRST, and DFRFT can be established. The computations of DFRFT for even or odd signals can be planted into the half-size DFRCT and DFRST calculations. This will reduce the computational load of the DFRFT by about one half     

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.     

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.     

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.     

Efficient computation of DFT commuting matrices by a closed-form infinite order approximation to the second differentiation matrix

In order to define the discrete fractional Fourier transform, Hermite Gauss-like eigenvectors are needed and one way of extracting these eigenvectors is to employ DFT commuting matrices. Recently, Pei et al. exploited the idea of obtaining higher order DFT-commuting matrices, which was introduced by Candan previously. The upper bound of O(h^2k) approximation to N×N commuting matrix is 2k+1≤N in Candan's work and Pei et al. improved the proximity by removing this upper bound at the expense of higher computational cost. In this paper, we derive an exact closed form expression of infinite-order Taylor series approximation to discrete second derivative operator and employ it in the definition of excellent DFT commuting matrices. We show that in the limit this Taylor series expansion converges to a trigonometric function of second-order differentiating matrix. The commuting matrices possess eigenvectors that are closer to the samples of Hermite-Gaussian eigenfunctions of DFT better than any other methods in the literature with no additional computational cost.     

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.     

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.     

An orthonormal class of exact and simple DFT eigenvectors with a high degree of symmetry

The paper presents a novel orthonormal class of eigenvectors of the discrete Fourier transform (DFT) whose order N is factored as N=rM/sup 2/. The DFT eigenvectors have the form e=E/spl alpha/, where /spl alpha/ are eigenvectors of some /spl lscr/ /spl times//spl lscr/ matrices, given by, or related to, the DFT matrix of order r, with /spl lscr/ = r, 2r, or 4r, and the matrix E expands /spl alpha/ to the full DFT size N=rM/sup 2/. In particular, when N is an arbitrarily large power of 2, r may be 1 or 2. The resulting eigenvectors are expressed exactly with simple exponential expressions, have a considerable number of elements constrained to 0, and show a high degree of symmetry. The derivation of such a class is based on a partition of the N-dimensional linear space into subspaces of very small dimension (r, 2r or 4r).     

基于双通道DFRFT互谱法的Chirp信号时延估计

针对脉冲Chirp类信号的时延估计问题,理论推导了基于离散分数阶Fourier变换的脉冲Chirp信号的特性,分析了当时延参量等效的分数阶Fourier域的频率大于采样率时,脉冲Chirp信号的分数阶Fourier域谱产生混叠,造成时延估计模糊的问题,并提出基于离散分数阶Fourier变换（DFRFT）双通道互谱法进行时延估计,给出两个通道采样率选取的原则及算法的性能分析,实验结果表明,在一定的采样率下,算法能够快速精确地估计脉冲Chirp信号的时延参数.     

Eigenfunctions of Fourier and Fractional Fourier Transforms With Complex Offsets and Parameters

In this paper, we derive the eigenfunctions of the Fourier transform (FT), the fractional FT (FRFT), and the linear canonical transform (LCT) with (1) complex parameters and (2) complex offsets. The eigenfunctions in the cases where the parameters and offsets are real were derived in literature. We extend the previous works to the cases of complex parameters and complex offsets. We first derive the eigenvectors of the offset discrete FT. They approximate the samples of the eigenfunctions of the continuous offset FT. We find that the eigenfunctions of the offset FT with complex offsets are the smoothed Hermite-Gaussian functions with shifting and modulation. Then we extend the results for the case of the offset FRFT and the offset LCT. We can use the derived eigenfunctions to simulate the self-imaging phenomenon for the optical system with energy-absorbing component, mode selection, encryption, and define the fractional Z-transform and the fractional Laplace transform.     

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

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