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.     

Quality Determination for Gate Delay Fault Tests Considering Three-State Elements

Most industrial digital circuits contain three-state elements besides pure logic gates. This paper presents a gate delay fault simulator for combinational circuits that can handle three-state elements like bus drivers, transmission gates and pulled busses. The well known delay faults--slow-to-rise and slow-to-fall--are considered as well as delayed transitions from isolating signal state high impedance to binary states 0 and 1 and vice versa. The presented parallel delay fault simulator distinguishes between non-robust, robust and hazard free tests and determines the quality of a test. Experimental results for ISCAS85/89 benchmark circuits are presented as well as results for industrial circuits containing three-state elements.     

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.     

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.     

Geometric properties of nonlinear networks containing capacitor-only cutsets and/or inductor-only loops. Part I: Conservation laws

This paper is the first 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 differentiable manifolds. Given such a nonlinear networkN, with °₀ equal to the sum of the number of independent capacitor-only cutsets and the number of independent inductor-only loops, we establish the following: (i) circuit theoretic sufficient conditions to guarantee that the set ⁰, of equilibrium points is a ₀-dimensional submanifold of the state space ofN; (ii) circuit theoretic sufficient conditions for the condition thatN has ₀ independent conservation laws and hence that through each point of the state space ofN, there passes a codimension ₀ invariant submanifold ^* of the network dynamics; (iii) circuit theoretic sufficient conditions to guarantee that the manifolds ^* and ⁰ intersect transversely.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.     

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.     

Signal Processing for Large Bandwidth and Long Duration Waveform SAR

We first show that for some kinds of signals a bandwidth and time duration reduction technique can be used to simulate waveform distortions caused by moving targets, that is, it is correct to measure the waveform distortions at very large TB with relatively small by reducing TB and increasing while keeping TB unchanged, where T is the duration of the transmitted signal, B is the bandwidth and is the relative speed of targets. We then study the waveform distortions in SAR signals caused by moving antenna. Based on the bandwidth and time duration reduction technique, a lot of time and memory are saved in simulations. We then confirm by simulations that waveform distortions do pose problems when processing very large bandwidth and long duration SAR data using conventional SAR processing methods. Finally we propose the concepts of wideband and narrowband processing of SAR data. Models are set up for wideband and narrowband SAR data processing, and new methods are presented for reconstructing targets using the proposed models. Simulations show that the methods can improve the quality of the simulated SAR images.     

A VLSI decoder for a new type of constellations adapted to the Rayleigh Fading Channel

Diversity is the key solution to obtain efficient channel coding in wireless communications, where the signal is subject to fading (Rayleigh Fading Channel). For high spectral efficiency, the best solutions used nowadays are based on QAM constellations of 1-order diversity, associated with a binary code or a trellis coded modulation to increase the overall diversity. It has been shown that a new class of d-dimensional non-QAM constellations, named -constellations, can bring a d-order diversity without the addition of redundancy. Combined with classical coding techniques, -constellations are very efficient. However, the decoding algorithm is far more complicated for -constellations than for QAM-constellations. A sub-optimal algorithm that allows the decoding of -constellations is proposed. An example of an application for a 4 bits/Hz/s spectral efficiency with a 4-D -constellation is given. The VLSI architecture of the decoder is described. The implementation leads to 72 K gates, a binary rate of 32 Mbits/s and a BER of 10^-3 for a SNR of 14 dB.     

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.     

A method for robust stabilization

LetP(y,M) be a family of polynomials, depending on a controller parameter vector y in ⁿ⁺¹, defined as follows: a family of interval matrices, and y in ⁿ⁺¹, set Given an initial stabilizing controller y⁰, this paper provides a simple method to robustify y⁰, i.e., to obtain a controller parameter vector y¹ which is more robust than y⁰. Furthermore we define the stability factort for a given robustly stable controller y, which serves as a measure of the robustness of y.     

Efficient linear-phase FIR, maximally flat error approximations for the amplitude response |1/ω r |,r,r=1, 2, 3,..., and a versatile realization

In this paper, designs of linear-phase finite impulse response (FIR) filters approximating the ideal frequency responseH (,r) |1/ ^r r=1, 2, 3,..., by using maximally flat error criteria have been proposed. Exact weights required for the realizations have been derived and are shown to be independent of the filter orderN. The suggested designs are particularly suitable for operation in the midband frequency range of 0.10–0.90 radians.     

Telepresence — the future of telephony

Opportunities for future telepresence services, creating a sense of being present at a remote location, are outlined against a backdrop of telephony as an existing, highly successful telecommunications service. In providing a context for the papers of this themed issue, key telepresence technologies, the building blocks of future services, addressing issues in audio, data, video and virtual environments are reviewed. The practical complexity of commercial telepresence applications, where developments in component multimedia technologies must be complemented by advances in integration, interface and service, is also considered. The paper concludes with a commentary on early applications and a vision of more generic future telepresence solutions — Immersive Conferencing and Persistent Communities.     

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.     

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.     

Stabilization of third-order, single-stage Sigma-Delta modulators

The issue of stability of higher-order, single-stage Sigma-Delta () modulators is addressed using a method from nonlinear system theory. As a result, theoretical bounds for the quantizer input of the modulators are derived. A new method for stabilizing the modulators is then presented. It uses the quantizer input bound for possible instability detection. Upon detection of such a state, the highest-order integrator is cut off, effectively reducing the order of the modulator, and thus resulting in a stable system. The method is easily implemented and results in a very good signal-to-noise ratio (SNR) and fast return to normal operation compared to other stabilization methods.Financial support from General Secretariat for Research and Technology of Greece under contract PENED 95/1729.     

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

Routing with multiple QoS requirements for supporting multimedia applications

Distributed multimedia applications usually require multiple QoS performance guarantees. However, in general, searching such a route in the network, to support multimedia applications, is known to be NPcomplete. In this paper, we propose a new heuristic QoS routing algorithm, called QoSR_DKS, for supporting multimedia applications in highspeed networks. QoSR_DKS is a modification of rulebased Fallback routing and Dijkstra algorithms. It can search a unicast route that would have enough network resources so that multiple QoS requirements (bandwidth, delay, and delay jitter) of the requested flow could be guaranteed. Its worst case computation time complexity is the same as that of the Dijkstra algorithm, i.e., O(V²), where V is the number of nodes in the network. Extensive simulations were done with various network sizes, upto 500 nodes networks, where each node uses Weighted Fair Queueing (WFQ) service discipline. Results show that QoSR_DKS is very efficient. It could always find the QoS satisfying route, whenever there exists one (success rate is optimal), and its average computation time is near to simple shortest path Dijkstra algorithm.     

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.     

Fault diagnosis in reconfigurable VLSI and WSI processor arrays

A systematic efficient fault diagnosis method for reconfigurable VLSI/WSI array architectures is presented. The basic idea is to utilize the output data path independence among a subset of processing elements (PEs) based on the topology of the array under test. The divide and conquer technique is applied to reduce the complexity of test application and enhance the controllability and observability of a processor array. The array under test is divided into nonoverlapping diagnosis blocks. Those PEs in the same diagnosis block can be diagnosed concurrently. The problem of finding diagnosis blocks is shown equivalent to a generalizedEight Queens problem. Three types of PEs and one type of switches, which are designed to be easily testable and reconfigurable, are used to show how to apply this approach. The main contribution of this paper is an efficient switch and link testing procedure, and a novel PE fault diagnosis approach which can speed up the testing by at leastO(V^1/2) for the processor arrays considered in this paper, where V is the number of PEs. The significance of our approach is the ability to detect as well as to locate multiple PE, switch, and link faults with little or no hardware overhead.