On the structure of the privacy hierarchy

An N argument function f(x ₁,...,x _N ) is called t-private if a protocol for computing f exists so that no coalition of at most t parties can infer any additional information from the execution, other than the value of the function. The motivation of this work is to understand what levels of privacy are attainable. So far, only two levels of privacy are known for N argument functions which are defined over finite domains: functions that are N-private and functions that are (N – 1)/2-private but not N/2-private.In this work we show that the privacy hierarchy for N-argument functions which are defined over finite domains, has exactly (N + 1)/2 levels. We prove this by constructing, for any N/2 t N – 2, an N-argument function which is t-private but not (t + 1)-private.This research was supported by US-Israel Binational Science Foundation Grant 88-00282.     

β-bit serial/parallel multipliers

A generalized -bit least-significant-digit (LSD) first, serial/parallel multiplier architecture is presented with 1n wheren is the operand size. The multiplier processes both the serial input operand and the double precision product -bits per clock cycle in an LSD first, synchronous fashion. The complete two's complement double precision product requires 2n/ clock cycles. This generalized architecture creates a continuum of multipliers between traditional bit-serial/parallel multipliers (=1) and fully-parallel multipliers (=n). -bit serial/parallel multipliers allow anoptimized integrated circuit arithmetic to be designed based on a particular application's area, power, throughput, latency, and numerical precision constraints.This project was pratically funded by the UCSD-NSF I/UCR Center on Ultra-High Speed Intergrated Circuits and Systems.     

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.     

Higher-order terms in asymptotic expansion for information loss in quantized random processes

Uniform quantization of random vectors onto -grids ⁿ is considered. Higherorder terms in asymptotic expansions for the entropy of the -quantized random vector and for the loss of the mutual information between two random vectors under such quantization as 0+are obtained. The coefficients in these asymptotics are explicitly calculated for Gaussian distributed vectors. Taken for initial segments of stationary Gaussian sequences, these factors have limit average values per unit of time. For such sequences governed by state-space equations, computation of these average values is reduced to solutions of algebraic matrix Riccati and Lyapunov equations.Work supported by the Australian Research Council grant A 4970 2246.     

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.     

On the distribution of characteristics in bijective mappings

Differential cryptanalysis is a method of attacking iterated mappings based on differences known as characteristics. The probability of a given characteristic is derived from the XOR tables associated with the iterated mapping. If is a mapping : Z ₂ ^m , then for each , X, Y Z ₂ ^m the XOR table for gives the number of input pairs of difference X=X+X for which gp(X)+(X)=Y.The complexity of a differential attack depends upon two properties of the XOR tables: the density of zero entries in the table, and the size of the largest entry in the table. In this paper we present the first results on the expected values of these properties for a general class of mappings . We prove that if : Z ₂ ^m Z ₂ ^m is a bijective mapping, then the expected size of the largest entry in the XOR table for is bounded by 2m, while the fraction of the XOR table that is zero approaches e ^–1/2=0.60653. We are then able to demonstrate that there are easily constructed classes of iterated mappings for which the probability of a differential-like attack succeeding is very small.The author is presently employed by the Distributed System Technology Center, Brisbane, Australia.     

Parallel sums and norm convergence

LetA andB be the impedance operators of two resistive Hilbert ports. Then theparallel sum ofA andB, denotedA: B, is defined to be the joint impedance of the parallel interconnection ofA andB. We survey some results about the norm convergence of lim₀(A+I): (B+I). By means of several new examples, we investigate the relation between such norm convergence and range inclusion conditions.     

On the convergence rate ofs-numbers of compact Hankel operators

It is well known that the sequence ofs-numbers {s_n},n=0, 1,..., of a compact operator, and particularly a compact Hankel operator =[h _j+k –1], converges monotonically to zero. Since the (n + 1)sts-number s_n measures the error ofL (¦z¦=1) approximation, modulo an additive H function, by nth degree proper rational functions whose poles are restricted to ¦z¦ < 1, it is very important to study how fast {s _n } converges to zero. It is not difficult to see that ifh _n =O(n ^–), for some > 1, thens _n =O(n ^–). In this paper we construct, for any given sequence _n 0, a compact Hankel operator such thats _{n n} for alln.The research of C. K. Chui was supported by the SDIO/IST managed by the U.S. Army under Contract No. DAAL-03-87-K-0025, and by the NSF under Grant No. DMS-8901345. X. Li's research was supported by the SDIO/IST managed by the U.S. Army under Contract No. DAAL-03-87-K-0025. The research of J. D. Ward was supported by the NSF under Grant No. DMS-8901345.     

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

A new algorithm to compute the discrete inverse radon transform

The aim of this paper is to compute the discrete inverse Radon transform over ⁿ . The Radon transform is a function with domainS ^n–1×. It is shown that under different measure this function can be defined with domain ⁿ . In this case one can compute the discrete inverse Radon transform in the Cartesian coordinate system without interpolating from polar to Cartesian coordinates or using the backprojection operator.     

Systematic Width-and-Length Dependent CMOS Transistor Mismatch Characterization and Simulation

This paper presents a methodology for characterizing the random component of transistor mismatch in CMOS technologies. The methodology is based on the design of a special purpose chip which allows automatic characterization of arrays of NMOS and PMOS transistors of different sizes. Up to 30 different transistor sizes were implemented in the same chip, with varying transistors width W and length L. A simple strong inversion large signal transistor model is considered, and a new five parameters MOS mismatch model is introduced. The current mismatch between two identical transistors is characterized by the mismatch in their respective current gain factors /, V _TO threshold voltages , bulk threshold parameters , and two components for the mobility degradation parameter mismatch ₀ and _e. These two components modulate the mismatch contribution differently, depending on whether the transistors are biased in ohmic or in saturation region. Using this five parameter mismatch model, an extraordinary fit between experimental and computed mismatch is obtained, including minimum length (1 m) transistors for both ohmic and saturation regions. Standard deviations for these five parameters are obtained as well as their respective correlation coefficients, and are fitted to two dimensional surfaces f(W, L) so that their values can be predicted as a function of transistor sizes. These functions are used in an electrical circuit simulator (Hspice) to predict transistor mismatch. Measured and simulated data are in excellent agreement.     

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.     

Some properties of order-Statistics filters

LetX ₁,X ₂,... be a stationary sequence of random variables with Pr{X _t, x}=F(x),t=1, 2,... Also let _i ^n,(t) ,i=1,...,n, denote the ith order statistic (OS) in the moving sample (X _t–N ,...,X _t,...,X _t+N) of odd sizen=2N+1. ThenY _t=a _i X _i ^n(t) with a _i=1 is an order-statistics filter. In practicea _i0,i=1,...,n. Fort>N, the sequence {Y _t} is also stationary. IfX ₁ X ₂, ... are independent, the autocorrelation function (r)=corr(Y _t,Y _t+r) is zero forr >n – 1 and forr n – 1 can be evaluated directly in terms of the means, variances, and covariances of the OS in random samples of sizen +r fromF(x).In special cases several authors have observed that the spectral density functionf() of {Y _t} is initially decreasing for > 0. This result is made more precise and shown to hold generally under white noise. The effect of outliers (impulses) is also discussed.This research was supported by the U.S. Army Research Office.     

Distance of a complex coefficient stable polynomial from the boundary of the stability set

In this paper, the distance in the 1 2p norm from a complex coefficient polynomial to the border of its Hurwitz region is analyzed. Simplified expressions for 2p=1, 2, are also obtained.This work was supported in part by Comisión Investigaciones Cientificas de la Provincia de Buenos Aires (CIC) and Comisión Nacional de Investigaciones Cientificas y Técnicas (CONICET).     

The significance of finite buffer edge effects in histogram measurements of queues

The empirically oberved fractal or self-similar nature of packet traffic implies heavy tailed queue processes for such traffic. However, based on our simulation analysis using real network data as well as standard models, we have found that the actual losses sustained are remarkably lower than those suggested by the heavy tail distribution. This can be explained by an effect observed in the tail of the histogram of a finite buffer queue process, which we call tail-raising, which contains information pertinent to performance estimation. This effect is also responsible for a significant reduction in packet losses for finite buffer systems, than would be otherwise predicted by the buffer overflow probability for heavy-tailed queues. We define a new parameter X _B on the histogram of a queue process for a finite buffer system, to calculate the tail of the queue process based on the information available in the histogram on the finite buffer. We propose an estimator that approximates X _B , namely, X _min, which is measurable because of the tail-raising effect and has a robust measurement method. The proposed estimator shows promise as a good predictor for performance metrics of queueing systems. We propose an innovative packet loss ratio estimation technique which uses histogram measurements combined with a virtual buffer scheme to find and extrapolate the objective packet loss rate using a binning strategy for histogram measurement, namely, Symmetric Logarithmic Binning (SLB).     

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.     

A Distributed Algorithm for Dynamic Channel Allocation

Recent demand for mobile telephone service has been growing rapidly while the electro-magnetic spectrum of frequencies allocated for this purpose remains limited. Any solution to the channel assignment problem is subject to this limitation, as well as the interference constraint between adjacent channels in the spectrum. Channel allocation schemes provide a flexible and efficient access to bandwidth in wireless and mobile communication systems. In this paper, we present an efficient distributed algorithm for dynamic channel allocation based upon mutual exclusion model, where the channels are grouped by the number of cells in a cluster and each group of channels cannot be shared concurrently within the cluster. We discuss the algorithm and prove its correctness. We also show that the algorithm requires at most (worst case) O(N _gN _n logN _n) messages, where N _g is the number of groups and N _n is the number of neighbors. This is compared to Choy's algorithm which requires O(N _g ²N _n), where N _g is the number of groups and N _n is the number of neighboring cells in the system. We report our algorithm's performance with several channel systems using different types of call arrival patterns. Our results indicate that significant low denial rate, low message complexity and low acquisition time can be obtained using our algorithm.     

Predictive Caching Strategy for On-Demand Routing Protocols in Wireless Ad Hoc Networks

Route caching strategy is important in on-demand routing protocols in wireless ad hoc networks. While high routing overhead usually has a significant performance impact in low bandwidth wireless networks, a good route caching strategy can reduce routing overheads by making use of the available route information more efficiently. In this paper, we first study the effects of two cache schemes, link cache and path cache, on the performance of on-demand routing protocols through simulations based on the Dynamic Source Routing (DSR) protocol. Since the path cache DSR has been extensively studied, we focus in this paper on the link cache DSR in combination with timer-based stale link expiry mechanisms. The effects of different link lifetime values on the performance of routing protocol in terms of routing overhead, packet delivery ratio and packet latency are investigated. A caching strategy incorporating adaptive link timeout is then proposed, which aims at tracking the optimal link lifetime under various node mobility levels by adaptively adjusting the link lifetime based on the real link lifetime statistics. The performance of the proposed strategy is then compared with the conventional path cache DSR. The results show that without a timeout mechanism, a link cache scheme may suffer severe performance degradation due to the use of broken routes, while the proposed adaptive link cache strategy achieves significantly improved performance by reducing the routing overhead when the network traffic load is high.     

Theory of PLL fractional-N frequency synthesizers

This paper presents an overview of the evolution of frequency synthesizers based on phase-locked loops (PLLs). The main limitations of the digital PLLs are described, and the consequent necessity of using fractional-N techniques is justified. The origin of the typical spurious noise lines on the sidelobes of the synthesized frequency is explained. It is shown how to eliminate these spurious noise lines by using digital modulators to control the frequency division value. Finally, the implications of using digital modulators together with fractional-N PLLs on the output phase noise are analysed.