Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronic Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Register Log in

Sequence detector Mealy Diagram

noobeestudent

Member level 1
Joined
Jul 4, 2019
Messages
37
Helped
0
Reputation
0
Reaction score
0
Trophy points
6
Activity points
287
Hi guys, I was tasked to built a 8-bit 2 sequences detector.

The sequences are 0111 0011 and 0100 0010. I have a question.
Is it possible to group the bits if they have an identical value?

For example,
1605878205615.png
grouping them like this to reduce the number of states in the Mealy diagram.

Is it possible? Please let me know. Any help would be appreciated
 

FvM

Super Moderator
Staff member
Joined
Jan 22, 2008
Messages
47,644
Helped
14,072
Reputation
28,401
Reaction score
12,739
Trophy points
1,393
Location
Bochum, Germany
Activity points
276,823
Possible yes, but it comprises the concept of advanding the state machine based only on the present sequence bit. You need to memorize the previous sequence bit.

It's a step towards a different sequence detector method that reads the sequence bit into a shift register and compare all bits at once. Presumedly not the intended solution of your exercise problem.

It would be interesting to check which sequence detector is optimal in terms of used hardware resources (registers and logic elements). A possible extra after solving the problem straightforwardly.
 

noobeestudent

Member level 1
Joined
Jul 4, 2019
Messages
37
Helped
0
Reputation
0
Reaction score
0
Trophy points
6
Activity points
287
I'm only dealing with logic gates and flip-flops. Would it be advised to reduce the number of states.

This is my current Mealy Diagram.
received_287261129318805.jpeg
Should I proceed with state diagram? And simplify the states using a implication chart?
 

KlausST

Super Moderator
Staff member
Joined
Apr 17, 2014
Messages
18,391
Helped
4,104
Reputation
8,208
Reaction score
4,036
Trophy points
113
Activity points
121,079
Hi,

my practical solution is to use a shift register a couple of inverters and a couple of gates.

01110011
01000010

1) green: 5 input AND gate with 3 inverters
2) blue: 3 input AND gate
3) orange: 3 input NOR gate
4) upper sequence: 1_out AND 2_out
5) lower sequence: 2_out AND 3_out

there will be a lot of other ways...

Klaus
 

Akanimo

Advanced Member level 2
Joined
Aug 30, 2016
Messages
683
Helped
124
Reputation
248
Reaction score
122
Trophy points
43
Activity points
4,664
Hi,

This is another way to make the comparison. Take the upper bit string as (X7 X6 X5 X4 X3 X2 X1 X0) and the lower bit string as (Y7 Y6 Y5 Y4 Y3 Y2 Y1 Y0).
Connect as follows: X7 NOR Y7; X6 AND Y6; X5 AND (X5 XOR Y5); X4 AND (X4 XOR Y4); X3 NOR Y3; X2 NOR Y2; X1 AND Y1; X0 AND (X0 XOR Y0) to obtain (Z7 Z6 Z5 Z4 Z3 Z2 Z1 Z0).
Connect (Z7 AND Z6 AND Z5 AND Z4 AND Z3 AND Z2 AND Z1 AND Z0) to obtain A.
Anytime A has the bit value '1' then you have had the sequence in succession.

But then, we should have two registers, X and Y, and we should always replace the content of X with the content of Y, so that we can have successive bit strings for the comparison as illustrated above.

From the values of the bits in the sequence, it is obvious that the bit string Y is moved into corresponding positions of bit string X every clock cycle (i.e. the registers are PIPO), else it would not be possible for the sequence to be in succession. Or if the bit strings are serial, then the sequence cannot possibly be in succession after a single clock cycle. You just didn't clarify this part though.
--- Updated ---

I have noticed that my solution has the same number of gates as that of Klaus. It seems like with my solution the number of gates cannot be reduced but taking a hard look at Klaus' solution reveals that the number of gates can be reduced, making Klaus' solution a better one.

So how can the number of gates be reduced in Klaus' solution? If we keep every other thing intact but have:
1) 5 input NOR gate with two inverters. Note that you will have two sets of this. One set for the upper and one set for the lower.

If the intention is to write a structural HDL code, then the number of gates can be even further reduced by making
1) 10 input NOR gate with four inverters.
 
Last edited:

noobeestudent

Member level 1
Joined
Jul 4, 2019
Messages
37
Helped
0
Reputation
0
Reaction score
0
Trophy points
6
Activity points
287
I think I was not clear with my question.
The bits are to entered into the machine 1 by 1, thus every correct bit will move in onto the next state.
The sequences I need to detect are 0111 0011 and 0100 0010.
Overlapping patterns are allowed.

1605937090835.png
It is supposed to be like this but with 8 bit sequences instead of 4 bit.

I hope that this can help to you to understand better.
Thanks in advance for your help.
 
Last edited:

KlausST

Super Moderator
Staff member
Joined
Apr 17, 2014
Messages
18,391
Helped
4,104
Reputation
8,208
Reaction score
4,036
Trophy points
113
Activity points
121,079
Hi,

Is this a practical task or a school project?

Klaus
 

KlausST

Super Moderator
Staff member
Joined
Apr 17, 2014
Messages
18,391
Helped
4,104
Reputation
8,208
Reaction score
4,036
Trophy points
113
Activity points
121,079
Hi,

So, then the task is to use Mealy...
School is long time ago for me, and I can't remember Mealy at all.

Thus I guess I'm not of much help.

Klaus
 

noobeestudent

Member level 1
Joined
Jul 4, 2019
Messages
37
Helped
0
Reputation
0
Reaction score
0
Trophy points
6
Activity points
287
This is the updated mealy diagram after i found some errors on the previous one
1605950265485.png
 

vGoodtimes

Advanced Member level 4
Joined
Feb 16, 2015
Messages
1,089
Helped
306
Reputation
612
Reaction score
302
Trophy points
83
Activity points
8,730
The practical solution is to use the shift-reg as previously mentioned. I think this is the case for most fixed-length pattern detectors. But the goal of the school project is to learn a bit about FSM's, not to overcomplicate the problem to the point a FSM is the only solution.

I only get 13 states: s00, s11, s22, s30, s40, s51, s61, s72, s13, s14, s15, s16, s27. Where the first digit is the number of bits matched on pattern1, second digit is number matched on pattern2. For a mealy machine -- where the match outputs can use the input bit -- there is no need for a s18 or s80.

I think these are S8, S14 in your diagram. They are not needed for the mealy machine and perhaps that is the intended lesson. Notice the example 4b detector only has states for 0, 00, 000, 001 -- not 0001 nor 0010.
 

Toggle Sidebar

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Top