Sequential logic : analysis and synthesis

Sequential

Logic

Analysis and Synthesis

CRC is an imprint of the Taylor & Francis Group,

an informa business

Sequential

Logic

Analysis and Synthesis

Joseph Cavanagh

Santa Clara University

Boca Raton London New York

CRC Press

Taylor & Francis Group

6000 Broken Sound Parkway NW, Suite 300

Boca Raton, FL 33487-2742

© 2007 by Taylor & Francis Group, LLC

CRC Press is an imprint of Taylor & Francis Group, an Informa business

No claim to original U.S. Government works

Version Date: 20130916

International Standard Book Number-13: 978-1-4200-0785-5 (eBook - PDF)

This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been

made to publish reliable data and information, but the author and publisher cannot assume responsibility for the valid￾ity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright

holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this

form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may

rectify in any future reprint.

Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or uti￾lized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopy￾ing, microfilming, and recording, or in any information storage or retrieval system, without written permission from the

publishers.

For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://

www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923,

978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For

organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged.

Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for

identification and explanation without intent to infringe.

Visit the Taylor & Francis Web site at

http://www.taylorandfrancis.com

and the CRC Press Web site at

http://www.crcpress.com

To my son Brad, who urged me onward.

CONTENTS

Preface xi

Chapter 1 Review of Combinational Logic 1

1.1 Number Systems 2

1.1.1 Binary Number System 3

1.1.2 Octal Number System 4

1.1.3 Decimal Number System 4

1.1.4 Hexadecimal Number System 5

1.2 Number Representations 8

1.2.1 Sign Magnitude 8

1.2.2 Diminished-Radix Complement 9

1.2.3 Radix Complement 10

1.3 Boolean Algebra 12

1.4 Minimization Techniques 18

1.4.1 Algebraic Minimization 19

1.4.2 Karnaugh Maps 20

1.4.3 Quine-McCluskey Algorithm 28

1.5 Logic Symbols 35

1.6 Analysis of Combinational Logic 37

1.7 Synthesis of Combinational Logic 42

1.8 Multiplexers 45

1.9 Decoders 47

1.10 Encoders 53

1.11 Comparators 54

1.12 Storage Elements 56

1.12.1 SR Latch 57

1.12.2 D Flip-Flop 57

1.12.3 JK Flip-Flop 59

1.12.4 T Flip-Flop 60

1.13 Programmable Logic Devices 61

1.13.1 Programmable Read-Only Memories 61

1.13.2 Programmable Array Logic 64

1.13.3 Programmable Logic Array 67

1.14 Problems 69

Chapter 2 Analysis of Synchronous Sequential Machines 77

2.1 Sequential Circuits 78

2.1.1 Machine Alphabets 79

2.1.2 Formal Definition of a Synchronous Sequential

Machine 82

viii Contents

2.2 Classes of Sequential Machines 89

2.2.1 Combinational Logic 89

2.2.2 Registers 93

2.2.3 Counters 98

2.2.4 Moore Machines 105

2.2.5 Mealy Machines 110

2.2.6 Asynchronous Sequential Machines 121

2.2.7 Additional Definitions for Synchronous Sequential

Machines 123

2.3 Methods of Analysis 136

2.3.1 Next-State Table 136

2.3.2 Present-State Map 137

2.3.3 Next-State Map 137

2.3.4 Input Map 138

2.3.5 Output Map 140

2.3.6 Timing Diagram 141

2.3.7 State Diagram 143

2.3.8 Analysis Examples 146

2.4 Complete and Incomplete Synchronous Sequential Machines 161

2.4.1 Complete Synchronous Sequential Machines 161

2.4.2 Incomplete Synchronous Sequential Machines 162

2.5 Problems 166

Chapter 3 Synthesis of Synchronous Sequential Machines 1 181

3.1 Synthesis Procedure 182

3.1.1 Equivalent States 183

3.2 Synchronous Registers 197

3.2.1 Parallel-In, Parallel-Out Registers 197

3.2.2 Parallel-In, Serial-Out Registers 201

3.2.3 Serial-In, Parallel-Out Registers 205

3.2.4 Serial-In, Serial-Out Registers 208

3.2.5 Linear Feedback Shift Registers 212

3.2.6 Combinational Shifter 218

3.3 Synchronous Counters 223

3.3.1 Modulo-8 Counter 223

3.3.2 Modulo-10 Counter 234

3.3.3 Johnson Counter 245

3.3.4 Binary-to-Gray Code Converter 248

3.4 Moore Machines 254

3.5 Mealy Machines 277

3.6 Moore-Mealy Equivalence 298

3.6.1 Mealy-to-Moore Transformation 298

3.6.2 Moore-to-Mealy Transformation 307

3.7 Output Glitches 307

Contents ix

3.7.1 Glitch Elimination Using State Code Assignment 312

3.7.2 Glitch Elimination Using Storage Elements 319

3.7.3 Glitch Elimination Using Complemented Clock 323

3.7.4 Glitch Elimination Using Delayed Clock 326

3.7.5 Glitches and Output Maps 333

3.7.6 Compendium of Output Glitches 339

3.8 Problems 344

Chapter 4 Synthesis of Synchronous Sequential Machines 2 361

4.1 Multiplexers for G Next-State Logic 361

4.1.1 Linear-Select Multiplexers 363

4.1.2 Nonlinear-Select Multiplexers 377

4.2 Decoders for O Output Logic 400

4.3 Programmable Logic Devices 412

4.3.1 Programmable Read-Only Memory 413

4.3.2 Programmable Array Logic 421

4.3.3 Programmable Logic Array 432

4.3.4 Field-Programmable Gate Array 437

4.4 Microprocessor-Controlled Sequential Machines 448

4.4.1 General Considerations 449

4.4.2 Mealy Machine Synthesis 453

4.4.3 Machine State Augmentation 461

4.4.4 Moore and Mealy Outputs 466

4.4.5 System Architecture 467

4.4.6 Multiple Machines 477

4.5 Sequential Iterative Machines 481

4.6 Error Detection in Synchronous Sequential Machines 489

4.7 Problems 500

Chapter 5 Analysis of Asynchronous Sequential Machines 519

5.1 Introduction 520

5.2 Fundamental-Mode Model 522

5.3 Methods of Analysis 526

5.4 Hazards 553

5.4.1 Static Hazards 553

5.4.2 Dynamic Hazards 568

5.4.3 Essential Hazards 572

5.4.4 Multiple-Order Hazards 577

5.5 Oscillations 578

5.6 Races 582

5.6.1 Noncritical Races 583

5.6.2 Cycles 586

x Contents

5.6.3 Critical Races 586

5.7 Problems 590

Chapter 6 Synthesis of Asynchronous Sequential

Machines 607

6.1 Introduction 608

6.2 Synthesis Procedure 610

6.2.1 State Diagram 612

6.2.2 Primitive Flow Table 616

6.2.3 Equivalent States 632

6.2.4 Merger Diagram 645

6.2.5 Merged Flow Table 656

6.2.6 Excitation Maps and Equations 661

6.2.7 Output Maps and Equations 691

6.2.8 Logic Diagram 710

6.3 Synthesis Examples 716

6.3.1 Mealy Machine with Two Inputs and One Output 716

6.3.2 Mealy Machine with Two Inputs and One Output

Using a Programmable Logic Array (PLA) 727

6.3.3 Moore Machine with One Input and One Output 735

6.3.4 Mealy Machine with Two Inputs and Two Outputs 741

6.3.5 Mealy Machine with Three Inputs and One Output 755

6.3.6 Mealy Machine with Two Inputs and Two Outputs 765

6.4 Problems 777

Chapter 7 Pulse-Mode Asynchronous Sequential Machines 807

7.1 Analysis Procedure 809

7.1.1 SR Latches as Storage Elements 810

7.1.2 SR Latches with D Flip-Flops as

Storage Elements 817

7.2 Synthesis Procedure 823

7.2.1 SR Latches as Storage Elements 823

7.2.2 T Flip-Flops as Storage Elements 830

7.2.3 SR-T Flip-Flops as Storage Elements 836

7.2.4 SR Latches with D Flip-Flops as Storage Elements 844

7.3 Problems 850

Appendix Answers to Selected Problems 861

Index 889

PREFACE

The field of digital logic consists primarily of analysis and synthesis of combinational

and sequential logic circuits, also referred to as finite-state machines. Finite-state

machines are designed into every computer. They occur in the form of counters, shift

registers, microprogram control sequencers, sequence detectors, and many other

sequential structures. The principal characteristic of combinational logic is that the

outputs are a function of the present inputs only, whereas, the outputs of sequential

logic are a function of the input sequence; that is, the input history. Sequential logic,

therefore, requires storage elements which indicate the present state of the machine

relative to a unique sequence of inputs.

Sequential logic is partitioned into synchronous and asynchronous sequential

machines. Synchronous sequential machines are controlled by a system clock which

provides the triggering mechanism to cause state changes. Asynchronous sequential

machines have no clocking mechanism — the machines change state upon the appli￾cation of input signals. The input signals provide the means to enable the sequential

machines to proceed through a prescribed sequence of states.

During the last three decades, the design of digital computers has progressed from

hand-drawn logic diagrams to automated logic diagrams to hardware description lan￾guages, where the latter precludes the need for logic diagrams of any type. Although

the methods for portraying the hardware functions may have changed, the necessity

for rigorous analysis and synthesis remains unchanged.

The purpose of this book is to present a thorough exposition of the analysis and

synthesis of both synchronous and asynchronous sequential machines. Emphasis is

placed on structured and rigorous design principles that can be applied to practical

applications. Each step of the analysis and synthesis procedures is clearly delineated.

Each method that is presented is expounded in sufficient detail with several accom￾panying examples. Many analysis and synthesis examples use mixed-logic symbols

which incorporate both positive- and negative-input logic gates for NAND and NOR

logic, while other examples utilize only positive-input logic gates. The use of mixed

logic parallels the use of these symbols in the industry.

This book is intended to be tutorial in nature, and as such, is comprehensive and

self-contained. All concepts and examples are explained in detail and carried out to

completion. The book provides techniques which help to develop logical thinking and

lend rigor to the analysis and synthesis procedures. The design philosophies that are

presented can be easily extended to apply to any digital system.

Chapter 1 reviews the analysis and synthesis of combinational logic. A knowl￾edge of combinational logic is a prerequisite for a study of sequential logic and it is

assumed that the reader has the necessary background. An overview of number sys￾tems and number representations is included. This chapter also contains a review of

xii Preface

boolean algebra, including axioms and theorems. Minimization techniques are pre￾sented using boolean algebra, Karnaugh maps, map-entered variables, and the Quine￾McCluskey algorithm. An introduction to the ANSI/IEEE Std. 91-1984 logic sym￾bols is presented, including their correlation with the distinctive shape logic symbols

of IEEE Std. 91-1962. The ANSI/IEEE Std. 91-1984 defines symbols and associated

terminology which describe a circuit function with a minimal amount of reference to

technical data manuals. These symbols are used only in Chapter 1; the remaining

chapters use the distinctive shape symbols, since these are more widely used and more

easily understood. Simple combinational logic circuits are analyzed and synthesized.

There are also sections describing latches, flip-flops, and programmable logic

devices.

Chapter 2 presents a formal definition of sequential machines. The machine

alphabets are described and include the input alphabet, the state alphabet, and the out￾put alphabet. Six general classes of machines are described with accompanying equa￾tions for the major functions of each machine class. A constituent part of this chapter

is additional definitions for sequential machines, which include state machines, sub￾machines, terminal states, strongly connected machines, machine homomorphism,

machine isomorphism, and equivalent machines. The main objective of this chapter is

to present methods of analysis for synchronous sequential machines. These tech￾niques form the basic mechanisms for effective analysis. Each method of analysis is

accompanied by appropriate examples. The final section discusses complete and

incomplete synchronous sequential machines.

Chapter 3 presents the first of two chapters on the synthesis of synchronous

sequential machines. The synthesis procedure is outlined, then methods are described

to determine state equivalence. If equivalent states can be identified, then redundant

states can be eliminated, resulting in a machine with a minimal number of logic gates.

The primary focus of this chapter is on the synthesis of deterministic synchronous

sequential machines in which the next state is uniquely determined by the present state

and the present inputs. The synthesis of each class of machine is presented with

accompanying examples. A section is included on Moore-Mealy machine equiva￾lence which includes Moore-to-Mealy and Mealy-to-Moore transformations. A final

section discusses output glitches, which are momentary erroneous outputs. Several

methods are presented to nullify the effects of these spurious signals which wreak

havoc in digital systems, especially if they occur on an output signal.

Chapter 4 covers alternative methods for synthesizing synchronous sequential

machines, in which logic functions other than discrete logic gates are utilized for both

the input and output logic. These methods include logic macros such as multiplexers

for the combinational input logic and decoders for the output logic. Programmable

logic devices are presented in which synchronous sequential machines are synthe￾sized using programmable read-only memories, programmable array logic devices,

programmable logic array devices, and field-programmable gate arrays. A section is

included on microprocessors and illustrates their use in the synthesis of synchronous

sequential machines. Microprocessors are extremely versatile, especially for sequen￾tial machines with a large number of states or for multiple machines. Iterative net￾works are discussed and a method is presented to convert a combinational iterative

network to a functionally equivalent sequential machine. A final section provides a

discourse on error detection in synchronous sequential machines.

Preface xiii

Chapter 5 covers the analysis of asynchronous sequential machines. The funda￾mental-mode model is introduced and is a major consideration in both the analysis and

synthesis of asynchronous sequential machines. Methods of analysis are presented

which completely characterize the operation of the machine. The mechanisms

include an excitation map, a next-state table, a state diagram, and a flow table. Three

significant items that are of paramount concern in the analysis and synthesis of asyn￾chronous sequential machines are discussed in detail: hazards, oscillations, and races.

Hazards are the result of varying propagation delays caused by logic gates, wires, and

different signal path lengths. Hazards can produce erroneous transient signals on the

outputs. Oscillations occur when a change to the input vector causes the machine to

oscillate between two or more unstable states. Races occur when a change to the input

vector results in simultaneous changes to two or more excitation variables.

Chapter 6 presents an exhaustive discourse on the synthesis of asynchronous

sequential machines. The chapter develops a systematic method for this relatively

complex procedure. Each step in the synthesis procedure employs several examples

which help to clarify the corresponding step. The synthesis procedure is developed as

individual fragments of the complete process. Using this approach, each step in the

procedure can be reviewed as a separate entity. The complete synthesis process is

explicated by several worked examples. Only through dedicated perseverance can the

synthesis of asynchronous sequential machines be effectively learned. To achieve this

goal, several examples are presented detailing the synthesis procedure in a step-by￾step process.

Chapter 7 presents analysis and synthesis procedures for pulse-mode asynchro￾nous sequential machines. Many situations are encountered in digital engineering

where the input signals occur as pulses and in which there is no periodic clock signal

to synchronize the operation of the machine. A vending machine is a typical example.

Due to the stringent requirements of input pulse characteristics, however, pulse-mode

machines are less preferred than synchronous sequential machines. Analysis of pulse￾mode asynchronous sequential machines consists of deriving a next-state table, input

maps, output maps, and a state diagram for a given logic diagram in much the same

manner as for synchronous sequential machines. The synthesis procedure is

described using several different types of storage elements.

It is assumed that the reader has an adequate background in the analysis and syn￾thesis of combinational logic. This book presents basic and advanced concepts in

sequential machine analysis and synthesis and is designed for practicing electrical and

computer engineers, graduate students who require a noncredit course in sequential

logic to supplement their program of studies, and for undergraduate students in elec￾trical and computer engineering.

I would like to express my appreciation and thanks to the following people who

gave generously of their time and expertise to review the manuscript and submit com￾ments: Professor Daniel W. Lewis, Chair, Department of Computer Engineering,

Santa Clara University who supported me in all my endeavors; Dr. Geri Lamble; Steve

Midford; and Ron Lewerenz. Thanks also to Nora Konopka and the staff at Taylor &

Francis for their support.

Joseph Cavanagh

1

Review of Combinational Logic

The purpose of this book is to analyze and synthesize finite-state machines; that is,

synchronous and asynchronous sequential machines. Prior to presenting sequential

machines in Chapter 2, however, a review of combinational logic will be covered. It

is assumed that a reader who is interested in studying sequential logic has an adequate

background in the analysis and synthesis of combinational logic. This chapter, there￾fore, presents only an overview of combinational logic. Combinational logic refers to

logic circuits whose present output values depend only upon the present input values.

A combinational circuit is a special case of a sequential circuit in which there is no

storage capability. The word combinational is used interchangeably with combinato￾rial.

A combinational logic circuit is comprised of combinational logic elements (or

logic primitives), which have one or more inputs and at least one output. The input

and output variables are characterized by discrete states such that, at any instant of

time, the state of each output is completely determined by the states of the inputs. A

combinational circuit refers to a logic circuit which performs the same fixed mapping

of inputs into outputs, regardless of the past input history and may be considered as a

one-state sequential machine.

This chapter will discuss number systems and number representations, define the

logical operations encountered in different logic families, and briefly review the IEEE

Standard: Graphic Symbols for Logic Functions, ANSI/IEEE Std. 91-1984. The

boolean axioms and theorems will be listed, without proof. Three minimization tech￾niques will be presented: algebraic minimization using boolean algebra, Karnaugh

maps, including map-entered variables, and the Quine-McCluskey algorithm.

The important, and sometimes confusing, topic of logic assertion levels will also

be discussed. Logic assertion levels are especially difficult to understand by new stu￾dents in the field of digital logic design. Combinational logic circuits will be analyzed

and synthesized (designed) using different logic families. Chapter 1 will also briefly

1.1 Number Systems

1.2 Number Representations

1.3 Boolean Algebra

1.4 Minimization Techniques

1.5 Logic Symbols

1.6 Analysis

1.7 Synthesis

1.8 Multiplexers

1.9 Decoders

1.10 Encoders

1.11 Comparators

1.12 Storage Elements

1.13 Programmable Logic

Devices

1.14 Problems

2 Chapter 1 Review of Combinational Logic

review the different storage elements that are used in the synthesis of synchro￾nous and asynchronous sequential machines.

1.1 Number Systems

Digital systems contain signals that are represented by two values: 0 or 1,

which describe the signal alphabet. Numerical data, or operands, are expressed

in various positional number systems for each radix. This section will discuss

binary, octal, decimal, and hexadecimal positional number systems. A posi￾tional number system is characterized by a radix (or base) r, which is an integer

greater than or equal to 2, and by a set of r digits, which are numbered from 0 to

r – 1. For example, for radix 8, the digits range from 0 to 7.

In a positional number system, a number is encoded as a vector of n digits

in which each digit is weighted according to its position in the vector. An n-bit

integer A is represented in a positional number system as follows:

A = (an–1an–2an–3 } a1a0) (1.1)

where 0 d ai d r – 1. The high-order and low-order digits are an–1 and a0, re￾spectively.

The number in Equation 1.1 (also referred to as a vector or operand) can

represent positive integer values in the range 0 to r

n – 1. Thus, a positive integer

A is written as

A = an–1r

n–1 + an–2r

n–2 + an–3 r

n–3 + } + a1r

1

+ a0r

0 (1.2)

The value for A can be represented more compactly as

A = 6

i = 0

n – 1

a (1.3) ir

i

The expression of Equation 1.2 can be extended to include fractions. For ex￾ample,

A = an–1r

n–1 + } + a1r

1

+ a0r

0

+ a–1r

–1 + a–2r

–2 + a–mr

–m (1.4)

1.1 Number Systems 3

Equation 1.4 can be represented as

A = 6

i = –m

n – 1

a (1.5) ir

i

The number system requires exactly r digits. For example, radix 10 consists of digits

0 through 9. The highest digit value is one less than the radix. Adding 1 to the highest

digit value produces a sum of zero and a carry of 1 to the next higher-order column.

1.1.1 Binary Number System

The radix is 2 in the binary number system; therefore, only two digits are used: 0 and

1. The low-value digit is 0 and the high-value digit is (r – 1) = 1. The binary number

system is the most conventional and easily implemented system for internal use in a

digital computer; therefore, most digital computers use the binary number system.

There is a disadvantage when converting to and from the externally used decimal sys￾tem; however, this is compensated for by the ease of implementation and the speed of

execution in binary of the four basic operations: addition, subtraction, multiplication,

and division. The radix point is implied within the internal structure of the computer;

that is, there is no specific storage element assigned to contain the radix point.

The weight assigned to each position of a binary number is as follows:

2n–1 2n–2 } 23

22

21

20

• 2–1 2–2 2–3 } 2–m

where the integer and fraction are separated by the radix point (binary point). The

decimal value of the binary number 1101.1012 is obtained by using Equation 1.4,

where r = 2 and ai  {0,1} for –m d i d n – 1. Therefore,

23 22 21 20 • 2–1 2–2 2–3

1101. 1012 = (1 u 23

) + (1 u 22

) + (0 u 21

) + (1 u 20

) +

(1 u 2–1) + (0 u 2–2) + (1 u 2–3)

= 13.62510