Bücher der Reihe The Springer International Series in Engineering and Computer Science

Lo, soul! seest thou not God's purpose from the first? The earth to be spann'd, connected by net-work From Passage to India! Walt Whitman, "e;Leaves of Grass"e;, 1900. The Internet is growing at a tremendous rate today. New services, such as telephony and multimedia, are being added to the pure data-delivery framework of yesterday. Such high demands on capacity could lead to a "e;bandwidth-crunch"e; at the core wide-area network resulting in degra- dation of service quality. Fortunately, technological innovations have emerged which can provide relief to the end-user to overcome the In- ternet's well-known delay and bandwidth limitations. At the physical layer, a major overhaul of existing networks has been envisaged from electronic media (such as twisted-pair and cable) to optical fibers - in the wide area, in the metropolitan area, and even in the local area set- tings. In order to exploit the immense bandwidth potential of the optical fiber, interesting multiplexing techniques have been developed over the years. Wavelength division multiplexing (WDM) is such a promising tech- nique in which multiple channels are operated along a single fiber si- multaneously, each on a different wavelength. These channels can be independently modulated to accommodate dissimilar bit rates and data formats, if so desired. Thus, WDM carves up the huge bandwidth of an optical fiber into channels whose bandwidths (1-10 Gbps) are compati- ble with peak electronic processing speed.

Iterative Detection: Adaptivity, Complexity Reduction, and Applications is a primary resource for both researchers and teachers in the field of communication. Unlike other books in the area, it presents a general view of iterative detection that does not rely heavily on coding theory or graph theory. The features of the text include: Both theoretical background and numerous real-world applications. Over 70 detailed examples, 100 problems, 180 illustrations, tables of notation and acronyms, and an extensive bibliography and subject index. A whole chapter devoted to a case study on turbo decoder design. Receiver design guidelines, rules and suggestions. The most advanced view of iterative (turbo) detection based only on block diagrams and standard detection and estimation theory. Development of adaptive iterative detection theory. Application of adaptive iterative detection to phase and channel tracking in turbo coded systems and systems representative of digital mobile radio designs. An entire chapter dedicated to complexity reduction. Numerous recent research results. Discussion of open problems at the end of each chapter. Among the applications considered in this book are joint equalization and decoding, turbo codes, multiuser detection and decoding, broadband wireless channel equalization, and applications to two-dimensional storage and imaging systems. Audience: Iterative Detection: Adaptivity, Complexity Reduction, and Applications provides an accessible and detailed reference for researchers, practicing engineers, and students working in the field of detection and estimation. It will be of particular interest to those who would like to learn how iterative detection can be applied to equalization, interference mitigation, and general signal processing tasks. Researchers and practicing engineers interested in learning the turbo decoding algorithm should also have this book.

Low-Voltage Low-Power Analog Integrated Circuits brings together in one place important contributions and state-of-the-art research results in this rapidly advancing area. Low-Voltage Low-Power Analog Integrated Circuits serves as an excellent reference, providing insight into some of the most important issues in the field.

Video and Image Processing in Multimedia Systems treats a number of critical topics in multimedia systems, with respect to image and video processing techniques and their implementations. These techniques include: Image and video compression techniques and standards, and Image and video indexing and retrieval techniques. Video and Image Processing in Multimedia Systems is divided into three parts. Part I serves as an introduction to multimedia systems, discussing basic concepts, multimedia networking and synchronization, and an overview of multimedia applications. Part II presents comprehensive coverage of image and video compression techniques and standards, their implementations and applications. Because multimedia data (specifically video and images) require efficient compression techniques in order to be stored and delivered in real-time, video and image compression is a crucial element of an effective multimedia system. In Part III attention is focused on the semantic nature of image and video source material, and how that material may be effectively indexed and retrieved. Topics discussed include static images, full-motion video, and the manner in which compressed representations can facilitate structural analysis. Part III concludes with an extended discussion of a case study. This book serves as an invaluable reference with respect to the most important standards in the field. Video and Image Processing in Multimedia Systems is suitable as a textbook for course use.

Responsive Computer Systems: Steps Towards Fault-Tolerant Real-Time Systems provides an extensive treatment of the most important issues in the design of modern Responsive Computer Systems. It lays the groundwork for a more comprehensive model that allows critical design issues to be treated in ways that more traditional disciplines of computer research have inhibited. It breaks important ground in the development of a fruitful, modern perspective on computer systems as they are currently developing and as they may be expected to develop over the next decade. Audience: An interesting and important road map to some of the most important emerging issues in computing, suitable as a secondary text for graduate level courses on responsive computer systems and as a reference for industrial practitioners.

Low-Voltage CMOS Operational Amplifiers: Theory, Design and Implementation discusses both single and two-stage architectures. Opamps with constant-gm input stage are designed and their excellent performance over the rail-to-rail input common mode range is demonstrated. The first set of CMOS constant-gm input stages was introduced by a group from Technische Universiteit, Delft and Universiteit Twente, the Netherlands. These earlier versions of circuits are discussed, along with new circuits developed at the Ohio State University. The design, fabrication (MOSIS Tiny Chips), and characterization of the new circuits are now complete. Basic analog integrated circuit design concepts should be understood in order to fully appreciate the work presented. However, the topics are presented in a logical order and the circuits are explained in great detail, so that Low-Voltage CMOS Operational Amplifiers can be read and enjoyed by those without much experience in analog circuit design. It is an invaluable reference book, and may be used as a text for advanced courses on the subject.

Silicon on Insulator is more than a technology, more than a job, and more than a venture in microelectronics; it is something different and refreshing in device physics. This book recalls the activity and enthu- siasm of our SOl groups. Many contributing students have since then disappeared from the SOl horizon. Some of them believed that SOl was the great love of their scientific lives; others just considered SOl as a fantastic LEGO game for adults. We thank them all for kindly letting us imagine that we were guiding them. This book was very necessary to many people. SOl engineers will certainly be happy: indeed, if the performance of their SOl components is not always outstanding, they can now safely incriminate the relations given in the book rather than their process. Martine, Gunter, and Y. S. Chang can contemplate at last the amount of work they did with the figures. Our SOl accomplices already know how much we borrowed from their expertise and would find it indecent to have their detailed contri- butions listed. Jean-Pierre and Dimitris incited the book, while sharing their experience in the reliability of floating bodies. Our families and friends now realize the SOl capability of dielectrically isolating us for about two years in a BOX. Our kids encouraged us to start writing. Our wives definitely gave us the courage to stop writing. They had a hard time fighting the symptoms of a rapidly developing SOl allergy.

Integrated Fiber-Optic Receivers covers many aspects of the design of integrated circuits for fiber-optic receivers and other high-speed serial data links. Fundamental concepts are explained at the system level, circuit level, and semiconductor device level. Techniques for extracting timing information from the random data stream are described in considerable detail, as are all other aspects of receiver design. Integrated Fiber-Optic Receivers is organized in two parts. Part I covers the theory of communications systems as it applies to high-speed PAM (Pulse Amplitude Modulation) systems. The primary emphasis is on clock recovery circuits. Because theoretical concepts are generally grasped more easily by example, Part II is devoted to circuit design issues that illustrate example realizations of architectures described in Part I. Part II presents the transistor-level design, and measured results, of fundamental building blocks and test circuits. For practicing engineers, more than just reporting on the results of specific circuits, this book serves as a tutorial on the design of integrated high-speed broadband PAM data systems, such as: repeaters in long-haul, fiber-optic, trunk-lines transceivers for use in LANs and WANs; read channels for high-density data storage devices; and wireless communication handsets. Integrated Fiber-Optic Receivers may be used as a text for advanced courses in both analog circuit design and communication systems.

Over the past two decades, research in the theory of Petri nets and the development of graphical tools has yielded a powerful methodology. The contributions in Petri Nets in Flexible and Agile Automation present theoretical development of Petri nets as well as in industrial applications to areas such as discrete- event control design, scheduling, performance evaluation and deadlock avoidance. These contributions also include comparative studies of Petri nets and other approaches. A primary theme of this book is to provide a unified approach to the applications of Petri nets in flexible and agile automation and, in that regard, a common notation and terminology is used. The book also allows readers to evaluate the benefits and applicability of state-of-the-art Petri net methods and apply CAD tools to problems of interest. Petri Nets in Flexible and Agile Automation is not only an essential reference for researchers, it is also a very useful tool for engineers, analysts and managers who are responsible for the design, implementation and operation of the next generation of manufacturing systems.

Modern electronics is driven by the explosive growth of digital communications and multi-media technology. A basic challenge is to design first-time-right complex digital systems, that meet stringent constraints on performance and power dissipation. In order to combine this growing system complexity with an increasingly short time-to-market, new system design technologies are emerging based on the paradigm of embedded programmable processors. This concept introduces modularity, flexibility and re-use in the electronic system design process. However, its success will critically depend on the availability of efficient and reliable CAD tools to design, programme and verify the functionality of embedded processors. Recently, new research efforts emerged on the edge between software compilation and hardware synthesis, to develop high-quality code generation tools for embedded processors. Code Generation for Embedded Systems provides a survey of these new developments. Although not limited to these targets, the main emphasis is on code generation for modern DSP processors. Important themes covered by the book include: the scope of general purpose versus application-specific processors, machine code quality for embedded applications, retargetability of the code generation process, machine description formalisms, and code generation methodologies. Code Generation for Embedded Systems is the essential introduction to this fast developing field of research for students, researchers, and practitioners alike.

Physical Design for Multichip Modules collects together a large body of important research work that has been conducted in recent years in the area of Multichip Module (MCM) design. The material consists of a survey of published results as well as original work by the authors. All major aspects of MCM physical design are discussed, including interconnect analysis and modeling, system partitioning and placement, and multilayer routing. For readers unfamiliar with MCMs, this book presents an overview of the different MCM technologies available today. An in-depth discussion of various recent approaches to interconnect analysis are also presented. Remaining chapters discuss the problems of partitioning, placement, and multilayer routing, with an emphasis on timing performance. For the first time, data from a wide range of sources is integrated to present a clear picture of a new, challenging and very important research area. For students and researchers looking for interesting research topics, open problems and suggestions for further research are clearly stated. Points of interest include : Clear overview of MCM technology and its relationship to physical design; Emphasis on performance-driven design, with a chapter devoted to recent techniques for rapid performance analysis and modeling of MCM interconnects; Different approaches to multilayer MCM routing collected together and compared for the first time; Explanation of algorithms is not overly mathematical, yet is detailed enough to give readers a clear understanding of the approach; Quantitative data provided wherever possible for comparison of different approaches; A comprehensive list of references to recent literature on MCMs provided.

Speech--to--Speech Translation: a Massively Parallel Memory-Based Approach describes one of the world's first successful speech--to--speech machine translation systems. This system accepts speaker-independent continuous speech, and produces translations as audio output. Subsequent versions of this machine translation system have been implemented on several massively parallel computers, and these systems have attained translation performance in the milliseconds range. The success of this project triggered several massively parallel projects, as well as other massively parallel artificial intelligence projects throughout the world. Dr. Hiroaki Kitano received the distinguished `Computers and Thought Award' from the International Joint Conferences on Artificial Intelligence in 1993 for his work in this area, and that work is reported in this book.

Since the early 1980s, CAD frameworks have received a great deal of attention, both in the research community and in the commercial arena. It is generally agreed that CAD framework technology promises much: advanced CAD frameworks can turn collections of individual tools into effective and user-friendly design environments. But how can this promise be fulfilled? CAD Frameworks: Principles and Architecture describes the design and construction of CAD frameworks. It presents principles for building integrated design environments and shows how a CAD framework can be based on these principles. It derives the architecture of a CAD framework in a systematic way, using well-defined primitives for representation. This architecture defines how the many different framework sub-topics, ranging from concurrency control to design flow management, relate to each other and come together into an overall system. The origin of this work is the research and development performed in the context of the Nelsis CAD Framework, which has been a working system for well over eight years, gaining functionality while evolving from one release to the next. The principles and concepts presented in this book have been field-tested in the Nelsis CAD Framework. CAD Frameworks: Principles and Architecture is primarily intended for EDA professionals, both in industry and in academia, but is also valuable outside the domain of electronic design. Many of the principles and concepts presented are also applicable to other design-oriented application domains, such as mechanical design or computer-aided software engineering (CASE). It is thus a valuable reference for all those involved in computer-aided design.

As any history student will tell you, all events must be understood within their political and sociological context. Yet science provides an interesting counterpoint to this idea, since scientific ideas stand on their own merit, and require no reference to the time and place of their conception beyond perhaps a simple citation. Even so, the historical context of a scientific discovery casts a special light on that discovery - a light that motivates the work and explains its significance against a backdrop of related ideas. The book that you hold in your hands is unusually adept at presenting technical ideas in the context of their time. On one level, Larry Bookman has produced a manuscript to satisfy the requirements of a PhD program. If that was all he did, my preface would praise the originality of his ideas and attempt to summarize their significance. But this book is much more than an accomplished disser- tation about some aspect of natural language - it is also a skillfully crafted tour through a vast body of computational, linguistic, neurophysiological, and psychological research.

Speech coding has been an ongoing area of research for several decades, yet the level of activity and interest in this area has expanded dramatically in the last several years. Important advances in algorithmic techniques for speech coding have recently emerged and excellent progress has been achieved in producing high quality speech at bit rates as low as 4.8 kb/s. Although the complexity of the newer more sophisticated algorithms greatly exceeds that of older methods (such as ADPCM), today's powerful programmable signal processor chips allow rapid technology transfer from research to product development and permit many new cost-effective applications of speech coding. In particular, low bit rate voice technology is converging with the needs of the rapidly evolving digital telecom- munication networks. The IEEE Workshop on Speech Coding for Telecommunications was held in Vancouver, British Columbia, Canada, from September 5 to 8, 1989. The objective of the workshop was to provide a forum for discussion of recent developments and future directions in speech coding. The workshop attracted over 130 researchers from several countries and its technical program included 51 papers.

Computer-Aided Design of Analog Circuits and Systems brings together in one place important contributions and state-of-the-art research results in the rapidly advancing area of computer-aided design of analog circuits and systems. This book serves as an excellent reference, providing insights into some of the most important issues in the field.

Application-Driven Architecture Synthesis describes the state of the art of architectural synthesis for complex real-time processing. In order to deal with the stringent timing requirements and the intricacies of complex real-time signal and data processing, target architecture styles and target application domains have been adopted to make the synthesis approach feasible. These approaches are also heavily application-driven, which is illustrated by many realistic demonstrations, used as examples in the book. The focus is on domains where application-specific solutions are attractive, such as significant parts of audio, telecom, instrumentation, speech, robotics, medical and automotive processing, image and video processing, TV, multi-media, radar, sonar. Application-Driven Architecture Synthesis is of interest to both academics and senior design engineers and CAD managers in industry. It provides an excellent overview of what capabilities to expect from future practical design tools, and includes an extensive bibliography.

This book brings together important contributions and state-of-the-art research results in the rapidly advancing area of symbolic analysis of analog circuits. It is also of interest to those working in analog CAD. The book is an excellent reference, providing insights into some of the most important issues in the symbolic analysis of analog circuits.

Speech and Audio Coding for Wireless and Network Applications contains 34 chapters, loosely grouped into six topical areas. The chapters in this volume reflect the progress and present the state of the art in low-bit-rate speech coding, primarily at bit rates from 2.4 kbit/s to 16 kbit/s. Together they represent important contributions from leading researchers in the speech coding community. Speech and Audio Coding for Wireless and Network Applications contains contributions describing technologies that are under consideration as standards for such applications as digital cellular communications (the half-rate American and European coding standards). A brief Introduction is followed by a section dedicated to low-delay speech coding, a research direction which emerged as a result of the CCITT requirement for a universal low-delay 16 kbit/s speech coding technology and now continues with the objective of achieving toll quality with moderate delay at a rate of 8 kbit/s. A section on the important topic of speech quality evaluation is then presented. This is followed by a section on speech coding for wireless transmission, and a section on audio coding which covers not only 7 kHz bandwidth speech, but also wideband coding applicable to high fidelity music. The book concludes with a section on speech coding for noisy transmission channels, followed by a section addressing future research directions. Speech and Audio Coding for Wireless and Network Applications presents a cross-section of the key contributions in speech and audio coding which have emerged recently. For this reason, the book is a valuable reference for all researchers and graduate students in the speech coding community.

In the last few years, the world of information networks has undergone significant changes that will revolutionize the future of communications. Data rates have reached the gigabit per second range. Optical fibers have become the transmission medium of choice. Standardization activities have very aggressively produced a set of well established standard for future LANs, MANs and WANs. It has become very difficult for computer and communications professionals to follow these rapidly evolving technologies and standards. High Performance Networks: Technology and Protocols provides a timely technical overview of the start-of-the-art in high performance networking. Chapters cover lightweight protocols, high performance protocol implementation techniques, high speed MAC protocols, optical networks, as well as emerging standards, including ATM, SMDS, B-ISDN, SONET, FCS and HIPPI. Professionals, engineers, and researchers in communications and computers, who need to understand the underlying technologies of high performance (gigabit) networks, will find this volume to be an invaluable reference. The book is also suitable for use as a text for advanced courses on the subject.

Generating Abstraction Hierarchies presents a completely automated approach to generating abstractions for problem solving. The abstractions are generated using a tractable, domain-independent algorithm whose only inputs are the definition of a problem space and the problem to be solved and whose output is an abstraction hierarchy that is tailored to the particular problem. The algorithm generates abstraction hierarchies that satisfy the `ordered monotonicity' property, which guarantees that the structure of an abstract solution is not changed in the process of refining it. An abstraction hierarchy with this property allows a problem to be decomposed such that the solution in an abstract space can be held invariant while the remaining parts of a problem are solved. The algorithm for generating abstractions is implemented in a system called ALPINE, which generates abstractions for a hierarchical version of the PRODIGY problem solver. Generating Abstraction Hierarchies formally defines this hierarchical problem solving method, shows that under certain assumptions this method can reduce the size of a search space from exponential to linear in the solution size, and describes the implementation of this method in PRODIGY. The abstractions generated by ALPINE are tested in multiple domains on large problem sets and are shown to produce shorter solutions with significantly less search than problem solving without using abstraction. Generating Abstraction Hierarchies will be of interest to researchers in machine learning, planning and problem reformation.

As MOS devices are scaled to meet increasingly demanding circuit specifications, process variations have a greater effect on the reliability of circuit performance. For this reason, statistical techniques are required to design integrated circuits with maximum yield. Statistical Modeling for Computer-Aided Design of MOS VLSI Circuits describes a statistical circuit simulation and optimization environment for VLSI circuit designers. The first step toward accomplishing statistical circuit design and optimization is the development of an accurate CAD tool capable of performing statistical simulation. This tool must be based on a statistical model which comprehends the effect of device and circuit characteristics, such as device size, bias, and circuit layout, which are under the control of the circuit designer on the variability of circuit performance. The distinctive feature of the CAD tool described in this book is its ability to accurately model and simulate the effect in both intra- and inter-die process variability on analog/digital circuits, accounting for the effects of the aforementioned device and circuit characteristics. Statistical Modeling for Computer-Aided Design of MOS VLSI Circuits serves as an excellent reference for those working in the field, and may be used as the text for an advanced course on the subject.

Field-Programmable Gate Arrays (FPGAs) have emerged as an attractive means of implementing logic circuits, providing instant manufacturing turnaround and negligible prototype costs. They hold the promise of replacing much of the VLSI market now held by mask-programmed gate arrays. FPGAs offer an affordable solution for customized VLSI, over a wide variety of applications, and have also opened up new possibilities in designing reconfigurable digital systems. Field-Programmable Gate Arrays discusses the most important aspects of FPGAs in a textbook manner. It provides the reader with a focused view of the key issues, using a consistent notation and style of presentation. It provides detailed descriptions of commercially available FPGAs and an in-depth treatment of the FPGA architecture and CAD issues that are the subjects of current research. The material presented is of interest to a variety of readers, including those who are not familiar with FPGA technology, but wish to be introduced to it, as well as those who already have an understanding of FPGAs, but who are interested in learning about the research directions that are of current interest.

The success of VHDL since it has been balloted in 1987 as an IEEE standard may look incomprehensible to the large population of hardware designers, who had never heared of Hardware Description Languages before (for at least 90% of them), as well as to the few hundreds of specialists who had been working on these languages for a long time (25 years for some of them). Until 1988, only a very small subset of designers, in a few large companies, were used to describe their designs using a proprietary HDL, or sometimes a HDL inherited from a University when some software environment happened to be developped around it, allowing usability by third parties. A number of benefits were definitely recognized to this practice, such as functional verification of a specification through simulation, first performance evaluation of a tentative design, and sometimes automatic microprogram generation or even automatic high level synthesis. As there was apparently no market for HDL's, the ECAD vendors did not care about them, start-up companies were seldom able to survive in this area, and large users of proprietary tools were spending more and more people and money just to maintain their internal system.

Integrated circuit technology is widely used for the full integration of electronic systems. In general, these systems are realized using digital techniques implemented in CMOS technology. The low power dissipation, high packing density, high noise immunity, ease of design and the relative ease of scaling are the driving forces of CMOS technology for digital applications. Parts of these systems cannot be implemented in the digital domain and will remain analog. In order to achieve complete system integration these analog functions are preferably integrated in the same CMOS technology. An important class of analog circuits that need to be integrated in CMOS are analog filters. This book deals with very high frequency (VHF) filters, which are filters with cut-off frequencies ranging from the low megahertz range to several hundreds of megahertz. Until recently the maximal cut-off frequencies of CMOS filters were limited to the low megahertz range. By applying the techniques presented in this book the limit could be pushed into the true VHF domain, and integrated VHF filters become feasible. Application of these VHF filters can be found in the field of communication, instrumentation and control systems. For example, pre and post filtering for high-speed AD and DA converters, signal reconstruction, signal decoding, etc. The general design philosophy used in this book is to allow only the absolute minimum of signal carrying nodes throughout the whole filter. This strategy starts at the filter synthesis level and is extended to the level of electronic circuitry. The result is a filter realization in which all capacitators (including parasitics) have a desired function. The advantage of this technique is that high frequency parasitic effects (parasitic poles/zeros) are minimally present. The book is a reference for engineers in research or development, and is suitable for use as a text for advanced courses on the subject. >

A color time-varying image can be described as a three-dimensional vector (representing the colors in an appropriate color space) defined on a three-dimensional spatiotemporal space. In conventional analog television a one-dimensional signal suitable for transmission over a communication channel is obtained by sampling the scene in the vertical and tem- poral directions and by frequency-multiplexing the luminance and chrominance informa- tion. In digital processing and transmission systems, sampling is applied in the horizontal direction, too, on a signal which has been already scanned in the vertical and temporal directions or directly in three dimensions when using some solid-state sensor. As a conse- quence, in recent years it has been considered quite natural to assess the potential advan- tages arising from an entire multidimensional approach to the processing of video signals. As a simple but significant example, a composite color video signal, such as the conven- tional PAL or NTSC signal, possesses a three-dimensional spectrum which, by using suitable three-dimensional filters, permits horizontal sampling at a rate which is less than that re- quired for correctly sampling the equivalent one-dimensional signal. More recently it has been widely recognized that the improvement of the picture quality in current and advanced television systems requires well-chosen signal processing algorithms which are multidimen- sional in nature within the demanding constraints of a real-time implementation.

As the computer gradually automates human-oriented tasks in multiple environ- ments, the interface between computers and the ever-wider population of human users assumes progressively increasing importance. In the office environment, for instance, clerical tasks such as document filing and retrieval, and higher-level tasks such as scheduling meetings, planning trip itineraries, and producing documents for publication, are being partially or totally automated. The range of users for office- oriented software includes clerks, secretaries, and businesspersons, none of whom are predominantly computer literate. The same phenomenon is echoed in the factory production line, in the securities trading floor, in government agencies, in educa- tional institutions, and even in the home. The arcane command languages of yes- teryear have proven too high a barrier for smooth acceptance of computerized func- tions into the workplace, no matter how useful these functions may be. Computer- naive users simply do not take the time to learn intimidating and complex computer interfaces. In order to place the functionality of modem computers at the disposition of diverse user populations, a number of different approaches have been tried, many meeting with a significant measure of success, to wit: special courses to train users in the simpler command languages (such as MS-DOS), designing point-and-click menu/graphics interfaces that require much less user familiarization (illustrated most clearly in the Apple Macintosh), and interacting with the user in his or her language of choice.

The layout of an integrated circuit (lC) is the process of assigning geometric shape, size and position to the components (transistors and connections) used in its fabrication. Since the number of components in modem ICs is enormous, computer- aided-design (CAD) programs are required to automate the difficult layout process. Prior CAD methods are inexact or limited in scope, and produce layouts whose area, and consequently manufacturing costs, are larger than necessary. This book addresses the problem of minimizing exactly the layout area of an important class of basic IC structures called CMOS cells. First, we precisely define the possible goals in area minimization for such cells, namely width and height minimization, with allowance for area-reducing reordering of transistors. We reformulate the layout problem in terms of a graph model and develop new graph-theoretic concepts that completely characterize the fundamental area minimization problems for series-parallel and nonseries-parallel circuits. These concepts lead to practical algorithms that solve all the basic layout minimization problems exactly, both for a single cell and for a one-dimensional array of such cells. Although a few of these layout problems have been solved or partially solved previously, we present here the first complete solutions to all the problems of interest.

The time has come for high-level synthesis. When research into synthesizing hardware from abstract, program-like de- scriptions started in the early 1970' s, there was no automated path from the register- transfer design produced by high-level synthesis to a complete hardware imple- mentation. As a result, it was very difficult to measure the effectiveness of high- level synthesis methods; it was also hard to justify to users the need to automate architecture design when low-level design had to be completed manually. Today's more mature CAD techniques help close the gap between an automat- ically synthesized design and a manufacturable design. Market pressures encour- age designers to make use of any and all automated tools. Layout synthesis, logic synthesis, and specialized datapath generators make it feasible to quickly imple- ment a register-transfer design in silicon,leaving designers more time to consider architectural improvements. As IC design becomes more automated, customers are increasing their demands; today's leading edge designers using logic synthesis systems are training themselves to be tomorrow's consumers of high-level synthe- sis systems. The need for very fast turnaround, a competitive fabrication market WhlCh makes small-quantity ASIC manufacturing possible, and the ever growing co:n- plexity of the systems being designed, all make higher-level design automaton inevitable.

The infonnation revolution is upon us. Whereas the industrial revolution heralded the systematic augmentation of human physical limitations by har- nessing external energy sources, the infonnation revolution strives to augment human memory and mental processing limitations by harnessing external computational resources. Computers can accumulate. transmit and output much more infonnation and in a more timely fashion than more con- ventional printed or spoken media. Of greater interest, however, is the computer's ability to process, classify and retrieve infonnation selectively in response to the needs of each human user. One cannot drink from the fire hydrant of infonnation without being immediately flooded with irrelevant text. Recent technological advances such as optical character readers only exacerbate the problem by increasing the volume of electronic text. Just as steam and internal combustion engines brought powerful energy sources under control to yield useful work in the industrial revolution, so must we build computational engines that control and apply the vast infonnation sources that they may yield useful knowledge. Information science is the study of systematic means to control, classify, process and retrieve vast amounts of infonnation in electronic fonn. In par- ticular, several methodologies have been developed to classify texts manually by annies of human indexers, as illustrated quite clearly at the National Library ofMedicine, and many computational techniques have been developed to search textual data bases automatically, such as full-text keyword searches. In general.