Petitioner’s Exhibit CSC 1014
`
`
`
`
`Petitioner’s Exhibit CSC 1014
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`
`
`t
`
`mm
`.mwtwm?
`
`
`
`Petitioner Cypress Semiconductor Corp. - EX. CSC 1014, p. 1
`
`Petitioner Cypress Semiconductor Corp. - Ex. CSC 1014, p. 1
`
`

`

`
`
`
`
`Executive Editor: Dan Joraanstad
`Sponsoring Editor: Jennifer Young
`Deveiopmentai Editor: Jamie Spencer
`Editorial Assistant: Laura Chen
`Marketing Manager: Mary Tudor
`Production Editors: Megan Rundel, Brian Jones
`Text and Cover Design: Rob Hegel, XXX Design
`Copyeditor: Mary Prescott
`Proofreader: Elizabeth Wiltsee
`Illustrations: Rolin Graphics Inc.
`Indexer: Ira Kleinberg
`Composition: Rad Proctor, Prootor—Willenbacher
`Film: The Courier Connection
`Cover Printer: New England Book Components, Inc.
`Text Printer and Binder: Courier/Westford
`Senior Manufacturing Coordinator: Merry Free Osborn
`
`The cover illustration is a reproduction of “Décalcomanie” by the twentieth-century
`Belgian surrealist painter Rene Magritte. We chose this particular painting by the
`author’s favorite painter to reflect the duality of computer design. “Décalcomanie”
`© 1992 C. Herscovici/ARS, New York.
`
`Copyright © 1994 by The Benjamin/Cummings Publishing Company, Inc.
`
`Ail rights reserved. No part of this pubiication may be reproduced, stored in a
`database or retrieval system, distributed, or transmitted, in any form or by any means,
`electronic, mechanical, photocopying, recording, or otherwise, without the prior
`written permission of the pubiisher. Printed in the United States of America.
`Published simultaneously in Canada.
`
`Library of Congress Cataloging-in-Pubiieation Data
`Katz, Randy H., 1955—
`Contemporary logic design / Randy H. Katz.
`p.
`cm.
`includes bibliographical references and index.
`ISBN 0-8053—2703—7
`
`1. Electronic digital computers—Circuits—Design. 2. Integrated circuits—
`Very targe scale integration-«Design—Data processing. 3. Logic design—Data
`processing. 4. Computer-aided design. I. Title.
`TK7BBB.4.K36
`1994
`621.39'5—“d029
`
`i
`
`93-9013
`CIP
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ISBN 0-8053-2703—7
`
`3 4 5 6 7 8 9 lO-CRW-999397969594
`
`
`
`The BenjaminlCummings Publishing Company, Inc.
`390 Bridge Parkway
`Redwood City, California 94065
`
`
`
`Petitioner Cypress Semiconductor Corp. - EX. CSC 1014, p. 2
`
`Petitioner Cypress Semiconductor Corp. - Ex. CSC 1014, p. 2
`
`

`

`338
`
`Ehapter 8
`
`Finite State Machine Design
`
`
`
`
`Figure 8.8
`
`State and output changes associated with the FSM fragments of Figure 8.7.
`
`
`
`
`
`Now that Y is 1, FSM1 goes to state B on the next rising edge. In this
`state, it will output a 0, but this is too late to affect FSMZ’S state change.
`It remains in state D.
`
`
`
`3.2:
`Essie fiestas Apsraach
`The counter design procedure presented in the last chapter-forms the
`
`
`core of a more general procedure for arbitrary finite state machines. You
`
`
`will discover that the procedure must be significantly extended for the
`
`general case.
`
`
`Finite State Machine Design Procedure
`8.2.1
`
`
`Step 1: Understand the problem. A finite state machine is often
`described in terms of an English-language specification of its behav-
`
`
`ior. It is important that you interpret this description in an unambig-
`
`
`uous manner. For counters, it is sufficient simply to enumerate the
`sequence. For finite state machines, try some input sequences to be
`
`
`sure you understand the conditions under which the various outputs
`
`
`are generated.
`
`
`Step 2: Obtain an abstract representation of the FSM. Once you
`understand the problem, you must place it in a form that is easy to
`
`
`manipulate by the procedures for
`implementing the finite state
`machine. A state diagram is one possibility. Other representations, to
`
`
`be introduced in the next section, include algorithmic state machines
`
`
`and specifications in hardware description languages.
`
`
`Step 3: Perform state minimization. Step 2, deriving the abstract
`representation, often results in a description that has too many
`
`
`states. Certain paths through the state machine can be eliminated
`because their input/output behavior is duplicated by other function-
`
`
`
`
`
`
`
`Petitioner Cypress Semiconductor Corp. - EX. CSC 1014, p. 3
`
`Petitioner Cypress Semiconductor Corp. - Ex. CSC 1014, p. 3
`
`

`

`Chapter 8
`
`Finite State Machine Design
`
`
`Coin
`G m
`
`uRelease
`Sensor
`Mechanism
`
`
`
`Figure 8.9 Vending machine block diagram.
`
`
`
`the customer? Sometimes we have to make reasonable assumptions. For
`the first question, we assume that the coin sensor returns any coins it
`does not recognize,
`leaving N and D unasserted. For the latter, we
`assume that external logic resets the machine after the gum is delivered.
`
`Abstract Representations Once you understand the behavior reasonably
`well, it is time to map the specification into a more suitable abstract
`representation. A good way to begin is by enumerating the possible
`unique sequences of inputs or configurations of the system. These will
`help define the states of the finite state machine.
`For this problem, it is not too difficult to enumerate all the possible
`input sequences that lead to releasing the gum:
`
`Three nickels in sequence: N, N, N
`
`‘
`
`Two nickels followed by a dime: N, N, D
`
`A nickel followed by a dime: N, D
`
`A dime followed by a nickel: D, N
`
`Two dimes in sequence: D, D
`This can be represented as a state diagram, as shown in Figure 8.10.
`For example, the machine will pass through the states 80, S}, 83, S7 if
`the input sequence is three nickels.
`we include only transi—
`To keep the state diagram simple and readable,
`ate SD, if neither
`tions that explicitly cause a state change. For example, in st
`input N or D is asserted, we assume the machine remains in state 5’D (the
`specification allows us to assume that N and D are never asserted at the
`same time). Also, we include the output Open only in states in which it is
`asserted. Open is implicitly unasserted in any other state.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`390
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`State Minimization This nine—state description isn’t the "best” possible.
`For one thing, since states 84, 55, Sfi, S7, and SB have identical behavior,
`they can be combined into a single state.
`further, we can think of each
`To reduce the number of states even
`(1 so far. For example,
`state as representing the amount of money receive
`
`
`
`
`Petitioner Cypress Semiconductor Corp. - EX. CSC 1014, p. 4
`
`Petitioner Cypress Semiconductor Corp. - Ex. CSC 1014, p. 4
`
`

`

`3.2 Basic Design Approach
`
`
`
`
`391
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`nine 8.11 Minimized vending
`'hine state diagram
`
`
`Figure l.1tl Vending machine state diagram.
`
`it shouldn’t matter whether the state representing 10 cents was reached
`through two nickels or one dime.
`A state diagram derived in this way is shown in Figure 8.11. We cap-
`ture the behavior in only four states, compared with nine in Figure 8.10.
`Also, as another illustration of a useful shorthand, notice the transition
`from state 10¢ to 15¢. We interpret the notation “N, D” associated with
`this transition as “go to state 15¢ if N is asserted OR Dis asserted."
`In the next chapter, we wili examine formal methods for finding a state
`diagram with the minimum number of states. The process of minimizing
`the states in a finite state machine description is called state minimization.
`
`State Encoding At this point, we have a finite state machine with a
`minimum number of states, but it is still symbolic. See Figure 8.12. for
`the symbolic state transition table. The next step is state encoding.
`The way you encode the state can have a major effect on the amount of
`hardware you need to implement the machine. A natural state assignment
`would encode the states in 2 bits: state Be as 00, state 5?? as 01, state 10¢ as
`10, and state 15¢ as 11. A less obvious assignment could lead to reduced
`hardware. The encoded state transition table is shown in Figure 8.13.
`In Chapter 9 we present a variety of methods and computer-based
`tools for finding an effective state encoding.
`
`Implementation The next step is to implement the state transition table
`after choosing storage elements. We will look at implementations based
`on D and I—K flip—flops.
`
`
`
`Petitioner Cypress Semiconductor Corp. - EX. CSC 1014, p. 5
`
`Petitioner Cypress Semiconductor Corp. - Ex. CSC 1014, p. 5
`
`

`

`
`
`
`
`
`
`
`Present
`State
`Out.
`
`Inputs
`D N
`0
`0
`0
`1
`1
`0
`1
`1
`
`""fifié"""""5”?)"""""""""""
`U
`1
`1
`0
`1
`1
`_____TD'tfg”’”_fi"’i)
`o
`1
`1
`0
`1
`1
`"”7#T5':iw"_‘Xi‘X‘w "#1513””””” I
`Figure 8.12 Minimized vending machine symbolic state transition table.
`
`Output
`Next State
` D1 D0 Open
`
`0
`0
`0
`0
`‘1
`0
`1
`D
`0
`X X
`X
`’A'_D’A T"__*"(‘I’”'
`
`Figure 8.13
`
`Encoded vending machine state ttansition table.
`
`
`
`'
`
`‘
`
`
`
`
`
`392
`
`Chapter 3
`
`Finite State Machine Design
`
`
`
`
`
`
`
`the D flip-flop implementation are shown in
`for
`The K—maps
`Figure 8.14. We filled these in directly from the encoded state transition
`table. The minimized equations for the flip—flop inputs and the output
`become
`
`
`
`
`
`
`
`
`D1 = Q1+D+QouN
`D0 = N'QU+Q0'N+Q1'N+Q1.D
`
`OPEN = Q1 ' Q0
`
`The logic implementation is shown in Figure 8.15. It uses eight gates
`and two flip-flops.
`
`
`
`Petitioner Cypress Semiconductor Corp. - EX. CSC 1014 p. 6
`
`Petitioner Cypress Semiconductor Corp. - Ex. CSC 1014, p. 6
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`_L!1i'__
`
`
`used state diagrams.
`
`To implement the state machine using I—K flip-flops, we must remap
`the next-state functions as in Chapter 7. The remapped state transition
`table for I—K flip—flop implementation is shown in Figure 8.16. We give
`the K-maps derived from this table in Figure 8.17. The minimized equa-
`tions for the flip-flop inputs become
`
`
`
`
`
`
`
`Basic Design Approach
`
`393
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Figure 8.14 K-maps for Dflip-fiop implementation of vending machine.
`
`K-map for Do
`
`K-map for Open
`
`
`
`Figure 8.15 Vending machine FSM implementation based on D flip-flops.
`
`IEMD+Q0.N
`
`K1
`
`6
`
`IoflQo‘N‘tQ1’D K0 QI'N
`
`Figure 8.18 shows the logic implementation. Using ]—K flip—flops moder-
`ately reduced the hardware: seven gates and two flip-flops.
`
`Discussion We briefly described the complete finite state machine design
`process and illustrated it by designing a simple vending machine con-
`troller. Starting with an English-language statement of the task, we first
`described the machine in a more formal representation. In this case, we
`
`Petitioner Cypress Semiconductor Corp. - EX. CSC 1014, p. 7
`
`Petitioner Cypress Semiconductor Corp. - Ex. CSC 1014, p. 7
`
`

`

`394
`
`Chapter 8
`
`Finite State Machine Design
`
`Present State
`Q1 Q0
`
`3* 5
`
`xowo
`
`NNNN
`
`t I
`
`i
`
`i>4>aw
`NHHD
`
`i i ii I
`
`DDDMRNN
`
`and requires four flip-flops for its implementation. The minimized state
`
`
`
`.1620
`00
`
`|’JC;1'-—Vi
`1’1
`10
`
`01
`
`
`
`
`
`
`
`Q0
`no
`
`rJ—n
`11
`10
`
`01
`
`K—map for In
`Kamap for K0
`y Figure 8.17
`K—maps tor J-Kflip-flop implementation of vending machine.
`
`Since more than one state diagram can lead to the same input/output
`behavior, it is important to find a description with as few states as possible.
`This usually reduces the implementation complexity of the finite state ma-
`chine. For example, the state diagram of Figure 8.10 contains nine states
`
`Petitioner Cypress Semiconductor Corp. - EX. CSC 1014 p 8
`
`Petitioner Cypress Semiconductor Corp. - Ex. CSC 1014, p. 8
`
`

`

`
`
`
`
`\reset
`
`Figure 8.18
`
`J»Ktlip-flop implementation for the vending machine example.
`
`lI
`
`_l
`
`
`
`
`
`diagram of Figure 8.11 has four states and can be implemented with only
`two flip—flops.
`Once we have obtained a minimum finite state description, the next
`step is to choose a good encoding of the states. The right choice can fur—
`ther reduce the logic for the next~state and output functions. In the
`example, we used only the most obvious state assignment.
`The final step is to choose a flip—flop type for the state registers. In the
`example, the implementation based on D flip-flops was more straightfor-
`ward. We did not need to remap the flip—flop inputs, but we used more
`gates than the I—K flip—flop implementation. This is usually the case.
`Now we are ready to examine some alternatives to the state diagram
`for describing finite state machine behavior.
`
`8.3
`
`Alternative State Machine Representations
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`You have already seen how to describe finite state machines in terms of
`state diagrams and tables. However, it can be difficult to describe complex
`finite state machines in this way. Recently, hardware designers have shifted
`toward using alternative representations of FSM behavior tl’iat look more
`like software descriptions. In this section, we introduce algorithmic state
`machine (ASM) notation and hardware description languages (HDLs).
`ASMs are similar to program flowcharts, but they have a more rigorous
`concept of timing. l-lDLs look much like modern programming languages,
`but they explicitly support computations that can occur in parallel.
`You may wonder what is wrong with state diagrams. The problem is ‘
`that they do not adequately capture the notion of an algorithm—a well—
`defined sequence of steps that produce a desired sequence of actions
`based on input data. State diagrams are weak at capturing the structure
`behind complex sequencing. The representations discussed next do a
`
`better job of making this sequencing structure explicit.
`
`
`
`
`Petitioner Cypress Semiconductor Corp. - Ex. CSC 1014, p. 9
`
`3.3 Alternative State Machine Representations
`
`395
`
`
`
`
`
`Q1
`
`
`
`
`
`
`
`
`
`Petitioner Cypress Semiconductor Corp. - Ex. CSC 1014, p. 9
`
`

`

` 8.3 Alternative State Machine Representations
`
`
`
`\reset
`
`Figure 8.18
`
`J—Ktlip-tiep implementation for the vending machine example.
`
`diagram of Figure 8.11 has four states and can be implemented with only
`two flip—flops.
`Once we have obtained a minimum finite state description, the next
`step is to choose a good encoding of the states. The right choice can fur—
`ther reduce the logic for the next-state and output functions. In the
`example, we used only the most obvious state assignment.
`The final step is to choose a flip-flop type for the state registers. In the
`example, the implementation based on D flip-flops was more straightfor-
`ward. We did not need to remap the flip-flop inputs, but we used more
`gates than the PK flip—flop implementation. This is usually the case.
`Now we are ready to examine some alternatives to the state diagram
`for describing finite state machine behavior.
`
`3.3
`
`
`
`
`
`
`
`
`
`
`You have already seen how to describe finite state machines in terms of
`
`state diagrams and tables. However, it can be difficult to describe complex
`
`finite state machines in this way. Recently, hardware designers have shifted
`
`toward using alternative representations of FSM behavior that look more
`
`like software descriptions. In this section, we introduce algorithmic state
`
`machine (ASM) notation and hardware description languages (HDLs).
`
`ASMs are similar to program flowcharts, but they have a more rigorous
`
`concept of timing. I-IDLs look much like modern programming languages,
`
`but they explicitly support computations that can occur in parailel.
`
`You may wonder What is wrong with state diagrams. The problem is
`
`that they do not adequately capture the notion of an algorithm—a well-
`
`defined sequence of steps that produce a desired sequence of actions
`
`based on input data. State diagrams are week at capturing the structure
`
`behind complex sequencing. The representations discussed next do a
`better job of making this sequencing structure explicit.
`
`
`Alternative State Machine Representations
`
`
`
`
`
`Petitioner Cypress Semiconductor Corp. - EX. CSC 1014, p. 10
`
`395
`
`OPEN
`
`N“
`
`
`
`D. re Q1
`
`
`‘w— M
`
`
`
`
`
`
`
`
`Petitioner Cypress Semiconductor Corp. - Ex. CSC 1014, p. 10
`
`

`

`396
`
`Chapter 8
`
`Finite State Machine Design
`
`Algorithmic State Machine Notation
`8.3.1
`The ASM notation consists of three primitive elements: the state box,
`the decision box, and the output box, as shown in Figure 8.19. Each
`major unit, called an ASM block, consists of a state box and, optionally,
`a network of condition and output boxes. A state machine is in exactly
`one state or ASM block during the stable portion of the state time.
`
`
`
`Condition Boxes The condition box tests an input to determine an exit
`path from the current ASM block to the block to be entered next. The
`order in Which condition boxes are cascaded has no effect on the deter-
`mination of the next ASM block. Figure 8.20(a) and (b) show function-
`ally equivalent ASM blocks: state B is to be entered next if IO and 11 are
`both 1; otherwise state C is next.
`
`State
`
`State Code"!
`
`Slate Boxes There is one state box per ASM block, reached from other
`ASM blocks through a single state entry path. in addition, for each com-
`bination of inputs there is a single unambiguous exit path from the ASM
`block. The state box is identified by a symbolic state name—in a circle——
`and a binary-encoded state code, and it contains an output signal list.
`The output list describes the signals that are asserted whenever the
`state is entered. Because signals may be expressed in either positive or
`negative logic, it is customary to place an “L.” or “H.” prefix before the
`signal name, indicating Whether it is asserted low or high. You can also
`specify Whether the signal is asserted immediately (I) or is delayed (no
`special prefix) until the next clocking event. A signal not mentioned in
`the output list is left unasserted.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Entry Pati\
`
`
`
`
`
`Output List
`- Block
`
`
`TwF
`
`Condition
`
`Box
`_
`Conditional
`
`
`Output List
`Other ASM Blocks
`
`
`Figure 8.19 Elements of the ASM notation.
`
`
`
` State ,
`
`
`
`State Box
`
`
`
`Petitioner Cypress Semiconductor Corp. - EX. CSC 1014, p. 11
`
`Petitioner Cypress Semiconductor Corp. - Ex. CSC 1014, p. 11
`
`

`

`8.3 Aiternative State Machine Representations
`
`397
`
`
`
`
`
`[a] State exit
`
`[b] Alternative
`
`Figure 8.20
`
`Functionally equivalent ASM blocks.
`
`Output Boxes Any output boxes on the path from the state box to an
`exit contain signals that should be asserted along with the signals men-
`tioned in the state box. The state machine advances from one state to
`the next in discrete rather than continuous steps. In this sense, ASM
`charts have different timing semantics than program flowcharts.
`
`The Parity Checker As an example, we give the parity
`Example
`checker’s ASM chart in Figure 8.21. It consists of two states, Even and
`Odd, encoded as 0 and 1, respectively. The input is the single bit X; the
`output is the single bit Z, asserted high when the finite state machine is
`in the Odd State.
`
`
`
`
`
`
`
`
`
`
`
`We can derive the state transition table from the ASM chart. We sim-
`ply list all the possible transition paths from one state to another and
`the input combinations that cause the transition to take place. For exam-
`ple, in state Even, when the input is 1, we go to state Odd. Otherwise
`we stay in state Even. For state Odd, if the input is 1, we advance to
`Even. Otherwise we remain in state Odd. The output Z is asserted only
`in state Odd. The transition table becomes:
`
`Figure 8.21
`
`Parity checkerASM chart.
`
`Present StateInput X Output Z Next State
`
`
`
`F
`Even
`Even
`Not asserted
`
`T
`
`F
`
`T
`
`Even
`
`Odd
`
`Odd
`
`Odd
`
`Odd
`
`Even
`
`Not asserted
`
`Asserted
`
`Asserted
`
`Petitioner Cypress Semiconductor Corp. - EX. CSC 1014, p. 12
`
`Petitioner Cypress Semiconductor Corp. - Ex. CSC 1014, p. 12
`
`

`

`
`398
`
`ChapterB Finite State Machine Design
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Figure 8.22 Vending machine ASM chart.
`
`8.3.2
`
`
`
`
`Example
`Vending Machine Contreiier We show the ASM chart for the
`vending machine in Figure 8.22. To extract the state transition table, we
`
`
`simply examine all exit paths from each state. For example, in the state
`
`
`0e, we advance to state 10¢ when input D is asserted. If N is asserted,
`we go to state 5a. Otherwise, we stay in state On. The rest of the table
`
`can be determined by looking at the remaining states in turn.
`
`
`
`
`Hardware Description Languages: VHDL
`ages provide another way to specify finite
`Hardware description langu
`state machine behavior. Such descriptions bear some resemblance to a
`
`
`program written in a modern structured programming language. But
`
`
`again, the concept of timing is radically different from that in a program
`
`
`written in a sequential programming language. Unlike state diagrams or
`ASM charts, specifications in a hardware description language can actu~
`
`
`ally be simulated. They are executable descriptions that can be used to
`
`
`verify that the digital system they describe behaves as expected.
`VHDL (VHSIC hardware description language) is an industry standard.
`
`
`Although its basic concepts are relatively straightforward,
`its detailed
`
`
`
`
`
`
`Petitioner Cypress Semiconductor Corp. - EX. CSC 1014, p. 13
`
`Petitioner Cypress Semiconductor Corp. - Ex. CSC 1014, p. 13
`
`

`

`
`
`8.3 Alternative State Machine Representations
`
`359
`
`syntax is beyond the scope of this text. However, we can illustrate its capa-
`bilities for describing finite state machines by examining a description of
`the parity checker written in VI-IDL:
`
`ENTITY parity_checker IS
`PORT (
`
`x, ch: IN BIT;
`2: OUT BIT);
`END parity_checker;
`
`ARCHITECTURE behavioral OF parity_checker IS
`BEGIN
`main: BLOCK (ch = '1' and not ch'STABLE)
`
`TYPE state IS (Even, Odd);
`SIGNAL state_register= state := Even I
`
`BEGIN state_even:
`BLOCK ((state_register = Even) AND GUARD)
`BEGIN
`
`state_register <= Odd WHEN x =
`ELSE Even
`END BLOCK state_even;
`
`'1‘
`
`BEGIN state_odd:
`BLOCK ((state_register r Odd) AND GUARD)
`BEGIN
`
`state_register <= Even WHEN x =
`ELSE Odd;
`END BLOCK statemodd;
`
`'1‘
`
`
`
`machine. The vaIues the state register can take on are defined by the
`type state, consisting of the symbols Even and Odd. We write VHDL
`statements that assign new values to the state register and the output Z,
`depending on the current value of input X, whenever we detect a rising
`clock edge‘
`
`2 <= '0' WHEN state_register
`'1' WHEN state_register
`END BLOCK main;
`END behavioral;
`
`Even ELSE
`Odd;
`
`Every VHDL description has two components: an interface descrip-
`tion and an architectural body. The former defines the input and output
`connections or “ports” to the hardware entity being designed; the latter
`describes the entity’s behavior.
`The architecture block defines the behavior of the finite state
`
`Petitioner Cypress Semiconductor Corp. - EX. CSC 1014, p. 14
`
`Petitioner Cypress Semiconductor Corp. - Ex. CSC 1014, p. 14
`
`

`

`
`
`400
`
`Chapter 8
`
`Finite State Machine Design
`
`
`
`Checking for events like a clock transition is handled through the
`VHDL concept of the guard, an expression that enables certain state-
`ments in the description when it evaluates to true. For example. the
`expression
`
`ctk =
`
`'1' and not ctk‘stabte
`
`true whenever the clock signal has recently
`is a guard that evaluates to
`is enabled for evaluation
`undergone a U-to-l transition. The main block
`when this particular guard becomes true.
`The description contains two subblocks. state_even and state_odd,
`that are enabled whenever the main guard is true and the machine is in
`the indicated state. Within each subblock, die state register receives a
`new assignment depending on the value of the input. Outside the sub-
`blocks, the output becomes 0 when the machine enters state Even and 1
`when it enters state Odd.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`8,3,3
`
`ABEL Hardware Description Language
`
`ABEL is a hardware description language closely tied to the specifica-
`tion of programmable logic components. It is also an industry standard
`and enjoys widespread use. The language is suitable for describing
`either
`combinational or
`sequential
`logic and supports hardware
`specification in terms of Boolean equations, truth tables, or state dia—
`gram descriptions. Although the detailed syntax and semantics of the
`language are beyond our scope, we can highlight its features with the
`parity checker finite state machine.
`Let’s look at the ABEL description of the parity checker:
`
`module parity
`title 'odd parity checker state machine
`Joe Engineer, Itty Bity Machines, Inc.‘
`device
`'pZZv'iG';
`
`U1
`
`"Input Fins
`
`"Output Pins
`Q,
`Z
`R,
`Z
`
`pin 21, 22;
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ctk, X, RESET pin 1, 2, 3;
`
`
`
`
`istype 'pos,reg';
`
`
`
`
`
`
`
`"State registers
`SREG
`=
`EQ, Z];
`EVEN
`=
`[0, DJ;
`ODD
`=
`[1, 1];
`
`
`" even number of 0's
`" odd number of 0's
`
`
`
`Petitioner Cypress Semiconductor Corp. - EX. CSC 1014, p. 15
`
`Petitioner Cypress Semiconductor Corp. - Ex. CSC 1014, p. 15
`
`

`

`8.3 Alternative State Machine Representations
`
`40‘!
`
`equations
`[Q.ar, Z.ar] = RESET;”Reset
`
`to state 50
`
`statemdiagram SREE
`state EVEN:
`if X then ODD
`else EVEN;
`state ODD:
`if X then EVEN
`
`else ODD;
`
`[SREG])
`
`te5t_vectors ([clk, RESET, X] —>
`[U,1,.X.]
`[EVEN];
`E.C.,D,1]
`[ODD];
`[.c.,0,1]
`[EVEN];
`[.C.,0,1]
`[ODD];
`[.C.,D,D]
`[ODD];
`[.C.,0,1]
`[EVEN];
`[.C.,0,1]
`[ODD];
`[.C.,0,U]
`[ODD];
`[.C.,0,D]
`[ODD];
`[.C.,0,D]
`[ODD];
`and parity;
`
`
`
`An ABEL description consists of several sections: module, title, descrip-
`tions, equations, truth tables, state diagrams, and test vectors, some of
`which are optional. Every ABEL description begins with a module state-
`ment and an optional title statement. These name the module and
`provide some basic documentation about its function.
`These are followed by the description section. The elements of
`this section are the kind of device being programmed, the specification
`of inputs and outputs, and the declaration of which signals constitute
`the state of the finite state machine.
`
`We must first describe the device selected for the implementation. It
`is a P22V10 PAL, with 12 inputs, 1%) outputs, and embedded flip~flops
`associated with the outputs. For identification within the schematic, we
`call the device 111.
`
`Next come the pin descriptions. The finite state machine’s inputs are
`the clock 01k, data X, and the RESET signal. The outputs are the state Q
`and the output Z. These are assigned to specific pins on the PAL. For
`example, pin 1 is connected to the clock inputs of the internal flip-flops.
`Many of the attributes of a PAL are selectable, so the description
`may need to make explicit choices. The next line of the description tells
`ABEL that Q and Z are POSitive logic outputs of the PAL’s internal flip—
`flops (REG) associated with particular output pins. The P22V10 PAL
`
`Petitioner Cypress Semiconductor Corp. - EX. CSC 1014, p. 16
`
`Petitioner Cypress Semiconductor Corp. - Ex. CSC 1014, p. 16
`
`

`

`402
`
`Chapter 8
`
`
`
`Finite State Machine Design
`also supports negative logic outputs as well as outputs that bypass the
`internal flip—flops.
`The state of the finite state machine is represented by the outputs Q
`and Z. EVEN is defined as the state where Q and Z are 0. ODD is
`defined as the state where Q and Z are 1.
`The equa t 1' on section defines outputs in terms of Boolean equations
`of the inputs. In this case, the asynchronous reset (. ar) inputs of the Q
`and Z flip—flops are driven high when the RESET signal is asserted.
`The state__di agram section describes the transitions among states
`using a programming language—like syntax. If we are in EVEN and the
`input X is asserted, we change to ODD. Otherwise we stay in EVEN.
`Similarly,
`if we are in ODD and X is asserted, we return to EVEN.
`Otherwise we stay in state ODD. ABEL supports a variety of control
`constructs, including such things as case statements.
`The final section in this example is for test__vectors. This is a.
`tabular listing of the expected input/output behavior of the finite state
`machine. The first entry describes what happens when RESET is
`asserted: independent of the current value of X, the machine is forced to
`EVEN. The rest of the entries describe the state sequence for the input
`string 111011000. The ABEL system simulates the description to ensure
`that the behavior matches the specified behavior of the test vectors.
`The major weakness of an ABEL description is that it forces the
`designer to understand many low-level details about the target PAL.
`Nevertheless, the state diagram description is an intuitively simple way
`to describe the behavior of a state machine.
`
`
`
`Moore and Mealy Machine Design Procedure
`8.4
`There are two basic ways to organize a clocked sequential network:
`I Moore machine: The outputs depend only on the present state. See
`the block diagram in Figure 8.23. A combinational logic block maps
`the inputs and the current state into the necessary flip-flop inputs to
`store the appropriate next state. The outputs are computed by a com-
`binational logic block whose only inputs are the flip—flops' state out—
`puts. The outputs change synchronously with the state transition and
`the clock edge. The finite state machines you have seen so far are all
`Moore machines.
`Mealy machine: The outputs depend on the present state and the
`present value of the inputs. See Figure 8.24. The outputs can change
`immediately after a change at the inputs, independent of the clock. A
`K Mealy machine constructed in this fashion has asynchronous outputs.
`Moore outputs are synchronous with the clock, only changing with
`state transitions. Mealy outputs are asynchronous and can change in
`response to any changes in the inputs. independent of the clock. This
`
`lb
`
`Petitioner Cypress Semiconductor Corp. - EX. CSC 1014 p 17
`
`Petitioner Cypress Semiconductor Corp. - Ex. CSC 1014, p. 17
`
`

`

`arcs rather than the state bubble. A slash separates the inputs from the
`
`An ASM chart intended for Moore implementation would have no con-
`ditional output boxes. The necessary outputs are simply listed in the
`state box. Conditional output boxes in the ASM chart usually imply a
`Mealy implementation.
`Figure 8.25 shows the notations for Mealy and Moore state diagrams,
`using the vending machine example. For Moore machines, the outputs
`are associated with the state in which they are asserted. Arcs are labeled
`with the input conditions that cause the transition from the state at the
`tail of the arc to the state at its head. Combinational logic functions are
`perfectly acceptable as arc labels.
`In Mealy machines, the outputs are associated with the transition
`
`84 Moore and Mealy Machine Design Procedure
`
`483
`
`State
`Register
`
`_- Comb»
`
`
`Logic f0
`Outputs
`
`= Combinationai - I
`.
`Legic for
`:
`Next State
`[Flip~Flep
`Inputs]
`
`--
`
`
`
`
`
`
`
`
`State
`Feedback
`
`Figure 8.23 Monre machine block diagram.
`
`Combinational
`Logic for
`Outputs and
`Next State
`
`
`
`
`
`
`
`State
`Feedback
`
`Figure 8.24 Mealy machine trJack diagram.
`
`gives Moore machines an advantage in terms of disciplined timing
`methodology. However, there is a synchronous variation of the Mealy
`machine, which we describe later.
`
`8.“
`
`State Diagram and ASE/E Chart Representatians
`
`Petitioner Cypress Semiconductor Corp. - EX. CSC 1014, p. 18
`
`Petitioner Cypress Semiconductor Corp. - Ex. CSC 1014, p. 18
`
`

`

`
`
`404
`
`Chapter 8
`
`Finite State Machine Design
`
`
`
`
`
`
`pm
`
`-E
`
`
`
`
`
`
`
`
`(in) Mealy machine
`(3] Moore machine
`Figure 8.25 Moore and Meaiv machine state diagrams for the vending machine FSM.
`
`if we are in state 10¢ and either N or D is
`outputs. For example,
`(:1. Any glitch on N or D could cause the
`asserted, Open will he asserts
`gum to be delivered by mistake.
`The state diagrams in this figure are labeled more completely than
`le, we make explicit the transitions
`that cause the machine to stay in the same state. We usually eliminate
`such transitions to simplify the state diagram. We also associate explicit
`output values with each transition in the Mealy state diagram and each
`agram. A common simplification places the
`state in the Moore state di
`output on the transition or in the state only when it is asserted. You
`should clarify your assumptions whenever you draw state diagrams.
`
`8.4.2
`Comparison of the Two Machine Types
`one, a Meaty machine can
`Because it can associate outputs with transitifewer states than a Moore
`often generate the same output sequence in
`machine.
`Consider a finite state machine that asserts its single output when-
`ever its input string has at least two 1’s in sequence. The minimum
`Moore and Mealy state diagrams are shown in Figure 8.26. The equiva-
`lent ASM charts are in Figure 8.27.
`To represent the 1’s sequence, the Moore machine requires two states to
`distinguish between the first and subsequent 1’s. The first state has output
`0, while the second has output 1. The Mealy machine accomplishes this
`
`
`
`.
`
`.
`_.l._-_.
`L
`'-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Petitioner Cypress Semiconductor Corp. - EX. CSC 1014 p. 19
`
`Petitioner Cypress Semiconductor Corp. - Ex. CSC 1014, p. 19
`
`

`

`
`
`8.4 Moore and MeaEy Machine Design Procedure
`
`405
`
`
`
`
`with a single state reached by two different transitions. For the first 1, the
`transition has output 0.