The author provides a personal memoire and reviews his 60 years in Control Systems engineering and engineering education.

Over the last 15 years, the Internet has enabled new modes of authorship, new forms of open licensing and distribution, and new forms of collaboration and peer production to flourish. But in turn, new anxieties have arisen, especially concerning quality assurance, peer review, reuse, and modification. New innovations are appearing in peer review, endorsement, the measurement of trust, and the understanding of reputation, but without any systematic analysis of the general principles of quality assurance and peer review in this new era. In this paper, we propose a general set of principles for understanding what peer review was in the past and how it should be applied today to different kinds of content and in new platforms for managing quality. The principles stress an analysis not only on the content in materials but also on their context of use. Our focus is on open educational resources, and we present a case study of the open education project Connexions' lens system for quality assurance and review. However, the principles can be applied across multiple levels of knowledge production, including scholarship in engineering and science and reference materials in addition to educational publishing.

Although the discrete wavelet transform (DWT) is a powerful tool for signal and image processing, it has three serious disadvantages: shift sensitivity, poor directionality, and lack of phase information. To overcome these disadvantages, we introduce multidimensional, mapping-based, complex wavelet transforms that consist of a mapping onto a complex function space followed by a DWT of the complex mapping. Unlike other popular transforms that also mitigate DWT shortcomings, the decoupled implementation of our transforms has two important advantages. First, the controllable redundancy of the mapping stage offers a balance between degree of shift sensitivity and transform redundancy. This allows us to create a directional, nonredundant, complex wavelet transform with potential benefits for image coding systems. To the best of our knowledge, no other complex wavelet transform is simultaneously directional and nonredundant. The second advantage of our approach is the flexibility to use any DWT in the transform implementation. As an example, we exploit this flexibility to create the complex double-density DWT: a shift-insensitive, directional, complex wavelet transform with a low redundancy of (3M - 1)/(2M - 1) in M dimensions. No other transform achieves all these properties at a lower redundancy, to the best of our knowledge. By exploiting the advantages of our multidimensional, mapping-based complex wavelet transforms in seismic signal-processing applications, we have demonstrated state-of-the-art results.

This paper introduces a factorization for the design of oversampled filter banks with linear phase and complex-valued coefficients. Our approach is based on the design of rectangular paraunitary polyphase matrices and gives a general formulation for perfect reconstruction filter banks with uniform sampling in the subbands, critically sampled or oversampled, and linear phase filters with real- or complex-valued coefficients. By using a framework that is not restricted to modulation of a prototype window, as in oversampled modulated filter banks, we are able to increase the design freedom and to allow the design of non uniform bandwidth oversampled filter banks.

Connexions is a new approach to authoring, teaching, and learning that aims to fully exploit modern information technology. Available free of charge to anyone under open-content and open-source licenses, Connexions offers custom-tailored, current course material, is adaptable to a wide range of learning styles, and encourages students to explore the links among courses and disciplines. In contrast to the traditional process of textbook writing and publishing, Connexions fosters world-wide, cross-institution communities of authors, instructors, and students, who collaboratively and dynamically fashion “modules” from which courses are constructed. We believe the ideas and philosophy embodied by Connexions have the potential to change the very nature of textbook writing and publishing, producing a dynamic, interconnected educational environment that is pedagogically sound, both time and cost efficient, and fun. This paper overviews the philosophy and technology behind Connexions and describes a nascent community developing material for DSP education.

Shift sensitivity, poor directional selectivity and lack of phase information are three major disadvantages of the discrete wavelet transform, In earlier research, we demonstrated that projection-based complex wavelet transforms have excellent directional selectivity and explicit phase information, In this paper, we discuss the theory of projection-based complex wavelet transforms and we prove that these transforms can have reduced shift sensitivity with low transform redundancy. We also provide experimental results to demonstrate the reduced shift sensitivity of our transforms.

Despite the great popularity of critically-decimated filter banks, oversampled filter banks are useful in applications where data expansion is not a problem. We studied oversampled filter banks and showed that for some popular classes of filter banks it is not possible to obtain perfect reconstruction with rational (non-integer) oversampling ratios. Nevertheless, it is always possible to oversample the analysis filter bank by an integer factor, ie, there will be a similar synthesis bank which would provide perfect reconstruction. The analysis is carried within a time-aliasing framework development to analyze non-critically decimated filter banks.

Shift variance and poor directional selectivity, two major disadvantages of the discrete wavelet transform, have previously been circumvented either by using highly redundant, non-separable wavelet transforms or by using restrictive designs to obtain a pair of wavelet trees with a transform-domain redundancy of 4.0 in 2D. We demonstrate that excellent shift-invariance properties and directional selectivity may be obtained with a transform-domain redundancy of only 2.67 in 2D. We achieve this by projecting the wavelet coefficients from Selesnick's (Selesnick et al., 2000) almost-shift-invariant, double-density wavelet transform so as to separate approximately the positive and negative frequencies, thereby increasing directionality. Subsequent decimation and a novel inverse projection maintain the low redundancy while ensuring perfect reconstruction. Although our transform generates complex-valued coefficients allowing processing capabilities that are impossible with real-valued coefficients, it may be implemented with a fast algorithm that uses only real arithmetic. To demonstrate the efficacy of our new transform, we show that it achieves state-of-the-art performance in a seismic image-processing application.

This paper introduces an iterative algorithm for designing IIR digital filters that minimize a complex approximation error in an L/sub p/ sense. The algorithm combines ideas that have proven successful in the similar problem of L/sub p/ FIR filter design. We use iterative prefiltering techniques common in applications such as parameter estimation together with an iterative reweighted least squares (IRLS) method. The result is a double iterative approach that generates IIR filters of arbitrary magnitude and phase response and arbitrary numerator and denominator orders. Such filters can be used in a variety of applications in which the typical L/sub 2/ or L/sub /spl infin// error criteria might not be suitable.

Shift sensitivity and poor directionality, two major disadvantages of the discrete wavelet transform, have previously been circumvented either by using highly redundant, non-separable wavelet transforms or by using restrictive designs to obtain a pair of wavelet trees with a transform-domain redundancy of 4.0 in 2D. We demonstrate that excellent shift-invariance properties and directional selectivity may be obtained with a transform-domain redundancy of only 2.67 in 2D. We achieve this by projecting the wavelet coefficients from Selesnick's (see Wavelet Applications VII, Proceedings of SPIE, 2000) shift-insensitive, double-density wavelet transform so as to separate approximately the positive and negative frequencies, thereby increasing directionality. Subsequent decimation and a novel inverse projection maintain the low redundancy while ensuring perfect reconstruction. Although our transform generates complex-valued coefficients that provide valuable phase information, it may be implemented with a fast algorithm that uses only real arithmetic. To demonstrate the efficacy of our new transform, we show that it achieves state-of-the-art performance in a seismic image-processing application.

Poor directional selectivity, a major disadvantage of the 2D separable discrete wavelet transform (DWT), has heretofore been circumvented either by using highly redundant, nonseparable wavelet transforms or by using restrictive designs to obtain a pair of wavelet trees. In this paper, we demonstrate that superior directional selectivity may be obtained with no redundancy in any separable wavelet transform. We achieve this by projecting the wavelet transform coefficients onto the Softy space of signals and decimating before processing. A novel reconstruction step guarantees perfect reconstruction within this critically-sampled framework.

This paper describes the first steps toward a multiwavelet system that may retain the advantages of a traditional multiwavelet system while alleviating some of its disadvantages. We attempt to achieve this through the introduction of a novel property-the disjoint support of the multiscaling functions. We derive the conditions on the matrix filter coefficients that guarantee the disjoint support of multiscaling functions. The preliminary results demonstrate that multiwavelet systems with this property may be arbitrarily complex. We then establish the existence of multiwavelet systems with two scaling functions and approximation order=2.

This paper presents an efficient adaptive algorithm for designing FIR digital filters that are efficient according to an L/sub p/ error criteria. The algorithm is an extension of Burrus' (1992) iterative reweighted least squares (IRLS) method for approximating L/sub p/ filters. Such algorithm will converge for most significant cases in a few iterations. In some cases however, the transition bandwidth is such that the number of iterations increases significantly. The proposed algorithm controls such problem and drastically reduces the number of iterations required.

The Coifman wavelets created by Daubechies (1992, 1993) have more zero moments than imposed by specifications. This results in systems with approximately equal numbers of zero scaling function and wavelet moments and gives a partitioning of the systems into three well defined classes. The nonunique solutions are more complex than for Daubechies wavelets.

We describe a generalized scale-redundant wavelet transform which approximates a dense sampling of the continuous wavelet transform (CWT) in both time and scale. The dyadic scaling requirement of the usual wavelet transform is relaxed in favor of an approximate scaling relationship which in the case of a Gaussian scaling function is known to be asymptotically exact and irrational. This scheme yields an arbitrarily dense sampling of the scale axis in the limit. Similar behavior is observed for other scaling functions with no explicit analytic form. We investigate characteristics of the family of Lagrange interpolating filters (related to the Daubechies (1988) family of compactly-supported orthonormal wavelets), and finally present applications of the transform to denoising and edge detection.

We construct general biorthogonal Coifman wavelet systems, a new class of compactly supported biorthogonal wavelet systems with vanishing moments equally distributed for a scaling function and wavelet pair. A time-domain design method is employed and closed-form expressions for the impulse responses and the frequency responses of the corresponding dual filters are derived. The resulting filter coefficients are all dyadic fractions, which is an attractive feature in the realization of multiplication-free discrete wavelet transform. Even-ordered systems in this family are symmetric, which correspond to linear-phase dual filters. In particular, three filterbanks (FBs) in this family are systematically verified to have competitive compression potential to the 9-7 tap biorthogonal wavelet FB by Cohen et al., which is currently the most widely used one in the field of wavelet transform coding. In addition, the proposed FB's have much smaller computational complexity in terms of floating-point operations required in transformation, and therefore indicate a better tradeoff between compression performance and computational complexity.

We propose an algorithm that uses the discrete wavelet transform (DWT) as a tool to compute the discrete Fourier transform (DFT). The Cooley-Tukey FFT is shown to be a special case of the proposed algorithm when the wavelets in use are trivial. If no intermediate coefficients are dropped and no approximations are made, the proposed algorithm computes the exact result, and its computational complexity is on the same order of the FFT, i.e. O(N log/sub 2/ N). The main advantage of the proposed algorithm is that the good time and frequency localization of wavelets can be exploited to approximate the Fourier transform for many classes of signals resulting in much less computation. Thus the new algorithm provides an efficient complexity vs. accuracy tradeoff. When approximations are allowed, under certain sparsity conditions, the algorithm can achieve linear complexity, i.e. O(N). The proposed algorithm also has built-in noise reduction capability.

Recently, the Burrows Wheeler transform (BWT) has been proposed for text compression. The BWT based compression algorithm performs close to the best algorithm known today on a set of standard text files, and it has less complexity. In this paper we propose a novel waveform and image compression scheme using the Burrows Wheeler transform. We show that the discrete wavelet transform (DWT) could be used before the Burrows Wheeler transform to improve the compression performance for many natural signals and images. We demonstrate that the simple concatenation of the DWT and BWT coding performs comparably as the embedded zerotree wavelet (EZW) compression for images. Various techniques that significantly improve the performance of our compression scheme are also discussed.

Convolution is one of the most widely used digital signal processing operations. It can be implemented using the fast Fourier transform (FFT) with a computational complexity of O (N log N). The undecimated discrete wavelet transform (UDWT) is linear and shift invariant, so it can also be used to implement convolution. We propose a scheme to implement the convolution using the UDWT, and study its advantages and limitations.

A new method for measuring and designing a smooth wavelet basis which dispenses with the need for having a large number of zero moments of the wavelet is given. The method is based on minimizing the "discrete finite variation", and is a measure of the local "roughness" of a sampled version of the scaling function giving rise to a "visually smooth" wavelet basis. A smooth wavelet basis is deemed to be important for several applications and in particular for image compression where the goal is to limit spurious artifacts due to non-smooth basis functions in the presence of quantization of the individual subbands. The definition of smoothness introduced here gives rise to new algorithms for designing smooth wavelet basis with only one vanishing moment leaving free parameters, otherwise used for setting moments to zero, for optimization.

This paper presents a formula-based method for the design of IIR filters having more zeros than (nontrivial) poles. The filters are designed so that their square magnitude frequency responses are maximally-flat at /spl omega/=0 and at /spl omega/=/spl pi/ and are thereby generalizations of classical digital Butterworth filters. A main result of the paper is that, for a specified half-magnitude frequency and a specified number of zeros, there is only one valid way in which to split the zeros between z=-1 and the passband. IIR filters having more zeros than poles are of interest, because often, to obtain a good trade-off between performance and the expense of implementation, just a few poles are best.

A new nonlinear noise reduction method is presented that uses the discrete wavelet transform. Similar to Donoho (1995) and Donohoe and Johnstone (1994, 1995), the authors employ thresholding in the wavelet transform domain but, following a suggestion by Coifman, they use an undecimated, shift-invariant, nonorthogonal wavelet transform instead of the usual orthogonal one. This new approach can be interpreted as a repeated application of the original Donoho and Johnstone method for different shifts. The main feature of the new algorithm is a significantly improved noise reduction compared to the original wavelet based approach. This holds for a large class of signals, both visually and in the l/sub 2/ sense, and is shown theoretically as well as by experimental results.

Describes a set of programs for circular convolution and prime length FFTs that are short, possess great structure, share many computational procedures, and cover a large variety of lengths. The programs make clear the structure of the algorithms and clearly enumerate independent computational branches that can be performed in parallel. Moreover, each of these independent operations is made up of a sequence of sub-operations which can be implemented as vector/parallel operations. This is in contrast with previously existing programs for prime length FFTs: they consist of straight line code, no code is shared between them, and they cannot be easily adapted for vector/parallel implementations. The authors have also developed a program that automatically generates these programs for prime length FFTs.

We consider the design of digital filters and discuss the inclusion of explicitly specified transition bands in the frequency domain design of FIR filters. We put forth the notion that explicitly specified transition bands have been introduced in the filter design literature as an indirect and sometimes inadequate approach for dealing with discontinuities in the desired frequency response. We also present a rapidly converging, robust, simple algorithm for the design of optimal peak constrained least square lowpass FIR filters that does not require the use of transition bands. This versatile algorithm will design linear and minimum phase FIR filters and gives the best L/sub 2/ filter and a continuum of Chebyshev filters as special cases.

We propose a nonlinear, universal method based on wavelet thresholding to efficiently improve the performance of various coding schemes. Coarse quantization of the transform coefficients often results in some undesirable artifacts, such as ringing effect, contouring effect and blocking effect, especially at very low bit rate. We perform the wavelet-domain thresholding on the decompressed image to attenuate the quantization noise effect while maintaining the relatively sharp features (e.g. edges) of the original image. Both the objective quality and the subjective quality of the reconstructed image are significantly improved with the reduction of coding artifacts. Experimental results show that de-noising using the undecimated discrete wavelet transform (DWT) achieves better performance than using the orthonormal DWT, with an acceptable computational complexity (O(MN log/sub 2/ (MN)) for an image of size M/spl times/N).

We propose a novel method for simultaneous noise reduction and data compression based on shrinking, quantizing and coding the wavelet packet (WP) coefficients. A dynamic programming and fast pruning algorithm is used to efficiently choose the best basis from the entire library of admissible WP bases, and jointly optimize the bit allocation strategy and the quantization scheme in the rate-distortion framework. Soft-thresholding in the wavelet domain can significantly suppress noise, e.g., the speckles of the synthetic aperture radar images, while maintaining bright reflections for subsequent detection and recognition. Optimal bit allocation, quantization and entropy coding achieve the goal of compression while maintaining the fidelity of the image.

Multiplicity M, K-regular, orthonormal wavelet bases (that have implications in transform coding applications) have previously been constructed by several authors. The paper describes and parameterizes the cosine-modulated class of multiplicity M wavelet tight frames (WTFs). In these WTFs, the scaling function uniquely determines the wavelets. This is in contrast to the general multiplicity M case, where one has to, for any given application, design the scaling function and the wavelets. Several design techniques for the design of K regular cosine-modulated WTFs are described and their relative merits discussed. Wavelets in K-regular WTFs may or may not be smooth, Since coding applications use WTFs with short length scaling and wavelet vectors (since long filters produce ringing artifacts, which is undesirable in, say, image coding), many smooth designs of K regular WTFs of short lengths are presented. In some cases, analytical formulas for the scaling and wavelet vectors are also given. In many applications, smoothness of the wavelets is more important than K regularity. The authors define smoothness of filter banks and WTFs using the concept of total variation and give several useful designs based on this smoothness criterion. Optimal design of cosine-modulated WTFs for signal representation is also described. All WTFs constructed in the paper are orthonormal bases.

This paper examines the use of the iteratively reweighted least squares (IRLS) error algorithm to obtain an L/sub p/-approximation for the design of FIR digital filters with a complex-valued desired frequency response. The algorithm presented, introduced by Burrus and Barreto (see IEEE Proceed. ISCAS 92, p.545, 1992) for the design of 1-D linear-phase FIR filters, considers the case of 2>

This paper will look at an approach that uses symmetric properties of the basis function to remove redundancies in the calculation of discrete Fourier transform (DFT). We will develop an algorithm, called the quick Fourier transform (QFT), that will reduce the number of floating point operations necessary to compute the DFT by a factor of two or four over direct methods or Goertzel's method for prime lengths. Further by applying the idea to the calculation of a DFT of length-2/sup M/, we construct a new O(N log N) algorithm. The algorithm can be easily modified to compute the DFT with only a subset of input points, and it will significantly reduce the number of operations when the data are real. The simple structure of the algorithm and the fact that it is well suited for DFTs on real data should lead to efficient implementations and to a wide range of applications.>

Studies the use of the iteratively reweighted least squares (IRLS) algorithm to obtain an L/sub p/-approximation for the design of two-dimensional (2D) linear-phase finite impulse response (FIR) digital filters. The algorithm is based on an iterative optimization technique first introduced in Burrus et al. for the design of 1D linear-phase digital filters and is very useful in the design of filters that give a trade-off between the traditional L/sub 2/ and L/sub /spl infin// designs. The new algorithm proposed, in terms of the maximum error in frequency response and complexity of implementation, compares favorably with the L/sub p/ optimization technique proposed by Lodge and Fahmy in [1980] and also with those obtained using other methods. Design examples and a comparison summary are presented.>

The paper introduces a novel speckle reduction method based on thresholding the wavelet coefficients of the logarithmically transformed image. The method is computational efficient and can significantly reduce the speckle while preserving the resolution of the original image. Both soft and hard thresholding schemes are studied and the results are compared. When fully polarimetric SAR images are available, the authors propose several approaches to combine the data from different polarizations to achieve even better performance. Wavelet processed imagery is shown to provide better detection performance for the synthetic-aperture radar (SAR) based automatic target detection/recognition (ATD/R) problem.>

For short data sequences, Winograd's convolution algorithms attaining the minimum number of multiplications also attain a low number of additions, making them very efficient. However, for longer lengths they require a larger number of additions. Winograd's approach is usually extended to longer lengths by using a nesting approach such as the Agarwal-Cooley (1977) or Split-Nesting algorithms. Although these nesting algorithms are organizationally quite simple, they do not make the greatest use of the factorability of the data sequence length. The algorithm we propose adheres to Winograd's original approach more closely than do the nesting algorithms. By evaluating polynomials over simple matrices we retain, in algorithms for longer lengths, the basic structure and strategy of Winograd's approach, thereby designing computationally refined algorithms. This tactic is arithmetically profitable because Winograd's approach is based on a theory of minimum multiplicative complexity.>

An approach to teaching the fast Fourier transform (FFT) using specially designed exercises to be done on modern workstations is presented. The interactive programming, high-speed calculations, and versatile graphics of the software system, Matlab, have proven particularly effective. Example exercises are given and discussed.>

Wavelet-based lowpass and bandpass interpolation schemes that are exact for certain classes of signals including polynomials of arbitrarily large degree are discussed. The interpolation technique is studied in the context of wavelet-Galerkin approximation of the shift operator. A recursive dyadic interpolation algorithm makes it an attractive alternative to other schemes. It turns out that the Fourier transform of the lowpass interpolatory function is also (a positive) interpolatory function. The nature of the corresponding interpolating class is not well understood. Extension to the case of multiplicity M orthonormal wavelet bases, where there is an efficient M-adic interpolation scheme, is also given.>

Wavelet methods give a flexible alternative to Fourier methods in nonstationary signal analysis. The concept of band-limitedness plays a fundamental role in Fourier analysis. Since wavelet theory replaces frequency with scale, a natural question is whether there exists a useful concept of scale-limitedness. Obvious definitions of scale-limitedness are too restrictive, in that there would be few or no useful scale-limited signals. The authors introduce a viable definition for scale-limited signals, and show that the class is rich enough to include bandlimited signals, and impulse trains, among others. Moreover, for a wide choice of criteria, it is shown how to design the optimal wavelet for representing a given signal, and how to design robust wavelets that optimally represent certain classes of signals.>

It is shown that the wavelet-Galerkin discretization of linear translation invariant (LTI) operators has good numerical properties, arising from the vanishing moments property of wavelets. If a wavelet has M vanishing moments, then it can have at most M-1 continuous derivatives, and hence operators of the form d/sup p//dx/sup p/, where p>M, have to be considered as generalized derivatives. Even in this case the approximation results derived hold. Also, the virtual expansion theorem is useful in the sense that there is no need to compute the expansion coefficients of the function at some level V/sub triangle x/.>

The authors propose a method to fit a discrete-time pole-zero filter model H(z)=A(z)/B(z) to arbitrary complex-valued frequency response samples Y(u/sub i/), i=0, 1, . . ., t in the least-square sense. An important attribute of the technique is that the frequency locations u/sub i/, i=0, 1, 2, . . ., t need not be equally spaced around the unit circle. The initial estimates of the denominator coefficients of the model system function H(z) are obtained by using an iterative algorithm. Starting from these initial estimates, a Newton-Raphson gradient technique is used to reach a minimum of the error criterion. The numerator polynomial coefficients are subsequently obtained by solving another set of linear equations. Simulation results using a filter design example are provided.>

The authors propose the use of transition bands and transition functions in the ideal amplitude frequency response of a linear finite impulse response phase (FIR) digital filter to allow the analytical design of optimal least integral squared error filters with an explicit control of the transition band edges. Design formulas for approximations to ideal frequency responses which use a pth-order spline transition function are derived and analyzed. A variable-order spline is used with a method for optimally choosing the order. The results of this method are compared with those of other optimal methods.>

An efficient algorithm is presented for the computation of the continuous wavelet transform (CWT). CWTs arise in the analysis of bandpass signals that are scale-time perturbed. To detect scale-time perturbed signals, the CWT of the received signal has to be computed with respect to the signals being detected. Efficient algorithms exist for the computation of the discrete wavelet transform, because the DWT wavelets give rise to quadrature mirror filters which can be implemented using lattice structures. Computation of the CWT with respect to an arbitrary wavelet (not necessarily a DWT wavelet), is time consuming. The DWT wavelets are used to compute the CWT of a signal with respect to an arbitrary wavelet. This is accomplished by using the computational properties of compactly supported DWT wavelet bases.>

A new class of FFT (fast Fourier transform) algorithms that run very efficiently on digital signal processors (DSPs) is described. The algorithms are based on a tensor product factorization of the DFT (discrete Fourier transform). The tensor product factorization not only controls the breakdown into short-length DFTs but also shows the data flow between the various blocks. This allows a better scheduling of operations, which again gives a better utilization of the DSP pipelining/parallel capabilities, and leads to algorithms with significantly lower overhead than traditional methods. Several different programs have been implemented in assembly code for the TMS320C30 and simulated to find their execution times. The new algorithms are shown to be more than 20% faster than traditional sequential algorithms adapted to the processor, because of lower overhead, and better utilization of the parallel instruction sets and the pipelining is obtained.>

Implementation of the FFT (fast Fourier transform) on currently available DSP (digital signal processing) devices is facilitated by hardware bit-reverse counters that are used for the unscrambling of the data. C.S. Burrus (1988) showed how these counters can also be used in the case of higher radix algorithms. The concept is generalized here to radices r/sub 1/ and r/sub 2/. It is shown that if r/sub 1/=r/sub 2//sup k/ a radix-r/sub 1/ FFT can be easily put in a digit-reversed order based on radix r/sub 2/. For instance, a radix-4 or radix-8 FFT can be put in a bit-reversed (i.e. radix-2) order without any extra computation or data movement.>

The short-time fast Fourier transform (STFFT) is an important tool in speech and other time-varying signal processing areas. The STFFT is often required to be performed in real time, which makes it important that computationally efficient methods exist. Traditionally the STFFT has been computed by repeated application of the fast Fourier transform (FFT) at consecutive time instances. This method does not utilize the redundancies that exist between the FFTs at different times, which, especially for small time differences, are quite large. A method for computing the STFFT is described which utilizes the redundancy to reduce the number of operations required to compute the STFFT. The reduction depends on the length of the STFFT and the time difference between FFTs. This method is more efficient than the regular FFT method for up to very large time differences.>

The traditional Cooley-Tukey and the prime factor FFT algorithms either produce the output in scrambled order or the input data order must be prescrambled. Several methods for scrambling and unscrambling the DFT are presented. The new result in this paper is the observation that the radix-4, radix-8, or any radix-2mFFT can be modified to give the output in the same bit-reversed order as the radix-2 FFT.

Since 1965, when Cooley and Tukey published their famous paper on the radix-2 fast Fourier transform, much effort has gone into developing even more efficient algorithms. Most algorithms, however, do not directly handle real-valued data very well, and them exist several ways to solve that problem. This paper derives a new algorithm; the decimation-in-time real-valued split-radix FFT, which can transform any length N = 2Msequence but uses less operations than any other known real-valued FFF, which is the fastest Cooley-Tukey real-valued transform in use. Instead of breaking the transform down equally as in traditional algorithms, the even and odd indexed parts are broken down differently in the split-radix algorithm. This gives a significant savings in both additions and multiplications over any fixed radix Cooley-Tukey FFT. The paper compares the split-radix transform with several of the already existing methods such as the Hartley transform, the prime factor, Winograd, Cooley-Tukey etc, and shows in which cases a specific algorithm is faster than the rest.

This paper develops an approach to deriving special FFT and convolution algorithms, considering the architecture of special-purpose DSP micros with a hardware multiplier and an adjacent accumulator. Because of the build-in accumulator, it is possible to combine multiplications and additions into one operation, and hence the optimality criterion is redefined to minimize the total number of additions, multiplications and combined multiply-additions, which results in new interesting algorithms. The structure of the algorithms depends strongly on the nature of N - the sequence length. Where most conventional fast algorithms decompose convolutions completely, it turns out that because the adjacent accumulator can hides some of the additions, they should only be partly decomposed. The decomposition is done by index mapping and the implementation uses Winograd's ideas. Discrete Fourier transforms are also only partly decomposed, in contrast to most algorithms. The DFTs are converted into convolutions, and the convolutions are implemented as block processing. Comparisons show up to a 35 % improvement in execution speed.

The multiplicative complexity of the length-2ndiscrete Fourier Transform is derived. A constructive approach is followed which describes the set of algorithms that realize the minimum number of multiplications. The operation counts of minimum multiply algorithms are compared to other FFT algorithms. The basic method is extended to derive the multiplicative complexity of length-pnDFFs where p is an odd prime number.

This paper presents two techniques for computing a discrete transform of a vector of real-valued data using the Prime Factor Algorithm (PFA) with high-speed convolution. These techniques are applied to the Discrete Fourier Transform (DFT) and the Discrete Hartley Transform (DHT). The primary goals of these techniques are to eliminate unnecessary computations required when implementing a complex transform on a real-valued vector, to compute the transform in-place in the original length-N real vector, and to obtain the transform coefficients in-order. The two algorithms described require modification of the Winograd short-length transform modules to accommodate a real input. One technique replaces the modules in the Burrus-Eschenbacher PFA program with the modified real-input modules and constructs the complete transform in a final step of additions and subtractions after modules for each factor have been executed. The other technique uses these real-input DFT modules for part of the computation associated with each factor and requires complex input DFT modules for another part of the computation. These algorithms require exactly one half of the number of multiplications and slightly less than one half of the number of additions required by a complex-input PFA.

Most Cooley-Tukey, in-place Fast Fourier Transform (FFT) algorithms result in the output being permuted or scrambled in order. For a radix-2 FFT, this order can be easily found by reversing the order of the bits of the address, and the unscrambler is called a bit-reversed counter. In some machines, this unscrambling takes from 10% to 50% of the total execution time. This paper presents an in-place, radix-2 FFT that does the unscrambling while the FFT is being calculated rather than as a separate process. The theoretical framework is based on index maps [1] and ideas used on the in-place, in-order prime factor FFT (PFA) [2]. The non-scrambled algorithm is implemented in FORTRAN. The size of the program is essentially the same as the regular radix-2 FFT with its bit-reversed counter.

This paper examines the structure of the prime length DFT algorithms that are developed by Winograd's approach. It is shown that these algorithms have considerable structure and that this can be exploited to develop a straight forward design procedure that does not use the Chinese remainder theorem. This structure also allows the design of real - data programs, and the improvement the data transfer properties of the PFA.

A broad class of efficient, discrete Fourier transform algorithms is developed by partitioning short DFT algorithms into factors. The factored short DFT's are combined into longer DFT's using a prime factor algorithm (PFA). By exploiting a property which allows some of the factors to commute, a large set of possible DFT algorithms is generated which contains both the prime factor algorithm and the Winograd Fourier Transform Algorithm (WFTA) as special cases. The problem of finding an algorithm from this class which is optimal with respect to the specific add, multiply, and data transfer characteristics of a partlcular implementation is posed, and a highly effective dynamic programming algorithm is presented as a solution.

This paper presents an approach to calculating the discrete Fourier transform (DFT) using a prime factor algorithm (PFA). A very simple indexing scheme is employed that results in a flexible, modular program that very efficiently calculates the DFT in-place. A modification of this indexing scheme gives a new algorithm with the output both in-place and in-order at a slight cost in flexibility. This means only 2N data storage is needed for a length N complex FFT and no unscrambling is necessary. The basic part of a FORTRAN program is given. A speed comparison shows the new algorithm to be faster than both the Cooley-Tukey and the nested Winograd algorithms.