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.     

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.     

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].     

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.     

CORDIC-Based Computation of ArcCos

CORDIC-based algorithms to compute cos and are proposed. The implementation requires a standard CORDIC module plus a module to compute the direction of rotation, this being the same hardware required for the extended CORDIC vectoring, recently proposed by the authors [T. Lang and E. Antelo, IEEE Transactions on Computers, vol. 47, no. 7, 1998, pp. 736–749.]. Although these functions can be obtained as a special case of this extended vectoring, the specific algorithm we propose here presents two significant improvements: (1) it uses the same datapath width as the standard CORDIC, even when t has 2n bits (to achieve a granularity of 2^–n for the whole range). In contrast, the extended vectoring unit requires about 2n bits. (2) no repetitions of iterations are needed (the extended vectoring needs some repetitions). The proposed algorithm is compatible with the extended vectoring and, in contrast with previous implementations, the number of iterations and the delay of each iteration are the same as for the conventional CORDIC algorithm.     

A VLSI structure forX(modm) operation

High-computing speed and modularity have made RNS-based arithmetic processors attractive for a long time, especially in signal processing, where additions and multiplications are very frequent. The VLSI technology renewed this interest because RNS-based circuits are becoming more feasible; however, intermodular operations degradate their performance and a great effort results on this topic. In this paper, we deal with the problem of performing the basic operationX(modm), that is the remainder of the integer divisionX/m, for large values of the integerX, following an approximating and correcting approach, which guarantees the correctness of the result.We also define a structure to computeX(modm) by means of few fast VLSI binary multipliers, which is exemplified for 32-bit long numbers, obtaining a total response time lower than 200 nsec. Furthermore, such a structure is evaluated in terms of VLSI complexity and area and time figuresA=(n ² T _m ² ) andT=(T _M ) for the parameterT _M in are derived. A simple positional-to-residue converter is finally presented, based on this structure; it improves some complexity results previously obtained by authors.This work has been supported by the National Program on Solid-State Electronics and Devices of the Italian National Research Council.     

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.     

Soft interference cancellation in multiuser communications

In this paper the performance of soft interference cancellation in synchronous multiuser channels is investigated. Two-stage detection with decorrelator in the first stage is considered. Soft first stage tentative decisions are formed by means of a multilevel quantizer or linear clipper. The asymptotic multiuser efficiency (AME) is used as a performance measured for optimization of the nonlinearity. It is shown, for the two-user case, that soft interference cancellation by means of an optimized linear clipper achieves the AME of the maximum likelihood detector if the crosscorrelation of the signature waveforms is less than . For the K-user case, novel upper bounds on the AME for two-stage detectors with feedback interference cancellation, with both hard and soft tentative decisions, are obtained. The derived bounds are used to examine the performance of two-stage detectors in a cellular scenario.     

High performance op amps in a 40V BiCMOS process and their applications

This paper describes the design of three high-performance op amps in a 40V BiCMOS technology. The first circuit is a low-noise op amp with MOS inputs. A thermal noise level as low as with a 1/f noise corner frequency of 100 Hz is achieved. For applications that can tolerate a lower input impedance, a more economical bipolar input low-noise op amp has been designed, yielding an even better noise performance for source impedances up to 20 k. The third circuit is an internally compensated high-gain-bandwidth (GBW=15 MHz) op amp that can drive loads from 0 to 20 pF. A fourth-order low-pass switched-capacitor filter making use of the latter op amp is discussed next. Finally the applications of this 40V BiCMOS process are illustrated.     

A fast algorithm for discrete hartley transform of arbitrary length

DHT of length p~lq(p is odd and q is arbitrary) is turned into p~l DHTs of length qand some additional operations, while the additional operations only involves the computation ofcos-DFT and sin-DFT with length p. If the length of a DHT is p_1~(l_1)…P_N~(l_N)2~l(P_1…,P_N are oddprimes), a fast algorithm is obtained by the similar recursive technique. Therefore, the algorithmcan compute DHT of arbitrary length. The paper also Proves that operations for computingDHT of length N by the algorithm are no more than O(Nlog_2N), when the length is N=p~l,operations of the algorithm are fewer than that of other known algorithms.     

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.     

Geometric properties of nonlinear networks containing capacitor-only cutsets and/or inductor-only loops. Part II: Symmetries

This paper is the last in a two-part sequence which studies nonlinear networks, containing capacitor-only cutsets and/or inductor-only loops, from the geometric coordinate-free point of view of the theory of differentiable manifolds. For such circuits, it is shown that (subject to certain assumptions) there is a naturally defined Lie group action of on the state space ofN, where ₀ is the sum of the number of independent capacitor-only cutsets and the number of independent inductor-only loops. Circuit theoretic sufficient conditions on the reactive constitutive relations are derived for the circuit dynamics to be invariant under this Lie group action.This work was supported by the Natural Sciences and Engineering Research Council of Canada, under Grant Number A7113, and by scholarships from the Natural Sciences and Engineering Research Council of Canada and the Ontario Provincial Government.     

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.     

Creep behavior of eutectic Sn-Cu lead-free solder alloy

Tensile creep behavior of precipitation-strengthened, tin-based eutectic Sn-0.7Cu alloy was investigated at three temperatures ranging from 303–393 K. The steady-state creep rates cover six orders of magnitude (10⁻³−10⁻⁸ s⁻¹) under the stress range of σ/E=10⁻⁴−10⁻³. The initial microstructure reveals that the intermetallic compound Cu₆Sn₅ is finely dispersed in the matrix of β-Sn. By incorporating a threshold stress, σ _th, into the analysis, the creep data of eutectic Sn-Cu at all temperatures can be fitted by a single straight line with a slope of 7 after normalizing the steady-state creep rate and the effective stress, indicating that the creep rates are controlled by the dislocation-pipe diffusion in the tin matrix. So the steady-state creep rate, , can be expressed as exp , where Q_c is the activation energy for creep, G is the temperature-dependent shear modulus, b is the Burgers vector, R is the universal gas constant, T is the temperature, σ is the applied stress, A is a material-dependent constant, and , in which σ _OB is the Orowan bowing stress, and k_R is the relaxation factor. An erratum to this article is available at .     

A Fully Integrated, Low Noise and Low Power BiCMOS Front-end Readout System for Capacitive Detectors

Bipolar transistors are interesting for low noise front-end readout systems when high speed and low power consumption are required. This paper presents a fully integrated, low noise front-end design for the future Large Hadron Collider (LHC) experiments using the radiation hard SOI BiCMOS process. In the present prototype, the input-referred Equivalent Noise Charge (ENC) of 990 electrons (rms) for 12 pF detector capacitance with a shaping time of 25 ns and power consumption of 1.4 mW/channel has been measured. The gain of this front-end is 90 mV/MIP (Minimum Ionisation Particle: 1 fC) with non-linearity of less than 3% and linear input dynamic range is MIP. These results are obtained at room temperature and before irradiation. The measurements after irradiations by high intensity pion beam with an integrated flux of pions/cm² are also presented in this paper.     

A Low Complexity and Low Power SoC Design Architecture for Adaptive MAI Suppression in CDMA Systems

In this paper, we propose a reduced complexity and power efficient System-on-Chip (SoC) architecture for adaptive interference suppression in CDMA systems. The adaptive Parallel-Residue-Compensation architecture leads to significant performance gain over the conventional interference cancellation algorithms. The multi-code commonality is explored to avoid the direct Interference Cancellation (IC), which reduces the IC complexity from to . The physical meaning of the complete versus weighted IC is applied to clip the weights above a certain threshold so as to reduce the VLSI circuit activity rate. Novel scalable SoC architectures based on simple combinational logic are proposed to eliminate dedicated multipliers with at least saving in hardware resource. A Catapult C High Level Synthesis methodology is apply to explore the VLSI design space extensively and achieve at least speedup. Multi-stage Convergence-Masking-Vector combined with clock gating is proposed to reduce the VLSI dynamic power consumption by up to This paper was presented in part at IEEE ISCAS in Vancouver, Canada, May, 2004.     

Variance and Covariance Computations for 2-D ARMA Processes

An algorithm is presented to compute the variance of the output of a two-dimensional (2-D) stable auto-regressive moving-average (ARMA) process driven by a white noise bi-sequence with unity variance. Actually, the algorithm is dedicated to the evaluation of a complex integral of the form , where and G(z₁,z₂) = B(z₁, z₂) / A(z₁, z₂) is stable (z₁,z₂)-transferfunction. Like other existing methods, the proposed algorithmis based on the partial-fraction decomposition G(z₁,z₂)G(z ₁ ^-1 , z ₂ ^-1 ) = X(z₁, z₁) / A(z₁,z₂)+ X(z ₁ ^-1 , z ₂ ^-1 ) / A(z ₁ ^-1 , z ₂ ^-1 ). However,the general and systematic partial-fraction decomposition schemeof Gorecki and Popek [1] is extended to determine X(z₁,z₂).The key to the extension is that of bilinearly transforming thediscrete (z₁, z₂)-transfer function G(z₁,z₂)into a mixed continuous-discrete (s₁, z₂)-transferfunction . As a result, the partial-fraction decomposition involves only efficient DFT computations for the inversion of a matrix polynomial, and the value of I is finally determined by the residue method with finding the roots of a 1-D polynomial. The algorithm is very easy to implement and it can be extended to the covariance computation for two 2-D ARMA processes.