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.     

A 70-MHz 1.2-μm CMOS 16-point DFT processor

A chip architecture designed to compute a 16-point discrete Fourier transform (DFT) using S. Winograd's algorithm (1978) every 457 ns is presented. The 99500-transistor 1.2-μm chip incorporates arithmetic, control, and input/output circuitry with testability and fault detection into a 144-pin package. A throughput of 2.3×10¹² gate-Hz/cm² and 79-million multiplications/s is attained with 70-MHz pipelined bit-serial logic. Combined with similar chips computing 15- and 17-point DFTs, 4080-point DFTs can be computed every 118 μs. Using the 16- and 17-point chips, 272×272-point complex data imagery can be transformed in 4.25 ms. A 24-bit block floating-point data representation combined with an adaptive scaling algorithm delivers a numerical precision of 106 dB (17.6 bits) after computing 4080-point DFTs     

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     

Multidimensional vector radix FHT algorithms

In this paper, efficient multidimensional (M-D) vector radix (VR) decimation-in-frequency and decimation-in-time fast Hartley transform (FHT) algorithms are derived for computing the discrete Hartley transform (DHT) of any dimension using an appropriate index mapping and the Kronecker product. The proposed algorithms are more effective and highly suitable for hardware and software implementations compared to all existing M-D FHT algorithms that are derived for the computation of the DHT of any dimension. The butterflies of the proposed algorithms are based on simple closed-form expressions that allow easy implementations of these algorithms for any dimension. In addition, the proposed algorithms possess properties such as high regularity, simplicity and in-place computation that are highly desirable for software and hardware implementations, especially for the M-D applications. A close relationship between the M-D VR complex-valued fast Fourier transform algorithms and the proposed M-D VR FHT algorithms is established. This type of relationship is of great significance for software and hardware implementations of the algorithms, since it is shown that because of this relationship and the fact that the DHT is an alternative to the discrete Fourier transform (DFT) for real data, a single module with a little or no modification can be used to carry out the forward and inverse M-D DFTs for real- or complex-valued data and M-D DHTs. Thus, the same module (with a little or no modification) can be used to cover all domains of applications that involve the DFTs or DHTs.     

Interpolating multiwavelet bases and the sampling theorem

This paper considers the classical sampling theorem in multiresolution spaces with scaling functions as interpolants. As discussed by Xia and Zhang (1993), for an orthogonal scaling function to support such a sampling theorem, the scaling function must be cardinal (interpolating). They also showed that the only orthogonal scaling function that is both cardinal and of compact support is the Haar function, which is not continuous. This paper addresses the same question, but in the multiwavelet context, where the situation is different. This paper presents the construction of compactly supported orthogonal multiscaling functions that are continuously differentiable and cardinal. The scaling functions thereby support a Shannon-like sampling theorem. Such wavelet bases are appealing because the initialization of the discrete wavelet transform (prefiltering) is the identity operator     

A concurrent implementation of the prime factor algorithm onhypercube

The prime factor algorithm (PFA) is an efficient discrete Fourier transform (DFT) computation algorithm in which a one-dimensional DFT is tuned into a multidimensional DFT, consisting of a few short DFTs whose lengths are mutually prime, and then an efficient algorithm is used for the short DFTs. The PFA was implemented on a hypercube using CrOS III communication routines, taking 120 ms to compute the DFT of 5040 complex points using 32 nodes of the Caltech-JPL MARK III Hypercube. It took 105 ms to do a DFT of 4096 complex points using the Cooley-Tukey algorithm with the same hardware configuration. The performance of hypercubes MARK III, NCUBE, and iPSC and the relative importance of communication and calculation are analyzed. With the current communication speed the Cooley-Tukey algorithm performs fast on a massively concurrent processor and the PFA is advantageous when the number of processors is less than 64 or so. The experience with using the PFA also serves as a useful guide to a multidimensional fast Fourier transform implementation using any algorithm     

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.     

Arbitrary tilings of the time-frequency plane using local bases

We show how to design filters given a prescribed tiling of the time-frequency plane. Moreover, we impose on these filters the structure of local orthogonal bases. These bases were recently constructed as a generalization of the cosine-modulated filter banks in discrete time and local trigonometric bases in continuous time. They have been found to be of considerable practical importance due to their simplicity (all filters are obtained from a single prototype) and low computational complexity. We show examples of design, in particular, that of a critical-band system for use in audio coding     

Analysis of random PWM switching methods for three-level powerinverters

This paper presents a generalized theory which covers both two-level and three-level random pulsewidth modulation (RPWM) schemes. Various three-level RPWM schemes with low switching frequency are presented and compared with two-level schemes. Three-level RPWM schemes have less discrete harmonics and continuous noise than two-level RPWM schemes. They have desirable spectral characteristics and can be employed in high-voltage inverter-fed motor drives. Measurements have confirmed the theory and the attractive features of three-level RPWM schemes     

Codecell convexity in optimal entropy-constrained vector quantization

Properties of optimal entropy-constrained vector quantizers (ECVQs) are studied for the squared-error distortion measure. It is known that restricting an ECVQ to have convex codecells may preclude its optimality for some sources with discrete distribution. We show that for sources with continuous distribution, any finite-level ECVQ can be replaced by another finite-level ECVQ with convex codecells that has equal or better performance. We generalize this result to infinite-level quantizers, and also consider the problem of existence of optimal ECVQs for continuous source distributions. In particular, we show that given any entropy constraint, there exists an ECVQ with (possibly infinitely many) convex codecells that has minimum distortion among all ECVQs satisfying the constraint. These results extend analogous statements in entropy-constrained scalar quantization. They also generalize results in entropy-constrained vector quantization that were obtained via the Lagrangian formulation and, therefore, are valid only for certain values of the entropy constraint.     

Hidden Markov modelling of speech based on a semicontinuous model

The discrete hidden Markov model (HMM) is extended here by using a combination of continuous Gaussian density functions derived from a vector quantised codebook together with discrete HMM output probabilities. Experimental results for a vocabulary consisting of the digit set for a group of speakers have shown that the semicontinuous approach to HMM offers improved performance in comparison to both the discrete HMM and to dynamic time warping methods which incorporate template adaptation     

Use of discrete Laguerre sequences to extrapolate wide-band response from early-time and low-frequency data

Extrapolation of wide-band response using early-time and low-frequency data has been accomplished by the use of the orthogonal polynomials, such as Laguerre polynomials, Hermite polynomials, and Bessel-Chebyshev functions. It is a good approach to reduce the computational loads and obtain stable results for computation intensive electromagnetic analysis. However, all the orthonormal basis functions that have been used are all continuous or analog functions, which means we have to sample the polynomials both in time and frequency domains before we can use them to carry out the extrapolation. The process of sampling will introduce some errors, especially for high degrees or small scaling factors and, hence, may destroy the orthogonality between the polynomials of various degrees in a discrete sense. In this paper, we introduce the discrete Laguerre functions, which are directly derived using the Z transform and, thus, are exactly orthonormal in a discrete sense. The discrete Laguerre polynomials are fundamentally different from its continuous counterparts, except asymptotically when the sampling interval approaches zero. The other advantage of using these discrete orthonormal functions is that they do not give rise to the Gibbs phenomenon unlike its continuous counterpart. Using it in the extrapolation, the range or convergence can be extended both for the scaling factor and order of expansion, and at the same time, the quality of performance can be improved. Since the error of extrapolation is sensitive to the scaling factor, an efficient way to estimate the error as a function of the scaling factor is explained and its feasibility for any problem is validated by numerical examples of antennas.     

Fast Splitting$alpha$-Rooting Method of Image Enhancement: Tensor Representation

In the tensor representation, a two-dimensional (2-D) image is represented uniquely by a set of one-dimensional (1-D) signals, so-called splitting-signals, that carry the spectral information of the image at frequency-points of specific sets that cover the whole domain of frequencies. The image enhancement is thus reduced to processing splitting-signals and such process requires a modification of only a few spectral components of the image, for each signal. For instance, the$alpha$-rooting method of image enhancement can be fulfilled through processing separately a maximum of$3N/2$splitting-signals of an image$(Ntimes N)$, where$N$is a power of two. In this paper, we propose a fast implementation of the$alpha$-rooting method by using one splitting-signal of the tensor representation with respect to the discrete Fourier transform (DFT). The implementation is described in the frequency and spatial domains. As a result, the proposed algorithms for image enhancement use two 1-D$N$-point DFTs instead of two 2-D$Ntimes N$-point DFTs in the traditional method of$alpha$-rooting.     

Identifikation kontinuierlicher Systeme mit Hilfe zeitdiskreter Modelle

Most linear processes can be modeled as discrete time linear systems. A lot of well known methods have been established to identify such systems providing time discrete transfer functions. To find a continuous model is a much more complicated task. Discrete methods for identification allow very flexible pertubation signals. Therefore it will be shown how to determine continuous transfer functions out of discrete models by assuming different envelopes of the pertubation signal. The presented algorithm is implemented in the ANA 2.5 CAE software.     

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.     

Efficient Systolic Designs for 1- and 2-Dimensional DFT of General Transform-Lengths for High-Speed Wireless Communication Applications

In wireless communication, multiple receive-antennas are used with orthogonal frequency division multiplexing (OFDM) to improve the system capacity and performance. The discrete Fourier transform (DFT) plays an important part in such a system since the DFTs are required to be performed for the output of all those antennas separately. This paper presents area-time efficient systolic structures for one-dimensional (1-D) and two-dimensional (2-D) DFTs of general lengths. A low-complexity recursive algorithm based on Clenshaw’s recurrence relation is formulated for the computation of 1-D DFT. The proposed algorithm is used further to derive a linear systolic array for the DFT. The concurrency of computation has been enhanced and complexity is minimized by the proposed algorithm where an N −point DFT is computed via four inner-products of real-valued data of length ≈ (N/2). The proposed 1-D structure offers significantly lower latency, twice the throughput, and involves nearly the same area-time complexity of the corresponding existing structures. The proposed algorithm for 1-D DFT is extended further to obtain a 2-D systolic structure for the 2-D DFT without involving any transposition operation.     

A multidimensional Z-transform evaluation of the discrete finite difference time domain Green's function

Analytical expressions for frequency and time domain discrete Green's functions are developed below. Rather than discretizing the continuous Green's functions directly, we derive the discrete Green's functions from first principles, i.e., the difference equations. This is done with the purpose of obtaining discrete integral operators that would replicate results obtained via the finite difference time domain (FDTD) method. The main effort is directed at inversions of multidimensional frequency domain expressions in the Z-transform domain. The Green's functions obtained in this way coincide with time domain developments presented earlier both in the form of direct numerical computations and via combinatorics and the Catalan triangle. The Z-transform methodology, resulting from this development, provides an orderly manner for deriving expressions for multidimensional discrete integral operators that can be hybridized with FDTD-based differential operators in a self consistent manner.     

随机射线的概率分布及其应用

在使用随机射线方法建模无线传播信道时,需要求解以反射次数为指标的无线电波经过若干次反射以后达到特定位置的概率分布。该文使用信息论中的最大熵原理,首先计算在Manhattan距离度量下二维和三维空间连续情形和离散情形下随机射线的概率密度函数。然后计算在Euclid距离度量下二维和三维空间连续情形下随机射线的概率密度函数,以及作随机游动的随机射线在二维空间的概率密度函数。使用城市密集传播地区的测量数据验证随机射线理论模型结果的可靠性。所得结果对于无线随机传播信道建模具有理论指导意义。     

Convex cost functions in blind equalization

Existing blind adaptive equalizers that use nonconvex cost functions and stochastic gradient descent suffer from lack of global convergence to an equalizer setup that removes sufficient ISI when an FIR equalizer is used. The authors impose convexity on the cost function and anchoring of the equalizer away from the all-zero setup. They establish that there exists a globally convergent blind equalization strategy for 1D pulse amplitude modulation (PAM) systems with bounded input data (discrete or continuous) even when the equalizer is truncated. The resulting cost function is a constrained l₁ norm of the joint impulse response of the channel and the equalizer. The results apply to arbitrary linear channels (provided there are no unit circle zeros) and apply regardless of the initial ISI (that is whether the eye is initially open or closed). They also show a globally convergent stochastic gradient scheme based on an implementable approximation of the l₁ cost function