why an FSM is not a counter?!

[Alessandro Basili]

After some study and a lot of discussions with colleagues and friends I
would like to pin down the reasons why I have always believed that a
finite state machine (FSM) _is not_ a counter and at the same time try
to explain why a counter is a very special FSM (hope the thread will not
be too hot!).
I will start with my definitions and proceed with conclusions.

_Definition_: an FSM is a mathematical abstraction used to describe a
particular process or model. It consists of states which carry no
information about the history of the process (*1*) and of arcs which
define the conditions to move from one state to another one.
*note*: every state may have multiple incoming arcs and multiple
outgoing arcs.

Formally one can say the following: given a set of states S and a set of
inputs I, it exists s_next = f(s_curr, i) which belongs to S (where i
belongs to I and s_curr belong to S).

Iff (not a typo) the function f(s, i) = f(i) for each state s, then our
FSM is describing a counter, since there are no multiple
outgoing/incoming arcs in any state. Every state is the same and next
state is only function of the input (so called "event").
In this case we can not only determine what will be the next state but
also the "previous state" (since it will be the nth-1 next state where n
is the periodicity of the counter).

Usually, together with the description of the states and the arcs, comes
a description of the output function, where the outputs may be a
function of the inputs and/or the current state (Mealy/Moore). In this
case the behavioral model of a process does not need any additional
information to be described.

_Definition_: a counter is a device which stores the number of times a
particular event has occurred since a certain moment in time.

Given this definition we cannot define multiple arcs from one state of
the counter to the other, since they are all the same. Therefore some
additional information (=states) would be needed to define the
behavioral model of the process.

Strictly speaking I should say that an FSM and a counter are completely
different objects, sitting on different levels. An FSM is a "way" to
describe a process such that given the state it is possible to predict
the next state of the process according to the current inputs.
A counter can not model anything, it can simply count the number of events.

IMHO whenever there is a need of a sequence of actions (set/reset bits
or outputs) that is "fixed", a counter may be handy, even though most of
the times the sequence inherit a structure that is best described with
an FSM.

Any comment is appreciated!

Al

(*1*) think about the liquid state of a material, like water. Given its
state it is not possible to determine whether it came from ice or from
gas. Same may happen in a logical device like a flip-flop, it is not
possible to know the previous state unless we stored the history of the
input, while it is possible to know the next state given the current
input. These considerations may be helpful when we are considering
phenomena which may upset the state of a register accidentally and
putting our system at risk.

--
Alessandro Basili
CERN, PH/UGC
Electronic Engineer

 

[glen herrmannsfeldt]

Alessandro Basili <alessandro.basili@cern.ch> wrote:

After some study and a lot of discussions with colleagues and friends I
would like to pin down the reasons why I have always believed that a
finite state machine (FSM) _is not_ a counter and at the same time try
to explain why a counter is a very special FSM (hope the thread will not
be too hot!).

_Definition_: an FSM is a mathematical abstraction used to describe a
particular process or model. It consists of states which carry no
information about the history of the process (*1*) and of arcs which
define the conditions to move from one state to another one.
*note*: every state may have multiple incoming arcs and multiple
outgoing arcs.

With the usual definition, a digital computer is a (very complicated)
finite state machine.

(snip)

_Definition_: a counter is a device which stores the number of times a
particular event has occurred since a certain moment in time.

Given this definition we cannot define multiple arcs from one state of
the counter to the other, since they are all the same. Therefore some
additional information (=states) would be needed to define the
behavioral model of the process.

Okay, but consider even the 7493, pretty early in the TTL line.
That is, if I remember right, a loadable synchronous up/down counter.
On any clock cycle, you can load a new count, increment,
decrement, or keep the count constant. In your arc sense,
up, down, and stay the same are three arcs into, and out of,
each state. But load allows you to go from any state to any
other state!

Strictly speaking I should say that an FSM and a counter are completely
different objects, sitting on different levels. An FSM is a "way" to
describe a process such that given the state it is possible to predict
the next state of the process according to the current inputs.
A counter can not model anything, it can simply count the number of events.

It seems to me that counters can be a lot more complex that you
indicate. Note that with an up/down counter, you lose history if
up/down can change, or if load was active.

-- glen

 

[backhus]

On 14 Feb., 23:17, Alessandro Basili <alessandro.bas...@cern.ch>
wrote:

After some study and a lot of discussions with colleagues and friends I
would like to pin down the reasons why I have always believed that a
finite state machine (FSM) _is not_ a counter and at the same time try
to explain why a counter is a very special FSM (hope the thread will not
be too hot!).
I will start with my definitions and proceed with conclusions.

_Definition_: an FSM is a mathematical abstraction used to describe a
particular process or model. It consists of states which carry no
information about the history of the process (*1*) and of arcs which
define the conditions to move from one state to another one.
*note*: every state may have multiple incoming arcs and multiple
outgoing arcs.

Formally one can say the following: given a set of states S and a set of
inputs I, it exists s_next = f(s_curr, i) which belongs to S (where i
belongs to I and s_curr belong to S).

Iff (not a typo) the function f(s, i) = f(i) for each state s, then our
FSM is describing a counter, since there are no multiple
outgoing/incoming arcs in any state. Every state is the same and next
state is only function of the input (so called "event").
In this case we can not only determine what will be the next state but
also the "previous state" (since it will be the nth-1 next state where n
is the periodicity of the counter).

Usually, together with the description of the states and the arcs, comes
a description of the output function, where the outputs may be a
function of the inputs and/or the current state (Mealy/Moore). In this
case the behavioral model of a process does not need any additional
information to be described.

_Definition_: a counter is a device which stores the number of times a
particular event has occurred since a certain moment in time.

Given this definition we cannot define multiple arcs from one state of
the counter to the other, since they are all the same. Therefore some
additional information (=states) would be needed to define the
behavioral model of the process.

Strictly speaking I should say that an FSM and a counter are completely
different objects, sitting on different levels. An FSM is a "way" to
describe a process such that given the state it is possible to predict
the next state of the process according to the current inputs.
A counter can not model anything, it can simply count the number of events.

IMHO whenever there is a need of a sequence of actions (set/reset bits
or outputs) that is "fixed", a counter may be handy, even though most of
the times the sequence inherit a structure that is best described with
an FSM.

Any comment is appreciated!

Al

(*1*) think about the liquid state of a material, like water. Given its
state it is not possible to determine whether it came from ice or from
gas. Same may happen in a logical device like a flip-flop, it is not
possible to know the previous state unless we stored the history of the
input, while it is possible to know the next state given the current
input. These considerations may be helpful when we are considering
phenomena which may upset the state of a register accidentally and
putting our system at risk.

--
Alessandro Basili
CERN, PH/UGC
Electronic Engineer

Hi Allessandro,
it's true, that a finite state machine (FSM) _is not, but can be,_ a
counter and a counter is a special case of a FSM.

That in a simple counter the past and future states can be predicted
does not disqualify the counter to be an FSM.
We just have the rare situation, that all inputs at all times are
known, since there are none.
If we had that information for any other FSM, it would be the same
situation. The unpredictability and unknown state history of an FSM is
just due to the missing knowledge of the input values after reset/pon.

It is not required for an FSM to have multiple arcs going from one
state to another.
Also, it is not required for an FSM to have any output logic at all.
This is called a Medvedev state machine.

So, the most simple FSM would be a Toggle FF (or 1 bit counter if you
like).
Once you need more than two states, you have to decide.
You can either expand the number of state bits, which leads to the
common FSM architectures with a state register and a feedback logic.
Or you can connect multiple two-state-FSMs. This is done in FPGAs when
you create a One-State-Hot FSM.
(You can generate a 1 state hot code with a common FSM-architecture
too, but that would enlarge the feedback logic unneccessarily.)

Your Definition of a counter is ok, but I can't follow your
conclusions.
When the counting value has to change due to an event (which is
normally the clock) you have to store that value.
FSM states can be coded in any fashion, as long as they are well-
defined. So there's no need for an extra state beside the counting
value.
The counting value _is_ the state of that particular FSM. (reminder:
Medvedev FSM)

That a counter can not model anything also is a claim that's worth
discussion.
What do you mean by "model sth."?
A counter is a model in itself, since it is limited (Finite). The
number of events is not finite (theoretically).

Of course a simple counter for itself has no big practical use, but
that holds for most FSMs.
Even a CPU (which, as Glen states too, can be seen as a big FSM or a
bunch of FSMs) is absolutely useless for itself.
It just becomes a sense with attached Interfaces, memory and a
programm.
And as part of a CPU we also find at least one counter, the Programm
Counter, which serves to address the programm memory.

Many things that need to act repetitively in a sequential order can be
controlled by a counter.
Provided that counting can be done in any binary coding scheme.
We as humans are reluctant to accept these codes as "counting" in the
common sense, so we already accept these machines as FSMs. (And Mr.
Medvedev put his name on them. )


One more thing about the predictability of a counter.
Due to it's limitation, you can only trace back it's history up to a
certain point. It's initial value.
Before that, you cant tell if it has already counted a number of
cycles, or if it had started at just that time.
And even if it had counted some full cycles before, you can't tell how
many. That information is lost in time.

So there are many arguments (practical and theoretical) that validate
a counter as a (special form of) FSM.

Have a nice synthesis
Eilert

 

[RCIngham]

After some study and a lot of discussions with colleagues and friends I
would like to pin down the reasons why I have always believed that a
finite state machine (FSM) _is not_ a counter and at the same time try
to explain why a counter is a very special FSM (hope the thread will not
be too hot!).

<snip>

Why has it taken you so long to work this out?



---------------------------------------
Posted through http://www.FPGARelated.com

 

[Alessandro Basili]

On 2/14/2011 5:35 PM, glen herrmannsfeldt wrote:
[snip]

Okay, but consider even the 7493, pretty early in the TTL line.
That is, if I remember right, a loadable synchronous up/down counter.
On any clock cycle, you can load a new count, increment,
decrement, or keep the count constant. In your arc sense,
up, down, and stay the same are three arcs into, and out of,
each state. But load allows you to go from any state to any
other state!

That is correct, in the sense that a synchronous load will enable the
counter to move wherever we want, but that means we need additional
logic for the load signal which cannot be considered part the inputs,
since the latter define the event on which the counter should count.
When you say up/down and "stay the same", you are including extra logic
which would be necessary to describe in order to explain what your
counter is doing.

Strictly speaking I should say that an FSM and a counter are completely
different objects, sitting on different levels. An FSM is a "way" to
describe a process such that given the state it is possible to predict
the next state of the process according to the current inputs.
A counter can not model anything, it can simply count the number of events.

It seems to me that counters can be a lot more complex that you
indicate. Note that with an up/down counter, you lose history if
up/down can change, or if load was active.

I agree that counters may be "controlled" in various ways, which will
change their behavior. Whenever we change, with a control set of signals
(not the set of inputs which will make the counter count), the content
of the counter and/or the direction of the counting, we are defining a
new moment in time.

> -- glen

 

[Alessandro Basili]

On 2/15/2011 3:31 AM, backhus wrote:
[snip]

That in a simple counter the past and future states can be predicted
does not disqualify the counter to be an FSM.

Never stated that.

We just have the rare situation, that all inputs at all times are
known, since there are none.

I didn't understand what you mean about that. What do you mean with
"since there are none"?

If we had that information for any other FSM, it would be the same
situation. The unpredictability and unknown state history of an FSM is
just due to the missing knowledge of the input values after reset/pon.

I'm sorry but I didn't get that. The "unpredictability of the history"
is somehow hard to explain, since the history is already in the past and
there is very little to predict.
On the contrary, the lack of knowledge of the previous state in an FSM
is due to the fact that a state may be reached throughout several arcs
and it would be needed to store all the inputs (iff all the states are
controllable!) to understand through which state the fsm went through.
You can essentially move only forward in time, never backward (otherwise
that would mean the function f, which indeed is a matrix, can be
inverted and we know it can not since there is more than one arc to
follow backward).

It is not required for an FSM to have multiple arcs going from one
state to another.
Also, it is not required for an FSM to have any output logic at all.
This is called a Medvedev state machine.

I agree, that is why I said "usually" when referring to the output

function, since I didn't want to go into a very hazy region of the
semiautomatons and stuff like that.
To be more precise though, I ought to say that a Medvedev state machine
is a state machine where the outputs are the states themselves.
Mealy and Moore FSM are nevertheless FSM where the output function is
defined and yet they are not a Medvedev state machine.

Your Definition of a counter is ok, but I can't follow your
conclusions.
When the counting value has to change due to an event (which is
normally the clock) you have to store that value.

What so special in storing the value?
By the way, a clock is a peculiarity of the technology you use, I would
say normally you don't count clocks but number of events (which you may,
or may not synchronize with an internal clock signal to set the pace of
your machine).

That a counter can not model anything also is a claim that's worth
discussion.
What do you mean by "model sth."?

A model of "something" is an abstract representation of the behavior of
that "something". In the 18th century, prior the studies of mr. Joule,
it was believed that a caloric fluid was moving from a hot body to a
cold one, changing their temperatures. That is a (wrong) model of a
phenomenon.

A counter is a model in itself, since it is limited (Finite). The
number of events is not finite (theoretically).

I don't see the implication between "being limited" and "being a model".
A counter cannot be a model, since it doesn't describe anything except
itself. While an FSM can describe the behavior of a counter.

Of course a simple counter for itself has no big practical use, but
that holds for most FSMs.
Even a CPU (which, as Glen states too, can be seen as a big FSM or a
bunch of FSMs) is absolutely useless for itself.
It just becomes a sense with attached Interfaces, memory and a
programm

A counter for itself may have big practical use, depending on the type
of events you are counting, especially when we compare with a fixed time
window.
The flux of a particular event is the first type of measurement that
comes to my mind, distribution may be measured with a counter as well.

What you say about the "sense" of an FSM I don't actually get. A
communication protocol may (and probably should) be described as an FSM,
so here is an example of its great use.

An FSM describes exactly what kind of output you should expect once you
know the state and the inputs, so for practical use it is of a
fundamental importance, since it gives the possibility to predict the
behavior of your system.
Without the set of inputs and *possibly* a set of output an FSM does not
exist.

Many things that need to act repetitively in a sequential order can be
controlled by a counter.
Provided that counting can be done in any binary coding scheme.

Why a "binary coding scheme"? Can a counter count in heptadecimal base?
I think so. Why this mix between semantic and syntax?

One more thing about the predictability of a counter.
Due to it's limitation, you can only trace back it's history up to a
certain point. It's initial value.
Before that, you cant tell if it has already counted a number of
cycles, or if it had started at just that time.
And even if it had counted some full cycles before, you can't tell how
many. That information is lost in time.

I'm not arguing about the possibility to predict, but about the
possibility to know what was the previous state. Formally you can always
trace back up to the initial time (by definition time does not exist
before the initial time!), this is the only thing you can do and the
only you are interested into, otherwise you wouldn't have changed the
initial time.

So there are many arguments (practical and theoretical) that validate
a counter as a (special form of) FSM.

A counter and a FSM happen to be the same iff the FSM has a very

peculiar form.
The same, by the way, applies to a shift-register, so why nobody
advocates for the shift-register rights to be an FSM? A matter of
technological discrimination?

Have a nice synthesis

Thanks for the time you spent, I appreciated your comments.

Eilert

 

[-jg]

On Feb 15, 11:35 am, glen herrmannsfeldt <g...@ugcs.caltech.edu>
wrote:

Alessandro Basili <alessandro.bas...@cern.ch> wrote:
After some study and a lot of discussions with colleagues and friends I
would like to pin down the reasons why I have always believed that a
finite state machine (FSM) _is not_ a counter and at the same time try
to explain why a counter is a very special FSM

You have self-contradicted already.

FSM stands for Finite State Machine : aka Something with finite
states.
It does not claim any more than that.

There are also many different counters, and counters can be designed
using FSM design entry.

Counters do not HAVE to include entry paths for all possible binary
states, and nor do FSMs
It's considered a good idea to have an exit from all possible binary
states, but that is up to the designer.

Once you have an Up/Down/Saturate/Load/Modulous counter, you also have
multiple pathways to your chosen states, and dependent exit states
too, so that's Pretty much described most common FSM's.

The rest is merely an exercise in semantics.

-jg

 

[Andy]

On Feb 15, 4:13 am, "RCIngham" >

Why has it taken you so long to work this out?

Amen!

BIG NEWS! All counters are FSMs. Not all FSMs are counters.

Do we need a dissertation to tell us this? Really?

Andy

 

[Alessandro Basili]

On 2/16/2011 4:54 PM, Andy wrote:

On Feb 15, 4:13 am, "RCIngham"
Why has it taken you so long to work this out?

Amen!

BIG NEWS! All counters are FSMs. Not all FSMs are counters.

Do we need a dissertation to tell us this? Really?

Apologies, I just "sensed" that was not clear to every one.
But I am glad I was wrong.
Amen!

> Andy

 

[Mike Treseler]

After some study and a lot of discussions with colleagues and friends I
would like to pin down the reasons why I have always believed that a
finite state machine (FSM) _is not_ a counter and at the same time try
to explain why a counter is a very special FSM (hope the thread will not
be too hot!).

This is indeed a job for the python argument clinic:
http://www.youtube.com/watch?v=teMlv3ripSM

-- Mike Treseler

 

[Thomas Entner]

On 18 Feb., 02:58, Mike Treseler <mtrese...@gmail.com> wrote:

After some study and a lot of discussions with colleagues and friends I
would like to pin down the reasons why I have always believed that a
finite state machine (FSM) _is not_ a counter and at the same time try
to explain why a counter is a very special FSM (hope the thread will not
be too hot!).

This is indeed a job for the python argument clinic:http://www.youtube.com/watch?v=teMlv3ripSM

       -- Mike Treseler

No, it isn't!

 

[Gabor]

Yes it is!