Fast biased polynomial transforms for two-dimensional convolutions

The fast biased polynomial transforms are defined directly on the ZN?1 ring instead of a conventional cyclotomic polynomial ring. Such biased polynomial transforms may be combined with very efficient fast FFT algorithms. Two-dimensional convolutions may be carried out without using the complicated Chinese remainder theorem, complex mapping and column-row reordering processes.     

Fast algorithms for the discrete Fourier preprocessing transforms

It is pointed out that the two-stage Fourier algorithms are useful in a variety of applications in signal/image processing and recognition. The first stage, known as the DFPT (discrete Fourier preprocessing transform), has the potential of very fast and low-cost implementation, say, in a VLSI chip, as well as high-quality performance in applications without the second stage. The DFT (discrete Fourier transform), the RDFT (real DFT), or any other DFPT can be obtained if the second stage is completed. Since the second stage consists of independent blocks of circular correlations, they can be computed in fast sequential or parallel architectures. There are two groups of fast algorithms for the computation of DFPTs. The first group involves the representation of a DFPT in terms of skew-circular correlations (SCCs), which are then computed by fast SCC algorithms or parallel architectures such as semisystolic arrays. The second group involves the fast computation of a DFPT, including the DFT and the RDFT, by the implementationally simplest DFPT, such as class 2, case V DFPT     

Fast prime factor decomposition algorithms for a family of discrete trigonometric transforms

This paper develops a set of fast prime factor decomposition algorithms (PFDAs) for a family of discrete trigonometric transforms of sizeN, whereN is a product of two relatively prime integers. Relevant equations for the PFDAs are derived. Computational procedures are presented followed by a specific example forN= 12. The input and output index mappings necessary for the algorithm are obtained and the computational complexity is briefly outlined.This research was supported by NSERC.Visiting scholar on leave of absence from Department of Radio and Electronics, Anhui University, Anhui, People's Republic of China.     

Fast and precise Fourier transforms

Many applications of fast Fourier transforms (FFTs), such as computer tomography, geophysical signal processing, high-resolution imaging radars, and prediction filters, require high-precision output. An error analysis reveals that the usual method of fixed-point computation of FFTs of vectors of length 2^l leads to an average loss of l/2 bits of precision. This phenomenon, often referred to as computational noise, causes major problems for arithmetic units with limited precision which are often used for real-time applications. Several researchers have noted that calculation of FFTs with algebraic integers avoids computational noise entirely. We combine a new algorithm for approximating complex numbers by cyclotomic integers with Chinese remaindering strategies to give an efficient algorithm to compute b-bit precision FFTs of length L. More precisely, we approximate complex numbers by cyclotomic integers in Z[e(2πi/2ⁿ)] whose coefficients, when expressed as polynomials in e(2πi/2ⁿ), are bounded in absolute value by some integer M. For fixed n our algorithm runs in time O(log(M)), and produces an approximation with worst case error of O(1/M(2^n-2-1)). We prove that this algorithm has optimal worst case error by proving a corresponding lower bound on the worst case error of any approximation algorithm for this task. The main tool for designing the algorithms is the use of the cyclotomic units, a subgroup of finite index in the unit group of the cyclotomic field. First implementations of our algorithms indicate that they are fast enough to be used for the design of low-cost high-speed/high-precision FFT chips     

Fast mersenne number transforms for the computation of discrete fourier transforms

In this paper we present results on the computation of Discrete Fourier Transforms (DFT) using Mersenne Number Transforms (MNT). It is shown that in the case of Mersenne-composite Number Transforms, the number of multiplications per point for real input data is never more than one, even for sequence lengths exceeding one thousand points. The computation time per point for a length (2P + 1)-point DFT is simply equal to the time for one MNT multiplication and 3 MNT additions if a high-speed, parallel hardware module is used to implement the MNT unit. This new approach allows a large choice of wordlengths and in addition the control of data flow is extremely simple. We also present the results obtained by using Winograd's Fourier Transform Algorithm and the nested MNT to compute efficiently the DFT's of long sequences. We also show that the number of additions can be reduced significantly if Pseudo Mersenne-Number Transforms are used for the computation of DFTs.     

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     

Hilbert and Fourier transforms of polynomial ratio time signals

Polynomial curve fittings have long been used to smooth data and provide functions from which, at specified times, samples may be obtained. Relationships of these polynomials to frequency content can be determined by including a denominator polynomial which does not essentially affect the fit over the data interval. Both Fourier and Hilbert transforms are found for general polynomial ratios, and their subsequent properties, duals of polynomial ratio frequency functions, are discussed.     

Comparison of discrete wavelet and Fourier transforms for ECG beatclassification

Two feature extraction methods, Fourier and wavelet analyses for ECG beat classification, are comparatively investigated. ECG features are searched by dynamic programming according to the divergence values. 10 types of ECG beat from an MTT-BIH database are classified with a success of 97% using a restricted Coulomb energy neural network trained by genetic algorithms     

Fast algorithms for the computation of sliding discrete sinusoidal transforms

Fast algorithms for computing various discrete cosine transforms and discrete sine transforms in a sliding window are proposed. The algorithms are based on a recursive relationship between three subsequent local transform spectra. Efficient inverse algorithms for signal processing in a sliding window are also presented. The computational complexity of the algorithms is compared with that of known fast discrete sinusoidal transforms and running recursive algorithms.     

Efficient real data filtering using complex-input discrete Fourier transforms

A new algorithm for efficient linear convolution of real signals using discrete Fourier transforms is presented. The traditional method uses a considerable amount of pre-processing and post-processing of both the input and output signals. We show that plenty of this processing can be shifted to the impulse response of the system, whose operations can be precomputed and therefore have no computational cost. This method results in computational savings, reducing the total arithmetic operations and particularly the execution time with regard to previously proposed techniques.     

Fast computation of the discrete Walsh and Hadamard transforms

The discrete Walsh and Hadamard transforms are often used in image processing tasks such as image coding, pattern recognition, and sequency filtering. A new discrete Walsh transform (DWT) algorithm is derived in which a modified form of the DWT relation is decomposed into smaller-sized transforms using vectorized quantities. A new sequency-ordered discrete Hadamard transform (DHAT) algorithm is also presented. The proposed approach results in more regular algorithms requiring no independent data swapping and fewer array-index updating and bit-reversal operations. An analysis of the computational complexity and the execution time performance are provided. The results are compared with those of the existing algorithms     

Fast algorithms of multidimensional discrete nonseparable𝒦-wave transforms

Fast algorithms for a wide class of nonseparable n-dimensional (n-D) discrete unitary 𝒦 transforms (DKTs) are introduced. They need fewer 1-D DKTs than in the case of the classical radix-2 FFT-type approach. The method utilizes a decomposition of the n-D K transform into the product of a new n-D discrete Radon transform and of a set of parallel/independ 1-D K transforms. If the n-D K transform has a separable kernel (e.g., the case of the discrete Fourier transform), our approach leads to decrease of multiplicative complexity by the factor of n, compared with the classical row/column separable approach     

Fast algorithms for 2-D circular convolutions and number theoretictransforms based on polynomial transforms over finite rings

We develop new fast algorithms for 2-D integer circular convolutions and 2-D number theoretic transforms (NTT). These new algorithms, which offer improved computational complexity, are constructed based on polynomial transforms over Z_p; these transforms are Fourier-like transforms over Z_p, which is the integral domain of polynomial forms over Z_p[x]. Having defined such polynomial transforms over Z_p we prove several necessary and sufficient conditions for their existence. We then apply the existence conditions to recognize two applicable polynomial transforms over Z_p. One is for p equal to Mersenne numbers and the other for Fermat numbers. Based on these two transforms, referred to as Mersenne number polynomial transforms (MNPT) and Fermat number polynomial transforms (FNPT), we develop fast algorithms for 2-D integer circular convolutions, 2-D Mersenne number transforms, and 2-D Fermat number transforms. As compared to the conventional row-column computation of 2-D NTT for 2-D integer circular convolutions and 2-D NTT, the new algorithms give rise to reduced computational complexities by saving more than 25 or 42% in numbers of operations for multiplying 2 ⁱ, i⩾1; these percentages of savings also grow with the size of the 2-D integer circular convolutions or the 2-D NTT     

Fast decimation-in-time algorithms for a family of discrete sine and cosine transforms

Fast decimation-in-time (DIT) algorithms for the various discrete cosine transforms (DCT) and discrete sine transforms (DST) are systematically developed, based on a radix-2 factorization of the transformation matrix. The results indicate these to be attractive alternatives to existing algorithms in terms of computational complexity and structural simplicity.Supported, in part, by NSERC Grant #A3635.     

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.     

Fast algorithm for calculation of both Walsh-Hadamard and Fourier transforms (FWFTs)

In the letter a fast and efficient algorithm is presented for calculating both DFT and the WHT. This is achieved through the factorisation of the intermediate transform T into a product of sparse matrices. The algorithm can be implemented using a single butterfly structure, and is amenable for both software and hardware implementations.<>     

A review of the discrete Fourier transform. 2. Non-radixalgorithms, real transforms and noise

For pt.1 see ibid., vol.7, no.4, p.169-77 (1995). Since fast algorithms for the discrete Fourier transform (DFT) were first introduced thirty years ago, they have had a major impact on signal processing and are now a basic part of every electrical engineer's education. However, some of the options, and particularly the recent advances, are not as widely known as they deserve. This article, the second of two which review the fast algorithms for the DFT, looks at algorithms for transforms whose orders are not a power of two. Also discussed are ways of adapting algorithms for purely real data, the problems of fixed-point noise, and implementation options with existing hardware     

Robust multiple color images encryption using discrete Fourier transforms and chaotic map

Based on discrete Fourier transforms and logistic-exponent-sine map, this paper investigates an encryption algorithm for multiple color images. In the encryption process, each color image represented in trinion matrix is performed by block-wise discrete trinion Fourier transforms. Then the first real matrix is constructed by splicing real and imaginary parts of transformed results. Followed by two-dimensional discrete Fourier transform, the second real matrix is synthesized only using half of the spectrum on the basis of the conjugate symmetry property. In order to further enhance the randomness of interim result, the random multi-resolution singular value decomposition is exploited. Afterwards, a sharing process is utilized to get final cipherimages. Numerical simulations performed on 300 color images have shown that quality of correctly decrypted images is much better, where the PSNR value is up to 305.03 dB. The number of changing pixel rate and unified average changing intensity are respectively greater than 99.99% and 33.33%, indicating good sensitivity. The comparison with other methods under noise and cropping attacks validates the reliability of the proposed algorithm.     

一种改进的二维离散极坐标Fourier变换快速算法

在雷达天线、图象配准、图象检索等领域内常常需要用极坐标表示二维数字信号的离散Fourier变换(DFT).与笛卡尔坐标系下的二维DFT不同,二维离散极坐标Fourier变换(DPFT)不具有行列可分性,直接计算非常耗时.本文提出一种改进的DPFT的快速算法.该算法针对二维阵列实信号,算法全部过程可用一维运算实现,大大降低了计算复杂度并且适用于实时处理.实验中与直接运算方法相比较,显示了该算法的良好性能.     

On approximating Fourier integral transforms by their discrete counterparts in certain geophysical applications

In the past, fast Fourier transforms (FFT's) have been used in geophysical data analysis and, with some success, in theoretical analysis. However, in the general situation when neither the function nor its transform image is of compact support, the digital transforms inevitably introduce aliasing errors in both the domain and range space. A technique to assess and minimize this error is given for a restricted set of functions.