July 10, 2002 12:54
`
`vra23151_fmt
`
`Sheet number 1 Page number i
`
`black
`
`Fundamentals
`of
`Digital Logic with Verilog Design
`
`Stephen Brown and Zvonko Vranesic
`Department of Electrical and Computer Engineering
`University of Toronto
`
`Boston Burr Ridge, IL Dubuque, IA Madison, WI New York San Francisco St. Louis
`Bangkok Bogotá Caracas Kuala Lumpur Lisbon London Madrid Mexico City
`Milan Montreal New Delhi Santiago Seoul Singapore Sydney Taipei Toronto
`
`1
`
`APPLE 1009
`
`

`

`July 15, 2002 09:50
`
`vra23151_cop
`
`Sheet number 1 Page number ii
`
`black
`
`McGraw-Hill Higher Education
`A Division of The McGraw-Hill Companies
`
`FUNDAMENTALS OF DIGITAL LOGIC WITH VERILOG DESIGN
`
`Published by McGraw-Hill, a business unit of The McGraw-Hill Companies, Inc., 1221 Avenue of the Americas,
`New York, NY 10020. Copyright © 2003 by The McGraw-Hill Companies, Inc. All rights reserved. No part of
`this publication may be reproduced or distributed in any form or by any means, or stored in a database or
`retrieval system, without the prior written consent of The McGraw-Hill Companies, Inc., including, but not
`limited to, in any network or other electronic storage or transmission, or broadcast for distance learning.
`
`Some ancillaries, including electronic and print components, may not be available to customers outside the
`United States.
`
`This book is printed on acid-free paper.
`
`International 1 2 3 4 5 6 7 8 9 0QPF/QPF 0 9 8 7 6 5 4 3 2
`Domestic
`1 2 3 4 5 6 7 8 9 0QPF/QPF 0 9 8 7 6 5 4 3 2
`
`ISBN 0-07-282315-1
`ISBN 0-07-121322-8 (ISE)
`
`Publisher: Elizabeth A. Jones
`Senior sponsoring editor: Carlise Paulson
`Administrative assistant: Michaela M. Graham
`Executive marketing manager: John Wannemacher
`Senior project manager: Jill R. Peter
`Production supervisor: Kara Kudronowicz
`Lead media project manager: Judi David
`Senior media technology producer: Phillip Meek
`Coordinator of freelance design: Michelle D. Whitaker
`Cover designer: Rokusek Design
`Cover image: Stephen Brown and Zvonko Vranesic
`Senior photo research coordinator: Lori Hancock
`Compositor: Techsetters, Inc.
`Typeface: 10/12 Times Roman
`Printer: Quebecor World Fairfield, PA
`
`Library of Congress Cataloging-in-Publication Data
`
`Brown, Stephen D.
`Fundamentals of digital logic with Verilog design / Stephen D. Brown, Zvonko G. Vranesic.—1st ed.
`p.
`cm. (McGraw-Hill Series in electrical and computer engineering)
`Includes index.
`ISBN 0-07-282315-1
`1. Logic circuits—Design and construction—Data processing. 2. Verilog (Computer hardware
`description language). 3. Computer-aided design.
`I. Vranesic, Zvonko G.
`II. Title.
`III. Series.
`
`TK7868.L6 B76 2003
`(cid:1)
`621.39
`2—dc21
`
`2002071439
`CIP
`
`INTERNATIONAL EDITION ISBN 0-07-121322-8
`Copyright © 2003. Exclusive rights by The McGraw-Hill Companies, Inc., for manufacture and export. This
`book cannot be re-exported from the country to which is is sold by McGraw-Hill. The International Edition is
`not available in North America.
`
`www.mhhe.com
`
`2
`
`

`

`June 14, 2002 09:52
`
`vra23151_ded
`
`Sheet number 1 Page number iii
`
`black
`
`To Susan and Anne
`
`3
`
`

`

`June 20, 2002 09:49
`
`vra23151_ata
`
`Sheet number 1 Page number v
`
`black
`
`About the Authors
`
`Stephen Brown received his B.A.Sc. degree in Electrical Engineering from the University
`of New Brunswick, Canada, and the M.A.Sc. and Ph.D. degrees in Electrical Engineering
`from the University of Toronto. He joined the University of Toronto faculty in 1992, where
`he is now an Associate Professor in the Department of Electrical & Computer Engineering.
`He is also Director of Software Development at the Altera Toronto Technology Center.
`His research interests include field-programmable VLSI technology and computer
`architecture. He won the Canadian Natural Sciences and Engineering Research Council’s
`1992 Doctoral Prize for the best Ph.D. thesis in Canada.
`He has won four awards for excellence in teaching electrical engineering, computer
`engineering, and computer science courses. He is a coauthor of two other books: Funda-
`mentals of Digital Logic with VHDL Design and Field-Programmable Gate Arrays.
`
`Zvonko Vranesic received his B.A.Sc., M.A.Sc., and Ph.D. degrees, all in Electrical Engi-
`neering, from the University of Toronto. From 1963–1965, he worked as a design engineer
`with the Northern Electric Co. Ltd. in Bramalea, Ontario. In 1968 he joined the University
`of Toronto, where he is now a Professor in the Departments of Electrical & Computer Engi-
`neering and Computer Science. During the 1978–79 academic year, he was a Senior Visitor
`at the University of Cambridge, England, and during 1984–85 he was at the University of
`Paris, 6. From 1995 to 2000 he served as Chair of the Division of Engineering Science at
`the University of Toronto. He is also involved in research and development at the Altera
`Toronto Technology Center.
`His current research interests include computer architecture, field-programmable VLSI
`technology, and multiple-valued logic systems.
`He is a coauthor of four other books: Computer Organization, 5th ed.; Fundamentals
`of Digital Logic with VHDL Design; Microcomputer Structures; and Field-Programmable
`Gate Arrays. In 1990, he received the Wighton Fellowship for “innovative and distinctive
`contributions to undergraduate laboratory instruction.”
`He has represented Canada in numerous chess competitions. He holds the title of
`International Master.
`
`v
`
`4
`
`

`

`June 13, 2002 15:36
`
`vra23151_ch06
`
`Sheet number 15 Page number 311
`
`black
`
`6.2 Decoders
`
`311
`
`+ w2fw2
`f = w2fw2
`= w2(w3 + w1w4) + w2(w1w3 + w3w4)
`= fw2; hence only two 3-LUTs are needed, as illustrated in Figure 6.14b.
`Observe that f w2
`+ w2f w2.
`The LUT on the right implements the two-variable function w2fw2
`Since it is possible to implement any logic function using multiplexers, general-purpose
`chips exist that contain multiplexers as their basic logic resources. Both Actel Corporation
`[2] and QuickLogic Corporation [3] offer FPGAs in which the logic block comprises an ar-
`rangement of multiplexers. Texas Instruments offers gate array chips that have multiplexer-
`based logic blocks [4].
`
`6.2 Decoders
`
`Decoder circuits are used to decode encoded information. A binary decoder, depicted in
`Figure 6.15, is a logic circuit with n inputs and 2n outputs. Only one output is asserted
`at a time, and each output corresponds to one valuation of the inputs. The decoder also
`has an enable input, En, that is used to disable the outputs; if En = 0, then none of the
`decoder outputs is asserted. If En = 1, the valuation of wn−1 ···w 1w0 determines which of
`the outputs is asserted. An n-bit binary code in which exactly one of the bits is set to 1 at a
`time is referred to as one-hot encoded, meaning that the single bit that is set to 1 is deemed
`to be “hot.” The outputs of a binary decoder are one-hot encoded.
`A 2-to-4 decoder is given in Figure 6.16. The two data inputs are w1 and w0. They
`represent a two-bit number that causes the decoder to assert one of the outputs y0, . . . ,y 3.
`Although a decoder can be designed to have either active-high or active-low outputs, in
`Figure 6.16 active-high outputs are assumed. Setting the inputs w1w0 to 00, 01, 10, or 11
`causes the output y0, y1, y2, or y3 to be set to 1, respectively. A graphical symbol for the
`decoder is given in part (b) of the figure, and a logic circuit is shown in part (c).
`Larger decoders can be built using the sum-of-products structure in Figure 6.16c, or
`else they can be constructed from smaller decoders. Figure 6.17 shows how a 3-to-8 decoder
`is built with two 2-to-4 decoders. The w2 input drives the enable inputs of the two decoders.
`The top decoder is enabled if w2 = 0, and the bottom decoder is enabled if w2 = 1. This
`concept can be applied for decoders of any size. Figure 6.18 shows how five 2-to-4 decoders
`can be used to construct a 4-to-16 decoder. Because of its treelike structure, this type of
`circuit is often referred to as a decoder tree.
`
`n
`inputs
`
`Enable
`
`w0
`
`y0
`
`wn 1–
`
`En
`
`y2n 1–
`
`2n
`outputs
`
`Figure 6.15
`
`An n-to-2n binary decoder.
`
`5
`
`

`

`June 13, 2002 15:36
`
`vra23151_ch06
`
`Sheet number 16 Page number 312
`
`black
`
`312
`
`C H A P T E R 6
`
`•
`
`Combinational-Circuit Building Blocks
`
`w0
`w1
`
`En
`
`y0
`y1
`y2
`y3
`
`y0
`
`y1
`
`y2
`
`y3
`
`0
`
`0 0 1
`
`0
`
`0
`
`0 1 0
`
`0
`
`0
`
`1 0 0
`
`0
`
`1
`
`0 0 0
`
`0
`
`0w
`
`0
`
`1 0 1
`
`x
`
`En
`
`w1
`
`0 0 1 1
`
`x
`
`1 1
`
`01 1
`
`(a) Truth table
`
`(b) Graphical symbol
`
`w0
`
`w1
`
`En
`
`y0
`
`y1
`
`y2
`
`y3
`
`(c) Logic circuit
`
`Figure 6.16
`
`A 2-to-4 decoder.
`
`w0
`w1
`
`w2
`
`En
`
`w0
`w1
`
`En
`
`w0
`w1
`
`En
`
`y0
`y1
`y2
`y3
`
`y0
`y1
`y2
`y3
`
`y0
`y1
`y2
`y3
`
`y4
`y5
`y6
`y7
`
`Figure 6.17
`
`A 3-to-8 decoder using two 2-to-4 decoders.
`
`6
`
`

`

`June 13, 2002 15:36
`
`vra23151_ch06
`
`Sheet number 17 Page number 313
`
`black
`
`6.2 Decoders
`
`313
`
`w0
`w1
`
`w2
`w3
`
`En
`
`w0
`w1
`
`En
`
`y0
`y1
`y2
`y3
`
`w0
`w1
`
`En
`
`w0
`w1
`
`En
`
`w0
`w1
`
`En
`
`w0
`w1
`
`En
`
`y0
`y1
`y2
`y3
`
`y0
`y1
`y2
`y3
`
`y0
`y1
`y2
`y3
`
`y0
`y1
`y2
`y3
`
`y0
`y1
`y2
`y3
`
`y4
`y5
`y6
`y7
`
`y8
`y9
`y10
`y11
`
`y12
`y13
`y14
`y15
`
`Figure 6.18
`
`A 4-to-16 decoder built using a decoder tree.
`
`Decoders are useful for many practical purposes. In Figure 6.2c we showed the sum-of-
`products implementation of the 4-to-1 multiplexer, which requires AND gates to distinguish
`the four different valuations of the select inputs s1 and s0. Since a decoder evaluates the
`values on its inputs, it can be used to build a multiplexer as illustrated in Figure 6.19. The
`enable input of the decoder is not needed in this case, and it is set to 1. The four outputs of
`the decoder represent the four valuations of the select inputs.
`
`Example 6.9
`
`In Figure 3.59 we showed how a 2-to-1 multiplexer can be constructed using two tri-state
`buffers. This concept can be applied to any size of multiplexer, with the addition of a
`decoder. An example is shown in Figure 6.20. The decoder enables one of the tri-state
`buffers for each valuation of the select lines, and that tri-state buffer drives the output, f ,
`with the selected data input. We have now seen that multiplexers can be implemented in
`various ways. The choice of whether to employ the sum-of-products form, transmission
`gates, or tri-state buffers depends on the resources available in the chip being used. For
`
`Example 6.10
`
`7
`
`

`

`June 13, 2002 15:36
`
`vra23151_ch06
`
`Sheet number 18 Page number 314
`
`black
`
`314
`
`C H A P T E R 6
`
`•
`
`Combinational-Circuit Building Blocks
`
`s0
`s1
`
`1
`
`w0
`w1
`
`En
`
`y0
`y1
`y2
`y3
`
`w0
`
`w1
`
`w2
`
`w3
`
`f
`
`Figure 6.19
`
`A 4-to-1 multiplexer built using a decoder.
`
`instance, most FPGAs that use lookup tables for their logic blocks do not contain tri-state
`buffers. Hence multiplexers must be implemented in the sum-of-products form using the
`lookup tables (see problem 6.15).
`
`6.2.1 Demultiplexers
`We showed in section 6.1 that a multiplexer has one output, n data inputs, and (cid:5) log2n (cid:6)
`select inputs. The purpose of the multiplexer circuit is to multiplex the n data inputs onto
`the single data output under control of the select inputs. A circuit that performs the opposite
`function, namely, placing the value of a single data input onto multiple data outputs, is
`
`s0
`s1
`
`1
`
`w0
`w1
`
`En
`
`y0
`y1
`y2
`y3
`
`w0
`
`w1
`
`w2
`
`w3
`
`f
`
`Figure 6.20
`
`A 4-to-1 multiplexer built using a decoder and tri-state
`buffers.
`
`8
`
`

`

`June 13, 2002 15:36
`
`vra23151_ch06
`
`Sheet number 19 Page number 315
`
`black
`
`6.2 Decoders
`
`315
`
`called a demultiplexer. The demultiplexer can be implemented using a decoder circuit. For
`example, the 2-to-4 decoder in Figure 6.16 can be used as a 1-to-4 demultiplexer. In this
`case the En input serves as the data input for the demultiplexer, and the y0 to y3 outputs
`are the data outputs. The valuation of w1w0 determines which of the outputs is set to the
`value of En. To see how the circuit works, consider the truth table in Figure 6.16a. When
`En = 0, all the outputs are set to 0, including the one selected by the valuation of w1w0.
`When En = 1, the valuation of w1w0 sets the appropriate output to 1.
`In general, an n-to-2n decoder circuit can be used as a 1-to-n demultiplexer. However, in
`practice decoder circuits are used much more often as decoders rather than as demultiplexers.
`In many applications the decoder’s En input is not actually needed; hence it can be omitted.
`In this case the decoder always asserts one of its data outputs, y0, . . . ,y 2n−1, according to
`the valuation of the data inputs, wn−1 . . .w 0. Example 6.11 uses a decoder that does not
`have the En input.
`
`One of the most important applications of decoders is in memory blocks, which are used to
`store information. Such memory blocks are included in digital systems, such as computers,
`where there is a need to store large amounts of information electronically. One type of
`memory block is called a read-only memory (ROM). A ROM consists of a collection of
`storage cells, where each cell permanently stores a single logic value, either 0 or 1. Figure
`6.21 shows an example of a ROM block. The storage cells are arranged in 2m rows with n
`
`Example 6.11
`
`0/1
`
`0/1
`
`0/1
`
`0/1
`
`d0
`
`Sel0
`
`Sel1
`
`Sel2
`
`0/1
`
`0/1
`
`0/1
`
`0/1
`
`0/1
`
`0/1
`
`Sel2m 1–
`
`0/1
`
`0/1
`
`Read
`
`m-to-2m decoder
`
`Address
`
`a0
`a1
`
`am 1–
`
`dn 1–
`dn 2–
`Data
`A 2m × n read-only memory (ROM) block.
`
`Figure 6.21
`
`9
`
`

`

`June 13, 2002 15:36
`
`vra23151_ch06
`
`Sheet number 20 Page number 316
`
`black
`
`316
`
`C H A P T E R 6
`
`•
`
`Combinational-Circuit Building Blocks
`
`cells per row. Thus each row stores n bits of information. The location of each row in the
`ROM is identified by its address. In the figure the row at the top of the ROM has address
`0, and the row at the bottom has address 2m − 1. The information stored in the rows can
`be accessed by asserting the select lines, Sel0 to Sel2m−1. As shown in the figure, a decoder
`with m inputs and 2m outputs is used to generate the signals on the select lines. Since
`the inputs to the decoder choose the particular address (row) selected, they are called the
`address lines. The information stored in the row appears on the data outputs of the ROM,
`dn−1, . . . ,d 0, which are called the data lines. Figure 6.21 shows that each data line has
`an associated tri-state buffer that is enabled by the ROM input named Read. To access, or
`read, data from the ROM, the address of the desired row is placed on the address lines and
`Read is set to 1.
`Many different types of memory blocks exist. In a ROM the stored information can
`be read out of the storage cells, but it cannot be changed (see problem 6.31). Another
`type of ROM allows information to be both read out of the storage cells and stored, or
`written, into them. Reading its contents is the normal operation, whereas writing requires
`a special procedure. Such a memory block is called a programmable ROM (PROM). The
`storage cells in a PROM are usually implemented using EEPROM transistors. We discussed
`EEPROM transistors in section 3.10 to show how they are used in PLDs. Other types of
`memory blocks are discussed in section 10.1.
`
`6.3 Encoders
`
`An encoder performs the opposite function of a decoder. It encodes given information into
`a more compact form.
`
`6.3.1 Binary Encoders
`
`A binary encoder encodes information from 2n inputs into an n-bit code, as indicated in
`Figure 6.22. Exactly one of the input signals should have a value of 1, and the outputs
`present the binary number that identifies which input is equal to 1. The truth table for a
`4-to-2 encoder is provided in Figure 6.23a. Observe that the output y0 is 1 when either
`input w1 or w3 is 1, and output y1 is 1 when input w2 or w3 is 1. Hence these outputs can be
`generated by the circuit in Figure 6.23b. Note that we assume that the inputs are one-hot
`
`2n
`inputs
`
`w0
`
`w2n 1–
`
`y0
`
`yn 1–
`
`n
`outputs
`
`Figure 6.22
`
`A 2n-to-n binary encoder.
`
`10
`
`