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     

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     

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.     

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.     

Discrete Sine and Cosine Transforms in Single Carrier Modulation Systems

In the DFT-based single carrier frequency division multiple access (SC-FDMA) modulation system, the discrete Fourier transform (DFT) is usually exploited to divide the frequency channel. In this paper, we propose to use discrete sine/cosine transforms in place of the DFT for SC-FDMA. Eight SC-FDMA systems based on various DST/DCT types are studied. The bit error rate (BER) and the peak to average power ratio (PAPR) are used to evaluate performance of these eight DST/DCT-based SC-FDMA systems in comparison with the conventional DFT-based SC-FDMA system in an AWGN environment. Simulation results show that the DST/DCT-based SC-FDMA systems with the use of localized FDMA scheme can provide better BER performance and yet keep the same PAPR performance as compared to the DFT-based SC-FDMA system.     

Parallel vector processing of multidimensional orthogonal transforms for digital signal processing applications

This paper presents vector and parallel algorithms and implementations of one- and two-dimensional orthogonal transforms. The speed performances are evaluated on Cray X-MP/48 vector computer. The sinusoidal orthogonal transforms are computed using fast real Fourier transform (FFT) kernel. The non-sinusoidal orthogonal transform algorithms are derived by using direct factorizations of transform matrices. Concurrent processing is achieved by using the multitasking capability of Cray X-MP/48 to transform long data vectors and two-dimensional data vectors. The discrete orthogonal transforms discussed in this paper include: Fourier transform (DFT), cosine transform (DCT), sine transform (DST), Hartley transform (DHT), Walsh transform (DWHT) and Hadamard transform (DHDT). The factors affecting the speedup of vector and parallel processing of these transforms are considered. The vectorization techniques are illustrated by an FFT example.This work is supported in part by the National Science Foundation, Pittsburgh Supercomputing Center (grant number ECS-880012P) and by the PEW Science Education Program.     

New 2D systolic array algorithm for DCT/DST

Presents an algorithm and the architecture of a 2D systolic array processor for the DCT (discrete cosine transform) and the DST (discrete sine transform). It is based on the IDFT (inverse discrete Fourier transform) version of the Goertzel algorithm via Horner's rule. This 2D systolic array for the DCT/DST can be met by achieving a systematic technique for transforming algorithms to specific forms for mapping onto 2D systolic arrays.<>     

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     

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.     

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     

A Fast Computational Algorithm for the Discrete Sine Transform

A sparse-matrix factorization is developed for the discrete sine transform (DST). This factorization has a recursive structure and leads directly to an efficient algorithm for implementing the DST, a feature most desirable and very similar ot that of the DCT. This algorithm requires fewer arithmetic operations compared to that for the discrete cosine transform (DCT).     

Restructured recursive DCT and DST algorithms

The discrete cosine transform (DCT) and the discrete sine transform (DST) have found wide applications in speech and image processing, as well as telecommunication signal processing for the purpose of data compression, feature extraction, image reconstruction, and filtering. In this paper, we present new recursive algorithms for the DCT and the DST. The proposed method is based on certain recursive properties of the DCT coefficient matrix, and can be generalized to design recursive algorithms for the 2-D DCT and the 2-D DST. These new structured recursive algorithms are able to decompose the DCT and the DST into two balanced lower-order subproblems in comparison to previous research works. Therefore, when converting our algorithms into hardware implementations, we require fewer hardware components than other recursive algorithms. Finally, we propose two parallel algorithms for accelerating the computation     

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

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

An embedding approach to frequency-domain and subband adaptivefiltering

Frequency-domain and subband implementations improve the computational efficiency and the convergence rate of adaptive schemes. The well-known multidelay adaptive filter (MDF) belongs to this class of block adaptive structures and is a DFT-based algorithm. We develop adaptive structures that are based on the trigonometric transforms, discrete cosine transform (DCT) and discrete sine transform (DST), and on the discrete Hartley transform (DHT). As a result, these structures involve only real arithmetic and are attractive alternatives in cases where the traditional DFT-based scheme exhibits poor performance. The filters are derived by first presenting a derivation for the classical DFT based filter that allows us to pursue these extensions immediately. The approach used in this paper also provides further insights into subband adaptive filtering     

Efficient VLSI Implementations of Fast Multiplierless Approximated DCT Using Parameterized Hardware Modules for Silicon Intellectual Property Design

An efficient implementation of discrete cosine transform (DCT) computations are presented based on the so-called shifted discrete Fourier transform (SDFT), a generalization of the conventional DFT (DFT). Due to the simple form of the factorized matrices, the derived architecture can be easily constructed from the cascade of only two types of parameterized hardware modules: butterfly operators and rotators. The butterfly operator performs the conventional butterfly shuffling and addition/subtraction. The rotator that performs plane rotations of two-dimensional (2-D) vectors is designed using carry-save-adder (CSA)-based unfolded pipelined CORDIC architecture where the rotation angles can be approximated with different accuracies using a sequence of bipolar signs. The proposed one-dimensional and 2-D DCT implementations composed of the above two types of parameterized modules can be used as flexible and reusable Silicon Intellectual Property (SIP) for the DCT computation unit to be embedded in system-on-a-chip (SoC) design. The proposed implementations have many features and advantages, including SIP reusability, low complexity, high-throughput, regularity, scalability (easy extension of transform length), and flexibility (approximated DCT with various accuracies).     

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

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

2-D DCT systolic array implementation

The algorithm and architecture of a 2-D systolic array processor for the DCT (discrete cosine transform) are proposed. It is based on the relationship between DCT and cosine DFT and sine DFT. Two systolic architectures of 1-D DCT data and control flow computation are discussed. By use of the main feature of the two systolic 1-D arrays for DCT, a full 2-D systolic DCT array is presented.<>     

All-Optical Discrete Sine Transform and Discrete Cosine Transform Based on Multimode Interference Couplers

In this letter, a novel method to realize all-optical discrete sine transform (DST) and discrete cosine transform (DCT) is proposed. The approach requires only one multimode interference (MMI) coupler and several phase shifters at the input and output ports. By properly arranging the length of the MMI coupler and adjusting the phase shifters, the DST can be directly realized all-optically. Meanwhile, the DCT is related to the DST with a simple formula. By changing the input phase and relabeling the output ports, it can also be realized on the MMI structure. The proposed methodology has no limit on the number of the inputs.      

Diagonalizing properties of the discrete cosine transforms

Since its introduction in 1974 by Ahmed et al., the discrete cosine transform (DCT) has become a significant tool in many areas of digital signal processing, especially in signal compression. There exist eight types of discrete cosine transforms (DCTs). We obtain the eight types of DCTs as the complete orthonormal set of eigenvectors generated by a general form of matrices in the same way as the discrete Fourier transform (DFT) can be obtained as the eigenvectors of an arbitrary circulant matrix. These matrices can be decomposed as the sum of a symmetric Toeplitz matrix plus a Hankel or close to Hankel matrix scaled by some constant factors. We also show that all the previously proposed generating matrices for the DCTs are simply particular cases of these general matrix forms. Using these matrices, we obtain, for each DCT, a class of stationary processes verifying certain conditions with respect to which the corresponding DCT has a good asymptotic behavior in the sense that it approaches Karhunen-Loeve transform performance as the block size N tends to infinity. As a particular result, we prove that the eight types of DCTs are asymptotically optimal for all finite-order Markov processes. We finally study the decorrelating power of the DCTs, obtaining expressions that show the decorrelating behavior of each DCT with respect to any stationary processes     

Computation of an odd-length DCT from a real-valued DFT of the samelength

The discrete cosine transform (DCT) is often computed from a discrete Fourier transform (DFT) of twice or four times the DCT length. DCT algorithms based on identical-length DFT algorithms generally require additional arithmetic operations to shift the phase of the DCT coefficients. It is shown that a DCT of odd length can be computed by an identical-length DFT algorithm, by simply permuting the input and output sequences. Using this relation, odd-length DCT modules for a prime factor DCT are derived from corresponding DFT modules. The multiplicative complexity of the DCT is then derived in terms of DFT complexities