In this review paper we discuss selected issues associated with the implementation of arithmetic for VLSI Digital Signal Processors. We start with a Silicon Technology Roadmap view of the next decade, in order to grasp some of the issues facing the next generation of VLSI designers, particularly associated with high performance DSP systems. We use this roadmap to open the discussion on the role basic arithmetic operations play in the construction of DSP systems; in particular we look at the interplay between algorithms, architecture, arithmetic representation and circuit implementation. Many of the illustrative examples are taken from work conducted in the VLSI Research Group, University of Windsor over the past few years, including on- going work.

In this paper we explore a new number system which uses a double base. The representation of the numbers has a very simple geometric interpretation, allowing potentially fast implementation of the basic arithmetic operations. The transformation of the integers into minimal form, however, leads to some problems associated with transcendental number theory, and we identify and open the discussion on these problems. An intriguing implementation vehicle, which has some of the properties associated with symbolic substitution in optical computing, is the use of Cellular Neural Network (CNNs) to perform digital reduction. Brief details are presented on CNN implementation, and a system-level example is shown in order to justify the applicability of the proposed theory in digital signal processing.

This paper presents an architecture for high-speed bit- parallel multiply-accumulate arithmetic operation. This architecture employs the modified-Booth recoding algorithm for multiplication, and a kernel using mixed (sign, value)- encoded signed-binary (SB) and two's complement (TC) computation for carry-free generation of the SB partial product sums. The final SB partial product sum undergoes full-precision accumulation, rounding, and overflow correction concurrently, to facilitate a high-speed overall operation. A high-performance architecture is proposed for IEEE Standard 754 default rounding of the SB result. This architecture exploits the carry-free property of redundant number addition to perform the rounding operation, again concurrently with the multiplication and accumulation operations. The conversion of the final rounded SB number into its corresponding TC format is achieved by using a fast pipelined lookahead converter. The resulting multiply- accumulate arithmetic architecture is subsequently parameterized for ASIC implementations using the Actel 1.2 (mu) FPGA technology parameters. It is demonstrated that the use of (sign, value)-encoding leads to combined area and time efficient implementations.

Reducing power consumption has become an important issue in many design problems. However, in some cases this should be done without affecting the speed of operation. In this paper we present a division algorithm which minimizes the number of add/sub operations. By splitting a single iteration of the algorithm into two steps we are able to reduce the clock period and make the execution time independent of quotient digits. The redundancy of the signed-digit quotient representation is exploited to reduce the comparison precision and use a CSA. This reduces the hardware complexity (hence lower power consumption) and reduces the propagation delay (hence faster operation). Finally, a comparison is given between the proposed and existing algorithms. The proposed algorithm reduces the power consumption by 15% over radix 4 division algorithm and by 45% over the radix 2 division algorithm.

In this paper, we introduce modifications on the classic CORDIC algorithm to reduce the number of iterations, and hence the rounding noise. The modified algorithm needs, at most, half the number of iterations to achieve the same accuracy as the classical one. The modifications are applicable to linear, circular and hyperbolic CORDIC in both vectoring and rotation modes. Simulations illustrate the effect of the new modifications.

This paper describes a circuit implementing 12 fully independent biquad digital filters operating on (Delta) - (Sigma) modulated signals with 28 b resolution. A carry-save adder with partial carry propagation (Delta) -(Sigma) modulator is used together with a pipelined architecture that interleaves all of the filters on a single datapath. Implemented in TSPC logic, the circuit comprises 95 K transistors, including a variable frequency on-chip clock generator.

An architecture which efficiently implements a fixed coefficient FIR filter using pipelined bit-serial arithmetic is described. A specialized multiplier decomposition exploiting multiplier coefficient similarities is used to obtain a reduced hardware area implementation. A design methodology which supports the conversion of a frequency response specification into a gate level implementation of the filter is presented. An 89 tap FIR filter meeting a multi-band frequency response specification, with 16 bit internal data precision and a sample rate of 1.6 GHz for parallel input and output data is implemented on a single XILINX 4005PG156 FPGA device.

A methodology for constructing parallel embedded DSP systems is described. The method uses a software and embedded processor abstraction to help raise the level of problem analysis above the raw state machine concept. Custom architectures are constructed by using multiple copies of a core embedded processor linked together with FIFO memories or other communication structures, and augmented with appropriate high speed data manipulation IO devices. Some field programmability and customization is possible through the use of SRAM program memories.

The design, implementation, and performance of a low-cost, real-time DSP system for source location is discussed. The system consists of an 8-element electret microphone array connected to a Signalogic DSP daughterboard hosted by a PC. The system determines the location of a speaker in the audience in an irregularly shaped auditorium. The auditorium presents a non-ideal acoustical environment; some of the walls are acoustically treated, but there still exists significant reverberation and a large amount of low frequency noise from fans in the ceiling. The source location algorithm is implemented in a two step process. The first step determines time delay of arrival (TDOA) for select microphone pairs. A modified version of the Cross- Power Spectrum Phase Method is used to compute TDOAs and is implemented on the DSP daughterboard. The second step uses the computed TDOAs in a least mean squares gradient descent search algorithm implemented on the PC to compute a location estimate.

Conventional least squares minimization beamforming algorithms suffer from `weight jitter' when small data sequences are used. One method for overcoming this problem requires that the SVD of the data matrix is calculated and the `signal' and `noise' subspaces identified. A more stable beampattern can then be formed by projecting the least squares weight vector onto the appropriate subspace. The SVD is computationally expensive to perform and difficult to implement in a parallel architecture. Several approximate `rank revealing' algorithms have been presented of late (e.g. URV, RRQR) which have a much reduced computational load. However, being `two-sided' decompositions, they all suffer from implementation difficulties. In this paper we present an algorithm, based on QR decomposition, that can approximately reveal the rank and signal subspace of a matrix and simultaneously perform a subspace projection. The algorithm has the potential for very simple parallel implementation.

For various audio, teleconference, hearing aid, and voice recognition applications, a microphone array is known to be an effective method to enhance the SNR in noisy environments resulting in significant improvement of speech intelligibility or recognition. We propose an novel electronically steerable microphone array based on the Maximum Energy concentration criterion to form a focused beam toward the desired speech source, attenuating background noises and rejecting discrete spatial interferers. The design and implementation of a prototype DSP-based microphone array system are described. Some details on microphone measurement, calibration, and optimization needed to achieve a high performance microphone array are discussed. Computer simulated and measured array performances are presented to show the effectiveness of the array system.

This paper considers a class of blind beamforming problems in which the amount of prior information is very limited. The array sensors are placed in unknown locations within a geographical region, and have unknown frequency/spatial response. The sensors communicate synchronously with a main processor unit. The array is illuminated by a source, which may be narrow- or broadband, in near or far field. Additional disturbances may be present, in the form of interferers, possibly correlated or coherent with the main signal, and additive noise. The goal is required to steer beam toward the desired signal. Four schemes are presented, each based on the type of prior available information.

A hypothesis H is parametric if every distribution from the process defined by H belongs to a family of distributions characterized by a finite number of parameters; on the other hand, if the distribution can not be defined by a finite number of parameters, the hypothesis is nonparametric. In this paper, we analyze a detector based on the optimum permutation test, applied to nonparametric radar detection which provide good performances without a large computational work, and we compare it with the parametric test and rank test in the Neyman-Pearson sense. The computational complexity of the detector is high and its implementation in real time is difficult, due to the number of operations increase with the factorial of the number of samples. Also, we present an algorithm that reduces the computational work required. We also present the detectability characteristic of the optimum permutation test against rank test and parametric test under Gaussian noise environments and different types of target models (nonfluctuating, Swerling I and Swerling II). The detection probability versus signal-to-noise ratio is estimated by Monte-Carlo simulations for different parameter values (N pulse, M reference samples and false alarm probability P_fa).

An adaptive algorithm and two stage filter structure were developed for adaptive filtering of certain classes of signals that exhibit cyclostationary characteristics. The new modified P-vector algorithm (mPa) eliminates the need for a separate desired signal which is typically required by conventional adaptive algorithms. It is then implemented in a time-sequenced manner to counteract the nonstationary characteristics typically found in certain radar and bioelectromagnetic signals. Initial algorithm testing is performed on evoked responses generated by the visual cortex of the human brain with the objective, ultimately, to transition the results to radar signals. Each sample of the evoked response is modeled as the sum of three uncorrelated signal components, a time-varying mean (M), a noise component (N), and a random jitter component (Q). A two stage single channel time-sequenced adaptive filter structure was developed which improves convergence characteristics by de coupling the time-varying mean component from the `Q' and noise components in the first stage. The EEG statistics must be known a priori and are adaptively estimated from the pre stimulus data. The performance of the two stage mPa time-sequenced adaptive filter approaches the performance for the ideal case of an adaptive filter having a noiseless desired response.

In array processing, one technique for cancelling interference in the presence of colored noise is the ULLV decomposition of a pair of matrices. The factorization is stable and accurate, and is easy to update when a row is added to either one of the two matrices. In earlier work, we made the assumptions that both matrices must have at least as many rows as columns and that the matrix representing interference must have full column rank. In this paper, we relax the latter restriction and allow the interference matrix to be rank deficient. We present an algorithm for computing the decomposition and two techniques for updating it. The details on updating are quite different from those in the full rank case.

A new method to estimate the energy distribution over the time-frequency plane of time-varying stochastic signals is presented. A state space modeling approach is used to represent the signal. A Kalman-smoothing algorithm is used to estimate the states from which the so-called `Kalman- smoothed time frequency distribution (KS-TFD)' is obtained. The KS-TFD estimate is positive, has good cross-term properties and high temporal resolution. The Kalman smoother-based estimates are optimal in the mean square sense and therefore the KS-TFD estimate has excellent noise performance. We demonstrate the `localizing' property of KS- TFD using deterministic signals such as impulses and Gabor logons. Minimum interference is seen with multi component signals. For Gabor logons buried in white noise at various signal-to-noise ratios, we show the excellent performance of the KS-TFD estimate in comparison to the non-causal spectrogram using quantitative performance indices.

We propose an extension of Thomson's multiple window spectrum estimation for stationary random processes to the time-varying spectrum estimation of non-stationary random processes. Unlike previous extensions of Thomson's method, in this paper we identify and utilize optimally concentrated window and wavelet functions for the time-frequency and time-scale planes respectively. Moreover, we develop a statistical test for detecting and extracting chirping line components.

We propose a time-frequency based pattern classification method which utilizes the joint moments of time-frequency distributions (TFDs) for features. The method is applied to a biomedical data set, and compared to a template matching scheme and to methods utilizing only temporal moments or spectral moments. Our results show that a classification algorithm which utilizes joint time-frequency information, as quantified by the joint moments of the TFD, can potentially improve performance over time or frequency-based methods alone, for classification of nonstationary time series.

This paper deals with the problem of blind source separation which consists of recovering a set of signals from instantaneous linear mixture of them. So far, this problem has been solved using statistical information available on the source signals. Here, we propose an approach for blind source separation based on time-frequency (t-f) signal representations. This approach is based on a `joint diagonalization' of a combined set of time frequency distribution matrices which correspond to different t-f points. It relies on the difference in the t-f signatures of the sources to be separated. In contrast to existing techniques, the proposed approach allows the separation of Gaussian sources with identical spectra shape. Because of changes incurred in the t-f signal structures due to time- delay, the new approach can be employed to separate multipath signals received by multi-sensor array. Moreover, the effects of spreading the noise power while localizing the source energy in the time frequency domain amounts to increasing the signal to noise ratio and hence improved performance. Numerical examples are provided to illustrate the effectiveness of our method.

Displacement events of nearest neighbor spring coupled mass points, embedded in a semi-infinite, periodic 1D lattice, which is driven at constant velocity at one end, are studied. The displacements of the mass points are due to small amplitude, linear oscillations, and large amplitude, low frequency translations due to nonlinear waves, or solitons, propagating on the lattice. The translational symmetry of the underlying rigid periodic lattice is broken by defect sites whose positions and amplitudes are random. Because of intermittent reflections and transmissions of the solitons at the impurity defect sites, there results stick- slip motions of the mass points of varying magnitudes and durations. The joint distribution for these events, of magnitude (delta) x and duration (delta) t, is approximated by way of the zero crossings of the wavelet transform of the displacement time series of a tracer atom in the complex flow. There follows estimates of the scaling laws of statistical quantities characterizing the motion.

We discuss some issues relevant to time-frequency analysis. Among them are, time-frequency spatial/spatial-frequency representations, generalized marginals and generalized characteristic functions. We derive representations that jointly involve the four variables, time, frequency, space, and spatial frequency. We apply these representations to wave packet motion. For the study on generalized marginals we show that there is an inherent difference between the standard methods of transforming variables and in time- frequency analysis. We use the method of generalized characteristic function operator method to generalize Taylor's theorem.

Time-frequency methods are applied for bearing analysis of a motor-generator. We show that these methods reveal features that are not seen by traditional methods, such as the power spectrum. These features may be used for detection of specific faults and as supplemental information to assess the condition of the machine.

The scale transform has been recently proposed and applied to 1D signals in applications such as speech processing, biological signals and machine vibration analysis. The purpose of this paper is to investigate how the concept of scale can be extended for multidimensional signals, and in particular in the case of images. A first example of denoising in the scale domain in comparison with Fourier filtering is presented. The importance of magnitude and phase of the scale transform is also discussed in the context of the Fourier transform. It is shown that scaling operators permit the analysis of the local frequency contents of an image at different resolutions.

Images and signals can be characterized by representations invariant to time shifts, spatial shifts, frequency shifts, and scale changes as the situation dictates. Advances in time-frequency analysis and scale transform techniques have made this possible. The next step is to distinguish between invariant forms representing different classes of image or signal. Unfortunately, additional factors such as noise contamination and `style' differences complicate this. A ready example is found in text, where letters and words may vary in size and position within the image segment being examined. Examples of complicating variations include font used, corruption during fax transmission, and printer characteristics. The solution advanced in this paper is to cast the desired invariants into separate subspaces for each extraneous factor or group of factors. The first goal is to have minimal overlap between these subspaces and the second goal is to be able to identify each subspace accurately. Concepts borrowed from high-resolution spectral analysis, but adapted uniquely to this problem have been found to be useful in this context. Once the pertinent subspace is identified, the recognition of a particular invariant form within this subspace is relatively simple using well-known singular value decomposition techniques.

The time-frequency analysis techniques developed for 1D time series are extended to determine the spatial frequencies at a specific point on a 2D surface or image. The 2D surface/image is sampled along a number of evenly angularly- spaced axes passing through the point of interest. The time- frequency analysis techniques are then applied to each of the 1D data sets. When taken together, the results from the Directional Spatial Frequency Distribution (DSFD), a 2D plot of spectral energy as a function of spatial frequency and the direction. When the 2D data consists of planar waves, a spatial correlation masking process can be used on the DSFD to produce a localized estimate of spatial frequency and direction of measurement called the Equivalent Planar Wave Sinusoidal Decomposition (EPWSD). The DSFD and EPWSD are calculated for simulated 2D data consisting of sinusoids and chirp signals from single and multiple directions as well as ocean wave measurements made by an airborne scanning radar altimeter and compared to a standard 2D Fourier transform. It is shown that the EPWSD technique provides a very localized estimate of frequency and direction of arrival even if the frequency is changing rapidly with position.

Processing a noise signal using Cohen's class of transformation gives a time-frequency distribution with distinct characteristics. Understanding the effects of noise is essential for using such distributions for signal analysis. The variance of a generalized discrete time- frequency distribution is developed analytically and confirmed numerically by simulation for several different time-frequency kernels.

Time-frequency distributions (TFDs) have proven useful in a wide variety of nonstationary signal processing applications. While sophisticated optimal bilinear TFDs have been developed to extract the maximum possible time- frequency information from signals, certain applications dictate simpler linear, running-FFT processing techniques. In this paper, we propose a signal-dependent short-time Fourier transform/spectrogram that enjoys many of the advantages of optimal bilinear TFDs yet retains the simplicity and efficiency of running-FFT processing. In addition, we extend the optimal kernel design problem to linear spaces of signals.

We all want the same kinds of things from our personal communication appliances. We want them to be 100% reliable, convenient, simple to use, cheap to buy and cheap to operate. In the last few years the list has been expanded to include the desires to be totally tetherless and totally mobile. Figure 1 illustrates this wireless dream, wherein one device maps to one person and to one address in the public network. How close are we coming to these objectives? What are the current trends in technology, business, and regulatory affairs that underlie attainment of the model? What are the technical challenges in device development that must be overcome? Successful implementations and large-scale rollouts of cellular (high-tier, fullymobile) and cordless (low-tier, limited-mobility) systems have been achieved in several markets and with a handful of different communication system approaches. We will examine one or two examples of design practices at the systems and circuit level to appreciate the current state of the art now in high-volume deployment. Strong moves to deregulate communication services and willingness to open large segments of the RF spectrum for novel new uses mark the trends in both the US domestic and many international administrations. These events are guaranteed to cause rapid acceleration of the acceptance of wireless services by the general public while also moving the choice of RF carrier frequencies upward. To fundamentally improve on appliance cost and performance (see Figure 2 for block diagram of wireless handset), a number of semiconductor and circuit-level breakthroughs will be required. For example, theorists are finding new and better ways to compress information sources and encode, modulate, and interleave the resulting information stream. Much has also been contributed on the increasingly complex techniques for selectively accessing the physical medium of the channel. Some of these techniques put special stress on RF componentry, some on the digital processors, memories, and/or fixed-logic functions that must deliver more performance at lower cost and lower power. Figure 3 shows the march of progress in one area, voice compression, and the resultant increase in digital signal processing required RF components (microwave monolithic ICs), on the other hand, must have high dynamic range, excellent linearity, low noise, low bias current, high isolation, and high passive component accuracy. We find that price/performance progress in RF componentry does not usually obey any trend close to "Moore's Law. " In addition, few fabs in the world have tackled the problems of understanding and controlling the parameters necessary to produce these high-performance RF devices. Now that the mass markets are developing, more companies are finding it worthwhile to examine which technologies have the best price/performance balance to solve the overall wireless engineering problems. For system designers there is a constant struggle to move the digital/analog boundary higher in the frequency domain, or alternatively to reduce the RF side of the problem to simpler architectures. This has the benefit of increasing the fraction of the wireless appliances' device production relegated to digital component fabrication. In this talk we will review and summarize some of the key challenges that system designers face as they sort through the myriad of tradeoffs and applications. Keywords: radio, telecommunications, wireless, digital, DSP, MMIC, PCS, cellular, cordless, pagin

Interactive communication concerns the number of bits that a person must transmit to convey information to another, and how this number of bits can be reduced if the two communicators are allowed to interact.

Emerging technology finally permits wireless communication systems to carry video information efficiently. System challenges include low-noise preprocessing to maximize compressibility, efficient compression, decompression, and error-correction of the compressed signal, and clean reconstruction of the video waveform. This paper discusses algorithms and hardware for clean, efficient conversion of signals between universal analog television formats and compression-ready or decompressed digital video component formats. Problems of gunlock jitter, video decoding, cross- luminance, and video filtering are considered.

Since a nonminimum-phase system can be divided into a minimum-phase system and into an allpass system, the parameters of the minimum-phase part can be estimated with well known algorithms based on second-order statistics, while for the allpass part higher-order statistics are useful. In this article we present a new algorithm for allpass identification, which processes the third-order cumulant (moment) sequence in contrast to known methods in a linear manner. Thus the inherent problems of nonlinear methods--the not-guaranteed global convergence and the high computational costs--can be avoided. The proposed method reduces the allpass parameter estimation problem to the estimation of MA (Moving Average)-parameters by use of the modulated third-order moment sequence. Some simulation results are provided to show that the algorithm works well. In addition we will compare this algorithm to the well known extended Yule-Walker equations based on third-order cumulant (moment) sequences.

One can find ample examples in the literature of implementations of image transforms such as the discrete cosine transform and the lapped orthogonal transform. The objective is invariantly the minimization of the number of multiplies and adds. Of course, a reduction of operations from O(N²) to O(NlogN) is a great achievement, yet the cost resulting from non-local communication and operation accuracy is seldom taken into account. Especially accuracy needed to preserve the dominant property of the transforms may turn out to be expensive. These properties are that the transforms are a collection of highly structured orthonormal basis functions and the first concern should be to preserve these properties by enforcing them through a decomposition of the transforms in terms of inexpensive elementary operations which can be inaccurate without violating the global properties. This paper presents a decomposition of image transforms into a network 2 X 2 so-called fast rotations which are inexpensive and orthonormal within the accuracy required by the application. The network results from a recursive decomposition which turns out to be applicable for most of the popular transforms. But even transforms that do not allow such a decomposition can be efficiently implemented as illustrated in this paper. Compression of X-ray image series with the transforms implemented as proposed in this paper has shown that high accuracy of low bit rates can be achieved at a small implementation cost. Real time compression and coding of image sequence giving rise to Gbit/sec datarates is achievable using a single chip and transforms of any size between 8 X 8 and 32 X 64.

This paper describes a convergent algorithms that is able to construct a multi-scale fuzzy-wavelet system for efficient image recovery and compression. Given only part of the original image and a prescribed compression error bound, a fuzzy system is firstly constructed at the coarsest scale. The fuzzy rules and corresponding membership functions can be stably extracted, and linguistic knowledge can also be combined with numerical one to make the scheme more flexible. Residual based wavelet system is then built to refine the performance by reaching certain fine scales. To increase the compression ratio, a reduction technique is developed to delete redundant fuzzy rules and wavelet nodes to make the whole fuzz-wavelet system as small as possible. The resulting image representation of the given image from coarse to fine scale is suitable for progressive transmission and video indexing purposes. An illustrative example is used to demonstrate the effectiveness of the scheme.

We present an IIR filtering technique based upon a recently proposed approach for reducing power consumption in implementation of frequency-selective filters. The basic idea in such techniques is to utilize the most recent input and output signal samples to estimate the current SNR (defined as the ratio of the in-band signal power to the out-of-band signal power) at the filter's input. This estimated input SNR is then used to update the filter order to the minimum value which would guarantee a minimum tolerable SNR at the filter's output. A key issue addressed in this paper is how well the estimated filter order converges to the theoretical minimum for situations satisfying the assumptions behind the derivation of the technique. Experimental results are used to verify that convergence to the correct filter order depends (1) upon the number of input and output samples used for estimating the input SNR, (2) upon the filter order applied in generating the output samples that are used in estimating the input SNR and (3) upon the proximity of the actual input SNR to boundaries in the input-SNR space corresponding to changes in the optimal choice for filter order.

The author's formulation of spatial filter design involves the optimization of the filter's signal-to-clutter ratio, a very nonlinear, nondifferentiable function with tens of thousands of free parameters. Statements have appeared in what purport to be refereed papers which claim that only random search methods can be used to solve the required optimization. These statements are false. This paper gives an outline of an iterative technique and algorithm, supported by reasoning of a very general though embarrassingly elementary character, by which the optimization can be efficiently carried out. This iterative technique essentially involves the solution of a specialized quadratic programming problem at each iterative step.

Index Mapping is a novel approach to mapping a class of algorithms onto linear permutation networks such as the shuffle graph. This class includes the Viterbi Algorithm, the Fast Fourier Transform, and the Bitonic Sort, among others. With this technique, it is possible to analyze a large number of possible partitioning and scheduling schemes and choose for a given technology the optimum implementation. This technique will be demonstrated by two mappings of a variable and large constraint length Viterbi decoder onto a smaller fixed interconnection processing network with minimum hardware resources. The hardware built for this mapping can calculate the Viterbi algorithm for any constraint length from 3 to 15 with programmable code polynomials and code rates from 1/2 to 1/6.

Recently, cepstral analysis based on second order statistics and homomorphic filtering techniques have been used in the adaptive decomposition of overlapping, or otherwise, and noise contaminated ECG complexes of mothers and fetals obtained by a transabdominal surface electrodes connected to a monitoring instrument, an interface card, and a PC. Differential time delays of fetal heart beats measured from a reference point located on the mother complex after transformation to cepstra domains are first obtained and this is followed by fetal heart rate variability computations. Homomorphic filtering in the complex cepstral domain and the subuent transformation to the time domain results in fetal complex recovery. However, three problems have been identified with second-order based cepstral techniques that needed rectification in this paper. These are (1) errors resulting from the phase unwrapping algorithms and leading to fetal complex perturbation, (2) the unavoidable conversion of noise statistics from Gaussianess to non-Gaussianess due to the highly non-linear nature of homomorphic transform does warrant stringent noise cancellation routines, (3) due to the aforementioned problems in (1) and (2), it is difficult to adaptively optimize windows to include all individual fetal complexes in the time domain based on amplitude thresholding routines in the complex cepstral domain (i.e. the task of `zooming' in on weak fetal complexes requires more processing time). The use of third-order based high resolution differential cepstrum technique results in recovery of the delay of the order of 120 milliseconds.

This paper presents an overview and results from an ongoing research project to study parallel algorithms for the acquisition of Code Division Multiple Access communication signals. The goal of this research is to evaluate a class of related algorithms and architectures for the acquisition problem and map them onto parallel architectures containing DSPs. The algorithms used are generally termed subspace- based algorithms, since they involve computation of subspaces of the vector space spanned by certain observation vectors. This paper presents results from some preliminary implementations of such a subspace-based algorithm on the Texas Instruments TMS320C40 Parallel Processing Development System.

In applications requiring soft decision metrics, e.g., systems with interleaved coded modulation, symbol-by-symbol detection is preferred to sequence detection. This paper develops some soft-output detectors called the Bayesian conditional decision feedback estimators (BCDFE), for the demodulation continuous phase modulated signals and the simultaneous estimation of possibly time varying, phase and frequency offsets. By varying certain parameters, the BCDFEs offer an effective trade-off between performance and complexity, as measured by arithmetic operation count and the number of integrators required. Additionally, some simple complexity reduction schemes can be used in conjunction with the BCDFEs. The phase and frequency offsets are estimated using an extended Kalman filter type of approximation. The properties of the phase and frequency offset estimator are explored by means of simulations.

Most of the signal processing application programs involve computationally intensive iterative steps. In such programs, various failures in the underlying hardware manifest as control-flow errors that affect the reliability of the computed results. Various techniques have been proposed in the past to detect and recover from such control-flow errors. Unfortunately, all these techniques need either additional hardware or modification of the hardware and are not portable across various platforms. To circumvent these limitations, recently we have developed a high-level control-flow checking approach using assertions (CCA). In CCA, branch-free intervals in a given high-level language program are identified and the entry and exit points of the intervals are fortified through pre-inserted assertions. In this paper we describe an implementation of CCA through a pre-processor that will automatically insert the necessary assertions into a high-level language program. Based on the implementation we study the fault detection capabilities of CCA with the help of fault injection experiments using FERRARI.

We present a solution to a complex multi-tone transient detection problem to illustrate the integrated use of symbolic and numeric processing techniques which are supported by well-established underlying models. Examples of such models include synchronous dataflow for numeric processing and the blackboard paradigm for symbolic heuristic search. Our transient detection solution serves to emphasize the importance of developing system design methods and tools which can support the integrated use of well- established symbolic and numerical models of computation. Recently, we incorporated a blackboard-based model of computation underlying the Integrated Processing and Understanding of Signals (IPUS) paradigm into a system-level design environment for numeric processing called Ptolemy. Using the IPUS/Ptolemy environment, we are implementing our solution to the multi-tone transient detection problem.

In a series of ten papers published since 1994, a radically new technique for implementing a wide range of standard image processing operations has been presented, under the acronym SKIPSM (Separated-Kernel Image Processing using finite State Machines). Key steps are: (1) the operation is separated into a row operation followed by a column operation, (2) these row and column operations are put in recursive form. That is, in a form compatible with either one-step software implementation or pipelined raster-scan hardware implementation, (3) the resulting operations are realized as FSMs (finite-state machines), and (4) these FSMs are implemented in software or in inexpensive off-the-shelf integrated circuits. Note that this technique does not require separability, in the usual sense. In this paper, the SKIPSM technique is applied to computing binary openings and closings in one pass using arbitrary binary structuring elements. Whether the resulting finite state machines are implemented in software or hardware, the result is generally much faster and/or much cheaper than conventional implementations. Furthermore, this same SKIPSM architecture is highly versatile and programmable, allowing it to be software-reconfigured to perform hundreds of other software- based or pipelined image processing operations, such a binary and grey-level morphology, the Grassfire Transform, binary and grey-level template matching, binary skeletonization, etc.