The Springer International Series in Engineering and Computer Science
Latest release: December 20, 2013
Series
724
Books
About this ebook series
The roots of the project which culminates with the writing of this book can be traced to the work on logic synthesis started in 1979 at the IBM Watson Research Center and at University of California, Berkeley. During the preliminary phases of these projects, the impor tance of logic minimization for the synthesis of area and performance effective circuits clearly emerged. In 1980, Richard Newton stirred our interest by pointing out new heuristic algorithms for two-level logic minimization and the potential for improving upon existing approaches. In the summer of 1981, the authors organized and participated in a seminar on logic manipulation at IBM Research. One of the goals of the seminar was to study the literature on logic minimization and to look at heuristic algorithms from a fundamental and comparative point of view. The fruits of this investigation were surprisingly abundant: it was apparent from an initial implementation of recursive logic minimiza tion (ESPRESSO-I) that, if we merged our new results into a two-level minimization program, an important step forward in automatic logic synthesis could result. ESPRESSO-II was born and an APL implemen tation was created in the summer of 1982. The results of preliminary tests on a fairly large set of industrial examples were good enough to justify the publication of our algorithms. It is hoped that the strength and speed of our minimizer warrant its Italian name, which denotes both express delivery and a specially-brewed black coffee.
Logic Minimization Algorithms for VLSI Synthesis
Book 2 · Dec 2012 ·
0.0star
The roots of the project which culminates with the writing of this book can be traced to the work on logic synthesis started in 1979 at the IBM Watson Research Center and at University of California, Berkeley. During the preliminary phases of these projects, the impor tance of logic minimization for the synthesis of area and performance effective circuits clearly emerged. In 1980, Richard Newton stirred our interest by pointing out new heuristic algorithms for two-level logic minimization and the potential for improving upon existing approaches. In the summer of 1981, the authors organized and participated in a seminar on logic manipulation at IBM Research. One of the goals of the seminar was to study the literature on logic minimization and to look at heuristic algorithms from a fundamental and comparative point of view. The fruits of this investigation were surprisingly abundant: it was apparent from an initial implementation of recursive logic minimiza tion (ESPRESSO-I) that, if we merged our new results into a two-level minimization program, an important step forward in automatic logic synthesis could result. ESPRESSO-II was born and an APL implemen tation was created in the summer of 1982. The results of preliminary tests on a fairly large set of industrial examples were good enough to justify the publication of our algorithms. It is hoped that the strength and speed of our minimizer warrant its Italian name, which denotes both express delivery and a specially-brewed black coffee.
Shadows and Silhouettes in Computer Vision
Book 3 · Mar 2013 ·
0.0star
Perceptual Organization and Visual Recognition
Book 5 · Dec 2012 ·
0.0star
COMPUTER VISION is a field of research that encompasses many objectives. A primary goal has been to construct visual sensors that can provide general-purpose robots with the same information about their surroundings as we receive from our own visual senses. This book takes an important step towards this goal by describing a working computer vision system named SCERPO. This system can recognize known three-dimensional objects in ordinary black-and-white images taken from unknown viewpoints, even when parts of the object are undetectable or hidden from view. A second major goal of computer vision re search is to provide a computational understanding of human vision. The research presented in this book has many implica tions for our understanding of human vision, particularly in the areas of perceptual organization and knowledge-based recogni tion. An attempt has been made to relate each computational result to the relevant areas in the psychology of vision. Since the material is meant to be accessible to a wide range of inter disciplinary readers, the book is written in plain language and attempts to explain most concepts from the starting position of the non-specialist. vii viii PREFACE One of the most important conclusions ansmg from this research is that visual recognition can commonly be achieved directly from the two-dimensional image without any prelim inary reconstruction of depth information or surface orienta tion from the visual input.
Robotic Grasping and Fine Manipulation
Book 6 · Dec 2012 ·
0.0star
When a person picks up a metal part and clamps it in the chuck of a lathe, he begins with his arm, proceeds with his wrist and finishes with his fingers. The arm brings the part near the chuck. The wrist positions the part, giving it the proper orientation to slide in. After the part is inserted, the wrist and fingers make tiny corrections to ensure that it is correctly seated. Today's robot attempting the same operations is at a grave disadvantage if it has to make all motions with the arm. The following work investigates the use of robotic wrists and hands to help industrial robots perform the fine motions needed in a metal working cell. Chapters 1 and 2 are an introduction to the field and a review of previous investigations on related subjects. Little work has been done on grasping and fine manipulation with a robot hand or wrist, but the related subjects of robot arm dynamics and control have an extensive literature.
Computer-Aided Design and VLSI Device Development
Book 7 · Dec 2013 ·
0.0star
This book is concerned with the use of Computer-Aided Design (CAD) in the device and process development of Very-Large-Scale-Integrated Circuits (VLSI). The emphasis is in Metal-Oxide-Semiconductor (MOS) technology. State-of-the-art device and process development are presented. This book is intended as a reference for engineers involved in VLSI develop ment who have to solve many device and process problems. CAD specialists will also find this book useful since it discusses the organization of the simula tion system, and also presents many case studies where the user applies the CAD tools in different situations. This book is also intended as a text or reference for graduate students in the field of integrated circuit fabrication. Major areas of device physics and processing are described and illustrated with Simulations. The material in this book is a result of several years of work on the implemen tation of the simulation system, the refinement of physical models in the simulation programs, and the application of the programs to many cases of device developments. The text began as publications in journals and con ference proceedings, as weil as lecture notes for a Hewlett-Packard internal CAD course. This book consists of two parts. It begins with an overview of the status of CAD in VLSI, which pointsout why CAD is essential in VLSI development. Part A presents the organization of the two-dimensional simulation system.
Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems
Book 8 · Apr 2013 ·
0.0star
Parsing Efficiency is crucial when building practical natural language systems. 'Ibis is especially the case for interactive systems such as natural language database access, interfaces to expert systems and interactive machine translation. Despite its importance, parsing efficiency has received little attention in the area of natural language processing. In the areas of compiler design and theoretical computer science, on the other hand, parsing algorithms 3 have been evaluated primarily in terms of the theoretical worst case analysis (e.g. lXn», and very few practical comparisons have been made. This book introduces a context-free parsing algorithm that parses natural language more efficiently than any other existing parsing algorithms in practice. Its feasibility for use in practical systems is being proven in its application to Japanese language interface at Carnegie Group Inc., and to the continuous speech recognition project at Carnegie-Mellon University. This work was done while I was pursuing a Ph.D degree at Carnegie-Mellon University. My advisers, Herb Simon and Jaime Carbonell, deserve many thanks for their unfailing support, advice and encouragement during my graduate studies. I would like to thank Phil Hayes and Ralph Grishman for their helpful comments and criticism that in many ways improved the quality of this book. I wish also to thank Steven Brooks for insightful comments on theoretical aspects of the book (chapter 4, appendices A, B and C), and Rich Thomason for improving the linguistic part of tile book (the very beginning of section 1.1).
An Artificial Intelligence Approach to VLSI Routing
Book 9 · Dec 2012 ·
4.0star
Routing of VLSI chips is an important, time consuming, and difficult problem. The difficulty of the problem is attributed to the large number of often conflicting factors that affect the routing quality. Traditional techniques have approached routing by ignoring some of these factors and imposing unnecessary constraints in order to make routing tractable. In addition to the imposition of these restrictions, which simplify the problems to a degree but at the same time reduce the routing quality, traditional approaches use brute force. They often transform the problem into mathematical or graph problems and completely ignore the specific knowledge about the routing task that can greatly help the solution. This thesis overcomes some of the above problems and presents a system that performs routing close to what human designers do. In other words it heavily capitalizes on the knowledge of human expertise in this area, it does not impose unnecessary constraints, it considers all the different factors that affect the routing quality, and most importantly it allows constant user interaction throughout the routing process. To achieve the above, this thesis presents background about some representative techniques for routing and summarizes their characteristics. It then studies in detail the different factors (such as minimum area, number of vias, wire length, etc.) that affect the routing quality, and the different criteria (such as vertical/horizontal constraint graph, merging, minimal rectilinear Steiner tree, etc.) that can be used to optimize these factors.
Introduction to VLSI Silicon Devices: Physics, Technology and Characterization
Book 10 · Dec 2012 ·
0.0star
There was a long felt need for this book in industrial and academic institutions. It provides new engineers, as well as practicing engineers and advanced laboratory personnel in the field of semiconductors a clear and thorough discussion of state-of-the-art silicon devices, without resorting to the complexity of higher mathematics and physics. This difficult task was made possible by detailing the explanation of equations that describe the device operation and characteristics without endeavoring their full derivation. This is reinforced by several problems which reflect practical cases observed in the laboratory. The problems are given after introducing a major equation or concept. They are arranged in the order of the text rather than in the order of difficulty. The answers to most of the problems are given in order to enable the student to "self-check" the method used for the solutions. The illustrations may prove to be of great help to "newcomers" when dealing with the characterization of real devices and relating the measured data to device physics and process parameters. The new engineer will find the book equivalent to "on the job training" and acquire a working knowledge of the fundamental principles underlying silicon devices. For the engineer with theoretical background, it offers a means for direct application of solid state theory to device analysis and synthesis. The book originated from a set of notes developed for an in-house one-year course in Device Physics, Technology and Characterization at IBM.
Universal Subgoaling and Chunking: The Automatic Generation and Learning of Goal Hierarchies
Book 11 · Dec 2012 ·
5.0star
Rarely do research paths diverge and converge as neatly and productively as the paths exemplified by the two efforts contained in this book. The story behind these researches is worth recounting. The story, as far as I'm concerned, starts back in the Fall of1976, when John Laird and Paul Rosenbloom, as new graduate students in computer science at Carnegie-Mellon University, joined the Instructible Production System (IPS) project (Rychener, Forgy, Langley, McDermott, Newell, Ramakrishna, 1977; Rychener & Newell, 1978). In those days, production systems were either small or special or both (Newell, 1973; Shortliffe, 1976). Mike Rychener had just completed his thesis (Rychener, 1976), showing how production systems could effectively and perspicuously program the full array of artificial intelligence (AI) systems, by creating versions of Studellt (done in an earlier study, Rychener 1975), EPAM, GPS, King-Pawn-King endgames, a toy-blocks problem solver, and a natural-language input system that connected to the blocks-world system.
Machine Learning: A Guide to Current Research
Book 12 · Dec 2012 ·
2.0star
One of the currently most active research areas within Artificial Intelligence is the field of Machine Learning. which involves the study and development of computational models of learning processes. A major goal of research in this field is to build computers capable of improving their performance with practice and of acquiring knowledge on their own. The intent of this book is to provide a snapshot of this field through a broad. representative set of easily assimilated short papers. As such. this book is intended to complement the two volumes of Machine Learning: An Artificial Intelligence Approach (Morgan-Kaufman Publishers). which provide a smaller number of in-depth research papers. Each of the 77 papers in the present book summarizes a current research effort. and provides references to longer expositions appearing elsewhere. These papers cover a broad range of topics. including research on analogy. conceptual clustering. explanation-based generalization. incremental learning. inductive inference. learning apprentice systems. machine discovery. theoretical models of learning. and applications of machine learning methods. A subject index IS provided to assist in locating research related to specific topics. The majority of these papers were collected from the participants at the Third International Machine Learning Workshop. held June 24-26. 1985 at Skytop Lodge. Skytop. Pennsylvania. While the list of research projects covered is not exhaustive. we believe that it provides a representative sampling of the best ongoing work in the field. and a unique perspective on where the field is and where it is headed.
Latchup in CMOS Technology: The Problem and Its Cure
Book 13 · Mar 2013 ·
0.0star
Why a book on Iatchup? Latchup has been, and continues to be, a potentially serious CMOS reliability concern. This concern is becoming more widespread with the ascendency of CMOS as the dominant VLSI technology, particularly as parasitic bipolar characteristics continue to improve at ever smaller dimensions on silicon wafers with ever lower defect densities. Although many successful parts have been marketed, latchup solutions have often been ad hoc. Although latchup avoidance techniques have been previously itemized, there has been little quantitative evaluation of prior latchup fixes. What is needed is a more general, more systematic treatment of the latchup problem. Because of the wide variety of CMOS technologies and the long term interest in latchup, some overall guiding principles are needed. Appreciating the variety of possible triggering mechanisms is key to a real understanding of latchup. This work reviews the origin of each and its effect on the parasitic structure. Each triggering mechanism is classified according to a new taxonomy.
A Natural Language Interface for Computer-Aided Design
Book 14 · Dec 2012 ·
0.0star
The advent of computer aided design and the proliferation of computer aided design tools have been instrumental in furthering the state-of-the art in integrated circuitry. Continuing this progress, however, demands an emphasis on creating user-friendly environments that facilitate the interaction between the designer and the CAD tool. The realization of this fact has prompted investigations into the appropriateness for CAD of a number of user-interface technologies. One type of interface that has hitherto not been considered is the natural language interface. It is our contention that natural language interfaces could solve many of the problems posed by the increasing number and sophistication of CAD tools. This thesis represents the first step in a research effort directed towards the eventual development of a natural language interface for the domain of computer aided design. The breadth and complexity of the CAD domain renders the task of developing a natural language interface for the complete domain beyond the scope of a single doctoral thesis. Hence, we have initally focussed on a sub-domain of CAD. Specifically, we have developed a natural language interface, named Cleopatra, for circuit-simulation post-processing. In other words, with Cleopatra a circuit-designer can extract and manipulate, in English, values from the output of a circuit-simulator (currently SPICE) without manually having to go through the output files produced by the simulator.
Machine Learning of Inductive Bias
Book 15 · Dec 2012 ·
0.0star
This book is based on the author's Ph.D. dissertation[56]. The the sis research was conducted while the author was a graduate student in the Department of Computer Science at Rutgers University. The book was pre pared at the University of Massachusetts at Amherst where the author is currently an Assistant Professor in the Department of Computer and Infor mation Science. Programs that learn concepts from examples are guided not only by the examples (and counterexamples) that they observe, but also by bias that determines which concept is to be considered as following best from the ob servations. Selection of a concept represents an inductive leap because the concept then indicates the classification of instances that have not yet been observed by the learning program. Learning programs that make undesir able inductive leaps do so due to undesirable bias. The research problem addressed here is to show how a learning program can learn a desirable inductive bias.
Digital CMOS Circuit Design
Book 16 · Dec 2012 ·
0.0star
Multi-Level Simulation for VLSI Design
Book 18 · Dec 2012 ·
0.0star
AND BACKGROUND 1. 1 CAD, Specification and Simulation Computer Aided Design (CAD) is today a widely used expression referring to the study of ways in which computers can be used to expedite the design process. This can include the design of physical systems, architectural environments, manufacturing processes, and many other areas. This book concentrates on one area of CAD: the design of computer systems. Within this area, it focusses on just two aspects of computer design, the specification and the simulation of digital systems. VLSI design requires support in many other CAD areas, induding automatic layout. IC fabrication analysis, test generation, and others. The problem of specification is unique, however, in that it i!> often the first one encountered in large chip designs, and one that is unlikely ever to be completely automated. This is true because until a design's objectives are specified in a machine-readable form, there is no way for other CAD tools to verify that the target system meets them. And unless the specifications can be simulated, it is unlikely that designers will have confidence in them, since specifications are potentially erroneous themselves. (In this context the term target system refers to the hardware and/or software that will ultimately be fabricated. ) On the other hand, since the functionality of a VLSI chip is ultimately determined by its layout geometry, one might question the need for CAD tools that work with areas other than layout.
An Artificial Intelligence Approach to Test Generation
Book 19 · Dec 2012 ·
0.0star
I am indebted to my thesis advisor, Michael Genesereth, for his guidance, inspiration, and support which has made this research possible. As a teacher and a sounding board for new ideas, Mike was extremely helpful in pointing out Haws, and suggesting new directions to explore. I would also like to thank Harold Brown for introducing me to the application of artificial intelligence to reasoning about designs, and his many valuable comments as a reader of this thesis. Significant contribu tions by the other members of my reading committee, Mark Horowitz, and Allen Peterson have greatly improved the content and organization of this thesis by forcing me to communicate my ideas more clearly. I am extremely grateful to the other members of the Logic Group at the Heuristic Programming Project for being a sounding board for my ideas, and providing useful comments. In particular, I would like to thank Matt Ginsberg, Vineet Singh, Devika Subramanian, Richard Trietel, Dave Smith, Jock Mackinlay, and Glenn Kramer for their pointed criticisms. This research was supported by Schlumberger Palo Alto Research (previously Fairchild Laboratory for Artificial Intelligence). I am grateful to Peter Hart, the former head of the AI lab, and his successor Marty Tenenbaum for providing an excellent environment for performing this research.
Relaxation Techniques for the Simulation of VLSI Circuits
Book 20 · Dec 2012 ·
0.0star
Circuit simulation has been a topic of great interest to the integrated circuit design community for many years. It is a difficult, and interesting, problem be cause circuit simulators are very heavily used, consuming thousands of computer hours every year, and therefore the algorithms must be very efficient. In addi tion, circuit simulators are heavily relied upon, with millions of dollars being gambled on their accuracy, and therefore the algorithms must be very robust. At the University of California, Berkeley, a great deal of research has been devoted to the study of both the numerical properties and the efficient imple mentation of circuit simulation algorithms. Research efforts have led to several programs, starting with CANCER in the 1960's and the enormously successful SPICE program in the early 1970's, to MOTIS-C, SPLICE, and RELAX in the late 1970's, and finally to SPLICE2 and RELAX2 in the 1980's. Our primary goal in writing this book was to present some of the results of our current research on the application of relaxation algorithms to circuit simu lation. As we began, we realized that a large body of mathematical and exper imental results had been amassed over the past twenty years by graduate students, professors, and industry researchers working on circuit simulation. It became a secondary goal to try to find an organization of this mass of material that was mathematically rigorous, had practical relevance, and still retained the natural intuitive simplicity of the circuit simulation subject.
Three-Dimensional Machine Vision
Book 21 · Dec 2012 ·
0.0star
Robot Dynamics Algorithms
Book 22 · Oct 2007 ·
0.0star
The purpose of this book is to present computationally efficient algorithms for calculating the dynamics of robot mechanisms represented as systems of rigid bodies. The efficiency is achieved by the use of recursive formulations of the equations of motion, i.e. formulations in which the equations of motion are expressed implicitly in terms of recurrence relations between the quantities describing the system. The use of recursive formulations in dynamics is fairly new, 50 the principles of their operation and reasons for their efficiency are explained. Three main algorithms are described: the recursIve Newton-Euler formulation for inverse dynamics (the calculation of the forces given the accelerations), and the composite-rigid-body and articulated-body methods for forward dynamics (the calculation of the accelerations given the forces). These algorithms are initially described in terms of an un-branched, open loop kinematic chain -- a typical serial robot mechanism. This is done to keep the descriptions of the algorithms simple, and is in line with descriptions appearing in the literature. Once the basic algorithms have been introduced, the restrictions on the mechanism are lifted and the algorithms are extended to cope with kinematic trees and loops, and general constraints at the joints. The problem of simulating the effect of contact between a robot and its environment is also considered. Some consideration is given to the details and practical problems of implementing these algori?hms on a computer.
Finite Fields for Computer Scientists and Engineers
Book 23 · Dec 2012 ·
0.0star
This book developed from a course on finite fields I gave at the University of Illinois at Urbana-Champaign in the Spring semester of 1979. The course was taught at the request of an exceptional group of graduate students (includ ing Anselm Blumer, Fred Garber, Evaggelos Geraniotis, Jim Lehnert, Wayne Stark, and Mark Wallace) who had just taken a course on coding theory from me. The theory of finite fields is the mathematical foundation of algebraic coding theory, but in coding theory courses there is never much time to give more than a "Volkswagen" treatment of them. But my 1979 students wanted a "Cadillac" treatment, and this book differs very little from the course I gave in response. Since 1979 I have used a subset of my course notes (correspond ing roughly to Chapters 1-6) as the text for my "Volkswagen" treatment of finite fields whenever I teach coding theory. There is, ironically, no coding theory anywhere in the book! If this book had a longer title it would be "Finite fields, mostly of char acteristic 2, for engineering and computer science applications. " It certainly does not pretend to cover the general theory of finite fields in the profound depth that the recent book of Lidl and Neidereitter (see the Bibliography) does.
