Computing Moments by Prefix Sums

Moments of images are widely used in pattern recognition, because in suitable form they can be made invariant to variations in translation, rotation and size. However the computation of discrete moments by their definition requires many multiplications which limits the speed of computation. In this paper we express the moments as a linear combination of higher order prefix sums, obtained by iterating the prefix sum computation on previous prefix sums, starting with the original function values. Thus the pth moment can be computed by O (N · p) additions followed by p multiply-adds. The prefix summations can be realized in time O(N) using p + 1 simple adders, and in time O(p log N) using parallel prefix computation and O(N) adders. The prefix sums can also be used in the computation of two-dimensional moments for any intensity function f(x,y). Using a simple bit-serial addition architecture, it is sufficient with 13 full adders and some shift registers to realize the 10 order 3 image moment computations for a 512 × 512 size image at the TV rate. In 1986 Hatamian published a computationally equivalent algorithm, based on a cascade of filters performing the summations. Our recursive derivation allows for explicit expressions and recursive equations for the coefficients used in the final moment calculation. Thus a number of alternative forms for the moment computation can be derived, based on different sets of prefix sums. It is also shown that similar expressions can be obtained for the moments introduced by Liao and Pawlak in 1996, forming better approximations to the exact geometric moments, at no extra computational cost.     

2D grid architectures for the DFT and the 2D DFT

New algorithms for the DFT and the 2-dimensional DFT are presented. The DFT and the 2-dimensional DFT matrices can be expressed as the Kronecker product of DFT matrices of smaller dimension. These algorithms are synthesized by combining the efficient factorization of the Kronecker product of matrices with the highly hardware efficient recursive implementation of the smaller DFT matrices, to yield these algorithms. The architectures of the processors implementing these algorithms consist of 2-dimensional grid of processing elements, have temporal and spatial locality of connections. For computing the DFT of sizeN or for the 2D DFT of sizeN=N ₁ byN ₁, these algorithms require 2N multipliers and adders, take approximately computational steps for computing a transform vector, and take approximately computation steps between the computation of two successive transform vectors.     

VLSI architecture for fast 2D discrete orthonormal wavelet transform

The discrete wavelet transform (DWT) provides a new method for signal/image analysis where high frequency components are studied with finer time resolution and low frequency components with coarser time resolution. It decomposes a signal or an image into localized contributions for multiscale analysis. In this paper, we present a parallel pipelined VLSI array architecture for 2D dyadic separable DWT. The 2D data array is partitioned into non-overlapping groups of rows. All rows in a partition are processed in parallel, and consecutive partitions are pipelined. Moreover, multiple wavelet levels are computed in the same pipeline, and multiple DWT problems can be pipelined also. The whole computation requires a single scan of the image data array. Thus, it is suitable for on-line real-time applications. For anN×N image, anm-level DWT can be computed in time units on a processor costing no more than , whereq is the partition size,p is the length of corresponding 1D DWT filters,C _m andC _a are the costs of a parallel multiplier and a parallel adder respectively, and a time unit is the time for a multiplication and an addition. Forq=N m, the computing time reduces to . When a large number of DWT problems are pipelined, the computing time is about per problem.     

A CMOS Monolithic Image-Reject Filter

A CMOS inductorless image-reject filter based on active RLC circuitry is discussed and designed with the emphasis on low-noise, low-power, and gigahertz-range circuits. Two -enhancement techniques are utilized to circumvent the low characteristics inherent in the simple feedback circuit. The frequency tuning is almost independent of tuning, facilitating the design of the automatic tuning circuitry. The stability and the tuning scheme of the filter are also discussed. Simulations using 0.6 m CMOS technology demonstrate the feasibility of the tunable image-reject filter for GSM wireless applications. Simulation results show 4.75 dB voltage gain, 9.5 dB noise figure, and –20 dBm IIP3 at a passband centered at 947 MHz. The image signal suppression is 60 dB at 1089 MHz and the power consumption is 27 mW.     

BIBO Stability of D-Dimensional Filters

Consider the class of d-dimensional causal filters characterized by a d-variate rational function analytic on the polydisk . The BIBO stability of such filters has been the subject of much research over the past two decades. In this paper we analyze the BIBO stability of such functions and prove necessary and sufficient conditions for BIBO stability of a d-dimensional filter. In particular, we prove if a d-variate filter H(z) analytic on has a Fourier expansion that converges uniformly on the closure of , then H(z) is BIBO stable. This result proves a long standing conjecture set forth by Bose in [3].     

Statistical Design of the Four-MOSFET Structure

The statistical design of the four-MOSFET structure is presented in this paper. The quantitative measure of the effect of mismatch between the four transistors on nonlinearity and offset current is provided through contours. Statistical optimization of the transistor and values is demonstrated. The four-MOSFET structure was fabricated through the MOSIS 2 m process using MOS transistor Level-3 model parameters. Experimental results are included in the paper.     

Finite-Memory Systems

Let K be a field, k and n positive integers and let matrices with coefficients in K. For any function

On the Scalability of 2-D Discrete Wavelet Transform Algorithms

The ability of a parallel algorithm to make efficient use of increasing computational resources is known as its scalability. In this paper, we develop four parallel algorithms for the 2-dimensional Discrete Wavelet Transform algorithm (2-D DWT), and derive their scalability properties on Mesh and Hypercube interconnection networks. We consider two versions of the 2-D DWT algorithm, known as the Standard (S) and Non-standard (NS) forms, mapped onto P processors under two data partitioning schemes, namely checkerboard (CP) and stripped (SP) partitioning. The two checkerboard partitioned algorithms (Non-standard form, NS-CP), and as (Standard form, S-CP); while on the store-and-forward-routed (SF-routed) Mesh and Hypercube they are scalable as (NS-CP), and as (S-CP), respectively, where M ² is the number of elements in the input matrix, and (0,1) is a parameter relating M to the number of desired octaves J as . On the CT-routed Hypercube, scalability of the NS-form algorithms shows similar behavior as on the CT-routed Mesh. The Standard form algorithm with stripped partitioning (S-SP) is scalable on the CT-routed Hypercube as M ² = (P ²), and it is unscalable on the CT-routed Mesh. Although asymptotically the stripped partitioned algorithm S-SP on the CT-routed Hypercube would appear to be inferior to its checkerboard counterpart S-CP, detailed analysis based on the proportionality constants of the isoefficiency function shows that S-SP is actually more efficient than S-CP over a realistic range of machine and problem sizes. A milder form of this result holds on the CT- and SF-routed Mesh, where S-SP would, asymptotically, appear to be altogether unscalable.     

Current-Mode High Output Impedance Multifunction Filters Employing Minimum Number of FTFNs

In this study, five current-mode FTFN-based multifunction filters are proposed, which realize the same transfer functions in ideal case. All circuits employ two capacitors and three resistors. For each circuit R-C:C-R transformation increases the number of realization possibilities to ten. The proposed topologies simultaneously realize three basic filtering functions using minimum number of FTFNs and provide high output impedances that enable easy cascading in current mode. Sensitivity analysis of the filters show that they have low passive sensitivities, and of the filters are insensitive to current tracking errors, furthermore of the filters are insensitive to voltage tracking errors of the FTFNs. The proposed circuits do not require component matching condition except for notch and allpass responses and permit independent adjustment of without disturbing . Experimental and simulation results are given to verify the theoretical analyses.     

The Design of a 2-V 900-MHz CMOS Bandpass Amplifier

A 900 MHz low-power CMOS bandpassamplifier suitable for the applications of RFfront-end in wireless communication receiversis proposed and analyzed. In this design, thetemperature compensation circuit is used tostabilize the amplifier gain so that theoverall amplifier has a good temperaturestability. Moreover, the compact tunablepositive-feedback circuit is connected to theintegrated spiral inductor to generate thenegative resistance and enhance its value. The simple diode varactor circuit isadopted for center-frequency tuning. These twoimproved circuits can reduce the powerdissipation of the amplifier. An experimentalchip fabricated by 0.5 mdouble-poly-double-metal CMOS technologyoccupies a chip area of ; chip area. The measuredresults have verified the performance of thefabricated CMOS bandpass amplifier. Under a2-V supply voltage, the measured quality factoris tunable between 4.5 and 50 and the tunablefrequency range is between 845 MHz and 915 MHz. At , the measured is 20 dB whereas thenoise figure is 5.2 dB in the passband. Thegain variation is less than 4 dB in the rangeof 0–80^°C. The dc powerdissipation is 35 mW. Suitable amplifier gain,low power dissipation, and good temperaturestability make the proposed bandpass amplifierquite feasible in RF front-endapplications.     

Linear phase FIR approximation of magnitude response |1/ω| for maximal flatness at an arbitrary frequency ω0, 0<ω0<π*

In many signal processing situations, the desired (ideal) magnitude response of the filter is a rational function: (a digital integrator). The requirements of a linear phase response and guaranteed stable performance limit the design to a finite impulse response (FIR) structure. In many applications we require the FIR filter to yield a highly accurate magnitude response for a narrow band of frequencies with maximal flatness at an arbitrary frequency ₀ in the spectrum (0, ). No techniques for meeting such requirements with respect to approximation of are known in the literature. This paper suggests a design by which the linear phase magnitude response can be approximated by an FIR configuration giving a maximally flat (in the Butterworth sense) response at an arbitrary frequency ₀, 0<₀<^*. A technique to compute exact weights for the design has also been given.     

A 5.8 GHz Low Noise Amplifier for Wireless LAN Applications in Silicon Bipolar Technology

A monolithic integrated low-noise amplifier for operation in the 5.8-GHzband is described. Two different versions have been implemented where the biasing wasadapted to allow operation over a different range of supply voltage. At 5-V, theamplifiers gain is about 17-dB, with a noise figure of 4.2-dB and 1-dB compressionpoint at –15-dBm input power. The circuits have been designed utilizing a0.6-micron silicon bipolar production technology, featuring npn transistors with and of about20-GHz.     

Can One Control the Vibrations of a Drum?

This paper considers the problem of constructing feedback stabilizing controllers for the wave operator on ⁿ (more generally AR systems determined by a hyperbolic operator). In order to accomplish this, it must first clarify the notion of an input-output structure on a distributed system, as well as what it means to interconnect two such systems. Both these notions are shown to be consequences of a structure which generalizes the standard causal structure of lumped systems determined by the flow of time. Given this apparatus, the paper then constructs feedback controllers which stabilize the wave equation along directions given by a proper cone in ⁿ.     

A Symbolic Circuit Analysis-Oriented Algorithm for Finding a Common Tree of the Current and Voltage Graphs

A fundamental problem of symbolic analysis of electric networks when using the signal-flow (SFG) graph method is to find the common tree of the current and voltage graph ( and , respectively). In this paper we introduce a novel method in order to determine a common tree of both graphs, which may be used to obtain the symbolic network transfer function when carrying out the small-signal analysis of linear(ised) circuits.     

Orthogonal cycle transforms of stochastic matrices

In this paper we investigate new Fourier series with respect to orthonormal families of directed cycles , which occur in the graph of a recurrent stochastic matrixP. Specifically, it is proved thatP may be approximated in a suitable Hilbert space by the Fourier series . This approach provides a proof in terms of Hilbert space of the cycle decomposition formula for finite stochastic matricesP.     

A DDS Synthesizer with Digital Time Domain Interpolator

A DDS type circuit structure for producing numericallyprogrammable square wave clock signal is presented. The high speed D/Aconverter needed in conventional DDS systems is replaced by an tap delay line time domain interpolator thateffectively increases the sampling rate by a factor of . Thus the circuit can be used up to full clock rate withoutimage filtering. A prototype IC with clock frequency of 30 MHz, 5 bitinterpolator and SFDR of –40 dBc up to 10 MHz and –33 dBcup to 15 MHz has been designed and tested.     

A Small Area Charge Sensitive Readout Chain with a Dual Mode of Operation

A charge sensitive readout chain has been designed and fabricated in acommercially available 0.8 m CMOS technology. The readout chain is optimizedfor pixel detectors measuring soft X-ray energies up to 20 KeV. In the first modean analog signal proportional to input charge is generated and processed in realtime. In the second mode a peak-and-hold operation is enabled and therelevant signal is processed in later time. This dual mode of operation iscontrolled by an external digital signal. The readout chain consists of a chargeamplifier, a shaper, an operational amplifier which can either operate as avoltage amplifier or a peak detector and an output buffer. Its area is . The gain at the shaper output is 378 mv/fC, theENC is 16 rms at 160 nsec shaping time. The overall gainis 557 mV/fC, the ENC is rms with 240 nsec peaking timeand 1.4 sec recovery time. The overall power dissipation is 1.5 mWatt with aload capacitance of 25 pF.     

Use of TCP Decoupling in Improving TCP Performance over Wireless Networks

We propose using the TCP decoupling approach to improve a TCP connection's goodput over wireless networks. The performance improvement can be analytically shown to be proportional to , where MTU is the maximum transmission unit of participating wireless links and HP_Sz is the size of a packet containing only a TCP/IP header. For example, on a WaveLAN [32] wireless network, where MTU is 1500 bytes and HP_Sz is 40 bytes, the achieved goodput improvement is about 350%. We present experimental results demonstrating that TCP decoupling outperforms TCP reno and TCP SACK. These results confirm the analysis of performance improvement.