designing a circuit

[Mike Herbakovich]

I have to design a circuit that recognizes the sequence 1101 with D flip
flops. So I need two flip flops. But I don't understand the state table,
why does the Present state in the third row 11 instead of 10?

Present Next State Ouput Z
State x=0 x=1 x=0 x=1
00 00 01 0 0
01 00 11 0 0
11 10 11 0 0
10 00 01 0 1

Here's the link, Table 4-7 which is a binary representation of Table 4-5.
The state diagram is Figure 4-21
ftp://ftp.prenhall.com/pub/esm/electrical_and_computer_engineering.s-045/mano/lcdf_2e_updated/supplements/ch04.pdf
I switched row three with row four and got
my equations
D_1= BX+AB
D_2= X
Z= AB'X

 

[Keith R. Williams]

In article <bm9fif$k4lfh$1@ID-198839.news.uni-berlin.de>,
ioqv@hotmail.com says...

I have to design a circuit that recognizes the sequence 1101 with D flip
flops. So I need two flip flops. But I don't understand the state table,
why does the Present state in the third row 11 instead of 10?

I can't get to your FTP site, but I presume the designer wanted a
grey-encoded state machine. Grey encoded state machines have the
advantage that only one bit changes at a time (for the valid
tree), thus you won't have glitches causing a false "true" on the
output ('Z').

--
Keith

Present Next State Ouput Z
State x=0 x=1 x=0 x=1
00 00 01 0 0
01 00 11 0 0
11 10 11 0 0
10 00 01 0 1

Here's the link, Table 4-7 which is a binary representation of Table 4-5.
The state diagram is Figure 4-21
ftp://ftp.prenhall.com/pub/esm/electrical_and_computer_engineering.s-045/mano/lcdf_2e_updated/supplements/ch04.pdf
I switched row three with row four and got
my equations
D_1= BX+AB
D_2= X
Z= AB'X

If you do as (I think) you suggest (a bit more than switching
lines) and have a binary encoded state machine:

Present Next State Ouput Z
State x=0 x=1 x=0 x=1
00 00 01 0 0
01 00 10 0 0
10 11 00 0 0
11 10 01 0 1
^^ kinda strange transition

Netween state "01" and "10" there may be a delay difference
between the two FFs causing a transient "11" on the outputs and
thus a glitch on output "Z".

 

[petrus bitbyter]

"Mike Herbakovich" <ioqv@hotmail.com> schreef in bericht
news:bm9fif$k4lfh$1@ID-198839.news.uni-berlin.de...

I have to design a circuit that recognizes the sequence 1101 with D flip
flops. So I need two flip flops. But I don't understand the state table,
why does the Present state in the third row 11 instead of 10?

Present Next State Ouput Z
State x=0 x=1 x=0 x=1
00 00 01 0 0
01 00 11 0 0
11 10 11 0 0
10 00 01 0 1

Here's the link, Table 4-7 which is a binary representation of Table 4-5.
The state diagram is Figure 4-21

ftp://ftp.prenhall.com/pub/esm/electrical_and_computer_engineering.s-045/mano/lcdf_2e_updated/supplements/ch04.pdf
I switched row three with row four and got
my equations
D_1= BX+AB
D_2= X
Z= AB'X


Mike,

The table (4-7) you mentioned, may be good to show what has to happed e.g.
the definition of the case. However, from the designers point of view it is
not so clear. A simplified method to describe the funtion to design it by
D-flip-flops is a kind of truth table. The current state, represented by Q0,
Q1 along with the input signal X can be considered as inputs. The next state
represented by D0, D1 and the output signal Z are outputs. So you find the
following table:

X Q1 Q0 | D1 D0 Z
--------|--------
0 0 0 | 0 0 0
0 0 1 | 0 0 0
0 1 0 | 0 0 0
0 1 1 | 1 0 0
1 0 0 | 0 1 0
1 0 1 | 1 1 0
1 1 0 | 0 1 1
1 1 1 | 1 1 0

Table 4-7 Rewritten for design. Use fixed font (Courier) to view.

From this table you can extract the formulas quite easily.

As for the third row in the original table 4-7, this is a matter of choice.
Theoretically your are free to choose the state codes. In practice, it is
usefull to change as less flipflops as possible when changing state,
especially when the outputs of the flipflops are fed into some combinatorial
logic. Flipflops tend to change not exactly at te same time and this can be
the cause of gliches in the output signal. In this particular case the
"normal" sequence 1101 is represented by the states 00, 01, 11, 10 and 01
again. All but the 10 state change by toggling only one flipflop. The 01
state changes both flipflops while accepting (recognising) the 1101
sequence. It is the only time an output signal has to be made so it may have
some glitches. However, you will not have any glitches as long as the
required sequence has *not* been recognised. In some cases, when glitches
are totaly unacceptable, an extra flipflop is used. But this lays beyond the
current problem I guess.

pieter


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.519 / Virus Database: 317 - Release Date: 18-9-2003

 

[Keith R. Williams]

In article <_r2ib.200392$lh.43268892@amsnews02.chello.com>,
p.kralt@hccnet.nl says...

"Mike Herbakovich" <ioqv@hotmail.com> schreef in bericht
news:bm9fif$k4lfh$1@ID-198839.news.uni-berlin.de...
I have to design a circuit that recognizes the sequence 1101 with D flip
flops. So I need two flip flops. But I don't understand the state table,
why does the Present state in the third row 11 instead of 10?

Present Next State Ouput Z
State x=0 x=1 x=0 x=1
00 00 01 0 0
01 00 11 0 0
11 10 11 0 0
10 00 01 0 1

Here's the link, Table 4-7 which is a binary representation of Table 4-5.
The state diagram is Figure 4-21

ftp://ftp.prenhall.com/pub/esm/electrical_and_computer_engineering.s-045/mano/lcdf_2e_updated/supplements/ch04.pdf
I switched row three with row four and got
my equations
D_1= BX+AB
D_2= X
Z= AB'X


Mike,

The table (4-7) you mentioned, may be good to show what has to happed e.g.
the definition of the case. However, from the designers point of view it is
not so clear. A simplified method to describe the funtion to design it by
D-flip-flops is a kind of truth table. The current state, represented by Q0,
Q1 along with the input signal X can be considered as inputs. The next state
represented by D0, D1 and the output signal Z are outputs. So you find the
following table:

X Q1 Q0 | D1 D0 Z
--------|--------
0 0 0 | 0 0 0
0 0 1 | 0 0 0
0 1 0 | 0 0 0
0 1 1 | 1 0 0
1 0 0 | 0 1 0
1 0 1 | 1 1 0
1 1 0 | 0 1 1
1 1 1 | 1 1 0

Table 4-7 Rewritten for design. Use fixed font (Courier) to view.

From this table you can extract the formulas quite easily.

This is a matter of form. I prefer the original notation. The
state transitions are clearer (for me). Perhaps that's because
I'd generally use an HDL to describe it and the original is
closer to a VHDL case construct. The logic is fairly clear
either way (a grey counter with a synchronous clear).

As for the third row in the original table 4-7, this is a matter of choice.
Theoretically your are free to choose the state codes. In practice, it is
usefull to change as less flipflops as possible when changing state,
especially when the outputs of the flipflops are fed into some combinatorial
logic.

Absolutely. Actually if I were designing this in an FPGA (or
some such), I'd use one (register the output) or two (one-hot
state machine) more FF(s) to be sure the output is registered,
eliminating the need for the grey counter. ...or let the
synthesis tool decide which encoding it preferred. ;-)

<snip>

--
Keith

 

[Mike Herbakovich]

So are my equations right? I get the same equations using petrus bitbyter
table, however I have no idea what a grey counter is and I think that is
what is showing up when I try simulating my circuit in Xilinx Simulator. I
don't get a nice 1 for the output, but like a 1 and grey colour underneath
the line.


"Keith R. Williams" <krw@attglobal.net> wrote in message
news:MPG.19f35fad91b4a34398a7ac@enews.newsguy.com...

In article <_r2ib.200392$lh.43268892@amsnews02.chello.com>,
p.kralt@hccnet.nl says...

"Mike Herbakovich" <ioqv@hotmail.com> schreef in bericht
news:bm9fif$k4lfh$1@ID-198839.news.uni-berlin.de...
I have to design a circuit that recognizes the sequence 1101 with D
flip
flops. So I need two flip flops. But I don't understand the state
table,
why does the Present state in the third row 11 instead of 10?

Present Next State Ouput Z
State x=0 x=1 x=0 x=1
00 00 01 0 0
01 00 11 0 0
11 10 11 0 0
10 00 01 0 1

Here's the link, Table 4-7 which is a binary representation of Table
4-5.
The state diagram is Figure 4-21


ftp://ftp.prenhall.com/pub/esm/electrical_and_computer_engineering.s-045/mano/lcdf_2e_updated/supplements/ch04.pdf
I switched row three with row four and got
my equations
D_1= BX+AB
D_2= X
Z= AB'X


Mike,

The table (4-7) you mentioned, may be good to show what has to happed
e.g.
the definition of the case. However, from the designers point of view it
is
not so clear. A simplified method to describe the funtion to design it
by
D-flip-flops is a kind of truth table. The current state, represented by
Q0,
Q1 along with the input signal X can be considered as inputs. The next
state
represented by D0, D1 and the output signal Z are outputs. So you find
the
following table:

X Q1 Q0 | D1 D0 Z
--------|--------
0 0 0 | 0 0 0
0 0 1 | 0 0 0
0 1 0 | 0 0 0
0 1 1 | 1 0 0
1 0 0 | 0 1 0
1 0 1 | 1 1 0
1 1 0 | 0 1 1
1 1 1 | 1 1 0

Table 4-7 Rewritten for design. Use fixed font (Courier) to view.

From this table you can extract the formulas quite easily.

This is a matter of form. I prefer the original notation. The
state transitions are clearer (for me). Perhaps that's because
I'd generally use an HDL to describe it and the original is
closer to a VHDL case construct. The logic is fairly clear
either way (a grey counter with a synchronous clear).

As for the third row in the original table 4-7, this is a matter of
choice.
Theoretically your are free to choose the state codes. In practice, it
is
usefull to change as less flipflops as possible when changing state,
especially when the outputs of the flipflops are fed into some
combinatorial
logic.

Absolutely. Actually if I were designing this in an FPGA (or
some such), I'd use one (register the output) or two (one-hot
state machine) more FF(s) to be sure the output is registered,
eliminating the need for the grey counter. ...or let the
synthesis tool decide which encoding it preferred. ;-)

snip

--
Keith

 

[Keith R. Williams]

In article <bmcfnv$k3tiq$1@ID-198839.news.uni-berlin.de>,
iop@hotmail.com says...

So are my equations right?

As far as I can tell, yes. It's unclear what to do at the final
state, but other than that I don't seen anything wrong.

I get the same equations using petrus bitbyter
table,

You would. THey're equivalent (from the 90 seconds I looked at
them).

however I have no idea what a grey counter is

Do a web search on "grey counter". It's a counter than only has
one output transition per count. Since there is only one
transition per input, output glitches aren't a huge problem. I
prefer registering all outputs, but that's experience.

and I think that is
what is showing up when I try simulating my circuit in Xilinx Simulator. I
don't get a nice 1 for the output, but like a 1 and grey colour underneath
the line.

I'm not exactly sure what you're looking at, but I'd expect
indeterminate states after the transision, with a binary counter.

I could give you an example of a VHDL solution to this (the final
state transition is still a mystery), if you promise that it's
not an answer to any homework nor exam. Most here are ready to
help you learn, not give answers.

I can do email, though will answer here.

--
Keith

 

[petrus bitbyter]

"Mike Herbakovich" <iop@hotmail.com> schreef in bericht
news:bmcfnv$k3tiq$1@ID-198839.news.uni-berlin.de...

In article <_r2ib.200392$lh.43268892@amsnews02.chello.com>,
p.kralt@hccnet.nl says...

"Mike Herbakovich" <ioqv@hotmail.com> schreef in bericht
news:bm9fif$k4lfh$1@ID-198839.news.uni-berlin.de...
I have to design a circuit that recognizes the sequence 1101 with D
flip
flops. So I need two flip flops. But I don't understand the state
table,
why does the Present state in the third row 11 instead of 10?

Present Next State Ouput Z
State x=0 x=1 x=0 x=1
00 00 01 0 0
01 00 11 0 0
11 10 11 0 0
10 00 01 0 1

Here's the link, Table 4-7 which is a binary representation of Table
4-5.
The state diagram is Figure 4-21



ftp://ftp.prenhall.com/pub/esm/electrical_and_computer_engineering.s-045/mano/lcdf_2e_updated/supplements/ch04.pdf
I switched row three with row four and got
my equations
D_1= BX+AB
D_2= X
Z= AB'X


Mike,

The table (4-7) you mentioned, may be good to show what has to happed
e.g.
the definition of the case. However, from the designers point of view
it
is
not so clear. A simplified method to describe the funtion to design it
by
D-flip-flops is a kind of truth table. The current state, represented
by
Q0,
Q1 along with the input signal X can be considered as inputs. The next
state
represented by D0, D1 and the output signal Z are outputs. So you find
the
following table:

X Q1 Q0 | D1 D0 Z
--------|--------
0 0 0 | 0 0 0
0 0 1 | 0 0 0
0 1 0 | 0 0 0
0 1 1 | 1 0 0
1 0 0 | 0 1 0
1 0 1 | 1 1 0
1 1 0 | 0 1 1
1 1 1 | 1 1 0

Table 4-7 Rewritten for design. Use fixed font (Courier) to view.

From this table you can extract the formulas quite easily.

This is a matter of form. I prefer the original notation. The
state transitions are clearer (for me). Perhaps that's because
I'd generally use an HDL to describe it and the original is
closer to a VHDL case construct. The logic is fairly clear
either way (a grey counter with a synchronous clear).

As for the third row in the original table 4-7, this is a matter of
choice.
Theoretically your are free to choose the state codes. In practice, it
is
usefull to change as less flipflops as possible when changing state,
especially when the outputs of the flipflops are fed into some
combinatorial
logic.

Absolutely. Actually if I were designing this in an FPGA (or
some such), I'd use one (register the output) or two (one-hot
state machine) more FF(s) to be sure the output is registered,
eliminating the need for the grey counter. ...or let the
synthesis tool decide which encoding it preferred. ;-)

snip

--
Keith


So are my equations right? I get the same equations using petrus bitbyter
table, however I have no idea what a grey counter is and I think that is
what is showing up when I try simulating my circuit in Xilinx Simulator.
I
don't get a nice 1 for the output, but like a 1 and grey colour underneath
the line.


"Keith R. Williams" <krw@attglobal.net> wrote in message
news:MPG.19f35fad91b4a34398a7ac@enews.newsguy.com...

Keith,

Gray (not Grey FAIK) developed the so called mirrored binary code also known
as Gray code. This code does not count in the usual binary sequence (so 000,
001, 010,011,100,101,110,111, 000 and so on, but 000, 001, 011, 010, 110,
111, 101, 100, 000, ....... The idea is that in the sequence only one bit at
a time will change. The code is used in code wheels that have to detect the
angle of shafts for instance.

As for your output signal, you have to change the input shortly after the
clock. The high output only exists from the moment the high input appears
untill the next clock.

BTW The last 1 in the recognised 1101 sequence is also considered to be the
possible first 1 of the next sequence. You can easily see it when you make a
state diagram.

pieter


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.525 / Virus Database: 322 - Release Date: 9-10-2003

 

[Keith R. Williams]

In article <%mxib.231430$lh.48495759@amsnews02.chello.com>,
p.kralt@hccnet.nl says...

"Mike Herbakovich" <iop@hotmail.com> schreef in bericht
news:bmcfnv$k3tiq$1@ID-198839.news.uni-berlin.de...
In article <_r2ib.200392$lh.43268892@amsnews02.chello.com>,
p.kralt@hccnet.nl says...

"Mike Herbakovich" <ioqv@hotmail.com> schreef in bericht
news:bm9fif$k4lfh$1@ID-198839.news.uni-berlin.de...
I have to design a circuit that recognizes the sequence 1101 with D
flip
flops. So I need two flip flops. But I don't understand the state
table,
why does the Present state in the third row 11 instead of 10?

Present Next State Ouput Z
State x=0 x=1 x=0 x=1
00 00 01 0 0
01 00 11 0 0
11 10 11 0 0
10 00 01 0 1

Here's the link, Table 4-7 which is a binary representation of Table
4-5.
The state diagram is Figure 4-21



ftp://ftp.prenhall.com/pub/esm/electrical_and_computer_engineering.s-045/mano/lcdf_2e_updated/supplements/ch04.pdf
I switched row three with row four and got
my equations
D_1= BX+AB
D_2= X
Z= AB'X


Mike,

The table (4-7) you mentioned, may be good to show what has to happed
e.g.
the definition of the case. However, from the designers point of view
it
is
not so clear. A simplified method to describe the funtion to design it
by
D-flip-flops is a kind of truth table. The current state, represented
by
Q0,
Q1 along with the input signal X can be considered as inputs. The next
state
represented by D0, D1 and the output signal Z are outputs. So you find
the
following table:

X Q1 Q0 | D1 D0 Z
--------|--------
0 0 0 | 0 0 0
0 0 1 | 0 0 0
0 1 0 | 0 0 0
0 1 1 | 1 0 0
1 0 0 | 0 1 0
1 0 1 | 1 1 0
1 1 0 | 0 1 1
1 1 1 | 1 1 0

Table 4-7 Rewritten for design. Use fixed font (Courier) to view.

From this table you can extract the formulas quite easily.

This is a matter of form. I prefer the original notation. The
state transitions are clearer (for me). Perhaps that's because
I'd generally use an HDL to describe it and the original is
closer to a VHDL case construct. The logic is fairly clear
either way (a grey counter with a synchronous clear).

As for the third row in the original table 4-7, this is a matter of
choice.
Theoretically your are free to choose the state codes. In practice, it
is
usefull to change as less flipflops as possible when changing state,
especially when the outputs of the flipflops are fed into some
combinatorial
logic.

Absolutely. Actually if I were designing this in an FPGA (or
some such), I'd use one (register the output) or two (one-hot
state machine) more FF(s) to be sure the output is registered,
eliminating the need for the grey counter. ...or let the
synthesis tool decide which encoding it preferred. ;-)

snip

--
Keith


So are my equations right? I get the same equations using petrus bitbyter
table, however I have no idea what a grey counter is and I think that is
what is showing up when I try simulating my circuit in Xilinx Simulator.
I
don't get a nice 1 for the output, but like a 1 and grey colour underneath
the line.


"Keith R. Williams" <krw@attglobal.net> wrote in message
news:MPG.19f35fad91b4a34398a7ac@enews.newsguy.com...

Keith,

Gray (not Grey FAIK)

You're right. I always muck-up grey/gray; not in only this context. :-(
http://www.nist.gov/dads/HTML/graycode.html

developed the so called mirrored binary code also known
as Gray code. This code does not count in the usual binary sequence (so 000,
001, 010,011,100,101,110,111, 000 and so on, but 000, 001, 011, 010, 110,
111, 101, 100, 000, ....... The idea is that in the sequence only one bit at
a time will change. The code is used in code wheels that have to detect the
angle of shafts for instance.

As for your output signal, you have to change the input shortly after the
clock. The high output only exists from the moment the high input appears
untill the next clock.

BTW The last 1 in the recognised 1101 sequence is also considered to be the
possible first 1 of the next sequence. You can easily see it when you make a
state diagram.

I thought that transition a tad suspect too, but that's the homework
problem. ;-)

--
Keith