1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html><head><title>Example of a Mealy Machine: string recognizer</title>
<meta name="GENERATOR" content="User-Agent: Mozilla/3.0Gold (Macintosh; I; 68K)">
<meta name="Author" content="J. Van der Spiegel"></head><body>
<h1 align="center"><i><font size="+1">University of Pennsylvania</font></i>
</h1>
<center><p><i><font size="+1">Department of Electrical Engineering </font></i><br>
<br>
</p></center>
<center><p><b>Finite State Machine implemented as a Mealy Machine: </b></p></center>
<center><p><b>a non-resetting sequence recognizer.</b><br>
</p></center>
<p>The following state diagram (Fig. 1) describes a finite state machine
with one input X and one output Z. The FSM asserts its output Z when it
recognizes the following input bit sequence: "1011". The machine
will keep checking for the proper bit sequence and does not reset to the
initial state after it has recognized the string. As an example the input
string X= "..1011011..." will cause the output to go high twice:
Z = "..0001001.." . When the machine is in the state S3 the output
will go high after the arrival of a "1" at the input. Thus the
output is associated with the <i>transitions</i> as indicated on the state
diagram.</p>
<center><p><br>
<img src="abel.ex1-Dateien/abel_002.gif" height="101" width="262"><br>
<br>
</p></center>
<p>Figure 1: State diagram, describing the sequence detector implemented
as a Mealy machine. The number in italics underneath the states indicate
which part of the sequence the state remembers.<br>
</p>
<p>This state diagram can be described in ABEL code given in Listing 1.
The output is described with the "<font face="Courier">With</font>"
keyword to indicate that the output will change when the input goes to
one. <br>
</p>
<p><font color="#000000">Listing 1: ABEL source code for the Mealy Machine
implementation of the sequence detector described in Fig. 1</font><br>
</p>
<ul>
<p><font size="-1"><font face="Courier"><font color="#000000">module Seqdet1</font></font>
</font></p>
</ul>
<ul>
<p><font face="Courier"><font color="#000000"><font size="-1">Title 'Sequence
Detector 1011 with Mealy Machine'</font></font></font><br>
</p>
<p><font face="Courier"><font color="#000000"><font size="-1">Declarations<br>
"Input and output signals</font></font></font></p>
<p><font size="-1"><font face="Courier"><font color="#000000">X, CLOCK, RST
PIN;</font></font> <br>
<font face="Courier"><font color="#000000">Z PIN istype 'com';</font></font>
<br>
<font face="Courier"><font color="#000000">Q1, Q0 PIN istype 'reg';</font></font>
</font></p>
<p><font size="-1"><font face="Courier"><font color="#000000">"State
register definitions</font></font> <br>
<font face="Courier"><font color="#000000">" and assignments of state
values</font></font> </font></p>
<p><font size="-1"><font face="Courier"><font color="#000000">SREG = [Q1,Q0];</font></font>
<br>
<font face="Courier"><font color="#000000">S0 = [0,0];</font></font> <br clear="right">
<font face="Courier"><font color="#000000">S1 = [0,1];</font></font> <br>
<font face="Courier"><font color="#000000">S2 = [1,0];</font></font> <br>
<font face="Courier"><font color="#000000">S3 = [1,1];</font></font></font><br>
</p>
<p><font face="Courier"><font color="#000000"><font size="-1">Equations<br>
"Define the clock signal for the state machine</font></font></font></p>
<p><font size="-1"><font face="Courier"><font color="#000000">[Q1,Q0].AR
= RST;</font></font> <br>
<font face="Courier"><font color="#000000">[Q1,Q0].CLK =CLOCK;</font></font></font><br>
</p>
<p><font size="-1"><font face="Courier"><font color="#000000">"Define
state diagram</font></font> </font></p>
<p><font size="-1"><font face="Courier"><font color="#000000">STATE_DIAGRAM
SREG</font></font> </font></p>
<p><font size="-1"><font face="Courier"><font color="#000000">STATE S0: IF
X THEN S1 ELSE S0;</font></font> <br>
<font face="Courier"><font color="#000000">STATE S1: IF X THEN S1 ELSE
S2;</font></font> <br>
<font face="Courier"><font color="#000000">STATE S2: IF X THEN S3 ELSE
S0;</font></font> <br>
<font face="Courier"><font color="#000000">STATE S3: IF X THEN S1 WITH
Z=1; ELSE S2;</font></font></font><br>
</p>
<p><font face="Courier"><font color="#000000"><font size="-1">end Seqdet1</font></font></font><br>
</p>
</ul>
<p>The ouput is specified with the "With" keyword. The corresponding
simulation is shown in Figure 2. </p>
<center><p><br>
<br>
<img src="abel.ex1-Dateien/abel_003.gif" height="333" width="548"><br>
</p></center>
<center><p>Figure 2: Simulation of the sequence detector for "1011"
described with the state diagram of Fig. 1. (Screen clip from Xilinx XACTstep(TM)
Foundation software)<br>
</p></center>
<p>Notice that the output Z asserts as soon as the input is "1"
when in state S3. Comparing this output with the one obtained for a <a href="http://www.ese.upenn.edu/rca/software/abel/abel.ex2.html">Moore
machine</a> of the same sequence detector may let a casual observer think
that there is a timing problem as the output seems to asserts already after
the "101" input sequence. However, when one looks at the output
carefully one concludes that the waveform is correct. One has to realize
that the outputs are valid at the end of the state time (just before the
positive clock-edge) while the valid inputs are sampled just before the
positive clock edge as indicated in Figure 3 below. The input sequence
"1011" gives indeed an output sequence of "0001". </p>
<center><p><img src="abel.ex1-Dateien/abel.gif" height="332" width="547"></p></center>
<center><p>Figure 3: Output waveform of the Mealy machine (sequence detector
for "1011") with valid inputs and outputs indicated. (Screen
clip from Xilinx XACTstep(TM) Foundation software)</p></center>
<p>One notices that there is a glitch in the output after the input sequence
10111010. However this occurs at a moment that the output is not valid
(the output is valid just before the positive clock edge). The valid output
sequence is than 000100000 as expected. </p>
<p>This example indicates that one has to be very careful with the timing
when using a Mealy machine. Outputs can show glitches and are only valid
at the end of a state time (i.e. just before the the positive clock edge
for a positive edge triggered flip-flop or just before the negative clock
transition for a negative egde triggered flip-flop). On the other hand
a Mealy machine can often be implemented with fewer states that a Moore
machine as can be seen from the <a href="http://www.ese.upenn.edu/rca/software/abel/abel.ex2.html">Moore example</a>.
An alternative way to prevent glitches and to make the ouput of a Mealy
machine synchronous with the clock, it to use a synchronous Mealy machine.
The implementation of the sequence detector as a synchronous Mealy machine
is given in the <a href="http://www.ese.upenn.edu/rca/software/abel/abel.ex3.html">next example</a>.<br>
</p>
<p>
</p><hr width="100%"><font size="-1">Back to ABEL Primer <a href="http://www.ee.upenn.edu/rca/software/abel/abel.primer.html#Contents">Contents</a>
| To to <a href="http://www.ee.upenn.edu/rca/software/xilinx/foundation/commistakes.html">Common
Mistakes</a> list | Go to the <a href="http://www.ee.upenn.edu/rca">EE
Undergraduate Lab</a> Homepage | Go to <a href="http://www.ee.upenn.edu/rca/software/xilinx.html">Xilinx
Lab Tutorial</a> Homepage | Go to the <a href="http://www.ee.upenn.edu/rca/software/xilinx/foundation/foundation.sch1.html">Foundation
Tutorial</a> page | Go to <a href="http://www.seas.upenn.edu/%7Eee200/">EE200
</a>or <a href="http://www.seas.upenn.edu/%7Eee200/lab/lab.html">EE200 Lab</a>
Homepage |</font><p></p>
<p>
</p><hr width="100%">Created by J. Van der Spiegel: November 16, 1997; Updated
by J. Van der Spiegel: Dec. 30, 1997.<p></p>
</body></html>
|
