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     

On the on-line computation of DCT-IV and DST-IV transforms

Various options available for the on-line computation of discrete cosine transform-IV (DCT-IV) and discrete sine transform-IV (DST-IV) in hardware are considered and compared. A novel architecture for the simultaneous, real-time computation of both the transforms, based on the decomposition of the odd-time, odd-frequency discrete Fourier transform (O² DFT), is also proposed     

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.      

On the computation of running discrete cosine and sine transform

Two algorithms are given for the computation of the updated discrete cosine transform-II (DCT-II), discrete sine transform-II (DST-II), discrete cosine transform-IV (DCT-IV), and discrete sine transform-IV (DST-IV). It is pointed out that the algorithm used for running DCT-IV can also be used for computation for running DST-IV without additional computational overhead. An architecture which is common and suitable for VLSI implementation of the derived algorithms is also presented. Preliminary studies have shown that the architecture can easily be implemented in VLSI form, and, in conjunction with a high-speed digital signal processor (for example ADSP 2100A), it can be used for real-time transform domain LMS adaptive filtering (128 taps) of 8 kHz sample rate speech signals     

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.     

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.     

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.     

The integer transforms analogous to discrete trigonometric transforms

The integer transform (such as the Walsh transform) is the discrete transform that all the entries of the transform matrix are integer. It is much easier to implement because the real number multiplication operations can be avoided, but the performance is usually worse. On the other hand, the noninteger transform, such as the DFT and DCT, has a good performance, but real number multiplication is required. W derive the integer transforms analogous to some popular noninteger transforms. These integer transforms retain most of the performance quality of the original transform, but the implementation is much simpler. Especially, for the two-dimensional (2-D) block transform in image/video, the saving can be huge using integer operations. In 1989, Cham had derived the integer cosine transform. Here, we will derive the integer sine, Hartley, and Fourier transforms. We also introduce the general method to derive the integer transform from some noninteger transform. Besides, the integer transform derived by Cham still requires real number multiplication for the inverse transform. We modify the integer transform introduced by Cham and introduce the complete integer transform. It requires no real number multiplication operation, no matter what the forward or inverse transform. The integer transform we derive would be more efficient than the original transform. For example, for the 8-point DFT and IDFT, there are in total four real numbers and eight fixed-point multiplication operations required, but for the forward and inverse 8-point complete integer Fourier transforms, there are totally 20 fixed-point multiplication operations required. However, for the integer transform, the implementation is simpler, and many of the properties of the original transform are kept.     

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     

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     

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.     

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.     

New fast computational structures for an efficient implementation of the forward/backward MDCT in MP3 audio coding standard

New fast computational structures identical for an efficient implementation of both the forward and backward modified discrete cosine transform (MDCT) in MPEG-1/2 Layer III (MP3) audio coding standard are described. They are based on a new proposed universal fast rotation-based MDCT computational structure [V. Britanak, New universal rotation-based fast computational structures for an efficient implementation of the DCT-IV/DST-IV and analysis/synthesis MDCT/MDST filter banks, Signal Processing 89 (11) (November 2009) 2213–2232]. New fast computational structures are derived in the form of a linear code and they are particularly suitable for high-performance programmable DSP processors. For the short audio block it is shown that our efficient MDCT implementation in MP3 can be modified to achieve the same minimal multiplicative complexity compared to that of Dai and Wagh [An MDCT hardware accelerator for MP3 audio, in: Proceedings of the IEEE Symposium on Application Specific Processors (SASP’2008), Anaheim, CA, June 2008, pp. 121–125].     

New fast algorithm for multidimensional type-IV DCT

The authors first propose an index mapping such that the type-IV m-dimensional discrete cosine transform (m-D DCT-IV) is turned into a sum involving a number of (m-1)-dimensional discrete cosine transforms ((m-1)-D DCTs). Then a polynomial transform is used for implementing the sum. Based on symmetrical properties, a refined fast polynomial transform algorithm is proposed for computing the polynomial transform. Compared to the row-column m-D DCT-IV algorithm, the proposed algorithm achieves remarkable savings in arithmetic operations. More precisely, the numbers of multiplications and additions for m-dimensional DCT-IV are nearly 1/m and (2m+1)/3m times those of the row-column method, respectively     

The Uniform Correlation Matrix and its Application to Diversity

We consider a complex-valued L times L square matrix whose diagonal elements are unity, and lower and upper diagonal elements are the same, each lower diagonal element being equal to a (a ne 1) and each upper diagonal element being equal to b (b ne 1). We call this matrix the generalized semiuniform matrix, and denote it as M(a, b,L). For this matrix, we derive closed-form expressions for the characteristic polynomial, eigenvalues, eigenvectors, and inverse. Treating the non-real-valued uniform correlation matrix M(a, a*, L), where (middot)* denotes the complex conjugate and a ne a*, as a Hermitian generalized semiuniform matrix, we obtain the eigenvalues, eigenvectors, and inverse of M(a, a*, L) in closed form. We present applications of these results to the analysis of communication systems using diversity under correlated fading conditions     

The Design and Implementation of FFTW3

FFTW is an implementation of the discrete Fourier transform (DFT) that adapts to the hardware in order to maximize performance. This paper shows that such an approach can yield an implementation that is competitive with hand-optimized libraries, and describes the software structure that makes our current FFTW3 version flexible and adaptive. We further discuss a new algorithm for real-data DFTs of prime size, a new way of implementing DFTs by means of machine-specific single-instruction, multiple-data (SIMD) instructions, and how a special-purpose compiler can derive optimized implementations of the discrete cosine and sine transforms automatically from a DFT algorithm.     

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     

Frequency ambiguity resolution in OFDM systems

In orthogonal frequency division multiplexing systems, the carrier-frequency offset can be divided into two parts: (1) an integer one-multiple of the subcarrier spacing 1/T and (2) a fractional one-less than 1/2T in amplitude. Some schemes proposed in the literature can only recover the fractional part. We derive two algorithms for estimating the integer part. They are based on the observation of two consecutive OFDM symbols. The first algorithm exploits pilot symbols multiplexed with the data, the other is blind     

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).     

The Imaginary Part: A Source of Creativity in Instrumentation and Measurement

To analyze a signal digitally in instrumentation and measurement, we need to record a series of samples of that signal, which we refer to as a captured waveform. The author discusses the discrete Fourier transform (DFT) which is a widely used powerful signal analysis method. The discrete nature of the method implies that the captured waveform being analyzed is a portion of a periodic signal, and the transform is performed on a whole period or an integer multiple of periods