Institute for Systems Research Technical Reports
Permanent URI for this collectionhttp://hdl.handle.net/1903/4376
This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.
Browse
9 results
Search Results
Item Design, Implementation and Testing of an 8x8 DCT Chip(1989) Sachidanandan, S.; JaJa, J.; ISRAn implementation of a fully pipelined bit serial architecture to compute the 2-D Discrete Cosine Tranform of an 8x8 element matrix is presented. The algorithm used requires the minimal number of multipliers to perform the computation. The basic hardware components required by our implementation are the one bit serial adder, one bit serial subtractor, one bit pipeline multiplier and the dynamic shift register. We use two's complement arithmetic. An internal precision of 18 bits is maintained throughout the chip. We have used the two phase non-overlapping clocking scheme. The basic architecture consists of an 1-D ROW DCT followed by a TRANSPOSE operation and another 1-D COLUMN DCT. All the components were custom designed and simulated at various levels. The chips were laid out using the layout editor MAGIC and were fabricated by MOSIS. The chips were tested using the IMS Logic Master. The results of the simulation and testing are also presented here. The throughput is very high and inputs can be processed successively with no delay and just two controls. The chip is designed to operate at clock speeds of 10Mhz or more.Item Parallel Algorithms for Several VLSI Routing Problems(1988) Chang, Shin-Chong; JaJa, Joseph; ISRAbstract's technical formulas were not compatible with the database used to create this booklet. To obtain a copy, please contact Maggie Virkus at (301) 454-6167, maggie@ra.src.umd.edu or write at to the Center's address listed in the front of this booklet.Item Asymptotic Nonlinear Filtering and Large Deviations with Application to Observer Design(1988) James, Matthew R.; Baras, J.; ISRAn important problem in control theory is the design of observers for nonlinear control systems. By observer we mean a deterministic dynamical system which uses observed information to compute an estimate of the state of the control system in such as way that the error decays to zero. Baras and Krishnaprasad have proposed that an observer design might result from a study of an asymptotic nonlinear filtering problem obtained by adding small noise terms to the equations defining the control system. The purpose of this thesis is to study this asymptotic filtering problem and to develop observer designs based on their idea. Asymptotic nonlinear filtering problems have been studied by several authors, and are closely related to large deviations (Wentzell-Freidlin theory). We prove using vanishing viscosity and control theoretic methods a logarithmic limit result for solutions of the Zakai equation. This limit is characterized by a Hamilton-Jacobi equation which, as noted by Hijab, arises in Mortensen's deterministic minimum energy estimation. We make a careful study of this equation in the light of the relatively recent theory of viscosity solutions due to Crandall and Lions. We study the weak limit of the conditional measures and filter. Inspired by Hijab's large deviation result for pathwise conditional measures, we obtain a large deviation principle "in probability" for the conditional measures, and also a large deviation principle for the distributions of these measures. This asymptotic analysis suggests that the limiting filter is a candidate observer. We present an exact infinite dimensional observer for uncontrolled observable systems. In the case of uncontrolled nonlinear dynamics and linear observations, Bensoussan obtained a finite dimensional observer which is an approximation to the limiting filter. A detectability condition was used to prove exponential decay of the error, provided the initial condition lies in a bounded region. We extend his approach to the general case of controlled nonlinear dynamics and nonlinear observation. In particular, we obtain an observer for a class of fully nonlinear systems with no constraints on the initial conditions. The Benes case is considered.Item Bayesian Sequential Hypothesis Testing(1987) MacEnany, David C.; Baras, J.; ISRIn this thesis, optimality results are presented for Bayesian problems of sequential hypothesis testing. Conditions are iven which are sufficient to demonstrate the existence and optimality of threshold policies and others are given which help characterize these policies. The general results are applied to solve four specific problems where the observations respectively arise from a time-homongeneous diffusion, a progressive semimartingale observed through a diffusion, a time-homogeneous Poisson process, and a predictable semimartingale observed through a point process. It is shown that threshold policies are optimal in all four cases. Exact formulas for the Bayesian costs in the point process cases will be presented for the first time.Item Efficient Algorithms for Circular-Arc Containment Graphs(1987) Nirkhe, M.V.; Nakajima, K.; ISRIn the recent past, a wide variety of algorithms have been developed for a class of intersection graphs, called interval graphs. As a generalization of interval graphs, circular-arc graphs have also been studied extensively. Another category of graphs, namely containment graphs, has recently received some attention. In particular, interval containment graphs have been studied recently and several optimal algorithms have been developed for this class of graphs. In this thesis we introduce a new class of containment graphs called circular-arc containment graphs. A circular-arc containment graph is a generalization of an interval containment graph and is defined as follows: A graph G sub A = (V sub A, E sub A) is called a ciruclar-arc containment graph for a family A = {A sub 1, A sub n} of arcs on a circle, if for each v sub i V sub A, there is an arc A sub i A, and (v sub i, v sub j) E sub A if and only if one of A sub i and A sub j contains the other. We characterize this class of graphs by establishing its equivalence to another relatively new class of intersection graphs, called circular permutation graphs. Given a circular-arc containment graph in the form of a family of arcs on a circle, we develop efficient algorithms for finding a maximum clique, a maximum independent set, and a minimum coloring of the graph.Item Asymptotic Behavior in Nonlinear Stochastic Filtering(1987) Saydy, L.; Blankenship, G.L.; ISRA lower and upper bound approach on the optimal mean square error is used to study the asymptotic behavior of one dimensional nonlinear filters. Two aspects are treated: (1) The long time behavior (t Ġ. (2) The asmptotic behavior as a small parameter Ġ0. Lower and upper bounds that satisfy Riccati equations are derived and it is shown that for nonlinear systems with linear limiting systems, the Kalman filter designed for the limiting systems is asymptotically optimal in a reasonable sense. In the case of nonlinear systems with low measurement noise level, three asymptotically optimal filters are provided one of which is linear. In chapter 4, the stationary behavior of the Benes filter is investigated.Item Order Determination for Probabilistic Functions of Finite Markov Chains(1987) Finesso, Lorenzo; Baras, John S.; ISRLet {Y sub t} be a stationary stochastic process with values in the finite set YY. We model {Y sub t} as a probabilistic function of a finite state Markov Chain {X sub t} i.e. X sub t is such that: P[Y sub t | X sup t, Y sup t-1] = P[Y sub t | X sub t] Define the cardinality of the state space of {X sub t} as the order of the model. The problem is to determine the order given the observations {y sub 1, y sub 2, y sub T}. We show that under mild conditions on the probability distribution function P sub Y (.) of {Y sub t} the order is identifiable and can be consistently determined from the data.Item Using Computer Algebra for Design of Nonlinear Control Systems(1987) Akhrif, O.; Blankenship, G.; ISRA rich collection of analytical tools based on differential geometric methods has been developed for the analysis and design of nonlinear control systems. The concept of feedback equivalence among nonlinear systems is used to linearize and control certain classes of nonlinear control systems. The left and right invertibility of nonlinear systems is used to solve the output tracking problem. Using computer algebra programming methods, a software system has been developed which makes these analytical procedures available to users who need not have an extensive knowledge of differential geometry. Examples of the use of this system are reported.Item Via Minimization for IC and PCB Layouts(1987) Naclerio, N.J.; Nakajima, K.; ISRIn the design of integrated circuits (ICs), it is important to minimize the number of vias between conductors on different layers since excess vias lead to decreased yield and degraded circuit performance. Similarly, in the design of printed circuit boards (PCBs), it is important to minimize the number of contact holes used to connect copper strips on opposite sides of the board. Excess contact holes increase manufacturing cost and decrease the board's reliability. Given a particular design of an IC (or PCB), the Constrained Via Minimization Problem is to find a layer assignment that requires the fewest possible vias (or contact holes). It is shown that this problem is NP-hard for two- layer layouts and remains so when the layout is restricted to be grid-based, vias are restricted to lie at previously existing junctions, and the maximum number of wires which are joined at any particular junction does not exceed six. A new graph- theoretic formulation of the two-layer problem is then presented along with an algorithm which yields optimum results when the maximum junction degree is limited to three. The worst-case time complexity of the algorithm is O (n sup 3) where n is the number of routing segments in the given layout. Unlike previous algorithms, this algorithm does not require the layout to be grid based and places no constraints on the location of vias or the number of wires that may be joined at a single junction. If there are junctions with degree exceeding three, then our solution may be slightly less then optimum. If vias are limited to a subset of all possible via sites such as those allowable by a particular set of geometric design rules, then a further speedup is possible. This algorithm has been fully implemented. When tested on examples from the literature, it was found to be faster than the existing heuristic algorithms. A new heuristic is also suggested that is based on properties of the optimum solutions which were generated by this algorithm.