debounce state diagram FSM

[Anson.Stuggart]

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

 

[Peter Alfke]

My suggestion:
Feed the input into a 3-bit shift register.
Detect all-ones (111) and used that signal to set a latch,
detect all-zeros (000) and use that signal to reset a latch.
The latch is your de-bounced signal.
Peter Alfke

 

[billwang05]

My suggestion:
Feed the input into a 3-bit shift register.
Detect all-ones (111) and used that signal to set a latch,
detect all-zeros (000) and use that signal to reset a latch.
The latch is your de-bounced signal.
Peter Alfke







- Show quoted text -

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.

Anson

 

[Mike Treseler]

maybe there's other better
ways to design the state diagram?

I wouldn't use a state diagram at all.
Just a 4 bit shift_left.
The value "0111" sets the output.
"1000" clears it.

-- Mike Treseler

 

[John Popelish]

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?

I'm not sure I understand your terminology, but I am
assuming that that state neames mean:

SEE1 = output = 0 after 1 has been input 1 times in a row.

SEE11 = output = 0 after 1 has been input 2 times in a row.

SEE111 = output = 1 after 1 has been input 3 times in a row
(or a 1 is input after 0 has been input less than 3
times in a row).

SEE0 = output = 1 after 0 has been input 1 times in a row.

SEE00 = output = 1 after 0 has been input 2 times in a row.

SEE000 = output = 0 after 0 has been input 3 times in a row
(or a 0 is input after 1 has been input less than 3
times in a row).

If this is the case, then the 12 transitions are:

before input after
SEE1 1 SEE11
SEE1 0 SEE000
SEE11 1 SEE111
SEE11 0 SEE000
SEE111 1 SEE111
SEE111 0 SEE0
SEE0 1 SEE111
SEE0 0 SEE00
SEE00 1 SEE111
SEE00 0 SEE000
SEE000 1 SEE1
SEE000 0 SEE000

 

[John O'Flaherty]

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?

A counter counts toward 3 as long as the input state stays the same.
Any change resets the counter to zero. On reaching 3, the counter
enables the last occurring input state to be latched to the output.
That is, instead of counting ones or zeros, count all clocks, with any
input change resetting the counter.

 

[John Popelish]

My suggestion:
Feed the input into a 3-bit shift register.
Detect all-ones (111) and used that signal to set a latch,
detect all-zeros (000) and use that signal to reset a latch.
The latch is your de-bounced signal.

That is exactly the way I do it with PIC code, a whole port
at a time, in parallel. I also generate additional bytes
that indicate a change of state of any of the port inputs
from 1 to 0 and 0 to 1. This single shot bits are very
handy to have on the shelf when a program development needs
one. So the storage requirement is i byte each for 8:

state of raw inputs,

previous state of inputs,

twice previous state of inputs,

debounced inputs,

debounced inputs that have just transitioned to 1,

debounced inputs that have just transitioned to 0.

I don't have the code handy, but I seem to remember that it
took only something like 18 instructions to maintain this
table of bytes servicing an 8 bit port.

 

[Anson.Stuggart]

I'm not sure I understand your terminology, but I am
assuming that that state neames mean:

SEE1 = output = 0 after 1 has been input 1 times in a row.

SEE11 = output = 0 after 1 has been input 2 times in a row.

SEE111 = output = 1 after 1 has been input 3 times in a row
(or a 1 is input after 0 has been input less than 3
times in a row).

SEE0 = output = 1 after 0 has been input 1 times in a row.

SEE00 = output = 1 after 0 has been input 2 times in a row.

SEE000 = output = 0 after 0 has been input 3 times in a row
(or a 0 is input after 1 has been input less than 3
times in a row).

If this is the case, then the 12 transitions are:

before input after
SEE1 1 SEE11
SEE1 0 SEE000
SEE11 1 SEE111
SEE11 0 SEE000
SEE111 1 SEE111
SEE111 0 SEE0
SEE0 1 SEE111
SEE0 0 SEE00
SEE00 1 SEE111
SEE00 0 SEE000
SEE000 1 SEE1
SEE000 0 SEE000- Hide quoted text -

- Show quoted text -

That's it John...Thanks a lot...you're the man!

 

[Flash Gordon]

I'm designing a debounce filter using Finite State Machine. The FSM

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

You need to decide whether you will be implementing it in hardware or
software. If hardware, which I suspect from all the groups other than
comp.lang.c when why are you cross-posting to a C language group? If
software, then why post to all the other groups? Either way your
selection of groups has to be wrong.

Personally I would suggest implementing it in HW rather than SW
(although I have implemented debounce in SW a couple of times when the
HW design was broken).

Follow-ups set to exclude comp.lang.c, and I would like to request that
others replying in other parts of the thread exclude comp.lang.c unless
they are posting C related answers to this problem.

 

[Keith Thompson]

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?

This question has nothing to do with the C programming language. Why
did you post to comp.lang.c? Followups redirected.

 

[Fred Bloggs]

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?

Debouncing can come in several flavors, and from what I can gather from
your description, the debouncing should be focussed on changing the
debounced representation of the input. Something like shown below where
the OUT FF is a conditional toggle using the EXOR feedback and
conditioned to toggle or remain-the-same as a function of the three
input states prior to the active clock edge, all different from OUT
causing a toggle and one or more the same as OUT preventing the toggle:
View in a fixed-width font such as Courier.

..
..
..
.. .--------------------+----------------+->OUT
.. | | |
.. | __ | __ ----- |
.. IN>---+-----------|--\ \ \ __ '-\ \ \ | | |
.. | | | | >------| \ | | >|D Q|-'
.. | +--/ /__/ .----| >--/ /__/ | |
.. | | | .-|__/ | |
.. | | | | clk-> |
.. | ----- | | | | |
.. | | | | __ | | -----
.. '-|D Q|-+-|--\ \ \ | |
.. | | | | | | >-' |
.. clk-> | | +--/ /__/ |
.. | | | | |
.. ----- | | |
.. .---------' | |
.. | ----- | |
.. | | | | __ |
.. '-|D Q|---|--\ \ \ |
.. | | | | | >----'
.. clk-> | '--/ /__/
.. | |
.. -----
..
..
..

 

[Amit]

I'm not sure I understand your terminology, but I am
assuming that that state neames mean:

SEE1 = output = 0 after 1 has been input 1 times in a row.

SEE11 = output = 0 after 1 has been input 2 times in a row.

SEE111 = output = 1 after 1 has been input 3 times in a row
(or a 1 is input after 0 has been input less than 3
times in a row).

SEE0 = output = 1 after 0 has been input 1 times in a row.

SEE00 = output = 1 after 0 has been input 2 times in a row.

SEE000 = output = 0 after 0 has been input 3 times in a row
(or a 0 is input after 1 has been input less than 3
times in a row).

If this is the case, then the 12 transitions are:

before input after
SEE1 1 SEE11
SEE1 0 SEE000
SEE11 1 SEE111
SEE11 0 SEE000
SEE111 1 SEE111
SEE111 0 SEE0
SEE0 1 SEE111
SEE0 0 SEE00
SEE00 1 SEE111
SEE00 0 SEE000
SEE000 1 SEE1
SEE000 0 SEE000

Hi John,

It is not that I'm saying the table is wrong (since I'm new to this
and trying to learn) but how do you say: SEE1 with input 0 goes to
SEE11 state? because then our state must be SEE01!

Any comment?

 

[John Popelish]

Hi John,

It is not that I'm saying the table is wrong (since I'm new to this
and trying to learn) but how do you say: SEE1 with input 0 goes to
SEE11 state? because then our state must be SEE01!

The 6 states are defined above the transition table. There
is no SEE01 state, because there is no reason to keep track
of that sequence. If you are at SEE1 a single 1 input has
been seen since the output was decided to be zero), and a
zero arrives, you just go back to state SEE000 (the one
where the output was decided to be changed to zero) since
the required 3 1s in a row cannot occur till at least a
single 1 arrives. Any zero arriving before that triple 1 is
received just starts the count over.

 

[Amit]

The 6 states are defined above the transition table. There
is no SEE01 state, because there is no reason to keep track
of that sequence. If you are at SEE1 a single 1 input has
been seen since the output was decided to be zero), and a
zero arrives, you just go back to state SEE000 (the one
where the output was decided to be changed to zero) since
the required 3 1s in a row cannot occur till at least a
single 1 arrives. Any zero arriving before that triple 1 is
received just starts the count over.

Thank you so much for your answer but before I complete the reading I
have a problem with this:

If you are at SEE1 a single 1 input has

been seen since the output was decided to be zero), and a
zero arrives

Question: let's say we are at SEE1 and input is 1. How should I know
the system expects 0? why not 1?

Regards,
amit

 

[Amit]

Thank you so much for your answer but before I complete the reading I
have a problem with this:


been seen since the output was decided to be zero), and a
zero arrives

Question: let's say we are at SEE1 and input is 1. How should I know
the system expects 0? why not 1?

Regards,
amit

The thing I'm trying to say is that regarding what Anson says the
first input 1 has an output as 1 and .... so the system in this phase
believes "1" is the right output and we haven't got to "000" yet to
switch to "0" output.

 

[Anson.Stuggart]

The thing I'm trying to say is that regarding what Anson says the
first input 1 has an output as 1 and .... so the system in this phase
believes "1" is the right output and we haven't got to "000" yet to
switch to "0" output.- Hide quoted text -

- Show quoted text -

Amit,

I admit it is a little messy to understand. Basically, to come up with
state diagram, usually try to focus on the objective. In this case, it
is to detect 3 consecutive 1s or 0s and result a change on the output.
Therefore, case SAW01 or SAW10 will be not important enough to be
named a state.

Before the logic detects 3 of consecutive 1s or 0s, it will just keep
output bits with the inital bit received at power on or 1s in the case
if there has been a reset. There are only two logic states which
logically change the output: SEE000 and SEE111. All other states don't
really changes the outputs. These are only internal states.

I must mention that the state diagram doesn't address the issue when
the logic is first turned on and is it 1 or 0 at the input port. You
can verify this with the the state diagram John Popelish provided
earlier. The first bit is a 1 and if you follow the state diagram, you
will get 0s all the way until 9th bit and it's still a 0 so it will
continue until the last bit received. Infact, you will have to provide
additional logic for the first 8 bits.

Correct me if I'm wrong, but this is what I think.

Anson

 

[John Popelish]

Question: let's say we are at SEE1 and input is 1. How should I know
the system expects 0? why not 1?

The system does not expect anything. It reacts to the input
sequence as it arrives (at clocked intervals). The purpose
of the algorithm is to remove any state changes that remain
less than 3 clocks in a row (bounces).

 

[John Popelish]

The thing I'm trying to say is that regarding what Anson says the
first input 1 has an output as 1 and .... so the system in this phase
believes "1" is the right output and we haven't got to "000" yet to
switch to "0" output.

I ignored that part. The initial power up state is
arbitrary. Choose it as you wish, and initialize the state
to SEE000 if you choose 0 or SEE111 if you choose 1.

 

[Amit]

Amit,

I admit it is a little messy to understand. Basically, to come up with
state diagram, usually try to focus on the objective. In this case, it
is to detect 3 consecutive 1s or 0s and result a change on the output.
Therefore, case SAW01 or SAW10 will be not important enough to be
named a state.

Before the logic detects 3 of consecutive 1s or 0s, it will just keep
output bits with the inital bit received at power on or 1s in the case
if there has been a reset. There are only two logic states which
logically change the output: SEE000 and SEE111. All other states don't
really changes the outputs. These are only internal states.

I must mention that the state diagram doesn't address the issue when
the logic is first turned on and is it 1 or 0 at the input port. You
can verify this with the the state diagram John Popelish provided
earlier. The first bit is a 1 and if you follow the state diagram, you
will get 0s all the way until 9th bit and it's still a 0 so it will
continue until the last bit received. Infact, you will have to provide
additional logic for the first 8 bits.

Correct me if I'm wrong, but this is what I think.

Anson

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

 

[Amit]

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

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