Digital Desgin - 5th Edition - Morris Mano & Michael D.Ciletti.pdf

 Digital Design With an Introduction to the Verilog HDL This page intentionally left blank  Digital Design With an Introduction to the Verilog HDL FIFTH EDITION...

 Digital Design With an Introduction to the Verilog HDL This page intentionally left blank  Digital Design With an Introduction to the Verilog HDL FIFTH EDITION M. Morris Mano Emeritus Professor of Computer Engineering California State University, Los Angeles Michael D. Ciletti Emeritus Professor of Electrical and Computer Engineering University of Colorado at Colorado Springs Upper Saddle River Boston Columbus San Franciso New York Indianapolis London Toronto Sydney Singapore Tokyo Montreal Dubai Madrid Hong Kong Mexico City Munich Paris Amsterdam Cape Town Vice President and Editorial Director, ECS: Cover Designer: Jayne Conte Marcia J. Horton Cover Photo: Michael D. Ciletti Executive Editor: Andrew Gilfillan Composition: Jouve India Private Limited Vice-President, Production: Vince O’Brien Full-Service Project Management: Jouve India Private Executive Marketing Manager: Tim Galligan Limited Marketing Assistant: Jon Bryant Printer/Binder: Edwards Brothers Permissions Project Manager: Karen Sanatar Typeface: Times Ten 10/12 Senior Managing Editor: Scott Disanno Production Project Manager/Editorial Production Manager: Greg Dulles Copyright © 2013, 2007, 2002, 1991, 1984 Pearson Education, Inc., publishing as Prentice Hall, One Lake Street, Upper Saddle River, New Jersey 07458. All rights reserved. Manufactured in the United States of America. This publication is protected by Copyright, and permission should be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. To obtain permission(s) to use material from this work, please submit a written request to Pearson Education, Inc., Permissions Department, One Lake Street, Upper Saddle River, New Jersey 07458. Many of the designations by manufacturers and seller to distinguish their products are claimed as trademarks. Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed in initial caps or all caps. All rights reserved. No part of this book may be reproduced, in any form or by any means, without permission in writing from the publisher. Verilogger Pro and SynaptiCAD are trademarks of SynaptiCAD, Inc., Blacksburg, VA 24062–0608. The author and publisher of this book have used their best efforts in preparing this book. These efforts include the development, research, and testing of the theories and programs to determine their effectiveness. The author and publisher make no warranty of any kind, expressed or implied, with regard to these programs or the documentation contained in this book. The author and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising out of, the furnishing, performance, or use of these programs. About the cover: “Spider Rock in Canyon de Chelley,” Chinle, Arizona, USA, January 2011. Photograph courtesy of mdc Images, LLC (www.mdcilettiphotography.com). Used by permission. Library of Congress Cataloging-in-Publication Data Mano, M. Morris, 1927– Digital design : with an introduction to the verilog hdl / M. Morris Mano, Michael D. Ciletti.—5th ed. p. cm. Includes index. ISBN-13: 978-0-13-277420-8 ISBN-10: 0-13-277420-8 1. Electronic digital computers—Circuits. 2. Logic circuits. 3. Logic design. 4. Digital integrated circuits. I. Ciletti, Michael D. II. Title. TK7888.3.M343 2011 621.39'5—dc23 2011039094 10 9 8 7 6 5 4 3 2 1 ISBN-13: 978-0-13-277420-8 ISBN-10: 0-13-277420-8 Contents Preface ix 1 Digital Systems and Binary Numbers 1 1.1 Digital Systems 1 1.2 Binary Numbers 3 1.3 Number‐Base Conversions 6 1.4 Octal and Hexadecimal Numbers 8 1.5 Complements of Numbers 10 1.6 Signed Binary Numbers 14 1.7 Binary Codes 18 1.8 Binary Storage and Registers 27 1.9 Binary Logic 30 2 Boolean Algebra and Logic Gates 38 2.1 Introduction 38 2.2 Basic Definitions 38 2.3 Axiomatic Definition of Boolean Algebra 40 2.4 Basic Theorems and Properties of Boolean Algebra 43 2.5 Boolean Functions 46 2.6 Canonical and Standard Forms 51 2.7 Other Logic Operations 58 2.8 Digital Logic Gates 60 2.9 Integrated Circuits 66 v vi Contents 3 Gate‐Level Minimization 73 3.1 Introduction 73 3.2 The Map Method 73 3.3 Four‐Variable K-Map 80 3.4 Product‐of‐Sums Simplification 84 3.5 Don’t‐Care Conditions 88 3.6 NAND and NOR Implementation 90 3.7 Other Two‐Level Implementations 97 3.8 Exclusive‐OR Function 103 3.9 Hardware Description Language 108 4 Combinational Logic 125 4.1 Introduction 125 4.2 Combinational Circuits 125 4.3 Analysis Procedure 126 4.4 Design Procedure 129 4.5 Binary Adder–Subtractor 133 4.6 Decimal Adder 144 4.7 Binary Multiplier 146 4.8 Magnitude Comparator 148 4.9 Decoders 150 4.10 Encoders 155 4.11 Multiplexers 158 4.12 HDL Models of Combinational Circuits 164 5 Synchronous Sequential Logic 190 5.1 Introduction 190 5.2 Sequential Circuits 190 5.3 Storage Elements: Latches 193 5.4 Storage Elements: Flip‐Flops 196 5.5 Analysis of Clocked Sequential Circuits 204 5.6 Synthesizable HDL Models of Sequential Circuits 217 5.7 State Reduction and Assignment 231 5.8 Design Procedure 236 6 Registers and Counters 255 6.1 Registers 255 6.2 Shift Registers 258 6.3 Ripple Counters 266 6.4 Synchronous Counters 271 6.5 Other Counters 278 6.6 HDL for Registers and Counters 283  Contents vii 7 Memory and Programmable Logic 299 7.1 Introduction 299 7.2 Random‐Access Memory 300 7.3 Memory Decoding 307 7.4 Error Detection and Correction 312 7.5 Read‐Only Memory 315 7.6 Programmable Logic Array 321 7.7 Programmable Array Logic 325 7.8 Sequential Programmable Devices 329 8 Design at the Register Tr a n s f e r L e v e l 351 8.1 Introduction 351 8.2 Register Transfer Level Notation 351 8.3 Register Transfer Level in HDL 354 8.4 Algorithmic State Machines (ASMs) 363 8.5 Design Example (ASMD Chart) 371 8.6 HDL Description of Design Example 381 8.7 Sequential Binary Multiplier 391 8.8 Control Logic 396 8.9 HDL Description of Binary Multiplier 402 8.10 Design with Multiplexers 411 8.11 Race‐Free Design (Software Race Conditions) 422 8.12 Latch‐Free Design (Why Waste Silicon?) 425 8.13 Other Language Features 426 9 Laboratory Experiments with Standard ICs and FPGAs 438 9.1 Introduction to Experiments 438 9.2 Experiment 1: Binary and Decimal Numbers 443 9.3 Experiment 2: Digital Logic Gates 446 9.4 Experiment 3: Simplification of Boolean Functions 448 9.5 Experiment 4: Combinational Circuits 450 9.6 Experiment 5: Code Converters 452 9.7 Experiment 6: Design with Multiplexers 453 9.8 Experiment 7: Adders and Subtractors 455 9.9 Experiment 8: Flip‐Flops 457 9.10 Experiment 9: Sequential Circuits 460 9.11 Experiment 10: Counters 461 9.12 Experiment 11: Shift Registers 463 9.13 Experiment 12: Serial Addition 466 9.14 Experiment 13: Memory Unit 467 9.15 Experiment 14: Lamp Handball 469 viii Contents 9.16 Experiment 15: Clock‐Pulse Generator 473 9.17 Experiment 16: Parallel Adder and Accumulator 475 9.18 Experiment 17: Binary Multiplier 478 9.19 Verilog HDL Simulation Experiments and Rapid Prototyping with FPGAs 480 10 Standard Graphic Symbols 488 10.1 Rectangular‐Shape Symbols 488 10.2 Qualifying Symbols 491 10.3 Dependency Notation 493 10.4 Symbols for Combinational Elements 495 10.5 Symbols for Flip‐Flops 497 10.6 Symbols for Registers 499 10.7 Symbols for Counters 502 10.8 Symbol for RAM 504 Appendix 507 Answers to Selected Problems 521 Index 539 Preface Since the fourth edition of Digital Design, the commercial availability of devices using digital technology to receive, manipulate, and transmit information seems to have exploded. Cell phones and handheld devices of various kinds offer new, competing features almost daily. Underneath the attractive graphical user interface of all of these devices sits a digital system that processes data in a binary format. The theoretical foundations of these systems have not changed much; indeed, one could argue that the stability of the core theory, coupled with modern design tools, has promoted the widespread response of manufacturers to the opportunities of the marketplace. Con- sequently, our refinement of our text has been guided by the need to equip our grad- uates with a solid understanding of digital machines and to introduce them to the methodology of modern design. This edition of Digital Design builds on the previous four editions, and the feedback of the team of reviewers who helped set a direction for our presentation. The focus of the text has been sharpened to more closely reflect the content of a foundation course in digital design and the mainstream technology of today’s digital systems: CMOS circuits. The intended audience is broad, embracing students of computer science, com- puter engineering, and electrical engineering. The key elements that the book focuses include (1) Boolean logic, (2) logic gates used by designers, (3) synchronous finite state machines, and (4) datapath controller design—all from a perspective of designing dig- ital systems. This focus led to elimination of material more suited for a course in elec- tronics. So the reader will not find here content for asynchronous machines or descriptions of bipolar transistors. Additionally, the widespread availability of web‐ based ancillary material prompted us to limit our discussion of field programmable gate arrays (FPGAs) to an introduction of devices offered by only one manufacturer, rather than two. Today’s designers rely heavily on hardware description languages ix x Preface (HDLs), and this edition of the book gives greater attention to their use and presents what we think is a clear development of a design methodology using the Verilog HDL. M U LT I ‐ M O D A L L E A R N I N G Digital Design supports a multimodal approach to learning. The so‐called VARK char- acterization of learning modalities identifies four major modes by which humans learn: (V) visual, (A) aural, (R) reading, and (K) kinesthetic. In hindsight, we note that the relatively high level of illustrations and graphical content of our text addresses the visual (V) component of VARK; discussions and numerous examples address the reading (R) component. Students who exploit the availability of free simulators to work assignments are led through a kinesthetic (K) learning experience, including the positive feedback and delight of designing a logic system that works. The remaining element of VARK, the aural/auditory (A) experience, is left to the instructor. We have provided an abundance of material and examples to support classroom lectures. Thus, a course in digital design, using Digital Design, can provide a rich, balanced learning experience and address all the modes identified by VARK. For those who might still question the presentation and use of HDLs in a first course in digital design, we note that industry has largely abandoned schematic‐based design entry, a style which emerged in the 1980s, during the nascent development of CAD tools for integrated circuit (IC) design. Schematic entry creates a representation of functional- ity that is implicit in the layout of the schematic. Unfortunately, it is difficult for anyone in a reasonable amount of time to determine the functionality represented by the sche- matic of a logic circuit without having been instrumental in its construction, or without having additional documentation expressing the design intent. Consequently, industry has migrated to HDLs (e.g., Verilog) to describe the functionality of a design and to serve as the basis for documenting, simulating, testing, and synthesizing the hardware imple- mentation of the design in a standard cell‐based ASIC or an FPGA. The utility of a schematic depends on the careful, detailed documentation of a carefully constructed hierarchy of design modules. In the old paradigm, designers relied upon their years of experience to create a schematic of a circuit to implement functionality. In today’s design flow, designers using HDLs can express functionality directly and explicitly, without years of accumulated experience, and use synthesis tools to generate the schematic as a by‐ product, automatically. Industry practices arrived here because schematic entry dooms us to inefficiency, if not failure, in understanding and designing large, complex ICs. We note, again in this edition, that introducing HDLs in a first course in designing digital circuits is not intended to replace fundamental understanding of the building blocks of such circuits or to eliminate a discussion of manual methods of design. It is still essential for a student to understand how hardware works. Thus, we retain a thorough treatment of combinational and sequential logic devices. Manual design practices are presented, and their results are compared with those obtained with a HDL‐based paradigm. What we are presenting, however, is an emphasis on how hardware is designed, to better prepare a student for a career in today’s industry, where HDL‐based design practices are dominant.  Preface xi FLEXIBILITY The sequence of topics in the text can accommodate courses that adhere to traditional, manual‐based, treatments of digital design, courses that treat design using an HDL, and courses that are in transition between or blend the two approaches. Because modern synthesis tools automatically perform logic minimization, Karnaugh maps and related topics in optimization can be presented at the beginning of a treatment of digital design, or they can be presented after circuits and their applications are examined and simulated with an HDL. The text includes both manual and HDL‐based design examples. Our end‐ of‐chapter problems further facilitate this flexibility by cross referencing problems that address a traditional manual design task with a companion problem that uses an HDL to accomplish the task. Additionally, we link the manual and HDL‐based approaches by presenting annotated results of simulations in the text, in answers to selected problems at the end of the text, and in the solutions manual. NEW TO THIS EDITION This edition of Digital Design uses the latest features of IEEE Standard 1364, but only insofar as they support our pedagogical objectives. The revisions and updates to the text include: Elimination of specialized circuit‐level content not typically covered in a first course in logic circuits and digital design (e.g., RTL, DTL, and emitter‐coupled logic circuits) Addition of “Web Search Topics” at the end of each chapter to point students to additional subject matter available on the web Revision of approximately one‐third of the problems at the end of the chapters A printed solution manual for entire text, including all new problems Streamlining of the discussion of Karnaugh maps Integration of treatment of basic CMOS technology with treatment of logic gates Inclusion of an appendix introducing semiconductor technology DESIGN METHODLOGY This text presents a systematic methodology for designing a state machine to control the datapath of a digital system. Moreover, the framework in which this material is pre- sented treats the realistic situation in which status signals from the datapath are used by the controller, i.e., the system has feedback. Thus, our treatment provides a foundation for designing complex and interactive digital systems. Although it is presented with an emphasis on HDL‐based design, the methodology is also applicable to manual‐based approaches to design. xii Preface JUST ENOUGH HDL We present only those elements of the Verilog language that are matched to the level and scope of this text. Also, correct syntax does not guarantee that a model meets a functional specification or that it can be synthesized into physical hardware. So, we introduce stu- dents to a disciplined use of industry‐based practices for writing models to ensure that a behavioral description can be synthesized into physical hardware, and that the behavior of the synthesized circuit will match that of the behavioral description. Failure to follow this discipline can lead to software race conditions in the HDL models of such machines, race conditions in the test bench used to verify them, and a mismatch between the results of simulating a behavioral model and its synthesized physical counterpart. Similarly, fail- ure to abide by industry practices may lead to designs that simulate correctly, but which have hardware latches that are introduced into the design accidentally as a consequence of the modeling style used by the designer. The industry‐based methodology we present leads to race‐free and latch‐free designs. It is important that students learn and follow industry practices in using HDL models, independent of whether a student’s curriculum has access to synthesis tools. V E R I F I C AT I O N In industry, significant effort is expended to verify that the functionality of a circuit is correct. Yet not much attention is given to verification in introductory texts on digital design, where the focus is on design itself, and testing is perhaps viewed as a secondary undertaking. Our experience is that this view can lead to premature “high‐fives” and declarations that “the circuit works beautifully.” Likewise, industry gains repeated returns on its investment in an HDL model by ensuring that it is readable, portable, and reusable. We demonstrate naming practices and the use of parameters to facilitate reusability and portability. We also provide test benches for all of the solutions and exercises to (1) verify the functionality of the circuit, (2) underscore the importance of thorough testing, and (3) introduce students to important concepts, such as self‐checking test benches. Advo- cating and illustrating the development of a test plan to guide the development of a test bench, we introduce test plans, albeit simply, in the text and expand them in the solutions manual and in the answers to selected problems at the end of the text. HDL CONTENT We have ensured that all examples in the text and all answers in the solution manual conform to accepted industry practices for modeling digital hardware. As in the previ- ous edition, HDL material is inserted in separate sections so that it can be covered or skipped as desired, does not diminish treatment of manual‐based design, and does not dictate the sequence of presentation. The treatment is at a level suitable for beginning students who are learning digital circuits and a HDL at the same time. The text prepares  Preface xiii students to work on signficant independent design projects and to succeed in a later course in computer architecture and advanced digital design. Instructor Resources Instructors can download the following classroom‐ready resources from the publisher’s website for the text (www.pearsonhighered.com/mano): Source code and test benches for all Verilog HDL examples in the test All figures and tables in the text Source code for all HDL models in the solutions manual A downloadable solutions manual with graphics suitable for classroom presentation HDL Simulators The Companion Website identifies web URLs to two simulators provided by Synapti- CAD. The first simulator is VeriLogger Pro, a traditional Verilog simulator that can be used to simulate the HDL examples in the book and to verify the solutions of HDL problems. This simulator accepts the syntax of the IEEE‐1995 standard and will be useful to those who have legacy models. As an interactive simulator, Verilogger Ex- treme accepts the syntax of IEEE‐2001 as well as IEEE‐1995, allowing the designer to simulate and analyze design ideas before a complete simulation model or schematic is available. This technology is particularly useful for students because they can quickly enter Boolean and D flip‐flop or latch input equations to check equivalency or to ex- periment with flip‐flops and latch designs. Students can access the Companion Website at www.pearsonhighered.com/mano. Chapter Summary The following is a brief summary of the topics that are covered in each chapter. Chapter 1 presents the various binary systems suitable for representing information in digital systems. The binary number system is explained and binary codes are illus- trated. Examples are given for addition and subtraction of signed binary numbers and decimal numbers in binary‐coded decimal (BCD) format. Chapter 2 introduces the basic postulates of Boolean algebra and shows the correla- tion between Boolean expressions and their corresponding logic diagrams. All possible logic operations for two variables are investigated, and the most useful logic gates used in the design of digital systems are identified. This chapter also introduces basic CMOS logic gates. Chapter 3 covers the map method for simplifying Boolean expressions. The map method is also used to simplify digital circuits constructed with AND‐OR, NAND, or NOR gates. All other possible two‐level gate circuits are considered, and their method of implementation is explained. Verilog HDL is introduced together with simple exam- ples of gate‐level models. xiv Preface Chapter 4 outlines the formal procedures for the analysis and design of combina- tional circuits. Some basic components used in the design of digital systems, such as adders and code converters, are introduced as design examples. Frequently used digital logic functions such as parallel adders and subtractors, decoders, encoders, and multi- plexers are explained, and their use in the design of combinational circuits is illustrated. HDL examples are given in gate‐level, dataflow, and behavioral models to show the alternative ways available for describing combinational circuits in Verilog HDL. The procedure for writing a simple test bench to provide stimulus to an HDL design is presented. Chapter 5 outlines the formal procedures for analyzing and designing clocked (syn- chronous) sequential circuits. The gate structure of several types of flip‐flops is presented together with a discussion on the difference between level and edge triggering. Specific examples are used to show the derivation of the state table and state diagram when analyzing a sequential circuit. A number of design examples are presented with empha- sis on sequential circuits that use D‐type flip‐flops. Behavioral modeling in Verilog HDL for sequential circuits is explained. HDL Examples are given to illustrate Mealy and Moore models of sequential circuits. Chapter 6 deals with various sequential circuit components such as registers, shift registers, and counters. These digital components are the basic building blocks from which more complex digital systems are constructed. HDL descriptions of shift registers and counter are presented. Chapter 7 deals with random access memory (RAM) and programmable logic devices. Memory decoding and error correction schemes are discussed. Combinational and sequential programmable devices such as ROMs, PLAs, PALs, CPLDs, and FPGAs are presented. Chapter 8 deals with the register transfer level (RTL) representation of digital sys- tems. The algorithmic state machine (ASM) chart is introduced. A number of examples demonstrate the use of the ASM chart, ASMD chart, RTL representation, and HDL description in the design of digital systems. The design of a finite state machine to con- trol a datapath is presented in detail, including the realistic situation in which status signals from the datapath are used by the state machine that controls it. This chapter is the most important chapter in the book as it provides the student with a systematic approach to more advanced design projects. Chapter 9 outlines experiments that can be performed in the laboratory with hard- ware that is readily available commercially. The operation of the ICs used in the experiments is explained by referring to diagrams of similar components introduced in previous chapters. Each experiment is presented informally and the student is expected to design the circuit and formulate a procedure for checking its operation in the laboratory. The lab experiments can be used in a stand‐alone manner too and can be accomplished by a traditional approach, with a breadboard and TTL circuits, or with an HDL/synthesis approach using FPGAs. Today, software for synthesizing an HDL model and implementing a circuit with an FPGA is available at no cost from vendors of FPGAs, allowing students to conduct a significant amount of work in their personal environment before using prototyping boards and other resources in a lab.  Preface xv Circuit boards for rapid prototyping circuits with FPGAs are available at a nominal cost, and typically include push buttons, switches, seven‐segment displays, LCDs, key- pads, and other I/O devices. With these resources, students can work prescribed lab exercises or their own projects and get results immediately. Chapter 10 presents the standard graphic symbols for logic functions recommended by an ANSI/IEEE standard. These graphic symbols have been developed for small‐scale integration (SSI) and medium‐scale integration (MSI) components so that the user can recognize each function from the unique graphic symbol assigned. The chapter shows the standard graphic symbols of the ICs used in the laboratory experiments. ACKNOWLEDGMENTS We are grateful to the reviewers of Digital Design, 5e. Their expertise, careful reviews, and suggestions helped shape this edition. Dmitri Donetski, Stony Brook University Ali Amini, California State University, Northridge Mihaela Radu, Rose Hulman Institute of Technology Stephen J Kuyath, University of North Carolina, Charlotte Peter Pachowicz, George Mason University David Jeff Jackson, University of Alabama A. John Boye, University of Nebraska, Lincoln William H. Robinson, Vanderbilt University Dinesh Bhatia, University of Texas, Dallas We also wish to express our gratitude to the editorial and publication team at Prentice Hall/Pearson Education for supporting this edition of our text. We are grateful, too, for the ongoing support and encouragement of our wives, Sandra and Jerilynn. M. Morris Mano Emeritus Professor of Computer Engineering California State University, Los Angeles Michael D. Ciletti Emeritus Professor of Electrical and Computer Engineering University of Colorado at Colorado Springs This page intentionally left blank Chapter 1 Digital Systems and Binary Numbers 1.1 D I G I TA L S Y S T E M S Digital systems have such a prominent role in everyday life that we refer to the present technological period as the digital age. Digital systems are used in communication, busi- ness transactions, traffic control, spacecraft guidance, medical treatment, weather mon- itoring, the Internet, and many other commercial, industrial, and scientific enterprises. We have digital telephones, digital televisions, digital versatile discs, digital cameras, handheld devices, and, of course, digital computers. We enjoy music downloaded to our portable media player (e.g., iPod Touch™) and other handheld devices having high‐ resolution displays. These devices have graphical user interfaces (GUIs), which enable them to execute commands that appear to the user to be simple, but which, in fact, involve precise execution of a sequence of complex internal instructions. Most, if not all, of these devices have a special‐purpose digital computer embedded within them. The most striking property of the digital computer is its generality. It can follow a sequence of instructions, called a program, that operates on given data. The user can specify and change the program or the data according to the specific need. Because of this flexibil- ity, general‐purpose digital computers can perform a variety of information‐processing tasks that range over a wide spectrum of applications. One characteristic of digital systems is their ability to represent and manipulate dis- crete elements of information. Any set that is restricted to a finite number of elements contains discrete information. Examples of discrete sets are the 10 decimal digits, the 26 letters of the alphabet, the 52 playing cards, and the 64 squares of a chessboard. Early digital computers were used for numeric computations. In this case, the discrete ele- ments were the digits. From this application, the term digital computer emerged. Dis- crete elements of information are represented in a digital system by physical quantities 1 2 Chapter 1 Digital Systems and Binary Numbers called signals. Electrical signals such as voltages and currents are the most common. Electronic devices called transistors predominate in the circuitry that implements these signals. The signals in most present‐day electronic digital systems use just two discrete values and are therefore said to be binary. A binary digit, called a bit, has two values: 0 and 1. Discrete elements of information are represented with groups of bits called binary codes. For example, the decimal digits 0 through 9 are represented in a digital system with a code of four bits (e.g., the number 7 is represented by 0111). How a pattern of bits is interpreted as a number depends on the code system in which it resides. To make this distinction, we could write (0111)2 to indicate that the pattern 0111 is to be inter- preted in a binary system, and (0111)10 to indicate that the reference system is decimal. Then 01112 = 710, which is not the same as 011110, or one hundred eleven. The subscript indicating the base for interpreting a pattern of bits will be used only when clarification is needed. Through various techniques, groups of bits can be made to represent discrete symbols, not necessarily numbers, which are then used to develop the system in a digital format. Thus, a digital system is a system that manipulates discrete elements of informa- tion represented internally in binary form. In today’s technology, binary systems are most practical because, as we will see, they can be implemented with electronic components. Discrete quantities of information either emerge from the nature of the data being processed or may be quantized from a continuous process. On the one hand, a payroll schedule is an inherently discrete process that contains employee names, social security numbers, weekly salaries, income taxes, and so on. An employee’s paycheck is processed by means of discrete data values such as letters of the alphabet (names), digits (salary), and special symbols (such as $). On the other hand, a research scientist may observe a continuous process, but record only specific quantities in tabular form. The scientist is thus quantizing continuous data, making each number in his or her table a discrete quantity. In many cases, the quantization of a process can be performed automatically by an analog‐to‐digital converter, a device that forms a digital (discrete) representation of a analog (continuous) quantity. The general‐purpose digital computer is the best‐known example of a digital system. The major parts of a computer are a memory unit, a central processing unit, and input– output units. The memory unit stores programs as well as input, output, and intermedi- ate data. The central processing unit performs arithmetic and other data‐processing operations as specified by the program. The program and data prepared by a user are transferred into memory by means of an input device such as a keyboard. An output device, such as a printer, receives the results of the computations, and the printed results are presented to the user. A digital computer can accommodate many input and output devices. One very useful device is a communication unit that provides interaction with other users through the Internet. A digital computer is a powerful instrument that can perform not only arithmetic computations, but also logical operations. In addition, it can be programmed to make decisions based on internal and external conditions. There are fundamental reasons that commercial products are made with digital cir- cuits. Like a digital computer, most digital devices are programmable. By changing the program in a programmable device, the same underlying hardware can be used for many different applications, thereby allowing its cost of development to be spread across a wider customer base. Dramatic cost reductions in digital devices have come about  Section 1.2 Binary Numbers 3 because of advances in digital integrated circuit technology. As the number of transistors that can be put on a piece of silicon increases to produce complex functions, the cost per unit decreases and digital devices can be bought at an increasingly reduced price. Equip- ment built with digital integrated circuits can perform at a speed of hundreds of millions of operations per second. Digital systems can be made to operate with extreme reli- ability by using error‐correcting codes. An example of this strategy is the digital versa- tile disk (DVD), in which digital information representing video, audio, and other data is recorded without the loss of a single item. Digital information on a DVD is recorded in such a way that, by examining the code in each digital sample before it is played back, any error can be automatically identified and corrected. A digital system is an interconnection of digital modules. To understand the opera- tion of each digital module, it is necessary to have a basic knowledge of digital circuits and their logical function. The first seven chapters of this book present the basic tools of digital design, such as logic gate structures, combinational and sequential circuits, and programmable logic devices. Chapter 8 introduces digital design at the register transfer level (RTL) using a modern hardware description language (HDL). Chapter 9 concludes the text with laboratory exercises using digital circuits. A major trend in digital design methodology is the use of a HDL to describe and simulate the functionality of a digital circuit. An HDL resembles a programming language and is suitable for describing digital circuits in textual form. It is used to simulate a digital system to verify its operation before hardware is built. It is also used in conjunction with logic syn- thesis tools to automate the design process. Because it is important that students become familiar with an HDL‐based design methodology, HDL descriptions of digital circuits are presented throughout the book. While these examples help illustrate the features of an HDL, they also demonstrate the best practices used by industry to exploit HDLs. Ignorance of these practices will lead to cute, but worthless, HDL models that may simulate a phenom- enon, but that cannot be synthesized by design tools, or to models that waste silicon area or synthesize to hardware that cannot operate correctly. As previously stated, digital systems manipulate discrete quantities of information that are represented in binary form. Operands used for calculations may be expressed in the binary number system. Other discrete elements, including the decimal digits and characters of the alphabet, are represented in binary codes. Digital circuits, also referred to as logic circuits, process data by means of binary logic elements (logic gates) using binary signals. Quantities are stored in binary (two‐valued) storage elements (flip‐flops). The purpose of this chapter is to introduce the various binary concepts as a frame of reference for further study in the succeeding chapters. 1.2 BINARY NUMBERS A decimal number such as 7,392 represents a quantity equal to 7 thousands, plus 3 hun- dreds, plus 9 tens, plus 2 units. The thousands, hundreds, etc., are powers of 10 implied by the position of the coefficients (symbols) in the number. To be more exact, 7,392 is a shorthand notation for what should be written as 7 * 103 + 3 * 102 + 9 * 101 + 2 * 100 4 Chapter 1 Digital Systems and Binary Numbers However, the convention is to write only the numeric coefficients and, from their posi- tion, deduce the necessary powers of 10 with powers increasing from right to left. In general, a number with a decimal point is represented by a series of coefficients: a5a4a3a2a1a0. a-1a-2a-3 The coefficients aj are any of the 10 digits (0, 1, 2, c , 9), and the subscript value j gives the place value and, hence, the power of 10 by which the coefficient must be multiplied. Thus, the preceding decimal number can be expressed as 105a5 + 104a4 + 103a3 + 102a2 + 101a1 + 100a0 + 10-1a-1 + 10-2a-2 + 10-3a-3 with a3 = 7, a2 = 3, a1 = 9, and a0 = 2. The decimal number system is said to be of base, or radix, 10 because it uses 10 digits and the coefficients are multiplied by powers of 10. The binary system is a different number system. The coefficients of the binary number system have only two possible values: 0 and 1. Each coefficient aj is multiplied by a power of the radix, e.g., 2j, and the results are added to obtain the decimal equivalent of the number. The radix point (e.g., the decimal point when 10 is the radix) distinguishes positive powers of 10 from negative powers of 10. For example, the decimal equivalent of the binary number 11010.11 is 26.75, as shown from the multiplication of the coefficients by powers of 2: 1 * 24 + 1 * 23 + 0 * 22 + 1 * 21 + 0 * 20 + 1 * 2-1 + 1 * 2-2 = 26.75 There are many different number systems. In general, a number expressed in a base‐r system has coefficients multiplied by powers of r: an # r n + an - 1 # r n - 1 + g + a2 # r 2 + a1 # r + a0 + a-1 # r-1 + a-2 # r-2 + g + a-m # r-m The coefficients aj range in value from 0 to r - 1. To distinguish between numbers of different bases, we enclose the coefficients in parentheses and write a subscript equal to the base used (except sometimes for decimal numbers, where the content makes it obvi- ous that the base is decimal). An example of a base‐5 number is (4021.2)5 = 4 * 53 + 0 * 52 + 2 * 51 + 1 * 50 + 2 * 5-1 = (511.4)10 The coefficient values for base 5 can be only 0, 1, 2, 3, and 4. The octal number system is a base‐8 system that has eight digits: 0, 1, 2, 3, 4, 5, 6, 7. An example of an octal number is 127.4. To determine its equivalent decimal value, we expand the number in a power series with a base of 8: (127.4)8 = 1 * 82 + 2 * 81 + 7 * 80 + 4 * 8-1 = (87.5)10 Note that the digits 8 and 9 cannot appear in an octal number. It is customary to borrow the needed r digits for the coefficients from the decimal system when the base of the number is less than 10. The letters of the alphabet are used to supplement the 10 decimal digits when the base of the number is greater than 10. For example, in the hexadecimal (base‐16) number system, the first 10 digits are borrowed  Section 1.2 Binary Numbers 5 from the decimal system. The letters A, B, C, D, E, and F are used for the digits 10, 11, 12, 13, 14, and 15, respectively. An example of a hexadecimal number is (B65F)16 = 11 * 163 + 6 * 162 + 5 * 161 + 15 * 160 = (46,687)10 The hexadecimal system is used commonly by designers to represent long strings of bits in the addresses, instructions, and data in digital systems. For example, B65F is used to represent 1011011001010000. As noted before, the digits in a binary number are called bits. When a bit is equal to 0, it does not contribute to the sum during the conversion. Therefore, the conversion from binary to decimal can be obtained by adding only the numbers with powers of two corresponding to the bits that are equal to 1. For example, (110101)2 = 32 + 16 + 4 + 1 = (53)10 There are four 1’s in the binary number. The corresponding decimal number is the sum of the four powers of two. Zero and the first 24 numbers obtained from 2 to the power of n are listed in Table 1.1. In computer work, 210 is referred to as K (kilo), 220 as M (mega), 230 as G (giga), and 240 as T (tera). Thus, 4K = 212 = 4,096 and 16M = 224 = 16,777,216. Computer capacity is usually given in bytes. A byte is equal to eight bits and can accom- modate (i.e., represent the code of) one keyboard character. A computer hard disk with four gigabytes of storage has a capacity of 4G = 232 bytes (approximately 4 billion bytes). A terabyte is 1024 gigabytes, approximately 1 trillion bytes. Arithmetic operations with numbers in base r follow the same rules as for decimal numbers. When a base other than the familiar base 10 is used, one must be careful to use only the r‐allowable digits. Examples of addition, subtraction, and multiplication of two binary numbers are as follows: augend: 101101 minuend: 101101 multiplicand: 1011 addend: +100111 subtrahend: -100111 multiplier: * 101 sum: 1010100 difference: 000110 1011 0000 partial product: 1011 product: 110111 Table 1.1 Powers of Two n 2n n 2n n 2n 0 1 8 256 16 65,536 1 2 9 512 17 131,072 2 4 10 1,024 (1K) 18 262,144 3 8 11 2,048 19 524,288 4 16 12 4,096 (4K) 20 1,048,576 (1M) 5 32 13 8,192 21 2,097,152 6 64 14 16,384 22 4,194,304 7 128 15 32,768 23 8,388,608 6 Chapter 1 Digital Systems and Binary Numbers The sum of two binary numbers is calculated by the same rules as in decimal, except that the digits of the sum in any significant position can be only 0 or 1. Any carry obtained in a given significant position is used by the pair of digits one significant posi- tion higher. Subtraction is slightly more complicated. The rules are still the same as in decimal, except that the borrow in a given significant position adds 2 to a minuend digit. (A borrow in the decimal system adds 10 to a minuend digit.) Multiplication is simple: The multiplier digits are always 1 or 0; therefore, the partial products are equal either to a shifted (left) copy of the multiplicand or to 0. 1.3 NUMBER‐BASE CONVERSIONS Representations of a number in a different radix are said to be equivalent if they have the same decimal representation. For example, (0011)8 and (1001)2 are equivalent—both have decimal value 9. The conversion of a number in base r to decimal is done by expanding the number in a power series and adding all the terms as shown previously. We now present a general procedure for the reverse operation of converting a decimal number to a number in base r. If the number includes a radix point, it is necessary to separate the number into an integer part and a fraction part, since each part must be converted differently. The conversion of a decimal integer to a number in base r is done by dividing the number and all successive quotients by r and accumulating the remain- ders. This procedure is best illustrated by example. EXAMPLE 1.1 Convert decimal 41 to binary. First, 41 is divided by 2 to give an integer quotient of 20 and a remainder of 12. Then the quotient is again divided by 2 to give a new quotient and remainder. The process is continued until the integer quotient becomes 0. The coefficients of the desired binary number are obtained from the remainders as follows: Integer Remainder Coefficient Quotient 41>2 = 20 + 1 a0 = 1 2 20>2 = 10 + 0 a1 = 0 10>2 = 5 + 0 a2 = 0 5>2 = 2 + 1 a3 = 1 2 2>2 = 1 + 0 a4 = 0 1>2 = 0 + 1 a5 = 1 2 Therefore, the answer is (41)10 = (a5a4a3a2a1a0)2 = (101001)2.  Section 1.3 Number‐Base Conversions 7 The arithmetic process can be manipulated more conveniently as follows: Integer Remainder 41 20 1 10 0 5 0 2 1 1 0 0 1 101001 = answer Conversion from decimal integers to any base‐r system is similar to this example, except that division is done by r instead of 2. EXAMPLE 1.2 Convert decimal 153 to octal. The required base r is 8. First, 153 is divided by 8 to give an integer quotient of 19 and a remainder of 1. Then 19 is divided by 8 to give an integer quotient of 2 and a remainder of 3. Finally, 2 is divided by 8 to give a quotient of 0 and a remainder of 2. This process can be conveniently manipulated as follows: 153 19 1 2 3 0 2 = (231)8 The conversion of a decimal fraction to binary is accomplished by a method similar to that used for integers. However, multiplication is used instead of division, and integers instead of remainders are accumulated. Again, the method is best explained by example. EXAMPLE 1.3 Convert (0.6875)10 to binary. First, 0.6875 is multiplied by 2 to give an integer and a fraction. Then the new fraction is multiplied by 2 to give a new integer and a new fraction. The process is continued until the fraction becomes 0 or until the number of digits has sufficient accuracy. The coefficients of the binary number are obtained from the integers as follows: Integer Fraction Coefficient 0.6875 * 2 = 1 + 0.3750 a-1 = 1 0.3750 * 2 = 0 + 0.7500 a-2 = 0 0.7500 * 2 = 1 + 0.5000 a-3 = 1 0.5000 * 2 = 1 + 0.0000 a-4 = 1 8 Chapter 1 Digital Systems and Binary Numbers Therefore, the answer is (0.6875)10 = (0. a-1 a-2 a-3 a-4)2 = (0.1011)2. To convert a decimal fraction to a number expressed in base r, a similar procedure is used. However, multiplication is by r instead of 2, and the coefficients found from the integers may range in value from 0 to r - 1 instead of 0 and 1. EXAMPLE 1.4 Convert (0.513)10 to octal. 0.513 * 8 = 4.104 0.104 * 8 = 0.832 0.832 * 8 = 6.656 0.656 * 8 = 5.248 0.248 * 8 = 1.984 0.984 * 8 = 7.872 The answer, to seven significant figures, is obtained from the integer part of the products: (0.513)10 = (0.406517 c )8 The conversion of decimal numbers with both integer and fraction parts is done by converting the integer and the fraction separately and then combining the two answers. Using the results of Examples 1.1 and 1.3, we obtain (41.6875)10 = (101001.1011)2 From Examples 1.2 and 1.4, we have (153.513)10 = (231.406517)8 1.4 O C TA L A N D H E X A D E C I M A L N U M B E R S The conversion from and to binary, octal, and hexadecimal plays an important role in digi- tal computers, because shorter patterns of hex characters are easier to recognize than long patterns of 1’s and 0’s. Since 23 = 8 and 24 = 16, each octal digit corresponds to three binary digits and each hexadecimal digit corresponds to four binary digits. The first 16 num- bers in the decimal, binary, octal, and hexadecimal number systems are listed in Table 1.2. The conversion from binary to octal is easily accomplished by partitioning the binary number into groups of three digits each, starting from the binary point and proceeding to the left and to the right. The corresponding octal digit is then assigned to each group. The following example illustrates the procedure: (10 110 001 101 011 # 111 100 000 110)2 = (26153.7406)8 2 6 1 5 3 7 4 0 6  Section 1.4 Octal and Hexadecimal Numbers 9 Table 1.2 Numbers with Different Bases Decimal Binary Octal Hexadecimal (base 10) (base 2) (base 8) (base 16) 00 0000 00 0 01 0001 01 1 02 0010 02 2 03 0011 03 3 04 0100 04 4 05 0101 05 5 06 0110 06 6 07 0111 07 7 08 1000 10 8 09 1001 11 9 10 1010 12 A 11 1011 13 B 12 1100 14 C 13 1101 15 D 14 1110 16 E 15 1111 17 F Conversion from binary to hexadecimal is similar, except that the binary number is divided into groups of four digits: (10 1100 0110 1011 # 1111 0010)2 = (2C6B.F2)16 2 C 6 B F 2 The corresponding hexadecimal (or octal) digit for each group of binary digits is easily remembered from the values listed in Table 1.2. Conversion from octal or hexadecimal to binary is done by reversing the preceding procedure. Each octal digit is converted to its three‐digit binary equivalent. Similarly, each hexadecimal digit is converted to its four‐digit binary equivalent. The procedure is illustrated in the following examples: (673.124)8 = (110 111 011 # 001 010 100)2 6 7 3 1 2 4 and (306.D)16 = (0011 0000 0110 # 1101)2 3 0 6 D Binary numbers are difficult to work with because they require three or four times as many digits as their decimal equivalents. For example, the binary number 111111111111 is equivalent to decimal 4095. However, digital computers use binary numbers, and it is sometimes necessary for the human operator or user to communicate directly with the 10 Chapter 1 Digital Systems and Binary Numbers machine by means of such numbers. One scheme that retains the binary system in the computer, but reduces the number of digits the human must consider, utilizes the rela- tionship between the binary number system and the octal or hexadecimal system. By this method, the human thinks in terms of octal or hexadecimal numbers and performs the required conversion by inspection when direct communication with the machine is nec- essary. Thus, the binary number 111111111111 has 12 digits and is expressed in octal as 7777 (4 digits) or in hexadecimal as FFF (3 digits). During communication between people (about binary numbers in the computer), the octal or hexadecimal representa- tion is more desirable because it can be expressed more compactly with a third or a quarter of the number of digits required for the equivalent binary number. Thus, most computer manuals use either octal or hexadecimal numbers to specify binary quantities. The choice between them is arbitrary, although hexadecimal tends to win out, since it can represent a byte with two digits. 1.5 COMPLEMENTS OF NUMBERS Complements are used in digital computers to simplify the subtraction operation and for logical manipulation. Simplifying operations leads to simpler, less expensive circuits to implement the operations. There are two types of complements for each base‐r system: the radix complement and the diminished radix complement. The first is referred to as the r’s complement and the second as the (r - 1)>s complement. When the value of the base r is substituted in the name, the two types are referred to as the 2’s complement and 1’s complement for binary numbers and the 10’s complement and 9’s complement for decimal numbers. Diminished Radix Complement Given a number N in base r having n digits, the (r - 1)>s complement of N, i.e., its diminished radix complement, is defined as (r n - 1) - N. For decimal numbers, r = 10 and r - 1 = 9, so the 9’s complement of N is (10 n - 1) - N. In this case, 10 n represents a number that consists of a single 1 followed by n 0’s. 10 n - 1 is a number represented by n 9’s. For example, if n = 4, we have 104 = 10,000 and 104 - 1 = 9999. It follows that the 9’s complement of a decimal number is obtained by subtracting each digit from 9. Here are some numerical examples: The 9>s complement of 546700 is 999999 - 546700 = 453299. The 9>s complement of 012398 is 999999 - 012398 = 987601. For binary numbers, r = 2 and r - 1 = 1, so the 1’s complement of N is (2n - 1) - N. Again, 2n is represented by a binary number that consists of a 1 followed by n 0’s. 2n - 1 is a binary number represented by n 1’s. For example, if n = 4, we have 24 = (10000)2 and 24 - 1 = (1111)2. Thus, the 1’s complement of a binary number is obtained by subtracting each digit from 1. However, when subtracting binary digits from 1, we can  Section 1.5 Complements of Numbers 11 have either 1 - 0 = 1 or 1 - 1 = 0, which causes the bit to change from 0 to 1 or from 1 to 0, respectively. Therefore, the 1’s complement of a binary number is formed by changing 1’s to 0’s and 0’s to 1’s. The following are some numerical examples: The 1’s complement of 1011000 is 0100111. The 1’s complement of 0101101 is 1010010. The (r - 1)>s complement of octal or hexadecimal numbers is obtained by subtracting each digit from 7 or F (decimal 15), respectively. Radix Complement The r’s complement of an n‐digit number N in base r is defined as r n - N for N ⬆ 0 and as 0 for N = 0. Comparing with the (r - 1)>s complement, we note that the r’s complement is obtained by adding 1 to the (r - 1)>s complement, since r n - N = [(r n - 1) - N] + 1. Thus, the 10’s complement of decimal 2389 is 7610 + 1 = 7611 and is obtained by adding 1 to the 9’s complement value.The 2’s complement of binary 101100 is 010011 + 1 = 010100 and is obtained by adding 1 to the 1’s‐complement value. Since 10 is a number represented by a 1 followed by n 0’s, 10 n - N, which is the 10’s complement of N, can be formed also by leaving all least significant 0’s unchanged, subtracting the first nonzero least significant digit from 10, and subtracting all higher significant digits from 9. Thus, the 10’s complement of 012398 is 987602 and the 10’s complement of 246700 is 753300 The 10’s complement of the first number is obtained by subtracting 8 from 10 in the least significant position and subtracting all other digits from 9. The 10’s complement of the second number is obtained by leaving the two least significant 0’s unchanged, subtract- ing 7 from 10, and subtracting the other three digits from 9. Similarly, the 2’s complement can be formed by leaving all least significant 0’s and the first 1 unchanged and replacing 1’s with 0’s and 0’s with 1’s in all other higher sig- nificant digits. For example, the 2’s complement of 1101100 is 0010100 and the 2’s complement of 0110111 is 1001001 The 2’s complement of the first number is obtained by leaving the two least significant 0’s and the first 1 unchanged and then replacing 1’s with 0’s and 0’s with 1’s in the other four most significant digits. The 2’s complement of the second number is obtained by leaving the least significant 1 unchanged and complementing all other digits. 12 Chapter 1 Digital Systems and Binary Numbers In the previous definitions, it was assumed that the numbers did not have a radix point. If the original number N contains a radix point, the point should be removed temporarily in order to form the r’s or (r - 1)>s complement. The radix point is then restored to the complemented number in the same relative position. It is also worth mentioning that the complement of the complement restores the number to its original value. To see this relationship, note that the r’s complement of N is r n - N, so that the complement of the complement is r n - (r n - N) = N and is equal to the original number. Subtraction with Complements The direct method of subtraction taught in elementary schools uses the borrow concept. In this method, we borrow a 1 from a higher significant position when the minuend digit is smaller than the subtrahend digit. The method works well when people perform sub- traction with paper and pencil. However, when subtraction is implemented with digital hardware, the method is less efficient than the method that uses complements. The subtraction of two n‐digit unsigned numbers M - N in base r can be done as follows: 1. Add the minuend M to the r’s complement of the subtrahend N. Mathematically, M + (r n - N) = M - N + r n. 2. If M Ú N, the sum will produce an end carry r n, which can be discarded; what is left is the result M - N. 3. If M 6 N, the sum does not produce an end carry and is equal to r n - (N - M), which is the r’s complement of (N - M). To obtain the answer in a familiar form, take the r’s complement of the sum and place a negative sign in front. The following examples illustrate the procedure: EXAMPLE 1.5 Using 10’s complement, subtract 72532 - 3250. M = 72532 10>s complement of N = + 96750 Sum = 169282 Discard end carry 105 = - 100000 Answer = 69282 Note that M has five digits and N has only four digits. Both numbers must have the same number of digits, so we write N as 03250. Taking the 10’s complement of N produces a 9 in the most significant position. The occurrence of the end carry signifies that M Ú N and that the result is therefore positive.  Section 1.5 Complements of Numbers 13 EXAMPLE 1.6 Using 10’s complement, subtract 3250 - 72532. M = 03250 10>s complement of N = + 27468 Sum = 30718 There is no end carry. Therefore, the answer is -(10>s complement of 30718) = -69282. Note that since 3250 6 72532, the result is negative. Because we are dealing with unsigned numbers, there is really no way to get an unsigned result for this case. When subtracting with complements, we recognize the negative answer from the absence of the end carry and the complemented result. When working with paper and pencil, we can change the answer to a signed negative number in order to put it in a famil- iar form. Subtraction with complements is done with binary numbers in a similar manner, using the procedure outlined previously. EXAMPLE 1.7 Given the two binary numbers X = 1010100 and Y = 1000011, perform the subtraction (a) X - Y and (b) Y - X by using 2’s complements. (a) X = 1010100 2>s complement of Y = + 0111101 Sum = 10010001 Discard end carry 27 = - 10000000 Answer: X - Y = 0010001 (b) Y = 1000011 2>s complement of X = + 0101100 Sum = 1101111 There is no end carry. Therefore, the answer is Y - X = -(2>s complement of 1101111) = -0010001. Subtraction of unsigned numbers can also be done by means of the (r - 1)>s com- plement. Remember that the (r - 1)>s complement is one less than the r’s comple- ment. Because of this, the result of adding the minuend to the complement of the subtrahend produces a sum that is one less than the correct difference when an end carry occurs. Removing the end carry and adding 1 to the sum is referred to as an end‐around carry. 14 Chapter 1 Digital Systems and Binary Numbers EXAMPLE 1.8 Repeat Example 1.7, but this time using 1’s complement. (a) X - Y = 1010100 - 1000011 X = 1010100 1>s complement of Y = + 0111100 Sum = 10010000 End@around carry = + 1 Answer: X - Y = 0010001 (b) Y - X = 1000011 - 1010100 Y = 1000011 1>s complement of X = + 0101011 Sum = 1101110 There is no end carry. Therefore, the answer is Y - X = -(1>s complement of 1101110) = -0010001. Note that the negative result is obtained by taking the 1’s complement of the sum, since this is the type of complement used. The procedure with end‐around carry is also appli- cable to subtracting unsigned decimal numbers with 9’s complement. 1.6 SIGNED BINARY NUMBERS Positive integers (including zero) can be represented as unsigned numbers. However, to represent negative integers, we need a notation for negative values. In ordinary arith- metic, a negative number is indicated by a minus sign and a positive number by a plus sign. Because of hardware limitations, computers must represent everything with binary digits. It is customary to represent the sign with a bit placed in the leftmost position of the number. The convention is to make the sign bit 0 for positive and 1 for negative. It is important to realize that both signed and unsigned binary numbers consist of a string of bits when represented in a computer. The user determines whether the number is signed or unsigned. If the binary number is signed, then the leftmost bit represents the sign and the rest of the bits represent the number. If the binary number is assumed to be unsigned, then the leftmost bit is the most significant bit of the number. For example, the string of bits 01001 can be considered as 9 (unsigned binary) or as +9 (signed binary) because the leftmost bit is 0. The string of bits 11001 represents the binary equivalent of 25 when considered as an unsigned number and the binary equivalent of -9 when con- sidered as a signed number. This is because the 1 that is in the leftmost position designates a negative and the other four bits represent binary 9. Usually, there is no confusion in interpreting the bits if the type of representation for the number is known in advance.  Section 1.6 Signed Binary Numbers 15 The representation of the signed numbers in the last example is referred to as the signed‐magnitude convention. In this notation, the number consists of a magnitude and a symbol ( + or - ) or a bit (0 or 1) indicating the sign. This is the representation of signed numbers used in ordinary arithmetic. When arithmetic operations are implemented in a computer, it is more convenient to use a different system, referred to as the signed‐ complement system, for representing negative numbers. In this system, a negative num- ber is indicated by its complement. Whereas the signed‐magnitude system negates a number by changing its sign, the signed‐complement system negates a number by taking its complement. Since positive numbers always start with 0 (plus) in the leftmost posi- tion, the complement will always start with a 1, indicating a negative number. The signed‐complement system can use either the 1’s or the 2’s complement, but the 2’s complement is the most common. As an example, consider the number 9, represented in binary with eight bits. +9 is represented with a sign bit of 0 in the leftmost position, followed by the binary equiva- lent of 9, which gives 00001001. Note that all eight bits must have a value; therefore, 0’s are inserted following the sign bit up to the first 1. Although there is only one way to represent +9, there are three different ways to represent -9 with eight bits: signed‐magnitude representation: 10001001 signed‐1’s‐complement representation: 11110110 signed‐2’s‐complement representation: 11110111 In signed‐magnitude, -9 is obtained from +9 by changing only the sign bit in the leftmost position from 0 to 1. In signed‐1’s-complement, -9 is obtained by complementing all the bits of +9, including the sign bit. The signed‐2’s‐complement representation of -9 is obtained by taking the 2’s complement of the positive number, including the sign bit. Table 1.3 lists all possible four‐bit signed binary numbers in the three representations. The equivalent decimal number is also shown for reference. Note that the positive num- bers in all three representations are identical and have 0 in the leftmost position. The signed‐2’s‐complement system has only one representation for 0, which is always posi- tive. The other two systems have either a positive 0 or a negative 0, something not encountered in ordinary arithmetic. Note that all negative numbers have a 1 in the leftmost bit position; that is the way we distinguish them from the positive numbers. With four bits, we can represent 16 binary numbers. In the signed‐magnitude and the 1’s‐complement representations, there are eight positive numbers and eight negative numbers, including two zeros. In the 2’s‐complement representation, there are eight positive numbers, including one zero, and eight negative numbers. The signed‐magnitude system is used in ordinary arithmetic, but is awkward when employed in computer arithmetic because of the separate handling of the sign and the magnitude. Therefore, the signed‐complement system is normally used. The 1’s com- plement imposes some difficulties and is seldom used for arithmetic operations. It is useful as a logical operation, since the change of 1 to 0 or 0 to 1 is equivalent to a logical complement operation, as will be shown in the next chapter. The discussion of signed binary arithmetic that follows deals exclusively with the signed‐2’s‐complement 16 Chapter 1 Digital Systems and Binary Numbers Table 1.3 Signed Binary Numbers Signed‐2’s Signed‐1’s Signed Decimal Complement Complement Magnitude +7 0111 0111 0111 +6 0110 0110 0110 +5 0101 0101 0101 +4 0100 0100 0100 +3 0011 0011 0011 +2 0010 0010 0010 +1 0001 0001 0001 +0 0000 0000 0000 -0 — 1111 1000 -1 1111 1110 1001 -2 1110 1101 1010 -3 1101 1100 1011 -4 1100 1011 1100 -5 1011 1010 1101 -6 1010 1001 1110 -7 1001 1000 1111 -8 1000 — — representation of negative numbers. The same procedures can be applied to the signed‐1’s‐complement system by including the end‐around carry as is done with unsigned numbers. Arithmetic Addition The addition of two numbers in the signed‐magnitude system follows the rules of ordinary arithmetic. If the signs are the same, we add the two magnitudes and give the sum the common sign. If the signs are different, we subtract the smaller magni- tude from the larger and give the difference the sign of the larger magnitude. For example, ( +25) + ( -37) = -(37 - 25) = -12 is done by subtracting the smaller mag- nitude, 25, from the larger magnitude, 37, and appending the sign of 37 to the result. This is a process that requires a comparison of the signs and magnitudes and then per- forming either addition or subtraction. The same procedure applies to binary numbers in signed‐magnitude representation. In contrast, the rule for adding numbers in the signed‐complement system does not require a comparison or subtraction, but only addition. The procedure is very simple and can be stated as follows for binary numbers: The addition of two signed binary numbers with negative numbers represented in signed‐2’s‐complement form is obtained from the addition of the two numbers, includ- ing their sign bits. A carry out of the sign‐bit position is discarded.  Section 1.6 Signed Binary Numbers 17 Numerical examples for addition follow: + 6 00000110 - 6 11111010 +13 00001101 +13 00001101 +19 00010011 + 7 00000111 + 6 00000110 - 6 11111010 -13 11110011 -13 11110011 - 7 11111001 -19 11101101 Note that negative numbers must be initially in 2’s‐complement form and that if the sum obtained after the addition is negative, it is in 2’s‐complement form. For example, -7 is represented as 11111001, which is the 2s complement of +7. In each of the four cases, the operation performed is addition with the sign bit included. Any carry out of the sign‐bit position is discarded, and negative results are automatically in 2’s‐complement form. In order to obtain a correct answer, we must ensure that the result has a sufficient number of bits to accommodate the sum. If we start with two n‐bit numbers and the sum occupies n + 1 bits, we say that an overflow occurs. When one performs the addition with paper and pencil, an overflow is not a problem, because we are not limited by the width of the page. We just add another 0 to a positive number or another 1 to a negative number in the most significant position to extend the number to n + 1 bits and then perform the addition. Overflow is a problem in computers because the number of bits that hold a number is finite, and a result that exceeds the finite value by 1 cannot be accommodated. The complement form of representing negative numbers is unfamiliar to those used to the signed‐magnitude system. To determine the value of a negative number in signed‐2’s complement, it is necessary to convert the number to a positive number to place it in a more familiar form. For example, the signed binary number 11111001 is negative because the leftmost bit is 1. Its 2’s complement is 00000111, which is the binary equivalent of +7. We therefore recognize the original negative number to be equal to -7. Arithmetic Subtraction Subtraction of two signed binary numbers when negative numbers are in 2’s‐complement form is simple and can be stated as follows: Take the 2’s complement of the subtrahend (including the sign bit) and add it to the minuend (including the sign bit). A carry out of the sign‐bit position is discarded. This procedure is adopted because a subtraction operation can be changed to an addi- tion operation if the sign of the subtrahend is changed, as is demonstrated by the following relationship: ( {A) - (+B) = ( {A) + (-B); ( {A) - (-B) = ( {A) + (+B). But changing a positive number to a negative number is easily done by taking the 2’s complement of the positive number. The reverse is also true, because the complement 18 Chapter 1 Digital Systems and Binary Numbers of a negative number in complement form produces the equivalent positive number. To see this, consider the subtraction ( -6) - ( -13) = +7. In binary with eight bits, this operation is written as (11111010 - 11110011). The subtraction is changed to addition by taking the 2’s complement of the subtrahend (-13), giving (+13). In binary, this is 11111010 + 00001101 = 100000111. Removing the end carry, we obtain the correct answer: 00000111 ( +7). It is worth noting that binary numbers in the signed‐complement system are added and subtracted by the same basic addition and subtraction rules as unsigned numbers. Therefore, computers need only one common hardware circuit to handle both types of arithmetic. This consideration has resulted in the signed‐complement system being used in virtually all arithmetic units of computer systems. The user or programmer must interpret the results of such addition or subtraction differently, depending on whether it is assumed that the numbers are signed or unsigned. 1.7 BINARY CODES Digital systems use signals that have two distinct values and circuit elements that have two stable states. There is a direct analogy among binary signals, binary circuit elements, and binary digits. A binary number of n digits, for example, may be repre- sented by n binary circuit elements, each having an output signal equivalent to 0 or 1. Digital systems represent and manipulate not only binary numbers, but also many other discrete elements of information. Any discrete element of information that is distinct among a group of quantities can be represented with a binary code (i.e., a pattern of 0’s and 1’s). The codes must be in binary because, in today’s technology, only circuits that represent and manipulate patterns of 0’s and 1’s can be manufac- tured economically for use in computers. However, it must be realized that binary codes merely change the symbols, not the meaning of the elements of information that they represent. If we inspect the bits of a computer at random, we will find that most of the time they represent some type of coded information rather than binary numbers. An n‐bit binary code is a group of n bits that assumes up to 2n distinct combinations of 1’s and 0’s, with each combination representing one element of the set that is being coded. A set of four elements can be coded with two bits, with each element assigned one of the following bit combinations: 00, 01, 10, 11. A set of eight elements requires a three‐bit code and a set of 16 elements requires a four‐bit code. The bit combination of an n‐bit code is determined from the count in binary from 0 to 2n - 1. Each element must be assigned a unique binary bit combination, and no two elements can have the same value; otherwise, the code assignment will be ambiguous. Although the minimum number of bits required to code 2 n distinct quantities is n, there is no maximum number of bits that may be used for a binary code. For example, the 10 decimal digits can be coded with 10 bits, and each decimal digit can be assigned a bit combination of nine 0’s and a 1. In this particular binary code, the digit 6 is assigned the bit combination 0001000000.  Section 1.7 Binary Codes 19 Binary-Coded Decimal Code Although the binary number system is the most natural system for a computer because it is readily represented in today’s electronic technology, most people are more accus- tomed to the decimal system. One way to resolve this difference is to convert decimal numbers to binary, perform all arithmetic calculations in binary, and then convert the binary results back to decimal. This method requires that we store decimal numbers in the computer so that they can be converted to binary. Since the computer can accept only binary values, we must represent the decimal digits by means of a code that contains 1’s and 0’s. It is also possible to perform the arithmetic operations directly on decimal numbers when they are stored in the computer in coded form. A binary code will have some unassigned bit combinations if the number of elements in the set is not a multiple power of 2. The 10 decimal digits form such a set. A binary code that distinguishes among 10 elements must contain at least four bits, but 6 out of the 16 possible combinations remain unassigned. Different binary codes can be obtained by arranging four bits into 10 distinct combinations. The code most commonly used for the decimal digits is the straight binary assignment listed in Table 1.4. This scheme is called binary‐coded decimal and is commonly referred to as BCD. Other decimal codes are possible and a few of them are presented later in this section. Table 1.4 gives the four‐bit code for one decimal digit. A number with k decimal digits will require 4k bits in BCD. Decimal 396 is represented in BCD with 12 bits as 0011 1001 0110, with each group of 4 bits representing one decimal digit. A decimal number in BCD is the same as its equivalent binary number only when the number is between 0 and 9. A BCD number greater than 10 looks different from its equivalent binary number, even though both contain 1’s and 0’s. Moreover, the binary combina- tions 1010 through 1111 are not used and have no meaning in BCD. Consider decimal 185 and its corresponding value in BCD and binary: (185)10 = (0001 1000 0101)BCD = (10111001)2 Table 1.4 Binary‐Coded Decimal (BCD) Decimal BCD Symbol Digit 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001 20 Chapter 1 Digital Systems and Binary Numbers The BCD value has 12 bits to encode the characters of the decimal value, but the equiv- alent binary number needs only 8 bits. It is obvious that the representation of a BCD number needs more bits than its equivalent binary value. However, there is an advantage in the use of decimal numbers, because computer input and output data are generated by people who use the decimal system. It is important to realize that BCD numbers are decimal numbers and not binary numbers, although they use bits in their representation. The only difference between a decimal number and BCD is that decimals are written with the symbols 0, 1, 2, c , 9 and BCD numbers use the binary code 0000, 0001, 0010, c , 1001. The decimal value is exactly the same. Decimal 10 is represented in BCD with eight bits as 0001 0000 and decimal 15 as 0001 0101. The corresponding binary values are 1010 and 1111 and have only four bits. BCD Addition Consider the addition of two decimal digits in BCD, together with a possible carry from a previous less significant pair of digits. Since each digit does not exceed 9, the sum cannot be greater than 9 + 9 + 1 = 19, with the 1 being a previous carry. Sup- pose we add the BCD digits as if they were binary numbers. Then the binary sum will produce a result in the range from 0 to 19. In binary, this range will be from 0000 to 10011, but in BCD, it is from 0000 to 1 1001, with the first (i.e., leftmost) 1 being a carry and the next four bits being the BCD sum. When the binary sum is equal to or less than 1001 (without a carry), the corresponding BCD digit is correct. However, when the binary sum is greater than or equal to 1010, the result is an invalid BCD digit. The addition of 6 = (0110)2 to the binary sum converts it to the correct digit and also produces a carry as required. This is because a carry in the most significant bit position of the binary sum and a decimal carry differ by 16 - 10 = 6. Consider the following three BCD additions: 4 0100 4 0100 8 1000 +5 +0101 +8 +1000 +9 1001 9 1001 12 1100 17 10001 +0110 +0110 10010 10111 In each case, the two BCD digits are added as if they were two binary numbers. If the binary sum is greater than or equal to 1010, we add 0110 to obtain the correct BCD sum and a carry. In the first example, the sum is equal to 9 and is the correct BCD sum. In the second example, the binary sum produces an invalid BCD digit. The addition of 0110 produces the correct BCD sum, 0010 (i.e., the number 2), and a carry. In the third example, the binary sum produces a carry. This condition occurs when the sum is greater than or equal to 16. Although the other four bits are less than 1001, the binary sum requires a correction because of the carry. Adding 0110, we obtain the required BCD sum 0111 (i.e., the number 7) and a BCD carry.  Section 1.7 Binary Codes 21 The addition of two n‐digit unsigned BCD numbers follows the same procedure. Consider the addition of 184 + 576 = 760 in BCD: BCD 1 1 0001 1000 0100 184 +0101 0111 0110 +576 Binary sum 0111 10000 1010 Add 6 0110 0110 BCD sum 0111 0110 0000 760 The first, least significant pair of BCD digits produces a BCD digit sum of 0000 and a carry for the next pair of digits. The second pair of BCD digits plus a previous carry produces a digit sum of 0110 and a carry for the next pair of digits. The third pair of digits plus a carry produces a binary sum of 0111 and does not require a correction. Decimal Arithmetic The representation of signed decimal numbers in BCD is similar to the representation of signed numbers in binary. We can use either the familiar signed‐magnitude system or the signed‐complement system. The sign of a decimal number is usually represented with four bits to conform to the four‐bit code of the decimal digits. It is customary to designate a plus with four 0’s and a minus with the BCD equivalent of 9, which is 1001. The signed‐magnitude system is seldom used in computers. The signed‐complement system can be either the 9’s or the 10’s complement, but the 10’s complement is the one most often used. To obtain the 10’s complement of a BCD number, we first take the 9’s complement and then add 1 to the least significant digit. The 9’s complement is calcu- lated from the subtraction of each digit from 9. The procedures developed for the signed‐2’s‐complement system in the previous section also apply to the signed‐10’s‐complement system for decimal numbers. Addition is done by summing all digits, including the sign digit, and discarding the end carry. This operation assumes that all negative numbers are in 10’s‐complement form. Consider the addition ( +375) + ( -240) = +135, done in the signed‐complement system: 0 375 +9 760 0 135 The 9 in the leftmost position of the second number represents a minus, and 9760 is the 10’s complement of 0240. The two numbers are added and the end carry is dis- carded to obtain +135. Of course, the decimal numbers inside the computer, including the sign digits, must be in BCD. The addition is done with BCD digits as described previously. The subtraction of decimal numbers, either unsigned or in the signed‐10’s‐complement system, is the same as in the binary case: Take the 10’s complement of the subtrahend and