debounce state diagram FSM

[Anson.Stuggart]

Anson, thanks for the explanation. Regarding SEE01 and SEE10 states,
that is right we won't need them and I read what John had said before
again and he is right.

But let's get back to the first input in the string which is "1" .
There, we can get to this conclusion that the previous value that
system was expecting to have as output has been "0" so the first input
(1) must be the third "1" of triple 1 string. Maybe following lines
explain it better:

hidden We
see
input: 11
10010100010111
output: 00
11111111000001

Right?

next question I have is regarding your very first question. What
happens to the state that once outputs "1" and in another situation it
outputs "0"?

how do you present this in your state diagram? If I'm not wrong this
is what you has asked in the first place.

Regards,
amit- Hide quoted text -

- Show quoted text -

Amit,

My first question came up because I draw the state diagram differently
or wrong. From state SEE000 and if a 1 is input, it will go to state
SEE1 and if another 0 comes in, it should go back to SEE000, not on to
SEE0 (where I get the wrong output).

Try to draw or map out the state diagram John has posted earlier. And
try to trace it with the input you have and you will get the correct
outputs at every single state or bit. However, I must highlight what
John wrote earlier. During the initial input at power-on, the first
bit should go to: if 1 go to state SEE111 and if 0 go to SEE000. As
you can see, state SEE111 and SEE000 serve two function. One is when
it sees 3 consecutive same bits it will change the output and other is
during initial bit at power-on (maybe they should be renamed to
Init_1&SEE111, Init_0&SEE000). Don't forget the reset which will set
output to 1 regardless of what's on the line but this will be changed
with sequences of bits streaming in later.

Hope this helps,

Anson

 

[billwang05]

it seems what I have typed above is messy and mixed. This is what I
was trying to show:

hidden We only see

11 10010100010111 <- input
00 11111111000001 <- output

regards,
amit- Hide quoted text -

- Show quoted text -

Do you mean a 1 in the input string at power-up or after reset? If so,
state Init_1&SEE111 is where it should go.

 

[jens]

Thanks Peter for the suggestion. But my problem is coming up with the

state diagram for this FSM. How can I implement what you suggested on
a state diagram? Thanks.

Here you go, I hope the ASCII art looks OK (if not, change to
monospaced font):

shift reg. = 111
+----+ --------------------> +----+
| S0 | | S1 |
+----+ <-------------------- +----+
shift reg. = 000

 

[petrus bitbyter]

I'm designing a debounce filter using Finite State Machine. The FSM
behavior is it follows the inital input bit and thinks that's real
output until it receives 3 consecutive same bits and it changes output
to that 3 consecutive bit until next 3 consecutive bits are received.
A reset will set the FSM to output 1s until it receives the correct
input and ouput.

This is the test sequence with input and correct output.

1 0 0 1 0 1 0 0 0 1 0 1 1 1 (input)
1 1 1 1 1 1 1 1 0 0 0 0 0 1 (output)

The state diagram I came up has 6 states and it's named SEE1, SEE11,
SEE111, SEE0, SEE00, SEE000. I am getting stuck at 11th bit, a 0 in
the input. Because it just came from SEE1 and before SEE1, it came
from SEE000, so at SEE1 it can not change ouput to 1 which is what I
have specified that state's ouput to be.

Anyone knows how to solve this problem? Or maybe there's other better
ways to design the state diagram?

Thanks,

Anson

Came into this this discussion late. Read the available texts but sure
missed some due to the "experimental" status of my ISPs newsserver. Also did
not analyse the tables to make sure I make my own mistakes So I came to
the next table:

Input Curent Next
state state
0 000 000
1 000 001
0 100 000
1 100 001
0 001 000
1 001 011
0 011 000
1 011 110
0 110 111
1 110 110
0 010 111
1 010 110
0 111 101
1 111 110
0 011 000
1 101 110
0 101 000

All possible (eight) states have been accounted for. As you need only six
states, you can combine state 000 with state 100 and state 110 with state
010. The leftmost bit of the state code is your output signal. See state
diagram below.

+--+
0| |
| v
.------.
| 000 |----------+
+--------->| 100 | |
| | |<------+ |
|0 '------' | |1
| ^ 0| |
| | | v
.------. |0 .------.
| | | | |
| 101 | | | 001 |
| |---------+ | | |
'------' | | '------'
^ | | |
| | | |1
|0 | | |
| | | v
.------. | | .------.
| | | +-------| |
| 111 | | | 011 |
| | | | |
'------' 1| '------'
^ | | |
| | v |
0| |1 .------. |1
| +-------->| | |
| | 110 |<------+
+------------| 010 |
'------'
| ^
1| |
+--+
created by Andy´s ASCII-Circuit v1.24.140803 Beta www.tech-chat.de

petrus bitbyter

 

[jpopelish]

It was a bit larger than I remembered, but if anyone is interested,
here is the code I used to debounce and edge detect an 8 bit PIC
port. This process was called once a millisecond.

; read port C, debounce and fire single shots
; shift input data down
movf cinfil,w ; fetch cinfil
movwf cinfil1 ; copy to cinfil1
bsf STATUS,RP0 ; select regiater page 1
movf cin1,w ; fetch 1ms old values
movwf cin2 ; overwrite 2ms old data
movf cin,w ; fetch stale value of cin
movwf cin1 ; store as 1ms old data
bcf STATUS,RP0 ; select regiater page 0
; read new port C values
movf PORTC,w ; read port C
bsf STATUS,RP0 ; select register page 1
movwf cin ; store port C data in cin
; (0=start, 1=up, 2= down, 3=home, 4=temp high not, 5=temp low not,
6=lid closed, 7=spare)
; debounce requires 3 similar states in a row to supercede filtered
value
; and cin, cin1 and cin2 to detect 3 1s in a row
andwf cin1,w ; and 1 ms old data with new version
andwf cin2,w ; and 2 ms old data with this
movwf cinand ; save this combination for later
; or cin, cin1 and cin2 to detect three 0s in a row
movf cin,w ; get latest values
iorwf cin1,w ; or latest and 1ms old data
iorwf cin2,w ; or 2 ms old data with this
andwf cinfil1,w ; and debounced state of port C inputs with this
; to clear any 1s that have been followed by 3 0s in a row.
iorwf cinand,w ; or cinand, to set any zeros that have been followed
; by 3 1s in a row.
movwf cinfil1 ; update filtered (debounced version of port C inputs)
bcf STATUS,RP0 ; select register page 0
movwf cinfil ; update filtered (debounced version of port C inputs)
bsf STATUS,RP0 ; select register page 1
; fire turn on and turn off single shots
; if present is off and last was on, set "off ss" bit
comf cinfil1,w ; compliment cinfil bits
andwf cinfld,w ; and with delayed bits
bcf STATUS,RP0 ; select register page zero
movwf cinofss ; store as turn off single shot bits
bsf STATUS,RP0 ; select register page 1
; if last was off, and present is on, set "on ss" bit
comf cinfld,w ; compliment delayed inputs
andwf cinfil1,w ; and current value of inputs
bcf STATUS,RP0 ; select register page 0
movwf cinonss ; store as turn on single shot bits

 

[Default User]

It was a bit larger than I remembered, but if anyone is interested,
here is the code I used to debounce and edge detect an 8 bit PIC
port. This process was called once a millisecond.

None of this is topical in comp.lang.c. Please remove that group from
your distribution. Thanks.





Brian

 

[Flash Gordon]

(e-mail address removed) wrote, On 30/04/07 04:42:

Do you mean a 1 in the input string at power-up or after reset? If so,
state Init_1&SEE111 is where it should go.

Would people PLEASE drop comp.lang.c from the groups, as this is
OBVIOUSLY not topical in a C programming group.

 

[John Popelish]

petrus bitbyter wrote:
(snip)

All possible (eight) states have been accounted for. As you need only six
states, you can combine state 000 with state 100 and state 110 with state
010. The leftmost bit of the state code is your output signal. See state
diagram below.

+--+
0| |
| v
.------.
| 000 |----------+
+--------->| 100 | |
| | |<------+ |
|0 '------' | |1
| ^ 0| |
| | | v
.------. |0 .------.
| | | | |
| 101 | | | 001 |
| |---------+ | | |
'------' | | '------'
^ | | |
| | | |1
|0 | | |
| | | v
.------. | | .------.
| | | +-------| |
| 111 | | | 011 |
| | | | |
'------' 1| '------'
^ | | |
| | v |
0| |1 .------. |1
| +-------->| | |
| | 110 |<------+
+------------| 010 |
'------'
| ^
1| |
+--+
created by Andy´s ASCII-Circuit v1.24.140803 Beta www.tech-chat.de

petrus bitbyter

This is exactly the state diagram I drew before answering
the post. Nice work.

 

[Default User]

This is exactly the state diagram I drew before answering
the post. Nice work.

This has nothing to do with comp.lang.c. Please remove that newsgroup
from your distribution.




Brian

 

[John Popelish]

This has nothing to do with comp.lang.c. Please remove that newsgroup
from your distribution.

I don't know where the original poster is reading this thread.

You could make this discussion relevant by translating the
algorithm into C.

 

[petrus bitbyter]

This has nothing to do with comp.lang.c. Please remove that newsgroup
from your distribution.




Brian

FAIK the OP was asking about the design of a finite state machine. Nothing
said about the implementation. C is a perfect language to build finite state
machines. The solution can for instance be implemented in a microcontroller
using C, most likely as a part of a larger design. (Although I'd prefer
assembler for small programs.) It can be implemented the same way in
programmable hardware using VHDL or Verilog. As a matter of fact, it is so
simple you can even implement it using old fashioned devices with flipflops
and gates. I can build all this possibilities plus some I did not mention.
Still complaints?

petrus bitbyter

 

[Robin]

I'm designing a debounce filter using Finite State Machine. The FSM
behavior is it follows the inital input bit and thinks that's real
output until it receives 3 consecutive same bits and it changes output
to that 3 consecutive bit until next 3 consecutive bits are received.
A reset will set the FSM to output 1s until it receives the correct
input and ouput.

This is the test sequence with input and correct output.

1 0 0 1 0 1 0 0 0 1 0 1 1 1 (input)
1 1 1 1 1 1 1 1 0 0 0 0 0 1 (output)

The state diagram I came up has 6 states and it's named SEE1, SEE11,
SEE111, SEE0, SEE00, SEE000. I am getting stuck at 11th bit, a 0 in
the input. Because it just came from SEE1 and before SEE1, it came
from SEE000, so at SEE1 it can not change ouput to 1 which is what I
have specified that state's ouput to be.

Anyone knows how to solve this problem? Or maybe there's other better
ways to design the state diagram?

Thanks,

Anson

This debounce idea is terrible. Straight away you have aliasing
problems not to mention arbitrary latency.

The simple thing to do is detect an edge by e.g. edge driven interrupt
and then fire the output state immediately according to the edge
direction and start your one-shot debounce-duration timer that
inhibits the interrupt until it times outs.

Now you have instant "analogue" style response and you can reduce the
duration until bouncing happens and then back it off by a safety
margin.

Cheers
Robin

 

[John Popelish]

This debounce idea is terrible. Straight away you have aliasing
problems not to mention arbitrary latency.

For many debounce situations, latency is no problem at all.
What may be more important is to ignore narrow pulses that
represent static discharges or other noise coupled into the
input. Instant reaction is not always a good thing. Have
you ever had to pass a static discharge test on a key pad?

(snip)

 

[John Larkin]

For many debounce situations, latency is no problem at all.
What may be more important is to ignore narrow pulses that
represent static discharges or other noise coupled into the
input. Instant reaction is not always a good thing. Have
you ever had to pass a static discharge test on a key pad?

(snip)

If esd is not an issue, debouncing can be just running the switch
level through a d-flop that's clocked at, say, 20 Hz. And if the
switch is going into an embedded processor or equivalent, don't even
do that: just check it 20 times a second.

If esd is an issue, you may need a real r-c before you hit any
semiconductors. So do the r-c, then the stuff above.

John

 

[jasen]

Obviously wrong.

what's wrong with it?

the labels on the states seem odd, but if you do this:

initial state 010

state output.
000,001,011,100 0
110,010,111,101 1

it behaves as requested,

Bye.
Jasen

 

[petrus bitbyter]

This debounce idea is terrible. Straight away you have aliasing
problems not to mention arbitrary latency.

The simple thing to do is detect an edge by e.g. edge driven interrupt
and then fire the output state immediately according to the edge
direction and start your one-shot debounce-duration timer that
inhibits the interrupt until it times outs.

Now you have instant "analogue" style response and you can reduce the
duration until bouncing happens and then back it off by a safety
margin.

Cheers
Robin

As so often, it depends. Ever met some "designers" having terrible problems
with the start button of their coffee machine. It made the coffee well
enough but started too often spontanuously. They connected the button to the
only interrupt line of their micro. The interrupt routine started the proces
on the first edge detected. Being mainly (C)programmers, it took some time
to convince them that false starts may occur due to interferences made by
the environment, even if you do not notice them yourself. But they did
understand that humans would not complain when the coffee maker started some
milliseconds later so they build in some delay and checked again. (IMHO a
typical example of too strict a separation of hard- and softwaredesign.)

petrus bitbyter

 

[Keith Thompson]

So repeated requests to redirect this discussion away from
comp.lang.c, where it's completely off-topic, have not worked. Does
anybody have any suggestions for what *would* work?

 

[John Larkin]

As so often, it depends. Ever met some "designers" having terrible problems
with the start button of their coffee machine. It made the coffee well
enough but started too often spontanuously. They connected the button to the
only interrupt line of their micro. The interrupt routine started the proces
on the first edge detected. Being mainly (C)programmers, it took some time
to convince them that false starts may occur due to interferences made by
the environment, even if you do not notice them yourself. But they did
understand that humans would not complain when the coffee maker started some
milliseconds later so they build in some delay and checked again. (IMHO a
typical example of too strict a separation of hard- and softwaredesign.)

petrus bitbyter

Interrupts are evil. They should have used a state machine that ran,
say, 5 times a second and checked the switch state.

John

 

[John Larkin]

So repeated requests to redirect this discussion away from
comp.lang.c, where it's completely off-topic, have not worked. Does
anybody have any suggestions for what *would* work?

Programming embedded systems, things that interface to the real world,
are off-topic to c programmers? Why am I not surprised?

John

 

[Keith Thompson]

Set follow-ups.

I did, but it didn't do any good. I could only set followups in my
own followup; other direct replies to the original message retained
the full cross-posting.