Hartley transforms over finite fields

A general framework is presented for constructing transforms in the field of the input which have a convolution-like property. The construction is carried out over finite fields, but is shown to be valid over the real and complex fields as well. It is shown that these basefield transforms can be viewed as “projections” of the discrete Fourier transform (DFT) and that they exist for all lengths N for which the DFT is defined. The convolution property of the basefield transforms is derived and a condition for such transforms to have the self-inverse property is given. Also, fast algorithms for these basefield transforms are developed, showing gains when compared to computations using the FFT. Application of the methodology to Hartley transforms over R leads to a simple derivation of fast algorithms for computing real Hartley transforms     

Algebraic Signal Processing Theory: Cooley–Tukey Type Algorithms for Real DFTs

In this paper, we systematically derive a large class of fast general-radix algorithms for various types of real discrete Fourier transforms (real DFTs) including the discrete Hartley transform (DHT) based on the algebraic signal processing theory. This means that instead of manipulating the transform definition, we derive algorithms by manipulating the polynomial algebras underlying the transforms using one general method. The same method yields the well-known Cooley-Tukey fast Fourier transform (FFT) as well as general radix discrete cosine and sine transform algorithms. The algebraic approach makes the derivation concise, unifies and classifies many existing algorithms, yields new variants, enables structural optimization, and naturally produces a human-readable structural algorithm representation based on the Kronecker product formalism. We show, for the first time, that the general-radix Cooley-Tukey and the lesser known Bruun algorithms are instances of the same generic algorithm. Further, we show that this generic algorithm can be instantiated for all four types of the real DFT and the DHT.     

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.     

快速变换算法三十年的发展

傅里叶变换快速算法发展已三十年，本文综述了高散变换快速算法的发展，特别是近几年的发展，其中包括传统的基2、基4、基8、分裂基算法的发展以及多维离散傅里叶变换、多维离散余（正）弦变换、多维离散W变换（哈特莱变换）的快速算法．阐述各种算法是如何将多维变换转换为一维变换的计算，并讨论了在有理数域上计算上述各种变换所需最小实数乘法的次数。     

Simple FFT and DCT algorithms with reduced number of operations

A simple algorithm for the evaluation of discrete Fourier transforms (DFT) and discrete cosine transforms (DCT) is presented. This approach, based on the divide and conquer technique, achieves a substantial decrease in the number of additions when compared to currently used FFT algorithms (30% for a DFT on real data, 15% for a DFT on complex data and 25% for a DCT) and keeps the same number of multiplications as the best known FFT algorithms. The simple structure of the algorithm and the fact that it is best suited for real data (one does not have to take a transform of two real sequences simultaneously anymore) should lead to efficient implementations and to a wide range of applications.     

A comparative review of real and complex Fourier-related transforms

Major continuous-time, discrete-time, and discrete Fourier-related transforms as well as Fourier-related series are discussed both with real and complex kernels. The complex Fourier transforms, Fourier series, cosine, sine, Hartley, Mellin, Laplace transforms, and z-transforms are covered on a comparative basis. Generalizations of the Fourier transform kernel lead to a number of novel transforms, in particular, special discrete cosine, discrete sine, and real discrete Fourier transforms, which have already found use in a number of applications. The fast algorithms for the real discrete Fourier transform provide a unified approach for the optimal fast computation of all discrete Fourier-related transforms. The short-time Fourier-related transforms are discussed for applications involving nonstationary signals. The one-dimensional transforms discussed are also extended to the two-dimensional transforms     

Basis-vector-decomposition based two-stage computational algorithmsfor DFT and DHT

Discrete Fourier transform (DFT)/discrete Hartley transform (DHT) algorithms based on the basis-vector decomposition of the corresponding transform matrices are derived. The computations of DFT are divided into two stages: an add/subtract preprocessing and a block-diagonal postprocessing. Both stages can be computed effectively. It can be proved that the computational complexity of the proposed DFT algorithm is identical to that of the most popular split-radix FFT, yet requires real number arithmetics only. Generation and storage of the real multiplicative coefficients are easier than that in conventional FFTs. Connections of the proposed approach with several well-known DFT algorithms are included. Furthermore, many variations of the proposed algorithm are also pointed out     

Normal bases expansion of the discrete cosine transform

In this correspondence, we show that the discrete cosine transform (DCT) can be obtained by projecting the discrete Fourier transform from the extension field to the basefield. Applying the framework of projection operator, a fast fully recursive algorithm for computing the DCT is also presented     

A three-dimensional DFT algorithm using the fast Hartley transform

A three-dimensional (3-D) Discrete Fourier Transform (DFT) algorithm for real data using the one-dimensional Fast Hartley Transform (FHT) is introduced. It requires the same number of one-dimensional transforms as a direct FFT approach but is simpler and retains the speed advantage that is characteristic of the Hartley approach. The method utilizes a decomposition of the cas function kernel of the Hartley transform to obtain a temporary transform, which is then corrected by some additions to yield the 3-D DFT. A Fortran subroutine is available on request.     

An Integer Approximation Method for Discrete Sinusoidal Transforms

Approximate methods have been considered as a means to the evaluation of discrete transforms. In this work, we propose and analyze a class of integer transforms for the discrete Fourier, Hartley, and cosine transforms (DFT, DHT, and DCT), based on simple dyadic rational approximation methods. The introduced method is general, applicable to several blocklengths, whereas existing approaches are usually dedicated to specific transform sizes. The suggested approximate transforms enjoy low multiplicative complexity and the orthogonality property is achievable via matrix polar decomposition. We show that the obtained transforms are competitive with archived methods in literature. New 8-point square wave approximate transforms for the DFT, DHT, and DCT are also introduced as particular cases of the introduced methodology.     

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.     

Fast radix-3/9 discrete Hartley transform

An efficient algorithm for computing radix-3/9 discrete Hartley transforms (DHTs) is presented. It is shown that the radix-3/9 fast Hartley transform (FHT) algorithm reduces the number of multiplications required by a radix-3 FHT algorithm for nearly 50%. For the computation of real-valued discrete Fourier transforms (DFTs) with sequence lengths that are powers of 3, it is shown that the radix-3/9 FHT algorithm reduces the number of multiplications by 16.2% over the fastest real-valued radix-3/9 fast Fourier transform (FFT) algorithm     

A comparison of the time involved in computing fast Hartley and fast Fourier transforms

It is shown that the DFT of a real sequence, formed via the Fast Hartley Transform, can be computed at most only 2 times faster than by using a complex Fast Fourier Transform. However, more sophisticated FFT algorithms exist which give the same speedup factor. A simple FHT subroutine is presented to illustrate the similarity of the FHT and FFT butterflies in their simplest forms.     

Discrete chirp-Fourier transform and its application to chirp rateestimation

The discrete Fourier transform (DFT) has found tremendous applications in almost all fields, mainly because it can be used to match the multiple frequencies of a stationary signal with multiple harmonics. In many applications, wideband and nonstationary signals, however, often occur. One of the typical examples of such signals is chirp-type signals that are usually encountered in radar signal processing, such as synthetic aperture radar (SAR) and inverse SAR imaging. Due to the motion of a target, the radar return signals are usually chirps, and their chirp rates include the information about the target, such as the location and the velocity. In this paper, we study discrete chirp-Fourier transform (DCFT), which is analogous to the DFT. Besides the multiple frequency matching similar to the DFT, the DCFT can be used to match the multiple chirp rates in a chirp-type signal with multiple chirp components. We show that when the signal length N is prime, the magnitudes of all the sidelobes of the DCFT of a quadratic chirp signal are 1, whereas the magnitude of the mainlobe of the DCFT is √N. With this result, an upper bound for the number of the detectable chirp components using the DCFT is provided in terms of signal length and signal and noise powers. We also show that the N-point DCFT performs optimally when N is a prime     

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.     

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.     

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.     

Generalized discrete Hartley transforms

The discrete Hartley transform is generalized into four classes in the same way as the generalized discrete Fourier transform. Fast algorithms for the resulting transforms are derived. The generalized transforms are expected to be useful in applications such as digital filter banks, fast computation of the discrete Hartley transform for any composite number of data points, fast computations of convolution, and signal representation. The fast computation of skew-circular convolution by the generalized transforms for any composite number of data points is discussed in detail     

Computationally Efficient FIR Filtering of Polynomial Signals in DFT Domain

Fast unbiased finite impulse response (UFIR) filtering of polynomial signals can be provided in the discrete Fourier transform (DFT) domain employing fast Fourier transform (FFT). We show that the computation time can further be reduced by utilizing properties of UFIR filters in the DFT domain. The transforms have been found and investigated in detail for low-degree FIRs most widely used in practice. As a special result, we address an explicit unbiasedness condition uniquely featured to UFIR filters in DFT domain. The noise power gain and estimation error bound have also been discussed. An application is given for state estimation in a crystal clock employing the Global Positioning System based measurement of time errors provided each second. Based upon it, it is shown that filtering in the time domain takes about 1?second, which is unacceptable for real-time applications. The Kalman-like algorithm reduces the computation time by the factor of about 8, the FFT-based algorithm by about 18, and FFT with the UFIR filter DFT properties by about 20.     

快速超复数傅氏变换和超复数互相关的新算法及应用

超复数把彩色图像作为一个矢量整体进行处理,与传统算法相比,它能更好地描述图像的色彩关联,超复数互相关已广泛应用到彩色图像处理的各个领域.本文首先分析和介绍了目前的实现二维超复数傅氏变换和超复数互相关的快速方法,然后通过把超复数按实部和各个虚部展开,分别进行传统的快速傅氏变换,再把对应的单位虚向量还原,从而为超复数傅氏变换和超复数互相关提出了一种新的快速算法.分析表明:本文提出的方法比目前现有的方法更简单易行,且计算量更小.最后,本文介绍了我们把超复数互相关技术应用到彩色目标跟踪上获得的一些新结果.