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.     

Linear systems in a saturated mode and convergence as gain becomes large of asymptotically stable equilibrium points of neural nets

We study solutions of the linear system in a saturated mode

Gaussian radial basis functions and inner product spaces

An approximation result is given concerning Gaussian radial basis functions in a general inner product space. Applications are described concerning the classification of the elements of disjoint sets of signals, and also the approximation of continuous real functions defined on all of ⁿ using radial basis function (RBF) networks. More specifically, it is shown that an important large class of classification problems involving signals can be solved using a structure consisting of only a generalized RBF network followed by a quantizer. It is also shown that Gaussian radial basis functions defined on ⁿ can uniformly approximate arbitrarily well over all of ⁿ any continuous real functionalf on ⁿ that meets the condition that |f(x)|0 as x.     

Symmetry relations in multidimensional Fourier transform pairs

A relation between the types of symmetries that exist in signal and Fourier transform domain representations is derived for continuous as well as discrete domain signals. The symmetry is expressed by a set of parameters, and the relations derived in this paper will help to find the parameters of a symmetry in the signal or transform domain resulting from a given symmetry in the transform or signal domain respectively. A duality among the relations governing the conversion of the parameters of symmetry in the two domains is also brought to light. The application of the relations is illustrated by a number of two-dimensional examples.Notation R the set of real numbers - R ^m R × R × ... × R m-dimensional real vector space - continuous domain real vector - L {¦ – _i , i = 1,2,..., m} - m-dimensional frequency vector - W { – _i ,i=1,2,..., m} - m-dimensional normalized frequency vector - _P {¦ – _i , i=1,2,...,m} - g(ol) g (₁,₂,..., _m ) continuous domain signal - () ( _{1 2},..., _m )=G (j ₁,j ₂,..., j _m ) Fourier transform ofg (ol) - (A,b,,,) parameters ofT- symmetry - N the set of integers - N ^m N × N × ... × N m-dimensional integer vector spacem-dimensional lattice - h(n) h (n ₁,.,n _m ) discrete domain signal - H() Fourier transform ofh (n) - v ₁,v ₂,..., v_m m sample-direction and interval vectors - V (v ₁ v ₂ ...v _m ) sampling basis matrix - [x]^* complex conjugate ofx - detA determinant ofA - X {x¦ – x _i , i=1,2,..., m} - A ^–t [A ^–1] ^t ,t stands for transpose This work was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant A-7739 to M. N. S. Swamy and in part by Tennessee Technological University under its Faculty Research support program to P. K. Rajan.     

Finite-Memory Systems

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

Using a WLFSR to Embed Test Pattern Pairs in Minimum Time

We propose a methodology for reducing the number of test cycles needed by a Weighted LFSR (WLFSR) to reproduce a 2P × W test matrix T of P pattern pairs. The methodology introduces a very small number of extra cells into the WLFSR and uses appropriate combinational mapping logic in order to make the time be equal to that required by a (W + )-bit WLFSR to generate vectors containing the W bits of the first pattern for each pair plus the extra bits. We present an algorithm that makes the value of be less than or equal to log₂, where is the size of the maximum subset of pairs in T with identical first patterns. This is a significant improvement over the time E _P,W · P required by a trivial approach that uses a WLFSR with W cells to generate the first patterns of the pairs and a P × W ROM to store the second patterns of the pairs. Experimental results on the application of the methodology to the embedding of test matrices for path delay faults are particularly encouraging, even for very large numbers of test pattern pairs that are necessary for provably high fault coverage.     

The discrete Einstein relation

In this paper the connection between massM, resistance and commute time for random walks on graphs is further explored, and the relation=2M · is proved. An extension of the result is made to multigraphs, which are an extension of the graph concept where a black box is treated like an edge.     

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 Low-Power Block-Matching Cell for Video Compression

This paper describes theimplementation of a block-matching modulewith digital I/O. Algorithmic analysisdemonstrates that the precisionrequirements can be met by a compactcircuit that processes the signal in thecharge domain. The required conversionbetween voltages and charges is achieved byMOS capacitors. As a result, it can befabricated by any inexpensive digital CMOStechnology. A test chip has beenimplemented in a standard CMOS 1.6 mtechnology and the measured energyconsumption is 1.2 nJ per block match usingan pixel matrix. Simulations ofthe same cell in 0.35 m and 0.25 mCMOS technology are presented, showing thescalability of the approach.     

Surface-Photovoltage Measurement of Volume Electron Lifetime in p-Si Wafers

The problem of estimating the volume lifetime _v of minority carriers in p-type Si wafers by surface-photovoltage measurements is addressed. An experiment is conducted in order to ascertain the relationship between measured and actual values of _v. The measurements are carried out on circular specimens whose thickness is reduced from about 2000 to 450 m by stepwise etching. The specimens are cut from a Czochralski-grown rod, their actual values of _v ranging from 10 to 300 s. The surface recombination rate of minority carriers is determined on both sides of the specimens covered with native oxide, the sides differing in surface finish. The results of the experiment allow one to determine _v up to about 400 s.     

Parametric toeplitz systems

This paper investigates the properties of the two-variable polynomialu (, z) built on the first column of the adjoint matrix ofI -C, whereC is a given Hermitian Toeplitz matrix. In particular, the stability properties ofu (,z) are discussed and are shown to depend essentially on the location of X with respect to the eigenvalues ofC. The eigenvectors ofC, which have recently found some applications in signal processing and estimation theory, are obtained from the polynomialu(,z) when tends to the eigenvalues ofC. This allows one to derive several results concerning the eigenpolynomials, including those for the case of multiple eigenvalues.     

On the design of feedback controllers to achieve prescribed initial value constraints

The problem of designing a stabilizing compensator for a control system to achieve prescribed initial value constraints ⁽ⁱ⁾(0⁺)=y_i is considered. Indeed, modulo certain technical conditions, such a compensator exists if and only if y_i=0;i= 0,1,...,rp +rt –2; whererp is the relative degree of the plant andrt is the relative degree of the system input. This theorem is derived and a complete parameterization of the set of compensators that achieve the prescribed design constraints is formulated.This research was supported in part by NSF Grant No. 921106.     

Estimation of Energy Aliasing Error for Nonbandlimited Signals

In this paper, we investigate the problem of approximating a given (not necessarily bandlimited) signal, x(t), by a (bandlimited) interpolation or sampling series of the form:

Detection of Defects Using Fault Model Oriented Test Sequences

This paper analyzes the possibilities and limitations of defect detection using fault model oriented test sequences. The analysis is conducted through the example of a short defect considering the static voltage test technique. Firstly, the problem of defect excitation and effect propagation is studied. It is shown that the effect can be either a defective effect or a defect-free effect depending on the value of unpredictable parameters. The concept of Analog Detectability Interval (ADI) is used to represent the range of the unpredictable parameters creating a defective effect. It is demonstrated that the ADIs are pattern dependent. New concepts (Global ADI, Covered ADI) are then proposed to optimize the defect detection taking into account the unpredictable parameters. Finally, the ability of a fault oriented test sequence to detect defect is discussed. In particular, it is shown that the test sequence generated to target the stuck-at faults can reasonably guarantee short defect detection till a limit given by the Analog Detectability Intervals.     

Optical-LSP Establishment and a QoS Maintenance Scheme Based on Differentiated Optical QoS Classes in OVPNs

A virtual private network (VPN) over Internet has the benefit of being cost-effective and flexible. However, it has difficulties providing sufficient QoS and adequate transmission capacity for high bandwidth services. Given the increasing demand for high bandwidth Internet and the demand for QoS assurances in a VPN over Internet, IP/generalized multi-protocol label switching (GMPLS) based on a control plane combined with a high-bandwidth, dense-wavelength division multiplexing (DWDM) optical network is seen as a very favorable approach for realizing the future optical VPN (OVPN) over IP/GMPLS over DWDM. Within this architecture, providing QoS guaranteed multimedia services with a differentiated QoS guaranteed protocol framework with QoS recovery is one of the key issues to implement. Therefore, we suggest in this paper optical-label switched path (O-LSP) establishment and its QoS maintenance scheme based on differentiated optical QoS-service (DOQoS) classes. They are the key components for this DOQoS framework in assuring end-to-end QoS in an OVPN over IP/GMPLS over DWDM architecture.     

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

Efficient,perfect polynomial random number generators

Let N be a positive integer and let P [x] be a polynomial that is nonlinear on the set _N of integers modulo N. If, by choosing x at random in an initial segment of _N , P(x) (mod N) appears to be uniformly distributed in _N to any polynomial-time observer, then it is possible to construct very efficient pseudorandom number generators that pass any polynomial-time statistical test. We analyse this generator from two points of view. A complexity theoretic analysis relates the perfectness of the generator to the security of the RSA-scheme. A statistical analysis proves that the least-significant bits of P(x) (mod N) are statistically random.This research was performed while C. P. Schnorr was visiting the Department of Computer Science of the University of Chicago, who also supported his research. A U.S. patent, based on this work, has been granted.