Search

Measuring visual quality, as perceived by human observers, is becoming increasingly important in a large number of applications where humans are the ultimate consumers of visual information. Many natural image databases have been developed that contain human subjective ratings of the images. Subjective quality evaluation data is less available for synthetic images, such as those commonly encountered in graphics novels, online games or internet ads. A wide variety of powerful full-reference, reduced-reference and no-reference Image Quality Assessment (IQA) algorithms have been proposed for natural images, but their performance has not been evaluated on synthetic images. In this paper we (1) conduct a series of subjective tests on a new publicly available Embedded Signal Processing Laboratory (ESPL) Synthetic Image Database, which contains 500 distorted images (20 distorted images for each of the 25 original images) in 1920 × 1080 resolution, and (2) evaluate the performance of more than 50 publicly available IQA algorithms on the new database. The synthetic images in the database were processed by post acquisition distortions, including those arising from compression and transmission. We collected 26,000 individual ratings from 64 human subjects which can be used to evaluate full-reference, reduced-reference, and no-reference IQA algorithm performance. We find that IQA models based on scene statistics models can successfully predict the perceptual quality of synthetic scenes. The database is available at: http://signal.ece.utexas.edu/%7Ebevans/synthetic/ .

In this paper, we investigate hybrid analog/digital beamforming for multiple-input multiple-output (MIMO) systems with low-resolution analog-to-digital converters (ADCs) for millimeter wave (mmWave) communications. In the receiver, we propose to split the analog combining subsystem into a channel gain aggregation stage followed by a spreading stage. Both stages use phase shifters. Our goal is to design the two-stage analog combiner to optimize mutual information (MI) between the transmitted and quantized signals by effectively managing quantization error. To this end, we formulate an unconstrained MI maximization problem without a constant modulus constraint on analog combiners, and derive a two-stage analog combining solution. The solution achieves the optimal scaling law with respect to the number of radio frequency chains and maximizes the MI for homogeneous singular values of a MIMO channel. We further develop a two-stage analog combining algorithm to implement the derived solution for mmWave channels. By decoupling channel gain aggregation and spreading functions from the derived solution, the proposed algorithm implements the two functions by using array response vectors and a discrete Fourier transform matrix under the constant modulus constraint on each matrix element. Therefore, the proposed algorithm provides a near optimal solution for the unconstrained problem, whereas conventional hybrid approaches offer a near optimal solution only for a constrained problem. The closed-form approximation of the ergodic rate is derived for the algorithm, showing that a practical digital combiner with two-stage analog combining also achieves the optimal scaling law. Simulation results validate the algorithm performance and the derived ergodic rate., 13 pages, 7 figures, submitted to IEEE Transactions on Signal Processing

In this paper, we propose a hybrid analog-digital beamforming architecture with resolution-adaptive ADCs for millimeter wave (mmWave) receivers with large antenna arrays. We adopt array response vectors for the analog combiners and derive ADC bit-allocation (BA) solutions in closed form. The BA solutions reveal that the optimal number of ADC bits is logarithmically proportional to the RF chain's signal-to-noise ratio raised to the 1/3 power. Using the solutions, two proposed BA algorithms minimize the mean square quantization error of received analog signals under a total ADC power constraint. Contributions of this paper include 1) ADC bit-allocation algorithms to improve communication performance of a hybrid MIMO receiver, 2) approximation of the capacity with the BA algorithm as a function of channels, and 3) a worst-case analysis of the ergodic rate of the proposed MIMO receiver that quantifies system tradeoffs and serves as the lower bound. Simulation results demonstrate that the BA algorithms outperform a fixed-ADC approach in both spectral and energy efficiency, and validate the capacity and ergodic rate formula. For a power constraint equivalent to that of fixed 4-bit ADCs, the revised BA algorithm makes the quantization error negligible while achieving 22% better energy efficiency. Having negligible quantization error allows existing state-of-the-art digital beamformers to be readily applied to the proposed system., Accepted to IEEE Transactions on Signal Processing

Video stabilization smooths camera motion estimates in a way that should adapt to different types of intentional motion. Corrective motion (the difference between smoothed and original motions) should be constrained so that black borders do not intrude into the (cropped) stabilized frames. Although offline smoothing can use all of the frames, online (real-time) smoothing can only use a small number of previous frames. In this paper, we propose an online motion smoothing method based on linear estimation applied to a constant-velocity model. We use estimate projection to ensure that the smoothed motion satisfies black-border constraints, which are modeled exactly by linear inequalities for general 2D motion models. We then combine the estimate projection with multiple-model estimation, which can adaptively smooth the camera motion in a probabilistic way. Experimental results show how the proposed algorithm can better smooth the camera motion and stabilize videos in real time.

We present a novel motion smoothing algorithm for hand-held cameras with application to video stabilization. Video stabilization seeks to remove unwanted frame-to-frame jitter due to camera shake. For video stabilization, we use a pure 3D rotation motion model with known camera projection parameters. The 3D camera rotation can be reliably tracked by a gyroscope as commonly found on a smart phone or tablet. In this paper, we directly smooth the sequence of camera rotation matrices for the video frames by exploiting the Riemannian geometry on a manifold. Our contributions are 1) formulation of motion smoothing as a geodesic-convex constrained regression problem on a nonlinear manifold based on geodesic distance, 2) computation of gradient and Hessian of the objective function using Riemannian geometry for gradient-related manifold optimization, and 3) generalization of the two-metric projection algorithm in Euclidean space to manifolds to solve the proposed manifold optimization problem efficiently. The geodesic-distance-based smoothness metric better exploits the manifold structure of sequences of rotation matrices. The geodesic-convex constraints effectively guarantee that no black borders intrude into the stabilized frames. The proposed manifold optimization algorithm can find the global optimal solution in only a few iterations. Experimental results show that video stabilization based on our motion smoothing algorithm outperforms state-of-the-art methods by generating videos with less jitter and without black borders.

Characterizing interference statistics is central to the design and analysis of both physical layer and medium access control layer techniques to mitigate interference in a wireless network. The applicability of interference statistics, however, is limited by the assumptions adopted to derive the statistics in closed-form. Common assumptions for a decentralized wireless network include temporally independent user locations and an unbounded pathloss function. In this correspondence, we derive the joint temporal statistics of interference that capture the temporal correlation in the network along with the realistic assumption of a bounded pathloss function. The closed-form statistics are asymptotically exact for low tail probabilities, and match closely in simulations even when the tail probability is fairly high. The primary contributions are to i) show that joint interference statistics follow a multivariate Gaussian mixture distribution under the assumption of a bounded pathloss function, and ii) characterize the joint tail probability decay behavior for both bounded and unbounded pathloss functions.

Many wireless data communications systems, such as LTE, Wi-Fi, and Wimax, have become or are rapidly becoming interference limited due to radio frequency interference (RFI) generated by both human-made and natural sources. Human-made sources of RFI include uncoordinated devices operating in the same frequency band, devices communicating in adjacent frequency bands, and computational platform subsystems radiating clock frequencies and their harmonics. Additive RFI for these wireless systems has predominantly non-Gaussian statistics, and is well modeled by the Middleton Class A distribution for centralized networks, and the symmetric alpha stable distribution for decentralized networks. Our primary contribution is the derivation of joint spatial statistical models of RFI generated from uncoordinated interfering sources randomly distributed around a multiantenna receiver. The derivation is based on statistical-physical interference generation and propagation mechanisms. Prior results on joint statistics of multiantenna interference model either spatially independent or spatially isotropic interference, and do not provide a statistical-physical derivation for certain network environments. Our proposed joint spatial statistical model captures a continuum between spatially independent and spatially isotropic statistics, and hence includes many previous results as special cases. Practical applications include co-channel interference modeling for various wireless network environments, including wireless ad hoc, cellular, local area, and femtocell networks.

Real-time streaming signal processing systems typically desire high throughput and low latency. Many such systems can be modeled as synchronous data flow graphs. In this paper, we address the problem of multi-objective mapping of SDF graphs onto heterogeneous multiprocessor platforms, where we account for the overhead of bus-based inter-processor communication. The primary contributions include (1) an integer linear programming (ILP) model that globally optimizes throughput, latency and cost; (2) low-complexity two-stage heuristics based on a combination of an evolutionary algorithm with an ILP to generate either a single sub-optimal mapping solution or a Pareto front for design space optimization. In our simulations, the proposed heuristic shows up to 12x run-time efficiency compared to the global ILP while maintaining a 10???6 optimality gap in throughput.

With increasing spatial reuse of radio spectrum, co-channel interference is becoming a dominant noise source and may severely degrade the communication performance of wireless transceivers. In this paper, we consider the problem of statistical-physical modeling of co-channel interference from an annular field of Poisson or Poisson-Poisson cluster distributed interferers. Poisson and Poisson-Poisson cluster processes are commonly used to model interferer distributions in large wireless networks without and with interferer clustering, respectively. Further, by considering the interferers distributed over a parametric annular region, we derive interference statistics for finite- and infinite- area interference region with and without a guard zone around the receiver. Statistical modeling of interference is a useful tool to analyze outage probabilities in wireless networks and design interference-aware transceivers. Our contributions include: 1) developing a unified framework for deriving interference models for various wireless network environments; 2) demonstrating the applicability of the symmetric alpha stable and Gaussian mixture (with Middleton Class A as a particular form) distributions in modeling co-channel interference; and 3) deriving analytical conditions on the system model parameters for which these distributions accurately model the statistical properties of the interference. Applications include co-channel interference modeling for various wireless networks, including wireless ad hoc, cellular, local area, and femtocell networks.

In the last two years, the embedded DSP market has been swept up by the general increase in interest in multicore that has been driven by companies such as Intel and Sun. One reason for this is that there is now a lot of focus on tooling in academia and also a willingness on the part of users to accept new programming paradigms. This industry-wide effort will have an effect on the way multicore DSPs are programmed and perhaps architected. But it is too early to say in what way this will occur. Programming multicore DSPs remains very challenging. The problem of how to take a piece of sequential code and optimally partition it across multiple cores remains unsolved. Hence, there will naturally be a lot of variations in the approaches taken. Equally important is the issue of debugging and visibility. Developing effective and easy-to-use code development and real-time debug tools is tremendously important as the opportunity for bugs goes up significantly when one starts to deal with both time and space. The markets that DSP plays in have unique features in their desire for low power, low cost, and hard real-time processing, with an emphasis on mathematical computation. How well the multicore research being performed presently in academia will address these concerns remains to be seen.

In laptop and desktop computers, clocks and busses generate significant radio frequency interference (RFI) for the embedded wireless data transceivers. RFI is well modeled using non-Gaussian impulsive statistics. Data communication transceivers, however, are typically designed under the assumption of additive Gaussian noise and exhibit degradation in communication performance in the presence of RFI. When detecting a signal in additive impulsive noise, Spaulding and Middleton showed a potential improvement in detection of 25 dB at a bit error rate of 10???5 when using a Bayesian detector instead of a standard correlation receiver. In this paper, we model RFI using Middleton Class A and Symmetric Alpha Stable (S ?S) models. The contributions of this paper are to evaluate (1) the performance vs. complexity of parameter estimation algorithms, (2) the closeness of fit of RFI models to the measured interference data from a computer platform, (3) the communication performance vs. computational complexity tradeoffs in receivers designed to mitigate RFI modeled as Class A interference, (4) the communication performance vs. computational complexity tradeoffs in filtering and detections methods to combat RFI modeled as S ?S interference, and (5) the approximations to filtering and detection methods developed to mitigate RFI for a computationally efficient implementation.

We propose a wireless fading channel prediction algorithm for a pilot-symbol aided orthogonal frequency division multiplexing (OFDM) system. Assuming a doubly selective (time and frequency varying) ray-based physical channel model and equispaced pilot subcarriers in time and frequency, this algorithm performs channel model parameter acquisition using a 2-Step 1-D ESPRIT (estimation of signal parameters via rotational invariance techniques) as a first stage, and channel prediction via model extrapolation as a second stage. Since the channel model parameter acquisition has cubic complexity, we also propose a linear complexity channel parameter tracking algorithm based on an improved adaptive ESPRIT algorithm to continuously adapt to the time-varying channel model parameters. We derive the Cramer-Rao lower bound (CRLB) and asymptotic CRLB (ACRLB) for the mean squared error (MSE) in OFDM channel prediction. We show that our proposed OFDM channel prediction algorithm has better MSE performance while maintaining similar computational complexity than previous methods in sparse multipath fading channels characterized by specular scattering, which is most suitable for outdoor mobile macrocell scenarios. Thus, our method can be seen as a complement to the existing schemes that are more suitable for dense multipath channels with diffuse scattering, which is typical of urban pico-cell and indoor wireless scenarios. We provide simulation results based on the IEEE 802.16e mobile broadband wireless access standard to corroborate our claims.

Block diagonalization (BD) is a precoding technique that eliminates interuser interference in downlink multiuser multiple-input multiple-output (MIMO) systems. With the assumptions that all users have the same number of receive antennas and utilize all receive antennas when scheduled for transmission, the number of simultaneously supportable users with BD is limited by the ratio of the number of base station transmit antennas to the number of user receive antennas. In a downlink MIMO system with a large number of users, the base station may select a subset of users to serve in order to maximize the total throughput. The brute-force search for the optimal user set, however, is computationally prohibitive. We propose two low-complexity suboptimal user selection algorithms for multiuser MIMO systems with BD. Both algorithms aim to select a subset of users such that the total throughput is nearly maximized. The first user selection algorithm greedily maximizes the total throughput, whereas the criterion of the second algorithm is based on the channel energy. We show that both algorithms have linear complexity in the total number of users and achieve around 95% of the total throughput of the complete search method in simulations

Several high-speed communication standards modulate encoded data on multiple-carrier frequencies using the fast Fourier transform (FFT). The real part of the quantized inverse FFT samples form a symbol. The symbol is periodically extended by prepending a copy of its last few samples, also known as a cyclic prefix. When the cyclic prefix is longer than the channel order, amplitude and phase distortion can be equalized entirely in the frequency domain. In the receiver, prior to the FFT, a time-domain equalizer, in the form of a finite-impulse response filter, shortens the effective channel impulse response. Alternately, a bank of equalizers tuned to each carrier frequency can be used. In earlier literature, we unified optimal multicarrier equalizer design algorithms as a product of generalized Rayleigh quotients. In this paper, we convert the unified theoretical framework into a framework for fast design algorithms. The relevant literature is reviewed and classified according to this framework. We analyze the achieved bit rate versus implementation complexity (in terms of multiply-and-accumulate operations) tradeoffs in the original and fast design algorithms. The comparison includes multiple implementations of each of 16 different equalizer structures and design algorithms using synthetic and measured discrete multitone modulated data

We describe the design and implementation of a hybrid intelligent surveillance system consisting of an embedded system and a personal computer (PC)-based system. The embedded system performs some of the image processing tasks and sends the processed data to a PC. The PC tracks persons and recognizes two-person interactions by using a grayscale side-view image sequence captured by a stationary camera. Based on our previous research, we explored the optimum division of tasks between the embedded system and the PC, simulated the embedded system using dataflow models in Ptolemy, and prototyped the embedded systems in real-time hardware and software using a 16-bit CISC microprocessor. This embedded system processes one frame image in 89 ms, which is within three frame-cycle periods for a 30 Hz video system. In addition, the real-time embedded system prototype uses 5.7 Kbytes of program memory, 854 Kbytes of internal data memory and 2 Mbytes external DRAM.

To ease equalization in a multicarrier system, a cyclic prefix (CP) is typically inserted between successive symbols. When the channel order exceeds the CP length, equalization can be accomplished via a time-domain equalizer (TEQ), which is a finite impulse response (FIR) filter. The TEQ is placed in cascade with the channel to produce an effective shortened impulse response. Alternatively, a bank of equalizers can remove the interference tone-by-tone. This paper presents a unified treatment of equalizer designs for multicarrier receivers, with an emphasis on discrete multitone systems. It is shown that almost all equalizer designs share a common mathematical framework based on the maximization of a product of generalized Rayleigh quotients. This framework is used to give an overview of existing designs (including an extensive literature survey), to apply a unified notation, and to present various common strategies to obtain a solution. Moreover, the unification emphasizes the differences between the methods, enabling a comparison of their advantages and disadvantages. In addition, 16 different equalizer structures and design procedures are compared in terms of computational complexity and achievable bit rate using synthetic and measured data.

We show that maximum shortening signal-to-noise ratio (SNR) time-domain equalizers (TEQs) are often nearly symmetric. Constraining the TEQ to be symmetric causes only a 3% loss in bit rate (averaged over eight standard ADSL channels). Symmetric TEQs have greatly reduced design and implementation complexity. We also show that for infinite length TEQs, minimum mean squared error (MMSE) target impulse responses have all zeros on the unit circle, which can lead to poor bit rate performance.

Grayscale halftoning converts a continuous-tone image (e.g., 8 bits per pixel) to a lower resolution (e.g., 1 bit per pixel) for printing or display. Grayscale halftoning by error diffusion uses feedback to shape the quantization noise into high frequencies where the human visual system (HVS) is least sensitive. In color halftoning, the application of grayscale error-diffusion methods to the individual colorant planes fails to exploit the HVS response to color noise. Ideally the quantization error must be diffused to frequencies and colors, to which the HVS is least sensitive. Further it is desirable for the color quantization to take place in a perceptual space so that the colorant vector selected as the output color is perceptually closest to the color vector being quantized. This article discusses the design principles of color error diffusion that differentiate it from grayscale error diffusion, focusing on color error diffusion halftoning systems using the red, green, and blue (RGB) space for convenience.

Image halftoning converts a high-resolution image to a low-resolution image, e.g., a 24-bit color image to a three-bit color image, for printing and display. Vector error diffusion captures correlation among color planes by using an error filter with matrix-valued coefficients. In optimizing vector error filters, Damera-Venkata and Evans (see IEEE Trans. Image Processing, vol.10, p.1552-65, Oct. 2001) transform the error image into an opponent color space where Euclidean distance has perceptual meaning. This letter evaluates color spaces for vector error filter optimization. In order of increasing quality, the color spaces are YIQ, YUV, opponent (by Poirson and Wandell, 1993), and linearized CIELab (by Flohr, Kolpatzik, Balasubramanian, Carrara, Bouman, and Allebach, 1993).

Lossy video compression methods often rely on modeling the abilities and limitations of the intended receiver, the human visual system (HVS), to achieve the highest possible compression with as little effect on perceived quality as possible. Foveation, which is non-uniform resolution perception of the visual stimulus by the HVS due to the non-uniform density of photoreceptor cells in the eye, has been demonstrated to be useful for reducing bit rates beyond the abilities of uniform resolution video coders. In this work, we present real-time foveation techniques for low bit rate video coding. First, we develop an approximate model for foveation. Then, we demonstrate that foveation, as described by this model, can be incorporated into standard motion compensation and discrete cosine transform (DCT)-based video coding techniques for low bit rate video coding, such as the H.263 or MPEG-4 video coding standards, without incurring prohibitive complexity overhead. We demonstrate that foveation in the DCT domain can actually result in computational speed-ups. The techniques presented can be implemented using the baseline modes in the video coding standards and do not require any modification to, or post-processing at, the decoder.

In this article, a novel method of performing subband analysis of digital signals is proposed. Conventional subband decomposition algorithms typically use a binary tree filterbank structure comprised of halfband filters. Due to design limitations of finite length filters, conventional decomposition algorithms typically suffer from interference due to aliasing. While longer halfband filters may reduce aliasing, such filters also increase latency and implementation complexity. Our proposed algorithm uses a novel structure of quadrature mirror filters to ensure aliasing is present outside of the spectral region of interest. Simulation results indicate that, compared to conventional algorithms, the proposed algorithm 1) reduces interference from aliasing by over 30dB, 2) reduces signal processing latency, and 3) reduces implementation complexity.

In a discrete multitone receiver, a time-domain equalizer (TEQ) reduces the intersymbol interference (ISI) by shortening the effective duration of the channel impulse response. Current TEQ design methods such as the minimum mean-squared error (MMSE), maximum shortening SNR (MSSNR), and maximum geometric SNR (MGSNR) do not directly maximize bit rate. We develop two TEQ design methods to maximize the bit rate. First, we partition an equalized multicarrier channel into its equivalent signal, noise, and ISI paths to develop a new subchannel SNR definition. Then, we derive a nonlinear function of TEQ taps that measures the bit rate, which the proposed maximum bit rate (MBR) method optimizes. We also propose a minimum-ISI method that generalizes the MSSNR method by weighting the ISI in the frequency domain to obtain higher performance. The minimum-ISI method is amenable to real-time implementation on a fixed-point digital signal processor. Based on simulations using eight different carrier-serving-area loop channels, (1) the proposed methods yield higher bit rates than MMSE, MGSNR, and MSSNR methods; (2) the proposed methods give three-tap TEQs with higher bit rates than 17-tap MMSE, MGSNR, and MSSNR TEQs; (3) the proposed MBR method achieves the channel capacity (as computed by the matched filter bound using the proposed subchannel SNR model) with a five-tap TEQ; and (4) the proposed minimum-ISI method achieves the bit rate of the optimal MBR method.

This paper introduces a new binary shape coding technique called generalized predictive shape coding (GPSC) to encode the boundary of a visual object compactly by using a vertex-based approach. GPSC consists of a contour pixel matching algorithm and a motion-compliant contour coding algorithm. The contour pixel matching algorithm utilizes the knowledge of previously decoded contours by using a uniform translational model for silhouette motion, and generalizes polygon approximation for lossless and lossy motion estimation by adjusting a tolerance parameter d max . To represent motion-compliant regions with minimum information in the transmitted bitstream, we develop a reference index-based coding scheme to represent the 2D positions of the matched segments using 1D reference contour indices. Finally, we encode the mismatched segments by sending residual polygons until the distortion is less than d max . While GPSC realizes polygon approximation exactly at every encoding stage, we can guarantee quality of service because the peak distortion is no greater than d max , and we improve coding efficiency as long as a silhouette complies with the model. The tolerance parameter d max can be assigned to each contour to smooth the transmitted data rate, which is especially useful for constant bandwidth channels. Compared with non-predictive approaches, simulation using MPEG-4 sequences demonstrates that GPSC not only improves objective gain but also enhances visual quality based on MPEG-4 subjective tests. The significance of GPSC is that it provides a generic framework for seamlessly extending conventional vertex coding schemes into the temporal domain yet it retains the advantages of existing polygon-based algorithms for visual content description while furnishing better geometric compression.

We present a robust noniterative algorithm to design optimal minimum-phase digital FIR filters with real or complex coefficients. We derive: (1) the discrete Hilbert transform (DHT) of the complex cepstrum of a causal complex minimum-phase sequence and (2) the minimum fast Fourier transform length for computing the DHT to achieve a desired coefficient accuracy.

We present a scalable framework for real-time data-intensive systems on commodity multiprocessor workstations. The framework is an extension of the process network model, which captures parallelism, guarantees determinate execution, and executes to bounded memory. We implement the framework using lightweight POSIX threads and prototype a 4-GFLOP sonar beamformer on a 12-processor 336-MHz Sun Enterprise server. The beamformer scales nearly linearly from 1 to 12 processors.

We present the first dual tone multiple frequency (DTMF) signal detector that meets the International Telecommunications Union (ITU) Q24 DTMF standard when implemented on an K-bit microcontroller. Key innovations include the use of adaptive notch filters and sophisticated decision logic. The DTMF detector is well suited for a multichannel digital signal processor implementation.

This paper presents an extensible framework for designing analog filters that exhibit several desired behavioral properties after being realized in circuits. In the framework, we model the constrained nonlinear optimization problem as a sequential quadratic programming (SQP) problem. SQP requires real-valued constraints and objective functions that are differentiable with respect to the free parameters (pole-zero locations). We derive the differentiable constraints and a weighted differentiable objective function for simultaneously optimizing the behavioral properties of magnitude response, phase response, peak overshoot, and the implementation property of quality factors. We use Mathematica to define the algebraic equations for the constraints and objective function, compute their gradients symbolically, and generate standalone MATLAB programs to perform the multicriteria optimization. Providing closed-form gradients prevents divergence in the SQP procedure. The automated approach avoids errors in algebraic calculations and errors in transcribing equations into software. The key contributions are: 1) an extensible, automated, multicriteria filter optimization framework; 2) an analytic approximation for peak overshoot; and 3) three novel filter designs. We have released the source code for the framework on the Internet.

The International Telecommunication Union (ITU) recommendations for dual-tone multifrequency (DTMF) signaling are not met by conventional DTMF detectors. We present an efficient DTMF detection algorithm based on the nonuniform discrete Fourier transform that meets all of the ITU recommendations. The key innovations are the use of two sliding windows and development of sophisticated timing tests. Our algorithm requires no buffering of input samples. To perform DTMF detection on n telephone channels, our algorithm requires approximately n MIPS on a digital signal processor (DSP), 75+30n words of data memory, and 1000 words of program memory. Using the new algorithm, a single fixed-point DSP can perform ITU-compliant DTMF detection on the 24 telephone channels of a T1 time-division multiple multiplexed telecommunications line.

We improve capacity of broadcast channels by employing multiple transmitters and exploiting the spatial diversity among the users. We derive fast algorithms to compute orthogonal, near-optimal, and optimal weight vectors for broadcasting message signals to two and three users. The key innovation is that we decouple the weight vectors in the measure of channel capacity to (1) simplify the optimization problem to a search for the maxima of a smooth multidimensional function and (2) derive closed-form expressions for the orthogonal and near-optimal algorithms.

In multiple dimensions, the cascade of an upsampler by L and a downsampler by M commutes if and only if the integer matrices L and M are right coprime and LM=ML. This letter presents algorithms to design L and M that yield commutative upsampler/dowsampler cascades. We prove that commutativity is possible if the Jordan canonical form of the rational (resampling) matrix R=LM/sup -1/ is equivalent to the Smith-McMillan form of R. A necessary condition for this equivalence is that R has an eigendecomposition and the eigenvalues are rational.

We propose a novel receiver for orthogonal frequency division multiplexing (OFDM) transmissions in impulsive noise environments. Impulsive noise arises in many modern wireless and wireline communication systems, such as Wi-Fi and powerline communications, due to uncoordinated interference that is much stronger than thermal noise. We first show that the bit-error-rate optimal receiver jointly estimates the propagation channel coefficients, the noise impulses, the finite-alphabet symbols, and the unknown bits. We then propose a near-optimal yet computationally tractable approach to this joint estimation problem using loopy belief propagation. In particular, we merge the recently proposed "generalized approximate message passing" (GAMP) algorithm with the forward-backward algorithm and soft-input soft-output decoding using a "turbo" approach. Numerical results indicate that the proposed receiver drastically outperforms existing receivers under impulsive noise and comes within 1 dB of the matched-filter bound. Meanwhile, with N tones, the proposed factor-graph-based receiver has only O(N log N) complexity, and it can be parallelized., Comment: 13 pages, 9 figures, submitted to IEEE Transactions on Signal Processing

A Smart Grid intelligently monitors and controls energy flows in an electric grid. Having up-to-date distributed readings of grid conditions helps utilities efficiently scale generation up or down to meet demand. Narrowband powerline communication (PLC) systems can provide these up-to-date readings from subscribers to the local utility over existing power lines. A key challenge in PLC systems is overcoming additive non-Gaussian noise. In this paper, we propose to use a cyclostationary model for the dominant component of additive non-Gaussian noise. The key contributions are (1) fitting measured data from outdoor narrowband PLC system field trials to a cyclostationary model, and (2) developing a cyclostationary noise generation model that fits measured data. We found that the period in the cyclostationary model matched half of the period of the main powerline frequency, which is consistent with previous work in indoor PLC additive noise modeling.

Imposing structure on the Smith form of an (integer) periodicity matrix N=U/spl Lambda/V leads to efficient multidimensional (m-D) DFT implementations (Guessoum, 1984). For nonsingular integer and rational matrices, the authors introduce algorithms to generate U (or V) matrices with minimum norm and /spl Lambda/ matrices whose diagonal elements exhibit minimum variance. Such structure simplifies nonuniform m-D filter-bank design (Gardos et al. 1992). >

Identifies a comprehensive set of compact rules and efficient algorithms for simplifying and rearranging structures common in multidimensional multirate signal processing. The authors extend the 1D rules reported by Crochiere and Rabiner (1983), especially the many equivalent forms of cascades of upsamplers and downsamplers. They also include rules reported by other authors for completeness. The extension to mD is based primarily on the Smith form decomposition of resampling (nonsingular integer square) matrices. The Smith form converts non-separable multidimensional operations into separable ones by means a shuffling of input samples and a reshuffling of the separable operations. Based on the Smith form, the authors have developed algorithms for 1) computing coset vectors 2) finding greatest common sublattices 3) simplifying cascades of up/downsampling operations. The algorithms and rules are put together in a form that can be implemented efficiently in a symbolic algebra package. The authors have encoded the knowledge in the commercially available Mathematica environment. >

A video display device having a lower number of bits per pixel than that required by the video to be displayed quantizes the video prior to its display. Halftoning can perform this quantization while attempting to reduce the visibility of certain quantization artifacts. Quantization artifacts are, nevertheless, not eliminated. A temporal artifact known as dirty-window effect (DWE) can be commonly observed in medium frame-rate binary video halftones. In this paper, we propose video halftone enhancement algorithms to reduce DWE. We assess the performance of the proposed algorithms by presenting objective measures for DWE in the original and the improved halftone videos. The expected contributions of this paper include three medium frame-rate binary video halftone enhancement algorithms that do the following: 1) reduce DWE under a spatial quality constraint; 2) reduce DWE under a spatial quality constraint with reduced complexity; and 3) reduce DWE under spatial and temporal quality constraints.

Mathematica, a computer algebra system that supports a sophisticated notebook user interface, which is useful for writing tutorials is discussed. Because of this interface, Mathematica was chosen to assist students in learning linear systems theory. Students interact with Mathematica at two different levels. The lower level is a collection of Mathematica routines known as the signal processing packages (SPP). These packages implement symbolic operations such as convolution and linear transforms and graphical operations such as pole zero diagrams and frequency response plots. The higher level of interaction is with a set of tutorial Notebooks on topics such as convolution and the z transform. The complete system will eventually support the theoretical aspects of a signals and systems curriculum from introductory courses through first-year graduate courses. >

Channel shortening equalizers are used in acoustics to reduce reverberation, in error control decoding to reduce complexity, and in communication receivers to reduce inter-symbol interference. The cascade of a channel and channel shortening equalizer ideally produces an overall impulse response that has most of its energy compacted into fewer adjacent samples. Once designed, channel shortening equalizers filter the received signal on a per-sample basis and need to be adapted or re-designed if the channel impulse response changes significantly. In this paper, we evaluate sparse filters as channel shortening equalizers. Unlike conventional dense filters, sparse filters have a small number of non-contiguous non-zero coefficients. Our contributions include (1) proposing optimal and sub-optimal low complexity algorithms for sparse shortening filter design, and (2) evaluating impulse response energy compaction vs. design and implementation stage computational complexity tradeoffs for the proposed algorithms. We apply the proposed equalizer design procedures to (1) asymmetric digital subscriber line channels and (2) underwater acoustic communication channels. Our simulation results utilize measured channel impulse responses and show that sparse filters are able to achieve the same channel energy compaction with half as many coefficients as dense filters.

Display of a video having a higher number of bits per pixel than that available on the display device requires quantization prior to display. Video halftoning performs this quantization so as to reduce visibility of certain artifacts. In many cases, visibility of one set of artifacts is decreased at the expense of increasing the visibility of another set. In this paper, we focus on two key temporal artifacts, flicker and dirty-window-effect, in binary video halftones. We quantify the visibility of these two artifacts when the video halftone is displayed at medium frame rates (15 to 30 frames per second). We propose new video halftoning methods to reduce visibility of these artifacts. The proposed contributions are (1) an enhanced measure of perceived flicker, (2) a new measure of perceived dirty-window-effect, (3) a new video halftoning method to reduce flicker, and (4) a new video halftoning method to reduce dirty-window-effect.

Many digital signal processing algorithms are first developed in floating point and later converted into fixed point for digital hardware implementation. During this conversion, more than 50% of the design time may be spent for complex designs, and optimum wordlengths are searched by trading off hardware complexity for arithmetic precision at system outputs. We propose a fast algorithm for searching for an optimum wordlength. This algorithm uses sensitivity information of hardware complexity and system output error with respect to the signal wordlengths, while other approaches use only one of the two sensitivities. This paper presents various optimization methods, and compares sensitivity search methods. Wordlength design case studies for a wireless demodulator show that the proposed method can find an optimum solution in one fourth of the time that the local search method takes. In addition, the optimum wordlength searched by the proposed method yields 30% lower hardware implementation costs than the sequential search method in wireless demodulators. Case studies demonstrate the proposed method is robust for searching for the optimum wordlength in a nonconvex space.

Two extensions of the McClellan transformation have been proposed to transform even-length symmetric one-dimensional (1-D) prototype filters into even/odd-length multidimensional filters. We show that, unlike the original McClellan transformation, the two extended McClellan transformations suffer from a limitation in the design of multidimensional two-channel finite impulse response (FIR) perfect reconstruction (PR) filterbanks and wavelets in the sense that there does not exist any transformation function that can preserve PR after transformation, However, for one of the transformations, we point out that near-PR filterbanks are possible.

Reducing power consumption prolongs battery life and increases integration. In digital CMOS designs, switching activity is closely connected with the total power consumption. Switching activity on programmable processors implementing linear filters, fast Fourier transforms, and other signal processing operations is dominated by the hardware multiplier. In this paper, we employ wordlength reduction of multiplicands to reduce switching activity in hardware multipliers using truncation and signed right shift methods. For 32 bit /spl times/ 32 bit Wallace and radix-4 modified Booth multipliers, truncation by 16 bits achieves a 4:1 and 2:1 reduction, respectively, in switching activity, whereas signed right shift gives little or no reduction. The key contribution of this paper is the reduction of power consumption by altering multiplicands in software without any hardware modifications.

Conventional grayscale error diffusion halftoning produces worms and other objectionable artifacts. Tone dependent error diffusion (Li, P. and Allebach, J.P. Proc. SPIE Color Imaging, vol.4663, p.310-21, 2002) reduces these artifacts by controlling the diffusion of quantization errors based on the input graylevel. Li and Allebach designed error filter weights and thresholds for each (input) graylevel with optimization based on a human visual system (HVS) model. We extend tone dependent error diffusion to color. In color error diffusion, what color to render becomes a major concern in addition to finding optimal dot patterns. We present a visually optimum design approach for input level (tone) dependent error filters (for each color plane). The resulting halftones reduce traditional error diffusion artifacts and achieve greater accuracy in color rendition.

During initialization, discrete multitone receivers train a time domain equalizer (TEQ) to shorten the channel impulse response to a preset length, /spl nu/+1. G. Arslan et al. report a minimum intersymbol interference (Min-ISI) method for TEQ design (see IEEE Trans. Sig. Process., vol.49, no.12, p.3123-35, 2001). Min-ISI TEQs give the highest bit rates among single-FIR TEQs amenable to real-time implementation on programmable fixed-point digital signal processors (DSPs). The Min-ISI method, however, has several disadvantages: (1) sensitivity to transmission delay; (2) inability to design TEQs longer than /spl nu/+1 taps; (3) sensitivity to the fixed-point computation in the Cholesky decomposition. We develop an alternate Min-ISI cost function, from which we derive: (1) a fast search method for the optimal transmission delay; (2) extensions to design arbitrary-length Min-ISI TEQs; (3) an iterative Min-ISI method. The iterative Min-ISI method avoids Cholesky decomposition, designs arbitrary length TEQs, and achieves the bit rate performance of the original Min-ISI method.

We evaluate the use of native signal processing with loop unrolling and software prefetching to achieve high-performance digital signal processing on general-purpose processors. We apply these techniques to minimize the number of processors necessary for real-time implementation of a 3-D sonar beamformer. Because our beamforming kernels operate on high-throughput (/spl sim/100 Mb/s) input/output streams, memory latency hiding techniques are key for maximum performance. On the Sun UltraSPARC-II processor, we find speedups of 2.4 for hand loop unrolling, 1.46 for the visual instruction set over floating-point arithmetic in C, and 1.33 for software prefetching.

We optimize implementations of one-dimensional and multidimensional signal processing algorithms by rewriting subexpressions according to a set of algebraic identities. We encode the algebraic identities as conditional rules, and program hill climbing and simulated annealing search techniques to apply the rules. Both of these search techniques avoid an exponential explosion in memory usage because they only keep a single state in memory instead of building the entire tree of possible equivalent forms. We compare the effectiveness of these search techniques in optimizing implementations of one-dimensional multirate signal processing algorithms. Our prototype environment is written in Mathematica.

We are developing a sophomore course to serve as a first course in electrical engineering. The course focuses on discrete-time systems. Its goal is to give students an intuitive understanding of concepts such as sinusoids, frequency domain, sampling, aliasing, and quantization. In the laboratory, students build simulations and real-time systems to test these ideas. By using a combination of high-level and DSP assembly languages, the students experiment with a variety of views into the representation, design, and implementation of systems. The students are exposed to a digital style of implementation based on programming both desktop and embedded processors.

The authors describe extensions to a symbolic mathematics program that make it an effective educational tool for courses in linear systems theory. These extensions are in the form of packages and notebooks for the Mathematica environment. The new signal processing packages contain rule bases that symbolically compute convolutions and all the transforms common to signal processing: Fourier, Laplace, z, etc. In order to introduce a student to these concepts and to how they are implemented in Mathematica, four tutorials have been written in Mathematica's notebook format. Notebooks, a form of hypertext, allow students to access material randomly, to discover insights at their own pace, and to evaluate code provided in the examples. Students can also use notebooks to solve homework problems in a self-documenting fashion. >

The implementation of basic signal analysis and transforms for DSP (digital signal processing) with a symbolic mathematical program called Mathematica is described. By extending its capabilities through a proper representation of knowledge of discrete signals, operators, and transforms, Mathematica can take the forward and inverse z-transforms symbolically and apply the discrete Fourier transform (DFT) as a symbolic summation. In addition to the 150+ common mathematical operators and functions built into Mathematica, the rule-based package defines 23 systems and 8 basic signals. Six of these systems provide the ability to take forward and inverse z-transforms, DFTs, and DTFTs of multidimensional signal processing expressions. More importantly, this package allows the user to manipulate signals (functions or data) and systems (operators) as algebraic expressions. The user can convert symbolic signal processing expressions to graphical, numeric, and textual representations. >

A typical path in learning digital signal processing begins at the theoretical end and progresses toward the practical constraints imposed by implementation in hardware or software. On this path, the student would learn how to convert mathematical theory into algorithms and then algorithms into efficient implementations. In this paper, we first summarize the electronic courseware we have already developed in Mathematica, MATLAB, and Ptolemy to teach DSP theory, algorithms, and implementation, respectively. Then, we discuss ways to integrate our efforts to help students discover the connections between these topics.