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     

Computationally attractive real Gabor transforms

We present a Gabor transform for real, discrete signals and present a computationally attractive method for computing the transform. For the critically sampled case, we derive a biorthogonal function which is very localized in the time domain. Therefore, truncation of this biorthogonal function allows us to compute approximate expansion coefficients with significantly reduced computational requirements. Further, truncation does not degrade the numerical stability of the transform. We present a tight upper bound on the reconstruction error incurred due to use of a truncated biorthogonal function and summarize computational savings. For example, the expense of transforming a length 2048 signal using length 16 blocks is reduced by a factor of 26 over similar FFT-based methods with at most 0.04% squared error in the reconstruction     

A new framework for complex wavelet transforms

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 two-stage 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, non-redundant, 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 non-redundant. The second advantage of our approach is the flexibility to use any DWT in the transform implementation. As an example, we can exploit this flexibility to create the complex double-density DWT (CDDWT): a shift-insensitive, directional, complex wavelet transform with a low redundancy of (3/sup m/-1/2/sup m/-1) in m dimensions. To the best of our knowledge, no other transform achieves all these properties at a lower redundancy.     

A VLSI architecture for the real time computation of discrete trigonometric transforms

The Discrete Trigonometric Transforms are defined as a class of transforms. An algorithm for calculating the Discrete Fourier Transform is extended to cover all members of the defined class. A VLSI architecture which provides for real time calculation of these transforms is presented. This architecture provides simple interconnections, identical processing elements and minimal control complexity.     

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.     

Family of generalised multi-polarity complex Hadamard transforms

A family of generalised complex Hadamard transforms using the concept of polarity is introduced. Forward and inverse transformation kernels and methods of recursive generation of transform matrices using Kronecker products of elementary matrices are shown. Mutual relationships among transform matrices and spectra for arbitrary polarities are presented. Efficient ways of calculating spectra for logic functions through decision diagrams are also shown. The half-spectrum property is used to reduce further the computational requirements for both fast transforms and decision diagram based calculations     

On real and complex normalizations

This paper presents a general expression relating the complex-normalized scattering matrix of ann-port network to that of its augmentedn-port network normalizing to then 1 – resistances, where the Darlington equivalent network may be either reciprocal or nonreciprocal.     

Fast algorithm for computer complex number-theoretic transforms

A high-radix f.f.t. algorithm for computing transforms over GF(q2), where q is a Mersenne prime, is developed to implement fast circular convolutions. This new algorithm requires substantially fewer multiplications than the conventional f.f.t.     

Multidimensional, mapping-based complex wavelet transforms.

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.     

Solution of large dense complex matrix equations utilizingwavelet-like transforms

This paper presents the wavelet-like transforms, which are quite different from the wavelet transform for the solution of large dense complex matrix equations. From a purely numerical standpoint, these wavelet-like transforms are not true orthogonal transforms as the condition number of the resulting matrix changes after the thresholding. These effects are illustrated through examples     

A fast d.f.t. algorithm using complex integer transforms

For certain large transform lengths, Winograd's algorithm for computing the discrete Fourier transform (d.f.t.) is extended considerably. This is accomplished by performing the cyclic convolution, required by Winograd's method, by a fast transform over certain complex integer fields developed previously by the authors. This new algorithm requires fewer multiplications than either the standard fast Fourier transform (f.f.t.) or Winograd's more conventional algorithm.     

Solution of large dense complex matrix equations utilizing wavelet-like transforms

The objective of this paper is to explore the validity of various mathematical properties of the wavelet-like transforms for the solution from thin wire structures utilizing the conventional integral equation technique based on the method of moments. It is illustrated through numerical experimentation that the conventional mathematical bounds existing for the classical wavelet transform do not apply to the wavelet-like transforms. Also the classical wavelet transform is really not applicable for the solution of the matrix equations. These statements will be illustrated through examples.     

Relationship of nonlinear operations on real and complex signals

The relationship between a nonlinearity applied to a narrow-band real signal and an equivalent nonlinearity applied to a complex modulation signal is derived.     

基于复小波变换的地震资料角度域信息提取

局部角度域属性是地震资料非常重要的属性之一,应用地震波在局部角度域的传播特性,提取地震属性,分析介质的物性参数.通过对三雏地震数据的深层切片处理获取局部角度域属性,提出采用基于映射的复小波变换对二维地震资料两步算法,提出局部角度域信息的解决方案.     

基于复小波变换的地震资料角度域信息提取

局部角度域属性是地震资料非常重要的属性之一,应用地震波在局部角度域的传播特性,提取地震属性,分析介质的物性参数。通过对三维地震数据的深层切片处理获取局部角度域属性,提出采用基于映射的复小波变换对二维地震资料两步算法．提出局部角度域信息的解决方案。     

A note on multirate Z transforms

The conventional input-output relation for linear sampled-data systems whose output is sampled at an integer multiple of the input sampling rate is shown to give incorrect results if the system transfer function contains time delays that are integer multiples of the basic sampling interval T. The correct input-output relation is developed.     

复杂真实约束条件下的多星测控资源调度

测控资源调度是卫星调度研究领域的关键问题之一,其在多星条件下面临着因约束信息来源不同、结构差异大、表达模糊而难以建立统一的约束模型,以及求调度问题的最优解是NP-hard的且不易得到较优解的问题。为此,首先将多星测控问题表达为组合优化模型,再将复杂的约束信息归纳为一套约束,最后提出了一种双层并行约束匹配算法求解问题。与用户现有算法对比,所提算法的周期测控调度成功率提升了9%左右,且可以处理更多约束信息类型。     

A generalized Mobius transform and arithmetic Fourier transforms

A general approach to arithmetic Fourier transforms (AFT) is developed. The implementation is based on the concept of killer polynomials and the solution of an arithmetic deconvolution problem pertaining to a generalized Mobius transform. This results in an extension of the Bruns (1903) procedure, valid for all prime numbers, and in an AFT that extracts directly the sine coefficients from the Fourier series     

A VLSI for real-time linear operations and transforms

A VLSI system, utilizing 16 systolic array multipliers, designed to compute vector-matrix products at a rate of 640×10⁶ MACs is presented. The 448,000-transistor, 1.6-μm CMOS device incorporates a dual timing scheme which allows multiplexing of hardware units over identical operations. This hardware balances maximum internal operating frequency with external data bandwidth and results in an improved ration of the signal throughput to silicon area. This system has wide application because of its ability to compute correlation, convolution, linear transforms, and connections in multilayer perceptrons