Home Home
Erich Fuchs, University of Passau (Germany)
Klaus Donner, University of Passau (Germany)
Only a few time series methods are applicable to signal trend analysis under real-time conditions. The use of orthogonal polynomials for least-squares approximations on discrete data turned out to be very efficient for providing estimators in the time domain. A polynomial extrapolation considering signal trends in a certain time window is obtainable even for high sampling rates. The presented method can be used as a prediction algorithm, e.g. in threshold monitoring systems, or as a trend correction possibility preparing the analysis of the remaining signal. In the theoretical derivation, the recursive computation of orthogonal polynomials allows the development of these fast algorithms for least-squares approximations in moving time windows.
ic971965.pdf ic971965.pdf
TOP
Yi Chu, National Taiwan Inst. of Technology (Taiwan)
Wen-Hsien Fang, National Taiwan Inst. of Technology (Taiwan)
Shun-Hsyung Chang, National Ocean University (Taiwan)
Modern subspace-based algorithms can offer high-resolution spectral estimates but with a cost of high computational complexity for the eigenvalue decomposition (EVD) involved. In this paper, we propose a novel preprocessing scheme which can be used in conjunction with the subspace-based algorithms to alleviate the high computations previously required. The new scheme is to demodulate the input data first, and then takes the computationally efficient discrete-time Haar wavelet transform (HWT). Only the principle subband component (PSC) of the transformed data is kept for further processing, which not only retains the same amount of information but also possesses the same characteristic as that of the original (noiseless) harmonic data. The subspace-based algorithms are thus applicable to this new set of transformed data but with substantially reduced computational load. Some simulation results are provided to justify the proposed approach.
ic971969.pdf ic971969.pdf TOP
Haitao Guo, Rice University (U.S.A.)
C. Sidney Burrus, Rice University (U.S.A.)
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(Nlog_2N)$. 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 v.s. 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.
ic971973.pdf ic971973.pdf TOP
Dragutin Sevic, INFIZ, Belgrade (Yugoslavia)
Miodrag Popovic, University of Belgrade (Yugoslavia)
In this paper a new implementation of the two-dimensional Extended Lapped Transform (2-D ELT) is proposed. Compared to the separable solution, proposed by Malvar [1], the new realization of 2-D ELT has reduced arithmetic complexity. Computational savings are achieved because scaling and inverse scaling of butterfly matrices, suggested by Malvar for 1-D case, are, after some modifications of the basic separable algorithm, extended to 2-D case. The new implementation has the same frequency response as Malvar's.
ic971977.pdf ic971977.pdf TOP
Isabel García, University of Extremadura (Spain)
Consuelo Gonzalo, Univ. Politécnica de Madrid (Spain)
Margarita Perez-Castellanos, Univ. Politécnica de Madrid (Spain)
José A. Moreno, University of Extremadura (Spain)
José M. Sánchez-Dehesa, University of Extremadura (Spain)
This paper presents a new iterative method to speed up the DWDF computation. At the present it has been considered from a computational point of view as an 1-D section of the Wigner Kernel (WK) N points FT's. We purpose a new way to compute the DWDF based on the symmetry properties of the WK and the cosine function. The proposed algorithm is doubly based on a subdivision procedure: on the one hand we have subdivided for each m-value the sum over the k variable into log2N/4-PL partial sums, where PL is the k parity level. And the other hand for each n-value the algorithm computes the DWDF elements by grouping its in group depending on the m PL. The algorithm has been optimized to reduce the accesses of memory, and it improves the FFT algorithms when the number of samples is less than 256 and for this number the algorithm match the FFT algorithms.
ic971981.pdf ic971981.pdf TOP
Joseph M. Winograd, Boston University (U.S.A.)
S. Hamid Nawab, Boston University (U.S.A.)
We present a probabilistic complexity analysis of a class of multi-stage algorithms for computing successive approximations to the DFT. While the quality of the approximate spectra obtained after any stage of these algorithms can be readily quantified in terms of commonly used input-independent metrics of spectral quality, each stage's arithmetic complexity is dependent on the nature of the input signal. Modeling the input signal as a stationary Gaussian-distributed random process, we obtain estimates of the distribution of the number of arithmetic operations required to complete any algorithm stage. This enables the derivation of important design information such as the probability with which a desired quality of approximation is achieved within a given arithmetic bound. Our results are verified using a Monte Carlo analysis.
ic971985.pdf ic971985.pdf TOP
Cuong Pham, St. Clara University (U.S.A.)
Tokunbo Ogunfunmi, St. Clara University (U.S.A.)
In this paper, by exploiting the Total Least-Square (TLS) closed-form solution and using the state-space structure in Krein space, we will show that the solution of the TLS problems can be computed via the recursive Kalman Filtering algorithm. This makes it possible to use the TLS in real-time applications.
ic971989.pdf TOP
Richard J. Kozick, Bucknell University (U.S.A.)
Maurice F. Aburdene, Bucknell University (U.S.A.)
A general approach is presented for implementing discrete transforms as a set of first-order or second-order recursive digital filters. Clenshaw's recurrence formulae are used to formulate the second-order filters. The resulting structure is suitable for efficient implementation of discrete transforms in VLSI or FPGA circuits. The general approach is applied to the discrete Legendre transform as an illustration.
ic971993.pdf ic971993.pdf TOPAndreas Klappenecker, University of Karlsruhe (Germany)
We show that it is possible to define Hartley-like transforms for (generalized) character tables of finite groups. This large class of transforms include Hartley transforms for discrete Fourier transforms over abelian groups and Hartley-like transforms for the discrete cosine transform of type I.
ic971997.pdf ic971997.pdf TOP
Peceli Gabor, Dept. of Meas.& Instr. Eng., Technical University of Budapest (Hungary)
Annamaria R. Varkonyi-Koczy, Dept. of Meas.& Instr. Eng., Technical University of Budapest (Hungary)
Block-oriented signal processing techniques have exceptional role due to the availability of fast algorithms. However, if larger data segments are to be evaluated in real-time, the delay caused by the block-oriented approach is not always tolerable especially if the response time of our evaluating system is also specified. This can be exceptionally critical if the signal processing is related to feedback loops. In this paper block-oriented signal processing methods are combined with recursive ones. This combination reduces the delay problem caused by the block-oriented fast algorithms and at the same time keeps the computational complexity on relatively low level. Possibly the most original component of the suggested solution is the extension of given size signal transformer-bank channels (e.g. DFT channels) toward larger blocks simply via recursive averaging.
ic972001.pdf ic972001.pdf TOP
Abdulnasir Hossen, University of Kiel (Germany)
Ulrich Heute, University of Kiel (Germany)
The discrete cosine transform (DCT) has a variety of applications in image and speech processing. The idea of the subband-DFT (SB-DFT) [1], [2] is applied in [3] to the DCT. In this paper the basic idea of the SB-DCT is discussed which is based on subband decomposition of the input sequence. Approximation is done by discarding the computations of bands of little energy. The complexity of this fast approximate method is examined in comparing it with a fast cosine-transform method [4] in terms of program running-time. New accurate analysis of the errors due to the approximation is presented for any number of decomposition stages. New applications of the SB-DCT in speech cepstrum analysis and in echo detection are also included by using the SB-DCT instead of the full-band FFT in calculating the real and complex cepstra.
ic972005.pdf ic972005.pdf TOP
Annamaria R. Varkonyi-Koczy, Dept. of Meas.& Instr. Eng., Technical University of Budapest (Hungary)
Sergios Theodoridis, University of Athens (Greece)
Transform-domain adaptive signal processing proved to be very successful in very many applications especially where systems with long impulse responses are to be evaluated. The popularity of these methods is due to the efficiency of the fast signal transformation algorithms and that of the block oriented adaptation mechanisms. In this paper the applicability of the fast sliding transformation algorithms is investigated for transform domain adaptive signal processing. It is shown that these sliding transformers may contribute to a better distribution of the computational load along time and therefore enable higher sampling rates. It is also shown that the execution time of the widely used Overlap-Save and Overlap-Add Algorithms can also be shortened. The prize to be paid for this improvements is the increase of the end-to-end delay which in certain configurations may cause some degradation of the tracking capabilities of the overall system. Fortunately, however, there are versions where this delay does not hu
ic972009.pdf ic972009.pdf TOP