Puzzle #7 – Transitions

July 17, 2007

It’s time for puzzle #7.

An FSM receives an endless stream of “0”s and “1”s. The stream can not be assumed to have certain properties like randomness, transition density or the like.

Is it possible to build a state machine, which at any given moment outputs whether there were more 0–>1 or 1–>0 transitions so far?

If yes, describe briefly the FSM. If no, give a short proof.

4 comments

1. You don’t need an FSM, except perhaps one with two states (a single flop) to retain the initial input state since you didn’t define it.

Initial input Current input output
————- ————- —————-
0 0 equal
0 1 more 0->1
1 0 more 1->0
1 1 equal

2. Because after a 0->1 transition there must be a 1->0 transition and vice versa. (No 0->1 transition can be followed directly by another 0->1 transition. The same holds for 1->0 transitions.)

Therefore one needs to store the 1st received bit and compare it to the actual one. If the stored bit value is equal to the actual one, the number of 0->1 and 1->0 transitions are equal.
Otherwise there is one more 0->1 transition, if the actual bit value is ‘1’.
Otherwise there is one more 1->0 transition if the actual bit value is ‘0’.

3. That is completely correct.
It was a trick question. I tried to formulate it in such a way so one would think an infinite amount of memory is needed.

Try to compare it with the FSM that identifies a palindrome on a serial input.

I will post an “official” solution a bit later.

4. but a fsm needs a clock which will have some defined frequency,

but the problem comes when we don’t know the frequency of the data change ,which may be more than the clock frequency of the fsm.

i was faced with the same problem like this

a rotating disk which was painted black for 180 degrees and white for 180 degrees ,
a ideal sensor is monitoring the disk’s rotation

we cannot use clock , because the disk may rotate at 0 to some mega RPM
and we don’t know the max RPM

we should say whether we are monitoring white or black region at present

answer

use a two toggle flip flops (one posedge and one negedge) and give the sensor output to the clock pins of the two flops