Transcript Digital

Digital Logic Design
Lecture # 19
University of Tehran
Outline


Continuing on Designing a 110 Detector
Using Moore Machine Method
Continuing on Designing a 011 Detector
Using Mealy Machine Method
Continuing on Designing a 110
Detector Using Moore Machine
Method
S 0
00 a a
01 b a
1 w
b
c
11
c
b
c d
10 d a
0
0

Let us continue the design of the sequence detector
for 110, that we started last session. We saw the
state diagram, now we want to work through a
couple more states to be able to find the circuit itself.
First we change the state diagram to a tabular form
as shown in this figure. This table is called a state
table that nears the state diagram to tables we saw
State
before, such as the KM etc.
x
0

1
S+
Next state
Output
Continuing on Designing a 110
Detector Using Moore Machine
Method (continued…)

Ultimately we need a form of the above table that
can be mapped in a KM. To do this we naturally
need to replace the state names with numbers. We
can use binary state assignment, where a unique
binary number is used to represent each state. In
order to make our state table more fitting to the KM
we can use the state assignment shown in the
previous slide.
Continuing on Designing a 110
Detector Using Moore Machine
Method (continued…)
Redrawing the state table after state assignment we
have the transition table as shown below:
v1v0 0 x 1
w
0
0

00 00
01
01 00
11
11 10
11
0
10 00
01
1
v1+v0+

Quote: Until now we haven’t ever talked about
having a clock explicitly. But it can be implied from
the fact that we have referred to a next state.
Continuing on Designing a 110
Detector Using Moore Machine
Method (continued…)



The next step of our synthesis is a decision that has
to be made about the type of flip flop we want to
use.
Because of the 4 states we have we will need 2
feedback lines (referring to the Huffman model) and
this means 2 flip flops with one clock on them.
The next stage (after choosing a particular flip flop)
is to form an excitation table considering that
particular flip flop in order to reach a stage where we
can move what we’ve had so far to a KM.
Continuing on Designing a 110
Detector Using Moore Machine
Method (continued…)
If we choose a D flip flop (as we will now for the last
example), the excitation table will simply be a copy of
the transition table we’ve seen above, this is because
for a D flip flop we have Q+=D. Thus we have:
v1v0 0 x 1
w
00 00
01
01 00
11
10 10
11
0
0
0

11 00
01
1
D 1D 0
Continuing on Designing a 110
Detector Using Moore Machine
Method (continued…)

Considering the Huffman model and the fact that we
have now the excitation tables for the flip flop inputs
we can find the glue logic needed before the inputs
of the flip flops. This is done by mapping the data in
the excitation table on a KM for D1 and D0:
w
x
Combinational
x
v1v0
0
1
x
v1v0
00
0
1
00
01
v0
v1
clock
v0+
4
0
1
1
3
10
1
6
D0=x
0
4
0
1
1
5
1
3
1
1
0
0
11
7
0
2
01
5
0
11
v1+
Huffman Model
0
0
10
1
7
0
2
0
6
D1=xv0 +v1v0
Continuing on Designing a 110
Detector Using Moore Machine
Method (continued…)


Quote: These maps can be filled by considering
corresponding slices of the excitation table.
The KM for the outputs equation:
x
v1v0
0
1
00
0
0
01
0
4
0
1
0
5
0
11
3
10
0
7
1
2
1
6
_
w=v1v0
Continuing on Designing a 110
Detector Using Moore Machine
Method (continued…)


Note: The outputs equation shows it’s independency
of the input (as we are using Moore Machines).
With these equations we can now sketch the final
logic circuit:
x
D1
1
v1
0
v0
*
D0
clock
w
Continuing on Designing a 110
Detector Using Moore Machine
Method (continued…)

The timing diagram of the above circuit looks
something like the following figure:
clock
x
w

We aren’t considered what the value of the output is
between the clock pulses. Values are only important
on the rising edges of the clock pulses (considering
that we have used rising edge D flip flops).
Continuing on Designing a 110
Detector Using Moore Machine
Method (continued…)


The mentioned method is valued because of its
scalability and mechanical steps that makes it a good
choice when it comes down to computer use for aid
in design.
Note: Let’s consider a state where a hazard may
occur in the point marked ‘*’ in the circuit of the last
example. Reality has it that we needn’t worry about
this happening because it can be easily solved by
setting the clock frequency to work on the worst case
delay and thus after any hazards that may occur in
such parts of a circuit.
Continuing on Designing a 110
Detector Using Moore Machine
Method (continued…)

Static flip flops can be used with any frequency less
than the maximum which is decided considering the
above mentioned, but when we are using dynamic
flip flops we also need to be concerned about a
minimum frequency, because data may be lost if we
do not refresh the transistors in time.
Continuing on Designing a 011
Detector Using Mealy Machine
Method


If we relax timing issues a little in our design,
another sate machine that can be more minimal can
be used. In this machine called the Mealy Machine,
the output is dependent on input changes and thus is
no longer synchronized to the clock.
The following is the Mealy machine for the 011
detector. The output changes to 1 as soon as the 0
of the sequence is seen.
0/0
a
1/0
1/0
1/0
b
0/0
0/1
c
Continuing on Designing a 011
Detector Using Mealy Machine
Method (continued…)
Let’s follow the steps mentioned for turning the state
diagram to the final circuit:
0
00 a a
01 b a
11
x
c a
1
b
c
x
x
v1v0
0
1
0
0
0
0
0
c 1
output
00
01
State Table
1 0
00 00
01
01 00
11
11 00
11
v1+v0+
0
0
x
0
0
0
1
0
00
5
1
01
D1=xv0
1
0
0
1
4
0
1
1
5
0
3
_
6
0
11
7
_
2
x
v1v0
1
0
10
1
4
3
1
0
1
output
Transition Table
0
11
0
0
v1v0 0
x

1
7
_
10
2
_
6
D0=x
Continuing on Designing a 011
Detector Using Mealy Machine
Method (continued…)
x
v1v0
00
0
1
0
0
0
4
x
01
0
1
3
2
v1
D0
0
v0
0
0
7
_
10
1
5
1
11
D1
_
6
_
w=xv1
clock
w
Continuing on Designing a 011
Detector Using Mealy Machine
Method (continued…)


In some cases, relaxing time issues of the problem
and using Mealy machines can help a lot in less
hardware use.
The contribution of the input signal to the output in
Mealy machines means less precision because any
hazard on the input (noise, hazards from the levels
before etc) can easily propagate onto the output.
Because of such problems, Mealy machines can be
never used in very precise designs.
Continuing on Designing a 011
Detector Using Mealy Machine
Method (continued…)

The following timing diagram shows the differences
in the two state machines output very clearly. The
contribution of the input on the output can be seen in
the timing diagram as well:
clock
a
a
a
a
b
b
c
c
d
a
a
a
x
x
w (Moore machine)
x
w(Mealy machine)
Continuing on Designing a 011
Detector Using Mealy Machine
Method (continued…)

Quote: In synchronous sequential circuits we only
care about the output’s value on clock pulses and we
don’t care about its value at instances in between.