debounce state diagram FSM

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

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

On Apr 29, 11:32 am, Anson.Stugg...@gmail.com wrote:
> 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

On Apr 29, 11:45 am, Peter Alfke <a...@sbcglobal.net> wrote:
> 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
>
> On Apr 29, 11:32 am, Anson.Stugg...@gmail.com wrote:
>
>
> 
> 
> 
> 
> 
> 
> 
>
> - 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

Anson.Stuggart@gmail.com wrote:
> 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

On Apr 29, 12:32 pm, Anson.Stugg...@gmail.com wrote:
> 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

Peter Alfke wrote:
> 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.

On Apr 29, 12:01 pm, John Popelish <jpopel...@rica.net> wrote:
> Anson.Stugg...@gmail.com wrote: 
> 
> 
> 
> 
>
> 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!

Anson.Stuggart@gmail.com wrote, On 29/04/07 19:32:
> I'm designing a debounce filter using Finite State Machine. The FSM

<snip>

> 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.
--
Flash Gordon

Anson.Stuggart@gmail.com writes:
> 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.

--
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center             <*>  <http://users.sdsc.edu/~kst>
"We must do something.  This is something.  Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

> 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->     |   '--/ /__/
.            |     |
.             -----
.
.
.