Show all abstracts
View Session
- Keynote Address
- Time-Frequency and Higher-Order Statistical Analysis I
- Time-Frequency and Higher-Order Statistical Signal Analysis II
- Time-Frequency and Higher-Order Statistical Signal Analysis III
- Nonlinearity-Constrained Optimization
- Adaptive Subspace Tracking
- Algorithms for Structured Matrices
- Algorithms for Signal and Image Processing
- Preconditioned Methods
- Implementations I
- Implementations II
Keynote Address
Statistical array signal processing of measured sonar and seismic data
Johann F. Boehme
Show abstract
Statistically motivated methods of array signal processing are investigated. One application of interest is source detection and location possibly followed by signal filtering with high resolution from passive sonar data recorded by a towed array. The second application is seismic signal retrieval from regional events with the problem of phase detection and separation using data from the GERESS array in Germany. Approximate maximum likelihood in the frequency domain is used for detection and parameter estimation of wideband signals superimposed by stationary noise. Numerical procedures for corresponding optimization and tests are explained. Results of numerical experiments with sonar data measured in the Baltic Sea and with GERESS data are discussed.
Time-Frequency and Higher-Order Statistical Analysis I
Modulated cumulant sequences applied to MA-model identification
Thomas Kaiser
Show abstract
Cumulant sequences have become a more and more powerful tool in statistical signal processing. Through modulation of cumulant sequences we have inserted some degrees of freedom called modulation frequencies. We will show the usefulness of this modulated cumulant sequences by a new linear method for MA-parameter estimation which avoids some disadvantages of existing methods. Furthermore, we develop a modification of the method for additive arbitrarily distributed noise. Extensive simulations have shown a significant improvement of the parameter estimation accuracy.
High-order statistics for sinusoid peak detection
Show abstract
Detection and estimation of harmonic signals embedded in noise is one of the most encountered problems in the signal processing area. Much research has been done for solving such a problem regarding its importance in many applications. Second order statistics have been used extensively by many authors such as Whittle, Bartlett, Hannan, and Priestley. Each of them proposed a test for harmonic signal detection. However, most of these tests have been proposed under the Gaussina assumption. As a matter of fact, when the the noise is non- Gaussian, statistics of higher order could provide much more information. This is where this paper is directed. We particularly focus our attention on the third and fourth order cumulant methods. Statistical tests based on an extension of the existing tests are used and their efficiency analyzed and discussed.
Time-Frequency and Higher-Order Statistical Signal Analysis II
Decomposition of time-frequency distributions using scaled-window spectrograms
Show abstract
The decomposition of time-frequency representations (TFRs) in terms of weighted spectrograms has been recently proposed by several authors. Spectrogram decomposition concepts allow inner products to be used in the computations rather than the more cumbersome outer products usually associated with TFR computations. Kernels are decomposed in terms of eigenvectors in such a manner that a TFR may be represented by a truncated spectrogram series according to the strength of the eigenvalues associated with these eigenvectors. Many TFRs can be represented by relatively few spectrograms due to the small contributions of the remaining spectrograms with eigenvalues below some threshold value. The windows of the spectrograms forming the spectrogram series are the eigenvectors of the decomposition of the kernel of the particular representation. In the present paper it is shown how full TFR representations can be obtained by using a carefully chosen set of scaled cross spectrogram windows, thus avoiding the inherent approximations of the eigenvector approach. Much redundancy can be taken advantage of to permit computation of a small number of short-time Fourier transforms (STFTs). It is not practical to compute the Wigner distribution via the spectrogram decomposition approach due to the fact that the singular values of the decomposition are plus or minus one, precluding truncation of the spectrogram series. The new approach, on the other hand, can represent a Wigner distribution and other TFRs with a small number of STFTs. These STFTs can be used to compute a number of spectrograms and cross-spectrograms which, when appropriately weighted and summed, yield a given TFR, depending on the kernel used in the decomposition.
New approach for interference excision in spread spectrum using time-frequency distributions
Show abstract
The capability of the time-frequency distributions (TFDs) to properly represent a single as well as multiple component signals in time and frequency permits the application of a new approach for interference excision in spread spectrum communication systems. In this paper, the instantaneous frequency estimate from the TFD is used to construct a finite impulse response filter which substantially reduces the interference power with a minimum possible distortion of the desired signal. The proposed technique is therefore a case of open loop adaptive filtering. Three- and five-coefficient zero phase excision filters are considered. Closed form expressions of the improvement of SNR at the receiver correlator output using the TFD-based adaptive filtering are derived.
Polynomial Wigner-Ville distributions
Messaoud Benidir,
Boualem Boashash
Show abstract
We propose a representation of the derivitive (phi) ' of any general polynomial (phi) of degree N in terms of Q equals N + 1 given parameters: t1,...,tQ. This representation allows us to express the derivative as a linear comination of q arbitrary ratios of [(phi) (t + (tau) (kappa )) - (phi) (t - (tau) (kappa ))]/(tau) (kappa ) calculated at q arbitrary points (tau) 1,...,(tau) q, where q denotes the integer part of (N + 1)/2. The coefficients appearing in this decomposition are independent of the polynomial coefficients. As an application, we give a formula that allows us to compute (phi) '(t) without using the coefficients of the polynomial (phi) (t) and establish a property of the polynomial Wigner-Ville distribution.
Uncertainty principles of the short-time Fourier transform
Show abstract
We show that there are a number of uncertainty principles for the short-time Fourier transform and spectrogram. Explicit expressions are derived and examples given. Also, we generalize the concept of the short-time Fourier transform to arbitrary variables.
Time-Frequency and Higher-Order Statistical Signal Analysis III
Pitch-based methods for speech detection and automatic frequency recovery
Show abstract
There are many applications for which it is desireable to reliably detect the presence of speech. Examples of these applications are speech compression, voice activated devices and machine speech recognition. In this paper, a method of speech detection is developed which uses a frequency-domain pitch-based signal-to-noise ratio (SNR) estimate. This method takes full advantage of the spectral structure of pitch, which is the primary speech excitation function. The primary output of the detection algorithm is a decision that speech is present or not present. In addition, the algorithm provides an estimate of the speech SNR which may be used to estimate signal quality. This SNR estimate is important for applications such as estimating the reliability of machine-based recognition processes. Additional advantages of this method are that it is independent of signal gain and it works well under adverse conditions such as poor SNR and in the presence of interference. A by-product of the pitch-based detection process is a method for automatic recovery of frequency offset of mistuned analog speech. Mistuning is a condition which can arise in the demodulation of single-side-band amplitude-modulated (SSB-AM) speech if the precise carrier is not used in the demodulation process. This can cause severe problems since speech becomes nearly unintelligible if it is mistuned more than 100 Hz. The methods presented here use a double complex correlation of the complex speech spectrum to recover the carrier offset. This process provides significantly better resolution than more conventional correlation processes based on the speech power- spectrum.
Modeling of newborn EEG data for seizure detection
Mark Roessgen,
Abdelhak M. Zoubir,
Boualem Boashash
Show abstract
Seizures are often the first sign of neurological disease or dysfunction in the human newborn. Their clinical manifestation however, is often subtle, which tends to hinder their diagnosis. This represents an undesireable situation since the failure to quickly and accurately diagnose seizure can lead to long term brain injury or even death. In this paper, the problem of automatic seizure detection in the newborn based on the electroencephalogram (EEG) is considered. It is shown that good detection performance of electrographic seizure, which is the manifestation of seizure within the EEG, is possible using a new approach which is based on a model for the generation of the EEG. This model is derived from the histology and biophysics of a localized portion of the brain and is thus physically motivated. The model for EEG seizure is first presented along with an estimator for the model parameters. Then a seizure detection scheme based on the model parameter estimates is suggested. The method is then used to detect seizure in both simulated and real newborn EEG data. This approach gives superior performance over conventional classification approaches which rely on training data to produce observable test statistics. This is because, in general, trained classifiers are particularly susceptible to the extreme variability of the EEG over time as well as from patient to patient.
Time-frequency analysis of radar target backscatter
Show abstract
Studies of two orbiting spheres demonstrate the usefulness of time-frequency distributions for the analysis of radar signals. The spheres served as a simplified model for moving blades of an engine propeller or helicopter rotor. Illuminating the moving spheres with a continuous wave radar generated a backscatter signal which was difficult to interpret in either the time or the frequency domains. By applying the binomial distribution (a discrete time-frequency distribution) we could clearly associate each sphere with its corresponding doppler return. The binomial distribution provided a detailed view of the target dynamics, opening the way for target classification and identification. The structures and details available in the time- frequency domain were not readily exploited in the original signal representation.
Classification of digital modulation types
Show abstract
We review the standard frequency domain methods for modulation classification as a baseline for comparison with new approaches. A new procedure based on the singular value decomposition of a particular data matrix is developed. This matrix has some very interesting properties that facilitate a solution of a difficult problem of QPSK versus MSK classification. Performance of the new method is assessed via simulations and compared against those in the published literature.
Identification of a class of time-invariant and time-varying nonlinear systems under non-Gaussian excitation
Johnathon C. Ralston,
Abdelhak M. Zoubir,
Boualem Boashash
Show abstract
We consider the identification of nonlinear systems when the excitation is a non-Gaussian process. Closed from expressions are found for a class of nonlinear time-invariant as well as for time-varying systems which are excited by stationary and nonstationary inputs, respectively. The nonlinear model used represents a subset of the Volterra series, judiciously chosen so that closed form expressions can be resolved for non-Gaussian inputs. Nonlinear coherence functions are also derived in closed form. Estimation issues are discussed. Two examples are given to illustrate the general results.
Nonlinearity-Constrained Optimization
Optimization and performance of broadband microphone arrays
Flavio Lorenzelli,
Arthur Wang,
D. Korompis,
et al.
Show abstract
This paper considers various wideband signal model optimization techniques and associated performance results for adaptive and steerable but fixed beam microphone array processing for hearing aid applications in freespace and reverberant conditions. We first review and compare various conventional broadband and narrowband array optimization techniques. These include the minimization of the output array power subject to desired signal distortion constraint; the maximization of the array gain subject to white noise gain and linear constraints; and maximum energy criterion subject to norm, linear, and quandratic distortion constraints. Then new results on maximum energy criterion broadband array optimization formulated for sub- band processing are presented. The uniformly spaced sub-band and the nonuniformly spaced sub-band using quandrature mirror filter approaches are treated. Finally, various simulation results under the maximum energy criterion for free-space and reverberant conditions are presented to demonstrate the usefulness of this class of microphone arrays.
Penalty function method for sidelobe control in least squares adaptive beam forming
Show abstract
The weights required to maximize the SNR for array processing are well known and used extensively. However, in realistic situations it is often desirable to consider other factors. A common problem is the reduction of sidelobe jitter and sidelobe suppression while simultaneously maximizing SNR. In this paper we discuss a penalty function approach which can be used to satisfy all of these requirements by constraining a beampattern to lie arbitrarily close to a desired or quiescent beampattern and also satisfy a conventional look direction gain constraint. By a simple transformation it is possible to show how, in certain situations of physical interest, the method is equivalent to constraining the weight vector itself. We show how this method can be used for linear array and how the performance is affected by varying a user defined parameter. We conclude by showing how the method can envisaged as being equivalent to both a subspace projection technique and to diagonal loading with an extra quiescent constraint.
Antenna pattern synthesis through convex optimization
Herve Lebret
Show abstract
Antenna pattern synthesis deals with choosing control parameters (the complex weights) of an array of antennas, in order to achieve a set of given specifications. It appears that these problems can often be formulated as convex optimization problems, which can be numerically solved with algorithms such as the ellipsoid algorithm of interior point methods. After a brief presentation of antenna pattern synthesis and of convex optimization, we illustrate then with simulations results. We first minimize the sidelobe levels of a cosecant diagram. Then we show an example of interference cancellation and compare it to adaptive techniques. We will also introduce the important problem of robust antenna arrays.
Semidefinite programming for quadratically constrained quadratic programs
Julia A. Olkin,
Paul James Titterton Jr.
Show abstract
We consider the linear least squares problem subject to multiple quadratic constraints, which is motivated by a practical application in controller design. We use the techniques of convex optimization, in particluar, interior-point methods for semi-definite programming. We reduce a quasi-convex potential function. Each iteration requires calculating a primal and dual search direction and minimizing along the plane defined by these search directions. The primal search direction requires solving a least squares problem whose matrix is composed of a block- Toeplitz portion plus other structured matrices. We make use of Kronecker products and FFTs to greatly reduce the calculation. In addition, the matrix updates and matrix inverses in the plane search are actually low-rank updates to structured matrices so we are able to further reduce the flops required. Consequently, we can design controllers for problems of considerable size.
Adaptive Subspace Tracking
Simultaneous subspace tracking and rank estimation
Aleksandar Kavcic,
Bin Yang
Show abstract
Jacobi-type singular value decomposition (SVD) is an exceptionally suitable method for recursive SVD updating. It has a low computational complexity per update, O(n2), where n is the problem size. Due to its parallel structure, it is very attractive for real-time applications on systolic arrays. In frequency and angle of arrival tracking problems, SVD can be used to track the signal subspace. Typically, only a few, r, dominant eigencomponents need to be tracked, where r is less than n. In this paper we show how to modify the Jacobi-type SVD to track only the r-dimensional signal subspace by forcing the (n - r)-dimensional noise subspace to be spherical. Thereby, the computational complexity is brought down from O(n2) to O(nr). Furthermore, we show how to exploit the structure of the Jacobi-type SVD to estimate the signal subspace dimension, r, in addition to tracking the subspace itself. Most available computationally efficient subspace tracking algorithms rely on off-line estimation of the singal subspace dimension. This acts as a bottleneck in real-time parallel implementations. The Jacobi-type spherical subspace tracking algorithm presented in this paper is thus a subspace tracking method of computational complexity O(nr), capable of tracking both the signal subspace and its dimension simultaneously. Thereby, the parallelism of the algorithm is not destroyed, as demonstrated in a systolic array implementation. Simulation results are presented to show the applicability of the algorithm in adaptive frequency tracking problems.
Local and global passivity relations for Gauss-Newton methods in adaptive filtering
Markus Rupp,
Ali H. Sayed
Show abstract
We provide a time-domain analysis of the robustness and stability performance of Gauss- Newton recursive methods that are often used in identification and control. Several free parameters are included in the filter description while combining the covariance update with the weight-vector update; the exponentially weighted recursive least squares algorithm being an important special case. One of the contributions of this work is to show that by properly selecting the free parameters, the resulting filter can be shown to impose certain bounds on the error quantities, thus resulting in desireable robustness and stability properties. We also show that an intrinsic feedback structure, mapping the noise sequence and the initial weight guess to the a priori estimation errors and the final weight estimate, can be associated with such schemes. The feedback configuration is motivated via energy arguments and is shown to consist of two major blocks: a time-variant lossless (i.e., energy preserving) feedforward path and a time-variant feedback path.
Adaptive subspace algorithm for direction finding and tracking
Sylvie Marcos,
Messaoud Benidir
Show abstract
This paper presents an adaptive subspace-based method for the direction of arrival estimation and the tracking of multiple sources. This method relies on a linear operator, referred to as the Propagator, which only exploits the linear independency of the source steering vectors, and which allows the determination of the source and the noise subspaces without any eigendecomposition ofthe cross-spectral matrix of the received signals. Two gradient-based adaptive algorithms are here proposed for the estimation of the Propagator, and then of the source and the noise subspaces. A theoretical analysis of the behavior of these two algorithms in a nonstationary environment is given. Simulations exhibit the good performances of the proposed algorithms for tracking moving sources.
Parallel SVD updating using approximate rotations
Juergen Goetze,
Peter Rieder,
J. A. Nossek
Show abstract
In this paper a parallel implementation of the SVD-updating algorithm using approximate rotations is presented. In its original form the SVD-updating algorithm had numerical problems if no reorthogonalization steps were applied. Representing the orthogonalmatrix V (right singular vectors) using its parameterization in terms of the rotation angles of n(n - 1)/2 plane rotations these reorthogonalization steps can be avoided during the SVD-updating algorithm. This results in a SVD-updating algorithm where all computations (matrix vector multiplication, QRD-updating, Kogbetliantz's algorithm) are entirely based on the evaluation and application of orthogonal plane rotations. Therefore, in this form the SVD-updating algorithm is amenable to an implementation using CORDIC-based approximate rotations. Using CORDIC-based approximate rotations the n(n - 1)/2 rotations representing V (as well as all other rotations) are only computed to a certain approximation accuracy (in the basis arctan 2i). All necessary computations required during the SVD-updating algorithm (exclusively rotations) are executed with the same accuracy, i.e., only r << w (w: wordlength) elementary orthonormal (mu) rotations are used per plane rotation. Simulations show the efficiency of the implementation using CORDIC-based approximate rotations.
Efficient high-performance subspace-based tracking problems
Eric M. Dowling,
Ronald D. DeGroat,
Darel A. Linebarger
Show abstract
In this paper, we discuss some issues relevant to efficient, high performance subspace based tracking problems. Efficient subspace updating has been widely applied to target tracking problems. In this paper, we discuss a linear frequency modulated (FM) signal model for approximating slowly time varying narrowband signals that frequently arise in subspace based tracking problems. We also discuss the appropriateness of forward-backward (FB) averaging for increasing the efficiency of subspace updating. We then derive bias expressions for the peak locations of a discrete time Fourier transform spectrum of a linear FM signal. Finally, simulations confirm our bias expressions, and show that FB averaging can enhance the time varying frequency estimation performance of MUSIC over that of forward only averaging.
Algorithms for Structured Matrices
Error analysis of a fast partial-pivoting method for structured matrices
Douglas Robin Sweet,
Richard P. Brent
Show abstract
Many matrices that arise in the solution of signal processing have a special displacement structure. For example, adaptive filtering and direction-of-arrival estimation yield matrices of a Toeplitz type. A recent method of Gohberg, Kailath, and Olshevsky (GKO) allows fast Gaussian elimination with partial pivoting for such structured matrices. In this paper, a rounding error analysis is performed on the Cauchy and Toeplitz variants of the GKO method. It is shown the error growth depends on the growth in certain auxiliary vectors, the generators, which are computed by the GKO algorithms, It is also shown that in certain circumstances, the growth in the generators can be large, and so the error growth is much larger than would be encountered with normal Gaussian elimination with partial pivoting. A modification of the algorithm to perform a type of row-column pivoting is proposed which may circumvent this problem.
Cauchy matrices and iterative methods for Toeplitz matrices
Thomas K. Huckle
Show abstract
In recent papers, the connection between Toeplitz-like matrices, Vandermonde matrices, and Cauchy matrices is analyzed. Especially every Toeplitz matrix can be written as a Cauchy matrix by means of the Fourier or Sine transform. This gives rise to the formulation of new stable direct solvers for linear Toeplitz systems. Also for iterative methods the transformation of a Toeplitz matrix into a Cauchy matrix allows a new view on fast transform based preconditioning for Toeplitz-like matrices. In this paper we will display some theoretical and practical applications of this new development.
Rank-revealing decomposition of symmetric Toeplitz matrices
Show abstract
In signal and image processing, regularization often requires a rank-revealing decomposition of a symmetric Toeplitz matrix with a small rank deficiency. In this paper, we present an efficient factorization method that exploits symmetry as well as the rank and Toeplitz properties of the given matrix.
Iterative solution of Toeplitz systems by preconditioning with the discrete sine transform
Fabio Di Benedetto
Show abstract
Solving linear systems or least-squares related to Toeplitz matrices is often required in the context of signal and image processing; conjugate-gradient-like methods are well-suited for solving such problems. The recent preconditioning technique involving the discrete sine transform is presented: convergence properties are reported and suitable generalizations to block matrices, nonsymmetric systems, and least-squares problems are discussed. Finally, these techniques are applied to regularized inverse problems arising in image restoration.
Algorithms for Signal and Image Processing
Continuation method for total variation denoising problems
Tony F. Chan,
H. M. Zhou,
Raymond Hon-fu Chan
Show abstract
The denoising problem can be solved by posing it as a constrained minimization problem. The objective function is the TV norm of the denoised image whereas the constraint is the requirement that the denoised image does not deviate too much from the observed image. The Euler-Lagrangian equation corresponding to the minimization problem is a nonlinear equation. The Newton method for such equation is known to have a very small domain of convergence. In this paper, we propose to couple the Newton method with the continuation method. Using the Newton-Kantorovich theorem, we give a bound on the domain of convergence. Numerical results are given to illustrate the convergence.
Conditioning and solution of Hermitian (block) Toeplitz systems by means of preconditioned conjugate gradient methods
Show abstract
Let {An(f)} be a sequence of nested n X n Toeplitz matrices generated by a Lebesgue integrable real-function f defined on (-(pi) , (pi) ). In this paper, we first present some results about the spectral properties of An(f) (density, range, behavior of the extreme eigenvalues etc.), then we apply these results to the preconditioning problem. We analyze in detail the preconditioned conjugate gradient method, where the proposed poreconditioners An1(g)An(f): we obtain new results about the range, the density and the extremal properties of their spectra. In particular we deal with the critical case where the matrices An(f) are asymptotically ill-conditioned, i.e., zero belongs to the convex hull of the essential range of f. We consider positive definite Toeplitz linear systems (f >= 0), nondefinite Toeplitz linear systems (f with nondefinite sign), with zeros of generic orders. Moreover, these analyses and techniques are partially extended to the block case, too.
Iterative solution methods for ill-posed problems
Show abstract
We describe new iterative methods for the solution of large ill-conditioned that arise from the discretization of ill-posed problems. In these methods a filter function, which determines the regularization of the problem, is chosen and expanded in terms of orthogonal polynomials. Each iteration yields one new term in this expansion. A variety of iterative methods, which differ in the choice of filter function and orthogonal polynomials, can be derived in this manner.
Blur detection using a neural network
Chong Sze Tong
Show abstract
Image restoration is an ill-posed inversion problem wherein an estimate of the ideal original image is to be extracted from a noisy and blurred observation. The ability to restore such a degraded digital image usually requires accurate knowledge of the blur function as well as additional information on the original image. Unfortunately, such a priori knowledge is not always accessible. This paper describes an iterative scheme for the identification of the blurring by making use of the neural network paradigm and the assumption of physical constraints on the blurring process.
Fast numerical methods for total variation minimization in image reconstruction
Show abstract
We apply a total variation minimization technique for the deblurring of 2D images. This yields an integro-differential equation with a nonlinear elliptic partial differential operator. In this paper we discuss a numerical scheme for the efficient solution of this integro-differential equation. Results are presented for a doconvolusion problem arising in ground-based astronomical imaging.
Preconditioned Methods
Preconditioned projection methods for recursive least-squares computations
Michael Kwok-po Ng
Show abstract
Recursive least square (RLS) estimations are used extensively in many signal processing and control applications. The least squares estimator w(t) can be found by solving a linear matrix system A(t)w(t) equals d(t) at each adaptive time step t. In this paper, we consider block RLS computations. Our approach is to employ Galerkin projection methods to solve the linear systems. The method generates a Krylov subspace from a set of direction vectors obtained by solving one of the systems and then projects the residuals of other systems orthogonally onto the generated Krylov subspace to get the approximate solutions. The whole process is repeated until all the systems are solved. Both the exponential data weighting infinite memory method and finite memory sliding data window method are used to formulate the equations. In order to speed up the convergence rate of the method, FFT-based preconditioners are also employed. Numerical results are reported to illustrate the effectiveness of the Galerkin projection method for RLS computations.
Modulation recognition via sequential probability ratio test
Show abstract
We examine the design of the modulation classifiers, which identify the modulation type of received noisy signals in this research. The family of modulation schemes of our concern is the quadrature amplitude modulation, which has been widely used in modern digital communication. Modulation recognition has been traditionally viewed as a hypothesis test problem with a fixed sample size. Because the amount of received data increases with time, we formulate the problem as a variable sample size test, and propose an iterative recognition procedure. The new approach called the sequential probability ratio test has important advantages, including low error rate, low computational complexity and flexible tradeoff between performance and speed.
Implementations I
Symbolic computation in system simulation and design
Show abstract
This paper examines some of the roles that symbolic computation plays in assisting system- level simulation and design. By symbolic computation, we mean programs like Mathematica that perform symbolic algebra and apply transformation rules based on algebraic identities. At a behavioral level, symbolic computation can compute parameters, generate new models, and optimize parameter settings. At the synthesis level, symbolic computation can work in tandem with synthesis tools to rewrite cascade and parallel combinations on components in sub- systems to meet design constraints. Symbolic computation represents one type of tool that may be invoked in the complex flow of the system design process. The paper discusses the qualities that a formal infrastructure for managing system design should have. The paper also describes an implementation of this infrastructure called DesignMaker, implemented in the Ptolemy environment, which manages the flow of tool invocations in an efficient manner using a graphical file dependency mechanism.
Software system for parsing signal processing tasks over multiple heterogeneous processors
Erwin H. Warshawsky
Show abstract
A design automation toolset of great applicability to the signal processing system design community is described herein, the JRS NetSyn product. NetSyn provides facilities for building and maintaining libraries of reusable hardware and software parts. The NetSyn methodology supports hardware/software codesign and tradeoffs and the distribution of software functions to processing elements in accordance with selected optimization objectives. NetSyn utilizes VHDL, Ada, and ANSI C standard languages and related tools. It facilities software reuse by porting application systems to alternative architectures. The paper presents some of the underlying concepts of NetSyn and then describes the functionality of the toolset in some detail.
Mixed-radix approach to incremental DFT refinement
Joseph M. Winograd,
S. Hamid Nawab
Show abstract
Incremental refinement algorithms can quickly produce approximate results and may then improve the quality of those results in subsequent stages of computation. They offer promise for the development of real-time systems whose performance degrades gracefully under diminishing hard deadlines. We present a new class of incremental refinement algorithms which employ mixed-radix signal representations for the calculation of successive approximations to the DFT. This class includes algorithms with a wide range of cost/quality tradeoff characteristics. This work generalized a previously reported class of algorithms which employ binary signal representations only. The mixed-radix formulation allows solutions of a given level of quality to be achieved using significantly fewer arithmetic operations in many instances. Under certain restrictions, these algorithms can also be implemented with no computational overhead using fixed-point binary hardware.
RASSP signal processing architectures
Fred Shirley,
Bob Bassett,
J. P. Letellier
Show abstract
The rapid prototyping of application specific signal processors (RASSP) program is an ARPA/tri-service effort to dramatically improve the process by which complex digital systems, particularly embedded signal processors, are specified, designed, documented, manufactured, and supported. The domain of embedded signal processing was chosen because it is important to a variety of military and commercial applications as well as for the challenge it presents in terms of complexity and performance demands. The principal effort is being performed by two major contractors, Lockheed Sanders (Nashua, NH) and Martin Marietta (Camden, NJ). For both, improvements in methodology are to be exercised and refined through the performance of individual 'Demonstration' efforts. The Lockheed Sanders' Demonstration effort is to develop an infrared search and track (IRST) processor. In addition, both contractors' results are being measured by a series of externally administered (by Lincoln Labs) six-month Benchmark programs that measure process improvement as a function of time. The first two Benchmark programs are designing and implementing a synthetic aperture radar (SAR) processor. Our demonstration team is using commercially available VME modules from Mercury Computer to assemble a multiprocessor system scalable from one to hundreds of Intel i860 microprocessors. Custom modules for the sensor interface and display driver are also being developed. This system implements either proprietary or Navy owned algorithms to perform the compute-intensive IRST function in real time in an avionics environment. Our Benchmark team is designing custom modules using commercially available processor ship sets, communication submodules, and reconfigurable logic devices. One of the modules contains multiple vector processors optimized for fast Fourier transform processing. Another module is a fiberoptic interface that accepts high-rate input data from the sensors and provides video-rate output data to a display. This paper discusses the impact of simulation on choosing signal processing algorithms and architectures, drawing from the experiences of the Demonstration and Benchmark inter-company teams at Lockhhed Sanders, Motorola, Hughes, and ISX.
Parallel filter structures for RLS-type blind equalization algorithms
Marc Moonen,
Ed F. A. Deprettere
Show abstract
It is shown that several RLS-type blind equalization algorithms, e.g., decision-directed schemes as well as 'orthogonalized' constant modulus algorithms, possess a common algorithmic structure and are therefore straightforwardly implemented on an earlier developed triangular array (filter structure) for recursive least squares estimation with inverse updating. While the computational complexity for such algorithms is O(N2), where N is the problem size, the throughput rate for the array implementation is O(1), i.e., independent of the problem size. Such a throughput rate cannot be achieved with standard (Gentleman-Kung- type) RLS/QR-updating arrays because of feedback loops in the computational schemes.
Implementations II
Application of frequency-domain polyphase filtering to quadrature sampling
Andrew Halberstadt
Show abstract
A new method for developing in-phase and quandrature samples of a band limited real signal is presented and compared with other methods. The proposed method improves the computational efficiency of a frequency-domain implementation of the required filtering by taking advantage of mirror-image symmetry between the filters on the in-phase and quandrature channels. This technique makes it possible to filteer both the in-phase and quadrature channels at once using one standard FFT for complex-valued input and one standard IFFT for complex-valued output without adding computational overhead. The proposed method is more computationally efficient than techniques using commonly available FFT routines for real-valued input. Specialized FFT routines derived specifically for real- valued input can achieve greater computational efficiency than the proposed method, but these routines are not as commonly available as the standard FFT routines used in the proposed method. For systems where the effective channel filter is short in length or has special structure, there are other implementations of the channel filters which are more efficient than the proposed method.
Time-domain feedback analysis of adaptive gradient algorithms via the small gain theorem
Ali H. Sayed,
Markus Rupp
Show abstract
This paper provides a time-domain feedback analysis of gradient-based adaptive schemes with emphasis on stability and robustness issues. It is shown that an intrinsic feedback structure, mapping the noise sequence and the initial weight guess to the a priori estimation errors and the final weight estimate, can be associated with such schemes. The feedback configuration is motivated via energy arguments and is shown to consist of two major blocks: a time-variant lossless (i.e., energy preserving) feedforward path and a time-variant feedback path. The configuration is further shown to lend itself rather immediately to analysis via a so-called small gain theorem; thus leading to stability conditions that require the contractivity of certain operators.
Multiscale system identification and estimation
Dzu K. Le
Show abstract
A formula for 'multiscale' representation of linear systems and stochastic processes is derived. The formula facilitates the synthesis of multiresolution analysis with linear systems theories. For example, it simplifies the use of scale-selective error metrics for system identification. This multiscale system identification framework yields closed form optimal solutions for non- parametric problems. Its 'wavelet-z-transform' version is a fast algorithm for the parametric case. Application of this method to nonlinear systems is also possible. In general, multiscale system identification is more effective for transient dynamics than classical time domain methods. Illustrations of this multiscale system identification method and comparison against time-domain approaches are presented.