# designing a circuit

Discussion in 'Electronic Basics' started by Mike Herbakovich, Oct 11, 2003.

1. ### Mike HerbakovichGuest

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

2. ### Keith R. WilliamsGuest

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
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".

3. ### petrus bitbyterGuest

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

4. ### Keith R. WilliamsGuest

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).
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>

5. ### Mike HerbakovichGuest

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.

6. ### Keith R. WilliamsGuest

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.
You would. THey're equivalent (from the 90 seconds I looked at
them).
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.
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

I can do email, though will answer here.

7. ### petrus bitbyterGuest

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

8. ### Keith R. WilliamsGuest

You're right. I always muck-up grey/gray; not in only this context. :-(