Contemporary Logic Design

by Katz, Randy H.; Borriello, Gaetano

• ISBN13: 9780201308570
• ISBN10: 0201308576
• Edition: 2nd
• Format: Paperback
• Copyright: 2004-12-15
• Publisher: Pearson

Summary

In the decade since the first edition of this book was published, the technologies of digital design have continued to evolve. The evolution has run along two related tracks: the underlying physical technology and the software tools that facilitate the application of new devices. The trends identified in the first edition have continued and promise to continue to do so. Programmable logic is virtually the norm for digital designers and the art of digital design now requires the software skills to deal with hardware description languages. Hardware designers now spend the majority of their time dealing with software. Specifically, the tools needed to efficiently map digital designs onto the emerging programmable devices that are growing more sophisticated. They capture their design specifications in software with language appropriate for describing the parallelism of hardware; they use software tools to simulate their designs and then to synthesize it into the implementation technology of choice. Design time is radically reduced, as market pressures require products to be introduced quickly at the right price and performance. Although the complexity of designs is necessitating ever more powerful abstractions, the fundamentals remain unchanged. The contemporary digital designer must have a much broader understanding of the discipline of computation, including both hardware and software. This broader perspective is present in this second edition.

Author Biography

Randy Katz received his undergraduate degree from Cornell University, and his M.S. and Ph.D. degrees from the University of California, Berkeley. He joined the faculty at Berkeley in 1983, where he is now the United Microelectronics Corporation Distinguished Professor in Electrical Engineering and Computer Science. He is a Fellow of the ACM and the IEEE, and a member of the National Academy of Engineering and the American Academy of Arts and Sciences. He has published over 230 refereed technical papers, book chapters, and books. He has won numerous awards, including 12 best paper awards, one "test of time" paper award, three best presentation awards, the Outstanding Alumni Award of the Computer Science Division, the CRA Outstanding Service Award, the Berkeley Distinguished Teaching Award, the Air Force Exceptional Civilian Service Decoration, The IEEE Reynolds Johnson Information Storage Award, the ASEE Frederic E. Terman Award, and the ACM Karl V. Karlstrom Outstanding Educator Award. With colleagues at Berkeley, he developed the terminology of and early prototypes for Redundant Arrays of Inexpensive Disks (RAID;. While on leave for government service in 1993-1994, he established whitehouse.gov and connected the White House to the Internet.

Gaetano Borriello is a Professor of Computer Science & Engineering at the University of Washington in Seattle. He received his undergraduate degree from the Polytechnic University, his M.S. degree from Stanford University, and his Ph.D. degree from the University of California, Berkeley. Prior to Berkeley he was a member of the research staff at Xerox's Palo Alto Research Center, where he was one of the designers of the first single-chip integrated Ethernet controller. He joined the faculty at UW in 1988 and received a Distinguished Teaching Award for his contributions in establishing the Computer Engineering undergraduate degree program. His research interests are in the design of ubiquitous computing technologies, the design of the embedded systems that connect the physical and virtual worlds, in the use of wireless sensors to infer human activities, and in creating applications that automatically adapt to their user's context. He is the founding director of Intel Research Seattle, a research laboratory focusing on new technologies and usage models for ubiquitous computing.

Table of Contents

Preface	xiii
Introduction	1	(32)
Dissecting the Title	2	(6)
Design	2	(2)
Logic Design	4	(2)
Contemporary Logic Design	6	(2)
A Brief History of Logic Design	8	(1)
Computation	9	(6)
Switches, Relays, and Circuits	10	(2)
Transistors	12	(1)
Digital Representations	13	(1)
Encoding	14	(1)
Examples	15	(18)
Chapter Review	25	(2)
Further Reading	27	(1)
Exercises	28	(5)
Combinational Logic	33	(60)
Outputs as a Function of Inputs	34	(3)
Combinational Logic Defined	34	(1)
Examples of Combinational Logic	34	(3)
Laws and Theorems of Boolean Logic	37	(9)
Axioms of Boolean Algebra	39	(3)
Theorems of Boolean Algebra	42	(3)
Duality and DeMorgan's Law	45	(1)
Realizing Boolean Formulas	46	(10)
Logic Gates	46	(3)
Logic Blocks and Hierarchy	49	(1)
Time Behavior and Waveforms	50	(2)
Minimizing the Number of Gates and Wires	52	(2)
Case Study: 7-Segment Decoder	54	(2)
Two-Level Logic	56	(9)
Canonical Forms	56	(7)
Incompletely Specified Functions	63	(2)
Motivation for Two-Level Simplification	65	(11)
Graphing Boolean Expressions	66	(1)
Boolean Cubes	67	(2)
Karnaugh Maps	69	(7)
Multilevel Logic	76	(4)
Motivation for Multilevel Minimization	80	(13)
Factored Forms	80	(1)
Criteria for Multilevel Simplification	81	(2)
Chapter Review	83	(1)
Further Reading	84	(1)
Exercises	85	(8)
Working with Combinational Logic	93	(62)
Two-Level Simplification	93	(10)
Formalizing the Process of Boolean Minimization	99	(3)
K-Maps Revisited: Five- and Six-Variable Functions	102	(1)
Automating Two-Level Simplification	103	(11)
Quine-McCluskey Method	104	(4)
Espresso Method	108	(3)
Realizing S-o-P and P-o-S Logic Networks	111	(3)
Multilevel Simplification	114	(8)
Automating Multilevel Simplification	122	(7)
Multilevel Logic Optimization Scripts	122	(4)
Realizing Multilevel Logic Networks	126	(3)
Time Response in Combinational Networks	129	(10)
Gate Delays	129	(1)
Timing Waveforms	130	(1)
Analysis of a Pulse-Shaper Circuit	131	(1)
Hazards and Glitches	132	(1)
Hazard Detection and Elimination in Two-Level Networks	133	(3)
Static Hazards in Multilevel Networks	136	(1)
Designing Static Hazard-Free Multilevel Circuits	137	(1)
Dynamic Hazards	138	(1)
Hardware Description Languages	139	(16)
Describing Structure	141	(1)
Describing Behavior	141	(2)
Delay	143	(1)
Event-Driven Simulation	143	(3)
Chapter Review	146	(1)
Further Reading	146	(1)
Exercises	147	(8)
Combinational Logic Technologies	155	(66)
History	156	(8)
From Switches to Integrated Circuits	156	(2)
Packaged Logic, Configurability, and Programmable Logic	158	(4)
Technology Metrics	162	(2)
Basic Logic Components	164	(32)
Fixed Logic	164	(4)
Look-Up Tables	168	(11)
Template-Based Logic	179	(17)
Two-Level and Multilevel Logic	196	(9)
Non-Gate Logic	205	(16)
Tri-State Outputs	206	(4)
Open-Collector Outputs and Wired Logic	210	(2)
Chapter Review	212	(1)
Further Reading	213	(1)
Exercises	213	(8)
Case Studies in Combinational Logic Design	221	(38)
Design Procedure	222	(2)
A Simple Process Line-Control Problem	224	(3)
Telephone Keypad Decoder	227	(4)
Leap Year Calculation	231	(3)
Logic Function Unit	234	(4)
Adder Design	238	(8)
Half Adder/Full Adder	238	(2)
Carry-Lookahead Circuits	240	(4)
Carry-Select Adder	244	(1)
BCD Adder Design	245	(1)
Arithmetic Logic Unit Design	246	(3)
A Sample ALU	247	(2)
Combinational Multiplier	249	(10)
Chapter Review	253	(1)
Further Reading	253	(1)
Exercises	254	(5)
Sequential Logic Design	259	(48)
Sequential Logic Elements	260	(18)
Simple Circuits with Feedback	260	(5)
Basic Latches	265	(2)
Clocks	267	(1)
Combining Latches	268	(2)
Master--Slave Latches and Edge-Triggered Flip-Flops	270	(3)
Timing Definitions	273	(5)
Timing Methodologies	278	(11)
Cascaded Flip-Flops and Setup/Hold/Propagation	279	(2)
Clock Skew	281	(1)
Asynchronous Inputs	282	(2)
Metastability and Synchronizer Failure	284	(1)
Self-timed and Speed-independent Circuits	285	(4)
Registers	289	(6)
Storage Registers	289	(2)
Shift Registers	291	(4)
Hardware Description Languages	295	(12)
Chapter Review	298	(1)
Further Reading	299	(1)
Exercises	300	(7)
Finite State Machines	307	(48)
Counters	308	(13)
Counter Design Procedure	310	(2)
Counters with More Complex Sequencing	312	(2)
Self-Starting Counters	314	(2)
Counter Reset	316	(1)
Counter Variations	316	(5)
The Concept of the State Machine	321	(5)
Odd or Even Parity Checker	321	(3)
Timing in State Machines	324	(2)
Basic FSM Design Approach	326	(13)
Finite State Machine Design Procedure	327	(5)
Moore and Mealy Machines	332	(1)
State Diagram Representation	333	(1)
Comparison of the Two Machine Types	334	(5)
Motivation for Optimization	339	(16)
Two State Diagrams, Same I/O Behavior	339	(1)
Advantages of Minimum States	340	(1)
State, Input, and Output Encoding	341	(1)
Factoring State Machines	342	(1)
A Traffic-Light Controller	342	(4)
Chapter Review	346	(1)
Further Reading	347	(1)
Exercises	348	(7)
Working with Finite State Machines	355	(46)
State Minimization/Reduction	356	(11)
Row-Matching Method	356	(4)
Implication Chart Method	360	(5)
Equivalent States in the Presence of Don't Cares	365	(1)
When State Minimization Doesn't Help	366	(1)
State Assignment	367	(13)
Sequential Encoding	369	(1)
Random Encoding	370	(1)
One-Hot Encoding	371	(1)
Output-Oriented Encoding	372	(2)
Heuristic Methods	374	(6)
Finite State Machine Partitioning	380	(6)
Finite State Machine Partitioning by Introducing Idle States	381	(5)
Hardware Description Languages	386	(15)
Chapter Review	391	(1)
Further Reading	392	(1)
Exercises	392	(9)
Sequential Logic Technologies	401	(51)
Basic Sequential Logic Components	402	(4)
FSM Design with Counters	406	(3)
FSM Design with Programmable Logic	409	(12)
Mapping a State Machine into a ROM Implementation	409	(1)
ROM Versus PLA-Based Design	410	(5)
Alternative PAL Architectures	415	(6)
FSM Design with More Sophisticated Programmable Logic Devices	421	(18)
PLDs: Programmable Logic Devices	422	(1)
Altera Erasable Programmable Logic Devices	422	(7)
Actel Field-Programmable Gate Arrays	429	(3)
Xilinx Field Programmable Gate Arrays	432	(7)
Case Study: Traffic-Light Controller	439	(13)
Problem Decomposition: Traffic-Light State Machine	439	(3)
PLA/PAL/ROM-Based Implementation	442	(1)
Counter-Based Implementation	443	(2)
FPGA-Based Implementation	445	(1)
Chapter Review	446	(1)
Further Reading	447	(1)
Exercises	447	(5)
Case Studies in Sequential Logic Design	452	(57)
A Finite String Recognizer	452	(8)
A Complex Counter	460	(3)
A Digital Combination Lock	463	(4)
A Memory Controller	467	(15)
RAM Basics: A 1024 x 4-Bit Static RAM	467	(3)
Dynamic RAM	470	(4)
DRAM Variations	474	(1)
Detailed SRAM Timing	475	(2)
Design of a Simple Memory Controller	477	(5)
A Sequential Multiplier	482	(5)
A Serial Line Transmitter/Receiver	487	(22)
Chapter Review	499	(1)
Further Reading	499	(1)
Exercises	500	(9)
Epilogue	509	(2)
Appendix A Number Systems	511	(22)
Positional Number Notation	511	(2)
Decimal Numbers	511	(1)
Binary, Octal, and Hexadecimal Numbers	512	(1)
Conversion Between Binary, Octal, and Hexadecimal Systems	513	(3)
Conversion from Binary to Octal or Hexadecimal	513	(1)
Conversion from Octal to Hexadecimal and Vice Versa	514	(1)
Conversion from Base 10 to Base 2: Successive Division	514	(2)
Binary Arithmetic Operations	516	(4)
Addition in Positional Notation	516	(2)
Subtraction in Positional Notation	518	(2)
Representation of Negative Numbers	520	(7)
Sign and Magnitude	520	(1)
Ones-Complement Numbers	521	(1)
Twos-Complement Numbers	522	(2)
Addition and Subtraction of Numbers	524	(2)
Overflow Conditions	526	(1)
BCD Number Representation	527	(6)
Appendix Review	528	(1)
Exercises	529	(4)
Appendix B Basic Electronics	533	(33)
Basic Electricity	533	(3)
Terminology	533	(1)
Fundamental Quantities and Laws	534	(2)
Logic Gates from Resistors and Diodes	536	(2)
Voltage Dividers	536	(1)
Diode Logic	537	(1)
Bipolar-Transistor Logic	538	(5)
Basic Bipolar-Transistor Logic	539	(1)
Diode-Transistor Logic	539	(2)
Transistor-Transistor Logic	541	(1)
TTL Circuits and Noise Margin	542	(1)
MOS Transistors	543	(11)
Voltage-Controlled Switches	543	(1)
Logic Gates from MOS Switches	544	(2)
CMOS Transmission Gate	546	(1)
Switch and Steering Logic	547	(7)
Elements of the Data Sheet	554	(2)
Simple Performance Calculations	556	(1)
Schematic Documentation Standards	556	(4)
Practical Aspects of Inputs, Outputs, and Clocks	560	(6)
Switches and LEDs as Inputs and Outputs	561	(1)
Debouncing Switches	562	(2)
Appendix Review	564	(1)
Exercises	565	(1)
Appendix C Flip-Flop Types	566	(13)
Flip-Flop Components	566	(2)
Realizing Circuits with Different Kinds of Flip-Flops	568	(2)
Conversion of One Flip-Flop Type to Another	568	(2)
Shift Registers and Counters	570	(9)
Implementation with R-S Flip-Flops	572	(2)
Implementation with J-K Flip-Flops	574	(2)
Implementation with T Flip-Flops	576	(1)
Implementation with D Flip-Flops	576	(2)
Comparison and Summary	578	(1)
Appendix Review	579	(1)
Exercises	579	(2)
Index	581

Excerpts

A Second Edition In the decade since the first edition of this book was published, the technologies of digital design have continued to evolve. The evolution has run along two closely related tracks: the underlying physical technology and the software tools that facilitate the application of the new devices. The trends identified in the first edition have continued stronger than ever and promise to continue for some time to come. Specifically, programmable logic has become virtually the norm for digital designers and the art of digital design now absolutely requires the software skills to deal with hardware description languages. No longer do we see the familiar yellow cover of the TTL Data Book on every designer''s bookshelf. In fact, for many application areas, even small programmable logic devices (PLDs), the mainstays of they 1970s and early 1980s, are rapidly disappearing. The burgeoning market for smaller, lower power, and more portable devices has driven high levels of integration into almost every product. This also has changed the nature of optimization; the focus is now on what goes into each chip rather than on the collection of individual gates needed to realize the design. The optimizations of today are more and more often made at the architecture level rather than in the switches. Hardware designers now spend the majority of their time dealing with software. Specifically, the tools needed to efficiently map digital designs onto the emerging programmable devices that are growing ever more sophisticated. They capture their design specifications in software with description languages appropriate for describing the parallelism of hardware; they use software tools to simulate their designs and then to synthesize it into the implementation technology of choice. Design time is reduced radically as market pressures require products to be introduced quickly, at the right price and performance. Although the overgrowing complexity of designs necessitates more powerful abstractions, the fundamentals haven''t changed. In fact, the contemporary digital designer must have a broader understanding of the discipline of computation than ever before, including both hardware and software. In this second edition, we provide this broader perspective. Changes from the First Edition There are many changes from the first edition that can be grouped into four rough categories. First, we updated the hardware technologies discussed in the book. Second, we added a more complete, if nevertheless introductory, treatment of the software tools that are now so commonplace in the designer''s tool kit. Third, we responded to the comments and suggestions received over the years by the many faculty and practitioners who have used the book. Finally, we rationalized the organization of the text so that concepts, technologies, tools, and practical matters were more clearly defined. New Introduction The introduction has been changed from one that focused on the process of design to one that introduces the concepts of computation, encoding, and sequencing. This sets out a better road map to the rest of the book and provides a rationale for its organization. Rather than discussing the design process in the abstract, we now include many more case studies to help the student gain that understanding by seeing the process in action. Repartitioning of Material Each of the two major sections on combinational and sequential logic was divided into a set of chapters. These first cover the fundamental concepts, then describe the principles of manipulating the logic into different forms, followed by a discussion of the optimizations and tools that are available, and concludes with an overview of the technologies available to build logic circuits. Each is capped by a set of comprehensive design case studies that make each of the issues concrete. More Emphasis on Programmable Logic We have added new material on the latest programmable logic technologies that have quickly become the dominant style for realizing digital designs. We do not attempt to provide all the information needed to work with any one technology. Those used will vary dramatically from institution to institution. Therefore, the book needs to be supplemented with a laboratory guide that covers the specifics of a particular installation. In this text, we focused on the underlying concepts. We expect laboratory guides to be available in the form of web-based materials that can be easily customized to the variety already out there and updated as new technologies emerge. Inclusion of Hardware Description Languages HDLs are now given a more central role to reflect their total acceptance by the design community over the past 10 years. We describe only the basics of one of the dominant languages, namely Verilog, focusing on describing behavior, as well as covering the basics of HDL simulation models. We highlight the power of the languages in making designs more parameterizable and customizable and designers more efficient. Design Case Studies Nothing helps students learn design as much as designing for themselves. The next best thing is to provide a large collection of examples where the intuitions and rules of thumb are discussed explicitly. The hope is that this will help bootstrap new digital designers into the world of practical applications rather than the drill problems that were the norm in simpler times. There are many new and extensive design examples sprinkled throughout the text and in two large case study chapters focusing on combinational and sequential logic. Elimination of Chapters on Datapath, Control, and Register-Transfer We decided to remove the last two chapters of the first edition, that focused on datapath and register-transfer design, and a simple processor as an in-depth design case study of the interaction of control and datapath. While these topics are without a doubt important, on reflection we felt they are better left for a more extended study of digital design than could be included within the page limit of this edition. Instead, we chose more intensive coverage of programmable logic and HDLs, with extensive but smaller design examples spread throughout the text. We plan to make supplementary materials on the eliminated topics available on the web. Navigating the Book The book is organized into 10 chapters and three appendices. Chapter 1 is an overall introduction to the field. Chapters 2 through 5 cover combinational logic. Chapters 6 through 10 cover sequential logic. The three appendices provide some potentially useful background material that may have been part of other courses in a computer or electrical engineering curriculum. Chapter 1 is an ambitious attempt to introduce many of the concepts of digital design through a short history of the evolution of digital hardware and two simple examples. Many may find that it introduces too many concepts too quickly for students to grasp their importance. However, this was not the intent. We fully expect students to be somewhat overwhelmed by the number of new concepts that come up in the discussion of the example. The purpose of the chapter is to provide an aerial view of the field so that students find it easier to see how the pieces they will see, in much greater detail and depth in later chapters, fit together coherently. It is certainly possible to replace this chapter with a more traditional introduction. The next four chapters lay out the concepts of combinational logic design, closing with a set of comprehensive examples. Chapter 2 covers the basics of combinational logic from simple gates to their time behavior. It lays out the concepts of two-level and multilevel logic and motivates why we would want to simplify logic. Some of the basic machinery for manipulating log