Section 8.4  Algorithmic State Machines (ASMs)    363
prototype for evaluation. A schematic and the database for fabricating the integrated 
circuit can be generated automatically by synthesis tools. The HDL model can be com-
piled by different tools into different technologies (e.g., ASIC cells or FPGAs), provid-
ing multiple returns on the investment to create the model.   
8.4    ALGORITHMIC STATE MACHINES (ASMs) 
The binary information stored in a digital system can be classified as either data or 
control information. Data are discrete elements of information (binary words) that are 
manipulated by performing arithmetic, logic, shift, and other similar data‐processing 
Develop/edit HDL
description
Yes
Correct?
No
Simulate/verify HDL
description
Synthesis
tools?
Synthesize
netlist
Develop
(manually)
gate-level
model
Simulate netlist/model
Compare
simulation
results
Create production
masks for ICs
Yes
Test bench
Match?
No
Yes
No
Develop specification
FIGURE 8.1  
A simplified flowchart for HDL‐based modeling, verification, and synthesis       
Convert pdf into powerpoint online - C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
convert pdf into powerpoint online; convert pdf slides to powerpoint online
Convert pdf into powerpoint online - VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
convert pdf to powerpoint online for; export pdf to powerpoint
364    Chapter 8  Design at the Register Transfer Level
operations. These operations are implemented with digital hardware components such 
as adders, decoders, multiplexers, counters, and shift registers. Control information pro-
vides command signals that coordinate and execute the various operations in the data 
section of the machine in order to accomplish the desired data‐processing tasks. 
The design of the logic of a digital system can be divided into two distinct efforts. One 
part is concerned with designing the digital circuits that perform the data‐processing 
operations. The other part is concerned with designing the control circuits that deter-
mine the sequence in which the various manipulations of data are performed. 
The relationship between the control logic and the data‐processing operations in a 
digital system is shown in  Fig.   8.2   . The data‐processing path, commonly referred to as 
the  datapath unit manipulates data in registers according to the system’s requirements. 
The  control unit  issues a sequence of commands to the datapath unit. Note that an 
internal feedback path from the datapath unit to the control unit provides status condi-
tions that the control unit uses together with the external (primary) inputs to determine 
the sequence of control signals (outputs of the control unit) that direct the operation 
of the datapath unit. We’ll see later that understanding how to model this feedback 
relationship with an HDL is very important.  
The control logic that generates the signals for sequencing the operations in the 
datapath unit is a finite state machine (FSM), i.e., a synchronous sequential circuit. The 
control commands for the system are produced by the FSM as functions of the primary 
inputs, the status signals, and the state of the machine. In a given state, the outputs of 
the controller are the inputs to the datapath unit and determine the operations that it 
will execute. Depending on status conditions and other external inputs, the FSM goes 
to its next state to initiate other operations. The digital circuits that act as the control 
logic provide a time sequence of signals for initiating the operations in the datapath and 
also determine the next state of the control subsystem itself. 
Control unit
(FSM)
Input
data
Datapath
unit
Output
data
Control
signals
Status
signals
Input
signals
(external)
FIGURE 8.2  
Control and datapath interaction       
Online Convert PowerPoint to PDF file. Best free online export
Convert a PPTX/PPT File to PDF. Just upload your file by clicking on the blue button or drag-and-drop your pptx or ppt file into the drop area.
how to convert pdf to ppt online; how to convert pdf into powerpoint presentation
RasterEdge XDoc.PowerPoint for .NET - SDK for PowerPoint Document
Convert PowerPoint to ODP/ ODP to PowerPoint. Insert Pages into PowerPoint File. Download Free Trial Download and try PDF for .NET with online support.
convert pdf into ppt; change pdf to powerpoint
Section 8.4  Algorithmic State Machines (ASMs)    365
The control sequence and datapath tasks of a digital system are specified by means of 
a hardware algorithm. An algorithm consists of a finite number of procedural steps that 
specify how to obtain a solution to a problem. A hardware algorithm is a procedure for 
solving the problem with a given piece of equipment. The most challenging and creative 
part of digital design is the formulation of hardware algorithms for achieving required 
objectives. The goal is to implement the algorithms in silicon as an integrated circuit. 
A flowchart is a convenient way to specify the sequence of procedural steps and deci-
sion paths for an algorithm. A flowchart for a hardware algorithm translates the verbal 
instructions to an information diagram that enumerates the sequence of operations 
together with the conditions necessary for their execution. An  algorithmic state machine  
(ASM) chart is a flowchart that has been developed to specifically define algorithms for 
execution on digital hardware. A  state machine  is another term for a sequential circuit, 
which is the basic structure of a digital system. 
ASM Chart 
An ASM chart resembles a conventional flowchart, but is interpreted somewhat differ-
ently. A conventional flowchart describes the procedural steps and decision paths of an 
algorithm in a sequential manner, without taking into consideration their time relation-
ship. The ASM chart describes the sequence of events, i.e., the ordering of events in time, 
as well as the timing relationship between the states of a sequential controller and the 
events that occur while going from one state to the next (i.e., the events that are syn-
chronous with changes in the state). The chart is adapted to specify accurately the con-
trol sequence and datapath operations in a digital system, taking into consideration the 
constraints of digital hardware.  
An ASM chart is composed of three basic elements: the state box, the decision box, 
and the conditional box. The boxes themselves are connected by directed edges indicat-
ing the sequential precedence and evolution of the states as the machine operates. There 
are various ways to attach information to an ASM chart. In one, a state in the control 
sequence is indicated by a state box, as shown in  Fig.   8.3   (a). The shape of the state box 
is a rectangle within which are written register operations or the names of output signals 
that the control generates while being in the indicated state. The state is given a symbolic 
name, which is placed within the upper left corner of the box. The binary code assigned 
to the state is placed at the upper right corner. (The state symbol and code can be placed 
State name
Moore-type
output signals, register operations
Binary code
0101
S_pause
R
0
Start_OP_A
(a)
(b)
FIGURE 8.3  
ASM chart state box       
C# PDF insert text Library: insert text into PDF content in C#.net
Able to add a single text character and text string to PDF files using online source codes in C#.NET class value, The char wil be added into PDF page, 0
converting pdf to powerpoint; pdf to ppt converter
XDoc.HTML5 Viewer for .NET, Zero Footprint AJAX Document Image
View, Convert, Edit, Sign Documents and Images. viewer library can be easily integrated into your ASP powerful & profession imaging controls, PDF document, image
how to change pdf to powerpoint slides; convert pdf to powerpoint online
366    Chapter 8  Design at the Register Transfer Level
in other places as well.)  Figure   8.3   (b) gives an example of a state box. The state has the 
symbolic name  S_pause and the binary code assigned to it is 0101. Inside the box is writ-
ten the register operation    R
d
0   , which indicates that register  R  is to be cleared to 0. The 
name  Start_OP_A  inside the box indicates, for example, a Moore‐type output signal that 
is asserted while the machine is in state  S_pause  and that launches a certain operation 
in the datapath unit. 
The style of state box shown in  Fig.   8.3   (b) is sometimes used in ASM charts, but it can 
lead to confusion about when the register operation    R
d
0    is to execute. Although the 
operation is written inside the state box, it actually occurs when the machine makes a 
transition from  S_pause  to its next state. In fact, writing the register operation within the 
state box is a way (albeit possibly confusing) to indicate that the controller must assert 
a signal that will cause the register operation to occur when the machine changes state. 
Later we’ll introduce a chart and notation that are more suited to digital design and that 
will eliminate any ambiguity about the register operations controlled by a state machine. 
The decision box of an ASM chart describes the effect of an input (i.e., a primary, or 
external, input or a status, or internal, signal) on the control subsystem. The box is dia-
mond shaped and has two or more exit paths, as shown in  Fig.   8.4   . The input condition 
to be tested is written inside the box. One or the other exit path is taken, depending on 
the evaluation of the condition. In the binary case, one path is taken if the condition is 
true and another when the condition is false. When an input condition is assigned a 
binary value, the two paths are indicated by 1 and 0, respectively.   
The state and decision boxes of an ASM chart are similar to those used in conven-
tional flowcharts. The third element, the conditional box, is unique to the ASM chart. 
The shape of the conditional box is shown in  Fig.   8.5   (a). Its rounded corners differenti-
ate it from the state box. The input path to the conditional box must come from one of 
the exit paths of a decision box. The outputs listed inside the conditional box are gener-
ated as Mealy‐type signals during a given state; the register operations listed in the 
conditional box are associated with a transition from the state.  Figure   8.5   (b) shows an 
example with a conditional box. The control generates the output signal  Start  while in 
state  S_1  and checks the status of input  Flag . If  Flag  = 1, then  R  is cleared to 0; otherwise, 
R  remains unchanged. In either case, the next state is  S_2 . A register operation is 
Condition
1
2
3
Exit path
Exit path
Exit path
FIGURE 8.4  
ASM chart decision box       
C# PDF Convert to Tiff SDK: Convert PDF to tiff images in C#.net
with specified zoom value and save it into stream The magnification of the original PDF page size Description: Convert to DOCX/TIFF with specified resolution and
adding pdf to powerpoint; copying image from pdf to powerpoint
C# PDF File Split Library: Split, seperate PDF into multiple files
SharePoint. C#.NET control for splitting PDF file into two or multiple files online. Support to break a large PDF file into smaller files.
convert pdf pages to powerpoint slides; how to convert pdf to powerpoint slides
Section 8.4  Algorithmic State Machines (ASMs)    367
associated with  S_2 . We again note that  this style of chart can be a source of confusion 
because the state machine does not execute the indicated register operation    R
d
0    when 
it is in  S_1  or the operation    F
d
G   when it is in  S_2 . The notation actually indicates that 
when the controller is in  S_1 it must assert a Mealy‐type signal that will cause the reg-
ister operation    R
d
0    to execute in the datapath unit
1
, subject to the condition that  Flag  
= 0. Likewise, in state  S_2,  the controller must generate a Moore‐type output signal that 
causes the register operation    F
d
G    to execute in the datapath unit. The operations in 
the datapath unit are synchronized to the clock edge that causes the state to move from 
S_1  to  S_2  and from  S_2  to  S_3 respectively. Thus,  the control signal generated in a given 
state affects the operation of a register in the datapath when the next clock transition 
occurs.  The result of the operation is apparent in the next state. 
The ASM chart in  Fig.   8.5   (b) mixes descriptions of the datapath and the controller. 
An ASM chart for only the controller is shown in  Fig.   8.5   (c), in which the register oper-
ations are omitted. In their place are the control signals that must be generated by the 
control unit to launch the operations of the datapath unit. This chart is useful for describ-
ing the controller, but it does not contain adequate information about the datapath. 
(We’ll address this issue later.)   
Binary code
Conditional
(Mealy) outputs
and register
operations
State name
Moore-type output signals
Unconditional register
operations
Condition
R
0
F G
S_1
001
Flag
S_2
0
Reset_b
010
Start
1
S_3
100
S_1
001
Flag
Load_F_G
0
Reset_b
010
Flush_R
Start
1
S_3
100
S_2
(a)
(b)
(c)
FIGURE 8.5  
ASM chart conditional box and examples       
1 If the path came from a state box the asserted signals would be moore type signals, dependent on only the 
state, and should be listed within the box.
VB.NET PDF File Split Library: Split, seperate PDF into multiple
Split PDF file into two or multiple files in ASP.NET webpage online. Support to break a large PDF file into smaller files in .NET WinForms.
how to convert pdf to powerpoint on; create powerpoint from pdf
C# PDF Page Insert Library: insert pages into PDF file in C#.net
from the ability to inserting a new PDF page into existing PDF or pages from various file formats, such as PDF, Tiff, Word, Excel, PowerPoint, Bmp, Jpeg
convert pdf to powerpoint slides; table from pdf to powerpoint
368    Chapter 8  Design at the Register Transfer Level
ASM Block 
An ASM block is a structure consisting of one state box and all the decision and condi-
tional boxes connected to its exit path. An ASM block has one entrance and any number 
of exit paths represented by the structure of the decision boxes. An ASM chart consists 
of one or more interconnected blocks. An example of an ASM block is given in  Fig.   8.6   . 
Associated with state  S_0  are two decision boxes and one conditional box. The diagram 
distinguishes the block with dashed lines around the entire structure, but this is not usu-
ally done, since the ASM chart uniquely defines each block from its structure. A state 
box without any decision or conditional boxes constitutes a simple block.  
Each block in the ASM chart describes the state of the system during one clock‐pulse 
interval (i.e., the interval between two successive active edges of the clock). The opera-
tions within the state and conditional boxes in  Fig.   8.6   (a) are initiated by a common 
clock pulse when the state of the controller transitions from  S_0  to its next state. The 
same clock pulse transfers the system controller to one of the next states,  S_1,   S_2 or 
S_3 as dictated by the binary values of  E  and  F . The ASM chart for the controller alone 
is shown in  Fig.   8.6   (b). The Moore‐type signal  incr_A  is asserted unconditionally while 
the machine is in  S_0 ; the Mealy‐type signal  Clear_R  is generated conditionally when 
the state is  S_0  and  E  is asserted. In general, the Moore‐type outputs of the controller 
are generated unconditionally and are indicated within a state box; the Mealy‐type 
outputs are generated conditionally and are indicated in the conditional boxes con-
nected to the edges that leave a decision box. 
The ASM chart is similar to a state transition diagram. Each state block is equivalent 
to a state in a sequential circuit. The decision box is equivalent to the binary information 
R
0
A A + 1
S_0
001
E
F
S_3
S_1
S_2
1
010
Reset_b
100
011
1
S_0
001
E
F
S_3
S_1
S_2
1
010
Reset_b
100
011
1
incr_A
Clear_B
(a)
(b)
FIGURE 8.6  
ASM blocks       
Section 8.4  Algorithmic State Machines (ASMs)    369
written along the directed lines that connect two states in a state diagram. As a conse-
quence, it is sometimes convenient to convert the chart into a state diagram and then use 
sequential circuit procedures to design the control logic. As an illustration, the ASM chart 
of  Fig.   8.6    is drawn as a state diagram (outputs are omitted) in  Fig.   8.7   . The states are 
symbolized by circles, with their binary values written inside. The directed lines indicate 
the conditions that determine the next state. The unconditional and conditional opera-
tions that must be performed in the datapath unit are not indicated in the state diagram.  
Simplifications 
A binary decision box of an ASM chart can be simplified by labeling only the edge cor-
responding to the asserted decision variable and leaving the other edge without a label. 
Afurther simplification is to omit the edges corresponding to the state transitions that 
occur when a reset condition is asserted. Output signals that are not asserted are not shown 
on the chart; the presence of the name of an output signal indicates that it is asserted.   
Timing Considerations 
The timing for all registers and flip‐flops in a digital system is controlled by a master‐
clock generator. The clock pulses are applied not only to the registers of the datapath, 
but also to all the flip‐flops in the state machine implementing the control unit. Inputs 
are also synchronized to the clock, because they are normally generated as outputs of 
another circuit that uses the same clock signals. If the input signal changes at an arbitrary 
time independently of the clock, we call it an asynchronous input. Asynchronous inputs 
may cause a variety of problems. To simplify the design, we will assume that all inputs 
are synchronized with the clock and change state in response to an edge transition. 
The major difference between a conventional flowchart and an ASM chart is in inter-
preting the time relationship among the various operations. For example, if  Fig.   8.6    were 
a conventional flowchart, then the operations listed would be considered to follow one 
after another in sequence: First register  A  is incremented, and only then is  E  evaluated. 
If  E  = 1, then register  R  is cleared and control goes to state  S_3 . Otherwise (if  E  = 0), 
the next step is to evaluate  F  and go to state  S_1  or  S_2 . In contrast, an ASM chart con-
siders the entire block as one unit. All the register operations that are specified within 
001
011
010
100
EF= 00
EF= 01
E= 1
FIGURE 8.7  
State diagram equivalent to the ASM chart of  Fig.   8.6          
370    Chapter 8  Design at the Register Transfer Level
the block must occur in synchronism at the edge transition of the same clock pulse while 
the system changes from  S_0  to the next state. This sequence of events is presented 
pictorially in  Fig.   8.8   . In this illustration, we assume positive‐edge triggering of all flip‐
flops. An asserted asynchronous reset signal ( reset_b ) transfers the control circuit into 
state  S_0 . While in state  S_0 the control circuits check inputs  E  and  F  and generate 
appropriate signals accordingly. If  reset_b  is not asserted, the following operations occur 
simultaneously at the next positive edge of the clock: 
 
1.   Register  A  is incremented.  
 
2.   If  E  = 1, register  R  is cleared.  
 
3.   Control transfers to the next state, as specified in  Fig.   8.7   .   
Note that the two operations in the datapath and the change of state in the control logic 
occur at the same time. Note also that the ASM chart in  Fig.   8.6   (a) indicates the register 
operations that must occur in the datapath unit, but does not indicate the control signal 
that is to be formed by the control unit. Conversely, the chart in  Fig.   8.6   (b) indicates the 
control signals, but not the datapath operations. We will now present an ASMD chart to 
provide the clarity and complete information needed by logic designers.   
ASMD Chart 
Algorithmic state machine and datapath (ASMD) charts were developed to clarify the 
information displayed by ASM charts and to provide an effective tool for designing a 
control unit for a given datapath unit. An ASMD chart differs from an ASM chart in 
three important ways: (1) An ASMD chart does not list register operations within a state 
box, (2) the edges of an ASMD chart are annotated with register operations that are 
concurrent with the state transition indicated by the edge, and (3) an ASMD chart 
includes conditional boxes identifying the signals which control the register operations 
that annotate the edges of the chart. Thus,  an ASMD chart associates register operations 
with state transitions rather than with states ; it also associates register operations with the 
signals that cause them. Consequently, an ASMD chart represents a partition of a com-
plex digital machine into its datapath and control units and clearly indicates the relation-
ship between them. There is no room for confusion about the timing of register 
operations or about the signals that launch them. 
Designers form an ASMD chart in a three‐step process that creates an annotated and 
completely specified ASM chart for the controller of a datapath unit. 
Present state
( S_0 )
Next state
(S_1 or S_2 or S_3)
Clock
Positive edge of Clock
FIGURE 8.8  
Transition between states       
Section 8.5  Design Example (ASMD Chart)    371
The steps to form an ASMD chart are:  
 
1.   Form an ASM chart showing only the states of the controller and the input signals 
2
that cause state transitions,  
 
2.   Convert the ASM chart into an ASMD chart by annotating the edges of the ASM 
chart to indicate the concurrent register operations of the datapath unit (i.e., reg-
ister operations that are concurrent with a state transition), and  
 
3.   Modify the ASMD chart to identify the control signals that are generated by the 
controller and that cause the indicated operations in the datapath unit.   
The ASMD chart produced by this process clearly and completely specifies the finite 
state machine of the controller, identifies the registers operations of the datapath unit, 
identifies signals reporting the status of the datapath to the controller, and links register 
operations to the signals that control them. 
One important use of a state machine is to control register operations on a datapath 
in a sequential machine that has been partitioned into a controller and a datapath. An 
ASMD chart links the ASM chart of the controller to the datapath it controls in a man-
ner that serves as a universal model representing all synchronous digital hardware 
design. ASMD charts help clarify the design of a sequential machine by separating the 
design of its datapath from the design of the controller, while maintaining a clear rela-
tionship between the two units. Register operations that occur concurrently with state 
transitions are annotated on a path of the chart, rather than in state boxes or in condi-
tional boxes on the path, because these registers are not part of the controller. The 
outputs generated by the controller are the signals that control the registers of the 
datapath and cause the register operations annotated on the ASMD chart.   
8.5    DESIGN EXAMPLE (ASMD CHART) 
We will now present a simple example demonstrating the use of the ASMD chart and 
the register transfer representation. We start from the initial specifications of a system 
and proceed with the development of an appropriate ASMD chart from which the 
digital hardware is then designed. 
The datapath unit is to consist of two  JK  flip‐flops  E  and  F and one four‐bit binary 
counter  A[3: 0] . The individual flip‐flops in  A  are denoted by    A
3
A
2
A
1
,and A
0
, with A
3
holding the most significant bit of the count. A signal,  Start initiates the system’s oper-
ation by clearing the counter  A  and flip‐flop  F . At each subsequent clock pulse, the 
counter is incremented by 1 until the operations stop. Counter bits    A
2
and    A
3
determine 
the sequence of operations: 
If    A
2
= 0   ,  E  is cleared to 0 and the count continues.  
If    A
2
=1   ,  E  is set to 1; then, if    A
3
= 0   , the count continues, but if    A
3
= 1   ,  F  is set to 
1 on the next clock pulse and the system stops counting.  
2 In general, the inputs to the control unit are external (primary) inputs and status signals that originate in 
the datapath unit.
372    Chapter 8  Design at the Register Transfer Level
Then, if  Start  = 0, the system remains in the initial state, but if  Start  = 1, the operation 
cycle repeats.   
A block diagram of the system’s architecture is shown in  Fig.   8.9   (a), with (1) the 
registers of the datapath unit, (2) the external (primary) input signals, (3) the status 
signals fed back from the datapath unit to the control unit, and (4) the control signals 
generated by the control unit and input to the datapath unit. Note that the names of the 
control signals clearly indicate the operations that they cause to be executed in the 
datapath unit. For example,  clr_A_F  clears registers  A  and  F . The name of the signal 
reset_b  (alternatively,  reset_bar ) indicates that the reset action is active low. The internal 
details of each unit are not shown. 
ASMD Chart 
An ASMD chart for the system is shown in  Fig.   8.9   (b) for asynchronous reset action and 
in  Fig.   8.9   (c) for synchronous reset action. The chart shows the state transitions of the 
controller and the datapath operations associated with those transitions. The chart is not 
in its final form, for it does not identify the control signals generated by the controller. 
The nonblocking Verilog operator (6=) is shown instead of the arrow    (
d
)    for register 
transfer operations because we will ultimately use the ASMD chart to write a Verilog 
description of the system. 
When the reset action is synchronous, the transition to the reset state is synchronous 
with the clock. This transition is shown for  S_idle  in the diagram, but  all other synchro-
nous reset paths are omitted for clarity . The system remains in the reset state,  S_idle until 
Start  is asserted. When that happens (i.e.,  Start  = 1), the state moves to  S_1. At the next 
clock edge depending on the values of    A
2
and    A
3
(decoded in a priority order), the state 
returns to  S_1  or goes to  S_2 . From  S_2 it moves unconditionally to  S_idle where it 
awaits another assertion of  Start . 
The edges of the chart represent the state transitions that occur at the active (i.e., 
synchronizing) edge of the clock (e.g., the rising edge) and are annotated with the 
register operations that are to occur in the datapath. With  Start  asserted in  S_idle 
the state will transition to  S_1  and the registers  A  and  F  will be cleared. Note that, 
on the one hand, if a register operation is annotated on the  edge  leaving a state box, 
the operation occurs unconditionally and will be controlled by a Moore‐type signal. 
For example, register  A  is incremented at every clock edge that occurs while the 
machine is in the state  S_1 . On the other hand, the register operation setting register 
E  annotates the edge leaving the  decision box  for    A
2
. The signal controlling the 
operation will be a Mealy‐type signal asserted when the system is in state  S_1  and 
A
2
has the value 1. Likewise, the control signal clearing  A  and  F  is asserted condition-
ally: The system is in state  S_idle  and  Start  is asserted. 
In addition to showing that the counter is incremented in state  S_1 the annotated 
paths show that other operations occur conditionally with the same clock edge: 
Either  E  is cleared and control stays in state  S_1     (A
2
= 0)    or  
E  is set and control stays in state  S_1     (A
2
A
3
= 10)    or  
E  is set and control goes to state  S_2     (A
2
A
3
=11).      
Documents you may be interested
Documents you may be interested