The prime and generalized nullspaces of right regular pencils

The classical notion of the -generalized nullspace, defined on a matrixA R ^n×n,where is an eigenvalue, is extended to the case of ordered pairs of matrices(F, G), F, G R ^m×nwhere the associated pencilsF – G is right regular. It is shown that for every C {} generalized eigenvalue of (F, G), an ascending nested sequence of spaces {P ⁱ ,i=1, 2,...} and a descending nested sequence of spaces {ie495-02 i=1, 2,...} are defined from the -Toeplitz matrices of (F, G); the first sequence has a maximal elementM ^* , the -generalized nullspace of (F, G), which is the element of the sequence corresponding to the index , the -index of annihilation of (F, G), whereas the second sequence has the first elementP ^* as its maximal element, the -prime space of (F, G). The geometric properties of the {M ⁱ ,i=1, 2,..., and {P ⁱ ,i=1, 2,...sets, as well as their interrelations are investigated and are shown to be intimately related to the existence of nested basis matrices of the nullspaces of the -Toeplitz matrices of (F, G). These nested basis matrices characterize completely the geometry ofM ^* and provide a systematic procedure for the selection of maximal length linearly independent vector chains characterizing the-Segre characteristic of (F, G).     

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.     

Input-output systems whose transmission operators furnish nearly best approximations to a given map

Let {S(A):A A}, whereA is a subset of an infinite-dimensional normed linear spaceL, be a class of general nonlinear input-output systems that are governed by operator equations relating the input, state, and output, all of which are in extended spaces. IfQ is a given operator from a specified set ¯D _i, of inputs into the space of outputs ¯H ₀, the problem we consider is to find, for a given >0, a parameterA A such that the transmission operatorR(A ) ofS(A ) furnishes a nearly best (or -best) approximation toQ from allR(A),A A. Here the distance betweenQ andR(A) is defined as the supremum of distances betweenQz andR(A)z taken over allz ¯D _i. In Theorems 2 through 5 we show that ifS(A) is normal (Definition 2),A satisfies some mild requirement andL contains a fundamental sequence, then establishingA A reduces to minimizing a certain continuous functional on a compact subset ofR ⁿ, and thus can be carried out by conventional methods. The applications of results are illustrated by the example of a model-matching problem for a nonlinear system, and of optimal tracking.     

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.     

An efficient characterization of some cost allocation solutions associated with capacitated network design problems

We analyze some game-theoretic solution concepts associated with a cost allocation problem arising from the Capacitated Network Design (CND) problem. The problem is formulated as a cost cooperative game in characteristic function form to be referred to as the CND game. We provide an efficient representation of several game-theoretic solution concepts associated with the CND game. In particular, we efficiently characterize the core, and in some cases the nucleolus, the least weighted-core and a certain central point in the least weighted-core. Our model properly generalizes several previously studied cooperative games. We also employ our model to analyze cost allocation problems associated with several classes of network design problems, which were not previously studied in the literature. Specifically, we efficiently characterize the above cost allocation solutions for cost allocation problems associated with the Capacitated Concentrator Location problem, the Capacitated Minimum Spanning Tree problem, the Capacitated Fixed Cost Spanning Forest problem, and the Capacitated Steiner Tree problem.     

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.     

Permittivity and Conductivity Measurements of Building Materials at 5.8 GHz and 41.5 GHz

The results of various experiments performed to characterize electromagnetic properties of typical building materials at BRAN (Broadband Radio Access Networks) and MVDS (Multipoint Video Distribution System) bands are presented and compared. Transmission and reflection coefficients were measured as functions of the angle of incidence, using a wideband sounder based on the swept frequency technique. A high precision angular positioning system was built and used in co-ordination with the measurement equipment.The dielectric constants (_r) were estimated by comparing values predicted with a multiple successive internal reflection model and measured transmission and reflection coefficients. It has been found that the variation of the dielectric constant value with the frequency does not necessarily follow the same trend for different materials. For example, the measured _r for plasterboard presents an increment withfrequency (2.02 at 5.8 GHz, 2.5 at 41.5 GHz – measured by theauthors –, 2.58 at 59.5 GHz, and 2.81 at 60.2 GHz – given byliterature –), while the values for glass follow a wanderingpattern (6.06 at 5.8 GHz, 5–10 at 10 GHz, 3.41 at 41.5 GHz, 7.51at 57.6 GHz, and 5.29 at 60.2 GHz). Moreover, the measured_r for a brick wall at 5.8 GHz (3.58) shows differenceswith values reported at 2 GHz (4.44).     

Pervasive Home Environments

For decades, technologists have been promising the intelligent house. The vision is usually portrayed as a house filled with technology which will do the dweller's bidding and take all domestic drudgery out of their lives. The truly intelligent house is still some way off, but the emergence of broadband, availability of faster, smaller and ever cheaper computing equipment and a variety of wired and wireless network technologies are enabling technologies that bring this vision closer to reality. These technology trends lead to the concept that computing and other smart devices will become pervasive, fully networked and disappear into the infrastructure of the home. People will carry out their tasks unaware of the complexity of the infrastructure that supports their activities in much the same way as people today use mains electricity.This paper introduces these concepts and discusses the technological challenges to be overcome. We present our vision of the pervasive home environment where inhabitants can focus on tasks rather than the technology: I need to create X and send it to Y rather than I need to use this computer and this application which needs access to service A and resource B. Although this sounds simple, the environment needs to understand who I is, and who or what Y is. Appropriate permissions must be in place and resources allocated, if available. The most appropriate interface for the task and user must be determined.The pervasive, intelligent home will make available new ways to access and share information. It will herald new services, such as care and support of people in the home, entertainment, educational and security services. The final part of the paper discusses the commercial opportunities and challenges which must be met, not least the need for industry to agree on open standards and interfaces.     

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.     

High Dynamic Range Design for ΣΔM with Wide Input Ranges

A new design algorithm is introduced to improve the input ranges of Sigma-Delta Modulation (M). Modified digital error correction techniques are proposed and employed to carry out the wide range DAC of a modulator. This design algorithm includes the advantages from both single-bit M and multi-bit M. This paper utilizes a second order lowpass modulator as an explanatory example to demonstrate our design process as well as the performance improvement. The analytical results from a quasilinear model are described to offer a theoretical explanation of the system performance. This algorithm can also be applied to bandpass and MASH architectures.     

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.     

Editorial

Future integrated microsystems will benefit significantlyfrom progress in the VLSI field. Two key elements will boostthe implementation of new micro-integrated architectures: progressin batch-manufactured silicon sensors and the introduction ofnew circuit techniques for designing interface circuits. Thesetwo factors will be essential in favoring the transition fromthe present research driven speculations to customer drivenactivities. This paper discusses the key issues in realizingmicrosensors and the most suitable circuit techniques for interfacingand processing their output signals. A number of examples ofintegrated structures will illustrate present problems and possiblesolutions.     

Factorizations in the elementary Abelian p-group and their cryptographic significance

Let G be a finite group and let A _i 1 i s, be subsets of G where ¦A _i ¦ 2, 1 i s and s 2. We say that (A₁, A₂,..., A₃) is a factorization of G if and only if for each g G there is exactly one way to express g = a ₁ a ₁ a ₂··· a ₃, where a _j A _i , 1 i s.The problem of finding factorizations of this type was first introduced by Hajos [3] in 1941. Since then a number of papers have appeared on the subject. More recently, Magliveras [6] has applied factorization of permutation groups to cryptography to obtain a private-key cryptosystem. Factorizations in the elementary abelian p-group were exploited (but not explicitly stated in these terms) by Webb [13] to produce a public-key cryptosystem conceptually similar to cryptosystems based on the knapsack problem.Using the result that certain types of factorizations in the elementary abelian p-group are necessarily transversal (a term introduced by Magliveras), this paper shows that the public-key system proposed by Webb is insecure.     

The Structure of Complex Thin-Film Systems from Ellipsometric Simulation: A PbI2–Cu Photoresist

It is shown that the structure of complex thin-film systems can be studied ellipsometrically. In the ellipsometric method used in this work, the distribution of the rf permittivity (z) across the depth is simulated within models of uniform layers and linearly nonuniform layers. Difficulties associated with finding the ellipsometric parameters for a reflecting system with nonuniformly distributed (z) are considered. It was demonstrated that vacuum deposition of PbI₂–Cu thin-film inorganic photoresist causes the transition layer to form at the Cu/PbI₂ interface due to copper penetrating into the interface region of PbI₂. The parameters of this layer correlate with the PbI₂ film porosity.     

A Fourth Order Bandpass Delta-Sigma Modulator with Digitally Programmable Passband Frequency

The design and implementation of a fourth order switched-capacitorbandpass delta-sigma modulator with digitally programmable passbandis described. The quantization noise null can be programmed from0.4 (0.2f_s) to 0.6(0.3f_s) in steps of 0.01 (f_s/200)by changing digital switch settings. This design enables theA/D conversion of a bandpass signal with digital tuning of thecenter frequency for application in systems such as a transceiverIF stage. The modulator IC measures 4.8mm² in a2µ m CMOS process and achieves an SNR of 47 and59 dB over a 0.01 bandwidth at sampling ratesof 2.358 MHz and 1.25 MHz, respectively.     

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.     

Year 2000 — a Sytems Integration challenge

BT, along with virtually every other IT-dependent business worldwide, is tackling a problem which is quite unique and if not corrected could be disastrous. The problem, sometimes known as the Year 2000 bug or millennium time bomb, has been caused by the use of two digits to represent the year in the majority of our systems and applications. The problem is technically not difficult to fix but the volume of changes occurring, and the need to potentially test every system to ensure that it is year 2000 proof, presents unique and challenging difficulties for integration and testing. Why this is the case, what problems need to be addressed, and an overview of some of the proposed integration and test strategies to tackle these problems, is the subject of this paper.     

CBC MACs for Arbitrary-Length Messages: The Three-Key Constructions

We suggest some simple variants of the CBC MAC that enable the efficient authentication of arbitrary-length messages. Our constructions use three keys, K1, K2, K3, to avoid unnecessary padding and MAC any message M {0,1}* using max{1, |M|/n} applications of the underlying n-bit block cipher. Our favorite construction, XCBC, works like this: if |M| is a positive multiple of n then XOR the n-bit key K2 with the last block of M and compute the CBC MAC keyed with K1; otherwise, extend Ms length to the next multiple of n by appending minimal 10 padding ( 0), XOR the n-bit key K3 with the last block of the padded message, and compute the CBC MAC keyed with K1. We prove the security of this and other constructions, giving concrete bounds on an adversarys inability to forge in terms of his inability to distinguish the block cipher from a random permutation. Our analysis exploits new ideas which simplify proofs compared with prior work.     

On the robustness of stability for uncertain large-scale systems subjected to multiple time delays

The robustness problem of stability for large-scale uncertain systems with a class of multiple time delays is addressed in this paper. By applying the complex Lyapunov stability theorem, the matrix measure techniques, and norm inequalities, a new approach for solving a general case of the above problem is proposed. Several robust stability conditions, delay-dependent or delay-independent, are derived to guarantee the asymptotic stability and exponential stability of the uncertain large-scale time-delay systems. Moreover, these obtained results can also be applied to the stabilization design.Notation real number field - complex number field - x x=(x ₁,x ₂,...,x _n ) ^T R ⁿ - x ^T transpose of vectorx - x* complex conjugate transpose of vectorx - Re(·) real part of (·) - x norm of vectorx; x=(x*x)^1/2 - A ^T transpose of matrixA - A* complex conjugate transpose of matrixA - ¯(·) maximal absolute value of eigenvalue of matrixA - (A) matrix measure of matrixA; (A)=¯((A + A*)/2) - A induced norm of matrix A; A=[¯(A*A)]^1/2 - ¦a_ij ¦ absolute value of element a_ij - ¦ A¦ {¦a_ij¦} for matrix A={a_ij} - A >B a_ij > b_ij for alli andj where A={a_ij} andB={b_ij} - z complex number - ¯z complex conjugate ofz Supported by National Science Council, Taiwan, Republic of China, Grant NSC83-0404-E006-001.     

A Direct Digital Synthesizer with Tunable Delta Sigma Modulator

In direct digital synthesizer (DDS) applications, the drawback of the conventional delta sigma () modulator structure is that its signal band is fixed. In the new architecture presented in this paper, the signal band of the modulator is tuned according to the DDS output frequency. We use a hardware efficient phase-to-sine amplitude converter in the DDS that approximates the first quadrant of the sine function with sixteen equal length second degree polynomial segments. The DDS is capable of frequency, phase, and quadrature amplitude modulation. Two DDSs with tunable 1-bit D/A converters (real and complex) were designed and implemented on a programmable logic device (PLD); experimental results show their desired operation and performance.